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