[people/ms/libloc.git] / src / network.c

/*
	libloc - A library to determine the location of someone on the Internet

	Copyright (C) 2017 IPFire Development Team <info@ipfire.org>

	This library is free software; you can redistribute it and/or
	modify it under the terms of the GNU Lesser General Public
	License as published by the Free Software Foundation; either
	version 2.1 of the License, or (at your option) any later version.

	This library is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
	Lesser General Public License for more details.
*/

#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>

struct loc_network {
	struct loc_ctx* ctx;
	int refcount;

	struct in6_addr start_address;
	unsigned int prefix;

	char country_code[3];
	uint32_t asn;
};

static int valid_prefix(struct in6_addr* address, unsigned int prefix) {
	// The prefix cannot be larger than 128 bits
	if (prefix > 128)
		return 1;

	// And the prefix cannot be zero
	if (prefix == 0)
		return 1;

	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;
	}

	// Address cannot be loopback
	if (IN6_IS_ADDR_LOOPBACK(&start_address)) {
		DEBUG(ctx, "Start address is loopback address\n");
		return -EINVAL;
	}

	// Address cannot be link-local
	if (IN6_IS_ADDR_LINKLOCAL(&start_address)) {
		DEBUG(ctx, "Start address cannot be link-local\n");
		return -EINVAL;
	}

	// Address cannot be site-local
	if (IN6_IS_ADDR_SITELOCAL(&start_address)) {
		DEBUG(ctx, "Start address cannot be site-local\n");
		return -EINVAL;
	}

	// Validate the prefix
	if (valid_prefix(&start_address, prefix) != 0) {
		DEBUG(ctx, "Invalid prefix: %u\n", prefix);
		return -EINVAL;
	}

	struct loc_network* n = calloc(1, sizeof(*n));
	if (!n)
		return -ENOMEM;

	n->ctx = loc_ref(ctx);
	n->refcount = 1;

	n->start_address = start_address;
	n->prefix = prefix;

	DEBUG(n->ctx, "Network allocated at %p\n", n);
	*network = n;
	return 0;
}

static int loc_network_address_family(struct loc_network* network) {
	if (IN6_IS_ADDR_V4MAPPED(&network->start_address))
		return AF_INET;

	return AF_INET6;
}

static int parse_address(struct loc_ctx* ctx, const char* string, struct in6_addr* address) {
	DEBUG(ctx, "Paring IP address %s\n", string);

	// Try parsing this as an IPv6 address
	int r = inet_pton(AF_INET6, string, address);

	// If inet_pton returns one it has been successful
	if (r == 1) {
		DEBUG(ctx, "%s is an IPv6 address\n", string);
		return 0;
	}

	// 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);

		// 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;

		return 0;
	}

	DEBUG(ctx, "%s is not an valid IP address\n", string);
	return 1;
}

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;

	// Make a copy of the string to work on it
	char* buffer = strdup(address_string);
	address_string = prefix_string = buffer;

	// Split address and prefix
	address_string = strsep(&prefix_string, "/");

	// Did we find a prefix?
	if (prefix_string) {
		// Convert prefix to integer
		prefix = strtol(prefix_string, NULL, 10);

		if (prefix) {
			// Parse the address
			r = parse_address(ctx, address_string, &start_address);
		}
	}

	// Free temporary buffer
	free(buffer);

	if (r == 0) {
		r = loc_network_new(ctx, network, start_address, prefix);
	}

	return r;
}

LOC_EXPORT struct loc_network* loc_network_ref(struct loc_network* network) {
	network->refcount++;

	return network;
}

static void loc_network_free(struct loc_network* network) {
	DEBUG(network->ctx, "Releasing network at %p\n", network);

	loc_unref(network->ctx);
	free(network);
}

LOC_EXPORT struct loc_network* loc_network_unref(struct loc_network* network) {
	if (--network->refcount > 0)
		return network;

	loc_network_free(network);
	return NULL;
}

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)
		return -1;

	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];

	const char* ret = inet_ntop(AF_INET, &ipv4_address, string, length);
	if (!ret)
		return -1;

	return 0;
}

