return 0;
}
-static int loc_network_properties_cmp(struct loc_network* self, struct loc_network* other) {
+int loc_network_properties_cmp(struct loc_network* self, struct loc_network* other) {
int r;
// Check country code
return subnets;
}
-static int loc_network_merge(struct loc_network** n,
+int loc_network_merge(struct loc_network** n,
struct loc_network* n1, struct loc_network* n2) {
struct loc_network* network = NULL;
struct in6_addr address;
// Reset pointer
*n = NULL;
+ DEBUG(n1->ctx, "Attempting to merge %s and %s\n", loc_network_str(n1), loc_network_str(n2));
+
// Family must match
if (n1->family != n2->family)
return 0;
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_ctx* ctx;
- int refcount;
-
- struct loc_network_tree_node* zero;
- struct loc_network_tree_node* one;
-
- struct loc_network* network;
-
- // Set if deleted
- int deleted:1;
-};
-
-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 1;
-
- t->ctx = loc_ref(ctx);
- t->refcount = 1;
-
- // Create the root node
- 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;
-}
-
-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 = NULL;
- int r;
-
- switch (path) {
- case 0:
- n = &node->zero;
- break;
-
- case 1:
- n = &node->one;
- break;
-
- default:
- errno = EINVAL;
- return NULL;
- }
-
- // If the node existed, but has been deleted, we undelete it
- if (*n && (*n)->deleted) {
- (*n)->deleted = 0;
-
- // If the desired node doesn't exist, yet, we will create it
- } else if (!*n) {
- 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, unsigned int prefix) {
- struct loc_network_tree_node* node = tree->root;
-
- for (unsigned int i = 0; i < prefix; i++) {
- // Check if the ith bit is one or zero
- node = loc_network_tree_get_node(node, loc_address_get_bit(address, i));
- }
-
- 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;
-
- // If the node has been deleted, don't process it
- if (node->deleted)
- return 0;
-
- // 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;
-}
-
-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(struct loc_network_tree* tree) {
- DEBUG(tree->ctx, "Releasing network tree at %p\n", tree);
-
- loc_network_tree_node_unref(tree->root);
-
- loc_unref(tree->ctx);
- free(tree);
-}
-
-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;
-}
-
-static int __loc_network_tree_dump(struct loc_network* network, void* data) {
- DEBUG(network->ctx, "Dumping network at %p\n", network);
-
- const char* s = loc_network_str(network);
- if (!s)
- return 1;
-
- INFO(network->ctx, "%s\n", s);
-
- return 0;
-}
-
-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);
-}
-
-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->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: %s\n",
- loc_network_str(node->network));
- return -EBUSY;
- }
-
- // Point node to the network
- node->network = loc_network_ref(network);
-
- return 0;
-}
-
-static int loc_network_tree_delete_network(
- struct loc_network_tree* tree, struct loc_network* network) {
- struct loc_network_tree_node* node = NULL;
-
- DEBUG(tree->ctx, "Deleting network %s from tree...\n", loc_network_str(network));
-
- node = loc_network_tree_get_path(tree, &network->first_address, network->prefix);
- if (!node) {
- ERROR(tree->ctx, "Network was not found in tree %s\n", loc_network_str(network));
- return 1;
- }
-
- // Drop the network
- if (node->network) {
- loc_network_unref(node->network);
- node->network = NULL;
- }
-
- // Mark the node as deleted if it was a leaf
- if (!node->zero && !node->one)
- node->deleted = 1;
-
- return 0;
-}
-
-static size_t __loc_network_tree_count_nodes(struct loc_network_tree_node* node) {
- size_t counter = 1;
-
- // Don't count deleted nodes
- if (node->deleted)
- return 0;
-
- 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->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);
-}
-
-/*
- Merge the tree!
-*/
-
-struct loc_network_tree_merge_ctx {
- struct loc_network_tree* tree;
- struct loc_network_list* networks;
- unsigned int merged;
-};
-
-static int loc_network_tree_merge_step(struct loc_network* network, void* data) {
- struct loc_network_tree_merge_ctx* ctx = (struct loc_network_tree_merge_ctx*)data;
- struct loc_network* n = NULL;
- struct loc_network* m = NULL;
- int r;
-
- // How many networks do we have?
- size_t i = loc_network_list_size(ctx->networks);
-
- // If the list is empty, just add the network
- if (i == 0)
- return loc_network_list_push(ctx->networks, network);
-
- while (i--) {
- // Fetch the last network of the list
- n = loc_network_list_get(ctx->networks, i);
-
- // Try to merge the two networks
- r = loc_network_merge(&m, n, network);
- if (r)
- goto ERROR;
-
- // Did we get a result?
- if (m) {
- DEBUG(ctx->tree->ctx, "Merged networks %s + %s -> %s\n",
- loc_network_str(n), loc_network_str(network), loc_network_str(m));
-
- // Add the new network
- r = loc_network_tree_add_network(ctx->tree, m);
- switch (r) {
- case 0:
- break;
-
- // There might already be a network
- case -EBUSY:
- r = 0;
- goto ERROR;
-
- default:
- goto ERROR;
- }
-
- // Remove the merge networks
- r = loc_network_tree_delete_network(ctx->tree, network);
- if (r)
- goto ERROR;
-
- r = loc_network_tree_delete_network(ctx->tree, n);
- if (r)
- goto ERROR;
-
- // Add the new network to the stack
- r = loc_network_list_push(ctx->networks, m);
- if (r)
- goto ERROR;
-
- // Remove the previous network from the stack
- r = loc_network_list_remove(ctx->networks, n);
- if (r)
- goto ERROR;
-
- // Count merges
- ctx->merged++;
-
- // Try merging the new network with others
- r = loc_network_tree_merge_step(m, data);
- if (r)
- goto ERROR;
-
- loc_network_unref(m);
- m = NULL;
-
- // Once we have found a merge, we are done
- break;
-
- // If we could not merge the two networks, we add the current one
- } else {
- r = loc_network_list_push(ctx->networks, network);
- if (r)
- goto ERROR;
- }
-
- loc_network_unref(n);
- n = NULL;
- }
-
- const unsigned int prefix = loc_network_prefix(network);
-
- // Remove any networks that we cannot merge
- loc_network_list_remove_with_prefix_smaller_than(ctx->networks, prefix);
-
-ERROR:
- if (m)
- loc_network_unref(m);
- if (n)
- loc_network_unref(n);
-
- return r;
-}
-
-static int loc_network_tree_merge(struct loc_network_tree* tree) {
- struct loc_network_tree_merge_ctx ctx = {
- .tree = tree,
- .networks = NULL,
- .merged = 0,
- };
- int r;
-
- // Create a new list
- r = loc_network_list_new(tree->ctx, &ctx.networks);
- if (r)
- goto ERROR;
-
- // Walk through the entire tree
- r = loc_network_tree_walk(tree, NULL, loc_network_tree_merge_step, &ctx);
- if (r)
- goto ERROR;
-
- DEBUG(tree->ctx, "%u network(s) have been merged\n", ctx.merged);
-
-ERROR:
- if (ctx.networks)
- loc_network_list_unref(ctx.networks);
-
- return r;
-}
-
-/*
- Deduplicate the tree
-*/
-
-struct loc_network_tree_dedup_ctx {
- struct loc_network_tree* tree;
- struct loc_network_list* stack;
- unsigned int removed;
-};
-
-static int loc_network_tree_dedup_step(struct loc_network* network, void* data) {
- struct loc_network_tree_dedup_ctx* ctx = (struct loc_network_tree_dedup_ctx*)data;
- struct loc_network* n = NULL;
- int r;
-
- // First call when we have not seen any networks, yet
- if (loc_network_list_empty(ctx->stack))
- return loc_network_list_push(ctx->stack, network);
-
- const unsigned int prefix = loc_network_prefix(network);
-
- // Remove any networks that are not interesting
- loc_network_list_remove_with_prefix_smaller_than(ctx->stack, prefix);
-
- for (int i = loc_network_list_size(ctx->stack) - 1; i >= 0; i--) {
- n = loc_network_list_get(ctx->stack, i);
-
- // Is network a subnet?
- if (loc_network_is_subnet(n, network)) {
- // Do all properties match?
- if (loc_network_properties_cmp(n, network) == 0) {
- r = loc_network_tree_delete_network(ctx->tree, network);
- if (r)
- return r;
-
- // Count
- ctx->removed++;
-
- // Once we removed the subnet, we are done
- goto END;
- }
-
- // Once we found a subnet, we are done
- break;
- }
- }
-
- // If network did not get removed, we push it into the stack
- r = loc_network_list_push(ctx->stack, network);
- if (r)
- return r;
-
-END:
- if (n)
- loc_network_unref(n);
-
- return r;
-}
-
-static int loc_network_tree_dedup(struct loc_network_tree* tree) {
- struct loc_network_tree_dedup_ctx ctx = {
- .tree = tree,
- .stack = NULL,
- .removed = 0,
- };
- int r;
-
- r = loc_network_list_new(tree->ctx, &ctx.stack);
- if (r)
- return r;
-
- // Walk through the entire tree
- r = loc_network_tree_walk(tree, NULL, loc_network_tree_dedup_step, &ctx);
- if (r)
- goto ERROR;
-
- DEBUG(tree->ctx, "%u network(s) have been removed\n", ctx.removed);
-
-ERROR:
- if (ctx.stack)
- loc_network_list_unref(ctx.stack);
-
- return r;
-}
-
-static int loc_network_tree_delete_node(struct loc_network_tree* tree,
- struct loc_network_tree_node** node) {
- struct loc_network_tree_node* n = *node;
- int r0 = 1;
- int r1 = 1;
-
- // Return for nodes that have already been deleted
- if (n->deleted)
- goto DELETE;
-
- // Delete zero
- if (n->zero) {
- r0 = loc_network_tree_delete_node(tree, &n->zero);
- if (r0 < 0)
- return r0;
- }
-
- // Delete one
- if (n->one) {
- r1 = loc_network_tree_delete_node(tree, &n->one);
- if (r1 < 0)
- return r1;
- }
-
- // Don't delete this node if we are a leaf
- if (n->network)
- return 0;
-
- // Don't delete this node if has child nodes that we need
- if (!r0 || !r1)
- return 0;
-
- // Don't delete root
- if (tree->root == n)
- return 0;
-
-DELETE:
- // It is now safe to delete the node
- loc_network_tree_node_unref(n);
- *node = NULL;
-
- return 1;
-}
-
-static int loc_network_tree_delete_nodes(struct loc_network_tree* tree) {
- int r;
-
- r = loc_network_tree_delete_node(tree, &tree->root);
- if (r < 0)
- return r;
-
- return 0;
-}
-
-int loc_network_tree_cleanup(struct loc_network_tree* tree) {
- int r;
-
- // Deduplicate the tree
- r = loc_network_tree_dedup(tree);
- if (r)
- return r;
-
- // Merge networks
- r = loc_network_tree_merge(tree);
- if (r) {
- ERROR(tree->ctx, "Could not merge networks: %m\n");
- return r;
- }
-
- // Delete any unneeded nodes
- r = loc_network_tree_delete_nodes(tree);
- if (r)
- return r;
-
- return 0;
-}
projects / location / libloc.git / blobdiff