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