LOC_EXPORT char* loc_network_str(struct loc_network* network) {
	int r;
	const size_t length = INET6_ADDRSTRLEN + 4;

	char* string = malloc(length);
	if (!string)
		return NULL;

	int family = loc_network_address_family(network);
	switch (family) {
		case AF_INET6:
			r = format_ipv6_address(network, string, length);
			break;

		case AF_INET:
			r = format_ipv4_address(network, string, length);
			break;

		default:
			r = -1;
			break;
	}

	if (r) {
		ERROR(network->ctx, "Could not convert network to string: %s\n", strerror(errno));
		free(string);

		return NULL;
	}

	// Append prefix
	sprintf(string + strlen(string), "/%u", network->prefix);

	return string;
}

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) {
	// Country codes must be two characters
	if (strlen(country_code) != 2)
		return -EINVAL;

	for (unsigned int i = 0; i < 3; i++) {
		network->country_code[i] = country_code[i];
	}

	return 0;
}

LOC_EXPORT uint32_t loc_network_get_asn(struct loc_network* network) {
	return network->asn;
}

LOC_EXPORT int loc_network_set_asn(struct loc_network* network, uint32_t asn) {
	network->asn = asn;

	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);

	// Add country code
	for (unsigned int i = 0; i < 2; i++) {
		dbobj->country_code[i] = network->country_code ? network->country_code[i] : '\0';
	}

	// Add ASN
	dbobj->asn = htobe32(network->asn);

	return 0;
}

struct loc_network_tree {
	struct loc_ctx* ctx;
	int refcount;

	struct loc_network_tree_node* root;
};

struct loc_network_tree_node {
	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) {
	struct loc_network_tree* t = calloc(1, sizeof(*t));
	if (!t)
		return -ENOMEM;

	t->ctx = loc_ref(ctx);
	t->refcount = 1;

	// Create the root node
	t->root = calloc(1, sizeof(*t->root));

	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;
}

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
		n = &node->zero;

	// If the desired node doesn't exist, yet, we will create it
	if (*n == NULL) {
		int r = loc_network_tree_node_new(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) {
	struct loc_network_tree_node* node = tree->root;

	for (unsigned int i = 127; i > 0; 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));
	}

	return node;
}

static int __loc_network_tree_walk(struct loc_ctx* ctx, struct loc_network_tree_node* node,
		int(*filter_callback)(struct loc_network* network, void* data),
		int(*callback)(struct loc_network* network, void* data), void* data) {
	int r;

	// Finding a network ends the walk here
	if (node->network) {
		if (filter_callback) {
			int f = filter_callback(node->network, data);
			if (f < 0)
				return f;

			// Skip network if filter function returns value greater than zero
			if (f > 0)
				return 0;
		}

		r = callback(node->network, data);
		if (r)
			return r;
	}

	// Walk down on the left side of the tree first
	if (node->zero) {
		r = __loc_network_tree_walk(ctx, node->zero, filter_callback, callback, data);
		if (r)
			return r;
	}

	// Then walk on the other side
	if (node->one) {
		r = __loc_network_tree_walk(ctx, node->one, filter_callback, callback, data);
		if (r)
			return r;
	}

	return 0;
}

LOC_EXPORT 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_unref(tree->ctx);
	free(tree);
}

LOC_EXPORT struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) {
	if (--tree->refcount > 0)
		return tree;

	loc_network_tree_free(tree);
	return NULL;
}

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);
	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) {
	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) {
	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);
	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;
	}

	// Point node to the network
	node->network = loc_network_ref(network);

	return 0;
}

static int __loc_network_tree_count(struct loc_network* network, void* data) {
	size_t* counter = (size_t*)data;

	// Increase the counter for each network
	counter++;

	return 0;
}

LOC_EXPORT 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);
	if (r)
		return r;

	return counter;
}
Commit	Line	Data
3b5f4af2 MT	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>
f3e02bc5	19	#include <endian.h>
3b5f4af2	20	#include <errno.h>
71ff3e69	21	#include <stdio.h>
3b5f4af2 MT	22	#include <stdlib.h>
	23	#include <string.h>
	24
	25	#include <loc/libloc.h>
	26	#include <loc/network.h>
