From 01ce25ac77fb1d8109cb45796ad9b4da1f9e8349 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Sun, 28 Oct 2018 14:00:47 +0100 Subject: Add SerdNodes class for storing a cache of nodes --- serd/serd.h | 65 +++++++++++++++++++++++++ src/node.c | 2 +- src/node.h | 1 + src/nodes.c | 137 +++++++++++++++++++++++++++++++++++++++++++++++++++++ tests/nodes_test.c | 105 ++++++++++++++++++++++++++++++++++++++++ wscript | 12 +++-- 6 files changed, 318 insertions(+), 4 deletions(-) create mode 100644 src/nodes.c create mode 100644 tests/nodes_test.c diff --git a/serd/serd.h b/serd/serd.h index 0dc95d5e..444330f9 100644 --- a/serd/serd.h +++ b/serd/serd.h @@ -62,6 +62,14 @@ extern "C" { */ typedef struct SerdWorldImpl SerdWorld; +/** + Nodes. + + A hashing container for nodes that can be used for interning and simplified + memory management. +*/ +typedef struct SerdNodesImpl SerdNodes; + /** Statement. @@ -1300,6 +1308,63 @@ SERD_API SerdStatus serd_writer_finish(SerdWriter* writer); +/** + @} + @name Nodes + @{ +*/ + +/** + Create a new node set. +*/ +SERD_API +SerdNodes* +serd_nodes_new(void); + +/** + Free `nodes` and all nodes that are stored in it. + + Note that this invalidates any pointers previously returned from + `serd_nodes_intern()` or `serd_nodes_manage()` calls on `nodes`. +*/ +SERD_API +void +serd_nodes_free(SerdNodes* nodes); + +/** + Intern `node`. + + Multiple calls with equivalent nodes will return the same pointer. + + @return A node that is different than, but equivalent to, `node`. +*/ +SERD_API +const SerdNode* +serd_nodes_intern(SerdNodes* nodes, const SerdNode* node); + +/** + Manage `node`. + + Like `serd_nodes_intern`, but takes ownership of `node`, freeing it and + returning a previously interned/managed equivalent node if necessary. + + @return A node that is equivalent to `node`. +*/ +SERD_API +const SerdNode* +serd_nodes_manage(SerdNodes* nodes, SerdNode* node); + +/** + Dereference `node`. + + Decrements the reference count of `node`, and frees the internally stored + equivalent node if this was the last reference. Does nothing if no node + equivalent to `node` is stored in `nodes`. +*/ +SERD_API +void +serd_nodes_deref(SerdNodes* nodes, const SerdNode* node); + /** @} @name Statement diff --git a/src/node.c b/src/node.c index 9e437c5e..dc19c2c6 100644 --- a/src/node.c +++ b/src/node.c @@ -96,7 +96,7 @@ serd_node_check_padding(const SerdNode* node) #endif } -static size_t +size_t serd_node_total_size(const SerdNode* node) { const size_t len = sizeof(SerdNode) + serd_node_pad_size(node->n_bytes); diff --git a/src/node.h b/src/node.h index dec63823..c5d0e56b 100644 --- a/src/node.h +++ b/src/node.h @@ -42,6 +42,7 @@ serd_node_buffer_c(const SerdNode* node) SerdNode* serd_node_malloc(size_t n_bytes, SerdNodeFlags flags, SerdType type); void serd_node_set(SerdNode** dst, const SerdNode* src); +size_t serd_node_total_size(const SerdNode* node); void serd_node_zero_pad(SerdNode* node); SerdNode* serd_new_resolved_uri_i(const char* str, const SerdURI* base); diff --git a/src/nodes.c b/src/nodes.c new file mode 100644 index 00000000..7a200c9f --- /dev/null +++ b/src/nodes.c @@ -0,0 +1,137 @@ +/* + Copyright 2011-2018 David Robillard + + Permission to use, copy, modify, and/or distribute this software for any + purpose with or without fee is hereby granted, provided that the above + copyright notice and this permission notice appear in all copies. + + THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. +*/ + +#include "node.h" + +#include "zix/common.h" +#include "zix/digest.h" +#include "zix/hash.h" + +#include +#include +#include + +typedef struct { + size_t refs; + SerdNode* node; +} NodesEntry; + +typedef struct { + size_t refs; + const SerdNode* node; +} NodesSearchKey; + +struct SerdNodesImpl { + ZixHash* hash; +}; + +static uint32_t +nodes_hash(const void* n) +{ + const SerdNode* node = ((const NodesEntry*)n)->node; + uint32_t hash = zix_digest_start(); + hash = zix_digest_add(hash, node, serd_node_total_size(node)); + return hash; +} + +static bool +nodes_equal(const void* a, const void* b) +{ + const SerdNode* a_node = ((const NodesEntry*)a)->node; + const SerdNode* b_node = ((const NodesEntry*)b)->node; + const size_t a_size = serd_node_total_size(a_node); + const size_t b_size = serd_node_total_size(b_node); + return ((a_node == b_node) || + (a_size == b_size && !memcmp(a_node, b_node, a_size))); +} + +static void +free_entry(void* value, void* user_data) +{ + NodesEntry* entry = (NodesEntry*)value; + serd_node_free(entry->node); +} + +SerdNodes* +serd_nodes_new(void) +{ + SerdNodes* nodes = (SerdNodes*)calloc(1, sizeof(SerdNodes)); + nodes->hash = zix_hash_new(nodes_hash, nodes_equal, sizeof(NodesEntry)); + return nodes; +} + +void +serd_nodes_free(SerdNodes* nodes) +{ + zix_hash_foreach(nodes->hash, free_entry, nodes); + zix_hash_free(nodes->hash); + free(nodes); +} + +const SerdNode* +serd_nodes_intern(SerdNodes* nodes, const SerdNode* node) +{ + if (!node) { + return NULL; + } + + NodesSearchKey key = { 1, node }; + NodesEntry* inserted = NULL; + switch (zix_hash_insert(nodes->hash, &key, (const void**)&inserted)) { + case ZIX_STATUS_EXISTS: + assert(serd_node_equals(inserted->node, node)); + ++inserted->refs; + break; + case ZIX_STATUS_SUCCESS: + inserted->node = serd_node_copy(node); + default: break; + } + + return inserted ? inserted->node : NULL; +} + +const SerdNode* +serd_nodes_manage(SerdNodes* nodes, SerdNode* node) +{ + if (!node) { + return NULL; + } + + NodesSearchKey key = { 1, node }; + NodesEntry* inserted = NULL; + switch (zix_hash_insert(nodes->hash, &key, (const void**)&inserted)) { + case ZIX_STATUS_EXISTS: + assert(serd_node_equals(inserted->node, node)); + serd_node_free(node); + ++inserted->refs; + break; + default: break; + } + + return inserted ? inserted->node : NULL; +} + +void +serd_nodes_deref(SerdNodes* nodes, const SerdNode* node) +{ + NodesSearchKey key = { 1, node }; + NodesEntry* entry = (NodesEntry*)zix_hash_find(nodes->hash, &key); + if (entry && --entry->refs == 0) { + SerdNode* const intern_node = entry->node; + zix_hash_remove(nodes->hash, entry); + serd_node_free(intern_node); + } +} diff --git a/tests/nodes_test.c b/tests/nodes_test.c new file mode 100644 index 00000000..08e08ff1 --- /dev/null +++ b/tests/nodes_test.c @@ -0,0 +1,105 @@ +/* + Copyright 2018 David Robillard + + Permission to use, copy, modify, and/or distribute this software for any + purpose with or without fee is hereby granted, provided that the above + copyright notice and this permission notice appear in all copies. + + THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. +*/ + +#include "serd/serd.h" + +#include "test_utils.h" + +static int +test_intern(void) +{ + SerdNodes* nodes = serd_nodes_new(); + SerdNode* node = serd_new_string("node"); + + const SerdNode* interned1 = serd_nodes_intern(nodes, node); + if (!serd_node_equals(node, interned1)) { + FAIL("First interned node does not equal original\n"); + } + + const SerdNode* interned2 = serd_nodes_intern(nodes, node); + if (!serd_node_equals(node, interned2)) { + FAIL("Second interned node does not equal original\n"); + } + + if (interned1 != interned2) { + FAIL("Equivalent interned nodes have different addresses\n"); + } + + serd_node_free(node); + serd_nodes_free(nodes); + return 0; +} + +static int +test_manage(void) +{ + SerdNodes* nodes = serd_nodes_new(); + SerdNode* node = serd_new_string("node"); + + if (serd_nodes_manage(nodes, NULL)) { + FAIL("Managing NULL returned a node\n"); + } + + const SerdNode* managed1 = serd_nodes_manage(nodes, node); + if (managed1 != node) { + FAIL("First managed node has a different address than original\n"); + } + + SerdNode* equal = serd_new_string("node"); + const SerdNode* managed2 = serd_nodes_manage(nodes, equal); + if (managed2 != node) { + FAIL("Double managed node has a different address than original\n"); + } + + serd_nodes_free(nodes); + return 0; +} + +static int +test_deref(void) +{ + SerdNodes* nodes = serd_nodes_new(); + const SerdNode* managed = serd_nodes_manage(nodes, serd_new_string("node")); + + serd_nodes_deref(nodes, managed); + + SerdNode* node = serd_new_string("node"); + const SerdNode* interned = serd_nodes_intern(nodes, node); + + if (interned == node) { + FAIL("Dereferenced node was not deleted\n"); + } + + serd_node_free(node); + serd_nodes_free(nodes); + return 0; +} + +int +main(int argc, char** argv) +{ + typedef int (*TestFunc)(void); + + const TestFunc tests[] = { test_intern, test_manage, test_deref, NULL }; + + for (const TestFunc* t = tests; *t; ++t) { + if ((*t)()) { + return 1; + } + } + + return 0; +} diff --git a/wscript b/wscript index 14eea8e1..f5f6cde7 100644 --- a/wscript +++ b/wscript @@ -81,6 +81,7 @@ lib_source = ['src/base64.c', 'src/env.c', 'src/n3.c', 'src/node.c', + 'src/nodes.c', 'src/reader.c', 'src/sink.c', 'src/statement.c', @@ -89,7 +90,9 @@ lib_source = ['src/base64.c', 'src/system.c', 'src/uri.c', 'src/world.c', - 'src/writer.c'] + 'src/writer.c', + 'src/zix/digest.c', + 'src/zix/hash.c'] def build(bld): # C Headers @@ -148,7 +151,8 @@ def build(bld): # Test programs for prog in [('serdi_static', 'src/serdi.c'), ('serd_test', 'tests/serd_test.c'), - ('read_chunk_test', 'tests/read_chunk_test.c')]: + ('read_chunk_test', 'tests/read_chunk_test.c'), + ('nodes_test', 'tests/nodes_test.c')]: bld(features = 'c cprogram', source = prog[1], use = 'libserd_profiled', @@ -480,7 +484,9 @@ def test(ctx): os.environ['PATH'] = '.' + os.pathsep + os.getenv('PATH') autowaf.pre_test(ctx, APPNAME) - autowaf.run_tests(ctx, APPNAME, ['serd_test', 'read_chunk_test'], name='Unit') + autowaf.run_tests(ctx, APPNAME, + ['serd_test', 'read_chunk_test', 'nodes_test'], + name='Unit') def test_syntax_io(in_name, expected_name, lang): in_path = 'tests/good/%s' % in_name -- cgit v1.2.1