X-Git-Url: http://git.ipfire.org/?a=blobdiff_plain;f=src%2Fnetwork.c;h=0266ebf3edc0fd63e159b0faa9a785e87a2654f6;hb=5559e08681b0a78118d6ee1671213693625e4e0a;hp=6c08070830c9aa36cf5adecc3b5b59969d68cc58;hpb=850e75167e8e03fe8b951992c9f7bc2ccb9fb711;p=people%2Fms%2Flibloc.git diff --git a/src/network.c b/src/network.c index 6c08070..0266ebf 100644 --- a/src/network.c +++ b/src/network.c @@ -25,11 +25,12 @@ # include #endif -#include -#include -#include -#include -#include +#include +#include +#include +#include +#include +#include struct loc_network { struct loc_ctx* ctx; @@ -50,10 +51,6 @@ static int valid_prefix(struct in6_addr* address, unsigned int prefix) { if (prefix > 128) return 1; - // And the prefix cannot be zero - if (prefix == 0) - return 1; - // For IPv4-mapped addresses the prefix has to be 96 or lager if (IN6_IS_ADDR_V4MAPPED(address) && prefix <= 96) return 1; @@ -61,92 +58,20 @@ static int valid_prefix(struct in6_addr* address, unsigned int prefix) { return 0; } -static struct in6_addr prefix_to_bitmask(unsigned int prefix) { - struct in6_addr bitmask; - - for (unsigned int i = 0; i < 16; i++) - bitmask.s6_addr[i] = 0; - - for (int i = prefix, j = 0; i > 0; i -= 8, j++) { - if (i >= 8) - bitmask.s6_addr[j] = 0xff; - else - bitmask.s6_addr[j] = 0xff << (8 - i); - } - - return bitmask; -} - -static struct in6_addr make_first_address(const struct in6_addr* address, const struct in6_addr* bitmask) { - struct in6_addr a; - - // Perform bitwise AND - for (unsigned int i = 0; i < 4; i++) - a.s6_addr32[i] = address->s6_addr32[i] & bitmask->s6_addr32[i]; - - return a; -} - -static struct in6_addr make_last_address(const struct in6_addr* address, const struct in6_addr* bitmask) { - struct in6_addr a; - - // Perform bitwise OR - for (unsigned int i = 0; i < 4; i++) - a.s6_addr32[i] = address->s6_addr32[i] | ~bitmask->s6_addr32[i]; - - return a; -} - -static struct in6_addr address_increment(const struct in6_addr* address) { - struct in6_addr a = *address; - - for (int octet = 15; octet >= 0; octet--) { - if (a.s6_addr[octet] < 255) { - a.s6_addr[octet]++; - break; - } else { - a.s6_addr[octet] = 0; - } - } - - return a; -} - LOC_EXPORT int loc_network_new(struct loc_ctx* ctx, struct loc_network** network, struct in6_addr* address, unsigned int prefix) { - // Address cannot be unspecified - if (IN6_IS_ADDR_UNSPECIFIED(address)) { - DEBUG(ctx, "Start address is unspecified\n"); - return -EINVAL; - } - - // Address cannot be loopback - if (IN6_IS_ADDR_LOOPBACK(address)) { - DEBUG(ctx, "Start address is loopback address\n"); - return -EINVAL; - } - - // Address cannot be link-local - if (IN6_IS_ADDR_LINKLOCAL(address)) { - DEBUG(ctx, "Start address cannot be link-local\n"); - return -EINVAL; - } - - // Address cannot be site-local - if (IN6_IS_ADDR_SITELOCAL(address)) { - DEBUG(ctx, "Start address cannot be site-local\n"); - return -EINVAL; - } - // Validate the prefix if (valid_prefix(address, prefix) != 0) { - DEBUG(ctx, "Invalid prefix: %u\n", prefix); - return -EINVAL; + ERROR(ctx, "Invalid prefix: %u\n", prefix); + errno = EINVAL; + return 1; } struct loc_network* n = calloc(1, sizeof(*n)); - if (!n) - return -ENOMEM; + if (!n) { + errno = ENOMEM; + return 1; + } n->ctx = loc_ref(ctx); n->refcount = 1; @@ -155,17 +80,14 @@ LOC_EXPORT int loc_network_new(struct loc_ctx* ctx, struct loc_network** network n->prefix = prefix; // Convert the prefix into a bitmask - struct in6_addr bitmask = prefix_to_bitmask(n->prefix); + struct in6_addr bitmask = loc_prefix_to_bitmask(n->prefix); // Store the first and last address in the network - n->first_address = make_first_address(address, &bitmask); - n->last_address = make_last_address(&n->first_address, &bitmask); + n->first_address = loc_address_and(address, &bitmask); + n->last_address = loc_address_or(&n->first_address, &bitmask); // Set family - if (IN6_IS_ADDR_V4MAPPED(&n->first_address)) - n->family = AF_INET; - else - n->family = AF_INET6; + n->family = loc_address_family(&n->first_address); DEBUG(n->ctx, "Network allocated at %p\n", n); *network = n; @@ -309,6 +231,18 @@ LOC_EXPORT int loc_network_address_family(struct loc_network* network) { return network->family; } +LOC_EXPORT unsigned int loc_network_prefix(struct loc_network* network) { + switch (network->family) { + case AF_INET6: + return network->prefix; + + case AF_INET: + return network->prefix - 96; + } + + return 0; +} + static char* loc_network_format_address(struct loc_network* network, const struct in6_addr* address) { const size_t length = INET6_ADDRSTRLEN; @@ -342,25 +276,33 @@ static char* loc_network_format_address(struct loc_network* network, const struc return string; } +LOC_EXPORT const struct in6_addr* loc_network_get_first_address(struct loc_network* network) { + return &network->first_address; +} + LOC_EXPORT char* loc_network_format_first_address(struct loc_network* network) { return loc_network_format_address(network, &network->first_address); } +LOC_EXPORT const struct in6_addr* loc_network_get_last_address(struct loc_network* network) { + return &network->last_address; +} + LOC_EXPORT char* loc_network_format_last_address(struct loc_network* network) { return loc_network_format_address(network, &network->last_address); } -LOC_EXPORT int loc_network_match_address(struct loc_network* network, const struct in6_addr* address) { +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 (in6_addr_cmp(&network->first_address, address) > 0) - return 1; + return 0; // Address must be smaller than the last address if (in6_addr_cmp(&network->last_address, address) < 0) - return 1; + return 0; // The address is inside this network - return 0; + return 1; } LOC_EXPORT const char* loc_network_get_country_code(struct loc_network* network) { @@ -383,11 +325,19 @@ LOC_EXPORT int loc_network_set_country_code(struct loc_network* network, const c return 0; } -LOC_EXPORT int loc_network_match_country_code(struct loc_network* network, const char* country_code) { +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); + + // 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]); } @@ -402,10 +352,6 @@ LOC_EXPORT int loc_network_set_asn(struct loc_network* network, uint32_t asn) { return 0; } -LOC_EXPORT int loc_network_match_asn(struct loc_network* network, uint32_t asn) { - return network->asn == asn; -} - LOC_EXPORT int loc_network_has_flag(struct loc_network* network, uint32_t flag) { return network->flags & flag; } @@ -416,133 +362,147 @@ LOC_EXPORT int loc_network_set_flag(struct loc_network* network, uint32_t flag) return 0; } -LOC_EXPORT int loc_network_match_flag(struct loc_network* network, uint32_t flag) { - return loc_network_has_flag(network, flag); -} - -LOC_EXPORT int loc_network_eq(struct loc_network* self, struct loc_network* other) { -#ifdef ENABLE_DEBUG - char* n1 = loc_network_str(self); - char* n2 = loc_network_str(other); - - DEBUG(self->ctx, "Is %s equal to %s?\n", n1, n2); - - free(n1); - free(n2); -#endif - - // Family must be the same - if (self->family != other->family) { - DEBUG(self->ctx, " Family mismatch\n"); - - return 0; - } - - // The start address must be the same - if (in6_addr_cmp(&self->first_address, &other->first_address) != 0) { - DEBUG(self->ctx, " Address mismatch\n"); - - return 0; - } - - // The prefix length must be the same - if (self->prefix != other->prefix) { - DEBUG(self->ctx, " Prefix mismatch\n"); - return 0; - } - - DEBUG(self->ctx, " Yes!\n"); - - return 1; -} +LOC_EXPORT int loc_network_cmp(struct loc_network* self, struct loc_network* other) { + // Compare address + int r = in6_addr_cmp(&self->first_address, &other->first_address); + if (r) + return r; -static int loc_network_gt(struct loc_network* self, struct loc_network* other) { - // Families must match - if (self->family != other->family) + // Compare prefix + if (self->prefix > other->prefix) + return 1; + else if (self->prefix < other->prefix) return -1; - int r = in6_addr_cmp(&self->first_address, &other->first_address); + // Both networks are equal + return 0; +} - switch (r) { - // Smaller - case -1: - return 0; +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; - // Larger - case 1: - return 1; + if (loc_network_matches_address(other, &self->first_address)) + return 1; - default: - break; - } + // Or either of the end addresses is in the other subnet + if (loc_network_matches_address(self, &other->last_address)) + return 1; - if (self->prefix > other->prefix) + if (loc_network_matches_address(other, &self->last_address)) return 1; - // Dunno return 0; } -LOC_EXPORT int loc_network_is_subnet_of(struct loc_network* self, struct loc_network* other) { +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 (in6_addr_cmp(&self->first_address, &other->first_address) < 0) + if (in6_addr_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 (in6_addr_cmp(&self->last_address, &other->last_address) > 0) + if (in6_addr_cmp(&self->last_address, &other->last_address) < 0) return 0; return 1; } -LOC_EXPORT struct loc_network_list* loc_network_subnets(struct loc_network* network) { - struct loc_network_list* list; +LOC_EXPORT int loc_network_subnets(struct loc_network* network, + struct loc_network** subnet1, struct loc_network** subnet2) { + int r; + *subnet1 = NULL; + *subnet2 = NULL; // New prefix length unsigned int prefix = network->prefix + 1; // Check if the new prefix is valid if (valid_prefix(&network->first_address, prefix)) - return NULL; - - // Create a new list with the result - int r = loc_network_list_new(network->ctx, &list); - if (r) { - ERROR(network->ctx, "Could not create network list: %d\n", r); - return NULL; - } - - struct loc_network* subnet1 = NULL; - struct loc_network* subnet2 = NULL; + return -1; // Create the first half of the network - r = loc_network_new(network->ctx, &subnet1, &network->first_address, prefix); + r = loc_network_new(network->ctx, subnet1, &network->first_address, prefix); if (r) - goto ERROR; + return r; // The next subnet starts after the first one - struct in6_addr first_address = address_increment(&subnet1->last_address); + struct in6_addr first_address = address_increment(&(*subnet1)->last_address); // Create the second half of the network - r = loc_network_new(network->ctx, &subnet2, &first_address, prefix); + r = loc_network_new(network->ctx, subnet2, &first_address, prefix); if (r) - goto ERROR; + return r; - // Push the both onto the stack (in reverse order) - r = loc_network_list_push(list, subnet2); - if (r) - goto ERROR; + // 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); + } + + // Copy ASN + uint32_t asn = loc_network_get_asn(network); + if (asn) { + loc_network_set_asn(*subnet1, asn); + loc_network_set_asn(*subnet2, asn); + } - r = loc_network_list_push(list, subnet1); + // 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; - loc_network_unref(subnet1); - loc_network_unref(subnet2); + 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; - return list; + } 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; + } ERROR: if (subnet1) @@ -551,10 +511,28 @@ ERROR: if (subnet2) loc_network_unref(subnet2); - if (list) - loc_network_list_unref(list); + return r; +} - return NULL; +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 struct loc_network_list* loc_network_exclude( @@ -571,102 +549,124 @@ LOC_EXPORT struct loc_network_list* loc_network_exclude( free(n2); #endif - // Family must match - if (self->family != other->family) { - DEBUG(self->ctx, "Family mismatch\n"); + // 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); return NULL; } - // Other must be a subnet of self - if (!loc_network_is_subnet_of(other, self)) { - DEBUG(self->ctx, "Network %p is not contained in network %p\n", other, self); + r = __loc_network_exclude_to_list(self, other, list); + if (r) { + loc_network_list_unref(list); return NULL; } - // We cannot perform this operation if both networks equal - if (loc_network_eq(self, other)) { - DEBUG(self->ctx, "Networks %p and %p are equal\n", self, other); + // Return the result + return list; +} +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); } - // Create a new list with the result - int r = loc_network_list_new(self->ctx, &list); + r = loc_network_list_new(network->ctx, &subnets); if (r) { - ERROR(self->ctx, "Could not create network list: %d\n", r); + loc_network_list_unref(to_check); return NULL; } - struct loc_network_list* subnets = loc_network_subnets(self); + off_t smallest_subnet = 0; - struct loc_network* subnet1 = NULL; - struct loc_network* subnet2 = NULL; + while (!loc_network_list_empty(to_check)) { + struct loc_network* subnet_to_check = loc_network_list_pop_first(to_check); - while (subnets) { - // Fetch both subnets - subnet1 = loc_network_list_get(subnets, 0); - subnet2 = loc_network_list_get(subnets, 1); + // 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; - // Free list - loc_network_list_unref(subnets); - subnets = NULL; + for (unsigned int i = smallest_subnet; i < loc_network_list_size(list); i++) { + subnet = loc_network_list_get(list, i); - if (loc_network_eq(other, subnet1)) { - r = loc_network_list_push(list, subnet2); - if (r) - goto ERROR; + // 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; + } - } else if (loc_network_eq(other, subnet2)) { - r = loc_network_list_push(list, subnet1); - if (r) - goto ERROR; + // Break it down if it overlaps + if (loc_network_overlaps(subnet, subnet_to_check)) { + passed = 0; - } else if (loc_network_is_subnet_of(other, subnet1)) { - r = loc_network_list_push(list, subnet2); - if (r) - goto ERROR; + __loc_network_exclude_to_list(subnet_to_check, subnet, to_check); - subnets = loc_network_subnets(subnet1); + loc_network_unref(subnet); + break; + } - } else if (loc_network_is_subnet_of(other, subnet2)) { - r = loc_network_list_push(list, subnet1); - if (r) - goto ERROR; + // 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; + } - subnets = loc_network_subnets(subnet2); + loc_network_unref(subnet); + } - } else { - ERROR(self->ctx, "We should never get here\n"); - goto ERROR; + if (passed) { + r = loc_network_list_push(subnets, subnet_to_check); } - loc_network_unref(subnet1); - loc_network_unref(subnet2); + loc_network_unref(subnet_to_check); } -#ifdef ENABLE_DEBUG - loc_network_list_dump(list); -#endif - - // Return the result - return list; - -ERROR: - if (subnet1) - loc_network_unref(subnet1); - - if (subnet2) - loc_network_unref(subnet2); - - if (list) - loc_network_list_unref(list); + loc_network_list_unref(to_check); - return NULL; + return subnets; } -LOC_EXPORT int loc_network_to_database_v1(struct loc_network* network, struct loc_database_network_v1* dbobj) { +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); @@ -679,7 +679,7 @@ LOC_EXPORT int loc_network_to_database_v1(struct loc_network* network, struct lo return 0; } -LOC_EXPORT int loc_network_new_from_database_v1(struct loc_ctx* ctx, struct loc_network** network, +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"; @@ -734,7 +734,7 @@ struct loc_network_tree_node { 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; @@ -754,7 +754,7 @@ LOC_EXPORT int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree return 0; } -LOC_EXPORT struct loc_network_tree_node* loc_network_tree_get_root(struct loc_network_tree* tree) { +struct loc_network_tree_node* loc_network_tree_get_root(struct loc_network_tree* tree) { return loc_network_tree_node_ref(tree->root); } @@ -826,7 +826,7 @@ static int __loc_network_tree_walk(struct loc_ctx* ctx, struct loc_network_tree_ 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); @@ -841,7 +841,7 @@ static void loc_network_tree_free(struct loc_network_tree* tree) { 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; @@ -862,13 +862,13 @@ static int __loc_network_tree_dump(struct loc_network* network, void* data) { 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, @@ -899,7 +899,7 @@ static int __loc_network_tree_count(struct loc_network* network, void* data) { 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); @@ -921,11 +921,11 @@ static size_t __loc_network_tree_count_nodes(struct loc_network_tree_node* node) return counter; } -LOC_EXPORT size_t loc_network_tree_count_nodes(struct loc_network_tree* tree) { +size_t loc_network_tree_count_nodes(struct loc_network_tree* tree) { return __loc_network_tree_count_nodes(tree->root); } -LOC_EXPORT int loc_network_tree_node_new(struct loc_ctx* ctx, struct loc_network_tree_node** node) { +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; @@ -940,7 +940,7 @@ LOC_EXPORT int loc_network_tree_node_new(struct loc_ctx* ctx, struct loc_network return 0; } -LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_ref(struct loc_network_tree_node* node) { +struct loc_network_tree_node* loc_network_tree_node_ref(struct loc_network_tree_node* node) { if (node) node->refcount++; @@ -963,7 +963,7 @@ static void loc_network_tree_node_free(struct loc_network_tree_node* node) { free(node); } -LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_unref(struct loc_network_tree_node* node) { +struct loc_network_tree_node* loc_network_tree_node_unref(struct loc_network_tree_node* node) { if (!node) return NULL; @@ -974,7 +974,7 @@ LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_unref(struct loc_ return NULL; } -LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_get(struct loc_network_tree_node* node, unsigned int index) { +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 @@ -986,161 +986,10 @@ LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_get(struct loc_ne return loc_network_tree_node_ref(node); } -LOC_EXPORT int loc_network_tree_node_is_leaf(struct loc_network_tree_node* node) { +int loc_network_tree_node_is_leaf(struct loc_network_tree_node* node) { return (!!node->network); } -LOC_EXPORT struct loc_network* loc_network_tree_node_get_network(struct loc_network_tree_node* node) { +struct loc_network* loc_network_tree_node_get_network(struct loc_network_tree_node* node) { return loc_network_ref(node->network); } - -// List - -struct loc_network_list { - struct loc_ctx* ctx; - int refcount; - - struct loc_network* list[1024]; - size_t size; - size_t max_size; -}; - -LOC_EXPORT int loc_network_list_new(struct loc_ctx* ctx, - struct loc_network_list** list) { - struct loc_network_list* l = calloc(1, sizeof(*l)); - if (!l) - return -ENOMEM; - - l->ctx = loc_ref(ctx); - l->refcount = 1; - - // Do not allow this list to grow larger than this - l->max_size = 1024; - - DEBUG(l->ctx, "Network list allocated at %p\n", l); - *list = l; - return 0; -} - -LOC_EXPORT struct loc_network_list* loc_network_list_ref(struct loc_network_list* list) { - list->refcount++; - - return list; -} - -static void loc_network_list_free(struct loc_network_list* list) { - DEBUG(list->ctx, "Releasing network list at %p\n", list); - - for (unsigned int i = 0; i < list->size; i++) - loc_network_unref(list->list[i]); - - loc_unref(list->ctx); - free(list); -} - -LOC_EXPORT struct loc_network_list* loc_network_list_unref(struct loc_network_list* list) { - if (!list) - return NULL; - - if (--list->refcount > 0) - return list; - - loc_network_list_free(list); - return NULL; -} - -LOC_EXPORT size_t loc_network_list_size(struct loc_network_list* list) { - return list->size; -} - -LOC_EXPORT int loc_network_list_empty(struct loc_network_list* list) { - return list->size == 0; -} - -LOC_EXPORT void loc_network_list_clear(struct loc_network_list* list) { - for (unsigned int i = 0; i < list->size; i++) - loc_network_unref(list->list[i]); - - list->size = 0; -} - -LOC_EXPORT void loc_network_list_dump(struct loc_network_list* list) { - struct loc_network* network; - char* s; - - for (unsigned int i = 0; i < list->size; i++) { - network = list->list[i]; - - s = loc_network_str(network); - - INFO(list->ctx, "%s\n", s); - free(s); - } -} - -LOC_EXPORT struct loc_network* loc_network_list_get(struct loc_network_list* list, size_t index) { - // Check index - if (index >= list->size) - return NULL; - - return loc_network_ref(list->list[index]); -} - -LOC_EXPORT int loc_network_list_push(struct loc_network_list* list, struct loc_network* network) { - // Check if we have space left - if (list->size == list->max_size) - return -ENOMEM; - - list->list[list->size++] = loc_network_ref(network); - - return 0; -} - -LOC_EXPORT struct loc_network* loc_network_list_pop(struct loc_network_list* list) { - // Return nothing when empty - if (loc_network_list_empty(list)) - return NULL; - - return list->list[--list->size]; -} - -static void loc_network_list_swap(struct loc_network_list* list, unsigned int i1, unsigned int i2) { - // Do nothing for invalid indices - if (i1 >= list->size || i2 >= list->size) - return; - - DEBUG(list->ctx, "Swapping %u with %u\n", i1, i2); - - struct loc_network* network1 = list->list[i1]; - struct loc_network* network2 = list->list[i2]; - - list->list[i1] = network2; - list->list[i2] = network1; -} - -LOC_EXPORT void loc_network_list_reverse(struct loc_network_list* list) { - unsigned int i = 0; - unsigned int j = list->size - 1; - - while (i < j) { - loc_network_list_swap(list, i++, j--); - } -} - -LOC_EXPORT void loc_network_list_sort(struct loc_network_list* list) { - unsigned int n = list->size; - int swapped; - - do { - swapped = 0; - - for (unsigned int i = 1; i < n; i++) { - if (loc_network_gt(list->list[i-1], list->list[i]) > 0) { - loc_network_list_swap(list, i-1, i); - swapped = 1; - } - } - - n--; - } while (swapped); -}