summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/sord.c250
-rw-r--r--src/syntax.c2
-rw-r--r--src/zix/common.h67
-rw-r--r--src/zix/hash.c226
-rw-r--r--src/zix/hash.h75
-rw-r--r--src/zix/tree.c590
-rw-r--r--src/zix/tree.h121
7 files changed, 1199 insertions, 132 deletions
diff --git a/src/sord.c b/src/sord.c
index eafc99f..241e5c9 100644
--- a/src/sord.c
+++ b/src/sord.c
@@ -23,8 +23,8 @@
#include <stdlib.h>
#include <string.h>
-// GLib
-#include <glib.h>
+#include "zix/hash.h"
+#include "zix/tree.h"
#include "sord-config.h"
#include "sord_internal.h"
@@ -54,7 +54,7 @@
#define DEFAULT_GRAPH_ORDER GSPO
#define TUP_FMT "(%s %s %s %s)"
-#define TUP_FMT_ELEM(e) ((e) ? sord_node_get_string(e) : "*")
+#define TUP_FMT_ELEM(e) ((e) ? sord_node_get_string(e) : (const uint8_t*)"*")
#define TUP_FMT_ARGS(t) \
TUP_FMT_ELEM((t)[0]), \
TUP_FMT_ELEM((t)[1]), \
@@ -99,10 +99,10 @@ static const int orderings[NUM_ORDERS][TUP_LEN] = {
/** World */
struct SordWorldImpl {
- GHashTable* names; ///< URI or blank node identifier string => ID
- GHashTable* langs; ///< Language tag => Interned language tag
- GHashTable* literals; ///< Literal => ID
- size_t n_nodes; ///< Number of nodes
+ ZixHash* names; ///< URI or blank node identifier string => ID
+ ZixHash* langs; ///< Language tag => Interned language tag
+ ZixHash* literals; ///< Literal => ID
+ size_t n_nodes; ///< Number of nodes
};
/** Store */
@@ -113,7 +113,7 @@ struct SordModelImpl {
* If an index for e.g. SPO exists, it is a dictionary with
* (S P O) keys (as a SordTuplrID), and ignored values.
*/
- GSequence* indices[NUM_ORDERS];
+ ZixTree* indices[NUM_ORDERS];
size_t n_quads;
};
@@ -130,7 +130,7 @@ typedef enum {
/** Iterator over some range of a store */
struct SordIterImpl {
const SordModel* sord; ///< Store this is an iterator for
- GSequenceIter* cur; ///< Current DB cursor
+ ZixTreeIter* cur; ///< Current DB cursor
SordQuad pat; ///< Iteration pattern (in ordering order)
int ordering[TUP_LEN]; ///< Store ordering
SearchMode mode; ///< Iteration mode
@@ -143,17 +143,18 @@ static unsigned
sord_literal_hash(const void* n)
{
SordNode* node = (SordNode*)n;
- return g_str_hash(node->node.buf) + (node->lang ? g_str_hash(node->lang) : 0);
+ return zix_string_hash(node->node.buf)
+ + (node->lang ? zix_string_hash(node->lang) : 0);
}
-static gboolean
+static bool
sord_literal_equal(const void* a, const void* b)
{
SordNode* a_node = (SordNode*)a;
SordNode* b_node = (SordNode*)b;
return (a_node == b_node)
- || (g_str_equal(sord_node_get_string(a_node),
- sord_node_get_string(b_node))
+ || (zix_string_equal(sord_node_get_string(a_node),
+ sord_node_get_string(b_node))
&& (a_node->lang == b_node->lang)
&& (a_node->datatype == b_node->datatype));
}
@@ -162,32 +163,39 @@ SordWorld*
sord_world_new(void)
{
SordWorld* world = malloc(sizeof(struct SordWorldImpl));
- world->names = g_hash_table_new_full(g_str_hash, g_str_equal, 0, 0);
- world->langs = g_hash_table_new_full(g_str_hash, g_str_equal, g_free, 0);
- world->literals = g_hash_table_new_full(sord_literal_hash, sord_literal_equal, 0, 0);
+ world->names = zix_hash_new(zix_string_hash, zix_string_equal);
+ world->langs = zix_hash_new(zix_string_hash, zix_string_equal);
+ world->literals = zix_hash_new(sord_literal_hash, sord_literal_equal);
world->n_nodes = 0;
return world;
}
static void
-free_hash_entry(void* key, void* value, void* user_data)
+free_node_entry(const void* key, void* value, void* user_data)
{
SordNode* node = (SordNode*)value;
if (node->node.type == SERD_LITERAL) {
sord_node_free((SordWorld*)user_data, node->datatype);
}
- g_free((uint8_t*)node->node.buf);
+ free((uint8_t*)node->node.buf);
free(node);
}
+static void
+free_lang_entry(const void* key, void* value, void* user_data)
+{
+ free(value);
+}
+
void
sord_world_free(SordWorld* world)
{
- g_hash_table_foreach(world->literals, free_hash_entry, world);
- g_hash_table_foreach(world->names, free_hash_entry, world);
- g_hash_table_unref(world->names);
- g_hash_table_unref(world->langs);
- g_hash_table_unref(world->literals);
+ zix_hash_foreach(world->literals, free_node_entry, world);
+ zix_hash_foreach(world->names, free_node_entry, world);
+ zix_hash_foreach(world->langs, free_lang_entry, world);
+ zix_hash_free(world->names);
+ zix_hash_free(world->langs);
+ zix_hash_free(world->literals);
free(world);
}
@@ -195,7 +203,7 @@ static inline int
sord_node_compare(const SordNode* a, const SordNode* b)
{
if (a == b || !a || !b) {
- return (const char*)a - (const char*)b;
+ return 0;
} else if (a->node.type != b->node.type) {
return a->node.type - b->node.type;
}
@@ -274,8 +282,9 @@ sord_quad_compare(const void* x_ptr, const void* y_ptr, void* user_data)
for (int i = 0; i < TUP_LEN; ++i) {
const int idx = ordering[i];
const int cmp = sord_node_compare(x[idx], y[idx]);
- if (cmp)
+ if (cmp) {
return cmp;
+ }
}
return 0;
@@ -285,18 +294,18 @@ static inline bool
sord_iter_forward(SordIter* iter)
{
if (!iter->skip_graphs) {
- iter->cur = g_sequence_iter_next(iter->cur);
- return g_sequence_iter_is_end(iter->cur);
+ iter->cur = zix_tree_iter_next(iter->cur);
+ return zix_tree_iter_is_end(iter->cur);
}
- SordNode** key = (SordNode**)g_sequence_get(iter->cur);
+ SordNode** key = (SordNode**)zix_tree_get(iter->cur);
const SordQuad initial = { key[0], key[1], key[2], key[3] };
while (true) {
- iter->cur = g_sequence_iter_next(iter->cur);
- if (g_sequence_iter_is_end(iter->cur))
+ iter->cur = zix_tree_iter_next(iter->cur);
+ if (zix_tree_iter_is_end(iter->cur))
return true;
- key = (SordNode**)g_sequence_get(iter->cur);
+ key = (SordNode**)zix_tree_get(iter->cur);
for (int i = 0; i < 3; ++i)
if (key[i] != initial[i])
return false;
@@ -312,9 +321,9 @@ static inline bool
sord_iter_seek_match(SordIter* iter)
{
for (iter->end = true;
- !g_sequence_iter_is_end(iter->cur);
+ !zix_tree_iter_is_end(iter->cur);
sord_iter_forward(iter)) {
- const SordNode** const key = (const SordNode**)g_sequence_get(iter->cur);
+ const SordNode** const key = (const SordNode**)zix_tree_get(iter->cur);
if (sord_quad_match_inline(key, iter->pat))
return (iter->end = false);
}
@@ -333,7 +342,7 @@ sord_iter_seek_match_range(SordIter* iter)
return true;
do {
- const SordNode** key = (const SordNode**)g_sequence_get(iter->cur);
+ const SordNode** key = (const SordNode**)zix_tree_get(iter->cur);
if (sord_quad_match_inline(key, iter->pat))
return false; // Found match
@@ -351,7 +360,7 @@ sord_iter_seek_match_range(SordIter* iter)
}
static SordIter*
-sord_iter_new(const SordModel* sord, GSequenceIter* cur, const SordQuad pat,
+sord_iter_new(const SordModel* sord, ZixTreeIter* cur, const SordQuad pat,
SordOrder order, SearchMode mode, int n_prefix)
{
const int* ordering = orderings[order];
@@ -373,7 +382,7 @@ sord_iter_new(const SordModel* sord, GSequenceIter* cur, const SordQuad pat,
case SINGLE:
case RANGE:
assert(
- sord_quad_match_inline((const SordNode**)g_sequence_get(iter->cur),
+ sord_quad_match_inline((const SordNode**)zix_tree_get(iter->cur),
iter->pat));
break;
case FILTER_RANGE:
@@ -403,7 +412,7 @@ sord_iter_get_model(SordIter* iter)
void
sord_iter_get(const SordIter* iter, SordQuad id)
{
- SordNode** key = (SordNode**)g_sequence_get(iter->cur);
+ SordNode** key = (SordNode**)zix_tree_get(iter->cur);
for (int i = 0; i < TUP_LEN; ++i) {
id[i] = key[i];
}
@@ -429,7 +438,7 @@ sord_iter_next(SordIter* iter)
case RANGE:
SORD_ITER_LOG("%p range next\n", (void*)iter);
// At the end if the MSNs no longer match
- key = (const SordNode**)g_sequence_get(iter->cur);
+ key = (const SordNode**)zix_tree_get(iter->cur);
assert(key);
for (int i = 0; i < iter->n_prefix; ++i) {
const int idx = iter->ordering[i];
@@ -573,10 +582,15 @@ sord_new(SordWorld* world, unsigned indices, bool graphs)
sord->n_quads = 0;
for (unsigned i = 0; i < (NUM_ORDERS / 2); ++i) {
+ const int* const ordering = orderings[i];
+ const int* const g_ordering = orderings[i + (NUM_ORDERS / 2)];
+
if (indices & (1 << i)) {
- sord->indices[i] = g_sequence_new(NULL);
+ sord->indices[i] = zix_tree_new(
+ false, sord_quad_compare, (void*)ordering);
if (graphs) {
- sord->indices[i + (NUM_ORDERS / 2)] = g_sequence_new(NULL);
+ sord->indices[i + (NUM_ORDERS / 2)] = zix_tree_new(
+ false, sord_quad_compare, (void*)g_ordering);
} else {
sord->indices[i + (NUM_ORDERS / 2)] = NULL;
}
@@ -587,7 +601,8 @@ sord_new(SordWorld* world, unsigned indices, bool graphs)
}
if (!sord->indices[DEFAULT_ORDER]) {
- sord->indices[DEFAULT_ORDER] = g_sequence_new(NULL);
+ sord->indices[DEFAULT_ORDER] = zix_tree_new(
+ false, sord_quad_compare, (void*)orderings[DEFAULT_ORDER]);
}
return sord;
@@ -598,18 +613,18 @@ sord_node_free_internal(SordWorld* world, SordNode* node)
{
assert(node->refs == 0);
if (node->node.type == SERD_LITERAL) {
- if (!g_hash_table_remove(world->literals, node)) {
+ if (zix_hash_remove(world->literals, node)) {
fprintf(stderr, "Failed to remove literal from hash.\n");
return;
}
sord_node_free(world, node->datatype);
} else {
- if (!g_hash_table_remove(world->names, node->node.buf)) {
+ if (zix_hash_remove(world->names, node->node.buf)) {
fprintf(stderr, "Failed to remove resource from hash.\n");
return;
}
}
- g_free((uint8_t*)node->node.buf);
+ free((uint8_t*)node->node.buf);
free(node);
}
@@ -660,16 +675,16 @@ sord_free(SordModel* sord)
sord_iter_free(i);
// Free quads
- for (GSequenceIter* i = g_sequence_get_begin_iter(sord->indices[DEFAULT_ORDER]);
- !g_sequence_iter_is_end(i);
- i = g_sequence_iter_next(i)) {
- free(g_sequence_get(i));
+ for (ZixTreeIter* i = zix_tree_begin(sord->indices[DEFAULT_ORDER]);
+ !zix_tree_iter_is_end(i);
+ i = zix_tree_iter_next(i)) {
+ free(zix_tree_get(i));
}
// Free indices
for (unsigned i = 0; i < NUM_ORDERS; ++i)
if (sord->indices[i])
- g_sequence_free(sord->indices[i]);
+ zix_tree_free(sord->indices[i]);
free(sord);
}
@@ -698,67 +713,47 @@ sord_begin(const SordModel* sord)
if (sord_num_quads(sord) == 0) {
return NULL;
} else {
- GSequenceIter* cur = g_sequence_get_begin_iter(sord->indices[DEFAULT_ORDER]);
+ ZixTreeIter* cur = zix_tree_begin(sord->indices[DEFAULT_ORDER]);
SordQuad pat = { 0, 0, 0, 0 };
return sord_iter_new(sord, cur, pat, DEFAULT_ORDER, ALL, 0);
}
}
-static inline GSequenceIter*
-index_search(GSequence* db, const SordQuad search_key, const int* ordering)
+static inline ZixTreeIter*
+index_search(ZixTree* db, const SordQuad search_key)
{
- return g_sequence_search(
- db, (void*)search_key, sord_quad_compare, (void*)ordering);
+ ZixTreeIter* iter = NULL;
+ zix_tree_find(db, (void*)search_key, &iter);
+ if (!iter) {
+ fprintf(stderr, "SEARCH FAILED\n");
+ }
+ return iter;
}
-static inline GSequenceIter*
-index_lower_bound_iter(GSequenceIter* i, const SordQuad search_key)
+static inline ZixTreeIter*
+index_lower_bound(ZixTree* db, const SordQuad search_key)
{
- /* i is now at the position where search_key would be inserted,
- but this is not necessarily a match, and we need the leftmost...
- */
-
- if (g_sequence_iter_is_begin(i)) {
- return i;
- } else if (g_sequence_iter_is_end(i)) {
- i = g_sequence_iter_prev(i);
+ ZixTreeIter* iter = NULL;
+ zix_tree_find(db, (void*)search_key, &iter);
+ if (!iter) {
+ return NULL;
}
- if (!sord_quad_match_inline(search_key, g_sequence_get(i))) {
- // No match, but perhaps immediately after a match
- GSequenceIter* const prev = g_sequence_iter_prev(i);
- if (!sord_quad_match_inline(search_key, g_sequence_get(prev))) {
- return i; // No match (caller must check)
- } else {
- i = prev;
+ ZixTreeIter* prev = NULL;
+ while ((prev = zix_tree_iter_prev(iter))) {
+ if (!prev) {
+ return iter;
}
- }
- /* i now points to some matching element,
- but not necessarily the first...
- */
- assert(sord_quad_match_inline(search_key, g_sequence_get(i)));
-
- while (!g_sequence_iter_is_begin(i)) {
- if (sord_quad_match_inline(search_key, g_sequence_get(i))) {
- GSequenceIter* const prev = g_sequence_iter_prev(i);
- if (sord_quad_match_inline(search_key, g_sequence_get(prev))) {
- i = prev;
- continue;
- }
+ const SordNode** const key = (const SordNode**)zix_tree_get(prev);
+ if (!sord_quad_match_inline(key, search_key)) {
+ return iter;
}
- break;
- }
- return i;
-}
+ iter = prev;
+ }
-static inline GSequenceIter*
-index_lower_bound(GSequence* db, const SordQuad search_key, const int* ordering)
-{
- GSequenceIter* i = g_sequence_search(
- db, (void*)search_key, sord_quad_compare, (void*)ordering);
- return index_lower_bound_iter(i, search_key);
+ return iter;
}
SordIter*
@@ -767,10 +762,9 @@ sord_find(SordModel* sord, const SordQuad pat)
if (!pat[0] && !pat[1] && !pat[2] && !pat[3])
return sord_begin(sord);
- SearchMode mode;
- int prefix_len;
- const SordOrder index_order = sord_best_index(sord, pat, &mode, &prefix_len);
- const int* const ordering = orderings[index_order];
+ SearchMode mode;
+ int prefix_len;
+ const SordOrder index_order = sord_best_index(sord, pat, &mode, &prefix_len);
SORD_FIND_LOG("Find " TUP_FMT " index=%s mode=%d prefix_len=%d ordering=%d%d%d%d\n",
TUP_FMT_ARGS(pat), order_names[index_order], mode, prefix_len,
@@ -779,13 +773,13 @@ sord_find(SordModel* sord, const SordQuad pat)
if (pat[0] && pat[1] && pat[2] && pat[3])
mode = SINGLE; // No duplicate quads (Sord is a set)
- GSequence* const db = sord->indices[index_order];
- GSequenceIter* const cur = index_lower_bound(db, pat, ordering);
- if (g_sequence_iter_is_end(cur)) {
+ ZixTree* const db = sord->indices[index_order];
+ ZixTreeIter* const cur = index_lower_bound(db, pat);
+ if (zix_tree_iter_is_end(cur)) {
SORD_FIND_LOG("No match found\n");
return NULL;
}
- const SordNode** const key = (const SordNode**)g_sequence_get(cur);
+ const SordNode** const key = (const SordNode**)zix_tree_get(cur);
if (!key || ( (mode == RANGE || mode == SINGLE)
&& !sord_quad_match_inline(pat, key) )) {
SORD_FIND_LOG("No match found\n");
@@ -807,7 +801,15 @@ sord_contains(SordModel* sord, const SordQuad pat)
static SordNode*
sord_lookup_name(SordWorld* world, const uint8_t* str)
{
- return g_hash_table_lookup(world->names, str);
+ return zix_hash_find(world->names, str);
+}
+
+char*
+sord_strndup(const char* str, size_t len)
+{
+ char* dup = malloc(len + 1);
+ memcpy(dup, str, len + 1);
+ return dup;
}
static SordNode*
@@ -820,7 +822,7 @@ sord_new_node(SerdType type, const uint8_t* data,
node->datatype = datatype;
node->refs = 1;
node->refs_as_obj = 0;
- node->node.buf = (uint8_t*)g_strdup((const char*)data);
+ node->node.buf = (uint8_t*)sord_strndup((const char*)data, n_bytes);
node->node.n_bytes = n_bytes;
node->node.n_chars = n_chars;
node->node.flags = flags;
@@ -833,10 +835,10 @@ const char*
sord_intern_lang(SordWorld* world, const char* lang)
{
if (lang) {
- char* ilang = g_hash_table_lookup(world->langs, lang);
+ char* ilang = zix_hash_find(world->langs, lang);
if (!ilang) {
- ilang = g_strdup(lang);
- g_hash_table_insert(world->langs, ilang, ilang);
+ ilang = sord_strndup(lang, strlen(lang));
+ zix_hash_insert(world->langs, ilang, ilang);
}
lang = ilang;
}
@@ -859,7 +861,7 @@ sord_lookup_literal(SordWorld* world, SordNode* type,
key.node.flags = 0;
key.node.type = SERD_LITERAL;
- SordNode* id = g_hash_table_lookup(world->literals, &key);
+ SordNode* id = zix_hash_find(world->literals, &key);
if (id) {
return id;
} else {
@@ -937,8 +939,8 @@ sord_new_uri_counted(SordWorld* world, const uint8_t* str,
}
node = sord_new_node(SERD_URI, str, n_bytes, n_chars, 0, 0, 0);
- assert(!g_hash_table_lookup(world->names, node->node.buf));
- g_hash_table_insert(world->names, (char*)node->node.buf, node);
+ assert(!zix_hash_find(world->names, node->node.buf));
+ zix_hash_insert(world->names, (char*)node->node.buf, node);
sord_add_node(world, node);
return node;
}
@@ -961,7 +963,7 @@ sord_new_blank_counted(SordWorld* world, const uint8_t* str,
}
node = sord_new_node(SERD_BLANK, str, n_bytes, n_chars, 0, 0, 0);
- g_hash_table_insert(world->names, (char*)node->node.buf, node);
+ zix_hash_insert(world->names, (char*)node->node.buf, node);
sord_add_node(world, node);
return node;
}
@@ -989,7 +991,7 @@ sord_new_literal_counted(SordWorld* world, SordNode* datatype,
node = sord_new_node(SERD_LITERAL,
str, n_bytes, n_chars, flags,
sord_node_copy(datatype), lang);
- g_hash_table_insert(world->literals, node, node); // FIXME: correct?
+ zix_hash_insert(world->literals, node, node); // FIXME: correct?
sord_add_node(world, node);
assert(node->refs == 1);
return node;
@@ -1103,17 +1105,7 @@ sord_node_copy(const SordNode* node)
static inline bool
sord_add_to_index(SordModel* sord, const SordNode** tup, SordOrder order)
{
- assert(sord->indices[order]);
- const int* const ordering = orderings[order];
- GSequenceIter* const cur = index_search(sord->indices[order], tup, ordering);
- GSequenceIter* const match = index_lower_bound_iter(cur, tup);
- if (!g_sequence_iter_is_end(match)
- && !sord_quad_compare(g_sequence_get(match), tup, (void*)ordering)) {
- return false; // Quad already stored in this index
- }
-
- g_sequence_insert_before(cur, tup);
- return true;
+ return !zix_tree_insert(sord->indices[order], tup, NULL);
}
bool
@@ -1142,7 +1134,7 @@ sord_add(SordModel* sord, const SordQuad tup)
sord_add_quad_ref(sord, tup[i], i);
++sord->n_quads;
- assert(sord->n_quads == (size_t)g_sequence_get_length(sord->indices[SPO]));
+ //assert(sord->n_quads == (size_t)zix_tree_get_length(sord->indices[SPO]));
return true;
}
@@ -1154,14 +1146,12 @@ sord_remove(SordModel* sord, const SordQuad tup)
SordNode** quad = NULL;
for (unsigned i = 0; i < NUM_ORDERS; ++i) {
if (sord->indices[i]) {
- const int* const ordering = orderings[i];
- GSequenceIter* const cur = index_lower_bound(
- sord->indices[i], tup, ordering);
- if (!g_sequence_iter_is_end(cur)) {
+ ZixTreeIter* const cur = index_search(sord->indices[i], tup);
+ if (!zix_tree_iter_is_end(cur)) {
if (!quad) {
- quad = g_sequence_get(cur);
+ quad = zix_tree_get(cur);
}
- g_sequence_remove(cur);
+ zix_tree_remove(sord->indices[i], cur);
} else {
assert(i == 0); // Assuming index coherency
return; // Quad not found, do nothing
diff --git a/src/syntax.c b/src/syntax.c
index ac87ad4..d7e4195 100644
--- a/src/syntax.c
+++ b/src/syntax.c
@@ -18,8 +18,6 @@
#include <stdlib.h>
#include <string.h>
-#include <glib.h>
-
#include "serd/serd.h"
#include "sord-config.h"
diff --git a/src/zix/common.h b/src/zix/common.h
new file mode 100644
index 0000000..a7edf76
--- /dev/null
+++ b/src/zix/common.h
@@ -0,0 +1,67 @@
+/*
+ Copyright 2011 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.
+*/
+
+#ifndef ZIX_COMMON_H
+#define ZIX_COMMON_H
+
+#include <stdbool.h>
+
+/**
+ @addtogroup zix
+ @{
+*/
+
+/** @cond */
+#ifdef ZIX_SHARED
+# ifdef __WIN32__
+# define ZIX_LIB_IMPORT __declspec(dllimport)
+# define ZIX_LIB_EXPORT __declspec(dllexport)
+# else
+# define ZIX_LIB_IMPORT __attribute__((visibility("default")))
+# define ZIX_LIB_EXPORT __attribute__((visibility("default")))
+# endif
+# ifdef ZIX_INTERNAL
+# define ZIX_API ZIX_LIB_EXPORT
+# else
+# define ZIX_API ZIX_LIB_IMPORT
+# endif
+#else
+# define ZIX_API
+#endif
+/** @endcond */
+
+typedef enum {
+ ZIX_STATUS_SUCCESS,
+ ZIX_STATUS_ERROR,
+ ZIX_STATUS_NO_MEM,
+ ZIX_STATUS_NOT_FOUND,
+ ZIX_STATUS_EXISTS,
+} ZixStatus;
+
+/**
+ Function for comparing two elements.
+*/
+typedef int (*ZixComparator)(const void* a, const void* b, void* user_data);
+
+/**
+ Function for testing equality of two elements.
+*/
+typedef bool (*ZixEqualFunc)(const void* a, const void* b);
+
+/**@}
+*/
+
+#endif /* ZIX_COMMON_H */
diff --git a/src/zix/hash.c b/src/zix/hash.c
new file mode 100644
index 0000000..c267757
--- /dev/null
+++ b/src/zix/hash.c
@@ -0,0 +1,226 @@
+/*
+ Copyright 2011 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 <assert.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "zix/hash.h"
+
+/**
+ Primes, each slightly less than twice its predecessor, and as far away
+ from powers of two as possible.
+*/
+static const unsigned sizes[] = {
+ 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317,
+ 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843,
+ 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 0
+};
+
+typedef struct _Entry {
+ const void* key; ///< Hash key
+ void* data; ///< Value
+ struct _Entry* next; ///< Next entry in bucket
+ unsigned hash; ///< Non-modulo hash value (for cheap rehash)
+} Entry;
+
+struct ZixHashImpl {
+ ZixHashFunc hash_func;
+ ZixEqualFunc key_equal_func;
+ Entry** buckets;
+ const unsigned* n_buckets;
+ unsigned count;
+};
+
+ZixHash*
+zix_hash_new(ZixHashFunc hash_func,
+ ZixEqualFunc key_equal_func)
+
+{
+ ZixHash* hash = (ZixHash*)malloc(sizeof(ZixHash));
+ hash->hash_func = hash_func;
+ hash->key_equal_func = key_equal_func;
+ hash->count = 0;
+ hash->n_buckets = &sizes[0];
+ hash->buckets = malloc(*hash->n_buckets * sizeof(Entry*));
+ memset(hash->buckets, 0, *hash->n_buckets * sizeof(Entry*));
+
+ return hash;
+}
+
+void
+zix_hash_free(ZixHash* hash)
+{
+ for (unsigned b = 0; b < *hash->n_buckets; ++b) {
+ Entry* bucket = hash->buckets[b];
+ for (Entry* e = bucket; e;) {
+ Entry* next = e->next;
+ free(e);
+ e = next;
+ }
+ }
+
+ free(hash->buckets);
+ free(hash);
+}
+
+unsigned
+zix_string_hash(const void* key)
+{
+ // Trusty old DJB hash
+ const char* str = (const char*)key;
+ unsigned h = 5381;
+ for (const char* s = str; *s != '\0'; ++s) {
+ h = (h << 5) + h + *s; // h = h * 33 + c
+ }
+ return h;
+}
+
+bool
+zix_string_equal(const void* a, const void* b)
+{
+ return !strcmp((const char*)a, (const char*)b);
+}
+
+static void
+insert_entry(Entry** bucket,
+ Entry* entry)
+{
+ entry->next = *bucket;
+ *bucket = entry;
+}
+
+static ZixStatus
+rehash(ZixHash* hash, unsigned new_n_buckets)
+{
+ Entry** new_buckets = (Entry**)malloc(new_n_buckets * sizeof(Entry*));
+ if (!new_buckets) {
+ return ZIX_STATUS_NO_MEM;
+ }
+
+ memset(new_buckets, 0, new_n_buckets * sizeof(Entry*));
+
+ for (unsigned b = 0; b < *hash->n_buckets; ++b) {
+ for (Entry* e = hash->buckets[b]; e;) {
+ Entry* const next = e->next;
+ const unsigned h = e->hash % new_n_buckets;
+ insert_entry(&new_buckets[h], e);
+ e = next;
+ }
+ }
+
+ free(hash->buckets);
+ hash->buckets = new_buckets;
+
+ return ZIX_STATUS_SUCCESS;
+}
+
+static Entry*
+find_entry(const ZixHash* hash,
+ const void* key,
+ unsigned h)
+{
+ for (Entry* e = hash->buckets[h]; e; e = e->next) {
+ if (hash->key_equal_func(e->key, key)) {
+ return e;
+ }
+ }
+
+ return NULL;
+}
+
+void*
+zix_hash_find(const ZixHash* hash, const void* key)
+{
+ const unsigned h = hash->hash_func(key) % *hash->n_buckets;
+ Entry* const entry = find_entry(hash, key, h);
+ return entry ? entry->data : 0;
+}
+
+ZixStatus
+zix_hash_insert(ZixHash* hash, const void* key, void* data)
+{
+ unsigned h_nomod = hash->hash_func(key);
+ unsigned h = h_nomod % *hash->n_buckets;
+
+ Entry* elem = find_entry(hash, key, h);
+ if (elem) {
+ assert(elem->hash == h_nomod);
+ return ZIX_STATUS_EXISTS;
+ }
+
+ elem = (Entry*)malloc(sizeof(Entry));
+ if (!elem) {
+ return ZIX_STATUS_NO_MEM;
+ }
+ elem->key = key;
+ elem->data = data;
+ elem->next = NULL;
+ elem->hash = h_nomod;
+ const unsigned next_n_buckets = *(hash->n_buckets + 1);
+ if (next_n_buckets != 0 && (hash->count + 1) >= next_n_buckets) {
+ if (!rehash(hash, next_n_buckets)) {
+ h = h_nomod % *(++hash->n_buckets);
+ }
+ }
+
+ insert_entry(&hash->buckets[h], elem);
+ ++hash->count;
+ return ZIX_STATUS_SUCCESS;
+}
+
+ZixStatus
+zix_hash_remove(ZixHash* hash, const void* key)
+{
+ unsigned h = hash->hash_func(key) % *hash->n_buckets;
+
+ Entry** next_ptr = &hash->buckets[h];
+ for (Entry* e = hash->buckets[h]; e; e = e->next) {
+ if (hash->key_equal_func(e->key, key)) {
+ *next_ptr = e->next;
+ free(e);
+ return ZIX_STATUS_SUCCESS;
+ }
+ next_ptr = &e->next;
+ }
+
+ if (hash->n_buckets != sizes) {
+ const unsigned prev_n_buckets = *(hash->n_buckets - 1);
+ if (hash->count - 1 <= prev_n_buckets) {
+ if (!rehash(hash, prev_n_buckets)) {
+ --hash->n_buckets;
+ }
+ }
+ }
+
+ --hash->count;
+ return ZIX_STATUS_NOT_FOUND;
+}
+
+ZIX_API
+void
+zix_hash_foreach(const ZixHash* hash,
+ void (*f)(const void* key, void* value, void* user_data),
+ void* user_data)
+{
+ for (unsigned b = 0; b < *hash->n_buckets; ++b) {
+ Entry* bucket = hash->buckets[b];
+ for (Entry* e = bucket; e; e = e->next) {
+ f(e->key, e->data, user_data);
+ }
+ }
+}
+
diff --git a/src/zix/hash.h b/src/zix/hash.h
new file mode 100644
index 0000000..44521f1
--- /dev/null
+++ b/src/zix/hash.h
@@ -0,0 +1,75 @@
+/*
+ Copyright 2011 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.
+*/
+
+#ifndef ZIX_HASH_H
+#define ZIX_HASH_H
+
+#include "zix/common.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+typedef struct ZixHashImpl ZixHash;
+
+/**
+ Function for computing the hash of an element.
+*/
+typedef unsigned (*ZixHashFunc)(const void* key);
+
+ZIX_API
+ZixHash*
+zix_hash_new(ZixHashFunc hash_func,
+ ZixEqualFunc key_equal_func);
+
+ZIX_API
+void
+zix_hash_free(ZixHash* hash);
+
+ZIX_API
+unsigned
+zix_string_hash(const void* key);
+
+ZIX_API
+bool
+zix_string_equal(const void* a, const void* b);
+
+ZIX_API
+ZixStatus
+zix_hash_insert(ZixHash* hash,
+ const void* key,
+ void* data);
+
+ZIX_API
+ZixStatus
+zix_hash_remove(ZixHash* hash, const void* key);
+
+ZIX_API
+void*
+zix_hash_find(const ZixHash* hash,
+ const void* key);
+
+ZIX_API
+void
+zix_hash_foreach(const ZixHash* hash,
+ void (*f)(const void* key, void* value, void* user_data),
+ void* user_data);
+
+#ifdef __cplusplus
+} /* extern "C" */
+#endif
+
+#endif /* ZIX_HASH_H */
diff --git a/src/zix/tree.c b/src/zix/tree.c
new file mode 100644
index 0000000..30ac3e2
--- /dev/null
+++ b/src/zix/tree.c
@@ -0,0 +1,590 @@
+/*
+ Copyright 2011 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 <assert.h>
+#include <inttypes.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "zix/common.h"
+#include "zix/tree.h"
+
+typedef struct ZixTreeNodeImpl ZixTreeNode;
+
+struct ZixTreeImpl {
+ ZixTreeNode* root;
+ ZixComparator cmp;
+ void* cmp_data;
+ bool allow_duplicates;
+};
+
+struct ZixTreeNodeImpl {
+ void* data;
+ struct ZixTreeNodeImpl* left;
+ struct ZixTreeNodeImpl* right;
+ struct ZixTreeNodeImpl* parent;
+ int_fast8_t balance;
+};
+
+#define MIN(a, b) (((a) < (b)) ? (a) : (b))
+#define MAX(a, b) (((a) > (b)) ? (a) : (b))
+
+ZIX_API
+ZixTree*
+zix_tree_new(bool allow_duplicates, ZixComparator cmp, void* cmp_data)
+{
+ ZixTree* t = malloc(sizeof(ZixTree));
+ t->root = NULL;
+ t->cmp = cmp;
+ t->cmp_data = cmp_data;
+ t->allow_duplicates = allow_duplicates;
+ return t;
+}
+
+static void
+zix_tree_free_rec(ZixTreeNode* n)
+{
+ if (n) {
+ zix_tree_free_rec(n->left);
+ zix_tree_free_rec(n->right);
+ free(n);
+ }
+}
+
+ZIX_API
+void
+zix_tree_free(ZixTree* t)
+{
+ zix_tree_free_rec(t->root);
+
+ free(t);
+}
+
+static void
+rotate(ZixTreeNode* p, ZixTreeNode* q)
+{
+ assert(q->parent == p);
+ assert(p->left == q || p->right == q);
+
+ q->parent = p->parent;
+ if (q->parent) {
+ if (q->parent->left == p) {
+ q->parent->left = q;
+ } else {
+ q->parent->right = q;
+ }
+ }
+
+ if (p->right == q) {
+ // Rotate left
+ p->right = q->left;
+ q->left = p;
+ if (p->right) {
+ p->right->parent = p;
+ }
+ } else {
+ // Rotate right
+ assert(p->left == q);
+ p->left = q->right;
+ q->right = p;
+ if (p->left) {
+ p->left->parent = p;
+ }
+ }
+
+ p->parent = q;
+}
+
+/**
+ * Rotate left about @a p.
+ *
+ * p q
+ * / \ / \
+ * A q => p C
+ * / \ / \
+ * B C A B
+ */
+static ZixTreeNode*
+rotate_left(ZixTreeNode* p, int* height_change)
+{
+ ZixTreeNode* const q = p->right;
+ *height_change = (q->balance == 0) ? 0 : -1;
+
+ assert(p->balance == 2);
+ assert(q->balance == 0 || q->balance == 1);
+
+ rotate(p, q);
+
+ --q->balance;
+ p->balance = -(q->balance);
+
+ return q;
+}
+
+/**
+ * Rotate right about @a p.
+ *
+ * p q
+ * / \ / \
+ * q C => A p
+ * / \ / \
+ * A B B C
+ *
+ */
+static ZixTreeNode*
+rotate_right(ZixTreeNode* p, int* height_change)
+{
+ ZixTreeNode* const q = p->left;
+ *height_change = (q->balance == 0) ? 0 : -1;
+
+ assert(p->balance == -2);
+ assert(q->balance == 0 || q->balance == -1);
+
+ rotate(p, q);
+
+ ++q->balance;
+ p->balance = -(q->balance);
+
+ return q;
+}
+
+/**
+ * Rotate left about @a p->left then right about @a p.
+ *
+ * p r
+ * / \ / \
+ * q D => q p
+ * / \ / \ / \
+ * A r A B C D
+ * / \
+ * B C
+ *
+ */
+static ZixTreeNode*
+rotate_left_right(ZixTreeNode* p, int* height_change)
+{
+ ZixTreeNode* const q = p->left;
+ ZixTreeNode* const r = q->right;
+
+ assert(p->balance == -2);
+ assert(q->balance == 1);
+ assert(r->balance == -1 || r->balance == 0 || r->balance == 1);
+
+ rotate(q, r);
+ rotate(p, r);
+
+ q->balance -= 1 + MAX(0, r->balance);
+ p->balance += 1 - MIN(MIN(0, r->balance) - 1, r->balance + q->balance);
+ r->balance = 0;
+
+ *height_change = -1;
+
+ return r;
+}
+
+/**
+ * Rotate right about @a p->right then right about @a p.
+ *
+ * p r
+ * / \ / \
+ * A q => p q
+ * / \ / \ / \
+ * r D A B C D
+ * / \
+ * B C
+ *
+ */
+static ZixTreeNode*
+rotate_right_left(ZixTreeNode* p, int* height_change)
+{
+ ZixTreeNode* const q = p->right;
+ ZixTreeNode* const r = q->left;
+
+ assert(p->balance == 2);
+ assert(q->balance == -1);
+ assert(r->balance == -1 || r->balance == 0 || r->balance == 1);
+
+ rotate(q, r);
+ rotate(p, r);
+
+ q->balance += 1 - MIN(0, r->balance);
+ p->balance -= 1 + MAX(MAX(0, r->balance) + 1, r->balance + q->balance);
+ r->balance = 0;
+
+ *height_change = -1;
+
+ return r;
+}
+
+static ZixTreeNode*
+zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change)
+{
+ *height_change = 0;
+ const bool is_root = !node->parent;
+ assert((is_root && t->root == node) || (!is_root && t->root != node));
+ ZixTreeNode* replacement = node;
+ if (node->balance == -2) {
+ assert(node->left);
+ if (node->left->balance == 1) {
+ replacement = rotate_left_right(node, height_change);
+ } else {
+ replacement = rotate_right(node, height_change);
+ }
+ } else if (node->balance == 2) {
+ assert(node->right);
+ if (node->right->balance == -1) {
+ replacement = rotate_right_left(node, height_change);
+ } else {
+ replacement = rotate_left(node, height_change);
+ }
+ }
+ if (is_root) {
+ assert(!replacement->parent);
+ t->root = replacement;
+ }
+
+ return replacement;
+}
+
+ZIX_API
+ZixStatus
+zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti)
+{
+ int cmp = 0;
+ ZixTreeNode* n = t->root;
+ ZixTreeNode* p = NULL;
+
+ // Find the parent p of e
+ while (n) {
+ p = n;
+ cmp = t->cmp(e, n->data, t->cmp_data);
+ if (cmp < 0) {
+ n = n->left;
+ } else if (cmp > 0) {
+ n = n->right;
+ } else if (t->allow_duplicates) {
+ n = n->right;
+ } else {
+ if (ti) {
+ *ti = n;
+ }
+ return ZIX_STATUS_EXISTS;
+ }
+ }
+
+ // Allocate a new node n
+ if (!(n = malloc(sizeof(ZixTreeNode)))) {
+ return ZIX_STATUS_NO_MEM;
+ }
+ memset(n, '\0', sizeof(ZixTreeNode));
+ n->data = e;
+ n->balance = 0;
+ if (ti) {
+ *ti = n;
+ }
+
+ bool p_height_increased = false;
+
+ // Make p the parent of n
+ n->parent = p;
+ if (!p) {
+ t->root = n;
+ } else {
+ if (cmp < 0) {
+ assert(!p->left);
+ assert(p->balance == 0 || p->balance == 1);
+ p->left = n;
+ --p->balance;
+ p_height_increased = !p->right;
+ } else {
+ assert(!p->right);
+ assert(p->balance == 0 || p->balance == -1);
+ p->right = n;
+ ++p->balance;
+ p_height_increased = !p->left;
+ }
+ }
+
+ // Rebalance if necessary (at most 1 rotation)
+ assert(!p || p->balance == -1 || p->balance == 0 || p->balance == 1);
+ if (p && p_height_increased) {
+ int height_change = 0;
+ for (ZixTreeNode* i = p; i && i->parent; i = i->parent) {
+ if (i == i->parent->left) {
+ if (--i->parent->balance == -2) {
+ zix_tree_rebalance(t, i->parent, &height_change);
+ break;
+ }
+ } else {
+ assert(i == i->parent->right);
+ if (++i->parent->balance == 2) {
+ zix_tree_rebalance(t, i->parent, &height_change);
+ break;
+ }
+ }
+
+ if (i->parent->balance == 0) {
+ break;
+ }
+ }
+ }
+
+ return ZIX_STATUS_SUCCESS;
+}
+
+ZIX_API
+ZixStatus
+zix_tree_remove(ZixTree* t, ZixTreeIter* ti)
+{
+ ZixTreeNode* const n = ti;
+ ZixTreeNode** pp = NULL; // parent pointer
+ ZixTreeNode* to_balance = n->parent; // lowest node to balance
+ int8_t d_balance = 0; // delta(balance) for n->parent
+
+ if ((n == t->root) && !n->left && !n->right) {
+ t->root = NULL;
+ free(n);
+ return ZIX_STATUS_SUCCESS;
+ }
+
+ // Set pp to the parent pointer to n, if applicable
+ if (n->parent) {
+ assert(n->parent->left == n || n->parent->right == n);
+ if (n->parent->left == n) { // n is left child
+ pp = &n->parent->left;
+ d_balance = 1;
+ } else { // n is right child
+ assert(n->parent->right == n);
+ pp = &n->parent->right;
+ d_balance = -1;
+ }
+ }
+
+ assert(!pp || *pp == n);
+
+ int height_change = 0;
+ if (!n->left && !n->right) {
+ // n is a leaf, just remove it
+ if (pp) {
+ *pp = NULL;
+ to_balance = n->parent;
+ height_change = (!n->parent->left && !n->parent->right) ? -1 : 0;
+ }
+ } else if (!n->left) {
+ // Replace n with right (only) child
+ if (pp) {
+ *pp = n->right;
+ to_balance = n->parent;
+ } else {
+ t->root = n->right;
+ }
+ n->right->parent = n->parent;
+ height_change = -1;
+ } else if (!n->right) {
+ // Replace n with left (only) child
+ if (pp) {
+ *pp = n->left;
+ to_balance = n->parent;
+ } else {
+ t->root = n->left;
+ }
+ n->left->parent = n->parent;
+ height_change = -1;
+ } else {
+ // Replace n with in-order successor (leftmost child of right subtree)
+ ZixTreeNode* replace = n->right;
+ while (replace->left) {
+ assert(replace->left->parent == replace);
+ replace = replace->left;
+ }
+
+ // Remove replace from parent (replace_p)
+ if (replace->parent->left == replace) {
+ height_change = replace->parent->right ? 0 : -1;
+ d_balance = 1;
+ to_balance = replace->parent;
+ replace->parent->left = replace->right;
+ } else {
+ assert(replace->parent == n);
+ height_change = replace->parent->left ? 0 : -1;
+ d_balance = -1;
+ to_balance = replace->parent;
+ replace->parent->right = replace->right;
+ }
+
+ if (to_balance == n) {
+ to_balance = replace;
+ }
+
+ if (replace->right) {
+ replace->right->parent = replace->parent;
+ }
+
+ replace->balance = n->balance;
+
+ // Swap node to delete with replace
+ if (pp) {
+ *pp = replace;
+ } else {
+ assert(t->root == n);
+ t->root = replace;
+ }
+ replace->parent = n->parent;
+ replace->left = n->left;
+ n->left->parent = replace;
+ replace->right = n->right;
+ if (n->right) {
+ n->right->parent = replace;
+ }
+
+ assert(!replace->parent
+ || replace->parent->left == replace
+ || replace->parent->right == replace);
+ }
+
+ // Rebalance starting at to_balance upwards.
+ for (ZixTreeNode* i = to_balance; i; i = i->parent) {
+ i->balance += d_balance;
+ if (d_balance == 0 || i->balance == -1 || i->balance == 1) {
+ break;
+ }
+
+ assert(i != n);
+ i = zix_tree_rebalance(t, i, &height_change);
+ if (i->balance == 0) {
+ height_change = -1;
+ }
+
+ if (i->parent) {
+ if (i == i->parent->left) {
+ d_balance = height_change * -1;
+ } else {
+ assert(i == i->parent->right);
+ d_balance = height_change;
+ }
+ }
+ }
+
+ free(n);
+
+ return ZIX_STATUS_SUCCESS;
+}
+
+ZIX_API
+ZixStatus
+zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti)
+{
+ ZixTreeNode* n = t->root;
+ while (n) {
+ const int cmp = t->cmp(e, n->data, t->cmp_data);
+ if (cmp == 0) {
+ break;
+ } else if (cmp < 0) {
+ n = n->left;
+ } else {
+ n = n->right;
+ }
+ }
+
+ *ti = n;
+ return (n) ? ZIX_STATUS_SUCCESS : ZIX_STATUS_NOT_FOUND;
+}
+
+ZIX_API
+void*
+zix_tree_get(ZixTreeIter* ti)
+{
+ return ti->data;
+}
+
+ZIX_API
+ZixTreeIter*
+zix_tree_begin(ZixTree* t)
+{
+ if (!t->root) {
+ return NULL;
+ }
+
+ ZixTreeNode* n = t->root;
+ while (n->left) {
+ n = n->left;
+ }
+ return n;
+}
+
+ZIX_API
+ZixTreeIter*
+zix_tree_end(ZixTree* t)
+{
+ return NULL;
+}
+
+ZIX_API
+bool
+zix_tree_iter_is_end(ZixTreeIter* i)
+{
+ return !i;
+}
+
+ZIX_API
+ZixTreeIter*
+zix_tree_iter_next(ZixTreeIter* i)
+{
+ if (!i) {
+ return NULL;
+ }
+
+ if (i->right) {
+ i = i->right;
+ while (i->left) {
+ i = i->left;
+ }
+ } else {
+ while (i->parent && i->parent->right == i) { // i is a right child
+ i = i->parent;
+ }
+
+ i = i->parent;
+ }
+
+ return i;
+}
+
+ZIX_API
+ZixTreeIter*
+zix_tree_iter_prev(ZixTreeIter* i)
+{
+ if (!i) {
+ return NULL;
+ }
+
+ if (i->left) {
+ i = i->left;
+ while (i->right) {
+ i = i->right;
+ }
+ } else {
+ while (i->parent && i->parent->left == i) { // i is a left child
+ i = i->parent;
+ }
+
+ i = i->parent;
+ }
+
+ return i;
+}
diff --git a/src/zix/tree.h b/src/zix/tree.h
new file mode 100644
index 0000000..670c437
--- /dev/null
+++ b/src/zix/tree.h
@@ -0,0 +1,121 @@
+/*
+ Copyright 2011 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.
+*/
+
+#ifndef ZIX_TREE_H
+#define ZIX_TREE_H
+
+#include <stdbool.h>
+
+#include "zix/common.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/**
+ @addtogroup zix
+ @{
+ @name Tree
+ @{
+*/
+
+/**
+ A balanced binary search tree.
+*/
+typedef struct ZixTreeImpl ZixTree;
+
+/**
+ An iterator over a @ref ZixTree.
+*/
+typedef struct ZixTreeNodeImpl ZixTreeIter;
+
+/**
+ Create a new (empty) tree.
+*/
+ZixTree*
+zix_tree_new(bool allow_duplicates, ZixComparator cmp, void* cmp_data);
+
+/**
+ Free @a t.
+*/
+void
+zix_tree_free(ZixTree* t);
+
+/**
+ Insert the element @a e into @a t and point @a ti at the new element.
+*/
+ZixStatus
+zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti);
+
+/**
+ Remove the item pointed at by @a ti from @a t.
+*/
+ZixStatus
+zix_tree_remove(ZixTree* t, ZixTreeIter* ti);
+
+/**
+ Set @a ti to an element equal to @a e in @a t.
+ If no such item exists, @a ti is set to NULL.
+*/
+ZixStatus
+zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti);
+
+/**
+ Return the data associated with the given tree item.
+*/
+void*
+zix_tree_get(ZixTreeIter* ti);
+
+/**
+ Return an iterator to the first (smallest) element in @a t.
+*/
+ZixTreeIter*
+zix_tree_begin(ZixTree* t);
+
+/**
+ Return an iterator the the element one past the last element in @a t.
+*/
+ZixTreeIter*
+zix_tree_end(ZixTree* t);
+
+/**
+ Return true iff @a i is an iterator to the end of its tree.
+*/
+bool
+zix_tree_iter_is_end(ZixTreeIter* i);
+
+/**
+ Return an iterator that points to the element one past @a i.
+*/
+ZixTreeIter*
+zix_tree_iter_next(ZixTreeIter* i);
+
+/**
+ Return an iterator that points to the element one before @a i.
+*/
+ZixTreeIter*
+zix_tree_iter_prev(ZixTreeIter* i);
+
+/**
+ @}
+ @}
+*/
+
+#ifdef __cplusplus
+} /* extern "C" */
+#endif
+
+#endif /* ZIX_TREE_H */
generated by cgit v1.2.1 (git 2.18.0) at 2024-11-13 23:42:38 +0000