diff options
| -rw-r--r-- | ChangeLog | 1 | ||||
| -rw-r--r-- | src/sord.c | 250 | ||||
| -rw-r--r-- | src/syntax.c | 2 | ||||
| -rw-r--r-- | src/zix/common.h | 67 | ||||
| -rw-r--r-- | src/zix/hash.c | 226 | ||||
| -rw-r--r-- | src/zix/hash.h | 75 | ||||
| -rw-r--r-- | src/zix/tree.c | 590 | ||||
| -rw-r--r-- | src/zix/tree.h | 121 | ||||
| -rw-r--r-- | wscript | 22 |
9 files changed, 1211 insertions, 143 deletions
@@ -1,5 +1,6 @@ sord (UNRELEASED) unstable; urgency=low + * Remove glib dependency * Add function sord_contains for checking for a triple pattern * Add function sord_write_iter for writing a queried range * Fix Sord::Namespaces::qualify to no longer chop prefixes @@ -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 */ @@ -44,9 +44,6 @@ def configure(conf): conf.load('compiler_cxx') conf.env.append_value('CFLAGS', '-std=c99') - autowaf.check_pkg(conf, 'glib-2.0', uselib_store='GLIB', - atleast_version='2.0.0', mandatory=True) - autowaf.check_pkg(conf, 'serd-0', uselib_store='SERD', atleast_version='0.4.0', mandatory=True) @@ -97,9 +94,12 @@ def build(bld): autowaf.build_pc(bld, 'SORD', SORD_VERSION, SORD_MAJOR_VERSION, 'SERD', {'SORD_MAJOR_VERSION' : SORD_MAJOR_VERSION}) + + source = 'src/sord.c src/syntax.c src/zix/hash.c src/zix/tree.c' + # Shared Library obj = bld(features = 'c cshlib', - source = 'src/sord.c src/syntax.c', + source = source, includes = ['.', './src'], export_includes = ['.'], name = 'libsord', @@ -110,12 +110,12 @@ def build(bld): cflags = [ '-fvisibility=hidden', '-DSORD_SHARED', '-DSORD_INTERNAL' ]) - autowaf.use_lib(bld, obj, 'GLIB SERD') + autowaf.use_lib(bld, obj, 'SERD') # Static Library if bld.env['BUILD_STATIC']: obj = bld(features = 'c cstlib', - source = 'src/sord.c src/syntax.c', + source = source, includes = ['.', './src'], export_includes = ['.'], name = 'libsord_static', @@ -124,21 +124,21 @@ def build(bld): install_path = '${LIBDIR}', libs = [ 'm' ], cflags = [ '-DSORD_INTERNAL' ]) - autowaf.use_lib(bld, obj, 'GLIB SERD') + autowaf.use_lib(bld, obj, 'SERD') if bld.env['BUILD_TESTS']: test_cflags = [ '-fprofile-arcs', '-ftest-coverage' ] # Static library (for unit test code coverage) obj = bld(features = 'c cstlib', - source = 'src/sord.c src/syntax.c', + source = source, includes = ['.', './src'], name = 'libsord_static', target = 'sord_static', install_path = '', cflags = test_cflags, libs = [ 'm' ]) - autowaf.use_lib(bld, obj, 'GLIB SERD') + autowaf.use_lib(bld, obj, 'SERD') # Unit test program obj = bld(features = 'c cprogram', @@ -149,7 +149,7 @@ def build(bld): target = 'sord_test', install_path = '', cflags = test_cflags) - autowaf.use_lib(bld, obj, 'GLIB SERD') + autowaf.use_lib(bld, obj, 'SERD') # Static sordi build obj = bld(features = 'c cprogram') @@ -170,7 +170,7 @@ def build(bld): target = 'sordmm_test', install_path = '', cflags = test_cflags) - autowaf.use_lib(bld, obj, 'GLIB SERD') + autowaf.use_lib(bld, obj, 'SERD') # Static command line utility (for testing) if bld.env['BUILD_UTILS']: |