From a8d64ce858c418cdcc5328a008e0b43446252095 Mon Sep 17 00:00:00 2001 From: Matthew Fernandez Date: Tue, 11 Jan 2022 19:21:47 -0800 Subject: [PATCH] dijkstra_bounded: replace boolean array 'node_in_neighborhood' with a bit array This is more memory efficient. This also undoes the retention and reuse of this array making its live range more obvious to the compiler. --- lib/neatogen/dijkstra.c | 20 +++++--------------- 1 file changed, 5 insertions(+), 15 deletions(-) diff --git a/lib/neatogen/dijkstra.c b/lib/neatogen/dijkstra.c index 93177f44d..404024a2e 100644 --- a/lib/neatogen/dijkstra.c +++ b/lib/neatogen/dijkstra.c @@ -185,8 +185,6 @@ dijkstra_bounded(int vertex, vtx_data * graph, int n, DistType * dist, { int num_visited_nodes; int i; - static boolean *node_in_neighborhood = NULL; - static int size = 0; Queue Q; heap H; int closestVertex, neighbor; @@ -201,15 +199,10 @@ dijkstra_bounded(int vertex, vtx_data * graph, int n, DistType * dist, } num_visited_nodes = bfs_bounded(vertex, graph, n, dist, &Q, bound, visited_nodes); - if (size < n) { - node_in_neighborhood = realloc(node_in_neighborhood, n * sizeof(boolean)); - for (i = size; i < n; i++) { - node_in_neighborhood[i] = FALSE; - } - size = n; - } + bitarray_t node_in_neighborhood = {0}; + bitarray_resize_or_exit(&node_in_neighborhood, n); for (i = 0; i < num_visited_nodes; i++) { - node_in_neighborhood[visited_nodes[i]] = TRUE; + bitarray_set(node_in_neighborhood, visited_nodes[i], true); } int *index = gcalloc(n, sizeof(int)); @@ -226,7 +219,7 @@ dijkstra_bounded(int vertex, vtx_data * graph, int n, DistType * dist, while (num_found < num_visited_nodes && extractMax(&H, &closestVertex, index, dist)) { - if (node_in_neighborhood[closestVertex]) { + if (bitarray_get(node_in_neighborhood, closestVertex)) { num_found++; } closestDist = dist[closestVertex]; @@ -239,10 +232,7 @@ dijkstra_bounded(int vertex, vtx_data * graph, int n, DistType * dist, } } - /* restore initial false-status of 'node_in_neighborhood' */ - for (i = 0; i < num_visited_nodes; i++) { - node_in_neighborhood[visited_nodes[i]] = FALSE; - } + bitarray_reset(&node_in_neighborhood); freeHeap(&H); free(index); freeQueue(&Q); -- 2.40.0