9fc7f001	27	#include <loc/private.h>
3b5f4af2 MT	28
	29	struct loc_network {
	30	struct loc_ctx* ctx;
	31	int refcount;
	32
	33	struct in6_addr start_address;
	34	unsigned int prefix;
	35
	36	char country_code[3];
71ff3e69	37	uint32_t asn;
3b5f4af2 MT	38	};
3b5f4af2 MT	39
6183c0f2 MT	40	static int valid_prefix(struct in6_addr* address, unsigned int prefix) {
	41	// The prefix cannot be larger than 128 bits
	42	if (prefix > 128)
	43	return 1;
	44
	45	// And the prefix cannot be zero
	46	if (prefix == 0)
	47	return 1;
	48
	49	return 0;
	50	}
	51
3b5f4af2 MT	52	LOC_EXPORT int loc_network_new(struct loc_ctx* ctx, struct loc_network** network,
	53	struct in6_addr start_address, unsigned int prefix) {
	54	// Address cannot be unspecified
	55	if (IN6_IS_ADDR_UNSPECIFIED(&start_address)) {
	56	DEBUG(ctx, "Start address is unspecified\n");
	57	return -EINVAL;
	58	}
	59
	60	// Address cannot be loopback
	61	if (IN6_IS_ADDR_LOOPBACK(&start_address)) {
	62	DEBUG(ctx, "Start address is loopback address\n");
	63	return -EINVAL;
	64	}
	65
	66	// Address cannot be link-local
	67	if (IN6_IS_ADDR_LINKLOCAL(&start_address)) {
	68	DEBUG(ctx, "Start address cannot be link-local\n");
	69	return -EINVAL;
	70	}
	71
	72	// Address cannot be site-local
	73	if (IN6_IS_ADDR_SITELOCAL(&start_address)) {
	74	DEBUG(ctx, "Start address cannot be site-local\n");
	75	return -EINVAL;
	76	}
	77
6183c0f2 MT	78	// Validate the prefix
	79	if (valid_prefix(&start_address, prefix) != 0) {
	80	DEBUG(ctx, "Invalid prefix: %u\n", prefix);
	81	return -EINVAL;
	82	}
	83
3b5f4af2 MT	84	struct loc_network* n = calloc(1, sizeof(*n));
	85	if (!n)
	86	return -ENOMEM;
	87
	88	n->ctx = loc_ref(ctx);
	89	n->refcount = 1;
	90
	91	n->start_address = start_address;
	92	n->prefix = prefix;
	93
	94	DEBUG(n->ctx, "Network allocated at %p\n", n);
	95	*network = n;
	96	return 0;
	97	}
	98
d3409788 MT	99	static int loc_network_address_family(struct loc_network* network) {
	100	if (IN6_IS_ADDR_V4MAPPED(&network->start_address))
	101	return AF_INET;
	102
	103	return AF_INET6;
	104	}
	105
	106	static int parse_address(struct loc_ctx* ctx, const char* string, struct in6_addr* address) {
	107	DEBUG(ctx, "Paring IP address %s\n", string);
	108
	109	// Try parsing this as an IPv6 address
	110	int r = inet_pton(AF_INET6, string, address);
	111
	112	// If inet_pton returns one it has been successful
	113	if (r == 1) {
	114	DEBUG(ctx, "%s is an IPv6 address\n", string);
	115	return 0;
	116	}
	117
	118	// Try parsing this as an IPv4 address
	119	struct in_addr ipv4_address;
	120	r = inet_pton(AF_INET, string, &ipv4_address);
	121	if (r == 1) {
	122	DEBUG(ctx, "%s is an IPv4 address\n", string);
	123
	124	// Convert to IPv6-mapped address
	125	address->s6_addr32[0] = htonl(0x0000);
	126	address->s6_addr32[1] = htonl(0x0000);
	127	address->s6_addr32[2] = htonl(0xffff);
	128	address->s6_addr32[3] = ipv4_address.s_addr;
	129
	130	return 0;
	131	}
	132
	133	DEBUG(ctx, "%s is not an valid IP address\n", string);
	134	return 1;
	135	}
	136
