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