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