aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2018-10-28 14:00:47 +0100
committerDavid Robillard <d@drobilla.net>2018-12-31 11:37:48 -0500
commitb4a73bd563cbc572bdfd749a764e0989aa7fbe71 (patch)
tree78af69e7d50ea480459f89b4f96b6a6aff76fbd5
parentdcf231a70418c978bd827eceb1e7714c9eac8357 (diff)
downloadserd-b4a73bd563cbc572bdfd749a764e0989aa7fbe71.tar.gz
serd-b4a73bd563cbc572bdfd749a764e0989aa7fbe71.tar.bz2
serd-b4a73bd563cbc572bdfd749a764e0989aa7fbe71.zip
Add SerdNodes class for storing a cache of nodes
-rw-r--r--serd/serd.h65
-rw-r--r--src/node.c2
-rw-r--r--src/node.h1
-rw-r--r--src/nodes.c139
-rw-r--r--tests/nodes_test.c92
-rw-r--r--wscript12
6 files changed, 307 insertions, 4 deletions
diff --git a/serd/serd.h b/serd/serd.h
index 5242d51a..ad131e2d 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.
A subject, predicate, and object, with optional graph context.
@@ -1299,6 +1307,63 @@ 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 80509640..36b1af79 100644
--- a/src/node.c
+++ b/src/node.c
@@ -98,7 +98,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 0763168f..bfd9ebf5 100644
--- a/src/node.h
+++ b/src/node.h
@@ -41,6 +41,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..c3a63c7e
--- /dev/null
+++ b/src/nodes.c
@@ -0,0 +1,139 @@
+/*
+ Copyright 2011-2018 David Robillard <http://drobilla.net>
+
+ 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 <assert.h>
+#include <stdlib.h>
+#include <string.h>
+
+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)
+{
+ (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..41058495
--- /dev/null
+++ b/tests/nodes_test.c
@@ -0,0 +1,92 @@
+/*
+ Copyright 2018 David Robillard <http://drobilla.net>
+
+ 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.
+*/
+
+#undef NDEBUG
+
+#include "serd/serd.h"
+
+#include <assert.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);
+ assert(serd_node_equals(node, interned1));
+
+ const SerdNode* interned2 = serd_nodes_intern(nodes, node);
+ assert(serd_node_equals(node, interned2));
+ assert(interned1 == interned2);
+
+ 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");
+
+ assert(!serd_nodes_manage(nodes, NULL));
+
+ const SerdNode* managed1 = serd_nodes_manage(nodes, node);
+ assert(managed1 == node);
+
+ SerdNode* equal = serd_new_string("node");
+ const SerdNode* managed2 = serd_nodes_manage(nodes, equal);
+ assert(managed2 == node);
+
+ 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);
+
+ assert(interned != node);
+
+ serd_node_free(node);
+ serd_nodes_free(nodes);
+ return 0;
+}
+
+int
+main(void)
+{
+ 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 e7e97b72..506cd3ae 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',
@@ -482,7 +486,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