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