};
struct loc_network_tree_node {
+ struct loc_ctx* ctx;
+ int refcount;
+
struct loc_network_tree_node* zero;
struct loc_network_tree_node* one;
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;
+LOC_EXPORT 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) {
// 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 __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 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) {
+ 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;
+}
+
+LOC_EXPORT 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);
+}
+
+LOC_EXPORT 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;
+}
+
+LOC_EXPORT 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);
+}
+
+LOC_EXPORT 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) {
+ return loc_network_ref(node->network);
+}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
+#include <sys/queue.h>
#include <time.h>
#include <loc/libloc.h>
return 0;
}
-static int loc_database_write_network_section(struct loc_network* network, void* data) {
- FILE* f = (FILE*)data;
+struct node {
+ TAILQ_ENTRY(node) nodes;
- struct loc_database_network_v0 n;
+ struct loc_network_tree_node* node;
- int r = loc_network_to_database_v0(network, &n);
- if (r)
- return r;
+ // Indices of the child nodes
+ uint32_t index_zero;
+ uint32_t index_one;
+};
- fwrite(&n, 1, sizeof(n), f);
+static struct node* make_node(struct loc_network_tree_node* node) {
+ struct node* n = malloc(sizeof(*n));
+ if (!n)
+ return NULL;
- return 0;
+ n->node = loc_network_tree_node_ref(node);
+ n->index_zero = n->index_one = 0;
+
+ return n;
+}
+
+static void free_node(struct node* node) {
+ loc_network_tree_node_unref(node->node);
+
+ free(node);
+}
+
+struct network {
+ TAILQ_ENTRY(network) networks;
+
+ struct loc_network* network;
+};
+
+static struct network* make_network(struct loc_network* network) {
+ struct network* n = malloc(sizeof(*n));
+ if (!n)
+ return NULL;
+
+ n->network = loc_network_ref(network);
+
+ return n;
}
-static int loc_database_write_networks_section(struct loc_writer* writer,
+static void free_network(struct network* network) {
+ loc_network_unref(network->network);
+
+ free(network);
+}
+
+static int loc_database_write_networks(struct loc_writer* writer,
struct loc_database_header_v0* header, off_t* offset, FILE* f) {
- DEBUG(writer->ctx, "Networks section starts at %jd bytes\n", *offset);
- header->networks_offset = htobe32(*offset);
+ // Write the network tree
+ DEBUG(writer->ctx, "Network tree starts at %jd bytes\n", *offset);
+ header->network_tree_offset = htobe32(*offset);
- size_t networks_length = sizeof(struct loc_database_network_v0)
- * loc_network_tree_count_networks(writer->networks);
- offset += networks_length;
+ size_t network_tree_length = 0;
+ size_t network_data_length = 0;
- int r = loc_network_tree_walk(writer->networks, NULL, loc_database_write_network_section, f);
- if (r)
- return r;
+ struct node* node;
+ struct node* child_node;
+
+ uint32_t index = 0;
+ uint32_t network_index = 0;
+
+ struct loc_database_network_v0 db_network;
+ struct loc_database_network_node_v0 db_node;
+
+ // Initialize queue for nodes
+ TAILQ_HEAD(node_t, node) nodes;
+ TAILQ_INIT(&nodes);
+
+ // Initialize queue for networks
+ TAILQ_HEAD(network_t, network) networks;
+ TAILQ_INIT(&networks);
+
+ // Add root
+ struct loc_network_tree_node* root = loc_network_tree_get_root(writer->networks);
+ node = make_node(root);
+
+ TAILQ_INSERT_TAIL(&nodes, node, nodes);
+
+ while (!TAILQ_EMPTY(&nodes)) {
+ // Pop first node in list
+ node = TAILQ_FIRST(&nodes);
+ TAILQ_REMOVE(&nodes, node, nodes);
+
+ DEBUG(writer->ctx, "Processing node %p\n", node);
+
+ // Get child nodes
+ struct loc_network_tree_node* node_zero = loc_network_tree_node_get(node->node, 0);
+ if (node_zero) {
+ node->index_zero = ++index;
+
+ child_node = make_node(node_zero);
+ loc_network_tree_node_unref(node_zero);
+
+ TAILQ_INSERT_TAIL(&nodes, child_node, nodes);
+ }
+
+ struct loc_network_tree_node* node_one = loc_network_tree_node_get(node->node, 1);
+ if (node_one) {
+ node->index_one = ++index;
+
+ child_node = make_node(node_one);
+ loc_network_tree_node_unref(node_one);
+
+ TAILQ_INSERT_TAIL(&nodes, child_node, nodes);
+ }
+
+ // Prepare what we are writing to disk
+ if (loc_network_tree_node_is_leaf(node->node)) {
+ struct loc_network* network = loc_network_tree_node_get_network(node->node);
+
+ // Append network to be written out later
+ struct network* nw = make_network(network);
+ TAILQ_INSERT_TAIL(&networks, nw, networks);
+
+ db_node.zero = htobe32(0xffffffff);
+ db_node.one = htobe32(network_index++);
+
+ loc_network_unref(network);
+ } else {
+ db_node.zero = htobe32(node->index_zero);
+ db_node.one = htobe32(node->index_one);
+ }
+
+ // Write the current node
+ DEBUG(writer->ctx, "Writing node %p (0 = %d, 1 = %d)\n",
+ node, node->index_zero, node->index_one);
+
+ *offset += fwrite(&db_node, 1, sizeof(db_node), f);
+ network_tree_length += sizeof(db_node);
+
+ free_node(node);
+ }
+
+ loc_network_tree_node_unref(root);
+
+ header->network_tree_length = htobe32(network_tree_length);
+
+ align_page_boundary(offset, f);
+
+ DEBUG(writer->ctx, "Networks data section starts at %jd bytes\n", *offset);
+ header->network_data_offset = htobe32(*offset);
+
+ // We have now written the entire tree and have all networks
+ // in a queue in order as they are indexed
+ while (!TAILQ_EMPTY(&networks)) {
+ struct network* nw = TAILQ_FIRST(&networks);
+ TAILQ_REMOVE(&networks, nw, networks);
+
+ // Prepare what we are writing to disk
+ int r = loc_network_to_database_v0(nw->network, &db_network);
+ if (r)
+ return r;
+
+ *offset += fwrite(&db_network, 1, sizeof(db_network), f);
+ network_data_length += sizeof(db_network);
+
+ free_network(nw);
+ }
- header->networks_length = htobe32(networks_length);
+ header->network_data_length = htobe32(network_data_length);
return 0;
}
align_page_boundary(&offset, f);
// Write all networks
- r = loc_database_write_networks_section(writer, &header, &offset, f);
+ r = loc_database_write_networks(writer, &header, &offset, f);
if (r)
return r;
projects / people / ms / libloc.git / commitdiff
