From 955be33cead7596506cf86211da6b0e53827ef96 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Thu, 22 Jul 2021 18:35:31 -0400 Subject: Avoid dynamic allocation when fetching interned nodes This is more or less a total rewrite of SerdNodes and the underlying ZixHash to make efficient use of the new node construction API. --- src/nodes.h | 69 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 69 insertions(+) create mode 100644 src/nodes.h (limited to 'src/nodes.h') diff --git a/src/nodes.h b/src/nodes.h new file mode 100644 index 00000000..b39bac66 --- /dev/null +++ b/src/nodes.h @@ -0,0 +1,69 @@ +/* + Copyright 2021 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. +*/ + +/* + 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_NODES_H +#define SERD_NODES_H + +#include "node.h" + +#include "serd/serd.h" + +#include + +/** + 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_NODES_H -- cgit v1.2.1