3b5f4af2 MT	137	LOC_EXPORT int loc_network_new_from_string(struct loc_ctx* ctx, struct loc_network** network,
	138	const char* address_string) {
	139	struct in6_addr start_address;
b61f14fc	140	unsigned int prefix = 0;
3b5f4af2	141	char* prefix_string;
b61f14fc	142	int r = 1;
3b5f4af2 MT	143
	144	// Make a copy of the string to work on it
	145	char* buffer = strdup(address_string);
	146	address_string = prefix_string = buffer;
	147
	148	// Split address and prefix
	149	address_string = strsep(&prefix_string, "/");
	150
b61f14fc MT	151	// Did we find a prefix?
	152	if (prefix_string) {
	153	// Convert prefix to integer
	154	prefix = strtol(prefix_string, NULL, 10);
3b5f4af2	155
b61f14fc MT	156	if (prefix) {
	157	// Parse the address
	158	r = parse_address(ctx, address_string, &start_address);
	159	}
	160	}
3b5f4af2 MT	161
	162	// Free temporary buffer
	163	free(buffer);
	164
d3409788	165	if (r == 0) {
3b5f4af2 MT	166	r = loc_network_new(ctx, network, start_address, prefix);
	167	}
	168
	169	return r;
	170	}
	171
	172	LOC_EXPORT struct loc_network* loc_network_ref(struct loc_network* network) {
	173	network->refcount++;
	174
	175	return network;
	176	}
	177
	178	static void loc_network_free(struct loc_network* network) {
	179	DEBUG(network->ctx, "Releasing network at %p\n", network);
	180
3b5f4af2 MT	181	loc_unref(network->ctx);
	182	free(network);
	183	}
	184
	185	LOC_EXPORT struct loc_network* loc_network_unref(struct loc_network* network) {
	186	if (--network->refcount > 0)
	187	return network;
	188
	189	loc_network_free(network);
	190	return NULL;
	191	}
	192
d3409788 MT	193	static int format_ipv6_address(struct loc_network* network, char* string, size_t length) {
	194	const char* ret = inet_ntop(AF_INET6, &network->start_address, string, length);
	195	if (!ret)
	196	return -1;
	197
	198	return 0;
	199	}
	200
	201	static int format_ipv4_address(struct loc_network* network, char* string, size_t length) {
	202	struct in_addr ipv4_address;
	203	ipv4_address.s_addr = network->start_address.s6_addr32[3];
	204
	205	const char* ret = inet_ntop(AF_INET, &ipv4_address, string, length);
	206	if (!ret)
	207	return -1;
	208
	209	return 0;
	210	}
	211
3b5f4af2	212	LOC_EXPORT char* loc_network_str(struct loc_network* network) {
d3409788 MT	213	int r;
d3409788 MT	214	const size_t length = INET6_ADDRSTRLEN + 4;
3b5f4af2	215
d3409788	216	char* string = malloc(length);
3b5f4af2 MT	217	if (!string)
	218	return NULL;
	219
d3409788 MT	220	int family = loc_network_address_family(network);
	221	switch (family) {
	222	case AF_INET6:
	223	r = format_ipv6_address(network, string, length);
	224	break;
3b5f4af2	225
d3409788 MT	226	case AF_INET:
	227	r = format_ipv4_address(network, string, length);
	228	break;
	229
	230	default:
	231	r = -1;
	232	break;
	233	}
	234
	235	if (r) {
	236	ERROR(network->ctx, "Could not convert network to string: %s\n", strerror(errno));
3b5f4af2	237	free(string);
d3409788	238
3b5f4af2 MT	239	return NULL;
	240	}
	241
	242	// Append prefix
	243	sprintf(string + strlen(string), "/%u", network->prefix);
	244
	245	return string;
	246	}
	247
	248	LOC_EXPORT const char* loc_network_get_country_code(struct loc_network* network) {
	249	return network->country_code;
	250	}
	251
	252	LOC_EXPORT int loc_network_set_country_code(struct loc_network* network, const char* country_code) {
	253	// Country codes must be two characters
	254	if (strlen(country_code) != 2)
	255	return -EINVAL;
	256
	257	for (unsigned int i = 0; i < 3; i++) {
	258	network->country_code[i] = country_code[i];
	259	}
	260
	261	return 0;
	262	}
	263
