DFS and BFS use 1 data array to improve spatial locality

1 files changed, 19 insertions, 22 deletions

diff --git a/src/lib/eina_graph_dfs.c b/src/lib/eina_graph_dfs.c
index 7951b3c..1b9a61a 100644
--- a/src/lib/eina_graph_dfs.c
+++ b/src/lib/eina_graph_dfs.c
@@ -38,6 +38,7 @@ _eina_graph_dfs_swalk(_Eina_Graph *_g, _Eina_Graph_DFS *_dfs, unsigned int v)
 {
    Eina_List *stack = NULL;
    _Eina_Graph_Adjacents *adjs;
+   _Eina_Graph_DFS_Data *vd;
    unsigned int p, w, n, i;
 
    p = v;
@@ -48,9 +49,10 @@ _eina_graph_dfs_swalk(_Eina_Graph *_g, _Eina_Graph_DFS *_dfs, unsigned int v)
         w = CAST_D(eina_list_data_get(stack));
         stack = eina_list_remove(stack, CAST_V(w));
 
-        if(_dfs->marked[w]) continue;
-        _dfs->marked[w] = EINA_TRUE;
-        _dfs->edge_to[w] = p;
+        vd = &_dfs->data[w];
+        if(vd->m) continue;
+        vd->m = EINA_TRUE;
+        vd->e = p;
         p = w;
 
         adjs = &_g->adjs[w];
@@ -58,7 +60,7 @@ _eina_graph_dfs_swalk(_Eina_Graph *_g, _Eina_Graph_DFS *_dfs, unsigned int v)
         for (i = 0; i < n; i++)
           {
              w =  adjs->data[i];
-             if (!_dfs->marked[w])
+             if (!_dfs->data[w].m)
                {
                   stack = eina_list_prepend(stack, CAST_V(w));
                }
@@ -70,19 +72,21 @@ static void
 _eina_graph_dfs_rwalk(_Eina_Graph *_g, _Eina_Graph_DFS *_dfs, unsigned int v)
 {
    _Eina_Graph_Adjacents *adjs;
+   _Eina_Graph_DFS_Data *vd;
    unsigned int i, n, w;
 
-   _dfs->marked[v] = EINA_TRUE;
+   _dfs->data[v].m = EINA_TRUE;
 
    adjs = &_g->adjs[v];
    n = adjs->count;
    for (i = 0; i < n; i++)
      {
         w =  adjs->data[i];
-        if (!_dfs->marked[w])
+        vd = &_dfs->data[w];
+        if (!vd->m)
           {
              _eina_graph_dfs_rwalk(_g, _dfs, w);
-             _dfs->edge_to[w] = v;
+             vd->e = v;
           }
      }
 }
@@ -97,13 +101,9 @@ eina_graph_dfs_new(Eina_Graph *g, unsigned int s, Eina_Bool r)
    if (!_dfs)
      goto error_dfs;
 
-   _dfs->marked = calloc(_g->vertices, sizeof(Eina_Bool));
-   if (!_dfs->marked)
-     goto error_marked;
-
-   _dfs->edge_to = calloc(_g->vertices, sizeof(unsigned int));
-   if (!_dfs->edge_to)
-     goto error_edge_to;
+   _dfs->data = calloc(_g->vertices, sizeof(_Eina_Graph_DFS_Data));
+   if (!_dfs->data)
+     goto error_data;
 
    _dfs->s = s;
    _dfs->vertices = _g->vertices;
@@ -115,9 +115,7 @@ eina_graph_dfs_new(Eina_Graph *g, unsigned int s, Eina_Bool r)
 
    return (Eina_Graph_DFS *) _dfs;
 
-error_edge_to:
-   free(_dfs->marked);
-error_marked:
+error_data:
    free(_dfs);
 error_dfs:
    ERR("calloc failed : %s", strerror(errno));
@@ -129,8 +127,7 @@ eina_graph_dfs_free(Eina_Graph_DFS *dfs)
 {
    _Eina_Graph_DFS *_dfs = (_Eina_Graph_DFS *) dfs;
 
-   free(_dfs->marked);
-   free(_dfs->edge_to);
+   free(_dfs->data);
    free(_dfs);
 }
 
@@ -153,7 +150,7 @@ eina_graph_dfs_has_path_to(Eina_Graph_DFS *dfs, unsigned int v)
         return EINA_FALSE;
      }
 
-   return _dfs->marked[v];
+   return _dfs->data[v].m;
 }
 
 EAPI Eina_List *
@@ -169,13 +166,13 @@ eina_graph_dfs_path_to(Eina_Graph_DFS *dfs, unsigned int v)
         return NULL;
      }
 
-   if (!_dfs->marked[v])
+   if (!_dfs->data[v].m)
      return NULL;
 
    while (w != _dfs->s)
      {
         path = eina_list_prepend(path, CAST_V(w));
-        w = _dfs->edge_to[w];
+        w = _dfs->data[w].e;
      }
    path = eina_list_prepend(path, CAST_V(_dfs->s));