#include <errno.h>
#include <stdlib.h>
+#include <time.h>
#include <loc/libloc.h>
#include <loc/network.h>
struct loc_ctx* ctx;
int refcount;
- struct loc_network* list[1024];
+ struct loc_network** elements;
+ size_t elements_size;
+
size_t size;
- size_t max_size;
};
+static int loc_network_list_grow(struct loc_network_list* list, size_t size) {
+ DEBUG(list->ctx, "Growing network list %p by %zu to %zu\n",
+ list, size, list->elements_size + size);
+
+ struct loc_network** elements = reallocarray(list->elements,
+ list->elements_size + size, sizeof(*list->elements));
+ if (!elements)
+ return -errno;
+
+ list->elements = elements;
+ list->elements_size += size;
+
+ return 0;
+}
+
LOC_EXPORT int loc_network_list_new(struct loc_ctx* ctx,
struct loc_network_list** list) {
struct loc_network_list* l = calloc(1, sizeof(*l));
l->ctx = loc_ref(ctx);
l->refcount = 1;
- // Do not allow this list to grow larger than this
- l->max_size = 1024;
-
DEBUG(l->ctx, "Network list allocated at %p\n", l);
*list = l;
return 0;
static void loc_network_list_free(struct loc_network_list* list) {
DEBUG(list->ctx, "Releasing network list at %p\n", list);
- for (unsigned int i = 0; i < list->size; i++)
- loc_network_unref(list->list[i]);
+ // Remove all content
+ loc_network_list_clear(list);
loc_unref(list->ctx);
free(list);
}
LOC_EXPORT void loc_network_list_clear(struct loc_network_list* list) {
+ if (!list->elements)
+ return;
+
for (unsigned int i = 0; i < list->size; i++)
- loc_network_unref(list->list[i]);
+ loc_network_unref(list->elements[i]);
+
+ free(list->elements);
+ list->elements = NULL;
+ list->elements_size = 0;
list->size = 0;
}
char* s;
for (unsigned int i = 0; i < list->size; i++) {
- network = list->list[i];
+ network = list->elements[i];
s = loc_network_str(network);
- INFO(list->ctx, "%s\n", s);
+ INFO(list->ctx, "%4d: %s\n", i, s);
free(s);
}
}
if (index >= list->size)
return NULL;
- return loc_network_ref(list->list[index]);
+ return loc_network_ref(list->elements[index]);
+}
+
+static off_t loc_network_list_find(struct loc_network_list* list,
+ struct loc_network* network, int* found) {
+ off_t lo = 0;
+ off_t hi = list->size - 1;
+ int result;
+
+ // Since we are working on an ordered list, there is often a good chance that
+ // the network we are looking for is at the end or has to go to the end.
+ if (hi >= 0) {
+ result = loc_network_cmp(network, list->elements[hi]);
+
+ // Match, so we are done
+ if (result == 0) {
+ *found = 1;
+
+ return hi;
+
+ // This needs to be added after the last one
+ } else if (result > 0) {
+ *found = 0;
+
+ return hi + 1;
+ }
+ }
+
+#ifdef ENABLE_DEBUG
+ // Save start time
+ clock_t start = clock();
+#endif
+
+ off_t i = 0;
+
+ while (lo <= hi) {
+ i = (lo + hi) / 2;
+
+ // Check if this is a match
+ result = loc_network_cmp(network, list->elements[i]);
+
+ if (result == 0) {
+ *found = 1;
+
+#ifdef ENABLE_DEBUG
+ clock_t end = clock();
+
+ // Log how fast this has been
+ DEBUG(list->ctx, "Found network in %.4fms at %jd\n",
+ (double)(end - start) / CLOCKS_PER_SEC * 1000, (intmax_t)i);
+#endif
+
+ return i;
+ }
+
+ if (result > 0)
+ lo = i + 1;
+ else
+ hi = i - 1;
+ }
+
+ *found = 0;
+
+#ifdef ENABLE_DEBUG
+ clock_t end = clock();
+
+ // Log how fast this has been
+ DEBUG(list->ctx, "Did not find network in %.4fms (last i = %jd)\n",
+ (double)(end - start) / CLOCKS_PER_SEC * 1000, (intmax_t)i);
+#endif
+
+ return i;
}
LOC_EXPORT int loc_network_list_push(struct loc_network_list* list, struct loc_network* network) {
- // Do not add networks that are already on the list
- if (loc_network_list_contains(list, network))
+ int found = 0;
+
+ off_t index = loc_network_list_find(list, network, &found);
+
+ // The network has been found on the list. Nothing to do.
+ if (found)
return 0;
+ DEBUG(list->ctx, "%p: Inserting network %p at index %jd\n",
+ list, network, (intmax_t)index);
+
// Check if we have space left
- if (list->size == list->max_size) {
- ERROR(list->ctx, "%p: Could not push network onto the stack: Stack full\n", list);
- return -ENOMEM;
+ if (list->size >= list->elements_size) {
+ int r = loc_network_list_grow(list, 64);
+ if (r)
+ return r;
}
- DEBUG(list->ctx, "%p: Pushing network %p onto stack\n", list, network);
+ // The list is now larger
+ list->size++;
+
+ // Move all elements out of the way
+ for (unsigned int i = list->size - 1; i > index; i--)
+ list->elements[i] = list->elements[i - 1];
- list->list[list->size++] = loc_network_ref(network);
+ // Add the new element at the right place
+ list->elements[index] = loc_network_ref(network);
return 0;
}
return NULL;
}
- struct loc_network* network = list->list[--list->size];
+ struct loc_network* network = list->elements[--list->size];
DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
return NULL;
}
- struct loc_network* network = list->list[0];
+ struct loc_network* network = list->elements[0];
// Move all elements to the top of the stack
- for (unsigned int i = 0; i < --list->size; i++) {
- list->list[i] = list->list[i+1];
+ for (unsigned int i = 0; i < list->size - 1; i++) {
+ list->elements[i] = list->elements[i+1];
}
+ // The list is shorter now
+ --list->size;
+
DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
return network;
}
LOC_EXPORT int loc_network_list_contains(struct loc_network_list* list, struct loc_network* network) {
- for (unsigned int i = 0; i < list->size; i++) {
- if (loc_network_eq(list->list[i], network))
- return 1;
- }
+ int found = 0;
- return 0;
-}
-
-static void loc_network_list_swap(struct loc_network_list* list, unsigned int i1, unsigned int i2) {
- // Do nothing for invalid indices
- if (i1 >= list->size || i2 >= list->size)
- return;
-
- struct loc_network* network1 = list->list[i1];
- struct loc_network* network2 = list->list[i2];
-
- list->list[i1] = network2;
- list->list[i2] = network1;
-}
-
-LOC_EXPORT void loc_network_list_reverse(struct loc_network_list* list) {
- unsigned int i = 0;
- unsigned int j = list->size - 1;
-
- while (i < j) {
- loc_network_list_swap(list, i++, j--);
- }
-}
-
-LOC_EXPORT void loc_network_list_sort(struct loc_network_list* list) {
- unsigned int n = list->size;
- int swapped;
-
- do {
- swapped = 0;
-
- for (unsigned int i = 1; i < n; i++) {
- if (loc_network_gt(list->list[i-1], list->list[i]) > 0) {
- loc_network_list_swap(list, i-1, i);
- swapped = 1;
- }
- }
+ loc_network_list_find(list, network, &found);
- n--;
- } while (swapped);
+ return found;
}
LOC_EXPORT int loc_network_list_merge(
int r;
for (unsigned int i = 0; i < other->size; i++) {
- r = loc_network_list_push(self, other->list[i]);
+ r = loc_network_list_push(self, other->elements[i]);
if (r)
return r;
}
projects / location / libloc.git / blobdiff