71ff3e69 MT	264	LOC_EXPORT uint32_t loc_network_get_asn(struct loc_network* network) {
	265	return network->asn;
	266	}
	267
	268	LOC_EXPORT int loc_network_set_asn(struct loc_network* network, uint32_t asn) {
	269	network->asn = asn;
	270
	271	return 0;
	272	}
	273
f3e02bc5 MT	274	LOC_EXPORT int loc_network_to_database_v0(struct loc_network* network, struct loc_database_network_v0* dbobj) {
	275	dbobj->prefix = htobe16(network->prefix);
	276
	277	// Add country code
	278	for (unsigned int i = 0; i < 2; i++) {
	279	dbobj->country_code[i] = network->country_code ? network->country_code[i] : '\0';
	280	}
	281
	282	// Add ASN
71ff3e69	283	dbobj->asn = htobe32(network->asn);
f3e02bc5 MT	284
	285	return 0;
	286	}
	287
3b5f4af2 MT	288	struct loc_network_tree {
	289	struct loc_ctx* ctx;
	290	int refcount;
	291
	292	struct loc_network_tree_node* root;
	293	};
	294
	295	struct loc_network_tree_node {
	296	struct loc_network_tree_node* zero;
	297	struct loc_network_tree_node* one;
	298
	299	struct loc_network* network;
	300	};
	301
	302	LOC_EXPORT int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree) {
	303	struct loc_network_tree* t = calloc(1, sizeof(*t));
	304	if (!t)
	305	return -ENOMEM;
	306
	307	t->ctx = loc_ref(ctx);
	308	t->refcount = 1;
	309
	310	// Create the root node
	311	t->root = calloc(1, sizeof(*t->root));
	312
	313	DEBUG(t->ctx, "Network tree allocated at %p\n", t);
	314	*tree = t;
	315	return 0;
	316	}
	317
	318	static int loc_network_tree_node_new(struct loc_network_tree_node** node) {
	319	struct loc_network_tree_node* n = calloc(1, sizeof(*n));
	320	if (!n)
	321	return -ENOMEM;
	322
	323	n->zero = n->one = NULL;
	324
	325	*node = n;
	326	return 0;
	327	}
	328
	329	static struct loc_network_tree_node* loc_network_tree_get_node(struct loc_network_tree_node* node, int path) {
	330	struct loc_network_tree_node** n;
	331
	332	if (path)
	333	n = &node->one;
	334	else
	335	n = &node->zero;
	336
	337	// If the desired node doesn't exist, yet, we will create it
	338	if (*n == NULL) {
	339	int r = loc_network_tree_node_new(n);
	340	if (r)
	341	return NULL;
	342	}
	343
	344	return *n;
	345	}
	346
	347	static struct loc_network_tree_node* loc_network_tree_get_path(struct loc_network_tree* tree, const struct in6_addr* address) {
	348	struct loc_network_tree_node* node = tree->root;
	349
	350	for (unsigned int i = 127; i > 0; i--) {
	351	// Check if the ith bit is one or zero
352	node = loc_network_tree_get_node(node, ((address->s6_addr32[i / 32] & (1 << (i % 32))) == 0));
353	}
354
355	return node;
356	}
357
358	static int __loc_network_tree_walk(struct loc_ctx* ctx, struct loc_network_tree_node* node,
f3e02bc5 MT	359	int(filter_callback)(struct loc_network network, void* data),
f3e02bc5 MT	360	int(callback)(struct loc_network network, void* data), void* data) {
3b5f4af2 MT	361	int r;
	362
	363	// Finding a network ends the walk here
	364	if (node->network) {
	365	if (filter_callback) {
f3e02bc5	366	int f = filter_callback(node->network, data);
3b5f4af2 MT	367	if (f < 0)
	368	return f;
	369
	370	// Skip network if filter function returns value greater than zero
	371	if (f > 0)
	372	return 0;
	373	}
	374
f3e02bc5	375	r = callback(node->network, data);
3b5f4af2 MT	376	if (r)
	377	return r;
	378	}
	379
	380	// Walk down on the left side of the tree first
	381	if (node->zero) {
f3e02bc5	382	r = __loc_network_tree_walk(ctx, node->zero, filter_callback, callback, data);
3b5f4af2 MT	383	if (r)
	384	return r;
	385	}
	386
	387	// Then walk on the other side
	388	if (node->one) {
f3e02bc5	389	r = __loc_network_tree_walk(ctx, node->one, filter_callback, callback, data);
3b5f4af2 MT	390	if (r)
	391	return r;
	392	}
	393
	394	return 0;
	395	}
	396
