src/network-list.c

   1 /*
   2         libloc - A library to determine the location of someone on the Internet
   3
   4         Copyright (C) 2020 IPFire Development Team <info@ipfire.org>
   5
   6         This library is free software; you can redistribute it and/or
   7         modify it under the terms of the GNU Lesser General Public
   8         License as published by the Free Software Foundation; either
   9         version 2.1 of the License, or (at your option) any later version.
  10
  11         This library is distributed in the hope that it will be useful,
  12         but WITHOUT ANY WARRANTY; without even the implied warranty of
  13         MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14         Lesser General Public License for more details.
  15 */
  16
  17 #include <errno.h>
  18 #include <stdlib.h>
  19 #include <time.h>
  20
  21 #include <loc/libloc.h>
  22 #include <loc/network.h>
  23 #include <loc/private.h>
  24
  25 struct loc_network_list {
  26         struct loc_ctx* ctx;
  27         int refcount;
  28
  29         struct loc_network** elements;
  30         size_t elements_size;
  31
  32         size_t size;
  33 };
  34
  35 static int loc_network_list_grow(struct loc_network_list* list, size_t size) {
  36         DEBUG(list->ctx, "Growing network list %p by %zu to %zu\n",
  37                 list, size, list->elements_size + size);
  38
  39         struct loc_network** elements = reallocarray(list->elements,
  40                         list->elements_size + size, sizeof(*list->elements));
  41         if (!elements)
  42                 return -errno;
  43
  44         list->elements = elements;
  45         list->elements_size += size;
  46
  47         return 0;
  48 }
  49
  50 LOC_EXPORT int loc_network_list_new(struct loc_ctx* ctx,
  51                 struct loc_network_list** list) {
  52         struct loc_network_list* l = calloc(1, sizeof(*l));
  53         if (!l)
  54                 return -ENOMEM;
  55
  56         l->ctx = loc_ref(ctx);
  57         l->refcount = 1;
  58
  59         DEBUG(l->ctx, "Network list allocated at %p\n", l);
  60         *list = l;
  61         return 0;
  62 }
  63
  64 LOC_EXPORT struct loc_network_list* loc_network_list_ref(struct loc_network_list* list) {
  65         list->refcount++;
  66
  67         return list;
  68 }
  69
  70 static void loc_network_list_free(struct loc_network_list* list) {
  71         DEBUG(list->ctx, "Releasing network list at %p\n", list);
  72
  73         for (unsigned int i = 0; i < list->size; i++)
  74                 loc_network_unref(list->elements[i]);
  75
  76         loc_unref(list->ctx);
  77         free(list);
  78 }
  79
  80 LOC_EXPORT struct loc_network_list* loc_network_list_unref(struct loc_network_list* list) {
  81         if (!list)
  82                 return NULL;
  83
  84         if (--list->refcount > 0)
  85                 return list;
  86
  87         loc_network_list_free(list);
  88         return NULL;
  89 }
  90
  91 LOC_EXPORT size_t loc_network_list_size(struct loc_network_list* list) {
  92         return list->size;
  93 }
  94
  95 LOC_EXPORT int loc_network_list_empty(struct loc_network_list* list) {
  96         return list->size == 0;
  97 }
  98
  99 LOC_EXPORT void loc_network_list_clear(struct loc_network_list* list) {
 100         if (!list->elements)
 101                 return;
 102
 103         for (unsigned int i = 0; i < list->size; i++)
 104                 loc_network_unref(list->elements[i]);
 105
 106         free(list->elements);
 107         list->elements_size = 0;
 108
 109         list->size = 0;
 110 }
 111
 112 LOC_EXPORT void loc_network_list_dump(struct loc_network_list* list) {
 113         struct loc_network* network;
 114         char* s;
 115
 116         for (unsigned int i = 0; i < list->size; i++) {
 117                 network = list->elements[i];
 118
 119                 s = loc_network_str(network);
 120
 121                 INFO(list->ctx, "%s\n", s);
 122                 free(s);
 123         }
 124 }
 125
 126 LOC_EXPORT struct loc_network* loc_network_list_get(struct loc_network_list* list, size_t index) {
 127         // Check index
 128         if (index >= list->size)
 129                 return NULL;
 130
 131         return loc_network_ref(list->elements[index]);
 132 }
 133
 134 //MOVE FUNCTION GOES HERE
 135
 136 static off_t loc_network_list_find(struct loc_network_list* list,
 137                 struct loc_network* network, int* found) {
 138         off_t lo = 0;
 139         off_t hi = list->size - 1;
 140
 141         *found = 0;
 142
 143 #ifdef ENABLE_DEBUG
 144         // Save start time
 145         clock_t start = clock();
 146 #endif
 147
 148         off_t i = 0;
 149
 150         while (lo <= hi) {
 151                 i = (lo + hi) / 2;
 152
 153                 // Check if this is a match
 154                 int result = loc_network_cmp(network, list->elements[i]);
 155
 156                 if (result == 0) {
 157                         *found = 1;
 158
 159 #ifdef ENABLE_DEBUG
 160                         clock_t end = clock();
 161
 162                         // Log how fast this has been
 163                         DEBUG(list->ctx, "Found network in %.4fms at %jd\n",
 164                                 (double)(end - start) / CLOCKS_PER_SEC * 1000, (intmax_t)i);
 165 #endif
 166
 167                         return i;
 168                 }
 169
 170                 if (result > 0)
 171                         lo = i + 1;
 172                 else
 173                         hi = i - 1;
 174         }
 175
 176 #ifdef ENABLE_DEBUG
 177         clock_t end = clock();
 178
 179         // Log how fast this has been
 180         DEBUG(list->ctx, "Did not find network in %.4fms (last i = %jd)\n",
 181                 (double)(end - start) / CLOCKS_PER_SEC * 1000, (intmax_t)i);
 182 #endif
 183
 184         return i;
 185 }
 186
 187 LOC_EXPORT int loc_network_list_push(struct loc_network_list* list, struct loc_network* network) {
 188         int found = 0;
 189
 190         off_t index = loc_network_list_find(list, network, &found);
 191
 192         // The network has been found on the list. Nothing to do.
 193         if (found)
 194                 return 0;
 195
 196         DEBUG(list->ctx, "%p: Inserting network %p at index %jd\n",
 197                 list, network, (intmax_t)index);
 198
 199         // Check if we have space left
 200         if (list->size >= list->elements_size) {
 201                 int r = loc_network_list_grow(list, 64);
 202                 if (r)
 203                         return r;
 204         }
 205
 206         // The list is now larger
 207         list->size++;
 208
 209         // Move all elements out of the way
 210         for (unsigned int i = list->size - 1; i > index; i--)
 211                 list->elements[i] = list->elements[i - 1];
 212
 213         // Add the new element at the right place
 214         list->elements[index] = loc_network_ref(network);
 215
 216         return 0;
 217 }
 218
 219 LOC_EXPORT struct loc_network* loc_network_list_pop(struct loc_network_list* list) {
 220         // Return nothing when empty
 221         if (loc_network_list_empty(list)) {
 222                 DEBUG(list->ctx, "%p: Popped empty stack\n", list);
 223                 return NULL;
 224         }
 225
 226         struct loc_network* network = list->elements[--list->size];
 227
 228         DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
 229
 230         return network;
 231 }
 232
 233 LOC_EXPORT struct loc_network* loc_network_list_pop_first(struct loc_network_list* list) {
 234         // Return nothing when empty
 235         if (loc_network_list_empty(list)) {
 236                 DEBUG(list->ctx, "%p: Popped empty stack\n", list);
 237                 return NULL;
 238         }
 239
 240         struct loc_network* network = list->elements[0];
 241
 242         // Move all elements to the top of the stack
 243         for (unsigned int i = 0; i < --list->size; i++) {
 244                 list->elements[i] = list->elements[i+1];
 245         }
 246
 247         DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
 248
 249         return network;
 250 }
 251
 252 LOC_EXPORT int loc_network_list_contains(struct loc_network_list* list, struct loc_network* network) {
 253         int found = 0;
 254
 255         loc_network_list_find(list, network, &found);
 256
 257         return found;
 258 }
 259
 260 LOC_EXPORT int loc_network_list_merge(
 261                 struct loc_network_list* self, struct loc_network_list* other) {
 262         int r;
 263
 264         for (unsigned int i = 0; i < other->size; i++) {
 265                 r = loc_network_list_push(self, other->elements[i]);
 266                 if (r)
 267                         return r;
 268         }
 269
 270         return 0;
 271 }