src/network.c

   1 /*
   2         libloc - A library to determine the location of someone on the Internet
   3
   4         Copyright (C) 2017 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 <arpa/inet.h>
  18 #include <assert.h>
  19 #include <errno.h>
  20 #include <stdio.h>
  21 #include <stdlib.h>
  22 #include <string.h>
  23
  24 #ifdef HAVE_ENDIAN_H
  25 #  include <endian.h>
  26 #endif
  27
  28 #include <loc/libloc.h>
  29 #include <loc/compat.h>
  30 #include <loc/country.h>
  31 #include <loc/network.h>
  32 #include <loc/private.h>
  33
  34 struct loc_network {
  35         struct loc_ctx* ctx;
  36         int refcount;
  37
  38         int family;
  39         struct in6_addr first_address;
  40         struct in6_addr last_address;
  41         unsigned int prefix;
  42
  43         char country_code[3];
  44         uint32_t asn;
  45         enum loc_network_flags flags;
  46 };
  47
  48 static int valid_prefix(struct in6_addr* address, unsigned int prefix) {
  49         // The prefix cannot be larger than 128 bits
  50         if (prefix > 128)
  51                 return 1;
  52
  53         // And the prefix cannot be zero
  54         if (prefix == 0)
  55                 return 1;
  56
  57         // For IPv4-mapped addresses the prefix has to be 96 or lager
  58         if (IN6_IS_ADDR_V4MAPPED(address) && prefix <= 96)
  59                 return 1;
  60
  61         return 0;
  62 }
  63
  64 static struct in6_addr prefix_to_bitmask(unsigned int prefix) {
  65         struct in6_addr bitmask;
  66
  67         for (unsigned int i = 0; i < 16; i++)
  68                 bitmask.s6_addr[i] = 0;
  69
  70         for (int i = prefix, j = 0; i > 0; i -= 8, j++) {
  71                 if (i >= 8)
  72                         bitmask.s6_addr[j] = 0xff;
  73                 else
  74                         bitmask.s6_addr[j] = 0xff << (8 - i);
  75         }
  76
  77         return bitmask;
  78 }
  79
  80 static struct in6_addr make_first_address(const struct in6_addr* address, const struct in6_addr* bitmask) {
  81         struct in6_addr a;
  82
  83         // Perform bitwise AND
  84         for (unsigned int i = 0; i < 4; i++)
  85                 a.s6_addr32[i] = address->s6_addr32[i] & bitmask->s6_addr32[i];
  86
  87         return a;
  88 }
  89
  90 static struct in6_addr make_last_address(const struct in6_addr* address, const struct in6_addr* bitmask) {
  91         struct in6_addr a;
  92
  93         // Perform bitwise OR
  94         for (unsigned int i = 0; i < 4; i++)
  95                 a.s6_addr32[i] = address->s6_addr32[i] | ~bitmask->s6_addr32[i];
  96
  97         return a;
  98 }
  99
 100 static struct in6_addr address_increment(const struct in6_addr* address) {
 101         struct in6_addr a = *address;
 102
 103         for (int octet = 15; octet >= 0; octet--) {
 104                 if (a.s6_addr[octet] < 255) {
 105                         a.s6_addr[octet]++;
 106                         break;
 107                 } else {
 108                         a.s6_addr[octet] = 0;
 109                 }
 110         }
 111
 112         return a;
 113 }
 114
 115 LOC_EXPORT int loc_network_new(struct loc_ctx* ctx, struct loc_network** network,
 116                 struct in6_addr* address, unsigned int prefix) {
 117         // Address cannot be unspecified
 118         if (IN6_IS_ADDR_UNSPECIFIED(address)) {
 119                 DEBUG(ctx, "Start address is unspecified\n");
 120                 return -EINVAL;
 121         }
 122
 123         // Address cannot be loopback
 124         if (IN6_IS_ADDR_LOOPBACK(address)) {
 125                 DEBUG(ctx, "Start address is loopback address\n");
 126                 return -EINVAL;
 127         }
 128
 129         // Address cannot be link-local
 130         if (IN6_IS_ADDR_LINKLOCAL(address)) {
 131                 DEBUG(ctx, "Start address cannot be link-local\n");
 132                 return -EINVAL;
 133         }
 134
 135         // Address cannot be site-local
 136         if (IN6_IS_ADDR_SITELOCAL(address)) {
 137                 DEBUG(ctx, "Start address cannot be site-local\n");
 138                 return -EINVAL;
 139         }
 140
 141         // Validate the prefix
 142         if (valid_prefix(address, prefix) != 0) {
 143                 DEBUG(ctx, "Invalid prefix: %u\n", prefix);
 144                 return -EINVAL;
 145         }
 146
 147         struct loc_network* n = calloc(1, sizeof(*n));
 148         if (!n)
 149                 return -ENOMEM;
 150
 151         n->ctx = loc_ref(ctx);
 152         n->refcount = 1;
 153
 154         // Store the prefix
 155         n->prefix = prefix;
 156
 157         // Convert the prefix into a bitmask
 158         struct in6_addr bitmask = prefix_to_bitmask(n->prefix);
 159
 160         // Store the first and last address in the network
 161         n->first_address = make_first_address(address, &bitmask);
 162         n->last_address = make_last_address(&n->first_address, &bitmask);
 163
 164         // Set family
 165         if (IN6_IS_ADDR_V4MAPPED(&n->first_address))
 166                 n->family = AF_INET;
 167         else
 168                 n->family = AF_INET6;
 169
 170         DEBUG(n->ctx, "Network allocated at %p\n", n);
 171         *network = n;
 172         return 0;
 173 }
 174
 175 LOC_EXPORT int loc_network_new_from_string(struct loc_ctx* ctx, struct loc_network** network,
 176                 const char* address_string) {
 177         struct in6_addr first_address;
 178         char* prefix_string;
 179         unsigned int prefix = 128;
 180         int r = -EINVAL;
 181
 182         DEBUG(ctx, "Attempting to parse network %s\n", address_string);
 183
 184         // Make a copy of the string to work on it
 185         char* buffer = strdup(address_string);
 186         address_string = prefix_string = buffer;
 187
 188         // Split address and prefix
 189         address_string = strsep(&prefix_string, "/");
 190
 191         DEBUG(ctx, "  Split into address = %s, prefix = %s\n", address_string, prefix_string);
 192
 193         // Parse the address
 194         r = loc_parse_address(ctx, address_string, &first_address);
 195         if (r) {
 196                 DEBUG(ctx, "The address could not be parsed\n");
 197                 goto FAIL;
 198         }
 199
 200         // If a prefix was given, we will try to parse it
 201         if (prefix_string) {
 202                 // Convert prefix to integer
 203                 prefix = strtol(prefix_string, NULL, 10);
 204
 205                 if (!prefix) {
 206                         DEBUG(ctx, "The prefix was not parsable: %s\n", prefix_string);
 207                         goto FAIL;
 208                 }
 209
 210                 // Map the prefix to IPv6 if needed
 211                 if (IN6_IS_ADDR_V4MAPPED(&first_address))
 212                         prefix += 96;
 213         }
 214
 215 FAIL:
 216         // Free temporary buffer
 217         free(buffer);
 218
 219         // Exit if the parsing was unsuccessful
 220         if (r)
 221                 return r;
 222
 223         // Create a new network
 224         return loc_network_new(ctx, network, &first_address, prefix);
 225 }
 226
 227 LOC_EXPORT struct loc_network* loc_network_ref(struct loc_network* network) {
 228         network->refcount++;
 229
 230         return network;
 231 }
 232
 233 static void loc_network_free(struct loc_network* network) {
 234         DEBUG(network->ctx, "Releasing network at %p\n", network);
 235
 236         loc_unref(network->ctx);
 237         free(network);
 238 }
 239
 240 LOC_EXPORT struct loc_network* loc_network_unref(struct loc_network* network) {
 241         if (!network)
 242                 return NULL;
 243
 244         if (--network->refcount > 0)
 245                 return network;
 246
 247         loc_network_free(network);
 248         return NULL;
 249 }
 250
 251 static int format_ipv6_address(const struct in6_addr* address, char* string, size_t length) {
 252         const char* ret = inet_ntop(AF_INET6, address, string, length);
 253         if (!ret)
 254                 return -1;
 255
 256         return 0;
 257 }
 258
 259 static int format_ipv4_address(const struct in6_addr* address, char* string, size_t length) {
 260         struct in_addr ipv4_address;
 261         ipv4_address.s_addr = address->s6_addr32[3];
 262
 263         const char* ret = inet_ntop(AF_INET, &ipv4_address, string, length);
 264         if (!ret)
 265                 return -1;
 266
 267         return 0;
 268 }
 269
 270 LOC_EXPORT char* loc_network_str(struct loc_network* network) {
 271         int r;
 272         const size_t length = INET6_ADDRSTRLEN + 4;
 273
 274         char* string = malloc(length);
 275         if (!string)
 276                 return NULL;
 277
 278         unsigned int prefix = network->prefix;
 279
 280         switch (network->family) {
 281                 case AF_INET6:
 282                         r = format_ipv6_address(&network->first_address, string, length);
 283                         break;
 284
 285                 case AF_INET:
 286                         r = format_ipv4_address(&network->first_address, string, length);
 287                         prefix -= 96;
 288                         break;
 289
 290                 default:
 291                         r = -1;
 292                         break;
 293         }
 294
 295         if (r) {
 296                 ERROR(network->ctx, "Could not convert network to string: %s\n", strerror(errno));
 297                 free(string);
 298
 299                 return NULL;
 300         }
 301
 302         // Append prefix
 303         sprintf(string + strlen(string), "/%u", prefix);
 304
 305         return string;
 306 }
 307
 308 LOC_EXPORT int loc_network_address_family(struct loc_network* network) {
 309         return network->family;
 310 }
 311
 312 static char* loc_network_format_address(struct loc_network* network, const struct in6_addr* address) {
 313         const size_t length = INET6_ADDRSTRLEN;
 314
 315         char* string = malloc(length);
 316         if (!string)
 317                 return NULL;
 318
 319         int r = 0;
 320
 321         switch (network->family) {
 322                 case AF_INET6:
 323                         r = format_ipv6_address(address, string, length);
 324                         break;
 325
 326                 case AF_INET:
 327                         r = format_ipv4_address(address, string, length);
 328                         break;
 329
 330                 default:
 331                         r = -1;
 332                         break;
 333         }
 334
 335         if (r) {
 336                 ERROR(network->ctx, "Could not format IP address to string: %s\n", strerror(errno));
 337                 free(string);
 338
 339                 return NULL;
 340         }
 341
 342         return string;
 343 }
 344
 345 LOC_EXPORT char* loc_network_format_first_address(struct loc_network* network) {
 346         return loc_network_format_address(network, &network->first_address);
 347 }
 348
 349 LOC_EXPORT char* loc_network_format_last_address(struct loc_network* network) {
 350         return loc_network_format_address(network, &network->last_address);
 351 }
 352
 353 LOC_EXPORT int loc_network_match_address(struct loc_network* network, const struct in6_addr* address) {
 354         // Address must be larger than the start address
 355         if (in6_addr_cmp(&network->first_address, address) > 0)
 356                 return 1;
 357
 358         // Address must be smaller than the last address
 359         if (in6_addr_cmp(&network->last_address, address) < 0)
 360                 return 1;
 361
 362         // The address is inside this network
 363         return 0;
 364 }
 365
 366 LOC_EXPORT const char* loc_network_get_country_code(struct loc_network* network) {
 367         return network->country_code;
 368 }
 369
 370 LOC_EXPORT int loc_network_set_country_code(struct loc_network* network, const char* country_code) {
 371         // Set empty country code
 372         if (!country_code || !*country_code) {
 373                 *network->country_code = '\0';
 374                 return 0;
 375         }
 376
 377         // Check country code
 378         if (!loc_country_code_is_valid(country_code))
 379                 return -EINVAL;
 380
 381         loc_country_code_copy(network->country_code, country_code);
 382
 383         return 0;
 384 }
 385
 386 LOC_EXPORT int loc_network_match_country_code(struct loc_network* network, const char* country_code) {
 387         // Check country code
 388         if (!loc_country_code_is_valid(country_code))
 389                 return -EINVAL;
 390
 391         return (network->country_code[0] == country_code[0])
 392                 && (network->country_code[1] == country_code[1]);
 393 }
 394
 395 LOC_EXPORT uint32_t loc_network_get_asn(struct loc_network* network) {
 396         return network->asn;
 397 }
 398
 399 LOC_EXPORT int loc_network_set_asn(struct loc_network* network, uint32_t asn) {
 400         network->asn = asn;
 401
 402         return 0;
 403 }
 404
 405 LOC_EXPORT int loc_network_match_asn(struct loc_network* network, uint32_t asn) {
 406         return network->asn == asn;
 407 }
 408
 409 LOC_EXPORT int loc_network_has_flag(struct loc_network* network, uint32_t flag) {
 410         return network->flags & flag;
 411 }
 412
 413 LOC_EXPORT int loc_network_set_flag(struct loc_network* network, uint32_t flag) {
 414         network->flags |= flag;
 415
 416         return 0;
 417 }
 418
 419 LOC_EXPORT int loc_network_match_flag(struct loc_network* network, uint32_t flag) {
 420         return loc_network_has_flag(network, flag);
 421 }
 422
 423 LOC_EXPORT int loc_network_eq(struct loc_network* self, struct loc_network* other) {
 424         // Family must be the same
 425         if (self->family != other->family)
 426                 return 0;
 427
 428         // The start address must be the same
 429         if (in6_addr_cmp(&self->first_address, &other->first_address) != 0)
 430                 return 0;
 431
 432         // The prefix length must be the same
 433         if (self->prefix != other->prefix)
 434                 return 0;
 435
 436         return 1;
 437 }
 438
 439 static int loc_network_gt(struct loc_network* self, struct loc_network* other) {
 440         // Families must match
 441         if (self->family != other->family)
 442                 return -1;
 443
 444         int r = in6_addr_cmp(&self->first_address, &other->first_address);
 445
 446         switch (r) {
 447                 // Smaller
 448                 case -1:
 449                         return 0;
 450
 451                 // Larger
 452                 case 1:
 453                         return 1;
 454
 455                 default:
 456                         break;
 457         }
 458
 459         if (self->prefix > other->prefix)
 460                 return 1;
 461
 462         // Dunno
 463         return 0;
 464 }
 465
 466 LOC_EXPORT int loc_network_overlaps(struct loc_network* self, struct loc_network* other) {
 467         if (loc_network_match_address(self, &other->first_address) == 0)
 468                 return 1;
 469
 470         if (loc_network_match_address(self, &other->last_address) == 0)
 471                 return 1;
 472
 473         if (loc_network_match_address(other, &self->first_address) == 0)
 474                 return 1;
 475
 476         if (loc_network_match_address(other, &self->last_address) == 0)
 477                 return 1;
 478
 479         return 0;
 480 }
 481
 482 LOC_EXPORT int loc_network_is_subnet_of(struct loc_network* self, struct loc_network* other) {
 483         // If the start address of the other network is smaller than this network,
 484         // it cannot be a subnet.
 485         if (in6_addr_cmp(&self->first_address, &other->first_address) < 0)
 486                 return 0;
 487
 488         // If the end address of the other network is greater than this network,
 489         // it cannot be a subnet.
 490         if (in6_addr_cmp(&self->last_address, &other->last_address) > 0)
 491                 return 0;
 492
 493         return 1;
 494 }
 495
 496 LOC_EXPORT struct loc_network_list* loc_network_subnets(struct loc_network* network) {
 497         struct loc_network_list* list;
 498
 499         // New prefix length
 500         unsigned int prefix = network->prefix + 1;
 501
 502         // Check if the new prefix is valid
 503         if (valid_prefix(&network->first_address, prefix))
 504                 return NULL;
 505
 506         // Create a new list with the result
 507         int r = loc_network_list_new(network->ctx, &list);
 508         if (r) {
 509                 ERROR(network->ctx, "Could not create network list: %d\n", r);
 510                 return NULL;
 511         }
 512
 513         struct loc_network* subnet1 = NULL;
 514         struct loc_network* subnet2 = NULL;
 515
 516         // Create the first half of the network
 517         r = loc_network_new(network->ctx, &subnet1, &network->first_address, prefix);
 518         if (r)
 519                 goto ERROR;
 520
 521         // The next subnet starts after the first one
 522         struct in6_addr first_address = address_increment(&subnet1->last_address);
 523
 524         // Create the second half of the network
 525         r = loc_network_new(network->ctx, &subnet2, &first_address, prefix);
 526         if (r)
 527                 goto ERROR;
 528
 529         // Push the both onto the stack (in reverse order)
 530         r = loc_network_list_push(list, subnet2);
 531         if (r)
 532                 goto ERROR;
 533
 534         r = loc_network_list_push(list, subnet1);
 535         if (r)
 536                 goto ERROR;
 537
 538         loc_network_unref(subnet1);
 539         loc_network_unref(subnet2);
 540
 541         return list;
 542
 543 ERROR:
 544         if (subnet1)
 545                 loc_network_unref(subnet1);
 546
 547         if (subnet2)
 548                 loc_network_unref(subnet2);
 549
 550         if (list)
 551                 loc_network_list_unref(list);
 552
 553         return NULL;
 554 }
 555
 556 LOC_EXPORT struct loc_network_list* loc_network_exclude(
 557                 struct loc_network* self, struct loc_network* other) {
 558         struct loc_network_list* list;
 559
 560 #ifdef ENABLE_DEBUG
 561         char* n1 = loc_network_str(self);
 562         char* n2 = loc_network_str(other);
 563
 564         DEBUG(self->ctx, "Returning %s excluding %s...\n", n1, n2);
 565
 566         free(n1);
 567         free(n2);
 568 #endif
 569
 570         // Family must match
 571         if (self->family != other->family) {
 572                 DEBUG(self->ctx, "Family mismatch\n");
 573
 574                 return NULL;
 575         }
 576
 577         // Other must be a subnet of self
 578         if (!loc_network_is_subnet_of(other, self)) {
 579                 DEBUG(self->ctx, "Network %p is not contained in network %p\n", other, self);
 580
 581                 return NULL;
 582         }
 583
 584         // We cannot perform this operation if both networks equal
 585         if (loc_network_eq(self, other)) {
 586                 DEBUG(self->ctx, "Networks %p and %p are equal\n", self, other);
 587
 588                 return NULL;
 589         }
 590
 591         // Create a new list with the result
 592         int r = loc_network_list_new(self->ctx, &list);
 593         if (r) {
 594                 ERROR(self->ctx, "Could not create network list: %d\n", r);
 595                 return NULL;
 596         }
 597
 598         struct loc_network_list* subnets = loc_network_subnets(self);
 599
 600         struct loc_network* subnet1 = NULL;
 601         struct loc_network* subnet2 = NULL;
 602
 603         while (subnets) {
 604                 // Fetch both subnets
 605                 subnet1 = loc_network_list_get(subnets, 0);
 606                 subnet2 = loc_network_list_get(subnets, 1);
 607
 608                 // Free list
 609                 loc_network_list_unref(subnets);
 610                 subnets = NULL;
 611
 612                 if (loc_network_eq(other, subnet1)) {
 613                         r = loc_network_list_push(list, subnet2);
 614                         if (r)
 615                                 goto ERROR;
 616
 617                 } else if (loc_network_eq(other, subnet2)) {
 618                         r = loc_network_list_push(list, subnet1);
 619                         if (r)
 620                                 goto ERROR;
 621
 622                 } else  if (loc_network_is_subnet_of(other, subnet1)) {
 623                         r = loc_network_list_push(list, subnet2);
 624                         if (r)
 625                                 goto ERROR;
 626
 627                         subnets = loc_network_subnets(subnet1);
 628
 629                 } else if (loc_network_is_subnet_of(other, subnet2)) {
 630                         r = loc_network_list_push(list, subnet1);
 631                         if (r)
 632                                 goto ERROR;
 633
 634                         subnets = loc_network_subnets(subnet2);
 635
 636                 } else {
 637                         ERROR(self->ctx, "We should never get here\n");
 638                         goto ERROR;
 639                 }
 640
 641                 loc_network_unref(subnet1);
 642                 loc_network_unref(subnet2);
 643         }
 644
 645 #ifdef ENABLE_DEBUG
 646         loc_network_list_dump(list);
 647 #endif
 648
 649         // Return the result
 650         return list;
 651
 652 ERROR:
 653         if (subnet1)
 654                 loc_network_unref(subnet1);
 655
 656         if (subnet2)
 657                 loc_network_unref(subnet2);
 658
 659         if (list)
 660                 loc_network_list_unref(list);
 661
 662         return NULL;
 663 }
 664
 665 LOC_EXPORT int loc_network_to_database_v1(struct loc_network* network, struct loc_database_network_v1* dbobj) {
 666         // Add country code
 667         loc_country_code_copy(dbobj->country_code, network->country_code);
 668
 669         // Add ASN
 670         dbobj->asn = htobe32(network->asn);
 671
 672         // Flags
 673         dbobj->flags = htobe16(network->flags);
 674
 675         return 0;
 676 }
 677
 678 LOC_EXPORT int loc_network_new_from_database_v1(struct loc_ctx* ctx, struct loc_network** network,
 679                 struct in6_addr* address, unsigned int prefix, const struct loc_database_network_v1* dbobj) {
 680         char country_code[3] = "\0\0";
 681
 682         int r = loc_network_new(ctx, network, address, prefix);
 683         if (r) {
 684                 ERROR(ctx, "Could not allocate a new network: %s", strerror(-r));
 685                 return r;
 686         }
 687
 688         // Import country code
 689         loc_country_code_copy(country_code, dbobj->country_code);
 690
 691         r = loc_network_set_country_code(*network, country_code);
 692         if (r) {
 693                 ERROR(ctx, "Could not set country code: %s\n", country_code);
 694                 return r;
 695         }
 696
 697         // Import ASN
 698         uint32_t asn = be32toh(dbobj->asn);
 699         r = loc_network_set_asn(*network, asn);
 700         if (r) {
 701                 ERROR(ctx, "Could not set ASN: %d\n", asn);
 702                 return r;
 703         }
 704
 705         // Import flags
 706         int flags = be16toh(dbobj->flags);
 707         r = loc_network_set_flag(*network, flags);
 708         if (r) {
 709                 ERROR(ctx, "Could not set flags: %d\n", flags);
 710                 return r;
 711         }
 712
 713         return 0;
 714 }
 715
 716 struct loc_network_tree {
 717         struct loc_ctx* ctx;
 718         int refcount;
 719
 720         struct loc_network_tree_node* root;
 721 };
 722
 723 struct loc_network_tree_node {
 724         struct loc_ctx* ctx;
 725         int refcount;
 726
 727         struct loc_network_tree_node* zero;
 728         struct loc_network_tree_node* one;
 729
 730         struct loc_network* network;
 731 };
 732
 733 LOC_EXPORT int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree) {
 734         struct loc_network_tree* t = calloc(1, sizeof(*t));
 735         if (!t)
 736                 return -ENOMEM;
 737
 738         t->ctx = loc_ref(ctx);
 739         t->refcount = 1;
 740
 741         // Create the root node
 742         int r = loc_network_tree_node_new(ctx, &t->root);
 743         if (r) {
 744                 loc_network_tree_unref(t);
 745                 return r;
 746         }
 747
 748         DEBUG(t->ctx, "Network tree allocated at %p\n", t);
 749         *tree = t;
 750         return 0;
 751 }
 752
 753 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_get_root(struct loc_network_tree* tree) {
 754         return loc_network_tree_node_ref(tree->root);
 755 }
 756
 757 static struct loc_network_tree_node* loc_network_tree_get_node(struct loc_network_tree_node* node, int path) {
 758         struct loc_network_tree_node** n;
 759
 760         if (path == 0)
 761                 n = &node->zero;
 762         else
 763                 n = &node->one;
 764
 765         // If the desired node doesn't exist, yet, we will create it
 766         if (*n == NULL) {
 767                 int r = loc_network_tree_node_new(node->ctx, n);
 768                 if (r)
 769                         return NULL;
 770         }
 771
 772         return *n;
 773 }
 774
 775 static struct loc_network_tree_node* loc_network_tree_get_path(struct loc_network_tree* tree, const struct in6_addr* address, unsigned int prefix) {
 776         struct loc_network_tree_node* node = tree->root;
 777
 778         for (unsigned int i = 0; i < prefix; i++) {
 779                 // Check if the ith bit is one or zero
 780                 node = loc_network_tree_get_node(node, in6_addr_get_bit(address, i));
 781         }
 782
 783         return node;
 784 }
 785
 786 static int __loc_network_tree_walk(struct loc_ctx* ctx, struct loc_network_tree_node* node,
 787                 int(*filter_callback)(struct loc_network* network, void* data),
 788                 int(*callback)(struct loc_network* network, void* data), void* data) {
 789         int r;
 790
 791         // Finding a network ends the walk here
 792         if (node->network) {
 793                 if (filter_callback) {
 794                         int f = filter_callback(node->network, data);
 795                         if (f < 0)
 796                                 return f;
 797
 798                         // Skip network if filter function returns value greater than zero
 799                         if (f > 0)
 800                                 return 0;
 801                 }
 802
 803                 r = callback(node->network, data);
 804                 if (r)
 805                         return r;
 806         }
 807
 808         // Walk down on the left side of the tree first
 809         if (node->zero) {
 810                 r = __loc_network_tree_walk(ctx, node->zero, filter_callback, callback, data);
 811                 if (r)
 812                         return r;
 813         }
 814
 815         // Then walk on the other side
 816         if (node->one) {
 817                 r = __loc_network_tree_walk(ctx, node->one, filter_callback, callback, data);
 818                 if (r)
 819                         return r;
 820         }
 821
 822         return 0;
 823 }
 824
 825 LOC_EXPORT int loc_network_tree_walk(struct loc_network_tree* tree,
 826                 int(*filter_callback)(struct loc_network* network, void* data),
 827                 int(*callback)(struct loc_network* network, void* data), void* data) {
 828         return __loc_network_tree_walk(tree->ctx, tree->root, filter_callback, callback, data);
 829 }
 830
 831 static void loc_network_tree_free(struct loc_network_tree* tree) {
 832         DEBUG(tree->ctx, "Releasing network tree at %p\n", tree);
 833
 834         loc_network_tree_node_unref(tree->root);
 835
 836         loc_unref(tree->ctx);
 837         free(tree);
 838 }
 839
 840 LOC_EXPORT struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) {
 841         if (--tree->refcount > 0)
 842                 return tree;
 843
 844         loc_network_tree_free(tree);
 845         return NULL;
 846 }
 847
 848 static int __loc_network_tree_dump(struct loc_network* network, void* data) {
 849         DEBUG(network->ctx, "Dumping network at %p\n", network);
 850
 851         char* s = loc_network_str(network);
 852         if (!s)
 853                 return 1;
 854
 855         INFO(network->ctx, "%s\n", s);
 856         free(s);
 857
 858         return 0;
 859 }
 860
 861 LOC_EXPORT int loc_network_tree_dump(struct loc_network_tree* tree) {
 862         DEBUG(tree->ctx, "Dumping network tree at %p\n", tree);
 863
 864         return loc_network_tree_walk(tree, NULL, __loc_network_tree_dump, NULL);
 865 }
 866
 867 LOC_EXPORT int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_network* network) {
 868         DEBUG(tree->ctx, "Adding network %p to tree %p\n", network, tree);
 869
 870         struct loc_network_tree_node* node = loc_network_tree_get_path(tree,
 871                         &network->first_address, network->prefix);
 872         if (!node) {
 873                 ERROR(tree->ctx, "Could not find a node\n");
 874                 return -ENOMEM;
 875         }
 876
 877         // Check if node has not been set before
 878         if (node->network) {
 879                 DEBUG(tree->ctx, "There is already a network at this path\n");
 880                 return -EBUSY;
 881         }
 882
 883         // Point node to the network
 884         node->network = loc_network_ref(network);
 885
 886         return 0;
 887 }
 888
 889 static int __loc_network_tree_count(struct loc_network* network, void* data) {
 890         size_t* counter = (size_t*)data;
 891
 892         // Increase the counter for each network
 893         counter++;
 894
 895         return 0;
 896 }
 897
 898 LOC_EXPORT size_t loc_network_tree_count_networks(struct loc_network_tree* tree) {
 899         size_t counter = 0;
 900
 901         int r = loc_network_tree_walk(tree, NULL, __loc_network_tree_count, &counter);
 902         if (r)
 903                 return r;
 904
 905         return counter;
 906 }
 907
 908 static size_t __loc_network_tree_count_nodes(struct loc_network_tree_node* node) {
 909         size_t counter = 1;
 910
 911         if (node->zero)
 912                 counter += __loc_network_tree_count_nodes(node->zero);
 913
 914         if (node->one)
 915                 counter += __loc_network_tree_count_nodes(node->one);
 916
 917         return counter;
 918 }
 919
 920 LOC_EXPORT size_t loc_network_tree_count_nodes(struct loc_network_tree* tree) {
 921         return __loc_network_tree_count_nodes(tree->root);
 922 }
 923
 924 LOC_EXPORT int loc_network_tree_node_new(struct loc_ctx* ctx, struct loc_network_tree_node** node) {
 925         struct loc_network_tree_node* n = calloc(1, sizeof(*n));
 926         if (!n)
 927                 return -ENOMEM;
 928
 929         n->ctx = loc_ref(ctx);
 930         n->refcount = 1;
 931
 932         n->zero = n->one = NULL;
 933
 934         DEBUG(n->ctx, "Network node allocated at %p\n", n);
 935         *node = n;
 936         return 0;
 937 }
 938
 939 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_ref(struct loc_network_tree_node* node) {
 940         if (node)
 941                 node->refcount++;
 942
 943         return node;
 944 }
 945
 946 static void loc_network_tree_node_free(struct loc_network_tree_node* node) {
 947         DEBUG(node->ctx, "Releasing network node at %p\n", node);
 948
 949         if (node->network)
 950                 loc_network_unref(node->network);
 951
 952         if (node->zero)
 953                 loc_network_tree_node_unref(node->zero);
 954
 955         if (node->one)
 956                 loc_network_tree_node_unref(node->one);
 957
 958         loc_unref(node->ctx);
 959         free(node);
 960 }
 961
 962 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_unref(struct loc_network_tree_node* node) {
 963         if (!node)
 964                 return NULL;
 965
 966         if (--node->refcount > 0)
 967                 return node;
 968
 969         loc_network_tree_node_free(node);
 970         return NULL;
 971 }
 972
 973 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_get(struct loc_network_tree_node* node, unsigned int index) {
 974         if (index == 0)
 975                 node = node->zero;
 976         else
 977                 node = node->one;
 978
 979         if (!node)
 980                 return NULL;
 981
 982         return loc_network_tree_node_ref(node);
 983 }
 984
 985 LOC_EXPORT int loc_network_tree_node_is_leaf(struct loc_network_tree_node* node) {
 986         return (!!node->network);
 987 }
 988
 989 LOC_EXPORT struct loc_network* loc_network_tree_node_get_network(struct loc_network_tree_node* node) {
 990         return loc_network_ref(node->network);
 991 }
 992
 993 // List
 994
 995 struct loc_network_list {
 996         struct loc_ctx* ctx;
 997         int refcount;
 998
 999         struct loc_network* list[1024];
1000         size_t size;
1001         size_t max_size;
1002 };
1003
1004 LOC_EXPORT int loc_network_list_new(struct loc_ctx* ctx,
1005                 struct loc_network_list** list) {
1006         struct loc_network_list* l = calloc(1, sizeof(*l));
1007         if (!l)
1008                 return -ENOMEM;
1009
1010         l->ctx = loc_ref(ctx);
1011         l->refcount = 1;
1012
1013         // Do not allow this list to grow larger than this
1014         l->max_size = 1024;
1015
1016         DEBUG(l->ctx, "Network list allocated at %p\n", l);
1017         *list = l;
1018         return 0;
1019 }
1020
1021 LOC_EXPORT struct loc_network_list* loc_network_list_ref(struct loc_network_list* list) {
1022         list->refcount++;
1023
1024         return list;
1025 }
1026
1027 static void loc_network_list_free(struct loc_network_list* list) {
1028         DEBUG(list->ctx, "Releasing network list at %p\n", list);
1029
1030         for (unsigned int i = 0; i < list->size; i++)
1031                 loc_network_unref(list->list[i]);
1032
1033         loc_unref(list->ctx);
1034         free(list);
1035 }
1036
1037 LOC_EXPORT struct loc_network_list* loc_network_list_unref(struct loc_network_list* list) {
1038         if (!list)
1039                 return NULL;
1040
1041         if (--list->refcount > 0)
1042                 return list;
1043
1044         loc_network_list_free(list);
1045         return NULL;
1046 }
1047
1048 LOC_EXPORT size_t loc_network_list_size(struct loc_network_list* list) {
1049         return list->size;
1050 }
1051
1052 LOC_EXPORT int loc_network_list_empty(struct loc_network_list* list) {
1053         return list->size == 0;
1054 }
1055
1056 LOC_EXPORT void loc_network_list_clear(struct loc_network_list* list) {
1057         for (unsigned int i = 0; i < list->size; i++)
1058                 loc_network_unref(list->list[i]);
1059
1060         list->size = 0;
1061 }
1062
1063 LOC_EXPORT void loc_network_list_dump(struct loc_network_list* list) {
1064         struct loc_network* network;
1065         char* s;
1066
1067         for (unsigned int i = 0; i < list->size; i++) {
1068                 network = list->list[i];
1069
1070                 s = loc_network_str(network);
1071
1072                 INFO(list->ctx, "%s\n", s);
1073                 free(s);
1074         }
1075 }
1076
1077 LOC_EXPORT struct loc_network* loc_network_list_get(struct loc_network_list* list, size_t index) {
1078         // Check index
1079         if (index >= list->size)
1080                 return NULL;
1081
1082         return loc_network_ref(list->list[index]);
1083 }
1084
1085 LOC_EXPORT int loc_network_list_push(struct loc_network_list* list, struct loc_network* network) {
1086         // Do not add networks that are already on the list
1087         if (loc_network_list_contains(list, network))
1088                 return 0;
1089
1090         // Check if we have space left
1091         if (list->size == list->max_size) {
1092                 ERROR(list->ctx, "%p: Could not push network onto the stack: Stack full\n", list);
1093                 return -ENOMEM;
1094         }
1095
1096         DEBUG(list->ctx, "%p: Pushing network %p onto stack\n", list, network);
1097
1098         list->list[list->size++] = loc_network_ref(network);
1099
1100         return 0;
1101 }
1102
1103 LOC_EXPORT struct loc_network* loc_network_list_pop(struct loc_network_list* list) {
1104         // Return nothing when empty
1105         if (loc_network_list_empty(list)) {
1106                 DEBUG(list->ctx, "%p: Popped empty stack\n", list);
1107                 return NULL;
1108         }
1109
1110         struct loc_network* network = list->list[--list->size];
1111
1112         DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
1113
1114         return network;
1115 }
1116
1117 LOC_EXPORT int loc_network_list_contains(struct loc_network_list* list, struct loc_network* network) {
1118         for (unsigned int i = 0; i < list->size; i++) {
1119                 if (loc_network_eq(list->list[i], network))
1120                         return 1;
1121         }
1122
1123         return 0;
1124 }
1125
1126 static void loc_network_list_swap(struct loc_network_list* list, unsigned int i1, unsigned int i2) {
1127         // Do nothing for invalid indices
1128         if (i1 >= list->size || i2 >= list->size)
1129                 return;
1130
1131         struct loc_network* network1 = list->list[i1];
1132         struct loc_network* network2 = list->list[i2];
1133
1134         list->list[i1] = network2;
1135         list->list[i2] = network1;
1136 }
1137
1138 LOC_EXPORT void loc_network_list_reverse(struct loc_network_list* list) {
1139         unsigned int i = 0;
1140         unsigned int j = list->size - 1;
1141
1142         while (i < j) {
1143                 loc_network_list_swap(list, i++, j--);
1144         }
1145 }
1146
1147 LOC_EXPORT void loc_network_list_sort(struct loc_network_list* list) {
1148         unsigned int n = list->size;
1149         int swapped;
1150
1151         do {
1152                 swapped = 0;
1153
1154                 for (unsigned int i = 1; i < n; i++) {
1155                         if (loc_network_gt(list->list[i-1], list->list[i]) > 0) {
1156                                 loc_network_list_swap(list, i-1, i);
1157                                 swapped = 1;
1158                         }
1159                 }
1160
1161                 n--;
1162         } while (swapped);
1163 }
1164
1165 LOC_EXPORT int loc_network_list_merge(
1166                 struct loc_network_list* self, struct loc_network_list* other) {
1167         int r;
1168
1169         for (unsigned int i = 0; i < other->size; i++) {
1170                 r = loc_network_list_push(self, other->list[i]);
1171                 if (r)
1172                         return r;
1173         }
1174
1175         return 0;
1176 }