f3e02bc5 MT	397	LOC_EXPORT int loc_network_tree_walk(struct loc_network_tree* tree,
	398	int(filter_callback)(struct loc_network network, void* data),
	399	int(callback)(struct loc_network network, void* data), void* data) {
	400	return __loc_network_tree_walk(tree->ctx, tree->root, filter_callback, callback, data);
	401	}
	402
3b5f4af2 MT	403	static void loc_network_tree_free_subtree(struct loc_network_tree_node* node) {
	404	if (node->network)
	405	loc_network_unref(node->network);
	406
	407	if (node->zero)
	408	loc_network_tree_free_subtree(node->zero);
	409
	410	if (node->one)
	411	loc_network_tree_free_subtree(node->one);
	412
	413	free(node);
	414	}
	415
	416	static void loc_network_tree_free(struct loc_network_tree* tree) {
	417	DEBUG(tree->ctx, "Releasing network tree at %p\n", tree);
	418
	419	loc_network_tree_free_subtree(tree->root);
	420
	421	loc_unref(tree->ctx);
	422	free(tree);
	423	}
	424
	425	LOC_EXPORT struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) {
	426	if (--tree->refcount > 0)
	427	return tree;
	428
	429	loc_network_tree_free(tree);
	430	return NULL;
	431	}
	432
f3e02bc5	433	int __loc_network_tree_dump(struct loc_network* network, void* data) {
3b5f4af2 MT	434	DEBUG(network->ctx, "Dumping network at %p\n", network);
	435
	436	char* s = loc_network_str(network);
	437	if (!s)
	438	return 1;
	439
	440	INFO(network->ctx, "%s\n", s);
	441	free(s);
	442
	443	return 0;
	444	}
	445
	446	LOC_EXPORT int loc_network_tree_dump(struct loc_network_tree* tree) {
	447	DEBUG(tree->ctx, "Dumping network tree at %p\n", tree);
	448
f3e02bc5	449	return loc_network_tree_walk(tree, NULL, __loc_network_tree_dump, NULL);
3b5f4af2 MT	450	}
	451
	452	LOC_EXPORT int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_network* network) {
	453	DEBUG(tree->ctx, "Adding network %p to tree %p\n", network, tree);
	454
	455	struct loc_network_tree_node* node = loc_network_tree_get_path(tree, &network->start_address);
	456	if (!node) {
	457	ERROR(tree->ctx, "Could not find a node\n");
	458	return -ENOMEM;
	459	}
	460
	461	// Check if node has not been set before
	462	if (node->network) {
	463	DEBUG(tree->ctx, "There is already a network at this path\n");
	464	return 1;
	465	}
	466
	467	// Point node to the network
	468	node->network = loc_network_ref(network);
	469
	470	return 0;
	471	}
f3e02bc5 MT	472
	473	static int __loc_network_tree_count(struct loc_network* network, void* data) {
	474	size_t* counter = (size_t*)data;
	475
	476	// Increase the counter for each network
	477	counter++;
	478
	479	return 0;
	480	}
	481
	482	LOC_EXPORT size_t loc_network_tree_count_networks(struct loc_network_tree* tree) {
	483	size_t counter = 0;
	484
	485	int r = loc_network_tree_walk(tree, NULL, __loc_network_tree_count, &counter);
	486	if (r)
	487	return r;
	488
	489	return counter;
	490	}