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 <libloc/libloc.h>
  29 #include <libloc/address.h>
  30 #include <libloc/compat.h>
  31 #include <libloc/country.h>
  32 #include <libloc/network.h>
  33 #include <libloc/network-list.h>
  34 #include <libloc/private.h>
  35
  36 struct loc_network {
  37         struct loc_ctx* ctx;
  38         int refcount;
  39
  40         int family;
  41         struct in6_addr first_address;
  42         struct in6_addr last_address;
  43         unsigned int prefix;
  44
  45         char country_code[3];
  46         uint32_t asn;
  47         enum loc_network_flags flags;
  48 };
  49
  50 static int valid_prefix(struct in6_addr* address, unsigned int prefix) {
  51         // The prefix cannot be larger than 128 bits
  52         if (prefix > 128)
  53                 return 1;
  54
  55         // For IPv4-mapped addresses the prefix has to be 96 or lager
  56         if (IN6_IS_ADDR_V4MAPPED(address) && prefix <= 96)
  57                 return 1;
  58
  59         return 0;
  60 }
  61
  62 LOC_EXPORT int loc_network_new(struct loc_ctx* ctx, struct loc_network** network,
  63                 struct in6_addr* address, unsigned int prefix) {
  64         // Validate the prefix
  65         if (valid_prefix(address, prefix) != 0) {
  66                 ERROR(ctx, "Invalid prefix: %u\n", prefix);
  67                 errno = EINVAL;
  68                 return 1;
  69         }
  70
  71         struct loc_network* n = calloc(1, sizeof(*n));
  72         if (!n) {
  73                 errno = ENOMEM;
  74                 return 1;
  75         }
  76
  77         n->ctx = loc_ref(ctx);
  78         n->refcount = 1;
  79
  80         // Store the prefix
  81         n->prefix = prefix;
  82
  83         // Convert the prefix into a bitmask
  84         struct in6_addr bitmask = loc_prefix_to_bitmask(n->prefix);
  85
  86         // Store the first and last address in the network
  87         n->first_address = loc_address_and(address, &bitmask);
  88         n->last_address  = loc_address_or(&n->first_address, &bitmask);
  89
  90         // Set family
  91         n->family = loc_address_family(&n->first_address);
  92
  93         DEBUG(n->ctx, "Network allocated at %p\n", n);
  94         *network = n;
  95         return 0;
  96 }
  97
  98 LOC_EXPORT int loc_network_new_from_string(struct loc_ctx* ctx, struct loc_network** network,
  99                 const char* address_string) {
 100         struct in6_addr first_address;
 101         char* prefix_string;
 102         unsigned int prefix = 128;
 103         int r = -EINVAL;
 104
 105         DEBUG(ctx, "Attempting to parse network %s\n", address_string);
 106
 107         // Make a copy of the string to work on it
 108         char* buffer = strdup(address_string);
 109         address_string = prefix_string = buffer;
 110
 111         // Split address and prefix
 112         address_string = strsep(&prefix_string, "/");
 113
 114         DEBUG(ctx, "  Split into address = %s, prefix = %s\n", address_string, prefix_string);
 115
 116         // Parse the address
 117         r = loc_parse_address(ctx, address_string, &first_address);
 118         if (r) {
 119                 DEBUG(ctx, "The address could not be parsed\n");
 120                 goto FAIL;
 121         }
 122
 123         // If a prefix was given, we will try to parse it
 124         if (prefix_string) {
 125                 // Convert prefix to integer
 126                 prefix = strtol(prefix_string, NULL, 10);
 127
 128                 if (!prefix) {
 129                         DEBUG(ctx, "The prefix was not parsable: %s\n", prefix_string);
 130                         goto FAIL;
 131                 }
 132
 133                 // Map the prefix to IPv6 if needed
 134                 if (IN6_IS_ADDR_V4MAPPED(&first_address))
 135                         prefix += 96;
 136         }
 137
 138 FAIL:
 139         // Free temporary buffer
 140         free(buffer);
 141
 142         // Exit if the parsing was unsuccessful
 143         if (r)
 144                 return r;
 145
 146         // Create a new network
 147         return loc_network_new(ctx, network, &first_address, prefix);
 148 }
 149
 150 LOC_EXPORT struct loc_network* loc_network_ref(struct loc_network* network) {
 151         network->refcount++;
 152
 153         return network;
 154 }
 155
 156 static void loc_network_free(struct loc_network* network) {
 157         DEBUG(network->ctx, "Releasing network at %p\n", network);
 158
 159         loc_unref(network->ctx);
 160         free(network);
 161 }
 162
 163 LOC_EXPORT struct loc_network* loc_network_unref(struct loc_network* network) {
 164         if (!network)
 165                 return NULL;
 166
 167         if (--network->refcount > 0)
 168                 return network;
 169
 170         loc_network_free(network);
 171         return NULL;
 172 }
 173
 174 static int format_ipv6_address(const struct in6_addr* address, char* string, size_t length) {
 175         const char* ret = inet_ntop(AF_INET6, address, string, length);
 176         if (!ret)
 177                 return -1;
 178
 179         return 0;
 180 }
 181
 182 static int format_ipv4_address(const struct in6_addr* address, char* string, size_t length) {
 183         struct in_addr ipv4_address;
 184         ipv4_address.s_addr = address->s6_addr32[3];
 185
 186         const char* ret = inet_ntop(AF_INET, &ipv4_address, string, length);
 187         if (!ret)
 188                 return -1;
 189
 190         return 0;
 191 }
 192
 193 LOC_EXPORT char* loc_network_str(struct loc_network* network) {
 194         int r;
 195         const size_t length = INET6_ADDRSTRLEN + 4;
 196
 197         char* string = malloc(length);
 198         if (!string)
 199                 return NULL;
 200
 201         unsigned int prefix = network->prefix;
 202
 203         switch (network->family) {
 204                 case AF_INET6:
 205                         r = format_ipv6_address(&network->first_address, string, length);
 206                         break;
 207
 208                 case AF_INET:
 209                         r = format_ipv4_address(&network->first_address, string, length);
 210                         prefix -= 96;
 211                         break;
 212
 213                 default:
 214                         r = -1;
 215                         break;
 216         }
 217
 218         if (r) {
 219                 ERROR(network->ctx, "Could not convert network to string: %s\n", strerror(errno));
 220                 free(string);
 221
 222                 return NULL;
 223         }
 224
 225         // Append prefix
 226         sprintf(string + strlen(string), "/%u", prefix);
 227
 228         return string;
 229 }
 230
 231 LOC_EXPORT int loc_network_address_family(struct loc_network* network) {
 232         return network->family;
 233 }
 234
 235 LOC_EXPORT unsigned int loc_network_prefix(struct loc_network* network) {
 236         switch (network->family) {
 237                 case AF_INET6:
 238                         return network->prefix;
 239
 240                 case AF_INET:
 241                         return network->prefix - 96;
 242         }
 243
 244         return 0;
 245 }
 246
 247 static char* loc_network_format_address(struct loc_network* network, const struct in6_addr* address) {
 248         const size_t length = INET6_ADDRSTRLEN;
 249
 250         char* string = malloc(length);
 251         if (!string)
 252                 return NULL;
 253
 254         int r = 0;
 255
 256         switch (network->family) {
 257                 case AF_INET6:
 258                         r = format_ipv6_address(address, string, length);
 259                         break;
 260
 261                 case AF_INET:
 262                         r = format_ipv4_address(address, string, length);
 263                         break;
 264
 265                 default:
 266                         r = -1;
 267                         break;
 268         }
 269
 270         if (r) {
 271                 ERROR(network->ctx, "Could not format IP address to string: %s\n", strerror(errno));
 272                 free(string);
 273
 274                 return NULL;
 275         }
 276
 277         return string;
 278 }
 279
 280 LOC_EXPORT const struct in6_addr* loc_network_get_first_address(struct loc_network* network) {
 281         return &network->first_address;
 282 }
 283
 284 LOC_EXPORT char* loc_network_format_first_address(struct loc_network* network) {
 285         return loc_network_format_address(network, &network->first_address);
 286 }
 287
 288 LOC_EXPORT const struct in6_addr* loc_network_get_last_address(struct loc_network* network) {
 289         return &network->last_address;
 290 }
 291
 292 LOC_EXPORT char* loc_network_format_last_address(struct loc_network* network) {
 293         return loc_network_format_address(network, &network->last_address);
 294 }
 295
 296 LOC_EXPORT int loc_network_matches_address(struct loc_network* network, const struct in6_addr* address) {
 297         // Address must be larger than the start address
 298         if (loc_address_cmp(&network->first_address, address) > 0)
 299                 return 0;
 300
 301         // Address must be smaller than the last address
 302         if (loc_address_cmp(&network->last_address, address) < 0)
 303                 return 0;
 304
 305         // The address is inside this network
 306         return 1;
 307 }
 308
 309 LOC_EXPORT const char* loc_network_get_country_code(struct loc_network* network) {
 310         return network->country_code;
 311 }
 312
 313 LOC_EXPORT int loc_network_set_country_code(struct loc_network* network, const char* country_code) {
 314         // Set empty country code
 315         if (!country_code || !*country_code) {
 316                 *network->country_code = '\0';
 317                 return 0;
 318         }
 319
 320         // Check country code
 321         if (!loc_country_code_is_valid(country_code))
 322                 return -EINVAL;
 323
 324         loc_country_code_copy(network->country_code, country_code);
 325
 326         return 0;
 327 }
 328
 329 LOC_EXPORT int loc_network_matches_country_code(struct loc_network* network, const char* country_code) {
 330         // Search for any special flags
 331         const int flag = loc_country_special_code_to_flag(country_code);
 332
 333         // If we found a flag, we will return whether it is set or not
 334         if (flag)
 335                 return loc_network_has_flag(network, flag);
 336
 337         // Check country code
 338         if (!loc_country_code_is_valid(country_code))
 339                 return -EINVAL;
 340
 341         // Check for an exact match
 342         return (network->country_code[0] == country_code[0])
 343                 && (network->country_code[1] == country_code[1]);
 344 }
 345
 346 LOC_EXPORT uint32_t loc_network_get_asn(struct loc_network* network) {
 347         return network->asn;
 348 }
 349
 350 LOC_EXPORT int loc_network_set_asn(struct loc_network* network, uint32_t asn) {
 351         network->asn = asn;
 352
 353         return 0;
 354 }
 355
 356 LOC_EXPORT int loc_network_has_flag(struct loc_network* network, uint32_t flag) {
 357         return network->flags & flag;
 358 }
 359
 360 LOC_EXPORT int loc_network_set_flag(struct loc_network* network, uint32_t flag) {
 361         network->flags |= flag;
 362
 363         return 0;
 364 }
 365
 366 LOC_EXPORT int loc_network_cmp(struct loc_network* self, struct loc_network* other) {
 367         // Compare address
 368         int r = loc_address_cmp(&self->first_address, &other->first_address);
 369         if (r)
 370                 return r;
 371
 372         // Compare prefix
 373         if (self->prefix > other->prefix)
 374                 return 1;
 375         else if (self->prefix < other->prefix)
 376                 return -1;
 377
 378         // Both networks are equal
 379         return 0;
 380 }
 381
 382 LOC_EXPORT int loc_network_overlaps(struct loc_network* self, struct loc_network* other) {
 383         // Either of the start addresses must be in the other subnet
 384         if (loc_network_matches_address(self, &other->first_address))
 385                 return 1;
 386
 387         if (loc_network_matches_address(other, &self->first_address))
 388                 return 1;
 389
 390         // Or either of the end addresses is in the other subnet
 391         if (loc_network_matches_address(self, &other->last_address))
 392                 return 1;
 393
 394         if (loc_network_matches_address(other, &self->last_address))
 395                 return 1;
 396
 397         return 0;
 398 }
 399
 400 LOC_EXPORT int loc_network_is_subnet(struct loc_network* self, struct loc_network* other) {
 401         // The prefix must be smaller (this avoids the more complex comparisons later)
 402         if (self->prefix > other->prefix)
 403                 return 0;
 404
 405         // If the start address of the other network is smaller than this network,
 406         // it cannot be a subnet.
 407         if (loc_address_cmp(&self->first_address, &other->first_address) > 0)
 408                 return 0;
 409
 410         // If the end address of the other network is greater than this network,
 411         // it cannot be a subnet.
 412         if (loc_address_cmp(&self->last_address, &other->last_address) < 0)
 413                 return 0;
 414
 415         return 1;
 416 }
 417
 418 LOC_EXPORT int loc_network_subnets(struct loc_network* network,
 419                 struct loc_network** subnet1, struct loc_network** subnet2) {
 420         int r;
 421         *subnet1 = NULL;
 422         *subnet2 = NULL;
 423
 424         // New prefix length
 425         unsigned int prefix = network->prefix + 1;
 426
 427         // Check if the new prefix is valid
 428         if (valid_prefix(&network->first_address, prefix))
 429                 return -1;
 430
 431         // Create the first half of the network
 432         r = loc_network_new(network->ctx, subnet1, &network->first_address, prefix);
 433         if (r)
 434                 return r;
 435
 436         // The next subnet starts after the first one
 437         struct in6_addr first_address = (*subnet1)->last_address;
 438         loc_address_increment(&first_address);
 439
 440         // Create the second half of the network
 441         r = loc_network_new(network->ctx, subnet2, &first_address, prefix);
 442         if (r)
 443                 return r;
 444
 445         // Copy country code
 446         const char* country_code = loc_network_get_country_code(network);
 447         if (country_code) {
 448                 loc_network_set_country_code(*subnet1, country_code);
 449                 loc_network_set_country_code(*subnet2, country_code);
 450         }
 451
 452         // Copy ASN
 453         uint32_t asn = loc_network_get_asn(network);
 454         if (asn) {
 455                 loc_network_set_asn(*subnet1, asn);
 456                 loc_network_set_asn(*subnet2, asn);
 457         }
 458
 459         // Copy flags
 460         loc_network_set_flag(*subnet1, network->flags);
 461         loc_network_set_flag(*subnet2, network->flags);
 462
 463         return 0;
 464 }
 465
 466 static int __loc_network_exclude(struct loc_network* network,
 467                 struct loc_network* other, struct loc_network_list* list) {
 468         struct loc_network* subnet1 = NULL;
 469         struct loc_network* subnet2 = NULL;
 470
 471         int r = loc_network_subnets(network, &subnet1, &subnet2);
 472         if (r)
 473                 goto ERROR;
 474
 475         if (loc_network_cmp(other, subnet1) == 0) {
 476                 r = loc_network_list_push(list, subnet2);
 477                 if (r)
 478                         goto ERROR;
 479
 480         } else if (loc_network_cmp(other, subnet2) == 0) {
 481                 r = loc_network_list_push(list, subnet1);
 482                 if (r)
 483                         goto ERROR;
 484
 485         } else  if (loc_network_is_subnet(subnet1, other)) {
 486                 r = loc_network_list_push(list, subnet2);
 487                 if (r)
 488                         goto ERROR;
 489
 490                 r = __loc_network_exclude(subnet1, other, list);
 491                 if (r)
 492                         goto ERROR;
 493
 494         } else if (loc_network_is_subnet(subnet2, other)) {
 495                 r = loc_network_list_push(list, subnet1);
 496                 if (r)
 497                         goto ERROR;
 498
 499                 r = __loc_network_exclude(subnet2, other, list);
 500                 if (r)
 501                         goto ERROR;
 502
 503         } else {
 504                 ERROR(network->ctx, "We should never get here\n");
 505                 r = 1;
 506                 goto ERROR;
 507         }
 508
 509 ERROR:
 510         if (subnet1)
 511                 loc_network_unref(subnet1);
 512
 513         if (subnet2)
 514                 loc_network_unref(subnet2);
 515
 516         return r;
 517 }
 518
 519 static int __loc_network_exclude_to_list(struct loc_network* self,
 520                 struct loc_network* other, struct loc_network_list* list) {
 521         // Other must be a subnet of self
 522         if (!loc_network_is_subnet(self, other)) {
 523                 DEBUG(self->ctx, "Network %p is not contained in network %p\n", other, self);
 524
 525                 // Exit silently
 526                 return 0;
 527         }
 528
 529         // We cannot perform this operation if both networks equal
 530         if (loc_network_cmp(self, other) == 0) {
 531                 DEBUG(self->ctx, "Networks %p and %p are equal\n", self, other);
 532
 533                 // Exit silently
 534                 return 0;
 535         }
 536
 537         return __loc_network_exclude(self, other, list);
 538 }
 539
 540 LOC_EXPORT struct loc_network_list* loc_network_exclude(
 541                 struct loc_network* self, struct loc_network* other) {
 542         struct loc_network_list* list;
 543
 544 #ifdef ENABLE_DEBUG
 545         char* n1 = loc_network_str(self);
 546         char* n2 = loc_network_str(other);
 547
 548         DEBUG(self->ctx, "Returning %s excluding %s...\n", n1, n2);
 549
 550         free(n1);
 551         free(n2);
 552 #endif
 553
 554         // Create a new list with the result
 555         int r = loc_network_list_new(self->ctx, &list);
 556         if (r) {
 557                 ERROR(self->ctx, "Could not create network list: %d\n", r);
 558
 559                 return NULL;
 560         }
 561
 562         r = __loc_network_exclude_to_list(self, other, list);
 563         if (r) {
 564                 loc_network_list_unref(list);
 565
 566                 return NULL;
 567         }
 568
 569         // Return the result
 570         return list;
 571 }
 572
 573 LOC_EXPORT struct loc_network_list* loc_network_exclude_list(
 574                 struct loc_network* network, struct loc_network_list* list) {
 575         struct loc_network_list* to_check;
 576
 577         // Create a new list with all networks to look at
 578         int r = loc_network_list_new(network->ctx, &to_check);
 579         if (r)
 580                 return NULL;
 581
 582         struct loc_network* subnet = NULL;
 583         struct loc_network_list* subnets = NULL;
 584
 585         for (unsigned int i = 0; i < loc_network_list_size(list); i++) {
 586                 subnet = loc_network_list_get(list, i);
 587
 588                 // Find all excluded networks
 589                 if (!loc_network_list_contains(to_check, subnet)) {
 590                         r = __loc_network_exclude_to_list(network, subnet, to_check);
 591                         if (r) {
 592                                 loc_network_list_unref(to_check);
 593                                 loc_network_unref(subnet);
 594
 595                                 return NULL;
 596                         }
 597                 }
 598
 599                 // Cleanup
 600                 loc_network_unref(subnet);
 601         }
 602
 603         r = loc_network_list_new(network->ctx, &subnets);
 604         if (r) {
 605                 loc_network_list_unref(to_check);
 606                 return NULL;
 607         }
 608
 609         off_t smallest_subnet = 0;
 610
 611         while (!loc_network_list_empty(to_check)) {
 612                 struct loc_network* subnet_to_check = loc_network_list_pop_first(to_check);
 613
 614                 // Check whether the subnet to check is part of the input list
 615                 if (loc_network_list_contains(list, subnet_to_check)) {
 616                         loc_network_unref(subnet_to_check);
 617                         continue;
 618                 }
 619
 620                 // Marks whether this subnet passed all checks
 621                 int passed = 1;
 622
 623                 for (unsigned int i = smallest_subnet; i < loc_network_list_size(list); i++) {
 624                         subnet = loc_network_list_get(list, i);
 625
 626                         // Drop this subnet if is a subnet of another subnet
 627                         if (loc_network_is_subnet(subnet, subnet_to_check)) {
 628                                 passed = 0;
 629                                 loc_network_unref(subnet);
 630                                 break;
 631                         }
 632
 633                         // Break it down if it overlaps
 634                         if (loc_network_overlaps(subnet, subnet_to_check)) {
 635                                 passed = 0;
 636
 637                                 __loc_network_exclude_to_list(subnet_to_check, subnet, to_check);
 638
 639                                 loc_network_unref(subnet);
 640                                 break;
 641                         }
 642
 643                         // If the subnet is strictly greater, we do not need to continue the search
 644                         r = loc_network_cmp(subnet, subnet_to_check);
 645                         if (r > 0) {
 646                                 loc_network_unref(subnet);
 647                                 break;
 648
 649                         // If it is strictly smaller, we can continue the search from here next
 650                         // time because all networks that are to be checked can only be larger
 651                         // than this one.
 652                         } else if (r < 0) {
 653                                 smallest_subnet = i;
 654                         }
 655
 656                         loc_network_unref(subnet);
 657                 }
 658
 659                 if (passed) {
 660                         r = loc_network_list_push(subnets, subnet_to_check);
 661                 }
 662
 663                 loc_network_unref(subnet_to_check);
 664         }
 665
 666         loc_network_list_unref(to_check);
 667
 668         return subnets;
 669 }
 670
 671 int loc_network_to_database_v1(struct loc_network* network, struct loc_database_network_v1* dbobj) {
 672         // Add country code
 673         loc_country_code_copy(dbobj->country_code, network->country_code);
 674
 675         // Add ASN
 676         dbobj->asn = htobe32(network->asn);
 677
 678         // Flags
 679         dbobj->flags = htobe16(network->flags);
 680
 681         return 0;
 682 }
 683
 684 int loc_network_new_from_database_v1(struct loc_ctx* ctx, struct loc_network** network,
 685                 struct in6_addr* address, unsigned int prefix, const struct loc_database_network_v1* dbobj) {
 686         char country_code[3] = "\0\0";
 687
 688         int r = loc_network_new(ctx, network, address, prefix);
 689         if (r) {
 690                 ERROR(ctx, "Could not allocate a new network: %s", strerror(-r));
 691                 return r;
 692         }
 693
 694         // Import country code
 695         loc_country_code_copy(country_code, dbobj->country_code);
 696
 697         r = loc_network_set_country_code(*network, country_code);
 698         if (r) {
 699                 ERROR(ctx, "Could not set country code: %s\n", country_code);
 700                 return r;
 701         }
 702
 703         // Import ASN
 704         uint32_t asn = be32toh(dbobj->asn);
 705         r = loc_network_set_asn(*network, asn);
 706         if (r) {
 707                 ERROR(ctx, "Could not set ASN: %d\n", asn);
 708                 return r;
 709         }
 710
 711         // Import flags
 712         int flags = be16toh(dbobj->flags);
 713         r = loc_network_set_flag(*network, flags);
 714         if (r) {
 715                 ERROR(ctx, "Could not set flags: %d\n", flags);
 716                 return r;
 717         }
 718
 719         return 0;
 720 }
 721
 722 struct loc_network_tree {
 723         struct loc_ctx* ctx;
 724         int refcount;
 725
 726         struct loc_network_tree_node* root;
 727 };
 728
 729 struct loc_network_tree_node {
 730         struct loc_ctx* ctx;
 731         int refcount;
 732
 733         struct loc_network_tree_node* zero;
 734         struct loc_network_tree_node* one;
 735
 736         struct loc_network* network;
 737 };
 738
 739 int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree) {
 740         struct loc_network_tree* t = calloc(1, sizeof(*t));
 741         if (!t)
 742                 return -ENOMEM;
 743
 744         t->ctx = loc_ref(ctx);
 745         t->refcount = 1;
 746
 747         // Create the root node
 748         int r = loc_network_tree_node_new(ctx, &t->root);
 749         if (r) {
 750                 loc_network_tree_unref(t);
 751                 return r;
 752         }
 753
 754         DEBUG(t->ctx, "Network tree allocated at %p\n", t);
 755         *tree = t;
 756         return 0;
 757 }
 758
 759 struct loc_network_tree_node* loc_network_tree_get_root(struct loc_network_tree* tree) {
 760         return loc_network_tree_node_ref(tree->root);
 761 }
 762
 763 static struct loc_network_tree_node* loc_network_tree_get_node(struct loc_network_tree_node* node, int path) {
 764         struct loc_network_tree_node** n;
 765
 766         if (path == 0)
 767                 n = &node->zero;
 768         else
 769                 n = &node->one;
 770
 771         // If the desired node doesn't exist, yet, we will create it
 772         if (*n == NULL) {
 773                 int r = loc_network_tree_node_new(node->ctx, n);
 774                 if (r)
 775                         return NULL;
 776         }
 777
 778         return *n;
 779 }
 780
 781 static struct loc_network_tree_node* loc_network_tree_get_path(struct loc_network_tree* tree, const struct in6_addr* address, unsigned int prefix) {
 782         struct loc_network_tree_node* node = tree->root;
 783
 784         for (unsigned int i = 0; i < prefix; i++) {
 785                 // Check if the ith bit is one or zero
 786                 node = loc_network_tree_get_node(node, loc_address_get_bit(address, i));
 787         }
 788
 789         return node;
 790 }
 791
 792 static int __loc_network_tree_walk(struct loc_ctx* ctx, struct loc_network_tree_node* node,
 793                 int(*filter_callback)(struct loc_network* network, void* data),
 794                 int(*callback)(struct loc_network* network, void* data), void* data) {
 795         int r;
 796
 797         // Finding a network ends the walk here
 798         if (node->network) {
 799                 if (filter_callback) {
 800                         int f = filter_callback(node->network, data);
 801                         if (f < 0)
 802                                 return f;
 803
 804                         // Skip network if filter function returns value greater than zero
 805                         if (f > 0)
 806                                 return 0;
 807                 }
 808
 809                 r = callback(node->network, data);
 810                 if (r)
 811                         return r;
 812         }
 813
 814         // Walk down on the left side of the tree first
 815         if (node->zero) {
 816                 r = __loc_network_tree_walk(ctx, node->zero, filter_callback, callback, data);
 817                 if (r)
 818                         return r;
 819         }
 820
 821         // Then walk on the other side
 822         if (node->one) {
 823                 r = __loc_network_tree_walk(ctx, node->one, filter_callback, callback, data);
 824                 if (r)
 825                         return r;
 826         }
 827
 828         return 0;
 829 }
 830
 831 int loc_network_tree_walk(struct loc_network_tree* tree,
 832                 int(*filter_callback)(struct loc_network* network, void* data),
 833                 int(*callback)(struct loc_network* network, void* data), void* data) {
 834         return __loc_network_tree_walk(tree->ctx, tree->root, filter_callback, callback, data);
 835 }
 836
 837 static void loc_network_tree_free(struct loc_network_tree* tree) {
 838         DEBUG(tree->ctx, "Releasing network tree at %p\n", tree);
 839
 840         loc_network_tree_node_unref(tree->root);
 841
 842         loc_unref(tree->ctx);
 843         free(tree);
 844 }
 845
 846 struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) {
 847         if (--tree->refcount > 0)
 848                 return tree;
 849
 850         loc_network_tree_free(tree);
 851         return NULL;
 852 }
 853
 854 static int __loc_network_tree_dump(struct loc_network* network, void* data) {
 855         DEBUG(network->ctx, "Dumping network at %p\n", network);
 856
 857         char* s = loc_network_str(network);
 858         if (!s)
 859                 return 1;
 860
 861         INFO(network->ctx, "%s\n", s);
 862         free(s);
 863
 864         return 0;
 865 }
 866
 867 int loc_network_tree_dump(struct loc_network_tree* tree) {
 868         DEBUG(tree->ctx, "Dumping network tree at %p\n", tree);
 869
 870         return loc_network_tree_walk(tree, NULL, __loc_network_tree_dump, NULL);
 871 }
 872
 873 int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_network* network) {
 874         DEBUG(tree->ctx, "Adding network %p to tree %p\n", network, tree);
 875
 876         struct loc_network_tree_node* node = loc_network_tree_get_path(tree,
 877                         &network->first_address, network->prefix);
 878         if (!node) {
 879                 ERROR(tree->ctx, "Could not find a node\n");
 880                 return -ENOMEM;
 881         }
 882
 883         // Check if node has not been set before
 884         if (node->network) {
 885                 DEBUG(tree->ctx, "There is already a network at this path\n");
 886                 return -EBUSY;
 887         }
 888
 889         // Point node to the network
 890         node->network = loc_network_ref(network);
 891
 892         return 0;
 893 }
 894
 895 static int __loc_network_tree_count(struct loc_network* network, void* data) {
 896         size_t* counter = (size_t*)data;
 897
 898         // Increase the counter for each network
 899         counter++;
 900
 901         return 0;
 902 }
 903
 904 size_t loc_network_tree_count_networks(struct loc_network_tree* tree) {
 905         size_t counter = 0;
 906
 907         int r = loc_network_tree_walk(tree, NULL, __loc_network_tree_count, &counter);
 908         if (r)
 909                 return r;
 910
 911         return counter;
 912 }
 913
 914 static size_t __loc_network_tree_count_nodes(struct loc_network_tree_node* node) {
 915         size_t counter = 1;
 916
 917         if (node->zero)
 918                 counter += __loc_network_tree_count_nodes(node->zero);
 919
 920         if (node->one)
 921                 counter += __loc_network_tree_count_nodes(node->one);
 922
 923         return counter;
 924 }
 925
 926 size_t loc_network_tree_count_nodes(struct loc_network_tree* tree) {
 927         return __loc_network_tree_count_nodes(tree->root);
 928 }
 929
 930 int loc_network_tree_node_new(struct loc_ctx* ctx, struct loc_network_tree_node** node) {
 931         struct loc_network_tree_node* n = calloc(1, sizeof(*n));
 932         if (!n)
 933                 return -ENOMEM;
 934
 935         n->ctx = loc_ref(ctx);
 936         n->refcount = 1;
 937
 938         n->zero = n->one = NULL;
 939
 940         DEBUG(n->ctx, "Network node allocated at %p\n", n);
 941         *node = n;
 942         return 0;
 943 }
 944
 945 struct loc_network_tree_node* loc_network_tree_node_ref(struct loc_network_tree_node* node) {
 946         if (node)
 947                 node->refcount++;
 948
 949         return node;
 950 }
 951
 952 static void loc_network_tree_node_free(struct loc_network_tree_node* node) {
 953         DEBUG(node->ctx, "Releasing network node at %p\n", node);
 954
 955         if (node->network)
 956                 loc_network_unref(node->network);
 957
 958         if (node->zero)
 959                 loc_network_tree_node_unref(node->zero);
 960
 961         if (node->one)
 962                 loc_network_tree_node_unref(node->one);
 963
 964         loc_unref(node->ctx);
 965         free(node);
 966 }
 967
 968 struct loc_network_tree_node* loc_network_tree_node_unref(struct loc_network_tree_node* node) {
 969         if (!node)
 970                 return NULL;
 971
 972         if (--node->refcount > 0)
 973                 return node;
 974
 975         loc_network_tree_node_free(node);
 976         return NULL;
 977 }
 978
 979 struct loc_network_tree_node* loc_network_tree_node_get(struct loc_network_tree_node* node, unsigned int index) {
 980         if (index == 0)
 981                 node = node->zero;
 982         else
 983                 node = node->one;
 984
 985         if (!node)
 986                 return NULL;
 987
 988         return loc_network_tree_node_ref(node);
 989 }
 990
 991 int loc_network_tree_node_is_leaf(struct loc_network_tree_node* node) {
 992         return (!!node->network);
 993 }
 994
 995 struct loc_network* loc_network_tree_node_get_network(struct loc_network_tree_node* node) {
 996         return loc_network_ref(node->network);
 997 }