diff options
| -rw-r--r-- | ChangeLog | 1 | ||||
| -rw-r--r-- | src/collections.c | 44 | ||||
| -rw-r--r-- | src/lilv_internal.h | 20 | ||||
| -rw-r--r-- | src/plugin.c | 15 | ||||
| -rw-r--r-- | src/pluginclass.c | 14 | ||||
| -rw-r--r-- | src/port.c | 2 | ||||
| -rw-r--r-- | src/query.c | 9 | ||||
| -rw-r--r-- | src/ui.c | 2 | ||||
| -rw-r--r-- | src/world.c | 55 | ||||
| -rw-r--r-- | src/zix/common.h | 72 | ||||
| -rw-r--r-- | src/zix/tree.c | 518 | ||||
| -rw-r--r-- | src/zix/tree.h | 149 | ||||
| -rw-r--r-- | wscript | 11 |
13 files changed, 820 insertions, 92 deletions
@@ -1,5 +1,6 @@ lilv (UNRELEASED) unstable; urgency=low + * Remove glib dependency * Add lv2core as a pkg-config dependency (for lv2.h header include) * Obey prefix when installing bash completion script * Support integer minimum, maximum, and default port values in diff --git a/src/collections.c b/src/collections.c index b969aff..fc24669 100644 --- a/src/collections.c +++ b/src/collections.c @@ -14,36 +14,40 @@ OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ -#include <glib.h> - #include "lilv_internal.h" +int +lilv_ptr_cmp(const void* a, const void* b, void* user_data) +{ + return (intptr_t)a - (intptr_t)b; +} + /* Generic collection functions */ static inline LilvCollection* -lilv_collection_new(GDestroyNotify destructor) +lilv_collection_new(ZixComparator cmp, ZixDestroyFunc destructor) { - return g_sequence_new(destructor); + return zix_tree_new(false, cmp, NULL, destructor); } void lilv_collection_free(LilvCollection* coll) { if (coll) - g_sequence_free((GSequence*)coll); + zix_tree_free((ZixTree*)coll); } unsigned lilv_collection_size(const LilvCollection* coll) { - return (coll ? g_sequence_get_length((GSequence*)coll) : 0); + return (coll ? zix_tree_size((ZixTree*)coll) : 0); } LilvIter* lilv_collection_begin(const LilvCollection* collection) { if (collection) { - return g_sequence_get_begin_iter((LilvCollection*)collection); + return zix_tree_begin((LilvCollection*)collection); } return NULL; } @@ -52,7 +56,7 @@ void* lilv_collection_get(const LilvCollection* collection, const LilvIter* i) { - return g_sequence_get((GSequenceIter*)i); + return zix_tree_get((ZixTreeIter*)i); } /* Constructors */ @@ -60,25 +64,29 @@ lilv_collection_get(const LilvCollection* collection, LilvScalePoints* lilv_scale_points_new(void) { - return lilv_collection_new((GDestroyNotify)lilv_scale_point_free); + return lilv_collection_new(lilv_ptr_cmp, + (ZixDestroyFunc)lilv_scale_point_free); } LilvNodes* lilv_nodes_new(void) { - return lilv_collection_new((GDestroyNotify)lilv_node_free); + return lilv_collection_new(lilv_ptr_cmp, + (ZixDestroyFunc)lilv_node_free); } LilvUIs* lilv_uis_new(void) { - return lilv_collection_new((GDestroyNotify)lilv_ui_free); + return lilv_collection_new(lilv_header_compare_by_uri, + (ZixDestroyFunc)lilv_ui_free); } LilvPluginClasses* lilv_plugin_classes_new(void) { - return lilv_collection_new((GDestroyNotify)lilv_plugin_class_free); + return lilv_collection_new(lilv_header_compare_by_uri, + (ZixDestroyFunc)lilv_plugin_class_free); } /* URI based accessors (for collections of things with URIs) */ @@ -88,14 +96,14 @@ const LilvPluginClass* lilv_plugin_classes_get_by_uri(const LilvPluginClasses* coll, const LilvNode* uri) { - return (LilvPluginClass*)lilv_sequence_get_by_uri(coll, uri); + return (LilvPluginClass*)lilv_collection_get_by_uri(coll, uri); } LILV_API const LilvUI* lilv_uis_get_by_uri(const LilvUIs* coll, const LilvNode* uri) { - return (LilvUI*)lilv_sequence_get_by_uri((LilvUIs*)coll, uri); + return (LilvUI*)lilv_collection_get_by_uri((LilvUIs*)coll, uri); } /* Plugins */ @@ -103,14 +111,14 @@ lilv_uis_get_by_uri(const LilvUIs* coll, const LilvNode* uri) LilvPlugins* lilv_plugins_new(void) { - return g_sequence_new(NULL); + return lilv_collection_new(lilv_header_compare_by_uri, NULL); } LILV_API const LilvPlugin* lilv_plugins_get_by_uri(const LilvPlugins* list, const LilvNode* uri) { - return (LilvPlugin*)lilv_sequence_get_by_uri((LilvPlugins*)list, uri); + return (LilvPlugin*)lilv_collection_get_by_uri((LilvPlugins*)list, uri); } /* Nodes */ @@ -131,13 +139,13 @@ lilv_nodes_contains(const LilvNodes* list, const LilvNode* value) LilvIter* lilv_iter_next(LilvIter* i) { - return g_sequence_iter_next((GSequenceIter*)i); + return zix_tree_iter_next((ZixTreeIter*)i); } bool lilv_iter_end(LilvIter* i) { - return !i || g_sequence_iter_is_end((GSequenceIter*)i); + return !i || zix_tree_iter_is_end((ZixTreeIter*)i); } #define LILV_COLLECTION_IMPL(prefix, CT, ET) \ diff --git a/src/lilv_internal.h b/src/lilv_internal.h index 770f144..03252a3 100644 --- a/src/lilv_internal.h +++ b/src/lilv_internal.h @@ -36,11 +36,11 @@ static inline char* dlerror(void) { return "Unknown error"; } # include <dlfcn.h> #endif -#include <glib.h> - #include "serd/serd.h" #include "sord/sord.h" +#include "zix/tree.h" + #include "lilv-config.h" #include "lilv/lilv.h" @@ -76,7 +76,7 @@ struct LilvSpecImpl { /** Header of an LilvPlugin, LilvPluginClass, or LilvUI. Any of these structs may be safely casted to LilvHeader, which is used to - implement sequences without code duplication (see lilv_sequence_get_by_uri). + implement collections using the same comparator. */ struct LilvHeader { LilvWorld* world; @@ -244,19 +244,11 @@ const SordNode* lilv_node_as_node(const LilvNode* value); int lilv_header_compare_by_uri(const void* a, const void* b, void* user_data); -static inline void -lilv_sequence_insert(GSequence* seq, void* value) -{ - g_sequence_insert_sorted(seq, value, lilv_header_compare_by_uri, NULL); -} - -static inline void -lilv_array_append(GSequence* seq, void* value) { - g_sequence_append(seq, value); -} +int +lilv_ptr_cmp(const void* a, const void* b, void* user_data); struct LilvHeader* -lilv_sequence_get_by_uri(const GSequence* seq, const LilvNode* uri); +lilv_collection_get_by_uri(const ZixTree* seq, const LilvNode* uri); LilvScalePoint* lilv_scale_point_new(LilvNode* value, LilvNode* label); void lilv_scale_point_free(LilvScalePoint* point); diff --git a/src/plugin.c b/src/plugin.c index f7adb18..c4233c4 100644 --- a/src/plugin.c +++ b/src/plugin.c @@ -18,6 +18,7 @@ #include <assert.h> #include <math.h> +#include <stdarg.h> #include <stdio.h> #include <stdlib.h> #include <string.h> @@ -244,9 +245,9 @@ lilv_plugin_load_ports_if_necessary(const LilvPlugin* const_p) FOREACH_MATCH(types) { const SordNode* type = lilv_match_object(types); if (sord_node_get_type(type) == SORD_URI) { - lilv_array_append( + zix_tree_insert( this_port->classes, - lilv_node_new_from_node(p->world, type)); + lilv_node_new_from_node(p->world, type), NULL); } else { LILV_WARNF("Plugin <%s> port type is not a URI\n", lilv_node_as_uri(p->plugin_uri)); @@ -619,11 +620,11 @@ lilv_plugin_get_supported_features(const LilvPlugin* p) LilvNodes* result = lilv_nodes_new(); LILV_FOREACH(nodes, i, optional) - lilv_array_append( - result, lilv_node_duplicate(lilv_nodes_get(optional, i))); + zix_tree_insert( + result, lilv_node_duplicate(lilv_nodes_get(optional, i)), NULL); LILV_FOREACH(nodes, i, required) - lilv_array_append( - result, lilv_node_duplicate(lilv_nodes_get(required, i))); + zix_tree_insert( + result, lilv_node_duplicate(lilv_nodes_get(required, i)), NULL); lilv_nodes_free(optional); lilv_nodes_free(required); @@ -780,7 +781,7 @@ lilv_plugin_get_uis(const LilvPlugin* p) type, binary); - lilv_sequence_insert(result, lilv_ui); + zix_tree_insert(result, lilv_ui, NULL); } lilv_match_end(uis); diff --git a/src/pluginclass.c b/src/pluginclass.c index eb6923d..0764576 100644 --- a/src/pluginclass.c +++ b/src/pluginclass.c @@ -82,16 +82,16 @@ lilv_plugin_class_get_children(const LilvPluginClass* plugin_class) { // Returned list doesn't own categories LilvPluginClasses* all = plugin_class->world->plugin_classes; - LilvPluginClasses* result = g_sequence_new(NULL); + LilvPluginClasses* result = zix_tree_new(false, lilv_ptr_cmp, NULL, NULL); - for (GSequenceIter* i = g_sequence_get_begin_iter(all); - i != g_sequence_get_end_iter(all); - i = g_sequence_iter_next(i)) { - const LilvPluginClass* c = g_sequence_get(i); - const LilvNode* parent = lilv_plugin_class_get_parent_uri(c); + for (ZixTreeIter* i = zix_tree_begin(all); + i != zix_tree_end(all); + i = zix_tree_iter_next(i)) { + const LilvPluginClass* c = zix_tree_get(i); + const LilvNode* parent = lilv_plugin_class_get_parent_uri(c); if (parent && lilv_node_equals(lilv_plugin_class_get_uri(plugin_class), parent)) - lilv_sequence_insert(result, (LilvPluginClass*)c); + zix_tree_insert(result, (LilvPluginClass*)c, NULL); } return result; @@ -232,7 +232,7 @@ lilv_port_get_scale_points(const LilvPlugin* p, p->world->rdfs_label_node); if (value && label) { - lilv_array_append(ret, lilv_scale_point_new(value, label)); + zix_tree_insert(ret, lilv_scale_point_new(value, label), NULL); } } lilv_match_end(points); diff --git a/src/query.c b/src/query.c index 5f6cc57..d37527f 100644 --- a/src/query.c +++ b/src/query.c @@ -79,13 +79,14 @@ lilv_nodes_from_stream_objects_i18n(LilvWorld* world, if (lm == LILV_LANG_MATCH_EXACT) { // Exact language match, add to results - lilv_array_append(values, lilv_node_new_from_node(world, value)); + zix_tree_insert( + values, lilv_node_new_from_node(world, value), NULL); } else if (lm == LILV_LANG_MATCH_PARTIAL) { // Partial language match, save in case we find no exact partial = value; } } else { - lilv_array_append(values, lilv_node_new_from_node(world, value)); + zix_tree_insert(values, lilv_node_new_from_node(world, value), NULL); } } lilv_match_end(stream); @@ -106,7 +107,7 @@ lilv_nodes_from_stream_objects_i18n(LilvWorld* world, } if (best) { - lilv_array_append(values, lilv_node_new_from_node(world, best)); + zix_tree_insert(values, lilv_node_new_from_node(world, best), NULL); } else { // No matches whatsoever lilv_nodes_free(values); @@ -131,7 +132,7 @@ lilv_nodes_from_stream_objects(LilvWorld* world, LilvNode* value = lilv_node_new_from_node( world, lilv_match_object(stream)); if (value) { - lilv_array_append(values, value); + zix_tree_insert(values, value, NULL); } } lilv_match_end(stream); @@ -45,7 +45,7 @@ lilv_ui_new(LilvWorld* world, free(bundle); ui->classes = lilv_nodes_new(); - lilv_array_append(ui->classes, type_uri); + zix_tree_insert(ui->classes, type_uri, NULL); return ui; } diff --git a/src/world.c b/src/world.c index 9cb00ac..6be8a37 100644 --- a/src/world.c +++ b/src/world.c @@ -149,10 +149,10 @@ lilv_world_free(LilvWorld* world) const LilvPlugin* p = lilv_plugins_get(world->plugins, i); lilv_plugin_free((LilvPlugin*)p); } - g_sequence_free(world->plugins); + zix_tree_free(world->plugins); world->plugins = NULL; - g_sequence_free(world->plugin_classes); + zix_tree_free(world->plugin_classes); world->plugin_classes = NULL; sord_free(world->model); @@ -278,34 +278,20 @@ lilv_header_compare_by_uri(const void* a, const void* b, void* user_data) lilv_node_as_uri(header_b->uri)); } -/** Get an element of a sequence of any object with an LilvHeader by URI. */ +/** Get an element of a collection of any object with an LilvHeader by URI. */ struct LilvHeader* -lilv_sequence_get_by_uri(const GSequence* const_seq, - const LilvNode* uri) +lilv_collection_get_by_uri(const ZixTree* const_seq, + const LilvNode* uri) { - GSequence* seq = (GSequence*)const_seq; + ZixTree* seq = (ZixTree*)const_seq; struct LilvHeader key = { NULL, (LilvNode*)uri }; - GSequenceIter* i = g_sequence_search( - seq, &key, lilv_header_compare_by_uri, NULL); - // i points to where plugin would be inserted (not necessarily a match) - - if (!g_sequence_iter_is_end(i)) { - LilvPlugin* p = g_sequence_get(i); - if (lilv_node_equals(lilv_plugin_get_uri(p), uri)) { - return (struct LilvHeader*)p; - } - } - - if (!g_sequence_iter_is_begin(i)) { - // Check if i is just past a match - i = g_sequence_iter_prev(i); - LilvPlugin* p = g_sequence_get(i); - if (lilv_node_equals(lilv_plugin_get_uri(p), uri)) { - return (struct LilvHeader*)p; - } + ZixTreeIter* i = NULL; + ZixStatus st = zix_tree_find(seq, &key, &i); + if (!st) { + return (struct LilvHeader*)zix_tree_get(i); } - + return NULL; } @@ -328,8 +314,9 @@ lilv_world_add_spec(LilvWorld* world, NULL); FOREACH_MATCH(files) { const SordNode* file_node = lilv_match_object(files); - lilv_array_append(spec->data_uris, - lilv_node_new_from_node(world, file_node)); + zix_tree_insert(spec->data_uris, + lilv_node_new_from_node(world, file_node), + NULL); } lilv_match_end(files); @@ -362,8 +349,9 @@ lilv_world_add_plugin(LilvWorld* world, LilvPlugin* plugin = lilv_plugin_new(world, plugin_uri, bundle_uri); // Add manifest as plugin data file (as if it were rdfs:seeAlso) - lilv_array_append(plugin->data_uris, - lilv_new_uri(world, (const char*)manifest_uri->buf)); + zix_tree_insert(plugin->data_uris, + lilv_new_uri(world, (const char*)manifest_uri->buf), + NULL); // Set dynamic manifest library URI, if applicable if (dyn_manifest_lib) { @@ -379,13 +367,14 @@ lilv_world_add_plugin(LilvWorld* world, NULL); FOREACH_MATCH(files) { const SordNode* file_node = lilv_match_object(files); - lilv_array_append(plugin->data_uris, - lilv_node_new_from_node(world, file_node)); + zix_tree_insert(plugin->data_uris, + lilv_node_new_from_node(world, file_node), + NULL); } lilv_match_end(files); // Add plugin to world plugin sequence - lilv_sequence_insert(world->plugins, plugin); + zix_tree_insert(world->plugins, plugin, NULL); } static void @@ -760,7 +749,7 @@ lilv_world_load_plugin_classes(LilvWorld* world) world, parent_node, class_node, (const char*)label); if (pclass) { - lilv_sequence_insert(classes, pclass); + zix_tree_insert(classes, pclass, NULL); } } lilv_match_end(classes); diff --git a/src/zix/common.h b/src/zix/common.h new file mode 100644 index 0000000..8ed0b0b --- /dev/null +++ b/src/zix/common.h @@ -0,0 +1,72 @@ +/* + 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); + +/** + Function to destroy an element. +*/ +typedef void (*ZixDestroyFunc)(const void* ptr); + +/**@} +*/ + +#endif /* ZIX_COMMON_H */ diff --git a/src/zix/tree.c b/src/zix/tree.c new file mode 100644 index 0000000..1be9227 --- /dev/null +++ b/src/zix/tree.c @@ -0,0 +1,518 @@ +/* + 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; + ZixDestroyFunc destroy; + ZixComparator cmp; + void* cmp_data; + size_t size; + 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)) + +// Uncomment these for debugging features +// #define ZIX_TREE_DUMP 1 +// #define ZIX_TREE_VERIFY 1 +// #define ZIX_TREE_HYPER_VERIFY 1 + +#if defined(ZIX_TREE_VERIFY) || defined(ZIX_TREE_HYPER_VERIFY) +# include "tree_debug.h" +# define ASSERT_BALANCE(n) assert(verify_balance(n)) +#else +# define ASSERT_BALANCE(n) +#endif + +#ifdef ZIX_TREE_DUMP +# include "tree_debug.h" +# define DUMP(t) zix_tree_print(t->root, 0) +# define DEBUG_PRINTF(fmt, ...) printf(fmt, __VA_ARGS__) +#else +# define DUMP(t) +# define DEBUG_PRINTF(fmt, ...) +#endif + +ZIX_API +ZixTree* +zix_tree_new(bool allow_duplicates, + ZixComparator cmp, + void* cmp_data, + ZixDestroyFunc destroy) +{ + ZixTree* t = malloc(sizeof(ZixTree)); + t->root = NULL; + t->destroy = destroy; + t->cmp = cmp; + t->cmp_data = cmp_data; + t->size = 0; + t->allow_duplicates = allow_duplicates; + return t; +} + +static void +zix_tree_free_rec(ZixTree* t, ZixTreeNode* n) +{ + if (n) { + zix_tree_free_rec(t, n->left); + zix_tree_free_rec(t, n->right); + if (t->destroy) { + t->destroy(n->data); + } + free(n); + } +} + +ZIX_API +void +zix_tree_free(ZixTree* t) +{ + zix_tree_free_rec(t, t->root); + free(t); +} + +size_t +zix_tree_size(ZixTree* t) +{ + return t->size; +} + +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; + + DEBUG_PRINTF("LL %ld\n", (intptr_t)p->data); + + assert(p->balance == 2); + assert(q->balance == 0 || q->balance == 1); + + rotate(p, q); + + // p->balance -= 1 + MAX(0, q->balance); + // q->balance -= 1 - MIN(0, p->balance); + --q->balance; + p->balance = -(q->balance); + + ASSERT_BALANCE(p); + ASSERT_BALANCE(q); + 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; + + DEBUG_PRINTF("RR %ld\n", (intptr_t)p->data); + + assert(p->balance == -2); + assert(q->balance == 0 || q->balance == -1); + + rotate(p, q); + + // p->balance += 1 - MIN(0, q->balance); + // q->balance += 1 + MAX(0, p->balance); + ++q->balance; + p->balance = -(q->balance); + + ASSERT_BALANCE(p); + ASSERT_BALANCE(q); + 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); + + DEBUG_PRINTF("LR %ld P: %2d Q: %2d R: %2d\n", + (intptr_t)p->data, p->balance, q->balance, r->balance); + + 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 += MAX(0, p->balance) + MIN(0, q->balance); + + // p->balance = (p->left && p->right) ? -MIN(r->balance, 0) : 0; + // q->balance = - MAX(r->balance, 0); + r->balance = 0; + + *height_change = -1; + + ASSERT_BALANCE(p); + ASSERT_BALANCE(q); + ASSERT_BALANCE(r); + 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); + + DEBUG_PRINTF("RL %ld P: %2d Q: %2d R: %2d\n", + (intptr_t)p->data, p->balance, q->balance, r->balance); + + 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 += MAX(0, q->balance) + MIN(0, p->balance); + + // p->balance = (p->left && p->right) ? -MAX(r->balance, 0) : 0; + // q->balance = - MIN(r->balance, 0); + r->balance = 0; + // assert(r->balance == 0); + + *height_change = -1; + + ASSERT_BALANCE(p); + ASSERT_BALANCE(q); + ASSERT_BALANCE(r); + return r; +} + +static ZixTreeNode* +zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change) +{ +#ifdef ZIX_TREE_HYPER_VERIFY + const size_t old_height = height(node); +#endif + DEBUG_PRINTF("REBALANCE %ld (%d)\n", (intptr_t)node->data, node->balance); + *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; + } + DUMP(t); +#ifdef ZIX_TREE_HYPER_VERIFY + assert(old_height + *height_change == height(replacement)); +#endif + return replacement; +} + +ZIX_API +ZixStatus +zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti) +{ + DEBUG_PRINTF("**** INSERT %ld\n", (intptr_t)e); + 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; + } + DEBUG_PRINTF("%ld EXISTS!\n", (intptr_t)e); + 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; + } + } + + DUMP(t); + + // 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; + } + } + } + + DUMP(t); + + ++t->size; + +#ifdef ZIX_TREE_VERIFY + if (!verify(t, t->root)) { + return ZIX_STATUS_ERROR; + } +#endif + + 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; +} diff --git a/src/zix/tree.h b/src/zix/tree.h new file mode 100644 index 0000000..378db28 --- /dev/null +++ b/src/zix/tree.h @@ -0,0 +1,149 @@ +/* + 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 <stddef.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, + ZixDestroyFunc destroy); + +/** + Free @a t. +*/ +void +zix_tree_free(ZixTree* t); + +/** + Return the number of elements in @a t. +*/ +size_t +zix_tree_size(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 to the last (largest) element in @a t. +*/ +ZixTreeIter* +zix_tree_rbegin(ZixTree* t); + +/** + Return an iterator the the element one before the first element in @a t. +*/ +ZixTreeIter* +zix_tree_rend(ZixTree* t); + +/** + Return true iff @a i is an iterator to the reverse end of its tree. +*/ +bool +zix_tree_iter_is_rend(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 */ @@ -65,10 +65,6 @@ def configure(conf): autowaf.display_header('Lilv Configuration') autowaf.check_pkg(conf, 'lv2core', uselib_store='LV2CORE', mandatory=True) - autowaf.check_pkg(conf, 'glib-2.0', uselib_store='GLIB', - atleast_version='2.0.0', mandatory=True) - autowaf.check_pkg(conf, 'gthread-2.0', uselib_store='GTHREAD', - atleast_version='2.0.0', mandatory=False) autowaf.check_pkg(conf, 'sord-0', uselib_store='SORD', atleast_version='0.4.0', mandatory=True) @@ -158,6 +154,7 @@ def build(bld): src/ui.c src/util.c src/world.c + src/zix/tree.c '''.split() linkflags = [ '-ldl' ] @@ -179,7 +176,7 @@ def build(bld): '-DLILV_SHARED', '-DLILV_INTERNAL' ], linkflags = linkflags) - autowaf.use_lib(bld, obj, 'SORD SERD LV2CORE GLIB') + autowaf.use_lib(bld, obj, 'SORD LV2CORE') if bld.env['BUILD_TESTS']: # Static library (for unit test code coverage) @@ -191,14 +188,14 @@ def build(bld): install_path = '', cflags = [ '-fprofile-arcs', '-ftest-coverage', '-DLILV_INTERNAL' ], linkflags = linkflags) - autowaf.use_lib(bld, obj, 'SORD SERD LV2CORE GLIB') + autowaf.use_lib(bld, obj, 'SORD LV2CORE') # Unit test program obj = bld(features = 'c cprogram', source = 'test/lilv_test.c', includes = ['.', './src'], use = 'liblilv_static', - uselib = 'SORD SERD LV2CORE', + uselib = 'SORD LV2CORE', linkflags = linkflags + ['-lgcov'], target = 'test/lilv_test', install_path = '', |