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