diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/lib/eina_graph_dfs.c | 22 | ||||
| -rw-r--r-- | src/lib/eina_graph_private.h | 19 |
2 files changed, 31 insertions, 10 deletions
diff --git a/src/lib/eina_graph_dfs.c b/src/lib/eina_graph_dfs.c index 1b9a61a..2b1cc73 100644 --- a/src/lib/eina_graph_dfs.c +++ b/src/lib/eina_graph_dfs.c @@ -34,20 +34,22 @@ #include "eina_graph_private.h" static void -_eina_graph_dfs_swalk(_Eina_Graph *_g, _Eina_Graph_DFS *_dfs, unsigned int v) +_eina_graph_dfs_swalk(_Eina_Graph *_g, _Eina_Graph_DFS *_dfs, + unsigned int v, unsigned int step) { - Eina_List *stack = NULL; + Eina_Array *stack = NULL; _Eina_Graph_Adjacents *adjs; _Eina_Graph_DFS_Data *vd; unsigned int p, w, n, i; p = v; - stack = eina_list_prepend(stack, CAST_V(v)); + stack = eina_array_new(step); + eina_array_push_uint(stack, v); - while (eina_list_count(stack) > 0) + while (eina_array_count_get(stack) > 0) { - w = CAST_D(eina_list_data_get(stack)); - stack = eina_list_remove(stack, CAST_V(w)); + w = eina_array_top_uint_get(stack); + eina_array_pop(stack); vd = &_dfs->data[w]; if(vd->m) continue; @@ -61,11 +63,11 @@ _eina_graph_dfs_swalk(_Eina_Graph *_g, _Eina_Graph_DFS *_dfs, unsigned int v) { w = adjs->data[i]; if (!_dfs->data[w].m) - { - stack = eina_list_prepend(stack, CAST_V(w)); - } + eina_array_push_uint(stack, w); } } + + eina_array_free(stack); } static void @@ -111,7 +113,7 @@ eina_graph_dfs_new(Eina_Graph *g, unsigned int s, Eina_Bool r) if (r) _eina_graph_dfs_rwalk(_g, _dfs, s); else - _eina_graph_dfs_swalk(_g, _dfs, s); + _eina_graph_dfs_swalk(_g, _dfs, s, eina_graph_degree_max(g) * 2); return (Eina_Graph_DFS *) _dfs; diff --git a/src/lib/eina_graph_private.h b/src/lib/eina_graph_private.h index 526e4e4..1c4ea86 100644 --- a/src/lib/eina_graph_private.h +++ b/src/lib/eina_graph_private.h @@ -90,6 +90,25 @@ eina_graph_adjacents_push(_Eina_Graph_Adjacents *adjs, unsigned int v, unsigned return EINA_TRUE; } +static inline Eina_Bool +eina_array_push_uint(Eina_Array *array, unsigned int v) +{ + if (EINA_UNLIKELY((array->count + 1) > array->total)) + if (!eina_array_grow(array)) + return EINA_FALSE; + + array->data[array->count++] = (void*) (uintptr_t) v; + + return EINA_TRUE; +} + +static inline unsigned int +eina_array_top_uint_get(const Eina_Array *array) +{ + return (unsigned int) (uintptr_t) + eina_array_data_get(array,eina_array_count_get(array) - 1 ); +} + /*+ * To cast a vertex number into Eina_List data. */ |