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                         i++;
 190                 } else {
 191                         hi = i - 1;
 192                 }
 193         }
 194
 195         *found = 0;
 196
 197 #ifdef ENABLE_DEBUG
 198         clock_t end = clock();
 199
 200         // Log how fast this has been
 201         DEBUG(list->ctx, "Did not find network in %.4fms (last i = %jd)\n",
 202                 (double)(end - start) / CLOCKS_PER_SEC * 1000, (intmax_t)i);
 203 #endif
 204
 205         return i;
 206 }
 207
 208 LOC_EXPORT int loc_network_list_push(struct loc_network_list* list, struct loc_network* network) {
 209         int found = 0;
 210
 211         off_t index = loc_network_list_find(list, network, &found);
 212
 213         // The network has been found on the list. Nothing to do.
 214         if (found)
 215                 return 0;
 216
 217         DEBUG(list->ctx, "%p: Inserting network %p at index %jd\n",
 218                 list, network, (intmax_t)index);
 219
 220         // Check if we have space left
 221         if (list->size >= list->elements_size) {
 222                 int r = loc_network_list_grow(list, 64);
 223                 if (r)
 224                         return r;
 225         }
 226
 227         // The list is now larger
 228         list->size++;
 229
 230         // Move all elements out of the way
 231         for (unsigned int i = list->size - 1; i > index; i--)
 232                 list->elements[i] = list->elements[i - 1];
 233
 234         // Add the new element at the right place
 235         list->elements[index] = loc_network_ref(network);
 236
 237         return 0;
 238 }
 239
 240 LOC_EXPORT struct loc_network* loc_network_list_pop(struct loc_network_list* list) {
 241         // Return nothing when empty
 242         if (loc_network_list_empty(list)) {
 243                 DEBUG(list->ctx, "%p: Popped empty stack\n", list);
 244                 return NULL;
 245         }
 246
 247         struct loc_network* network = list->elements[--list->size];
 248
 249         DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
 250
 251         return network;
 252 }
 253
 254 LOC_EXPORT struct loc_network* loc_network_list_pop_first(struct loc_network_list* list) {
 255         // Return nothing when empty
 256         if (loc_network_list_empty(list)) {
 257                 DEBUG(list->ctx, "%p: Popped empty stack\n", list);
 258                 return NULL;
 259         }
 260
 261         struct loc_network* network = list->elements[0];
 262
 263         // Move all elements to the top of the stack
 264         for (unsigned int i = 0; i < list->size - 1; i++) {
 265                 list->elements[i] = list->elements[i+1];
 266         }
 267
 268         // The list is shorter now
 269         --list->size;
 270
 271         DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
 272
 273         return network;
 274 }
 275
 276 LOC_EXPORT int loc_network_list_contains(struct loc_network_list* list, struct loc_network* network) {
 277         int found = 0;
 278
 279         loc_network_list_find(list, network, &found);
 280
 281         return found;
 282 }
 283
 284 LOC_EXPORT int loc_network_list_merge(
 285                 struct loc_network_list* self, struct loc_network_list* other) {
 286         int r;
 287
 288         for (unsigned int i = 0; i < other->size; i++) {
 289                 r = loc_network_list_push(self, other->elements[i]);
 290                 if (r)
 291                         return r;
 292         }
 293
 294         return 0;
 295 }