summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/fat_patree.c239
-rw-r--r--src/hash.c226
-rw-r--r--src/patree.c373
-rw-r--r--src/ring.c225
-rw-r--r--src/sorted_array.c205
-rw-r--r--src/strindex.c253
-rw-r--r--src/tree.c730
-rw-r--r--src/tree_debug.h159
8 files changed, 0 insertions, 2410 deletions
diff --git a/src/fat_patree.c b/src/fat_patree.c
deleted file mode 100644
index 454cfba..0000000
--- a/src/fat_patree.c
+++ /dev/null
@@ -1,239 +0,0 @@
-/*
- 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.
-*/
-
-#define _XOPEN_SOURCE 500
-
-#include <assert.h>
-#include <stdint.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "zix/common.h"
-#include "zix/fat_patree.h"
-
-#define N_CHILDREN 256
-
-typedef uint_fast8_t n_edges_t;
-
-typedef struct _ZixFatPatreeNode {
- char* label_first; /* Start of incoming label */
- char* label_last; /* End of incoming label */
- char* str; /* String stored at this node */
- struct _ZixFatPatreeNode* children[N_CHILDREN]; /* Children of this node */
-} ZixFatPatreeNode;
-
-struct _ZixFatPatree {
- ZixFatPatreeNode* root; /* Root of the tree */
-};
-
-ZIX_API
-ZixFatPatree*
-zix_fat_patree_new(void)
-{
- ZixFatPatree* t = (ZixFatPatree*)malloc(sizeof(ZixFatPatree));
- memset(t, '\0', sizeof(struct _ZixFatPatree));
-
- t->root = (ZixFatPatreeNode*)malloc(sizeof(ZixFatPatreeNode));
- memset(t->root, '\0', sizeof(ZixFatPatreeNode));
-
- return t;
-}
-
-static void
-zix_fat_patree_free_rec(ZixFatPatreeNode* n)
-{
- if (n) {
- for (int i = 0; i < N_CHILDREN; ++i) {
- zix_fat_patree_free_rec(n->children[i]);
- }
- }
-}
-
-ZIX_API
-void
-zix_fat_patree_free(ZixFatPatree* t)
-{
- zix_fat_patree_free_rec(t->root);
- free(t->root);
- free(t);
-}
-
-static inline bool
-patree_find_edge(ZixFatPatreeNode* n, uint8_t c, n_edges_t* index)
-{
- if (n->children[c]) {
- *index = c;
- return true;
- }
- return false;
-}
-
-static void
-patree_add_edge(ZixFatPatreeNode* n,
- char* str,
- char* first,
- char* last)
-{
- assert(last >= first);
- const int index = (uint8_t)first[0];
- assert(!n->children[index]);
-
- ZixFatPatreeNode* new_node = (ZixFatPatreeNode*)malloc(
- sizeof(ZixFatPatreeNode));
- n->children[index] = new_node;
- n->children[index]->label_first = first;
- n->children[index]->label_last = last;
- n->children[index]->str = str;
- for (int i = 0; i < N_CHILDREN; ++i) {
- n->children[index]->children[i] = NULL;
- }
-}
-
-/* Split an outgoing edge (to a child) at the given index */
-static void
-patree_split_edge(ZixFatPatreeNode* child,
- size_t index)
-{
- char* const first = child->label_first + index;
- char* const last = child->label_last;
- assert(last >= first);
-
- ZixFatPatreeNode* new_node = (ZixFatPatreeNode*)malloc(
- sizeof(ZixFatPatreeNode));
- new_node->label_first = first;
- new_node->label_last = last;
- new_node->str = child->str;
- memcpy(new_node->children, child->children,
- sizeof(ZixFatPatreeNode*) * N_CHILDREN);
-
- child->label_last = child->label_first + (index - 1); // chop end
- child->str = NULL;
-
- for (int i = 0; i < N_CHILDREN; ++i) {
- child->children[i] = NULL;
- }
- const int new_node_index = (int)first[0];
- assert(new_node_index < N_CHILDREN);
- assert(!child->children[new_node_index]);
- child->children[new_node_index] = new_node;
-}
-
-static ZixStatus
-patree_insert_internal(ZixFatPatreeNode* n, char* str, char* first, char* last)
-{
- n_edges_t child_i;
- assert(first <= last);
-
- if (patree_find_edge(n, *first, &child_i)) {
- ZixFatPatreeNode* child = n->children[child_i];
- char* const label_first = child->label_first;
- char* const label_last = child->label_last;
- size_t split_i = 0;
- const size_t label_len = label_last - label_first + 1;
- const size_t s_len = last - first + 1;
- const size_t max_len = (s_len < label_len) ? s_len : label_len;
-
- while (split_i < max_len && first[split_i] == label_first[split_i]) {
- ++split_i;
- }
- child = n->children[child_i];
-
- if (label_len < s_len) {
- if (split_i == label_len) {
- return patree_insert_internal(child, str, first + label_len, last);
- } else {
- patree_split_edge(child, split_i);
- return patree_insert_internal(child, str, first + split_i, last);
- }
- } else if (label_len != split_i) {
- patree_split_edge(child, split_i);
- if (split_i != s_len) {
- patree_add_edge(child, str, first + split_i, last);
- } else {
- assert(!child->str);
- child->str = str;
- }
- return ZIX_STATUS_SUCCESS;
- } else if (label_len == s_len && !child->str) {
- child->str = str;
- } else {
- return ZIX_STATUS_EXISTS;
- }
-
- } else {
- patree_add_edge(n, str, first, last);
- }
-
- return ZIX_STATUS_SUCCESS;
-}
-
-ZIX_API
-ZixStatus
-zix_fat_patree_insert(ZixFatPatree* t, const char* str)
-{
- const size_t len = strlen(str);
- // FIXME: awful casts
- return patree_insert_internal(t->root, (char*)str, (char*)str, (char*)str + len - 1);
-}
-
-ZIX_API
-ZixStatus
-zix_fat_patree_find(ZixFatPatree* t, const char* p, char** match)
-{
- ZixFatPatreeNode* n = t->root;
- n_edges_t child_i;
-
- *match = NULL;
-
- while (*p != '\0') {
- if (patree_find_edge(n, p[0], &child_i)) {
- ZixFatPatreeNode* const child = n->children[child_i];
- const char* const label_first = child->label_first;
- const char* const label_last = child->label_last;
-
- /* Prefix compare search string and label */
- const char* l = label_first;
- while (*p != '\0' && l <= label_last) {
- if (*l++ != *p++) {
- return ZIX_STATUS_NOT_FOUND;
- }
- }
-
- if (!*p) {
- /* Reached end of search string */
- if (l == label_last + 1) {
- /* Reached end of label string as well, match */
- *match = child->str;
- return *match ? ZIX_STATUS_SUCCESS : ZIX_STATUS_NOT_FOUND;
- } else {
- /* Label string is longer, no match (prefix match) */
- return ZIX_STATUS_NOT_FOUND;
- }
- } else {
- /* Match at this node, continue search downwards.
- Possibly we have prematurely hit a leaf, so the next
- edge search will fail.
- */
- n = child;
- }
- } else {
- return ZIX_STATUS_NOT_FOUND;
- }
- }
-
- return ZIX_STATUS_NOT_FOUND;
-}
diff --git a/src/hash.c b/src/hash.c
deleted file mode 100644
index f654e91..0000000
--- a/src/hash.c
+++ /dev/null
@@ -1,226 +0,0 @@
-/*
- 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 = (Entry**)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/patree.c b/src/patree.c
deleted file mode 100644
index f3603a2..0000000
--- a/src/patree.c
+++ /dev/null
@@ -1,373 +0,0 @@
-/*
- 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.
-*/
-
-#define _XOPEN_SOURCE 500
-
-#include <assert.h>
-#include <stdint.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "zix/common.h"
-#include "zix/patree.h"
-
-//#undef __SSE4_2__
-
-#ifdef __SSE4_2__
-#include <smmintrin.h>
-//#warning Using SSE 4.2
-#else
-//#warning SSE 4.2 disabled
-#endif
-
-typedef uint_fast8_t n_edges_t;
-
-struct _ZixPatreeNode;
-
-typedef struct {
- struct _ZixPatreeNode* child;
- char first_char;
-} ZixChildRef;
-
-typedef struct _ZixPatreeNode {
- const char* label_first; /* Start of incoming label */
- const char* label_last; /* End of incoming label */
- const char* str; /* String stored at this node */
- n_edges_t num_children; /* Number of outgoing edges */
- ZixChildRef children[]; /* Children of this node */
-} ZixPatreeNode;
-
-struct _ZixPatree {
- ZixPatreeNode* root; /* Root of the tree */
-};
-
-static void
-zix_patree_print_rec(ZixPatreeNode* node, FILE* fd)
-{
- if (node->label_first) {
- size_t edge_label_len = node->label_last - node->label_first + 1;
- char* edge_label = (char*)malloc(edge_label_len + 1);
- strncpy(edge_label, node->label_first, edge_label_len);
- fprintf(fd, "\t\"%p\" [label=<"
- "<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">"
- "<TR><TD>%s</TD></TR>", (void*)node, edge_label);
- free(edge_label);
- if (node->str) {
- fprintf(fd, "<TR><TD>\"%s\"</TD></TR>", node->str);
- }
- fprintf(fd, "</TABLE>>,shape=\"plaintext\"] ;\n");
- } else {
- fprintf(fd, "\t\"%p\" [label=\"\"] ;\n", (void*)node);
- }
-
-
- for (n_edges_t i = 0; i < node->num_children; ++i) {
- ZixPatreeNode* const child = node->children[i].child;
- zix_patree_print_rec(child, fd);
- fprintf(fd, "\t\"%p\" -> \"%p\" ;\n", (void*)node, (void*)child);
- }
-}
-
-ZIX_API
-void
-zix_patree_print_dot(const ZixPatree* t, FILE* fd)
-{
- fprintf(fd, "digraph Patree { \n");
- zix_patree_print_rec(t->root, fd);
- fprintf(fd, "}\n");
-}
-
-static inline ZixPatreeNode*
-realloc_node(ZixPatreeNode* n, int num_children)
-{
- return (ZixPatreeNode*)realloc(n, sizeof(ZixPatreeNode)
- + num_children * sizeof(ZixChildRef));
-}
-
-ZIX_API
-ZixPatree*
-zix_patree_new(void)
-{
- ZixPatree* t = (ZixPatree*)malloc(sizeof(ZixPatree));
- memset(t, '\0', sizeof(struct _ZixPatree));
-
- t->root = realloc_node(NULL, 0);
- memset(t->root, '\0', sizeof(ZixPatreeNode));
-
- return t;
-}
-
-static void
-zix_patree_free_rec(ZixPatreeNode* n)
-{
- if (n) {
- for (n_edges_t i = 0; i < n->num_children; ++i) {
- zix_patree_free_rec(n->children[i].child);
- }
- free(n);
- }
-}
-
-ZIX_API
-void
-zix_patree_free(ZixPatree* t)
-{
- zix_patree_free_rec(t->root);
- free(t);
-}
-
-static inline bool
-patree_is_leaf(const ZixPatreeNode* n)
-{
- return n->num_children == 0;
-}
-
-static bool
-patree_find_edge(const ZixPatreeNode* n, const char c, n_edges_t* const index)
-{
- for (n_edges_t i = 0; i < n->num_children; ++i) {
- if (n->children[i].first_char == c) {
- *index = i;
- return true;
- }
- }
- return false;
-}
-
-static void
-patree_add_edge(ZixPatreeNode** n_ptr,
- const char* str,
- const char* first)
-{
- ZixPatreeNode* n = *n_ptr;
-
- const char* last = first;
- for (; *last; ++last) ;
- --last;
-
- /* Interesting performance note: building a sorted array here makes
- the search considerably slower, regardless of whether binary search
- or the existing search algorithm is used. I suppose moving things
- around blows the cache for child->children which trumps everything.
- */
- assert(last >= first);
-
- ZixPatreeNode* const child = realloc_node(NULL, 0);
- child->label_first = first;
- child->label_last = last;
- child->str = str;
- child->num_children = 0;
-
- ++n->num_children;
- n = realloc_node(n, n->num_children);
- n->children[n->num_children - 1].first_char = first[0];
- n->children[n->num_children - 1].child = child;
-
- *n_ptr = n;
-
- for (n_edges_t i = 0; i < n->num_children; ++i) {
- assert(n->children[i].first_char != '\0');
- }
- for (n_edges_t i = 0; i < child->num_children; ++i) {
- assert(child->children[i].first_char != '\0');
- }
-}
-
-/* Split an outgoing edge (to a child) at the given index */
-static void
-patree_split_edge(ZixPatreeNode** child_ptr,
- size_t index)
-{
- ZixPatreeNode* child = *child_ptr;
-
- const size_t grandchild_size = sizeof(ZixPatreeNode)
- + (child->num_children * sizeof(ZixChildRef));
-
- ZixPatreeNode* const grandchild = realloc_node(NULL, child->num_children);
- memcpy(grandchild, child, grandchild_size);
- grandchild->label_first = child->label_first + index;
-
- child = realloc_node(child, 1);
- child->children[0].first_char = grandchild->label_first[0];
- child->children[0].child = grandchild;
- child->label_last = child->label_first + (index - 1); // chop end
-
- child->num_children = 1;
-
- child->str = NULL;
-
- *child_ptr = child;
-
- for (n_edges_t i = 0; i < child->num_children; ++i) {
- assert(child->children[i].first_char != '\0');
- }
- for (n_edges_t i = 0; i < grandchild->num_children; ++i) {
- assert(grandchild->children[i].first_char != '\0');
- }
-}
-
-static ZixStatus
-patree_insert_internal(ZixPatreeNode** n_ptr, const char* str, const char* first)
-{
- ZixPatreeNode* n = *n_ptr;
- n_edges_t child_i;
- if (patree_find_edge(n, *first, &child_i)) {
- ZixPatreeNode** child_ptr = &n->children[child_i].child;
- ZixPatreeNode* child = *child_ptr;
- const char* const label_first = child->label_first;
- const char* const label_last = child->label_last;
- size_t split_i = 0;
- const size_t label_len = label_last - label_first + 1;
-
- while (first[split_i] && split_i < label_len
- && first[split_i] == label_first[split_i]) {
- ++split_i;
- }
-
- if (first[split_i]) {
- if (split_i == label_len) {
- return patree_insert_internal(child_ptr, str, first + label_len);
- } else {
- patree_split_edge(child_ptr, split_i);
- return patree_insert_internal(child_ptr, str, first + split_i);
- }
- } else if (label_len != split_i) {
- patree_split_edge(child_ptr, split_i);
- if (first[split_i]) {
- patree_add_edge(child_ptr, str, first + split_i);
- } else {
- assert(!(*child_ptr)->str);
- (*child_ptr)->str = str;
- }
- return ZIX_STATUS_SUCCESS;
- } else if (label_first[split_i] && !child->str) {
- child->str = str;
- } else {
- return ZIX_STATUS_EXISTS;
- }
- } else {
- patree_add_edge(n_ptr, str, first);
- }
-
- return ZIX_STATUS_SUCCESS;
-}
-
-ZIX_API
-ZixStatus
-zix_patree_insert(ZixPatree* t, const char* str)
-{
- return patree_insert_internal(&t->root, str, str);
-}
-
-static inline int
-change_index_c(const char* a, const char* b, size_t len)
-{
- for (size_t i = 0; i < len; ++i) {
- if (a[i] != b[i]) {
- return i;
- }
- }
- return len;
-}
-
-#ifdef __SSE4_2__
-static inline int
-change_index_sse(const char* a, const char* b, const size_t len)
-{
- for (size_t i = 0; i < len; i += sizeof(__m128i)) {
- const __m128i r = _mm_loadu_si128((const __m128i*)(a + i));
- const __m128i* s = (const __m128i*)(b + i);
- const int index = _mm_cmpistri(
- r, *s, _SIDD_SBYTE_OPS|_SIDD_CMP_EQUAL_EACH|_SIDD_NEGATIVE_POLARITY);
-
- if (index != sizeof(__m128i)) {
- size_t ret = i + index;
- if (ret > len) {
- ret = len;
- }
- return ret;
- }
- }
-
- return len;
-}
-#endif
-
-ZIX_API
-ZixStatus
-zix_patree_find(const ZixPatree* t, const char* const str, const char** match)
-{
- ZixPatreeNode* n = t->root;
- n_edges_t child_i;
-
- const char* p = str;
-
- while (patree_find_edge(n, p[0], &child_i)) {
- assert(child_i <= n->num_children);
- ZixPatreeNode* const child = n->children[child_i].child;
- const char* const child_str = child->str;
-
- /* Prefix compare search string and label */
- const char* l = child->label_first;
- const char* const l_end = child->label_last;
- const size_t len = l_end - l + 1;
-#ifdef __SSE4_2__
- int change_index;
- if (len >= sizeof(__m128i)) {
- change_index = change_index_sse(p, l, len);
- } else {
- change_index = change_index_c(p, l, len);
- }
-#else
- int change_index = change_index_c(p, l, len);
-#endif
-
- l += change_index;
- p += change_index;
-
-#if 0
- while (l <= l_end) {
- if (*l++ != *p++) {
- return ZIX_STATUS_NOT_FOUND;
- }
- }
-#endif
-
- if (!*p) {
- /* Reached end of search string */
- if (l == l_end + 1) {
- /* Reached end of label string as well, match */
- *match = child_str;
- return *match ? ZIX_STATUS_SUCCESS : ZIX_STATUS_NOT_FOUND;
- } else {
- /* Label string is longer, no match (prefix match) */
- return ZIX_STATUS_NOT_FOUND;
- }
- } else {
- /* Didn't reach end of search string */
- if (patree_is_leaf(n)) {
- /* Hit leaf early, no match */
- return ZIX_STATUS_NOT_FOUND;
- } else {
- /* Match at this node, continue search downwards (or match) */
- n = child;
- }
- }
- }
-
- return ZIX_STATUS_NOT_FOUND;
-}
diff --git a/src/ring.c b/src/ring.c
deleted file mode 100644
index b701497..0000000
--- a/src/ring.c
+++ /dev/null
@@ -1,225 +0,0 @@
-/*
- 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 <stdint.h>
-#include <stdlib.h>
-#include <string.h>
-
-#ifdef HAVE_MLOCK
-# include <sys/mman.h>
-# define ZIX_MLOCK(ptr, size) mlock((ptr), (size))
-#elif defined(_WIN32)
-# include <windows.h>
-# define ZIX_MLOCK(ptr, size) VirtualLock((ptr), (size))
-#else
-# pragma message("warning: No memory locking, possible RT violations")
-# define ZIX_MLOCK(ptr, size)
-#endif
-
-#if defined(__APPLE__)
-# include <libkern/OSAtomic.h>
-# define ZIX_FULL_BARRIER() OSMemoryBarrier()
-#elif defined(_WIN32)
-# include <windows.h>
-# define ZIX_FULL_BARRIER() MemoryBarrier()
-#elif (__GNUC__ > 4) || (__GNUC__ == 4 && __GNUC_MINOR__ >= 1)
-# define ZIX_FULL_BARRIER() __sync_synchronize()
-#else
-# pragma message("warning: No memory barriers, possible SMP bugs")
-# define ZIX_FULL_BARRIER()
-#endif
-
-/* No support for any systems with separate read and write barriers */
-#define ZIX_READ_BARRIER() ZIX_FULL_BARRIER()
-#define ZIX_WRITE_BARRIER() ZIX_FULL_BARRIER()
-
-#include "zix/ring.h"
-
-struct ZixRingImpl {
- uint32_t write_head; ///< Read index into buf
- uint32_t read_head; ///< Write index into buf
- uint32_t size; ///< Size (capacity) in bytes
- uint32_t size_mask; ///< Mask for fast modulo
- char* buf; ///< Contents
-};
-
-static inline uint32_t
-next_power_of_two(uint32_t size)
-{
- // http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
- size--;
- size |= size >> 1;
- size |= size >> 2;
- size |= size >> 4;
- size |= size >> 8;
- size |= size >> 16;
- size++;
- return size;
-}
-
-ZixRing*
-zix_ring_new(uint32_t size)
-{
- ZixRing* ring = (ZixRing*)malloc(sizeof(ZixRing));
- ring->write_head = 0;
- ring->read_head = 0;
- ring->size = next_power_of_two(size);
- ring->size_mask = ring->size - 1;
- ring->buf = (char*)malloc(ring->size);
- return ring;
-}
-
-void
-zix_ring_free(ZixRing* ring)
-{
- free(ring->buf);
- free(ring);
-}
-
-void
-zix_ring_mlock(ZixRing* ring)
-{
- ZIX_MLOCK(ring, sizeof(ZixRing));
- ZIX_MLOCK(ring->buf, ring->size);
-}
-
-void
-zix_ring_reset(ZixRing* ring)
-{
- ring->write_head = 0;
- ring->read_head = 0;
-}
-
-static inline uint32_t
-read_space_internal(const ZixRing* ring, uint32_t r, uint32_t w)
-{
- if (r < w) {
- return w - r;
- } else {
- return (w - r + ring->size) & ring->size_mask;
- }
-}
-
-uint32_t
-zix_ring_read_space(const ZixRing* ring)
-{
- return read_space_internal(ring, ring->read_head, ring->write_head);
-}
-
-static inline uint32_t
-write_space_internal(const ZixRing* ring, uint32_t r, uint32_t w)
-{
- if (r == w) {
- return ring->size - 1;
- } else if (r < w) {
- return ((r - w + ring->size) & ring->size_mask) - 1;
- } else {
- return (r - w) - 1;
- }
-}
-
-uint32_t
-zix_ring_write_space(const ZixRing* ring)
-{
- return write_space_internal(ring, ring->read_head, ring->write_head);
-}
-
-uint32_t
-zix_ring_capacity(const ZixRing* ring)
-{
- return ring->size - 1;
-}
-
-static inline uint32_t
-peek_internal(const ZixRing* ring, uint32_t r, uint32_t w,
- uint32_t size, void* dst)
-{
- if (read_space_internal(ring, r, w) < size) {
- return 0;
- }
-
- if (r + size < ring->size) {
- memcpy(dst, &ring->buf[r], size);
- } else {
- const uint32_t first_size = ring->size - r;
- memcpy(dst, &ring->buf[r], first_size);
- memcpy((char*)dst + first_size, &ring->buf[0], size - first_size);
- }
-
- return size;
-}
-
-uint32_t
-zix_ring_peek(ZixRing* ring, void* dst, uint32_t size)
-{
- const uint32_t r = ring->read_head;
- const uint32_t w = ring->write_head;
-
- return peek_internal(ring, r, w, size, dst);
-}
-
-uint32_t
-zix_ring_read(ZixRing* ring, void* dst, uint32_t size)
-{
- const uint32_t r = ring->read_head;
- const uint32_t w = ring->write_head;
-
- if (peek_internal(ring, r, w, size, dst)) {
- ZIX_READ_BARRIER();
- ring->read_head = (r + size) & ring->size_mask;
- return size;
- } else {
- return 0;
- }
-}
-
-uint32_t
-zix_ring_skip(ZixRing* ring, uint32_t size)
-{
- const uint32_t r = ring->read_head;
- const uint32_t w = ring->write_head;
- if (read_space_internal(ring, r, w) < size) {
- return 0;
- }
-
- ZIX_READ_BARRIER();
- ring->read_head = (r + size) & ring->size_mask;
- return size;
-}
-
-uint32_t
-zix_ring_write(ZixRing* ring, const void* src, uint32_t size)
-{
- const uint32_t r = ring->read_head;
- const uint32_t w = ring->write_head;
- if (write_space_internal(ring, r, w) < size) {
- return 0;
- }
-
- if (w + size <= ring->size) {
- memcpy(&ring->buf[w], src, size);
- ZIX_WRITE_BARRIER();
- ring->write_head = (w + size) & ring->size_mask;
- } else {
- const uint32_t this_size = ring->size - w;
- memcpy(&ring->buf[w], src, this_size);
- memcpy(&ring->buf[0], (const char*)src + this_size, size - this_size);
- ZIX_WRITE_BARRIER();
- ring->write_head = size - this_size;
- }
-
- return size;
-}
diff --git a/src/sorted_array.c b/src/sorted_array.c
deleted file mode 100644
index f8e785d..0000000
--- a/src/sorted_array.c
+++ /dev/null
@@ -1,205 +0,0 @@
-/*
- 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 <stdint.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "zix/common.h"
-#include "zix/sorted_array.h"
-
-// #define ZIX_SORTED_ARRAY_DUMP 1
-
-struct ZixSortedArrayImpl {
- void* array;
- ZixComparator cmp;
- void* cmp_data;
- size_t elem_size;
- size_t num_elems;
- bool allow_duplicates;
-};
-
-#ifdef ZIX_SORTED_ARRAY_DUMP
-static void
-zix_sorted_array_print(ZixSortedArray* a)
-{
- for (size_t i = 0; i < a->num_elems; ++i) {
- printf(" %ld", *(intptr_t*)((char*)a->array + (i * a->elem_size)));
- }
- printf("\n");
-}
-# define DUMP(a) zix_sorted_array_print(a)
-#else
-# define DUMP(a)
-#endif
-
-ZIX_API
-ZixSortedArray*
-zix_sorted_array_new(bool allow_duplicates,
- ZixComparator cmp,
- void* cmp_data,
- size_t elem_size)
-{
- ZixSortedArray* a = (ZixSortedArray*)malloc(sizeof(ZixSortedArray));
- a->array = NULL;
- a->cmp = cmp;
- a->cmp_data = cmp_data;
- a->elem_size = elem_size;
- a->num_elems = 0;
- a->allow_duplicates = allow_duplicates;
- return a;
-}
-
-ZIX_API
-void
-zix_sorted_array_free(ZixSortedArray* a)
-{
- free(a->array);
- free(a);
-}
-
-ZIX_API
-size_t
-zix_sorted_array_size(ZixSortedArray* a)
-{
- return a->num_elems;
-}
-
-ZIX_API
-ZixStatus
-zix_sorted_array_insert(ZixSortedArray* a,
- const void* e,
- ZixSortedArrayIter* ai)
-{
- if (a->num_elems == 0) {
- assert(!a->array);
- a->array = malloc(a->elem_size);
- memcpy(a->array, e, a->elem_size);
- ++a->num_elems;
- *ai = a->array;
- return ZIX_STATUS_SUCCESS;
- }
-
- zix_sorted_array_find(a, e, ai);
- assert(*ai);
- const size_t i = ((char*)*ai - (char*)a->array) / a->elem_size;
-
- a->array = realloc(a->array, ++a->num_elems * a->elem_size);
- memmove((char*)a->array + ((i + 1) * a->elem_size),
- (char*)a->array + (i * a->elem_size),
- (a->num_elems - i - 1) * a->elem_size);
- memcpy((char*)a->array + (i * a->elem_size),
- e,
- a->elem_size);
-
- *ai = (char*)a->array + (i * a->elem_size);
- DUMP(t);
- return ZIX_STATUS_SUCCESS;
-}
-
-ZIX_API
-ZixStatus
-zix_sorted_array_remove(ZixSortedArray* a, ZixSortedArrayIter ai)
-{
- const size_t i = ((char*)ai - (char*)a->array) / a->elem_size;
- memmove((char*)a->array + (i * a->elem_size),
- (char*)a->array + ((i + 1) * a->elem_size),
- (a->num_elems - i - 1) * a->elem_size);
- --a->num_elems;
- DUMP(a);
- return ZIX_STATUS_SUCCESS;
-}
-
-static inline void*
-zix_sorted_array_index_unchecked(const ZixSortedArray* a, size_t index)
-{
- return (char*)a->array + (a->elem_size * index);
-}
-
-ZIX_API
-void*
-zix_sorted_array_index(const ZixSortedArray* a, size_t index)
-{
- if (index >= a->num_elems) {
- return NULL;
- }
-
- return zix_sorted_array_index_unchecked(a, index);
-}
-
-ZIX_API
-ZixStatus
-zix_sorted_array_find(const ZixSortedArray* a,
- const void* e,
- ZixSortedArrayIter* ai)
-{
- intptr_t lower = 0;
- intptr_t upper = a->num_elems - 1;
- while (upper >= lower) {
- const intptr_t i = lower + ((upper - lower) / 2);
- void* const elem_i = zix_sorted_array_index_unchecked(a, i);
- const int cmp = a->cmp(elem_i, e, a->cmp_data);
-
- if (cmp == 0) {
- *ai = elem_i;
- return ZIX_STATUS_SUCCESS;
- } else if (cmp > 0) {
- upper = i - 1;
- } else {
- lower = i + 1;
- }
- }
-
- *ai = zix_sorted_array_index_unchecked(a, lower);
- return ZIX_STATUS_NOT_FOUND;
-}
-
-ZIX_API
-void*
-zix_sorted_array_get_data(ZixSortedArrayIter ai)
-{
- return ai;
-}
-
-ZIX_API
-ZixSortedArrayIter
-zix_sorted_array_begin(ZixSortedArray* a)
-{
- return a->array;
-}
-
-ZIX_API
-ZixSortedArrayIter
-zix_sorted_array_end(ZixSortedArray* a)
-{
- return (char*)a->array + (a->elem_size * a->num_elems);
-}
-
-ZIX_API
-bool
-zix_sorted_array_iter_is_end(ZixSortedArray* a, ZixSortedArrayIter i)
-{
- return i != zix_sorted_array_end(a);
-}
-
-ZIX_API
-ZixSortedArrayIter
-zix_sorted_array_iter_next(ZixSortedArray* a, ZixSortedArrayIter i)
-{
- return (char*)i + a->elem_size;
-}
diff --git a/src/strindex.c b/src/strindex.c
deleted file mode 100644
index bd97db5..0000000
--- a/src/strindex.c
+++ /dev/null
@@ -1,253 +0,0 @@
-/*
- 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.
- */
-
-#define _XOPEN_SOURCE 500
-
-#include <assert.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "zix/common.h"
-#include "zix/strindex.h"
-
-typedef struct _ZixStrindexNode {
- struct _ZixStrindexNode* children; /* Children of this node */
- size_t num_children; /* Number of outgoing edges */
- char* first; /* Start of this suffix */
- char* label_first; /* Start of incoming label */
- char* label_last; /* End of incoming label */
-} ZixStrindexNode;
-
-struct _ZixStrindex {
- char* s; /* String contained in this tree */
- ZixStrindexNode* root; /* Root of the tree */
-};
-
-static ZixStatus
-strindex_insert(ZixStrindexNode* n,
- char* suffix_first,
- char* first,
- char* last);
-
-ZIX_API
-ZixStrindex*
-zix_strindex_new(const char* s)
-{
- ZixStrindex* t = (ZixStrindex*)malloc(sizeof(ZixStrindex));
- memset(t, '\0', sizeof(struct _ZixStrindex));
- t->s = strdup(s);
- t->root = (ZixStrindexNode*)malloc(sizeof(ZixStrindexNode));
- memset(t->root, '\0', sizeof(ZixStrindexNode));
- t->root->num_children = 0;
- t->root->first = t->s;
-
- const size_t len = strlen(t->s);
- for (size_t i = 0; i < len; ++i) {
- strindex_insert(t->root, t->s + i, t->s + i, t->s + (len - 1));
- }
-
- return t;
-}
-
-static void
-zix_strindex_free_rec(ZixStrindexNode* n)
-{
- if (n) {
- for (size_t i = 0; i < n->num_children; ++i) {
- zix_strindex_free_rec(&n->children[i]);
- }
- free(n->children);
- }
-}
-
-ZIX_API
-void
-zix_strindex_free(ZixStrindex* t)
-{
- zix_strindex_free_rec(t->root);
- free(t->s);
- free(t->root);
- free(t);
-}
-
-static inline int
-strindex_is_leaf(ZixStrindexNode* n)
-{
- return n->num_children == 0;
-}
-
-static int
-strindex_find_edge(ZixStrindexNode* n, char c, size_t* index)
-{
- for (size_t i = 0; i < n->num_children; ++i) {
- if (n->children[i].label_first[0] == c) {
- *index = i;
- return 1;
- }
- }
- return 0;
-}
-
-static void
-strindex_add_edge(ZixStrindexNode* n,
- char* suffix_first,
- char* first,
- char* last)
-{
- assert(last > first);
- n->children = (ZixStrindexNode*)realloc(
- n->children, (n->num_children + 1) * sizeof(ZixStrindexNode));
-
- memset(&n->children[n->num_children], '\0', sizeof(ZixStrindexNode));
-
- n->children[n->num_children].first = suffix_first;
- n->children[n->num_children].label_first = first;
- n->children[n->num_children].label_last = last;
- ++n->num_children;
-}
-
-/* Split an outgoing edge (to a child) at the given index */
-static void
-strindex_split_edge(ZixStrindexNode* child,
- size_t index)
-{
- ZixStrindexNode* children = child->children;
- size_t num_children = child->num_children;
-
- char* first = child->label_first + index;
- char* last = child->label_last;
- assert(last > first);
- assert(child->first);
-
- child->children = (ZixStrindexNode*)malloc(sizeof(ZixStrindexNode));
-
- child->children[0].children = children;
- child->children[0].num_children = num_children;
- child->children[0].first = child->first;
- child->children[0].label_first = first;
- child->children[0].label_last = last;
-
- child->label_last = child->label_first + (index - 1); // chop end
-
- child->num_children = 1;
-}
-
-static ZixStatus
-strindex_insert(ZixStrindexNode* n, char* suffix_first, char* first, char* last)
-{
- size_t child_i;
- ZixStrindexNode* child;
- assert(first <= last);
-
- if (strindex_find_edge(n, *first, &child_i)) {
- char* label_first = n->children[child_i].label_first;
- char* label_last = n->children[child_i].label_last;
- size_t split_i = 0;
- const size_t label_len = label_last - label_first + 1;
- const size_t s_len = last - first + 1;
- const size_t max_len = (s_len < label_len) ? s_len : label_len;
-
- while (split_i < max_len && first[split_i] == label_first[split_i]) {
- ++split_i;
- }
- child = n->children + child_i;
-
- if (label_len < s_len) {
- if (split_i == label_len) {
- strindex_insert(child, suffix_first, first + label_len, last);
- } else {
- strindex_split_edge(child, split_i);
- strindex_insert(child, suffix_first, first + split_i, last);
- }
- } else if ((label_len != split_i) && (label_len != s_len)) {
- strindex_split_edge(child, split_i);
- if (split_i != s_len) {
- strindex_add_edge(child, suffix_first, first + split_i, last);
- }
- }
- } else {
- strindex_add_edge(n, suffix_first, first, last);
- }
-
- return ZIX_STATUS_SUCCESS;
-}
-
-ZIX_API
-ZixStatus
-zix_strindex_find(ZixStrindex* t, const char* p, char** match)
-{
-#ifndef NDEBUG
- const char* orig_p = p;
-#endif
-
- ZixStrindexNode* n = t->root;
- size_t child_i;
-
- *match = NULL;
-
- while (*p != '\0') {
- size_t p_len = strlen(p);
- if (strindex_find_edge(n, p[0], &child_i)) {
- char* label_first = n->children[child_i].label_first;
- char* label_last = n->children[child_i].label_last;
- size_t label_len = label_last - label_first + 1;
- size_t max_len = (p_len < label_len) ? p_len : label_len;
- assert(child_i <= n->num_children);
- assert(max_len > 0);
-
- /* Set match to the start of substring
- (but may not actually be a complete match yet)
- */
- if (*match == NULL) {
- assert(p[0] == orig_p[0]);
- assert(orig_p[0] == label_first[0]);
- *match = n->children[child_i].first;
- assert((*match)[0] == orig_p[0]);
- }
-
- if (strncmp(p, label_first, max_len)) {
- /* no match */
- *match = NULL;
- return ZIX_STATUS_NOT_FOUND;
- }
-
- if (p_len <= label_len) {
- /* At the last node, match */
- *match = n->children[child_i].first;
- assert(!strncmp(*match, orig_p, strlen(orig_p)));
- return ZIX_STATUS_SUCCESS;
- } else if (strindex_is_leaf(n)) {
- /* Hit leaf early, no match */
- return ZIX_STATUS_NOT_FOUND;
- } else {
- /* Match at this node, continue search downwards (or match) */
- p += label_len;
- n = &n->children[child_i];
- if (label_len >= p_len) {
- assert(strstr(t->s, orig_p) != NULL);
- assert(strncmp(orig_p, *match, max_len));
- return ZIX_STATUS_SUCCESS;
- }
- }
-
- } else {
- assert(strstr(t->s, orig_p) == NULL);
- return ZIX_STATUS_NOT_FOUND;
- }
- }
- return ZIX_STATUS_NOT_FOUND;
-}
diff --git a/src/tree.c b/src/tree.c
deleted file mode 100644
index 8523228..0000000
--- a/src/tree.c
+++ /dev/null
@@ -1,730 +0,0 @@
-/*
- 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 <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 = (ZixTree*)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)
-{
- if (t) {
- zix_tree_free_rec(t, t->root);
- free(t);
- }
-}
-
-size_t
-zix_tree_size(const 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 = (ZixTreeNode*)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_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
-
- DEBUG_PRINTF("*** REMOVE %ld\n", (intptr_t)n->data);
-
- if ((n == t->root) && !n->left && !n->right) {
- t->root = NULL;
- if (t->destroy) {
- t->destroy(n->data);
- }
- free(n);
- --t->size;
- assert(t->size == 0);
- 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;
- }
- }
- }
-
- DUMP(t);
-
- if (t->destroy) {
- t->destroy(n->data);
- }
- free(n);
-
- --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 ? ti->data : NULL;
-}
-
-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
-ZixTreeIter*
-zix_tree_rbegin(ZixTree* t)
-{
- if (!t->root) {
- return NULL;
- }
-
- ZixTreeNode* n = t->root;
- while (n->right) {
- n = n->right;
- }
- return n;
-}
-
-ZIX_API
-ZixTreeIter*
-zix_tree_rend(ZixTree* t)
-{
- return NULL;
-}
-
-ZIX_API
-bool
-zix_tree_iter_is_end(ZixTreeIter* i)
-{
- return !i;
-}
-
-ZIX_API
-bool
-zix_tree_iter_is_rend(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/tree_debug.h b/src/tree_debug.h
deleted file mode 100644
index e903265..0000000
--- a/src/tree_debug.h
+++ /dev/null
@@ -1,159 +0,0 @@
-/*
- 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_DEBUG_H
-#define ZIX_TREE_DEBUG_H
-
-#ifndef _MSC_VER
-# include <inttypes.h>
-#endif
-
-#ifdef ZIX_TREE_DUMP
-static void
-zix_tree_print(ZixTreeNode* node, int level)
-{
- if (node) {
- if (!node->parent) {
- printf("{{{\n");
- }
- zix_tree_print(node->right, level + 1);
- for (int i = 0; i < level; i++) {
- printf(" ");
- }
- printf("%ld.%d\n", (intptr_t)node->data, node->balance);
- zix_tree_print(node->left, level + 1);
- if (!node->parent) {
- printf("}}}\n");
- }
- }
-}
-#endif
-
-#ifdef ZIX_TREE_HYPER_VERIFY
-static size_t
-height(ZixTreeNode* n)
-{
- if (!n) {
- return 0;
- } else {
- return 1 + MAX(height(n->left), height(n->right));
- }
-}
-#endif
-
-#if defined(ZIX_TREE_VERIFY) || !defined(NDEBUG)
-static bool
-verify_balance(ZixTreeNode* n)
-{
- if (!n) {
- return true;
- }
-
- if (n->balance < -2 || n->balance > 2) {
- fprintf(stderr, "Balance out of range : %ld (balance %d)\n",
- (intptr_t)n->data, n->balance);
- return false;
- }
-
- if (n->balance < 0 && !n->left) {
- fprintf(stderr, "Bad balance : %ld (balance %d) has no left child\n",
- (intptr_t)n->data, n->balance);
- return false;
- }
-
- if (n->balance > 0 && !n->right) {
- fprintf(stderr, "Bad balance : %ld (balance %d) has no right child\n",
- (intptr_t)n->data, n->balance);
- return false;
- }
-
- if (n->balance != 0 && !n->left && !n->right) {
- fprintf(stderr, "Bad balance : %ld (balance %d) has no children\n",
- (intptr_t)n->data, n->balance);
- return false;
- }
-
-#ifdef ZIX_TREE_HYPER_VERIFY
- const intptr_t left_height = (intptr_t)height(n->left);
- const intptr_t right_height = (intptr_t)height(n->right);
- if (n->balance != right_height - left_height) {
- fprintf(stderr, "Bad balance at %ld: h_r (%" PRIdPTR ")"
- "- l_h (%" PRIdPTR ") != %d\n",
- (intptr_t)n->data, right_height, left_height, n->balance);
- assert(false);
- return false;
- }
-#endif
-
- return true;
-}
-#endif
-
-#ifdef ZIX_TREE_VERIFY
-static bool
-verify(ZixTree* t, ZixTreeNode* n)
-{
- if (!n) {
- return true;
- }
-
- if (n->parent) {
- if ((n->parent->left != n) && (n->parent->right != n)) {
- fprintf(stderr, "Corrupt child/parent pointers\n");
- return false;
- }
- }
-
- if (n->left) {
- if (t->cmp(n->left->data, n->data, t->cmp_data) > 0) {
- fprintf(stderr, "Bad order: %" PRIdPTR " with left child\n",
- (intptr_t)n->data);
- fprintf(stderr, "%p ? %p\n", (void*)n, (void*)n->left);
- fprintf(stderr, "%" PRIdPTR " ? %" PRIdPTR "\n", (intptr_t)n->data,
- (intptr_t)n->left->data);
- return false;
- }
- if (!verify(t, n->left)) {
- return false;
- }
- }
-
- if (n->right) {
- if (t->cmp(n->right->data, n->data, t->cmp_data) < 0) {
- fprintf(stderr, "Bad order: %" PRIdPTR " with right child\n",
- (intptr_t)n->data);
- return false;
- }
- if (!verify(t, n->right)) {
- return false;
- }
- }
-
- if (!verify_balance(n)) {
- return false;
- }
-
- if (n->balance <= -2 || n->balance >= 2) {
- fprintf(stderr, "Imbalance: %p (balance %d)\n",
- (void*)n, n->balance);
- return false;
- }
-
- return true;
-}
-#endif
-
-#endif // ZIX_TREE_DEBUG_H
generated by cgit v1.2.1 (git 2.18.0) at 2024-11-17 08:21:53 +0000