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         for (unsigned int i = 0; i < list->size; i++)
 100                 loc_network_unref(list->elements[i]);
 101
 102         list->size = 0;
 103 }
 104
 105 LOC_EXPORT void loc_network_list_dump(struct loc_network_list* list) {
 106         struct loc_network* network;
 107         char* s;
 108
 109         for (unsigned int i = 0; i < list->size; i++) {
 110                 network = list->elements[i];
 111
 112                 s = loc_network_str(network);
 113
 114                 INFO(list->ctx, "%s\n", s);
 115                 free(s);
 116         }
 117 }
 118
 119 LOC_EXPORT struct loc_network* loc_network_list_get(struct loc_network_list* list, size_t index) {
 120         // Check index
 121         if (index >= list->size)
 122                 return NULL;
 123
 124         return loc_network_ref(list->elements[index]);
 125 }
 126
 127 LOC_EXPORT int loc_network_list_push(struct loc_network_list* list, struct loc_network* network) {
 128         // Do not add networks that are already on the list
 129         if (loc_network_list_contains(list, network))
 130                 return 0;
 131
 132         // Check if we have space left
 133         if (list->size >= list->elements_size) {
 134                 int r = loc_network_list_grow(list, 64);
 135                 if (r)
 136                         return r;
 137         }
 138
 139         DEBUG(list->ctx, "%p: Pushing network %p onto stack\n", list, network);
 140
 141         list->elements[list->size++] = loc_network_ref(network);
 142
 143         return 0;
 144 }
 145
 146 LOC_EXPORT struct loc_network* loc_network_list_pop(struct loc_network_list* list) {
 147         // Return nothing when empty
 148         if (loc_network_list_empty(list)) {
 149                 DEBUG(list->ctx, "%p: Popped empty stack\n", list);
 150                 return NULL;
 151         }
 152
 153         struct loc_network* network = list->elements[--list->size];
 154
 155         DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
 156
 157         return network;
 158 }
 159
 160 LOC_EXPORT struct loc_network* loc_network_list_pop_first(struct loc_network_list* list) {
 161         // Return nothing when empty
 162         if (loc_network_list_empty(list)) {
 163                 DEBUG(list->ctx, "%p: Popped empty stack\n", list);
 164                 return NULL;
 165         }
 166
 167         struct loc_network* network = list->elements[0];
 168
 169         // Move all elements to the top of the stack
 170         for (unsigned int i = 0; i < --list->size; i++) {
 171                 list->elements[i] = list->elements[i+1];
 172         }
 173
 174         DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
 175
 176         return network;
 177 }
 178
 179 LOC_EXPORT int loc_network_list_contains(struct loc_network_list* list, struct loc_network* network) {
 180         for (unsigned int i = 0; i < list->size; i++) {
 181                 if (loc_network_eq(list->elements[i], network))
 182                         return 1;
 183         }
 184
 185         return 0;
 186 }
 187
 188 static void loc_network_list_swap(struct loc_network_list* list, unsigned int i1, unsigned int i2) {
 189         // Do nothing for invalid indices
 190         if (i1 >= list->size || i2 >= list->size)
 191                 return;
 192
 193         struct loc_network* network1 = list->elements[i1];
 194         struct loc_network* network2 = list->elements[i2];
 195
 196         list->elements[i1] = network2;
 197         list->elements[i2] = network1;
 198 }
 199
 200 LOC_EXPORT void loc_network_list_reverse(struct loc_network_list* list) {
 201         unsigned int i = 0;
 202         unsigned int j = list->size - 1;
 203
 204         while (i < j) {
 205                 loc_network_list_swap(list, i++, j--);
 206         }
 207 }
 208
 209 LOC_EXPORT void loc_network_list_sort(struct loc_network_list* list) {
 210         unsigned int n = list->size;
 211         int swapped;
 212
 213         do {
 214                 swapped = 0;
 215
 216                 for (unsigned int i = 1; i < n; i++) {
 217                         if (loc_network_gt(list->elements[i-1], list->elements[i]) > 0) {
 218                                 loc_network_list_swap(list, i-1, i);
 219                                 swapped = 1;
 220                         }
 221                 }
 222
 223                 n--;
 224         } while (swapped);
 225 }
 226
 227 LOC_EXPORT int loc_network_list_merge(
 228                 struct loc_network_list* self, struct loc_network_list* other) {
 229         int r;
 230
 231         for (unsigned int i = 0; i < other->size; i++) {
 232                 r = loc_network_list_push(self, other->elements[i]);
 233                 if (r)
 234                         return r;
 235         }
 236
 237         return 0;
 238 }