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         int result;
 141
 142         // Since we are working on an ordered list, there is often a good chance that
 143         // the network we are looking for is at the end or has to go to the end.
 144         if (hi >= 0) {
 145                 result = loc_network_cmp(network, list->elements[hi]);
 146
 147                 // Match, so we are done
 148                 if (result == 0) {
 149                         *found = 1;
 150
 151                         return hi;
 152
 153                 // This needs to be added after the last one
 154                 } else if (result > 0) {
 155                         *found = 0;
 156
 157                         return hi + 1;
 158                 }
 159         }
 160
 161 #ifdef ENABLE_DEBUG
 162         // Save start time
 163         clock_t start = clock();
 164 #endif
 165
 166         off_t i = 0;
 167
 168         while (lo <= hi) {
 169                 i = (lo + hi) / 2;
 170
 171                 // Check if this is a match
 172                 result = loc_network_cmp(network, list->elements[i]);
 173
 174                 if (result == 0) {
 175                         *found = 1;
 176
 177 #ifdef ENABLE_DEBUG
 178                         clock_t end = clock();
 179
 180                         // Log how fast this has been
 181                         DEBUG(list->ctx, "Found network in %.4fms at %jd\n",
 182                                 (double)(end - start) / CLOCKS_PER_SEC * 1000, (intmax_t)i);
 183 #endif
 184
 185                         return i;
 186                 }
 187
 188                 if (result > 0)
 189                         lo = i + 1;
 190                 else
 191                         hi = i - 1;
 192         }
 193
 194         *found = 0;
 195
 196 #ifdef ENABLE_DEBUG
 197         clock_t end = clock();
 198
 199         // Log how fast this has been
 200         DEBUG(list->ctx, "Did not find network in %.4fms (last i = %jd)\n",
 201                 (double)(end - start) / CLOCKS_PER_SEC * 1000, (intmax_t)i);
 202 #endif
 203
 204         return i;
 205 }
 206
 207 LOC_EXPORT int loc_network_list_push(struct loc_network_list* list, struct loc_network* network) {
 208         int found = 0;
 209
 210         off_t index = loc_network_list_find(list, network, &found);
 211
 212         // The network has been found on the list. Nothing to do.
 213         if (found)
 214                 return 0;
 215
 216         DEBUG(list->ctx, "%p: Inserting network %p at index %jd\n",
 217                 list, network, (intmax_t)index);
 218
 219         // Check if we have space left
 220         if (list->size >= list->elements_size) {
 221                 int r = loc_network_list_grow(list, 64);
 222                 if (r)
 223                         return r;
 224         }
 225
 226         // The list is now larger
 227         list->size++;
 228
 229         // Move all elements out of the way
 230         for (unsigned int i = list->size - 1; i > index; i--)
 231                 list->elements[i] = list->elements[i - 1];
 232
 233         // Add the new element at the right place
 234         list->elements[index] = loc_network_ref(network);
 235
 236         return 0;
 237 }
 238
 239 LOC_EXPORT struct loc_network* loc_network_list_pop(struct loc_network_list* list) {
 240         // Return nothing when empty
 241         if (loc_network_list_empty(list)) {
 242                 DEBUG(list->ctx, "%p: Popped empty stack\n", list);
 243                 return NULL;
 244         }
 245
 246         struct loc_network* network = list->elements[--list->size];
 247
 248         DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
 249
 250         return network;
 251 }
 252
 253 LOC_EXPORT struct loc_network* loc_network_list_pop_first(struct loc_network_list* list) {
 254         // Return nothing when empty
 255         if (loc_network_list_empty(list)) {
 256                 DEBUG(list->ctx, "%p: Popped empty stack\n", list);
 257                 return NULL;
 258         }
 259
 260         struct loc_network* network = list->elements[0];
 261
 262         // Move all elements to the top of the stack
 263         for (unsigned int i = 0; i < --list->size; i++) {
 264                 list->elements[i] = list->elements[i+1];
 265         }
 266
 267         DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
 268
 269         return network;
 270 }
 271
 272 LOC_EXPORT int loc_network_list_contains(struct loc_network_list* list, struct loc_network* network) {
 273         int found = 0;
 274
 275         loc_network_list_find(list, network, &found);
 276
 277         return found;
 278 }
 279
 280 LOC_EXPORT int loc_network_list_merge(
 281                 struct loc_network_list* self, struct loc_network_list* other) {
 282         int r;
 283
 284         for (unsigned int i = 0; i < other->size; i++) {
 285                 r = loc_network_list_push(self, other->elements[i]);
 286                 if (r)
 287                         return r;
 288         }
 289
 290         return 0;
 291 }