From 35598bc2d9a41ddaabded5f21e0ec92f001c5a1b Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= Date: Sat, 4 Jan 2014 13:44:00 +0100 Subject: DFS and BFS use 1 data array to improve spatial locality --- src/lib/eina_graph_bfs.c | 51 +++++++++++++++++--------------------------- src/lib/eina_graph_dfs.c | 41 +++++++++++++++++------------------ src/lib/eina_graph_private.h | 20 ++++++++++++----- 3 files changed, 54 insertions(+), 58 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; } 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)); diff --git a/src/lib/eina_graph_private.h b/src/lib/eina_graph_private.h index ccbff01..526e4e4 100644 --- a/src/lib/eina_graph_private.h +++ b/src/lib/eina_graph_private.h @@ -103,21 +103,31 @@ typedef struct _Eina_Graph _Eina_Graph_Adjacents *adjs; } _Eina_Graph; +typedef struct _Eina_Graph_DFS_Data +{ + Eina_Bool m; + unsigned int e; +} _Eina_Graph_DFS_Data; + typedef struct _Eina_Graph_DFS { unsigned int s; unsigned int vertices; - Eina_Bool *marked; - unsigned int *edge_to; + _Eina_Graph_DFS_Data *data; } _Eina_Graph_DFS; +typedef struct _Eina_Graph_BFS_Data +{ + Eina_Bool m; + unsigned int e; + unsigned int d; +} _Eina_Graph_BFS_Data; + typedef struct _Eina_Graph_BFS { unsigned int s; unsigned int vertices; - Eina_Bool *marked; - unsigned int *edge_to; - unsigned int *dist_to; + _Eina_Graph_BFS_Data *data; } _Eina_Graph_BFS; #endif /* _EINA_GRAPH_PRIVATE_H */ -- cgit v1.1-2-g2b99