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