summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/lib/eina_graph.c25
-rw-r--r--src/lib/eina_graph_bfs.c8
-rw-r--r--src/lib/eina_graph_dfs.c16
-rw-r--r--src/lib/eina_graph_main.c16
-rw-r--r--src/lib/eina_graph_private.h42
5 files changed, 34 insertions, 73 deletions
diff --git a/src/lib/eina_graph.c b/src/lib/eina_graph.c
index ac42012..4cea67f 100644
--- a/src/lib/eina_graph.c
+++ b/src/lib/eina_graph.c
@@ -36,18 +36,19 @@
EAPI Eina_Graph *
eina_graph_new(unsigned int v, unsigned int step)
{
+ unsigned int i;
_Eina_Graph *_g;
- _g = calloc(1, sizeof(_Eina_Graph) + (v * sizeof(_Eina_Graph_Adjacents)));
+ _g = calloc(1, sizeof(_Eina_Graph) + (v * sizeof(Eina_Array *)));
if (!_g)
{
ERR("calloc failed : %s", strerror(errno));
return NULL;
}
- _g->step = step;
_g->vertices = v;
- _g->adjs = (_Eina_Graph_Adjacents *) ((char *) _g + sizeof(_Eina_Graph));
+ for (i = 0; i < v; i++)
+ _g->adjs[i] = eina_array_new(step);
return (Eina_Graph *) _g;
}
@@ -59,7 +60,7 @@ eina_graph_free(Eina_Graph *g)
_Eina_Graph * _g = (_Eina_Graph *) g;
for (i = 0; i< _g->vertices; i++)
- eina_graph_adjacents_free(&_g->adjs[i]);
+ eina_array_free(_g->adjs[i]);
free(_g);
}
@@ -91,7 +92,7 @@ eina_graph_degree(const Eina_Graph *g, unsigned int v)
return 0;
}
- return _g->adjs[v].count;
+ return eina_array_count_get(_g->adjs[v]);
}
EAPI unsigned int
@@ -103,7 +104,7 @@ eina_graph_degree_max(const Eina_Graph *g)
max = 0;
for (i = 0; i< _g->vertices; i++)
{
- n = _g->adjs[i].count;
+ n = eina_array_count_get(_g->adjs[i]);
if ( n > max ) max = n;
}
@@ -121,18 +122,18 @@ eina_graph_degree_avg(const Eina_Graph *g)
EAPI unsigned int
eina_graph_self_loops(const Eina_Graph *g)
{
- unsigned int *data;
unsigned int i, j, n, loops;
+ Eina_Array *ar;
_Eina_Graph * _g = (_Eina_Graph *) g;
loops = 0;
for (i = 0; i< _g->vertices; i++)
{
- n = _g->adjs[i].count;
- data = _g->adjs[i].data;
+ ar = _g->adjs[i];
+ n = eina_array_count_get(ar);
for (j = 0; j < n; j++)
{
- if(i == data[j]) loops++;
+ if(i == eina_array_uint_nth_get(ar, j)) loops++;
}
}
@@ -150,9 +151,9 @@ eina_graph_edge_add(Eina_Graph *g, unsigned int v, unsigned int w)
return EINA_FALSE;
}
- if(!eina_graph_adjacents_push(&_g->adjs[v], w, _g->step)) return EINA_FALSE;
+ if (!eina_array_push_uint(_g->adjs[v], w)) return EINA_FALSE;
if (v != w )
- if(!eina_graph_adjacents_push(&_g->adjs[w], v, _g->step)) return EINA_FALSE;
+ if (!eina_array_push_uint(_g->adjs[w], v)) return EINA_FALSE;
_g->edges++;
diff --git a/src/lib/eina_graph_bfs.c b/src/lib/eina_graph_bfs.c
index 651695f..2632c4a 100644
--- a/src/lib/eina_graph_bfs.c
+++ b/src/lib/eina_graph_bfs.c
@@ -37,7 +37,7 @@ static void
_eina_graph_bfs_fwalk(_Eina_Graph *_g, _Eina_Graph_BFS *_bfs, unsigned int v)
{
Eina_List *fifo = NULL;
- _Eina_Graph_Adjacents *adjs;
+ Eina_Array *adjs;
_Eina_Graph_BFS_Data *vd;
unsigned int p, w, n, i, d;
@@ -56,11 +56,11 @@ _eina_graph_bfs_fwalk(_Eina_Graph *_g, _Eina_Graph_BFS *_bfs, unsigned int v)
p = w;
d++;
- adjs = &_g->adjs[w];
- n = adjs->count;
+ adjs = _g->adjs[w];
+ n = eina_array_count_get(adjs);
for (i = 0; i < n; i++)
{
- w = adjs->data[i];
+ w = eina_array_uint_nth_get(adjs, i);
vd = &_bfs->data[w];
if (!vd->m)
{
diff --git a/src/lib/eina_graph_dfs.c b/src/lib/eina_graph_dfs.c
index 2b1cc73..f958d41 100644
--- a/src/lib/eina_graph_dfs.c
+++ b/src/lib/eina_graph_dfs.c
@@ -38,7 +38,7 @@ _eina_graph_dfs_swalk(_Eina_Graph *_g, _Eina_Graph_DFS *_dfs,
unsigned int v, unsigned int step)
{
Eina_Array *stack = NULL;
- _Eina_Graph_Adjacents *adjs;
+ Eina_Array *adjs;
_Eina_Graph_DFS_Data *vd;
unsigned int p, w, n, i;
@@ -57,11 +57,11 @@ _eina_graph_dfs_swalk(_Eina_Graph *_g, _Eina_Graph_DFS *_dfs,
vd->e = p;
p = w;
- adjs = &_g->adjs[w];
- n = adjs->count;
+ adjs = _g->adjs[w];
+ n = eina_array_count_get(adjs);
for (i = 0; i < n; i++)
{
- w = adjs->data[i];
+ w = eina_array_uint_nth_get(adjs, i);
if (!_dfs->data[w].m)
eina_array_push_uint(stack, w);
}
@@ -73,17 +73,17 @@ _eina_graph_dfs_swalk(_Eina_Graph *_g, _Eina_Graph_DFS *_dfs,
static void
_eina_graph_dfs_rwalk(_Eina_Graph *_g, _Eina_Graph_DFS *_dfs, unsigned int v)
{
- _Eina_Graph_Adjacents *adjs;
+ Eina_Array *adjs;
_Eina_Graph_DFS_Data *vd;
unsigned int i, n, w;
_dfs->data[v].m = EINA_TRUE;
- adjs = &_g->adjs[v];
- n = adjs->count;
+ adjs = _g->adjs[v];
+ n = eina_array_count_get(adjs);
for (i = 0; i < n; i++)
{
- w = adjs->data[i];
+ w = eina_array_uint_nth_get(adjs, i);
vd = &_dfs->data[w];
if (!vd->m)
{
diff --git a/src/lib/eina_graph_main.c b/src/lib/eina_graph_main.c
index a42ed98..7a05f44 100644
--- a/src/lib/eina_graph_main.c
+++ b/src/lib/eina_graph_main.c
@@ -91,19 +91,3 @@ eina_graph_shutdown(void)
return _eina_graph_init_count;
}
-Eina_Bool
-_eina_graph_adjacents_grow(_Eina_Graph_Adjacents *adjs, unsigned int step)
-{
- unsigned int *tmp;
- unsigned int total;
-
- total = adjs->total + step;
- tmp = realloc(adjs->data, sizeof (unsigned int) * total);
- if (EINA_UNLIKELY(!tmp)) return EINA_FALSE;
-
- adjs->total = total;
- adjs->data = tmp;
-
- return EINA_TRUE;
-}
-
diff --git a/src/lib/eina_graph_private.h b/src/lib/eina_graph_private.h
index 1c4ea86..1925cf7 100644
--- a/src/lib/eina_graph_private.h
+++ b/src/lib/eina_graph_private.h
@@ -60,36 +60,6 @@ extern int _eina_graph_log_dom;
#endif
#define DBG(...) EINA_LOG_DOM_DBG(_eina_graph_log_dom, __VA_ARGS__)
-typedef struct _Eina_Graph_Adjacents
-{
- unsigned int *data;
- unsigned int total;
- unsigned int count;
-} _Eina_Graph_Adjacents;
-
-static inline void
-eina_graph_adjacents_free(_Eina_Graph_Adjacents *adjs)
-{
- if (adjs->data)
- free(adjs->data);
- adjs->data = NULL;
-}
-
-Eina_Bool
-_eina_graph_adjacents_grow(_Eina_Graph_Adjacents *adjs, unsigned int step);
-
-static inline Eina_Bool
-eina_graph_adjacents_push(_Eina_Graph_Adjacents *adjs, unsigned int v, unsigned int step)
-{
- if (EINA_UNLIKELY((adjs->count + 1) > adjs->total))
- if (!_eina_graph_adjacents_grow(adjs, step))
- return EINA_FALSE;
-
- adjs->data[adjs->count++] = v;
-
- return EINA_TRUE;
-}
-
static inline Eina_Bool
eina_array_push_uint(Eina_Array *array, unsigned int v)
{
@@ -103,10 +73,17 @@ eina_array_push_uint(Eina_Array *array, unsigned int v)
}
static inline unsigned int
+eina_array_uint_nth_get(const Eina_Array *array, unsigned int idx)
+{
+ return (unsigned int) (uintptr_t)
+ eina_array_data_get(array, idx);
+}
+
+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 );
+ eina_array_data_get(array, eina_array_count_get(array) - 1 );
}
/*+
@@ -118,8 +95,7 @@ typedef struct _Eina_Graph
{
unsigned int vertices;
unsigned int edges;
- unsigned int step;
- _Eina_Graph_Adjacents *adjs;
+ Eina_Array *adjs[];
} _Eina_Graph;
typedef struct _Eina_Graph_DFS_Data
generated by cgit v1.1-2-g2b99 at 2024-11-21 14:08:51 +0100