DFS and BFS use 1 data array to improve spatial locality

1 files changed, 20 insertions, 31 deletions

diff --git a/src/lib/eina_graph_bfs.c b/src/lib/eina_graph_bfs.c
index c1e67d7..80f6be7 100644
--- a/src/lib/eina_graph_bfs.c
+++ b/src/lib/eina_graph_bfs.c
@@ -38,12 +38,14 @@ _eina_graph_bfs_fwalk(_Eina_Graph *_g, _Eina_Graph_BFS *_bfs, unsigned int v)
 {
    Eina_List *fifo = NULL;
    _Eina_Graph_Adjacents *adjs;
+   _Eina_Graph_BFS_Data *vd;
    unsigned int p, w, n, i, d;
 
    d = 0;
-   _bfs->marked[v] = EINA_TRUE;
-   _bfs->edge_to[v] = v;
-   _bfs->dist_to[v] = d;
+   vd = &_bfs->data[v];
+   vd->m = EINA_TRUE;
+   vd->e = v;
+   vd->d = d;
    fifo = eina_list_append(fifo, CAST_V(v));
 
    while (eina_list_count(fifo) > 0)
@@ -58,12 +60,13 @@ _eina_graph_bfs_fwalk(_Eina_Graph *_g, _Eina_Graph_BFS *_bfs, unsigned int v)
         n = adjs->count;
         for (i = 0; i < n; i++)
           {
-             w =  adjs->data[i];
-             if (!_bfs->marked[w])
+             w = adjs->data[i];
+             vd = &_bfs->data[w];
+             if (!vd->m)
                {
-                  _bfs->marked[w] = EINA_TRUE;
-                  _bfs->edge_to[w] = p;
-                  _bfs->dist_to[w] = d;
+                  vd->m = EINA_TRUE;
+                  vd->e = p;
+                  vd->d = d;
                   fifo = eina_list_append(fifo, CAST_V(w));
                }
           }
@@ -80,17 +83,9 @@ eina_graph_bfs_new(Eina_Graph *g, unsigned int s)
    if (!_bfs)
      goto error_bfs;
 
-   _bfs->marked = calloc(_g->vertices, sizeof(Eina_Bool));
-   if (!_bfs->marked)
-     goto error_marked;
-
-   _bfs->edge_to = calloc(_g->vertices, sizeof(unsigned int));
-   if (!_bfs->edge_to)
-     goto error_edge_to;
-
-   _bfs->dist_to = calloc(_g->vertices, sizeof(unsigned int));
-   if (!_bfs->dist_to)
-     goto error_dist_to;
+   _bfs->data = calloc(_g->vertices, sizeof(_Eina_Graph_BFS_Data));
+   if (!_bfs->data)
+     goto error_data;
 
    _bfs->s = s;
    _bfs->vertices = _g->vertices;
@@ -99,11 +94,7 @@ eina_graph_bfs_new(Eina_Graph *g, unsigned int s)
 
    return (Eina_Graph_BFS *) _bfs;
 
-error_dist_to:
-   free(_bfs->edge_to);
-error_edge_to:
-   free(_bfs->marked);
-error_marked:
+error_data:
    free(_bfs);
 error_bfs:
    ERR("calloc failed : %s", strerror(errno));
@@ -115,9 +106,7 @@ eina_graph_bfs_free(Eina_Graph_BFS *bfs)
 {
    _Eina_Graph_BFS *_bfs = (_Eina_Graph_BFS *) bfs;
 
-   free(_bfs->marked);
-   free(_bfs->edge_to);
-   free(_bfs->dist_to);
+   free(_bfs->data);
    free(_bfs);
 }
 
@@ -140,7 +129,7 @@ eina_graph_bfs_has_path_to(Eina_Graph_BFS *bfs, unsigned int v)
         return EINA_FALSE;
      }
 
-   return _bfs->marked[v];
+   return _bfs->data[v].m;
 }
 
 EAPI Eina_List *
@@ -156,13 +145,13 @@ eina_graph_bfs_path_to(Eina_Graph_BFS *bfs, unsigned int v)
         return NULL;
      }
 
-   if (!_bfs->marked[v])
+   if (!_bfs->data[v].m)
      return NULL;
 
    while (w != _bfs->s)
      {
         path = eina_list_prepend(path, CAST_V(w));
-        w = _bfs->edge_to[w];
+        w = _bfs->data[w].e;
      }
    path = eina_list_prepend(path, CAST_V(_bfs->s));
 
@@ -180,5 +169,5 @@ eina_graph_bfs_dist_to(Eina_Graph_BFS *bfs, unsigned int v)
         return UINT_MAX;
      }
 
-   return _bfs->dist_to[v];
+   return _bfs->data[v].d;
 }