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 = 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, "%s\n", 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 //MOVE FUNCTION GOES HERE
 136
 137 static off_t loc_network_list_find(struct loc_network_list* list,
 138                 struct loc_network* network, int* found) {
 139         off_t lo = 0;
 140         off_t hi = list->size - 1;
 141         int result;
 142
 143         // Since we are working on an ordered list, there is often a good chance that
 144         // the network we are looking for is at the end or has to go to the end.
 145         if (hi >= 0) {
 146                 result = loc_network_cmp(network, list->elements[hi]);
 147
 148                 // Match, so we are done
 149                 if (result == 0) {
 150                         *found = 1;
 151
 152                         return hi;
 153
 154                 // This needs to be added after the last one
 155                 } else if (result > 0) {
 156                         *found = 0;
 157
 158                         return hi + 1;
 159                 }
 160         }
 161
 162 #ifdef ENABLE_DEBUG
 163         // Save start time
 164         clock_t start = clock();
 165 #endif
 166
 167         off_t i = 0;
 168
 169         while (lo <= hi) {
 170                 i = (lo + hi) / 2;
 171
 172                 // Check if this is a match
 173                 result = loc_network_cmp(network, list->elements[i]);
 174
 175                 if (result == 0) {
 176                         *found = 1;
 177
 178 #ifdef ENABLE_DEBUG
 179                         clock_t end = clock();
 180
 181                         // Log how fast this has been
 182                         DEBUG(list->ctx, "Found network in %.4fms at %jd\n",
 183                                 (double)(end - start) / CLOCKS_PER_SEC * 1000, (intmax_t)i);
 184 #endif
 185
 186                         return i;
 187                 }
 188
 189                 if (result > 0)
 190                         lo = i + 1;
 191                 else
 192                         hi = i - 1;
 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; i++) {
 265                 list->elements[i] = list->elements[i+1];
 266         }
 267
 268         DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
 269
 270         return network;
 271 }
 272
 273 LOC_EXPORT int loc_network_list_contains(struct loc_network_list* list, struct loc_network* network) {
 274         int found = 0;
 275
 276         loc_network_list_find(list, network, &found);
 277
 278         return found;
 279 }
 280
 281 LOC_EXPORT int loc_network_list_merge(
 282                 struct loc_network_list* self, struct loc_network_list* other) {
 283         int r;
 284
 285         for (unsigned int i = 0; i < other->size; i++) {
 286                 r = loc_network_list_push(self, other->elements[i]);
 287                 if (r)
 288                         return r;
 289         }
 290
 291         return 0;
 292 }