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
  20 #include <loc/libloc.h>
  21 #include <loc/network.h>
  22 #include <loc/private.h>
  23
  24 struct loc_network_list {
  25         struct loc_ctx* ctx;
  26         int refcount;
  27
  28         struct loc_network** elements;
  29         size_t elements_size;
  30
  31         size_t size;
  32 };
  33
  34 static int loc_network_list_grow(struct loc_network_list* list, size_t size) {
  35         DEBUG(list->ctx, "Growing network list %p by %zu to %zu\n",
  36                 list, size, list->elements_size + size);
  37
  38         struct loc_network** elements = reallocarray(list->elements,
  39                         list->elements_size + size, sizeof(*list->elements));
  40         if (!elements)
  41                 return -errno;
  42
  43         list->elements = elements;
  44         list->elements_size += size;
  45
  46         return 0;
  47 }
  48
  49 LOC_EXPORT int loc_network_list_new(struct loc_ctx* ctx,
  50                 struct loc_network_list** list) {
  51         struct loc_network_list* l = calloc(1, sizeof(*l));
  52         if (!l)
  53                 return -ENOMEM;
  54
  55         l->ctx = loc_ref(ctx);
  56         l->refcount = 1;
  57
  58         DEBUG(l->ctx, "Network list allocated at %p\n", l);
  59         *list = l;
  60         return 0;
  61 }
  62
  63 LOC_EXPORT struct loc_network_list* loc_network_list_ref(struct loc_network_list* list) {
  64         list->refcount++;
  65
  66         return list;
  67 }
  68
  69 static void loc_network_list_free(struct loc_network_list* list) {
  70         DEBUG(list->ctx, "Releasing network list at %p\n", list);
  71
  72         for (unsigned int i = 0; i < list->size; i++)
  73                 loc_network_unref(list->elements[i]);
  74
  75         loc_unref(list->ctx);
  76         free(list);
  77 }
  78
  79 LOC_EXPORT struct loc_network_list* loc_network_list_unref(struct loc_network_list* list) {
  80         if (!list)
  81                 return NULL;
  82
  83         if (--list->refcount > 0)
  84                 return list;
  85
  86         loc_network_list_free(list);
  87         return NULL;
  88 }
  89
  90 LOC_EXPORT size_t loc_network_list_size(struct loc_network_list* list) {
  91         return list->size;
  92 }
  93
  94 LOC_EXPORT int loc_network_list_empty(struct loc_network_list* list) {
  95         return list->size == 0;
  96 }
  97
  98 LOC_EXPORT void loc_network_list_clear(struct loc_network_list* list) {
  99         if (!list->elements)
 100                 return;
 101
 102         for (unsigned int i = 0; i < list->size; i++)
 103                 loc_network_unref(list->elements[i]);
 104
 105         free(list->elements);
 106         list->elements_size = 0;
 107
 108         list->size = 0;
 109 }
 110
 111 LOC_EXPORT void loc_network_list_dump(struct loc_network_list* list) {
 112         struct loc_network* network;
 113         char* s;
 114
 115         for (unsigned int i = 0; i < list->size; i++) {
 116                 network = list->elements[i];
 117
 118                 s = loc_network_str(network);
 119
 120                 INFO(list->ctx, "%s\n", s);
 121                 free(s);
 122         }
 123 }
 124
 125 LOC_EXPORT struct loc_network* loc_network_list_get(struct loc_network_list* list, size_t index) {
 126         // Check index
 127         if (index >= list->size)
 128                 return NULL;
 129
 130         return loc_network_ref(list->elements[index]);
 131 }
 132
 133 LOC_EXPORT int loc_network_list_push(struct loc_network_list* list, struct loc_network* network) {
 134         // Do not add networks that are already on the list
 135         if (loc_network_list_contains(list, network))
 136                 return 0;
 137
 138         // Check if we have space left
 139         if (list->size >= list->elements_size) {
 140                 int r = loc_network_list_grow(list, 64);
 141                 if (r)
 142                         return r;
 143         }
 144
 145         DEBUG(list->ctx, "%p: Pushing network %p onto stack\n", list, network);
 146
 147         list->elements[list->size++] = loc_network_ref(network);
 148
 149         return 0;
 150 }
 151
 152 LOC_EXPORT struct loc_network* loc_network_list_pop(struct loc_network_list* list) {
 153         // Return nothing when empty
 154         if (loc_network_list_empty(list)) {
 155                 DEBUG(list->ctx, "%p: Popped empty stack\n", list);
 156                 return NULL;
 157         }
 158
 159         struct loc_network* network = list->elements[--list->size];
 160
 161         DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
 162
 163         return network;
 164 }
 165
 166 LOC_EXPORT struct loc_network* loc_network_list_pop_first(struct loc_network_list* list) {
 167         // Return nothing when empty
 168         if (loc_network_list_empty(list)) {
 169                 DEBUG(list->ctx, "%p: Popped empty stack\n", list);
 170                 return NULL;
 171         }
 172
 173         struct loc_network* network = list->elements[0];
 174
 175         // Move all elements to the top of the stack
 176         for (unsigned int i = 0; i < --list->size; i++) {
 177                 list->elements[i] = list->elements[i+1];
 178         }
 179
 180         DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
 181
 182         return network;
 183 }
 184
 185 LOC_EXPORT int loc_network_list_contains(struct loc_network_list* list, struct loc_network* network) {
 186         for (unsigned int i = 0; i < list->size; i++) {
 187                 if (loc_network_eq(list->elements[i], network))
 188                         return 1;
 189         }
 190
 191         return 0;
 192 }
 193
 194 static void loc_network_list_swap(struct loc_network_list* list, unsigned int i1, unsigned int i2) {
 195         // Do nothing for invalid indices
 196         if (i1 >= list->size || i2 >= list->size)
 197                 return;
 198
 199         struct loc_network* network1 = list->elements[i1];
 200         struct loc_network* network2 = list->elements[i2];
 201
 202         list->elements[i1] = network2;
 203         list->elements[i2] = network1;
 204 }
 205
 206 LOC_EXPORT void loc_network_list_reverse(struct loc_network_list* list) {
 207         unsigned int i = 0;
 208         unsigned int j = list->size - 1;
 209
 210         while (i < j) {
 211                 loc_network_list_swap(list, i++, j--);
 212         }
 213 }
 214
 215 LOC_EXPORT void loc_network_list_sort(struct loc_network_list* list) {
 216         unsigned int n = list->size;
 217         int swapped;
 218
 219         do {
 220                 swapped = 0;
 221
 222                 for (unsigned int i = 1; i < n; i++) {
 223                         if (loc_network_gt(list->elements[i-1], list->elements[i]) > 0) {
 224                                 loc_network_list_swap(list, i-1, i);
 225                                 swapped = 1;
 226                         }
 227                 }
 228
 229                 n--;
 230         } while (swapped);
 231 }
 232
 233 LOC_EXPORT int loc_network_list_merge(
 234                 struct loc_network_list* self, struct loc_network_list* other) {
 235         int r;
 236
 237         for (unsigned int i = 0; i < other->size; i++) {
 238                 r = loc_network_list_push(self, other->elements[i]);
 239                 if (r)
 240                         return r;
 241         }
 242
 243         return 0;
 244 }