#include <arpa/inet.h>
#include <assert.h>
-#include <endian.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
-#include <loc/libloc.h>
-#include <loc/network.h>
-#include <loc/private.h>
+#ifdef HAVE_ENDIAN_H
+# include <endian.h>
+#endif
+
+#include <libloc/libloc.h>
+#include <libloc/address.h>
+#include <libloc/compat.h>
+#include <libloc/country.h>
+#include <libloc/network.h>
+#include <libloc/network-list.h>
+#include <libloc/private.h>
struct loc_network {
struct loc_ctx* ctx;
int refcount;
- struct in6_addr start_address;
+ int family;
+ struct in6_addr first_address;
+ struct in6_addr last_address;
unsigned int prefix;
char country_code[3];
uint32_t asn;
+ enum loc_network_flags flags;
+
+ char string[INET6_ADDRSTRLEN + 4];
};
-static int valid_prefix(struct in6_addr* address, unsigned int prefix) {
- // The prefix cannot be larger than 128 bits
- if (prefix > 128)
+LOC_EXPORT int loc_network_new(struct loc_ctx* ctx, struct loc_network** network,
+ struct in6_addr* address, unsigned int prefix) {
+ // Validate the prefix
+ if (!loc_address_valid_prefix(address, prefix)) {
+ ERROR(ctx, "Invalid prefix in %s: %u\n", loc_address_str(address), prefix);
+ errno = EINVAL;
return 1;
+ }
- // And the prefix cannot be zero
- if (prefix == 0)
+ struct loc_network* n = calloc(1, sizeof(*n));
+ if (!n) {
+ errno = ENOMEM;
return 1;
+ }
+
+ n->ctx = loc_ref(ctx);
+ n->refcount = 1;
+
+ // Store the prefix
+ if (IN6_IS_ADDR_V4MAPPED(address))
+ n->prefix = prefix + 96;
+ else
+ n->prefix = prefix;
+
+ // Convert the prefix into a bitmask
+ struct in6_addr bitmask = loc_prefix_to_bitmask(n->prefix);
+
+ // Store the first and last address in the network
+ n->first_address = loc_address_and(address, &bitmask);
+ n->last_address = loc_address_or(&n->first_address, &bitmask);
+ // Set family
+ n->family = loc_address_family(&n->first_address);
+
+ DEBUG(n->ctx, "Network allocated at %p\n", n);
+ *network = n;
return 0;
}
-LOC_EXPORT int loc_network_new(struct loc_ctx* ctx, struct loc_network** network,
- struct in6_addr start_address, unsigned int prefix) {
- // Address cannot be unspecified
- if (IN6_IS_ADDR_UNSPECIFIED(&start_address)) {
- DEBUG(ctx, "Start address is unspecified\n");
- return -EINVAL;
- }
+LOC_EXPORT int loc_network_new_from_string(struct loc_ctx* ctx,
+ struct loc_network** network, const char* string) {
+ struct in6_addr address;
+ unsigned int prefix;
- // Address cannot be loopback
- if (IN6_IS_ADDR_LOOPBACK(&start_address)) {
- DEBUG(ctx, "Start address is loopback address\n");
- return -EINVAL;
+ // Parse the input
+ int r = loc_address_parse(&address, &prefix, string);
+ if (r) {
+ ERROR(ctx, "Could not parse network %s: %m\n", string);
+ return r;
}
- // Address cannot be link-local
- if (IN6_IS_ADDR_LINKLOCAL(&start_address)) {
- DEBUG(ctx, "Start address cannot be link-local\n");
- return -EINVAL;
- }
+ // Create a new network
+ return loc_network_new(ctx, network, &address, prefix);
+}
- // Address cannot be site-local
- if (IN6_IS_ADDR_SITELOCAL(&start_address)) {
- DEBUG(ctx, "Start address cannot be site-local\n");
- return -EINVAL;
- }
+LOC_EXPORT struct loc_network* loc_network_ref(struct loc_network* network) {
+ network->refcount++;
- // Validate the prefix
- if (valid_prefix(&start_address, prefix) != 0) {
- DEBUG(ctx, "Invalid prefix: %u\n", prefix);
- return -EINVAL;
- }
+ return network;
+}
- struct loc_network* n = calloc(1, sizeof(*n));
- if (!n)
- return -ENOMEM;
+static void loc_network_free(struct loc_network* network) {
+ DEBUG(network->ctx, "Releasing network at %p\n", network);
- n->ctx = loc_ref(ctx);
- n->refcount = 1;
+ loc_unref(network->ctx);
+ free(network);
+}
- n->start_address = start_address;
- n->prefix = prefix;
+LOC_EXPORT struct loc_network* loc_network_unref(struct loc_network* network) {
+ if (!network)
+ return NULL;
- DEBUG(n->ctx, "Network allocated at %p\n", n);
- *network = n;
- return 0;
+ if (--network->refcount > 0)
+ return network;
+
+ loc_network_free(network);
+ return NULL;
}
-static int loc_network_address_family(struct loc_network* network) {
- if (IN6_IS_ADDR_V4MAPPED(&network->start_address))
- return AF_INET;
+LOC_EXPORT const char* loc_network_str(struct loc_network* network) {
+ if (!*network->string) {
+ // Format the address
+ const char* address = loc_address_str(&network->first_address);
+ if (!address)
+ return NULL;
+
+ // Fetch the prefix
+ unsigned int prefix = loc_network_prefix(network);
+
+ // Format the string
+ int r = snprintf(network->string, sizeof(network->string) - 1,
+ "%s/%u", address, prefix);
+ if (r < 0) {
+ ERROR(network->ctx, "Could not format network string: %m\n");
+ *network->string = '\0';
+ return NULL;
+ }
+ }
- return AF_INET6;
+ return network->string;
}
-static int parse_address(struct loc_ctx* ctx, const char* string, struct in6_addr* address) {
- DEBUG(ctx, "Paring IP address %s\n", string);
+LOC_EXPORT int loc_network_address_family(struct loc_network* network) {
+ return network->family;
+}
- // Try parsing this as an IPv6 address
- int r = inet_pton(AF_INET6, string, address);
+LOC_EXPORT unsigned int loc_network_prefix(struct loc_network* network) {
+ switch (network->family) {
+ case AF_INET6:
+ return network->prefix;
- // If inet_pton returns one it has been successful
- if (r == 1) {
- DEBUG(ctx, "%s is an IPv6 address\n", string);
- return 0;
+ case AF_INET:
+ return network->prefix - 96;
}
- // Try parsing this as an IPv4 address
- struct in_addr ipv4_address;
- r = inet_pton(AF_INET, string, &ipv4_address);
- if (r == 1) {
- DEBUG(ctx, "%s is an IPv4 address\n", string);
+ return 0;
+}
- // Convert to IPv6-mapped address
- address->s6_addr32[0] = htonl(0x0000);
- address->s6_addr32[1] = htonl(0x0000);
- address->s6_addr32[2] = htonl(0xffff);
- address->s6_addr32[3] = ipv4_address.s_addr;
+LOC_EXPORT const struct in6_addr* loc_network_get_first_address(struct loc_network* network) {
+ return &network->first_address;
+}
- return 0;
- }
+LOC_EXPORT const char* loc_network_format_first_address(struct loc_network* network) {
+ return loc_address_str(&network->first_address);
+}
- DEBUG(ctx, "%s is not an valid IP address\n", string);
- return 1;
+LOC_EXPORT const struct in6_addr* loc_network_get_last_address(struct loc_network* network) {
+ return &network->last_address;
}
-LOC_EXPORT int loc_network_new_from_string(struct loc_ctx* ctx, struct loc_network** network,
- const char* address_string) {
- struct in6_addr start_address;
- unsigned int prefix = 0;
- char* prefix_string;
- int r = 1;
+LOC_EXPORT const char* loc_network_format_last_address(struct loc_network* network) {
+ return loc_address_str(&network->last_address);
+}
- // Make a copy of the string to work on it
- char* buffer = strdup(address_string);
- address_string = prefix_string = buffer;
+LOC_EXPORT int loc_network_matches_address(struct loc_network* network, const struct in6_addr* address) {
+ // Address must be larger than the start address
+ if (loc_address_cmp(&network->first_address, address) > 0)
+ return 0;
- // Split address and prefix
- address_string = strsep(&prefix_string, "/");
+ // Address must be smaller than the last address
+ if (loc_address_cmp(&network->last_address, address) < 0)
+ return 0;
- // Did we find a prefix?
- if (prefix_string) {
- // Convert prefix to integer
- prefix = strtol(prefix_string, NULL, 10);
+ // The address is inside this network
+ return 1;
+}
- if (prefix) {
- // Parse the address
- r = parse_address(ctx, address_string, &start_address);
- }
+LOC_EXPORT const char* loc_network_get_country_code(struct loc_network* network) {
+ return network->country_code;
+}
+
+LOC_EXPORT int loc_network_set_country_code(struct loc_network* network, const char* country_code) {
+ // Set empty country code
+ if (!country_code || !*country_code) {
+ *network->country_code = '\0';
+ return 0;
}
- // Free temporary buffer
- free(buffer);
+ // Check country code
+ if (!loc_country_code_is_valid(country_code))
+ return -EINVAL;
- if (r == 0) {
- r = loc_network_new(ctx, network, start_address, prefix);
- }
+ loc_country_code_copy(network->country_code, country_code);
- return r;
+ return 0;
}
-LOC_EXPORT struct loc_network* loc_network_ref(struct loc_network* network) {
- network->refcount++;
+LOC_EXPORT int loc_network_matches_country_code(struct loc_network* network, const char* country_code) {
+ // Search for any special flags
+ const int flag = loc_country_special_code_to_flag(country_code);
- return network;
+ // If we found a flag, we will return whether it is set or not
+ if (flag)
+ return loc_network_has_flag(network, flag);
+
+ // Check country code
+ if (!loc_country_code_is_valid(country_code))
+ return -EINVAL;
+
+ // Check for an exact match
+ return (network->country_code[0] == country_code[0])
+ && (network->country_code[1] == country_code[1]);
}
-static void loc_network_free(struct loc_network* network) {
- DEBUG(network->ctx, "Releasing network at %p\n", network);
+LOC_EXPORT uint32_t loc_network_get_asn(struct loc_network* network) {
+ return network->asn;
+}
- loc_unref(network->ctx);
- free(network);
+LOC_EXPORT int loc_network_set_asn(struct loc_network* network, uint32_t asn) {
+ network->asn = asn;
+
+ return 0;
}
-LOC_EXPORT struct loc_network* loc_network_unref(struct loc_network* network) {
- if (--network->refcount > 0)
- return network;
+LOC_EXPORT int loc_network_has_flag(struct loc_network* network, uint32_t flag) {
+ return network->flags & flag;
+}
- loc_network_free(network);
- return NULL;
+LOC_EXPORT int loc_network_set_flag(struct loc_network* network, uint32_t flag) {
+ network->flags |= flag;
+
+ return 0;
}
-static int format_ipv6_address(struct loc_network* network, char* string, size_t length) {
- const char* ret = inet_ntop(AF_INET6, &network->start_address, string, length);
- if (!ret)
+LOC_EXPORT int loc_network_cmp(struct loc_network* self, struct loc_network* other) {
+ // Compare address
+ int r = loc_address_cmp(&self->first_address, &other->first_address);
+ if (r)
+ return r;
+
+ // Compare prefix
+ if (self->prefix > other->prefix)
+ return 1;
+ else if (self->prefix < other->prefix)
return -1;
+ // Both networks are equal
return 0;
}
-static int format_ipv4_address(struct loc_network* network, char* string, size_t length) {
- struct in_addr ipv4_address;
- ipv4_address.s_addr = network->start_address.s6_addr32[3];
+LOC_EXPORT int loc_network_overlaps(struct loc_network* self, struct loc_network* other) {
+ // Either of the start addresses must be in the other subnet
+ if (loc_network_matches_address(self, &other->first_address))
+ return 1;
- const char* ret = inet_ntop(AF_INET, &ipv4_address, string, length);
- if (!ret)
- return -1;
+ if (loc_network_matches_address(other, &self->first_address))
+ return 1;
+
+ // Or either of the end addresses is in the other subnet
+ if (loc_network_matches_address(self, &other->last_address))
+ return 1;
+
+ if (loc_network_matches_address(other, &self->last_address))
+ return 1;
return 0;
}
-LOC_EXPORT char* loc_network_str(struct loc_network* network) {
+LOC_EXPORT int loc_network_is_subnet(struct loc_network* self, struct loc_network* other) {
+ // The prefix must be smaller (this avoids the more complex comparisons later)
+ if (self->prefix > other->prefix)
+ return 0;
+
+ // If the start address of the other network is smaller than this network,
+ // it cannot be a subnet.
+ if (loc_address_cmp(&self->first_address, &other->first_address) > 0)
+ return 0;
+
+ // If the end address of the other network is greater than this network,
+ // it cannot be a subnet.
+ if (loc_address_cmp(&self->last_address, &other->last_address) < 0)
+ return 0;
+
+ return 1;
+}
+
+LOC_EXPORT int loc_network_subnets(struct loc_network* network,
+ struct loc_network** subnet1, struct loc_network** subnet2) {
int r;
- const size_t length = INET6_ADDRSTRLEN + 4;
+ *subnet1 = NULL;
+ *subnet2 = NULL;
- char* string = malloc(length);
- if (!string)
- return NULL;
+ // New prefix length
+ unsigned int prefix = loc_network_prefix(network) + 1;
- int family = loc_network_address_family(network);
- switch (family) {
- case AF_INET6:
- r = format_ipv6_address(network, string, length);
- break;
+ // Check if the new prefix is valid
+ if (!loc_address_valid_prefix(&network->first_address, prefix)) {
+ ERROR(network->ctx, "Invalid prefix: %d\n", prefix);
+ errno = EINVAL;
+ return 1;
+ }
- case AF_INET:
- r = format_ipv4_address(network, string, length);
- break;
+ // Create the first half of the network
+ r = loc_network_new(network->ctx, subnet1, &network->first_address, prefix);
+ if (r)
+ return r;
+
+ // The next subnet starts after the first one
+ struct in6_addr first_address = (*subnet1)->last_address;
+ loc_address_increment(&first_address);
+
+ // Create the second half of the network
+ r = loc_network_new(network->ctx, subnet2, &first_address, prefix);
+ if (r)
+ return r;
- default:
- r = -1;
- break;
+ // Copy country code
+ const char* country_code = loc_network_get_country_code(network);
+ if (country_code) {
+ loc_network_set_country_code(*subnet1, country_code);
+ loc_network_set_country_code(*subnet2, country_code);
}
- if (r) {
- ERROR(network->ctx, "Could not convert network to string: %s\n", strerror(errno));
- free(string);
+ // Copy ASN
+ uint32_t asn = loc_network_get_asn(network);
+ if (asn) {
+ loc_network_set_asn(*subnet1, asn);
+ loc_network_set_asn(*subnet2, asn);
+ }
- return NULL;
+ // Copy flags
+ loc_network_set_flag(*subnet1, network->flags);
+ loc_network_set_flag(*subnet2, network->flags);
+
+ return 0;
+}
+
+static int __loc_network_exclude(struct loc_network* network,
+ struct loc_network* other, struct loc_network_list* list) {
+ struct loc_network* subnet1 = NULL;
+ struct loc_network* subnet2 = NULL;
+
+ int r = loc_network_subnets(network, &subnet1, &subnet2);
+ if (r)
+ goto ERROR;
+
+ if (loc_network_cmp(other, subnet1) == 0) {
+ r = loc_network_list_push(list, subnet2);
+ if (r)
+ goto ERROR;
+
+ } else if (loc_network_cmp(other, subnet2) == 0) {
+ r = loc_network_list_push(list, subnet1);
+ if (r)
+ goto ERROR;
+
+ } else if (loc_network_is_subnet(subnet1, other)) {
+ r = loc_network_list_push(list, subnet2);
+ if (r)
+ goto ERROR;
+
+ r = __loc_network_exclude(subnet1, other, list);
+ if (r)
+ goto ERROR;
+
+ } else if (loc_network_is_subnet(subnet2, other)) {
+ r = loc_network_list_push(list, subnet1);
+ if (r)
+ goto ERROR;
+
+ r = __loc_network_exclude(subnet2, other, list);
+ if (r)
+ goto ERROR;
+
+ } else {
+ ERROR(network->ctx, "We should never get here\n");
+ r = 1;
+ goto ERROR;
}
- // Append prefix
- sprintf(string + strlen(string), "/%u", network->prefix);
+ERROR:
+ if (subnet1)
+ loc_network_unref(subnet1);
- return string;
+ if (subnet2)
+ loc_network_unref(subnet2);
+
+ if (r)
+ DEBUG(network->ctx, "%s has failed with %d\n", __FUNCTION__, r);
+
+ return r;
}
-LOC_EXPORT const char* loc_network_get_country_code(struct loc_network* network) {
- return network->country_code;
+static int __loc_network_exclude_to_list(struct loc_network* self,
+ struct loc_network* other, struct loc_network_list* list) {
+ // Other must be a subnet of self
+ if (!loc_network_is_subnet(self, other)) {
+ DEBUG(self->ctx, "Network %p is not contained in network %p\n", other, self);
+
+ // Exit silently
+ return 0;
+ }
+
+ // We cannot perform this operation if both networks equal
+ if (loc_network_cmp(self, other) == 0) {
+ DEBUG(self->ctx, "Networks %p and %p are equal\n", self, other);
+
+ // Exit silently
+ return 0;
+ }
+
+ return __loc_network_exclude(self, other, list);
}
-LOC_EXPORT int loc_network_set_country_code(struct loc_network* network, const char* country_code) {
- // Country codes must be two characters
- if (strlen(country_code) != 2)
- return -EINVAL;
+LOC_EXPORT struct loc_network_list* loc_network_exclude(
+ struct loc_network* self, struct loc_network* other) {
+ struct loc_network_list* list;
+
+ DEBUG(self->ctx, "Returning %s excluding %s...\n",
+ loc_network_str(self), loc_network_str(other));
+
+ // Create a new list with the result
+ int r = loc_network_list_new(self->ctx, &list);
+ if (r) {
+ ERROR(self->ctx, "Could not create network list: %d\n", r);
- for (unsigned int i = 0; i < 3; i++) {
- network->country_code[i] = country_code[i];
+ return NULL;
}
- return 0;
+ r = __loc_network_exclude_to_list(self, other, list);
+ if (r) {
+ loc_network_list_unref(list);
+
+ return NULL;
+ }
+
+ // Return the result
+ return list;
}
-LOC_EXPORT uint32_t loc_network_get_asn(struct loc_network* network) {
- return network->asn;
+LOC_EXPORT struct loc_network_list* loc_network_exclude_list(
+ struct loc_network* network, struct loc_network_list* list) {
+ struct loc_network_list* to_check;
+
+ // Create a new list with all networks to look at
+ int r = loc_network_list_new(network->ctx, &to_check);
+ if (r)
+ return NULL;
+
+ struct loc_network* subnet = NULL;
+ struct loc_network_list* subnets = NULL;
+
+ for (unsigned int i = 0; i < loc_network_list_size(list); i++) {
+ subnet = loc_network_list_get(list, i);
+
+ // Find all excluded networks
+ if (!loc_network_list_contains(to_check, subnet)) {
+ r = __loc_network_exclude_to_list(network, subnet, to_check);
+ if (r) {
+ loc_network_list_unref(to_check);
+ loc_network_unref(subnet);
+
+ return NULL;
+ }
+ }
+
+ // Cleanup
+ loc_network_unref(subnet);
+ }
+
+ r = loc_network_list_new(network->ctx, &subnets);
+ if (r) {
+ loc_network_list_unref(to_check);
+ return NULL;
+ }
+
+ off_t smallest_subnet = 0;
+
+ while (!loc_network_list_empty(to_check)) {
+ struct loc_network* subnet_to_check = loc_network_list_pop_first(to_check);
+
+ // Check whether the subnet to check is part of the input list
+ if (loc_network_list_contains(list, subnet_to_check)) {
+ loc_network_unref(subnet_to_check);
+ continue;
+ }
+
+ // Marks whether this subnet passed all checks
+ int passed = 1;
+
+ for (unsigned int i = smallest_subnet; i < loc_network_list_size(list); i++) {
+ subnet = loc_network_list_get(list, i);
+
+ // Drop this subnet if is a subnet of another subnet
+ if (loc_network_is_subnet(subnet, subnet_to_check)) {
+ passed = 0;
+ loc_network_unref(subnet);
+ break;
+ }
+
+ // Break it down if it overlaps
+ if (loc_network_overlaps(subnet, subnet_to_check)) {
+ passed = 0;
+
+ __loc_network_exclude_to_list(subnet_to_check, subnet, to_check);
+
+ loc_network_unref(subnet);
+ break;
+ }
+
+ // If the subnet is strictly greater, we do not need to continue the search
+ r = loc_network_cmp(subnet, subnet_to_check);
+ if (r > 0) {
+ loc_network_unref(subnet);
+ break;
+
+ // If it is strictly smaller, we can continue the search from here next
+ // time because all networks that are to be checked can only be larger
+ // than this one.
+ } else if (r < 0) {
+ smallest_subnet = i;
+ }
+
+ loc_network_unref(subnet);
+ }
+
+ if (passed) {
+ r = loc_network_list_push(subnets, subnet_to_check);
+ }
+
+ loc_network_unref(subnet_to_check);
+ }
+
+ loc_network_list_unref(to_check);
+
+ return subnets;
}
-LOC_EXPORT int loc_network_set_asn(struct loc_network* network, uint32_t asn) {
- network->asn = asn;
+int loc_network_to_database_v1(struct loc_network* network, struct loc_database_network_v1* dbobj) {
+ // Add country code
+ loc_country_code_copy(dbobj->country_code, network->country_code);
+
+ // Add ASN
+ dbobj->asn = htobe32(network->asn);
+
+ // Flags
+ dbobj->flags = htobe16(network->flags);
return 0;
}
-LOC_EXPORT int loc_network_to_database_v0(struct loc_network* network, struct loc_database_network_v0* dbobj) {
- dbobj->prefix = htobe16(network->prefix);
+int loc_network_new_from_database_v1(struct loc_ctx* ctx, struct loc_network** network,
+ struct in6_addr* address, unsigned int prefix, const struct loc_database_network_v1* dbobj) {
+ char country_code[3] = "\0\0";
- // Add country code
- for (unsigned int i = 0; i < 2; i++) {
- dbobj->country_code[i] = network->country_code ? network->country_code[i] : '\0';
+ // Adjust prefix for IPv4
+ if (IN6_IS_ADDR_V4MAPPED(address))
+ prefix -= 96;
+
+ int r = loc_network_new(ctx, network, address, prefix);
+ if (r) {
+ ERROR(ctx, "Could not allocate a new network: %s", strerror(-r));
+ return r;
}
- // Add ASN
- dbobj->asn = htobe32(network->asn);
+ // Import country code
+ loc_country_code_copy(country_code, dbobj->country_code);
+
+ r = loc_network_set_country_code(*network, country_code);
+ if (r) {
+ ERROR(ctx, "Could not set country code: %s\n", country_code);
+ return r;
+ }
+
+ // Import ASN
+ uint32_t asn = be32toh(dbobj->asn);
+ r = loc_network_set_asn(*network, asn);
+ if (r) {
+ ERROR(ctx, "Could not set ASN: %d\n", asn);
+ return r;
+ }
+
+ // Import flags
+ int flags = be16toh(dbobj->flags);
+ r = loc_network_set_flag(*network, flags);
+ if (r) {
+ ERROR(ctx, "Could not set flags: %d\n", flags);
+ return r;
+ }
return 0;
}
};
struct loc_network_tree_node {
+ struct loc_ctx* ctx;
+ int refcount;
+
struct loc_network_tree_node* zero;
struct loc_network_tree_node* one;
struct loc_network* network;
};
-LOC_EXPORT int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree) {
+int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree) {
struct loc_network_tree* t = calloc(1, sizeof(*t));
if (!t)
return -ENOMEM;
t->refcount = 1;
// Create the root node
- t->root = calloc(1, sizeof(*t->root));
+ int r = loc_network_tree_node_new(ctx, &t->root);
+ if (r) {
+ loc_network_tree_unref(t);
+ return r;
+ }
DEBUG(t->ctx, "Network tree allocated at %p\n", t);
*tree = t;
return 0;
}
-static int loc_network_tree_node_new(struct loc_network_tree_node** node) {
- struct loc_network_tree_node* n = calloc(1, sizeof(*n));
- if (!n)
- return -ENOMEM;
-
- n->zero = n->one = NULL;
-
- *node = n;
- return 0;
+struct loc_network_tree_node* loc_network_tree_get_root(struct loc_network_tree* tree) {
+ return loc_network_tree_node_ref(tree->root);
}
static struct loc_network_tree_node* loc_network_tree_get_node(struct loc_network_tree_node* node, int path) {
struct loc_network_tree_node** n;
- if (path)
- n = &node->one;
- else
+ if (path == 0)
n = &node->zero;
+ else
+ n = &node->one;
// If the desired node doesn't exist, yet, we will create it
if (*n == NULL) {
- int r = loc_network_tree_node_new(n);
+ int r = loc_network_tree_node_new(node->ctx, n);
if (r)
return NULL;
}
return *n;
}
-static struct loc_network_tree_node* loc_network_tree_get_path(struct loc_network_tree* tree, const struct in6_addr* address) {
+static struct loc_network_tree_node* loc_network_tree_get_path(struct loc_network_tree* tree, const struct in6_addr* address, unsigned int prefix) {
struct loc_network_tree_node* node = tree->root;
- for (unsigned int i = 127; i > 0; i--) {
+ for (unsigned int i = 0; i < prefix; i++) {
// Check if the ith bit is one or zero
- node = loc_network_tree_get_node(node, ((address->s6_addr32[i / 32] & (1 << (i % 32))) == 0));
+ node = loc_network_tree_get_node(node, loc_address_get_bit(address, i));
}
return node;
return 0;
}
-LOC_EXPORT int loc_network_tree_walk(struct loc_network_tree* tree,
+int loc_network_tree_walk(struct loc_network_tree* tree,
int(*filter_callback)(struct loc_network* network, void* data),
int(*callback)(struct loc_network* network, void* data), void* data) {
return __loc_network_tree_walk(tree->ctx, tree->root, filter_callback, callback, data);
}
-static void loc_network_tree_free_subtree(struct loc_network_tree_node* node) {
- if (node->network)
- loc_network_unref(node->network);
-
- if (node->zero)
- loc_network_tree_free_subtree(node->zero);
-
- if (node->one)
- loc_network_tree_free_subtree(node->one);
-
- free(node);
-}
-
static void loc_network_tree_free(struct loc_network_tree* tree) {
DEBUG(tree->ctx, "Releasing network tree at %p\n", tree);
- loc_network_tree_free_subtree(tree->root);
+ loc_network_tree_node_unref(tree->root);
loc_unref(tree->ctx);
free(tree);
}
-LOC_EXPORT struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) {
+struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) {
if (--tree->refcount > 0)
return tree;
return NULL;
}
-int __loc_network_tree_dump(struct loc_network* network, void* data) {
+static int __loc_network_tree_dump(struct loc_network* network, void* data) {
DEBUG(network->ctx, "Dumping network at %p\n", network);
- char* s = loc_network_str(network);
+ const char* s = loc_network_str(network);
if (!s)
return 1;
INFO(network->ctx, "%s\n", s);
- free(s);
return 0;
}
-LOC_EXPORT int loc_network_tree_dump(struct loc_network_tree* tree) {
+int loc_network_tree_dump(struct loc_network_tree* tree) {
DEBUG(tree->ctx, "Dumping network tree at %p\n", tree);
return loc_network_tree_walk(tree, NULL, __loc_network_tree_dump, NULL);
}
-LOC_EXPORT int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_network* network) {
+int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_network* network) {
DEBUG(tree->ctx, "Adding network %p to tree %p\n", network, tree);
- struct loc_network_tree_node* node = loc_network_tree_get_path(tree, &network->start_address);
+ struct loc_network_tree_node* node = loc_network_tree_get_path(tree,
+ &network->first_address, network->prefix);
if (!node) {
ERROR(tree->ctx, "Could not find a node\n");
return -ENOMEM;
// Check if node has not been set before
if (node->network) {
DEBUG(tree->ctx, "There is already a network at this path\n");
- return 1;
+ return -EBUSY;
}
// Point node to the network
return 0;
}
-LOC_EXPORT size_t loc_network_tree_count_networks(struct loc_network_tree* tree) {
+size_t loc_network_tree_count_networks(struct loc_network_tree* tree) {
size_t counter = 0;
int r = loc_network_tree_walk(tree, NULL, __loc_network_tree_count, &counter);
return counter;
}
+
+static size_t __loc_network_tree_count_nodes(struct loc_network_tree_node* node) {
+ size_t counter = 1;
+
+ if (node->zero)
+ counter += __loc_network_tree_count_nodes(node->zero);
+
+ if (node->one)
+ counter += __loc_network_tree_count_nodes(node->one);
+
+ return counter;
+}
+
+size_t loc_network_tree_count_nodes(struct loc_network_tree* tree) {
+ return __loc_network_tree_count_nodes(tree->root);
+}
+
+int loc_network_tree_node_new(struct loc_ctx* ctx, struct loc_network_tree_node** node) {
+ struct loc_network_tree_node* n = calloc(1, sizeof(*n));
+ if (!n)
+ return -ENOMEM;
+
+ n->ctx = loc_ref(ctx);
+ n->refcount = 1;
+
+ n->zero = n->one = NULL;
+
+ DEBUG(n->ctx, "Network node allocated at %p\n", n);
+ *node = n;
+ return 0;
+}
+
+struct loc_network_tree_node* loc_network_tree_node_ref(struct loc_network_tree_node* node) {
+ if (node)
+ node->refcount++;
+
+ return node;
+}
+
+static void loc_network_tree_node_free(struct loc_network_tree_node* node) {
+ DEBUG(node->ctx, "Releasing network node at %p\n", node);
+
+ if (node->network)
+ loc_network_unref(node->network);
+
+ if (node->zero)
+ loc_network_tree_node_unref(node->zero);
+
+ if (node->one)
+ loc_network_tree_node_unref(node->one);
+
+ loc_unref(node->ctx);
+ free(node);
+}
+
+struct loc_network_tree_node* loc_network_tree_node_unref(struct loc_network_tree_node* node) {
+ if (!node)
+ return NULL;
+
+ if (--node->refcount > 0)
+ return node;
+
+ loc_network_tree_node_free(node);
+ return NULL;
+}
+
+struct loc_network_tree_node* loc_network_tree_node_get(struct loc_network_tree_node* node, unsigned int index) {
+ if (index == 0)
+ node = node->zero;
+ else
+ node = node->one;
+
+ if (!node)
+ return NULL;
+
+ return loc_network_tree_node_ref(node);
+}
+
+int loc_network_tree_node_is_leaf(struct loc_network_tree_node* node) {
+ return (!!node->network);
+}
+
+struct loc_network* loc_network_tree_node_get_network(struct loc_network_tree_node* node) {
+ return loc_network_ref(node->network);
+}