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(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 // XXX DEPRECATED - I find this too difficult to use
 497 LOC_EXPORT int loc_network_is_subnet_of(struct loc_network* self, struct loc_network* other) {
 498         // If the start address of the other network is smaller than this network,
 499         // it cannot be a subnet.
 500         if (in6_addr_cmp(&self->first_address, &other->first_address) < 0)
 501                 return 0;
 502
 503         // If the end address of the other network is greater than this network,
 504         // it cannot be a subnet.
 505         if (in6_addr_cmp(&self->last_address, &other->last_address) > 0)
 506                 return 0;
 507
 508         return 1;
 509 }
 510
 511 LOC_EXPORT struct loc_network_list* loc_network_subnets(struct loc_network* network) {
 512         struct loc_network_list* list;
 513
 514         // New prefix length
 515         unsigned int prefix = network->prefix + 1;
 516
 517         // Check if the new prefix is valid
 518         if (valid_prefix(&network->first_address, prefix))
 519                 return NULL;
 520
 521         // Create a new list with the result
 522         int r = loc_network_list_new(network->ctx, &list);
 523         if (r) {
 524                 ERROR(network->ctx, "Could not create network list: %d\n", r);
 525                 return NULL;
 526         }
 527
 528         struct loc_network* subnet1 = NULL;
 529         struct loc_network* subnet2 = NULL;
 530
 531         // Create the first half of the network
 532         r = loc_network_new(network->ctx, &subnet1, &network->first_address, prefix);
 533         if (r)
 534                 goto ERROR;
 535
 536         // The next subnet starts after the first one
 537         struct in6_addr first_address = address_increment(&subnet1->last_address);
 538
 539         // Create the second half of the network
 540         r = loc_network_new(network->ctx, &subnet2, &first_address, prefix);
 541         if (r)
 542                 goto ERROR;
 543
 544         // Push the both onto the stack (in reverse order)
 545         r = loc_network_list_push(list, subnet2);
 546         if (r)
 547                 goto ERROR;
 548
 549         r = loc_network_list_push(list, subnet1);
 550         if (r)
 551                 goto ERROR;
 552
 553         loc_network_unref(subnet1);
 554         loc_network_unref(subnet2);
 555
 556         return list;
 557
 558 ERROR:
 559         if (subnet1)
 560                 loc_network_unref(subnet1);
 561
 562         if (subnet2)
 563                 loc_network_unref(subnet2);
 564
 565         if (list)
 566                 loc_network_list_unref(list);
 567
 568         return NULL;
 569 }
 570
 571 LOC_EXPORT struct loc_network_list* loc_network_exclude(
 572                 struct loc_network* self, struct loc_network* other) {
 573         struct loc_network_list* list;
 574
 575 #ifdef ENABLE_DEBUG
 576         char* n1 = loc_network_str(self);
 577         char* n2 = loc_network_str(other);
 578
 579         DEBUG(self->ctx, "Returning %s excluding %s...\n", n1, n2);
 580
 581         free(n1);
 582         free(n2);
 583 #endif
 584
 585         // Family must match
 586         if (self->family != other->family) {
 587                 DEBUG(self->ctx, "Family mismatch\n");
 588
 589                 return NULL;
 590         }
 591
 592         // Other must be a subnet of self
 593         if (!loc_network_is_subnet_of(other, self)) {
 594                 DEBUG(self->ctx, "Network %p is not contained in network %p\n", other, self);
 595
 596                 return NULL;
 597         }
 598
 599         // We cannot perform this operation if both networks equal
 600         if (loc_network_eq(self, other)) {
 601                 DEBUG(self->ctx, "Networks %p and %p are equal\n", self, other);
 602
 603                 return NULL;
 604         }
 605
 606         // Create a new list with the result
 607         int r = loc_network_list_new(self->ctx, &list);
 608         if (r) {
 609                 ERROR(self->ctx, "Could not create network list: %d\n", r);
 610                 return NULL;
 611         }
 612
 613         struct loc_network_list* subnets = loc_network_subnets(self);
 614
 615         struct loc_network* subnet1 = NULL;
 616         struct loc_network* subnet2 = NULL;
 617
 618         while (subnets) {
 619                 // Fetch both subnets
 620                 subnet1 = loc_network_list_get(subnets, 0);
 621                 subnet2 = loc_network_list_get(subnets, 1);
 622
 623                 // Free list
 624                 loc_network_list_unref(subnets);
 625                 subnets = NULL;
 626
 627                 if (loc_network_eq(other, subnet1)) {
 628                         r = loc_network_list_push(list, subnet2);
 629                         if (r)
 630                                 goto ERROR;
 631
 632                 } else if (loc_network_eq(other, subnet2)) {
 633                         r = loc_network_list_push(list, subnet1);
 634                         if (r)
 635                                 goto ERROR;
 636
 637                 } else  if (loc_network_is_subnet_of(other, subnet1)) {
 638                         r = loc_network_list_push(list, subnet2);
 639                         if (r)
 640                                 goto ERROR;
 641
 642                         subnets = loc_network_subnets(subnet1);
 643
 644                 } else if (loc_network_is_subnet_of(other, subnet2)) {
 645                         r = loc_network_list_push(list, subnet1);
 646                         if (r)
 647                                 goto ERROR;
 648
 649                         subnets = loc_network_subnets(subnet2);
 650
 651                 } else {
 652                         ERROR(self->ctx, "We should never get here\n");
 653                         goto ERROR;
 654                 }
 655
 656                 loc_network_unref(subnet1);
 657                 loc_network_unref(subnet2);
 658         }
 659
 660 #ifdef ENABLE_DEBUG
 661         loc_network_list_dump(list);
 662 #endif
 663
 664         // Return the result
 665         return list;
 666
 667 ERROR:
 668         if (subnet1)
 669                 loc_network_unref(subnet1);
 670
 671         if (subnet2)
 672                 loc_network_unref(subnet2);
 673
 674         if (list)
 675                 loc_network_list_unref(list);
 676
 677         return NULL;
 678 }
 679
 680 LOC_EXPORT int loc_network_to_database_v1(struct loc_network* network, struct loc_database_network_v1* dbobj) {
 681         // Add country code
 682         loc_country_code_copy(dbobj->country_code, network->country_code);
 683
 684         // Add ASN
 685         dbobj->asn = htobe32(network->asn);
 686
 687         // Flags
 688         dbobj->flags = htobe16(network->flags);
 689
 690         return 0;
 691 }
 692
 693 LOC_EXPORT int loc_network_new_from_database_v1(struct loc_ctx* ctx, struct loc_network** network,
 694                 struct in6_addr* address, unsigned int prefix, const struct loc_database_network_v1* dbobj) {
 695         char country_code[3] = "\0\0";
 696
 697         int r = loc_network_new(ctx, network, address, prefix);
 698         if (r) {
 699                 ERROR(ctx, "Could not allocate a new network: %s", strerror(-r));
 700                 return r;
 701         }
 702
 703         // Import country code
 704         loc_country_code_copy(country_code, dbobj->country_code);
 705
 706         r = loc_network_set_country_code(*network, country_code);
 707         if (r) {
 708                 ERROR(ctx, "Could not set country code: %s\n", country_code);
 709                 return r;
 710         }
 711
 712         // Import ASN
 713         uint32_t asn = be32toh(dbobj->asn);
 714         r = loc_network_set_asn(*network, asn);
 715         if (r) {
 716                 ERROR(ctx, "Could not set ASN: %d\n", asn);
 717                 return r;
 718         }
 719
 720         // Import flags
 721         int flags = be16toh(dbobj->flags);
 722         r = loc_network_set_flag(*network, flags);
 723         if (r) {
 724                 ERROR(ctx, "Could not set flags: %d\n", flags);
 725                 return r;
 726         }
 727
 728         return 0;
 729 }
 730
 731 struct loc_network_tree {
 732         struct loc_ctx* ctx;
 733         int refcount;
 734
 735         struct loc_network_tree_node* root;
 736 };
 737
 738 struct loc_network_tree_node {
 739         struct loc_ctx* ctx;
 740         int refcount;
 741
 742         struct loc_network_tree_node* zero;
 743         struct loc_network_tree_node* one;
 744
 745         struct loc_network* network;
 746 };
 747
 748 LOC_EXPORT int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree) {
 749         struct loc_network_tree* t = calloc(1, sizeof(*t));
 750         if (!t)
 751                 return -ENOMEM;
 752
 753         t->ctx = loc_ref(ctx);
 754         t->refcount = 1;
 755
 756         // Create the root node
 757         int r = loc_network_tree_node_new(ctx, &t->root);
 758         if (r) {
 759                 loc_network_tree_unref(t);
 760                 return r;
 761         }
 762
 763         DEBUG(t->ctx, "Network tree allocated at %p\n", t);
 764         *tree = t;
 765         return 0;
 766 }
 767
 768 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_get_root(struct loc_network_tree* tree) {
 769         return loc_network_tree_node_ref(tree->root);
 770 }
 771
 772 static struct loc_network_tree_node* loc_network_tree_get_node(struct loc_network_tree_node* node, int path) {
 773         struct loc_network_tree_node** n;
 774
 775         if (path == 0)
 776                 n = &node->zero;
 777         else
 778                 n = &node->one;
 779
 780         // If the desired node doesn't exist, yet, we will create it
 781         if (*n == NULL) {
 782                 int r = loc_network_tree_node_new(node->ctx, n);
 783                 if (r)
 784                         return NULL;
 785         }
 786
 787         return *n;
 788 }
 789
 790 static struct loc_network_tree_node* loc_network_tree_get_path(struct loc_network_tree* tree, const struct in6_addr* address, unsigned int prefix) {
 791         struct loc_network_tree_node* node = tree->root;
 792
 793         for (unsigned int i = 0; i < prefix; i++) {
 794                 // Check if the ith bit is one or zero
 795                 node = loc_network_tree_get_node(node, in6_addr_get_bit(address, i));
 796         }
 797
 798         return node;
 799 }
 800
 801 static int __loc_network_tree_walk(struct loc_ctx* ctx, struct loc_network_tree_node* node,
 802                 int(*filter_callback)(struct loc_network* network, void* data),
 803                 int(*callback)(struct loc_network* network, void* data), void* data) {
 804         int r;
 805
 806         // Finding a network ends the walk here
 807         if (node->network) {
 808                 if (filter_callback) {
 809                         int f = filter_callback(node->network, data);
 810                         if (f < 0)
 811                                 return f;
 812
 813                         // Skip network if filter function returns value greater than zero
 814                         if (f > 0)
 815                                 return 0;
 816                 }
 817
 818                 r = callback(node->network, data);
 819                 if (r)
 820                         return r;
 821         }
 822
 823         // Walk down on the left side of the tree first
 824         if (node->zero) {
 825                 r = __loc_network_tree_walk(ctx, node->zero, filter_callback, callback, data);
 826                 if (r)
 827                         return r;
 828         }
 829
 830         // Then walk on the other side
 831         if (node->one) {
 832                 r = __loc_network_tree_walk(ctx, node->one, filter_callback, callback, data);
 833                 if (r)
 834                         return r;
 835         }
 836
 837         return 0;
 838 }
 839
 840 LOC_EXPORT int loc_network_tree_walk(struct loc_network_tree* tree,
 841                 int(*filter_callback)(struct loc_network* network, void* data),
 842                 int(*callback)(struct loc_network* network, void* data), void* data) {
 843         return __loc_network_tree_walk(tree->ctx, tree->root, filter_callback, callback, data);
 844 }
 845
 846 static void loc_network_tree_free(struct loc_network_tree* tree) {
 847         DEBUG(tree->ctx, "Releasing network tree at %p\n", tree);
 848
 849         loc_network_tree_node_unref(tree->root);
 850
 851         loc_unref(tree->ctx);
 852         free(tree);
 853 }
 854
 855 LOC_EXPORT struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) {
 856         if (--tree->refcount > 0)
 857                 return tree;
 858
 859         loc_network_tree_free(tree);
 860         return NULL;
 861 }
 862
 863 static int __loc_network_tree_dump(struct loc_network* network, void* data) {
 864         DEBUG(network->ctx, "Dumping network at %p\n", network);
 865
 866         char* s = loc_network_str(network);
 867         if (!s)
 868                 return 1;
 869
 870         INFO(network->ctx, "%s\n", s);
 871         free(s);
 872
 873         return 0;
 874 }
 875
 876 LOC_EXPORT int loc_network_tree_dump(struct loc_network_tree* tree) {
 877         DEBUG(tree->ctx, "Dumping network tree at %p\n", tree);
 878
 879         return loc_network_tree_walk(tree, NULL, __loc_network_tree_dump, NULL);
 880 }
 881
 882 LOC_EXPORT int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_network* network) {
 883         DEBUG(tree->ctx, "Adding network %p to tree %p\n", network, tree);
 884
 885         struct loc_network_tree_node* node = loc_network_tree_get_path(tree,
 886                         &network->first_address, network->prefix);
 887         if (!node) {
 888                 ERROR(tree->ctx, "Could not find a node\n");
 889                 return -ENOMEM;
 890         }
 891
 892         // Check if node has not been set before
 893         if (node->network) {
 894                 DEBUG(tree->ctx, "There is already a network at this path\n");
 895                 return -EBUSY;
 896         }
 897
 898         // Point node to the network
 899         node->network = loc_network_ref(network);
 900
 901         return 0;
 902 }
 903
 904 static int __loc_network_tree_count(struct loc_network* network, void* data) {
 905         size_t* counter = (size_t*)data;
 906
 907         // Increase the counter for each network
 908         counter++;
 909
 910         return 0;
 911 }
 912
 913 LOC_EXPORT size_t loc_network_tree_count_networks(struct loc_network_tree* tree) {
 914         size_t counter = 0;
 915
 916         int r = loc_network_tree_walk(tree, NULL, __loc_network_tree_count, &counter);
 917         if (r)
 918                 return r;
 919
 920         return counter;
 921 }
 922
 923 static size_t __loc_network_tree_count_nodes(struct loc_network_tree_node* node) {
 924         size_t counter = 1;
 925
 926         if (node->zero)
 927                 counter += __loc_network_tree_count_nodes(node->zero);
 928
 929         if (node->one)
 930                 counter += __loc_network_tree_count_nodes(node->one);
 931
 932         return counter;
 933 }
 934
 935 LOC_EXPORT size_t loc_network_tree_count_nodes(struct loc_network_tree* tree) {
 936         return __loc_network_tree_count_nodes(tree->root);
 937 }
 938
 939 LOC_EXPORT int loc_network_tree_node_new(struct loc_ctx* ctx, struct loc_network_tree_node** node) {
 940         struct loc_network_tree_node* n = calloc(1, sizeof(*n));
 941         if (!n)
 942                 return -ENOMEM;
 943
 944         n->ctx = loc_ref(ctx);
 945         n->refcount = 1;
 946
 947         n->zero = n->one = NULL;
 948
 949         DEBUG(n->ctx, "Network node allocated at %p\n", n);
 950         *node = n;
 951         return 0;
 952 }
 953
 954 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_ref(struct loc_network_tree_node* node) {
 955         if (node)
 956                 node->refcount++;
 957
 958         return node;
 959 }
 960
 961 static void loc_network_tree_node_free(struct loc_network_tree_node* node) {
 962         DEBUG(node->ctx, "Releasing network node at %p\n", node);
 963
 964         if (node->network)
 965                 loc_network_unref(node->network);
 966
 967         if (node->zero)
 968                 loc_network_tree_node_unref(node->zero);
 969
 970         if (node->one)
 971                 loc_network_tree_node_unref(node->one);
 972
 973         loc_unref(node->ctx);
 974         free(node);
 975 }
 976
 977 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_unref(struct loc_network_tree_node* node) {
 978         if (!node)
 979                 return NULL;
 980
 981         if (--node->refcount > 0)
 982                 return node;
 983
 984         loc_network_tree_node_free(node);
 985         return NULL;
 986 }
 987
 988 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_get(struct loc_network_tree_node* node, unsigned int index) {
 989         if (index == 0)
 990                 node = node->zero;
 991         else
 992                 node = node->one;
 993
 994         if (!node)
 995                 return NULL;
 996
 997         return loc_network_tree_node_ref(node);
 998 }
 999
