Add SerdNodes for storing a cache of interned nodes

16 files changed, 1395 insertions, 70 deletions

diff --git a/doc/conf.py.in b/doc/conf.py.in
index c6e146f2..70efec61 100644
--- a/doc/conf.py.in
+++ b/doc/conf.py.in
@@ -31,6 +31,7 @@ _opaque = [
     "SerdCaretImpl",
     "SerdEnvImpl",
     "SerdNodeImpl",
+    "SerdNodesImpl",
     "SerdReaderImpl",
     "SerdSinkImpl",
     "SerdStatementImpl",
diff --git a/include/serd/node.h b/include/serd/node.h
index d140e4c0..8dbdbde4 100644
--- a/include/serd/node.h
+++ b/include/serd/node.h
@@ -120,7 +120,7 @@ typedef uint32_t SerdNodeFlags;
 
    Arguments constructors like #serd_a_file_uri return a temporary view of
    their arguments, which can be passed (usually inline) to node construction
-   functions like #serd_node_new, or #serd_node_construct.
+   functions like #serd_node_new, #serd_node_construct, or #serd_nodes_get.
 
    @{
 */
@@ -413,6 +413,9 @@ serd_node_construct(size_t buf_size, void* ZIX_NULLABLE buf, SerdNodeArgs args);
    nodes with an allocator.  The returned nodes must be freed with
    serd_node_free() using the same allocator.
 
+   Note that in most cases it is better to use a #SerdNodes instead of managing
+   individual node allocations.
+
    @{
 */
 
diff --git a/include/serd/nodes.h b/include/serd/nodes.h
new file mode 100644
index 00000000..c23fe024
--- /dev/null
+++ b/include/serd/nodes.h
@@ -0,0 +1,88 @@
+// Copyright 2011-2022 David Robillard <d@drobilla.net>
+// SPDX-License-Identifier: ISC
+
+#ifndef SERD_NODES_H
+#define SERD_NODES_H
+
+#include "serd/attributes.h"
+#include "serd/memory.h"
+#include "serd/node.h"
+#include "zix/attributes.h"
+
+#include <stddef.h>
+
+SERD_BEGIN_DECLS
+
+/**
+   @defgroup serd_nodes Nodes
+   @ingroup serd_storage
+   @{
+*/
+
+/// Hashing node container for interning and simplified memory management
+typedef struct SerdNodesImpl SerdNodes;
+
+/// Create a new node set
+SERD_API SerdNodes* ZIX_ALLOCATED
+serd_nodes_new(SerdAllocator* ZIX_NULLABLE allocator);
+
+/**
+   Free `nodes` and all nodes that are stored in it.
+
+   Note that this invalidates any node pointers previously returned from
+   `nodes`.
+*/
+SERD_API void
+serd_nodes_free(SerdNodes* ZIX_NULLABLE nodes);
+
+/// Return the number of interned nodes
+SERD_PURE_API size_t
+serd_nodes_size(const SerdNodes* ZIX_NONNULL nodes);
+
+/**
+   Return the existing interned copy of a node if it exists.
+
+   This either returns an equivalent to the given node, or null if this node
+   has not been interned.
+*/
+SERD_API const SerdNode* ZIX_NULLABLE
+serd_nodes_existing(const SerdNodes* ZIX_NONNULL nodes,
+                    const SerdNode* ZIX_NULLABLE node);
+
+/**
+   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* ZIX_ALLOCATED
+serd_nodes_intern(SerdNodes* ZIX_NONNULL       nodes,
+                  const SerdNode* ZIX_NULLABLE node);
+
+/**
+   Make a node of any type.
+
+   A new node will be added if an equivalent node is not already in the set.
+*/
+SERD_API const SerdNode* ZIX_ALLOCATED
+serd_nodes_get(SerdNodes* ZIX_NONNULL nodes, SerdNodeArgs args);
+
+/**
+   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* ZIX_NONNULL       nodes,
+                 const SerdNode* ZIX_NULLABLE node);
+
+/**
+   @}
+*/
+
+SERD_END_DECLS
+
+#endif // SERD_NODES_H
diff --git a/include/serd/serd.h b/include/serd/serd.h
index d264192f..4f1d97b5 100644
--- a/include/serd/serd.h
+++ b/include/serd/serd.h
@@ -88,6 +88,14 @@
 
 /**
    @}
+   @defgroup serd_storage Storage
+   @{
+*/
+
+#include "serd/nodes.h"
+
+/**
+   @}
 */
 
 // IWYU pragma: end_exports
diff --git a/meson.build b/meson.build
index 82dc839b..3e8500ec 100644
--- a/meson.build
+++ b/meson.build
@@ -137,6 +137,7 @@ c_headers = files(
   'include/serd/log.h',
   'include/serd/memory.h',
   'include/serd/node.h',
+  'include/serd/nodes.h',
   'include/serd/output_stream.h',
   'include/serd/reader.h',
   'include/serd/serd.h',
@@ -166,6 +167,7 @@ sources = files(
   'src/log.c',
   'src/memory.c',
   'src/node.c',
+  'src/nodes.c',
   'src/output_stream.c',
   'src/read_nquads.c',
   'src/read_ntriples.c',
@@ -204,7 +206,7 @@ libserd = library(
   ] + c_suppressions + extra_c_args + platform_c_args,
   dependencies: [exess_dep, m_dep, zix_dep],
   gnu_symbol_visibility: 'hidden',
-  include_directories: include_dirs,
+  include_directories: include_directories(['include', 'src']),
   install: true,
   soversion: soversion,
   version: meson.project_version(),
diff --git a/src/.clang-tidy b/src/.clang-tidy
index 53834f98..161eabda 100644
--- a/src/.clang-tidy
+++ b/src/.clang-tidy
@@ -10,5 +10,4 @@ Checks: >
   -hicpp-signed-bitwise,
   -llvm-header-guard,
   -misc-no-recursion,
-  -modernize-macro-to-enum,
 InheritParentConfig: true
diff --git a/src/node_spec.h b/src/node_spec.h
new file mode 100644
index 00000000..97243bf6
--- /dev/null
+++ b/src/node_spec.h
@@ -0,0 +1,41 @@
+// Copyright 2021 David Robillard <d@drobilla.net>
+// SPDX-License-Identifier: ISC
+
+#ifndef SERD_SRC_NODE_SPEC_H
+#define SERD_SRC_NODE_SPEC_H
+
+#include "serd/node.h"
+#include "serd/string_view.h"
+
+/**
+   A lightweight "specification" of a node.
+
+   This is essentially the arguments needed to construct any node combined into
+   a single structure.  Since it only refers to strings elsewhere, it is
+   convenient as a way to completely specify a node without having to actually
+   allocate one.
+*/
+typedef struct {
+  SerdNodeType   type;   ///< Basic type of this node
+  SerdStringView string; ///< String contents of this node
+  SerdNodeFlags  flags;  ///< Additional node flags
+  SerdStringView meta;   ///< String contents of datatype or language node
+} NodeSpec;
+
+static inline NodeSpec
+token_spec(const SerdNodeType type, const SerdStringView string)
+{
+  NodeSpec spec = {type, string, 0U, serd_empty_string()};
+  return spec;
+}
+
+static inline NodeSpec
+literal_spec(const SerdStringView string,
+             const SerdNodeFlags  flags,
+             const SerdStringView meta)
+{
+  NodeSpec spec = {SERD_LITERAL, string, flags, meta};
+  return spec;
+}
+
+#endif // SERD_SRC_NODE_SPEC_H
diff --git a/src/nodes.c b/src/nodes.c
new file mode 100644
index 00000000..68d9cf3c
--- /dev/null
+++ b/src/nodes.c
@@ -0,0 +1,506 @@
+// Copyright 2011-2022 David Robillard <d@drobilla.net>
+// SPDX-License-Identifier: ISC
+
+#include "nodes.h"
+
+#include "memory.h"
+#include "node.h"
+#include "node_spec.h"
+
+// Define the types used in the hash interface for more type safety
+#define ZIX_HASH_KEY_TYPE SerdNode
+#define ZIX_HASH_RECORD_TYPE NodesEntry
+#define ZIX_HASH_SEARCH_DATA_TYPE NodeSpec
+
+#include "serd/memory.h"
+#include "serd/nodes.h"
+#include "serd/string_view.h"
+#include "serd/write_result.h"
+#include "zix/allocator.h"
+#include "zix/attributes.h"
+#include "zix/digest.h"
+#include "zix/hash.h"
+
+#include <assert.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <string.h>
+
+#if ((defined(__STDC_VERSION__) && __STDC_VERSION__ >= 201112l) || \
+     (defined(__cplusplus) && __cplusplus >= 201103L))
+
+static_assert(sizeof(NodesEntryHead) == sizeof(SerdNode),
+              "NodesEntryHead must be the same size as SerdNode for alignment");
+
+#endif
+
+/*
+  The main goal here is to make getting an existing node as fast as possible,
+  so that this can be used as a convenient node cache with minimal performance
+  overhead.  Mainly this means striving to avoid allocation when potentially
+  inserting a new node.
+
+  This is achieved by generating a hash code from node components without
+  actually allocating that node, and using the low-level insertion interface of
+  ZixHash to do a custom search.  This way, an entry is only allocated when
+  necessary, and the hash table is only searched once.
+
+  The downside is that subtle and very bad things will happen if the hash
+  generated for the node does not match the actual hash of the node.  The
+  exessive number of assertions around this are there to provide some defense
+  against such mistakes.  Cave operatur.
+*/
+
+/**
+   The maximum size of a node that will be made statically on the stack.
+
+   This mostly applies to things like numeric literal nodes, where a small
+   maximum size is exploited to avoid allocation.  The largest static node
+   string is the longest xsd:decimal, which is 327 bytes.  We need a bit more
+   space than that here for the node header, padding, and datatype.
+*/
+#define MAX_STATIC_NODE_SIZE 384
+
+typedef struct {
+  SerdNode node;
+  char     body[MAX_STATIC_NODE_SIZE];
+} StaticNode;
+
+/**
+   Allocator for allocating entries in the node hash table.
+
+   This allocator implements only the methods used by the serd_node_*
+   constructors, and transparently increases the allocation size so there is
+   room for an extra NodesEntryHead at the start.  This allows the serd_node_*
+   constructors to be re-used here, even though the table stores entries (nodes
+   with an extra header) rather than node pointers directly.
+*/
+typedef struct {
+  SerdAllocator  base; ///< Implementation of SerdAllocator (base "class")
+  SerdAllocator* real; ///< Underlying "real" memory allocator
+} SerdNodesEntryAllocator;
+
+ZIX_MALLOC_FUNC static void*
+serd_nodes_entry_aligned_alloc(SerdAllocator* const allocator,
+                               const size_t         alignment,
+                               const size_t         size)
+{
+  SerdAllocator* const real = ((SerdNodesEntryAllocator*)allocator)->real;
+
+  void* const ptr =
+    real->aligned_alloc(real, alignment, serd_node_align + size);
+
+  return ptr ? (((uint8_t*)ptr) + serd_node_align) : NULL;
+}
+
+static void
+serd_nodes_entry_aligned_free(SerdAllocator* const allocator, void* const ptr)
+{
+  SerdAllocator* const real = ((SerdNodesEntryAllocator*)allocator)->real;
+
+  if (ptr) {
+    real->aligned_free(real, (((uint8_t*)ptr) - serd_node_align));
+  }
+}
+
+static SerdNodesEntryAllocator
+serd_nodes_entry_allocator(SerdAllocator* const real)
+{
+  const SerdNodesEntryAllocator entry_allocator = {
+    {
+      NULL,
+      NULL,
+      NULL,
+      NULL,
+      serd_nodes_entry_aligned_alloc,
+      serd_nodes_entry_aligned_free,
+    },
+    real ? real : serd_default_allocator(),
+  };
+
+  return entry_allocator;
+}
+
+struct SerdNodesImpl {
+  SerdNodesEntryAllocator allocator;
+  ZixHash*                hash;
+};
+
+static const StaticNode empty_static_node = {{0U, 0U, SERD_LITERAL}, {'\0'}};
+
+static const SerdNodeFlags meta_mask = (SERD_HAS_DATATYPE | SERD_HAS_LANGUAGE);
+
+static const SerdNode*
+nodes_key(const NodesEntry* const entry)
+{
+  return &entry->node;
+}
+
+static ZixHashCode
+token_hash(const ZixHashCode    seed,
+           const SerdNodeType   type,
+           const SerdStringView string)
+{
+  const SerdNode node_header = {string.length, 0U, type};
+  ZixHashCode    h           = seed;
+
+  h = zix_digest_aligned(h, &node_header, sizeof(node_header));
+  h = zix_digest(h, string.data, string.length);
+  return h;
+}
+
+static ZixHashCode
+spec_hash(const NodeSpec spec)
+{
+  ZixHashCode h = token_hash(0U, spec.type, spec.string);
+
+  if (spec.flags & SERD_HAS_DATATYPE) {
+    h = token_hash(h, SERD_URI, spec.meta);
+  } else if (spec.flags & SERD_HAS_LANGUAGE) {
+    h = token_hash(h, SERD_LITERAL, spec.meta);
+  }
+
+  return zix_digest(h, &spec.flags, sizeof(spec.flags));
+}
+
+static ZixHashCode
+nodes_hash(const SerdNode* const node)
+{
+  /* If you're thinking "I know, I'll make this faster by just hashing the
+     entire node in one call!", think harder.  Since zero bytes affect the hash
+     value, that would mean that the hash code for the node won't match the one
+     for the node spec, and the above-mentioned subtle and very bad things will
+     happen.  This function deliberately mirrors spec_hash() above to make it
+     relatively easy to see that the two will match.
+
+     It would be more elegant to construct a spec from the node and then hash
+     that with the exact same code used for searching, but there's currently no
+     use for that anywhere else and this way is a bit faster. */
+
+  ZixHashCode h = token_hash(0U, node->type, serd_node_string_view(node));
+
+  if (node->flags & SERD_HAS_DATATYPE) {
+    h = token_hash(h, SERD_URI, serd_node_string_view(serd_node_meta_c(node)));
+  } else if (node->flags & SERD_HAS_LANGUAGE) {
+    h = token_hash(
+      h, SERD_LITERAL, serd_node_string_view(serd_node_meta_c(node)));
+  }
+
+  return zix_digest(h, &node->flags, sizeof(node->flags));
+}
+
+static bool
+node_equals_spec(const SerdNode* const node, const NodeSpec* const spec)
+{
+  return serd_node_type(node) == spec->type &&
+         serd_node_length(node) == spec->string.length &&
+         node->flags == spec->flags &&
+         !strcmp(serd_node_string_i(node), spec->string.data) &&
+         (!(node->flags & meta_mask) ||
+          !strcmp(serd_node_string_i(serd_node_meta_c(node)), spec->meta.data));
+}
+
+static bool
+nodes_meta_equal(const SerdNode* const a, const SerdNode* const b)
+{
+  assert(a->flags & meta_mask);
+  assert(b->flags & meta_mask);
+
+  const size_t          padded_length = serd_node_pad_length(a->length);
+  const size_t          offset        = padded_length / sizeof(SerdNode);
+  const SerdNode* const am            = a + 1U + offset;
+  const SerdNode* const bm            = b + 1U + offset;
+
+  return am->length == bm->length && am->type == bm->type &&
+         !memcmp(serd_node_string_i(am), serd_node_string_i(bm), am->length);
+}
+
+static bool
+nodes_equal(const SerdNode* const a, const SerdNode* const b)
+{
+  return (a == b) ||
+         (a->length == b->length && a->flags == b->flags &&
+          a->type == b->type &&
+          !memcmp(serd_node_string_i(a), serd_node_string_i(b), a->length) &&
+          (!(a->flags & meta_mask) || nodes_meta_equal(a, b)));
+}
+
+static void
+free_entry(SerdNodes* const nodes, NodesEntry* const entry)
+{
+  serd_aaligned_free(&nodes->allocator.base, &entry->node);
+}
+
+SerdNodes*
+serd_nodes_new(SerdAllocator* const allocator)
+{
+  SerdNodes* const nodes =
+    (SerdNodes*)serd_acalloc(allocator, 1, sizeof(SerdNodes));
+
+  if (nodes) {
+    nodes->allocator = serd_nodes_entry_allocator(allocator);
+
+    if (!(nodes->hash = zix_hash_new(
+            (ZixAllocator*)allocator, nodes_key, nodes_hash, nodes_equal))) {
+      serd_afree(allocator, nodes);
+      return NULL;
+    }
+  }
+
+  return nodes;
+}
+
+void
+serd_nodes_free(SerdNodes* nodes)
+{
+  if (nodes) {
+    for (ZixHashIter i = zix_hash_begin(nodes->hash);
+         i != zix_hash_end(nodes->hash);
+         i = zix_hash_next(nodes->hash, i)) {
+      free_entry(nodes, (NodesEntry*)zix_hash_get(nodes->hash, i));
+    }
+
+    zix_hash_free(nodes->hash);
+    serd_afree(nodes->allocator.real, nodes);
+  }
+}
+
+size_t
+serd_nodes_size(const SerdNodes* nodes)
+{
+  assert(nodes);
+
+  return zix_hash_size(nodes->hash);
+}
+
+const SerdNode*
+serd_nodes_intern(SerdNodes* nodes, const SerdNode* node)
+{
+  assert(nodes);
+  if (!node) {
+    return NULL;
+  }
+
+  const ZixHashInsertPlan plan     = zix_hash_plan_insert(nodes->hash, node);
+  NodesEntry* const       existing = zix_hash_record_at(nodes->hash, plan);
+  if (existing) {
+    assert(serd_node_equals(&existing->node, node));
+    ++existing->head.refs;
+    return &existing->node;
+  }
+
+  SerdNode* const new_node = serd_node_copy(&nodes->allocator.base, node);
+  if (!new_node) {
+    return NULL;
+  }
+
+  NodesEntry* const entry = (NodesEntry*)(new_node - 1U);
+
+  entry->head.refs = 1U;
+
+  // Insert the entry (blissfully ignoring a failed hash size increase)
+  if (zix_hash_insert_at(nodes->hash, plan, entry)) {
+    free_entry(nodes, entry);
+    return NULL;
+  }
+
+  return &entry->node;
+}
+
+const SerdNode*
+serd_nodes_existing(const SerdNodes* const nodes, const SerdNode* const node)
+{
+  assert(nodes);
+
+  if (!node) {
+    return NULL;
+  }
+
+  NodesEntry* const entry = zix_hash_find_record(nodes->hash, node);
+
+  return entry ? &entry->node : NULL;
+}
+
+static const SerdNode*
+serd_nodes_manage_entry_at(SerdNodes* const        nodes,
+                           NodesEntry* const       entry,
+                           const ZixHashInsertPlan plan)
+{
+  assert(nodes);
+  assert(entry);
+
+  entry->head.refs = 1U;
+
+  // Insert the entry (blissfully ignoring a failed hash size increase)
+  if (zix_hash_insert_at(nodes->hash, plan, entry)) {
+    free_entry(nodes, entry);
+    return NULL;
+  }
+
+  return &entry->node;
+}
+
+static const SerdNode*
+serd_nodes_manage_entry_node_at(SerdNodes* const        nodes,
+                                SerdNode* const         node,
+                                const ZixHashInsertPlan plan)
+{
+  if (!node) {
+    return NULL;
+  }
+
+  NodesEntry* const entry = (NodesEntry*)(node - 1U);
+
+  return serd_nodes_manage_entry_at(nodes, entry, plan);
+}
+
+static const SerdNode*
+serd_nodes_manage_entry_node(SerdNodes* const nodes, SerdNode* const node)
+{
+  if (!node) {
+    return NULL;
+  }
+
+  NodesEntry* const       entry    = (NodesEntry*)(node - 1U);
+  const ZixHashInsertPlan plan     = zix_hash_plan_insert(nodes->hash, node);
+  NodesEntry* const       existing = zix_hash_record_at(nodes->hash, plan);
+  if (existing) {
+    assert(serd_node_equals(&existing->node, node));
+    assert(nodes_hash(&existing->node) == plan.code);
+    ++existing->head.refs;
+    free_entry(nodes, entry);
+    return &existing->node;
+  }
+
+  assert(nodes_hash(&entry->node) == plan.code);
+
+  return serd_nodes_manage_entry_at(nodes, entry, plan);
+}
+
+static const SerdNode*
+serd_nodes_token(SerdNodes* const     nodes,
+                 const SerdNodeType   type,
+                 const SerdStringView string)
+{
+  // Calculate a hash code for the token without actually constructing it
+  const NodeSpec    key  = token_spec(type, string);
+  const ZixHashCode code = spec_hash(key);
+
+  // Find an insert position in the hash table
+  const ZixHashInsertPlan plan =
+    zix_hash_plan_insert_prehashed(nodes->hash, code, node_equals_spec, &key);
+
+  // If we found an existing node, bump its reference count and return it
+  NodesEntry* const existing = zix_hash_record_at(nodes->hash, plan);
+  if (existing) {
+    assert(nodes_hash(&existing->node) == code);
+    ++existing->head.refs;
+    return &existing->node;
+  }
+
+  // Otherwise, allocate and manage a new one
+  SerdAllocator* const alloc = &nodes->allocator.base;
+  SerdNode* const      node  = serd_node_new(alloc, serd_a_token(type, string));
+
+  return serd_nodes_manage_entry_node_at(nodes, node, plan);
+}
+
+static const SerdNode*
+serd_nodes_literal(SerdNodes* const     nodes,
+                   const SerdStringView string,
+                   const SerdNodeFlags  flags,
+                   const SerdStringView meta)
+{
+  // Calculate a hash code for the literal without actually constructing it
+  const NodeSpec    spec = literal_spec(string, flags, meta);
+  const ZixHashCode code = spec_hash(spec);
+
+  // Find an insert position in the hash table
+  const ZixHashInsertPlan plan =
+    zix_hash_plan_insert_prehashed(nodes->hash, code, node_equals_spec, &spec);
+
+  // If we found an existing node, bump its reference count and return it
+  NodesEntry* const existing = zix_hash_record_at(nodes->hash, plan);
+  if (existing) {
+    assert(nodes_hash(&existing->node) == code);
+    ++existing->head.refs;
+    return &existing->node;
+  }
+
+  // Otherwise, allocate and manage a new one
+  SerdAllocator* const alloc = &nodes->allocator.base;
+  SerdNode* const      node =
+    serd_node_new(alloc, serd_a_literal(string, flags, meta));
+
+  return serd_nodes_manage_entry_node_at(nodes, node, plan);
+}
+
+static const SerdNode*
+try_intern(SerdNodes* const      nodes,
+           const SerdWriteResult r,
+           const SerdNode* const node)
+{
+  return r.status ? NULL : serd_nodes_intern(nodes, node);
+}
+
+const SerdNode*
+serd_nodes_get(SerdNodes* const nodes, const SerdNodeArgs args)
+{
+  StaticNode key = empty_static_node;
+
+  /* Some types here are cleverly hashed without allocating a node, but others
+     simply allocate a new node and attempt to manage it.  It would be possible
+     to calculate an in-place hash for some of them, but this is quite
+     complicated and error-prone, so more difficult edge cases aren't yet
+     implemented. */
+
+  switch (args.type) {
+  case SERD_NODE_ARGS_TOKEN:
+    return serd_nodes_token(
+      nodes, args.data.as_token.type, args.data.as_token.string);
+
+  case SERD_NODE_ARGS_PARSED_URI:
+  case SERD_NODE_ARGS_FILE_URI:
+    break;
+
+  case SERD_NODE_ARGS_LITERAL:
+    return serd_nodes_literal(nodes,
+                              args.data.as_literal.string,
+                              args.data.as_literal.flags,
+                              args.data.as_literal.meta);
+
+  case SERD_NODE_ARGS_PRIMITIVE:
+  case SERD_NODE_ARGS_DECIMAL:
+  case SERD_NODE_ARGS_INTEGER:
+    return try_intern(
+      nodes, serd_node_construct(sizeof(key), &key, args), &key.node);
+
+  case SERD_NODE_ARGS_HEX:
+  case SERD_NODE_ARGS_BASE64:
+    break;
+  }
+
+  return serd_nodes_manage_entry_node(
+    nodes, serd_node_new(&nodes->allocator.base, args));
+}
+
+void
+serd_nodes_deref(SerdNodes* const nodes, const SerdNode* const node)
+{
+  if (!node) {
+    return;
+  }
+
+  ZixHashIter i = zix_hash_find(nodes->hash, node);
+  if (i == zix_hash_end(nodes->hash)) {
+    return;
+  }
+
+  NodesEntry* const entry = zix_hash_get(nodes->hash, i);
+  if (--entry->head.refs == 0U) {
+    NodesEntry* removed = NULL;
+    zix_hash_erase(nodes->hash, i, &removed);
+    assert(removed == entry);
+    free_entry(nodes, removed);
+  }
+}
diff --git a/src/nodes.h b/src/nodes.h
new file mode 100644
index 00000000..daec673d
--- /dev/null
+++ b/src/nodes.h
@@ -0,0 +1,56 @@
+// Copyright 2021 David Robillard <d@drobilla.net>
+// SPDX-License-Identifier: ISC
+
+/*
+  Nothing here is actually used outside the nodes implementation, but we need
+  the types to be defined before including zix/hash.h to enable its type-safe
+  interface.  Putting those here is a way of doing that without messy hacks
+  like including headers half-way through the implementation.
+*/
+
+#ifndef SERD_SRC_NODES_H
+#define SERD_SRC_NODES_H
+
+#include "node.h"
+
+#include "serd/node.h"
+
+#include <stddef.h>
+
+/**
+   The header of an entry in the nodes table.
+
+   The table stores nodes with an additional reference count.  For efficiency,
+   entries are allocated as a single block of memory, which start with this
+   header and are followed by the body of the node.
+
+   This structure must be the same size as SerdNode to preserve the alignment
+   of the contained node.  This is a bit wasteful, but the alignment guarantee
+   allows the node implementation to avoid messy casts and byte-based pointer
+   arithmetic that could cause alignment problems.  This might be worth
+   reconsidering, since this wasted space has a real (if small) negative
+   impact, while the alignment guarantee just allows the implementation to use
+   stricter compiler settings.
+
+   Better yet, shrink SerdNode down to size_t, which is malloc's alignment
+   guarantee, and all of this goes away, at the cost of a reduced maximum
+   length for literal nodes.
+*/
+typedef struct {
+  size_t   refs; ///< Reference count
+  unsigned pad1; ///< Padding to align the following SerdNode
+  unsigned pad2; ///< Padding to align the following SerdNode
+} NodesEntryHead;
+
+/**
+   An entry in the nodes table.
+
+   This is a variably-sized structure that is allocated specifically to contain
+   the node.
+*/
+typedef struct {
+  NodesEntryHead head; ///< Extra data associated with the node
+  SerdNode       node; ///< Node header (body immediately follows)
+} NodesEntry;
+
+#endif // SERD_SRC_NODES_H
diff --git a/test/meson.build b/test/meson.build
index d7dcfa05..2528ef66 100644
--- a/test/meson.build
+++ b/test/meson.build
@@ -130,6 +130,7 @@ unit_tests = [
   'free_null',
   'log',
   'node',
+  'nodes',
   'overflow',
   'reader',
   'reader_writer',
diff --git a/test/test_canon.c b/test/test_canon.c
index 7d7fbf28..89d1312b 100644
--- a/test/test_canon.c
+++ b/test/test_canon.c
@@ -8,6 +8,7 @@
 #include "serd/canon.h"
 #include "serd/event.h"
 #include "serd/node.h"
+#include "serd/nodes.h"
 #include "serd/sink.h"
 #include "serd/status.h"
 #include "serd/string_view.h"
@@ -30,6 +31,7 @@ test_new_failed_alloc(void)
   SerdFailingAllocator allocator = serd_failing_allocator();
 
   SerdWorld* const world = serd_world_new(&allocator.base);
+  SerdNodes* const nodes = serd_nodes_new(&allocator.base);
 
   SerdSink* target = serd_sink_new(&allocator.base, NULL, ignore_event, NULL);
   const size_t n_setup_allocs = allocator.n_allocations;
@@ -47,6 +49,7 @@ test_new_failed_alloc(void)
 
   serd_sink_free(canon);
   serd_sink_free(target);
+  serd_nodes_free(nodes);
   serd_world_free(world);
 }
 
@@ -60,13 +63,13 @@ test_write_failed_alloc(void)
     serd_string("http://www.w3.org/2001/XMLSchema#float");
 
   SerdFailingAllocator allocator = serd_failing_allocator();
+  SerdWorld* const     world     = serd_world_new(&allocator.base);
+  SerdNodes* const     nodes     = serd_nodes_new(&allocator.base);
 
-  SerdWorld* const world = serd_world_new(&allocator.base);
-
-  SerdNode* const s = serd_node_new(&allocator.base, serd_a_uri(s_string));
-  SerdNode* const p = serd_node_new(&allocator.base, serd_a_uri(p_string));
-  SerdNode* const o =
-    serd_node_new(&allocator.base, serd_a_typed_literal(o_string, xsd_float));
+  const SerdNode* const s = serd_nodes_get(nodes, serd_a_uri(s_string));
+  const SerdNode* const p = serd_nodes_get(nodes, serd_a_uri(p_string));
+  const SerdNode* const o =
+    serd_nodes_get(nodes, serd_a_typed_literal(o_string, xsd_float));
 
   SerdSink* target = serd_sink_new(&allocator.base, NULL, ignore_event, NULL);
   SerdSink* canon  = serd_canon_new(world, target, 0U);
@@ -87,9 +90,7 @@ test_write_failed_alloc(void)
 
   serd_sink_free(canon);
   serd_sink_free(target);
-  serd_node_free(&allocator.base, o);
-  serd_node_free(&allocator.base, p);
-  serd_node_free(&allocator.base, s);
+  serd_nodes_free(nodes);
   serd_world_free(world);
 }
 
diff --git a/test/test_free_null.c b/test/test_free_null.c
index 891f9b65..7b186fba 100644
--- a/test/test_free_null.c
+++ b/test/test_free_null.c
@@ -7,6 +7,7 @@
 #include "serd/env.h"
 #include "serd/memory.h"
 #include "serd/node.h"
+#include "serd/nodes.h"
 #include "serd/reader.h"
 #include "serd/sink.h"
 #include "serd/world.h"
@@ -24,6 +25,7 @@ main(void)
   serd_sink_free(NULL);
   serd_reader_free(NULL);
   serd_writer_free(NULL);
+  serd_nodes_free(NULL);
   serd_caret_free(NULL, NULL);
 
   return 0;
diff --git a/test/test_nodes.c b/test/test_nodes.c
new file mode 100644
index 00000000..7c2c8508
--- /dev/null
+++ b/test/test_nodes.c
@@ -0,0 +1,597 @@
+// Copyright 2018 David Robillard <d@drobilla.net>
+// SPDX-License-Identifier: ISC
+
+#undef NDEBUG
+
+#include "failing_allocator.h"
+
+#include "serd/memory.h"
+#include "serd/node.h"
+#include "serd/nodes.h"
+#include "serd/string_view.h"
+#include "serd/uri.h"
+#include "serd/value.h"
+
+#include <assert.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <string.h>
+
+#define NS_XSD "http://www.w3.org/2001/XMLSchema#"
+
+static void
+test_new_failed_alloc(void)
+{
+  SerdFailingAllocator allocator = serd_failing_allocator();
+
+  // Successfully allocate a node set to count the number of allocations
+  SerdNodes* nodes = serd_nodes_new(&allocator.base);
+  assert(nodes);
+
+  // Test that each allocation failing is handled gracefully
+  const size_t n_new_allocs = allocator.n_allocations;
+  for (size_t i = 0; i < n_new_allocs; ++i) {
+    allocator.n_remaining = i;
+    assert(!serd_nodes_new(&allocator.base));
+  }
+
+  serd_nodes_free(nodes);
+}
+
+static void
+test_intern_failed_alloc(void)
+{
+  SerdFailingAllocator allocator = serd_failing_allocator();
+
+  SerdNode* const node = serd_node_new(&allocator.base, serd_a_string("node"));
+
+  // Successfully intern a node to count the number of allocations
+  SerdNodes*      nodes     = serd_nodes_new(&allocator.base);
+  const SerdNode* interned1 = serd_nodes_intern(nodes, node);
+  assert(serd_node_equals(node, interned1));
+  assert(serd_nodes_size(nodes) == 1U);
+
+  const size_t n_new_allocs = allocator.n_allocations;
+  serd_nodes_free(nodes);
+
+  // Test that each allocation failing is handled gracefully
+  for (size_t i = 0; i < n_new_allocs; ++i) {
+    allocator.n_remaining = i;
+
+    if ((nodes = serd_nodes_new(&allocator.base))) {
+      const SerdNode* interned2 = serd_nodes_intern(nodes, node);
+      if (interned2) {
+        assert(serd_node_equals(node, interned2));
+        assert(serd_nodes_size(nodes) == 1U);
+      }
+      serd_nodes_free(nodes);
+    }
+  }
+
+  serd_node_free(&allocator.base, node);
+}
+
+static void
+test_intern(void)
+{
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* nodes = serd_nodes_new(allocator);
+  SerdNode*  node  = serd_node_new(NULL, serd_a_string("node"));
+
+  assert(serd_nodes_size(nodes) == 0U);
+  assert(!serd_nodes_intern(nodes, NULL));
+
+  const SerdNode* interned1 = serd_nodes_intern(nodes, node);
+  assert(serd_node_equals(node, interned1));
+  assert(serd_nodes_size(nodes) == 1U);
+
+  const SerdNode* interned2 = serd_nodes_intern(nodes, node);
+  assert(serd_node_equals(node, interned2));
+  assert(interned1 == interned2);
+  assert(serd_nodes_size(nodes) == 1U);
+
+  serd_node_free(NULL, node);
+  serd_nodes_free(nodes);
+}
+
+static void
+test_string(void)
+{
+  const SerdStringView string = serd_string("string");
+
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const      nodes = serd_nodes_new(allocator);
+  const SerdNode* const node =
+    serd_nodes_get(nodes, serd_a_string_view(string));
+
+  assert(node);
+  assert(serd_node_type(node) == SERD_LITERAL);
+  assert(!serd_node_flags(node));
+  assert(!serd_node_datatype(node));
+  assert(!serd_node_language(node));
+  assert(serd_node_length(node) == string.length);
+  assert(!strcmp(serd_node_string(node), string.data));
+
+  const SerdNode* const long_node = serd_nodes_get(
+    nodes, serd_a_literal(string, SERD_IS_LONG, serd_empty_string()));
+
+  assert(long_node);
+  assert(long_node != node);
+  assert(serd_node_type(long_node) == SERD_LITERAL);
+  assert(serd_node_flags(long_node) == SERD_IS_LONG);
+  assert(!serd_node_datatype(long_node));
+  assert(!serd_node_language(long_node));
+  assert(serd_node_length(long_node) == string.length);
+  assert(!strcmp(serd_node_string(long_node), string.data));
+
+  serd_nodes_free(nodes);
+}
+
+static void
+test_invalid_literal(void)
+{
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const nodes = serd_nodes_new(allocator);
+
+  assert(!serd_nodes_get(nodes,
+                         serd_a_literal(serd_string("double meta"),
+                                        SERD_HAS_LANGUAGE | SERD_HAS_DATATYPE,
+                                        serd_string("What am I?"))));
+
+  assert(!serd_nodes_get(nodes,
+                         serd_a_literal(serd_string("empty language"),
+                                        SERD_HAS_LANGUAGE,
+                                        serd_empty_string())));
+
+  assert(!serd_nodes_get(nodes,
+                         serd_a_literal(serd_string("empty datatype"),
+                                        SERD_HAS_DATATYPE,
+                                        serd_empty_string())));
+
+  serd_nodes_free(nodes);
+}
+
+static void
+test_plain_literal(void)
+{
+  const SerdStringView string   = serd_string("string");
+  const SerdStringView language = serd_string("en");
+
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const      nodes = serd_nodes_new(allocator);
+  const SerdNode* const node =
+    serd_nodes_get(nodes, serd_a_plain_literal(string, language));
+
+  assert(node);
+  assert(serd_node_type(node) == SERD_LITERAL);
+  assert(serd_node_flags(node) == SERD_HAS_LANGUAGE);
+  assert(!serd_node_datatype(node));
+
+  const SerdNode* const language_node = serd_node_language(node);
+  assert(language_node);
+  assert(serd_node_type(language_node) == SERD_LITERAL);
+  assert(!serd_node_flags(language_node));
+  assert(serd_node_length(language_node) == language.length);
+  assert(!strcmp(serd_node_string(language_node), language.data));
+  assert(serd_node_length(node) == string.length);
+  assert(!strcmp(serd_node_string(node), string.data));
+
+  const SerdNode* const alias =
+    serd_nodes_get(nodes, serd_a_plain_literal(string, language));
+
+  assert(alias == node);
+
+  const SerdNode* const long_version = serd_nodes_get(
+    nodes, serd_a_literal(string, SERD_HAS_LANGUAGE | SERD_IS_LONG, language));
+
+  assert(long_version != node);
+
+  const SerdNode* const other =
+    serd_nodes_get(nodes, serd_a_plain_literal(string, serd_string("de")));
+
+  assert(other != node);
+
+  const SerdNode* const other_language_node = serd_node_language(other);
+  assert(other_language_node);
+  assert(serd_node_type(other_language_node) == SERD_LITERAL);
+  assert(!serd_node_flags(other_language_node));
+  assert(serd_node_length(other_language_node) == 2);
+  assert(!strcmp(serd_node_string(other_language_node), "de"));
+  assert(serd_node_length(other) == string.length);
+  assert(!strcmp(serd_node_string(other), string.data));
+
+  serd_nodes_free(nodes);
+}
+
+static void
+test_typed_literal(void)
+{
+  const SerdStringView string   = serd_string("string");
+  const SerdStringView datatype = serd_string("http://example.org/Type");
+
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const      nodes = serd_nodes_new(allocator);
+  const SerdNode* const node =
+    serd_nodes_get(nodes, serd_a_typed_literal(string, datatype));
+
+  assert(node);
+  assert(serd_node_type(node) == SERD_LITERAL);
+  assert(serd_node_flags(node) == SERD_HAS_DATATYPE);
+  assert(!serd_node_language(node));
+
+  const SerdNode* const datatype_node = serd_node_datatype(node);
+  assert(datatype_node);
+
+  assert(serd_node_type(datatype_node) == SERD_URI);
+  assert(!serd_node_flags(datatype_node));
+  assert(serd_node_length(datatype_node) == datatype.length);
+  assert(!strcmp(serd_node_string(datatype_node), datatype.data));
+  assert(serd_node_length(node) == string.length);
+  assert(!strcmp(serd_node_string(node), string.data));
+
+  const SerdNode* const alias =
+    serd_nodes_get(nodes, serd_a_typed_literal(string, datatype));
+
+  assert(alias == node);
+
+  serd_nodes_free(nodes);
+}
+
+static void
+test_boolean(void)
+{
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const nodes = serd_nodes_new(allocator);
+
+  const SerdNode* const false1 =
+    serd_nodes_get(nodes, serd_a_primitive(serd_bool(false)));
+
+  const SerdNode* const false2 =
+    serd_nodes_get(nodes, serd_a_primitive(serd_bool(false)));
+
+  const SerdNode* const true1 =
+    serd_nodes_get(nodes, serd_a_primitive(serd_bool(true)));
+
+  const SerdNode* const true2 =
+    serd_nodes_get(nodes, serd_a_primitive(serd_bool(true)));
+
+  assert(false1 == false2);
+  assert(true1 == true2);
+  assert(false1 != true1);
+  assert(!strcmp(serd_node_string(false1), "false"));
+  assert(!strcmp(serd_node_string(true1), "true"));
+  assert(serd_node_length(false1) == strlen(serd_node_string(false1)));
+  assert(serd_node_length(true1) == strlen(serd_node_string(true1)));
+  assert(serd_nodes_size(nodes) == 2);
+
+  const SerdNode* const true_datatype = serd_node_datatype(true1);
+  assert(true_datatype);
+  assert(!strcmp(serd_node_string(true_datatype), NS_XSD "boolean"));
+
+  const SerdNode* const false_datatype = serd_node_datatype(false1);
+  assert(false_datatype);
+  assert(!strcmp(serd_node_string(false_datatype), NS_XSD "boolean"));
+
+  serd_nodes_free(nodes);
+}
+
+static void
+test_decimal(void)
+{
+  SerdAllocator* const allocator = serd_default_allocator();
+  SerdNodes* const     nodes     = serd_nodes_new(allocator);
+
+  const SerdNode* const a = serd_nodes_get(nodes, serd_a_decimal(-12.3456789));
+  const SerdNode* const b = serd_nodes_get(nodes, serd_a_decimal(-12.3456789));
+
+  assert(a == b);
+  assert(!strcmp(serd_node_string(a), "-12.3456789"));
+  assert(serd_node_length(a) == strlen(serd_node_string(a)));
+  assert(serd_nodes_size(nodes) == 1);
+
+  const SerdNode* const default_datatype = serd_node_datatype(a);
+  assert(default_datatype);
+  assert(!strcmp(serd_node_string(default_datatype), NS_XSD "decimal"));
+
+  serd_nodes_free(nodes);
+}
+
+static void
+test_double(void)
+{
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const nodes = serd_nodes_new(allocator);
+
+  const SerdNode* const a =
+    serd_nodes_get(nodes, serd_a_primitive(serd_double(-1.2E3)));
+
+  const SerdNode* const b =
+    serd_nodes_get(nodes, serd_a_primitive(serd_double(-1.2E3)));
+
+  assert(a == b);
+  assert(!strcmp(serd_node_string(a), "-1.2E3"));
+  assert(serd_node_length(a) == strlen(serd_node_string(a)));
+  assert(serd_nodes_size(nodes) == 1);
+
+  serd_nodes_free(nodes);
+}
+
+static void
+test_float(void)
+{
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const nodes = serd_nodes_new(allocator);
+
+  const SerdNode* const a =
+    serd_nodes_get(nodes, serd_a_primitive(serd_float(-1.2E3f)));
+
+  const SerdNode* const b =
+    serd_nodes_get(nodes, serd_a_primitive(serd_float(-1.2E3f)));
+
+  assert(a == b);
+  assert(!strcmp(serd_node_string(a), "-1.2E3"));
+  assert(serd_node_length(a) == strlen(serd_node_string(a)));
+  assert(serd_nodes_size(nodes) == 1);
+
+  serd_nodes_free(nodes);
+}
+
+static void
+test_integer(void)
+{
+  SerdAllocator* const allocator = serd_default_allocator();
+  SerdNodes* const     nodes     = serd_nodes_new(allocator);
+
+  const SerdNode* const a = serd_nodes_get(nodes, serd_a_integer(-1234567890));
+  const SerdNode* const b = serd_nodes_get(nodes, serd_a_integer(-1234567890));
+
+  assert(a == b);
+  assert(!strcmp(serd_node_string(a), "-1234567890"));
+  assert(serd_node_length(a) == strlen(serd_node_string(a)));
+  assert(serd_nodes_size(nodes) == 1);
+
+  const SerdNode* const default_datatype = serd_node_datatype(a);
+  assert(default_datatype);
+  assert(!strcmp(serd_node_string(default_datatype), NS_XSD "integer"));
+
+  serd_nodes_free(nodes);
+}
+
+static void
+test_base64(void)
+{
+  static const char data[] = {'f', 'o', 'o', 'b', 'a', 'r'};
+
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const nodes = serd_nodes_new(allocator);
+
+  const SerdNode* const a =
+    serd_nodes_get(nodes, serd_a_base64(sizeof(data), &data));
+
+  const SerdNode* const b =
+    serd_nodes_get(nodes, serd_a_base64(sizeof(data), &data));
+
+  assert(a == b);
+  assert(!strcmp(serd_node_string(a), "Zm9vYmFy"));
+  assert(serd_node_length(a) == strlen(serd_node_string(a)));
+  assert(serd_nodes_size(nodes) == 1);
+
+  const SerdNode* const default_datatype = serd_node_datatype(a);
+  assert(default_datatype);
+  assert(!strcmp(serd_node_string(default_datatype), NS_XSD "base64Binary"));
+
+  serd_nodes_free(nodes);
+}
+
+static void
+test_uri(void)
+{
+  const SerdStringView string = serd_string("http://example.org/");
+
+  SerdAllocator* const allocator = serd_default_allocator();
+  SerdNodes* const     nodes     = serd_nodes_new(allocator);
+
+  const SerdNode* const node = serd_nodes_get(nodes, serd_a_uri(string));
+
+  assert(node);
+  assert(serd_node_type(node) == SERD_URI);
+  assert(!serd_node_flags(node));
+  assert(!serd_node_datatype(node));
+  assert(!serd_node_language(node));
+  assert(serd_node_length(node) == string.length);
+  assert(!strcmp(serd_node_string(node), string.data));
+
+  serd_nodes_free(nodes);
+}
+
+static void
+test_parsed_uri(void)
+{
+  const SerdStringView string = serd_string("http://example.org/");
+
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const      nodes = serd_nodes_new(allocator);
+  const SerdURIView     uri   = serd_parse_uri(string.data);
+  const SerdNode* const node  = serd_nodes_get(nodes, serd_a_parsed_uri(uri));
+
+  assert(node);
+  assert(serd_node_type(node) == SERD_URI);
+  assert(!serd_node_flags(node));
+  assert(!serd_node_datatype(node));
+  assert(!serd_node_language(node));
+  assert(serd_node_length(node) == string.length);
+  assert(!strcmp(serd_node_string(node), string.data));
+
+  const SerdNode* const alias = serd_nodes_get(nodes, serd_a_parsed_uri(uri));
+
+  assert(alias == node);
+
+  const SerdNode* const other = serd_nodes_get(
+    nodes, serd_a_parsed_uri(serd_parse_uri("http://example.org/x")));
+
+  assert(other != node);
+
+  serd_nodes_free(nodes);
+}
+
+static void
+test_file_uri(void)
+{
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  const SerdStringView local_string  = serd_string("file:///d/f.txt");
+  const SerdStringView local_path    = serd_string("/d/f.txt");
+  const SerdStringView remote_host   = serd_string("server");
+  const SerdStringView remote_string = serd_string("file://server/d/f.txt");
+
+  SerdNodes* const nodes = serd_nodes_new(allocator);
+
+  const SerdNode* const local_uri =
+    serd_nodes_get(nodes, serd_a_uri(local_string));
+  const SerdNode* const local_file_uri =
+    serd_nodes_get(nodes, serd_a_file_uri(local_path, serd_empty_string()));
+
+  assert(local_uri);
+  assert(local_file_uri);
+  assert(local_uri == local_file_uri);
+  assert(serd_node_type(local_uri) == SERD_URI);
+  assert(!serd_node_flags(local_uri));
+  assert(!serd_node_datatype(local_uri));
+  assert(!serd_node_language(local_uri));
+  assert(serd_node_length(local_uri) == local_string.length);
+  assert(!strcmp(serd_node_string(local_uri), local_string.data));
+
+  const SerdNode* const remote_uri =
+    serd_nodes_get(nodes, serd_a_uri(remote_string));
+  const SerdNode* const remote_file_uri =
+    serd_nodes_get(nodes, serd_a_file_uri(local_path, remote_host));
+
+  assert(remote_uri);
+  assert(remote_file_uri);
+  assert(remote_uri == remote_file_uri);
+  assert(serd_node_type(remote_uri) == SERD_URI);
+  assert(!serd_node_flags(remote_uri));
+  assert(!serd_node_datatype(remote_uri));
+  assert(!serd_node_language(remote_uri));
+  assert(serd_node_length(remote_uri) == remote_string.length);
+  assert(!strcmp(serd_node_string(remote_uri), remote_string.data));
+
+  serd_nodes_free(nodes);
+}
+
+static void
+test_blank(void)
+{
+  const SerdStringView string = serd_string("b42");
+
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const      nodes = serd_nodes_new(allocator);
+  const SerdNode* const node  = serd_nodes_get(nodes, serd_a_blank(string));
+
+  assert(node);
+  assert(serd_node_type(node) == SERD_BLANK);
+  assert(!serd_node_flags(node));
+  assert(!serd_node_datatype(node));
+  assert(!serd_node_language(node));
+  assert(serd_node_length(node) == string.length);
+  assert(!strcmp(serd_node_string(node), string.data));
+
+  serd_nodes_free(nodes);
+}
+
+static void
+test_deref(void)
+{
+  SerdAllocator* const allocator = serd_default_allocator();
+  SerdNodes*           nodes     = serd_nodes_new(allocator);
+
+  const SerdNode* original = serd_nodes_get(nodes, serd_a_string("node"));
+  const SerdNode* another  = serd_nodes_get(nodes, serd_a_string("node"));
+
+  assert(original == another);
+
+  // Dereference the original and ensure the other reference kept it alive
+  serd_nodes_deref(nodes, original);
+  assert(serd_node_length(another) == 4);
+  assert(!strcmp(serd_node_string(another), "node"));
+
+  // Drop the other/final reference (freeing the node)
+  serd_nodes_deref(nodes, another);
+
+  /* Intern some other irrelevant node first to (hopefully) avoid the allocator
+     just giving us back the same piece of memory. */
+
+  const SerdNode* other = serd_nodes_get(nodes, serd_a_string("XXXX"));
+  assert(!strcmp(serd_node_string(other), "XXXX"));
+
+  // Intern a new equivalent node to the original and check that it's really new
+  const SerdNode* imposter = serd_nodes_get(nodes, serd_a_string("node"));
+  assert(imposter != original);
+  assert(serd_node_length(imposter) == 4);
+  assert(!strcmp(serd_node_string(imposter), "node"));
+
+  // Check that dereferencing some random unknown node doesn't crash
+  SerdNode* unmanaged = serd_node_new(NULL, serd_a_string("unmanaged"));
+  serd_nodes_deref(nodes, unmanaged);
+  serd_node_free(NULL, unmanaged);
+
+  serd_nodes_deref(nodes, NULL);
+  serd_nodes_deref(nodes, imposter);
+  serd_nodes_deref(nodes, other);
+  serd_nodes_free(nodes);
+}
+
+static void
+test_get(void)
+{
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* nodes = serd_nodes_new(allocator);
+  SerdNode*  node  = serd_node_new(NULL, serd_a_string("node"));
+
+  assert(!serd_nodes_existing(nodes, NULL));
+  assert(!serd_nodes_existing(nodes, node));
+
+  const SerdNode* interned1 = serd_nodes_intern(nodes, node);
+  assert(serd_node_equals(node, interned1));
+  assert(serd_nodes_existing(nodes, node) == interned1);
+
+  serd_node_free(NULL, node);
+  serd_nodes_free(nodes);
+}
+
+int
+main(void)
+{
+  test_new_failed_alloc();
+  test_intern_failed_alloc();
+  test_intern();
+  test_string();
+  test_invalid_literal();
+  test_plain_literal();
+  test_typed_literal();
+  test_boolean();
+  test_decimal();
+  test_double();
+  test_float();
+  test_integer();
+  test_base64();
+  test_uri();
+  test_parsed_uri();
+  test_file_uri();
+  test_blank();
+  test_deref();
+  test_get();
+  return 0;
+}
diff --git a/test/test_statement.c b/test/test_statement.c
index fe1ce818..4cc3a0fa 100644
--- a/test/test_statement.c
+++ b/test/test_statement.c
@@ -4,7 +4,9 @@
 #undef NDEBUG
 
 #include "serd/caret.h"
+#include "serd/memory.h"
 #include "serd/node.h"
+#include "serd/nodes.h"
 #include "serd/statement.h"
 
 #include <assert.h>
@@ -15,36 +17,44 @@
 static void
 test_new(void)
 {
-  SerdNode* const u = serd_node_new(NULL, serd_a_uri_string(NS_EG "s"));
-  SerdNode* const b = serd_node_new(NULL, serd_a_blank_string("b0"));
-  SerdNode* const l = serd_node_new(NULL, serd_a_string("str"));
-
-  assert(!serd_statement_new(NULL, u, b, u, NULL, NULL));
-  assert(!serd_statement_new(NULL, l, u, u, NULL, NULL));
-  assert(!serd_statement_new(NULL, l, u, b, u, NULL));
-  assert(!serd_statement_new(NULL, u, l, b, NULL, NULL));
-  assert(!serd_statement_new(NULL, u, l, b, u, NULL));
-  assert(!serd_statement_new(NULL, u, u, u, l, NULL));
-
-  serd_node_free(NULL, l);
-  serd_node_free(NULL, b);
-  serd_node_free(NULL, u);
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  assert(!serd_statement_copy(allocator, NULL));
+
+  SerdNodes* const nodes = serd_nodes_new(allocator);
+
+  const SerdNode* const s = serd_nodes_get(nodes, serd_a_string("s"));
+  const SerdNode* const u = serd_nodes_get(nodes, serd_a_uri_string(NS_EG "u"));
+  const SerdNode* const b =
+    serd_nodes_get(nodes, serd_a_blank_string(NS_EG "b"));
+
+  // S, P, and G may not be strings (must be resources)
+  assert(!serd_statement_new(allocator, s, u, u, u, NULL));
+  assert(!serd_statement_new(allocator, u, s, u, u, NULL));
+  assert(!serd_statement_new(allocator, u, u, u, s, NULL));
+
+  // P may not be a blank node
+  assert(!serd_statement_new(allocator, u, b, u, u, NULL));
+
+  serd_nodes_free(nodes);
 }
 
 static void
 test_copy(void)
 {
+  SerdAllocator* const alloc = NULL;
+
   assert(!serd_statement_copy(NULL, NULL));
 
-  SerdNode* const f = serd_node_new(NULL, serd_a_string("file"));
-  SerdNode* const s = serd_node_new(NULL, serd_a_uri_string(NS_EG "s"));
-  SerdNode* const p = serd_node_new(NULL, serd_a_uri_string(NS_EG "p"));
-  SerdNode* const o = serd_node_new(NULL, serd_a_uri_string(NS_EG "o"));
-  SerdNode* const g = serd_node_new(NULL, serd_a_uri_string(NS_EG "g"));
+  SerdNode* const f = serd_node_new(alloc, serd_a_string("file"));
+  SerdNode* const s = serd_node_new(alloc, serd_a_uri_string(NS_EG "s"));
+  SerdNode* const p = serd_node_new(alloc, serd_a_uri_string(NS_EG "p"));
+  SerdNode* const o = serd_node_new(alloc, serd_a_uri_string(NS_EG "o"));
+  SerdNode* const g = serd_node_new(alloc, serd_a_uri_string(NS_EG "g"));
 
-  SerdCaret* const     caret     = serd_caret_new(NULL, f, 1, 1);
-  SerdStatement* const statement = serd_statement_new(NULL, s, p, o, g, caret);
-  SerdStatement* const copy      = serd_statement_copy(NULL, statement);
+  SerdCaret* const     caret     = serd_caret_new(alloc, f, 1, 1);
+  SerdStatement* const statement = serd_statement_new(alloc, s, p, o, g, caret);
+  SerdStatement* const copy      = serd_statement_copy(alloc, statement);
 
   assert(serd_statement_equals(copy, statement));
   assert(serd_caret_equals(serd_statement_caret(copy), caret));
@@ -62,20 +72,24 @@ test_copy(void)
 static void
 test_free(void)
 {
+  serd_statement_free(serd_default_allocator(), NULL);
   serd_statement_free(NULL, NULL);
 }
 
 static void
 test_fields(void)
 {
-  SerdNode* const f = serd_node_new(NULL, serd_a_string("file"));
-  SerdNode* const s = serd_node_new(NULL, serd_a_uri_string(NS_EG "s"));
-  SerdNode* const p = serd_node_new(NULL, serd_a_uri_string(NS_EG "p"));
-  SerdNode* const o = serd_node_new(NULL, serd_a_uri_string(NS_EG "o"));
-  SerdNode* const g = serd_node_new(NULL, serd_a_uri_string(NS_EG "g"));
+  SerdAllocator* const alloc = NULL;
+
+  SerdNode* const f = serd_node_new(alloc, serd_a_string("file"));
+  SerdNode* const s = serd_node_new(alloc, serd_a_uri_string(NS_EG "s"));
+  SerdNode* const p = serd_node_new(alloc, serd_a_uri_string(NS_EG "p"));
+  SerdNode* const o = serd_node_new(alloc, serd_a_uri_string(NS_EG "o"));
+  SerdNode* const g = serd_node_new(alloc, serd_a_uri_string(NS_EG "g"));
+
+  SerdCaret* const caret = serd_caret_new(alloc, f, 1, 1);
 
-  SerdCaret* const     caret     = serd_caret_new(NULL, f, 1, 1);
-  SerdStatement* const statement = serd_statement_new(NULL, s, p, o, g, caret);
+  SerdStatement* const statement = serd_statement_new(alloc, s, p, o, g, caret);
 
   assert(serd_statement_equals(statement, statement));
   assert(!serd_statement_equals(statement, NULL));
@@ -102,29 +116,29 @@ test_fields(void)
   assert(!serd_statement_matches(statement, NULL, NULL, s, NULL));
   assert(!serd_statement_matches(statement, NULL, NULL, NULL, s));
 
-  SerdStatement* const diff_s = serd_statement_new(NULL, o, p, o, g, caret);
+  SerdStatement* const diff_s = serd_statement_new(alloc, o, p, o, g, caret);
   assert(!serd_statement_equals(statement, diff_s));
-  serd_statement_free(NULL, diff_s);
+  serd_statement_free(alloc, diff_s);
 
-  SerdStatement* const diff_p = serd_statement_new(NULL, s, o, o, g, caret);
+  SerdStatement* const diff_p = serd_statement_new(alloc, s, o, o, g, caret);
   assert(!serd_statement_equals(statement, diff_p));
-  serd_statement_free(NULL, diff_p);
+  serd_statement_free(alloc, diff_p);
 
-  SerdStatement* const diff_o = serd_statement_new(NULL, s, p, s, g, caret);
+  SerdStatement* const diff_o = serd_statement_new(alloc, s, p, s, g, caret);
   assert(!serd_statement_equals(statement, diff_o));
-  serd_statement_free(NULL, diff_o);
+  serd_statement_free(alloc, diff_o);
 
-  SerdStatement* const diff_g = serd_statement_new(NULL, s, p, o, s, caret);
+  SerdStatement* const diff_g = serd_statement_new(alloc, s, p, o, s, caret);
   assert(!serd_statement_equals(statement, diff_g));
-  serd_statement_free(NULL, diff_g);
-
-  serd_statement_free(NULL, statement);
-  serd_caret_free(NULL, caret);
-  serd_node_free(NULL, g);
-  serd_node_free(NULL, o);
-  serd_node_free(NULL, p);
-  serd_node_free(NULL, s);
-  serd_node_free(NULL, f);
+  serd_statement_free(alloc, diff_g);
+
+  serd_statement_free(alloc, statement);
+  serd_caret_free(alloc, caret);
+  serd_node_free(alloc, g);
+  serd_node_free(alloc, o);
+  serd_node_free(alloc, p);
+  serd_node_free(alloc, s);
+  serd_node_free(alloc, f);
 }
 
 int
diff --git a/test/test_uri.c b/test/test_uri.c
index 7a15ffb8..294b00ec 100644
--- a/test/test_uri.c
+++ b/test/test_uri.c
@@ -7,6 +7,7 @@
 
 #include "serd/memory.h"
 #include "serd/node.h"
+#include "serd/nodes.h"
 #include "serd/string_view.h"
 #include "serd/uri.h"
 
@@ -75,8 +76,10 @@ test_file_uri(const char* const hostname,
     expected_path = path;
   }
 
-  SerdNode* node = serd_node_new(
-    NULL, serd_a_file_uri(serd_string(path), serd_string(hostname)));
+  SerdNodes* const nodes = serd_nodes_new(NULL);
+
+  const SerdNode* node = serd_nodes_get(
+    nodes, serd_a_file_uri(serd_string(path), serd_string(hostname)));
 
   const char* node_str     = serd_node_string(node);
   char*       out_hostname = NULL;
@@ -89,7 +92,7 @@ test_file_uri(const char* const hostname,
 
   serd_free(NULL, out_path);
   serd_free(NULL, out_hostname);
-  serd_node_free(NULL, node);
+  serd_nodes_free(nodes);
 }
 
 static void
@@ -231,6 +234,7 @@ check_relative_uri(const char* const uri_string,
   const SerdURIView uri    = serd_node_uri_view(uri_node);
   SerdNode* const   base_node =
     serd_node_new(NULL, serd_a_uri_string(base_string));
+
   const SerdURIView base = serd_node_uri_view(base_node);
 
   SerdNode* result_node = NULL;
@@ -246,7 +250,6 @@ check_relative_uri(const char* const uri_string,
       serd_uri_is_within(uri, root)
         ? serd_node_new(NULL, serd_a_parsed_uri(serd_relative_uri(uri, base)))
         : serd_node_new(NULL, serd_a_uri_string(uri_string));
-
     serd_node_free(NULL, root_node);
   }
 
diff --git a/test/test_writer.c b/test/test_writer.c
index 8f4fef5c..8b0d31c6 100644
--- a/test/test_writer.c
+++ b/test/test_writer.c
@@ -10,6 +10,7 @@
 #include "serd/event.h"
 #include "serd/memory.h"
 #include "serd/node.h"
+#include "serd/nodes.h"
 #include "serd/output_stream.h"
 #include "serd/sink.h"
 #include "serd/statement.h"
@@ -74,18 +75,22 @@ test_write_failed_alloc(void)
   SerdFailingAllocator allocator = serd_failing_allocator();
 
   SerdWorld*       world  = serd_world_new(&allocator.base);
+  SerdNodes*       nodes  = serd_nodes_new(&allocator.base);
   SerdEnv*         env    = serd_env_new(NULL, serd_empty_string());
   SerdBuffer       buffer = {&allocator.base, NULL, 0};
   SerdOutputStream output = serd_open_output_buffer(&buffer);
 
-  SerdNode* s  = serd_node_new(NULL, serd_a_uri_string("http://example.org/s"));
-  SerdNode* p1 = serd_node_new(NULL, serd_a_uri_string("http://example.org/p"));
+  const SerdNode* s =
+    serd_nodes_get(nodes, serd_a_uri_string("http://example.org/s"));
 
-  SerdNode* p2 = serd_node_new(
-    NULL,
+  const SerdNode* p1 =
+    serd_nodes_get(nodes, serd_a_uri_string("http://example.org/p"));
+
+  const SerdNode* p2 = serd_nodes_get(
+    nodes,
     serd_a_uri_string("http://example.org/dramatically/longer/predicate"));
 
-  SerdNode* o = serd_node_new(NULL, serd_a_blank_string("o"));
+  const SerdNode* o = serd_nodes_get(nodes, serd_a_blank_string("o"));
 
   const size_t n_setup_allocs = allocator.n_allocations;
 
@@ -122,10 +127,8 @@ test_write_failed_alloc(void)
   serd_env_free(env);
   serd_buffer_close(&buffer);
   serd_free(NULL, buffer.buf);
-  serd_node_free(NULL, o);
-  serd_node_free(NULL, p2);
-  serd_node_free(NULL, p1);
-  serd_node_free(NULL, s);
+
+  serd_nodes_free(nodes);
   serd_world_free(world);
 }