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