LOC_EXPORT int loc_network_new(struct loc_ctx* ctx, struct loc_network** network,
struct in6_addr* address, unsigned int prefix) {
+ struct loc_network* n = NULL;
+
// Validate the prefix
if (!loc_address_valid_prefix(address, prefix)) {
ERROR(ctx, "Invalid prefix in %s: %u\n", loc_address_str(address), prefix);
return 1;
}
- struct loc_network* n = calloc(1, sizeof(*n));
+ // Allocate a new network
+ n = calloc(1, sizeof(*n));
if (!n)
return 1;
n->prefix = prefix;
// Convert the prefix into a bitmask
- struct in6_addr bitmask = loc_prefix_to_bitmask(n->prefix);
+ const 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);
return 0;
}
+unsigned int loc_network_raw_prefix(struct loc_network* network) {
+ return network->prefix;
+}
+
LOC_EXPORT const struct in6_addr* loc_network_get_first_address(struct loc_network* network) {
return &network->first_address;
}
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;
const unsigned int prefix = loc_network_prefix(n1);
// How many bits do we need to represent this address?
- const size_t bitlength = loc_address_bit_length(&n1->first_address) - 1;
+ const size_t bitlength = loc_address_bit_length(&n1->first_address);
// We cannot shorten this any more
- if (bitlength < prefix)
+ if (bitlength >= prefix) {
+ DEBUG(n1->ctx, "Cannot shorten this any further because we need at least %jd bits,"
+ " but only have %d\n", bitlength, prefix);
+
return 0;
+ }
// Increment the last address of the first network
address = n1->last_address;
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) {
+static char* loc_network_reverse_pointer6(struct loc_network* network, const char* suffix) {
+ char* buffer = NULL;
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);
+ unsigned int prefix = loc_network_prefix(network);
- 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;
+ // Must border on a nibble
+ if (prefix % 4) {
+ errno = ENOTSUP;
+ return NULL;
}
- // 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;
+ if (!suffix)
+ suffix = "ip6.arpa.";
- 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;
- }
+ // Initialize the buffer
+ r = asprintf(&buffer, "%s", suffix);
+ if (r < 0)
+ goto ERROR;
- // Drop the network
- if (node->network) {
- loc_network_unref(node->network);
- node->network = NULL;
+ for (unsigned int i = 0; i < (prefix / 4); i++) {
+ r = asprintf(&buffer, "%x.%s", loc_address_get_nibble(&network->first_address, i), buffer);
+ if (r < 0)
+ goto ERROR;
}
- // 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)
+ // Add the asterisk
+ if (prefix < 128) {
+ r = asprintf(&buffer, "*.%s", buffer);
+ if (r < 0)
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);
+ return buffer;
ERROR:
- if (m)
- loc_network_unref(m);
- if (n)
- loc_network_unref(n);
+ if (buffer)
+ free(buffer);
- return r;
+ return NULL;
}
-static int loc_network_tree_merge(struct loc_network_tree* tree) {
- struct loc_network_tree_merge_ctx ctx = {
- .tree = tree,
- .networks = NULL,
- .merged = 0,
- };
+static char* loc_network_reverse_pointer4(struct loc_network* network, const char* suffix) {
+ char* buffer = NULL;
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;
-}
+ unsigned int prefix = loc_network_prefix(network);
-/*
- Deduplicate the tree
-*/
-
-struct loc_network_tree_dedup_ctx {
- struct loc_network_tree* tree;
- struct loc_network* network;
- 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;
-
- // First call when we have not seen any networks, yet
- if (!ctx->network) {
- ctx->network = loc_network_ref(network);
- return 0;
- }
-
- // If network is a subnet of ctx->network, and all properties match,
- // we can drop the network.
- if (loc_network_is_subnet(ctx->network, network)) {
- if (loc_network_properties_cmp(ctx->network, network) == 0) {
- // Increment counter
- ctx->removed++;
-
- // Remove the network
- return loc_network_tree_delete_network(ctx->tree, network);
- }
-
- return 0;
+ // Must border on an octet
+ if (prefix % 8) {
+ errno = ENOTSUP;
+ return NULL;
}
- // Drop the reference to the previous network
- if (ctx->network)
- loc_network_unref(ctx->network);
- ctx->network = loc_network_ref(network);
-
- return 0;
-}
-
-static int loc_network_tree_dedup(struct loc_network_tree* tree) {
- struct loc_network_tree_dedup_ctx ctx = {
- .tree = tree,
- .network = NULL,
- .removed = 0,
- };
- int r;
+ if (!suffix)
+ suffix = "in-addr.arpa.";
- // Walk through the entire tree
- r = loc_network_tree_walk(tree, NULL, loc_network_tree_dedup_step, &ctx);
- if (r)
- goto ERROR;
+ switch (prefix) {
+ case 32:
+ r = asprintf(&buffer, "%d.%d.%d.%d.%s",
+ loc_address_get_octet(&network->first_address, 3),
+ loc_address_get_octet(&network->first_address, 2),
+ loc_address_get_octet(&network->first_address, 1),
+ loc_address_get_octet(&network->first_address, 0),
+ suffix);
+ break;
- DEBUG(tree->ctx, "%u network(s) have been removed\n", ctx.removed);
+ case 24:
+ r = asprintf(&buffer, "*.%d.%d.%d.%s",
+ loc_address_get_octet(&network->first_address, 2),
+ loc_address_get_octet(&network->first_address, 1),
+ loc_address_get_octet(&network->first_address, 0),
+ suffix);
+ break;
-ERROR:
- if (ctx.network)
- loc_network_unref(ctx.network);
+ case 16:
+ r = asprintf(&buffer, "*.%d.%d.%s",
+ loc_address_get_octet(&network->first_address, 1),
+ loc_address_get_octet(&network->first_address, 0),
+ suffix);
+ break;
- return r;
-}
+ case 8:
+ r = asprintf(&buffer, "*.%d.%s",
+ loc_address_get_octet(&network->first_address, 0),
+ suffix);
+ break;
-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;
- }
+ case 0:
+ r = asprintf(&buffer, "*.%s", suffix);
+ break;
- // Delete one
- if (n->one) {
- r1 = loc_network_tree_delete_node(tree, &n->one);
- if (r1 < 0)
- return r1;
+ // To make the compiler happy
+ default:
+ return NULL;
}
- // 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 NULL;
- return 0;
+ return buffer;
}
-int loc_network_tree_cleanup(struct loc_network_tree* tree) {
- int r;
+LOC_EXPORT char* loc_network_reverse_pointer(struct loc_network* network, const char* suffix) {
+ switch (network->family) {
+ case AF_INET6:
+ return loc_network_reverse_pointer6(network, suffix);
- // Deduplicate the tree
- r = loc_network_tree_dedup(tree);
- if (r)
- return r;
+ case AF_INET:
+ return loc_network_reverse_pointer4(network, suffix);
- // Merge networks
- r = loc_network_tree_merge(tree);
- if (r) {
- ERROR(tree->ctx, "Could not merge networks: %m\n");
- return r;
+ default:
+ break;
}
- // Delete any unneeded nodes
- r = loc_network_tree_delete_nodes(tree);
- if (r)
- return r;
-
- return 0;
+ return NULL;
}
projects / people / ms / libloc.git / blobdiff