From 438db08c95a9fcd9ec0d09ac35a260bd484ff1a5 Mon Sep 17 00:00:00 2001 From: Michael Tremer Date: Sun, 7 Jan 2018 13:32:51 +0000 Subject: [PATCH] writer: Write out the network tree Signed-off-by: Michael Tremer --- src/loc/format.h | 8 ++- src/loc/network.h | 10 +++ src/network.c | 106 +++++++++++++++++++++------- src/writer.c | 174 +++++++++++++++++++++++++++++++++++++++++----- 4 files changed, 252 insertions(+), 46 deletions(-) diff --git a/src/loc/format.h b/src/loc/format.h index 1f36aae..a1c0ebd 100644 --- a/src/loc/format.h +++ b/src/loc/format.h @@ -46,8 +46,12 @@ struct loc_database_header_v0 { uint32_t as_length; // Tells us where the networks start - uint32_t networks_offset; - uint32_t networks_length; + uint32_t network_data_offset; + uint32_t network_data_length; + + // Tells us where the network tree starts + uint32_t network_tree_offset; + uint32_t network_tree_length; // Tells us where the pool starts uint32_t pool_offset; diff --git a/src/loc/network.h b/src/loc/network.h index 71e31c1..05e2650 100644 --- a/src/loc/network.h +++ b/src/loc/network.h @@ -42,6 +42,7 @@ int loc_network_to_database_v0(struct loc_network* network, struct loc_database_ struct loc_network_tree; int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree); struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree); +struct loc_network_tree_node* loc_network_tree_get_root(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); @@ -50,4 +51,13 @@ int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_netwo size_t loc_network_tree_count_networks(struct loc_network_tree* tree); size_t loc_network_tree_count_nodes(struct loc_network_tree* tree); +struct loc_network_tree_node; +int loc_network_tree_node_new(struct loc_ctx* ctx, struct loc_network_tree_node** node); +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_unref(struct loc_network_tree_node* node); +struct loc_network_tree_node* loc_network_tree_node_get(struct loc_network_tree_node* node, unsigned int index); + +int loc_network_tree_node_is_leaf(struct loc_network_tree_node* node); +struct loc_network* loc_network_tree_node_get_network(struct loc_network_tree_node* node); + #endif diff --git a/src/network.c b/src/network.c index 296a354..9bba222 100644 --- a/src/network.c +++ b/src/network.c @@ -332,6 +332,9 @@ struct loc_network_tree { }; struct loc_network_tree_node { + struct loc_ctx* ctx; + int refcount; + struct loc_network_tree_node* zero; struct loc_network_tree_node* one; @@ -347,22 +350,19 @@ LOC_EXPORT int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree 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) { @@ -375,7 +375,7 @@ static struct loc_network_tree_node* loc_network_tree_get_node(struct loc_networ // 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; } @@ -439,23 +439,10 @@ LOC_EXPORT int loc_network_tree_walk(struct loc_network_tree* tree, 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); @@ -543,3 +530,72 @@ static size_t __loc_network_tree_count_nodes(struct loc_network_tree_node* node) 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); +} diff --git a/src/writer.c b/src/writer.c index 44b783a..84331d0 100644 --- a/src/writer.c +++ b/src/writer.c @@ -19,6 +19,7 @@ #include #include #include +#include #include #include @@ -221,34 +222,169 @@ static int loc_database_write_as_section(struct loc_writer* writer, 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; } @@ -294,7 +430,7 @@ LOC_EXPORT int loc_writer_write(struct loc_writer* writer, FILE* f) { 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; -- 2.39.2