1000 LOC_EXPORT int loc_network_tree_node_is_leaf(struct loc_network_tree_node* node) {
1001         return (!!node->network);
1002 }
1003
1004 LOC_EXPORT struct loc_network* loc_network_tree_node_get_network(struct loc_network_tree_node* node) {
1005         return loc_network_ref(node->network);
1006 }
1007
1008 // List
1009
1010 struct loc_network_list {
1011         struct loc_ctx* ctx;
1012         int refcount;
1013
1014         struct loc_network* list[1024];
1015         size_t size;
1016         size_t max_size;
1017 };
1018
1019 LOC_EXPORT int loc_network_list_new(struct loc_ctx* ctx,
1020                 struct loc_network_list** list) {
1021         struct loc_network_list* l = calloc(1, sizeof(*l));
1022         if (!l)
1023                 return -ENOMEM;
1024
1025         l->ctx = loc_ref(ctx);
1026         l->refcount = 1;
1027
1028         // Do not allow this list to grow larger than this
1029         l->max_size = 1024;
1030
1031         DEBUG(l->ctx, "Network list allocated at %p\n", l);
1032         *list = l;
1033         return 0;
1034 }
1035
1036 LOC_EXPORT struct loc_network_list* loc_network_list_ref(struct loc_network_list* list) {
1037         list->refcount++;
1038
1039         return list;
1040 }
1041
1042 static void loc_network_list_free(struct loc_network_list* list) {
1043         DEBUG(list->ctx, "Releasing network list at %p\n", list);
1044
1045         for (unsigned int i = 0; i < list->size; i++)
1046                 loc_network_unref(list->list[i]);
1047
1048         loc_unref(list->ctx);
1049         free(list);
1050 }
1051
1052 LOC_EXPORT struct loc_network_list* loc_network_list_unref(struct loc_network_list* list) {
1053         if (!list)
1054                 return NULL;
1055
1056         if (--list->refcount > 0)
1057                 return list;
1058
1059         loc_network_list_free(list);
1060         return NULL;
1061 }
1062
1063 LOC_EXPORT size_t loc_network_list_size(struct loc_network_list* list) {
1064         return list->size;
1065 }
1066
1067 LOC_EXPORT int loc_network_list_empty(struct loc_network_list* list) {
1068         return list->size == 0;
1069 }
1070
1071 LOC_EXPORT void loc_network_list_clear(struct loc_network_list* list) {
1072         for (unsigned int i = 0; i < list->size; i++)
1073                 loc_network_unref(list->list[i]);
1074
1075         list->size = 0;
1076 }
1077
1078 LOC_EXPORT void loc_network_list_dump(struct loc_network_list* list) {
1079         struct loc_network* network;
1080         char* s;
1081
1082         for (unsigned int i = 0; i < list->size; i++) {
1083                 network = list->list[i];
1084
1085                 s = loc_network_str(network);
1086
1087                 INFO(list->ctx, "%s\n", s);
1088                 free(s);
1089         }
1090 }
1091
1092 LOC_EXPORT struct loc_network* loc_network_list_get(struct loc_network_list* list, size_t index) {
1093         // Check index
1094         if (index >= list->size)
1095                 return NULL;
1096
1097         return loc_network_ref(list->list[index]);
1098 }
1099
1100 LOC_EXPORT int loc_network_list_push(struct loc_network_list* list, struct loc_network* network) {
1101         // Do not add networks that are already on the list
1102         if (loc_network_list_contains(list, network))
1103                 return 0;
1104
1105         // Check if we have space left
1106         if (list->size == list->max_size) {
1107                 ERROR(list->ctx, "%p: Could not push network onto the stack: Stack full\n", list);
1108                 return -ENOMEM;
1109         }
1110
1111         DEBUG(list->ctx, "%p: Pushing network %p onto stack\n", list, network);
1112
1113         list->list[list->size++] = loc_network_ref(network);
1114
1115         return 0;
1116 }
1117
1118 LOC_EXPORT struct loc_network* loc_network_list_pop(struct loc_network_list* list) {
1119         // Return nothing when empty
1120         if (loc_network_list_empty(list)) {
1121                 DEBUG(list->ctx, "%p: Popped empty stack\n", list);
1122                 return NULL;
1123         }
1124
1125         struct loc_network* network = list->list[--list->size];
1126
1127         DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
1128
1129         return network;
1130 }
1131
1132 LOC_EXPORT int loc_network_list_contains(struct loc_network_list* list, struct loc_network* network) {
1133         for (unsigned int i = 0; i < list->size; i++) {
1134                 if (loc_network_eq(list->list[i], network))
1135                         return 1;
1136         }
1137
1138         return 0;
1139 }
1140
1141 static void loc_network_list_swap(struct loc_network_list* list, unsigned int i1, unsigned int i2) {
1142         // Do nothing for invalid indices
1143         if (i1 >= list->size || i2 >= list->size)
1144                 return;
1145
1146         struct loc_network* network1 = list->list[i1];
1147         struct loc_network* network2 = list->list[i2];
1148
1149         list->list[i1] = network2;
1150         list->list[i2] = network1;
1151 }
1152
1153 LOC_EXPORT void loc_network_list_reverse(struct loc_network_list* list) {
1154         unsigned int i = 0;
1155         unsigned int j = list->size - 1;
1156
1157         while (i < j) {
1158                 loc_network_list_swap(list, i++, j--);
1159         }
1160 }
1161
1162 LOC_EXPORT void loc_network_list_sort(struct loc_network_list* list) {
1163         unsigned int n = list->size;
1164         int swapped;
1165
1166         do {
1167                 swapped = 0;
1168
1169                 for (unsigned int i = 1; i < n; i++) {
1170                         if (loc_network_gt(list->list[i-1], list->list[i]) > 0) {
1171                                 loc_network_list_swap(list, i-1, i);
1172                                 swapped = 1;
1173                         }
1174                 }
1175
1176                 n--;
1177         } while (swapped);
1178 }
1179
1180 LOC_EXPORT int loc_network_list_merge(
1181                 struct loc_network_list* self, struct loc_network_list* other) {
1182         int r;
1183
1184         for (unsigned int i = 0; i < other->size; i++) {
1185                 r = loc_network_list_push(self, other->list[i]);
1186                 if (r)
1187                         return r;
1188         }
1189
1190         return 0;
1191 }