diff options
Diffstat (limited to 'zix')
| -rw-r--r-- | zix/chunk.c | 32 | ||||
| -rw-r--r-- | zix/chunk.h | 47 | ||||
| -rw-r--r-- | zix/common.h | 5 | ||||
| -rw-r--r-- | zix/digest.c | 56 | ||||
| -rw-r--r-- | zix/digest.h | 39 | ||||
| -rw-r--r-- | zix/fat_patree.c | 239 | ||||
| -rw-r--r-- | zix/hash.c | 228 | ||||
| -rw-r--r-- | zix/hash.h | 123 | ||||
| -rw-r--r-- | zix/patree.c | 373 | ||||
| -rw-r--r-- | zix/ring.c | 225 | ||||
| -rw-r--r-- | zix/sorted_array.c | 205 | ||||
| -rw-r--r-- | zix/strindex.c | 253 | ||||
| -rw-r--r-- | zix/tree.c | 716 | ||||
| -rw-r--r-- | zix/tree.h | 45 | ||||
| -rw-r--r-- | zix/tree_debug.h | 159 |
15 files changed, 2686 insertions, 59 deletions
diff --git a/zix/chunk.c b/zix/chunk.c new file mode 100644 index 0000000..4533b26 --- /dev/null +++ b/zix/chunk.c @@ -0,0 +1,32 @@ +/* + Copyright 2012 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 <string.h> + +#include "zix/chunk.h" +#include "zix/digest.h" + +ZIX_API uint32_t +zix_chunk_hash(const ZixChunk* const chunk) +{ + return zix_digest_add(zix_digest_start(), chunk->buf, chunk->len); +} + +ZIX_API bool +zix_chunk_equal(const ZixChunk* a, const ZixChunk* b) +{ + return a->len == b->len && !memcmp(a->buf, b->buf, a->len); +} diff --git a/zix/chunk.h b/zix/chunk.h new file mode 100644 index 0000000..6efa766 --- /dev/null +++ b/zix/chunk.h @@ -0,0 +1,47 @@ +/* + Copyright 2012 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_CHUNK_H +#define ZIX_CHUNK_H + +#include <stddef.h> +#include <stdint.h> + +#include "zix/common.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/** + A chunk of memory. +*/ +typedef struct { + void* buf; /**< Start of memory chunk */ + size_t len; /**< Length of memory chunk */ +} ZixChunk; + +ZIX_API uint32_t +zix_chunk_hash(const ZixChunk* chunk); + +ZIX_API bool +zix_chunk_equal(const ZixChunk* a, const ZixChunk* b); + +#ifdef __cplusplus +} /* extern "C" */ +#endif + +#endif /* ZIX_CHUNK_H */ diff --git a/zix/common.h b/zix/common.h index 59e1f55..f126cd1 100644 --- a/zix/common.h +++ b/zix/common.h @@ -36,8 +36,13 @@ # else # define ZIX_API ZIX_LIB_IMPORT # endif +# define ZIX_PRIVATE static +#elif defined(ZIX_INLINE) +# define ZIX_API static inline +# define ZIX_PRIVATE static inline #else # define ZIX_API +# define ZIX_PRIVATE static #endif /** @endcond */ diff --git a/zix/digest.c b/zix/digest.c new file mode 100644 index 0000000..4e8e974 --- /dev/null +++ b/zix/digest.c @@ -0,0 +1,56 @@ +/* + Copyright 2012 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 "zix/digest.h" + +#ifdef __SSE4_2__ +# include <smmintrin.h> +#endif + +ZIX_API uint32_t +zix_digest_start(void) +{ +#ifdef __SSE4_2__ + return 1; // CRC32 initial value +#else + return 5381; // DJB hash initial value +#endif +} + +ZIX_API uint32_t +zix_digest_add(uint32_t hash, const void* buf, const size_t len) +{ +#ifdef __SSE4_2__ + // SSE 4.2 CRC32 + for (size_t i = 0; i < (len / sizeof(uint32_t)); ++i) { + hash = _mm_crc32_u32(hash, *(uint32_t*)buf); + buf += sizeof(uint32_t); + } + if (len & sizeof(uint16_t)) { + hash = _mm_crc32_u16(hash, *(uint16_t*)buf); + buf += sizeof(uint16_t); + } + if (len & sizeof(uint8_t)) { + hash = _mm_crc32_u8(hash, *(uint8_t*)buf); + } +#else + // Classic DJB hash + for (size_t i = 0; i < len; ++i) { + hash = (hash << 5) + hash + ((const uint8_t*)buf)[i]; + } +#endif + return hash; +} diff --git a/zix/digest.h b/zix/digest.h new file mode 100644 index 0000000..34ab376 --- /dev/null +++ b/zix/digest.h @@ -0,0 +1,39 @@ +/* + Copyright 2012 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_DIGEST_H +#define ZIX_DIGEST_H + +#include <stddef.h> +#include <stdint.h> + +#include "zix/common.h" + +#ifdef __cplusplus +extern "C" { +#endif + +ZIX_API uint32_t +zix_digest_start(void); + +ZIX_API uint32_t +zix_digest_add(uint32_t hash, const void* buf, const size_t len); + +#ifdef __cplusplus +} /* extern "C" */ +#endif + +#endif /* ZIX_DIGEST_H */ diff --git a/zix/fat_patree.c b/zix/fat_patree.c new file mode 100644 index 0000000..454cfba --- /dev/null +++ b/zix/fat_patree.c @@ -0,0 +1,239 @@ +/* + 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/zix/hash.c b/zix/hash.c new file mode 100644 index 0000000..b24ee78 --- /dev/null +++ b/zix/hash.c @@ -0,0 +1,228 @@ +/* + 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 <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 ZixHashEntry { + struct ZixHashEntry* next; ///< Next entry in bucket + uint32_t hash; ///< Non-modulo hash value + // Value follows here (access with zix_hash_value) +} ZixHashEntry; + +struct ZixHashImpl { + ZixHashFunc hash_func; + ZixEqualFunc equal_func; + ZixHashEntry** buckets; + const unsigned* n_buckets; + size_t value_size; + unsigned count; +}; + +static inline const void* +zix_hash_value(const ZixHashEntry* entry) +{ + return entry + 1; +} + +ZIX_API ZixHash* +zix_hash_new(ZixHashFunc hash_func, + ZixEqualFunc equal_func, + size_t value_size) +{ + ZixHash* hash = (ZixHash*)malloc(sizeof(ZixHash)); + hash->hash_func = hash_func; + hash->equal_func = equal_func; + hash->n_buckets = &sizes[0]; + hash->value_size = value_size; + hash->count = 0; + hash->buckets = (ZixHashEntry**)calloc(*hash->n_buckets, + sizeof(ZixHashEntry*)); + return hash; +} + +ZIX_API void +zix_hash_free(ZixHash* hash) +{ + for (unsigned b = 0; b < *hash->n_buckets; ++b) { + ZixHashEntry* bucket = hash->buckets[b]; + for (ZixHashEntry* e = bucket; e;) { + ZixHashEntry* next = e->next; + free(e); + e = next; + } + } + + free(hash->buckets); + free(hash); +} + +ZIX_API size_t +zix_hash_size(const ZixHash* hash) +{ + return hash->count; +} + +static inline void +insert_entry(ZixHashEntry** bucket, ZixHashEntry* entry) +{ + entry->next = *bucket; + *bucket = entry; +} + +static inline ZixStatus +rehash(ZixHash* hash, unsigned new_n_buckets) +{ + ZixHashEntry** new_buckets = (ZixHashEntry**)calloc( + new_n_buckets, sizeof(ZixHashEntry*)); + if (!new_buckets) { + return ZIX_STATUS_NO_MEM; + } + + const unsigned old_n_buckets = *hash->n_buckets; + for (unsigned b = 0; b < old_n_buckets; ++b) { + for (ZixHashEntry* e = hash->buckets[b]; e;) { + ZixHashEntry* 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 inline ZixHashEntry* +find_entry(const ZixHash* hash, + const void* key, + const unsigned h, + const unsigned h_nomod) +{ + for (ZixHashEntry* e = hash->buckets[h]; e; e = e->next) { + if (e->hash == h_nomod && hash->equal_func(zix_hash_value(e), key)) { + return e; + } + } + return NULL; +} + +ZIX_API const void* +zix_hash_find(const ZixHash* hash, const void* value) +{ + const unsigned h_nomod = hash->hash_func(value); + const unsigned h = h_nomod % *hash->n_buckets; + ZixHashEntry* const entry = find_entry(hash, value, h, h_nomod); + return entry ? zix_hash_value(entry) : 0; +} + +ZIX_API ZixStatus +zix_hash_insert(ZixHash* hash, const void* value, const void** inserted) +{ + unsigned h_nomod = hash->hash_func(value); + unsigned h = h_nomod % *hash->n_buckets; + + ZixHashEntry* elem = find_entry(hash, value, h, h_nomod); + if (elem) { + assert(elem->hash == h_nomod); + if (inserted) { + *inserted = zix_hash_value(elem); + } + return ZIX_STATUS_EXISTS; + } + + elem = (ZixHashEntry*)malloc(sizeof(ZixHashEntry) + hash->value_size); + if (!elem) { + return ZIX_STATUS_NO_MEM; + } + elem->next = NULL; + elem->hash = h_nomod; + memcpy(elem + 1, value, hash->value_size); + + 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; + if (inserted) { + *inserted = zix_hash_value(elem); + } + return ZIX_STATUS_SUCCESS; +} + +ZIX_API ZixStatus +zix_hash_remove(ZixHash* hash, const void* value) +{ + const unsigned h_nomod = hash->hash_func(value); + const unsigned h = h_nomod % *hash->n_buckets; + + ZixHashEntry** next_ptr = &hash->buckets[h]; + for (ZixHashEntry* e = hash->buckets[h]; e; e = e->next) { + if (h_nomod == e->hash && + hash->equal_func(zix_hash_value(e), value)) { + *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, + ZixHashVisitFunc f, + void* user_data) +{ + for (unsigned b = 0; b < *hash->n_buckets; ++b) { + ZixHashEntry* bucket = hash->buckets[b]; + for (const ZixHashEntry* e = bucket; e; e = e->next) { + f(zix_hash_value(e), user_data); + } + } +} + @@ -1,5 +1,5 @@ /* - Copyright 2011 David Robillard <http://drobilla.net> + Copyright 2011-2012 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 @@ -17,56 +17,121 @@ #ifndef ZIX_HASH_H #define ZIX_HASH_H +#include <stddef.h> +#include <stdint.h> + #include "zix/common.h" #ifdef __cplusplus extern "C" { #endif +/** + @addtogroup zix + @{ + @name Hash + @{ +*/ + typedef struct ZixHashImpl ZixHash; /** Function for computing the hash of an element. */ -typedef unsigned (*ZixHashFunc)(const void* key); +typedef uint32_t (*ZixHashFunc)(const void* value); + +/** + Function to visit a hash element. +*/ +typedef void (*ZixHashVisitFunc)(const void* value, + void* user_data); -ZIX_API -ZixHash* +/** + Create a new hash table. + + To minimize space overhead, unlike many hash tables this stores a single + value, not a key and a value. Any size of value can be stored, but all the + values in the hash table must be the same size, and the values must be safe + to copy with memcpy. To get key:value behaviour, simply insert a struct + with a key and value into the hash. + + @param hash_func The hashing function. + @param equal_func A function to test value equality. + @param value_size The size of the values to be stored. +*/ +ZIX_API ZixHash* zix_hash_new(ZixHashFunc hash_func, - ZixEqualFunc key_equal_func); + ZixEqualFunc equal_func, + size_t value_size); -ZIX_API -void +/** + Free @p hash. +*/ +ZIX_API void zix_hash_free(ZixHash* hash); -ZIX_API -unsigned -zix_string_hash(const void* key); +/** + Return the number of elements in @p hash. +*/ +ZIX_API size_t +zix_hash_size(const ZixHash* hash); + +/** + Insert an item into @p hash. + + If no matching value is found, ZIX_STATUS_SUCCESS will be returned, and @p + inserted will be pointed to the copy of @p value made in the new hash node. + + If a matching value already exists, ZIX_STATUS_EXISTS will be returned, and + @p inserted will be pointed to the existing value. + + @param hash The hash table. + @param value The value to be inserted. + @param inserted The copy of @p value in the hash table. + @return ZIX_STATUS_SUCCESS, ZIX_STATUS_EXISTS, or ZIX_STATUS_NO_MEM. +*/ +ZIX_API ZixStatus +zix_hash_insert(ZixHash* hash, + const void* value, + const void** inserted); -ZIX_API -bool -zix_string_equal(const void* a, const void* b); +/** + Remove an item from @p hash. -ZIX_API -ZixStatus -zix_hash_insert(ZixHash* hash, - const void* key, - void* data); + @param hash The hash table. + @param value The value to remove. + @return ZIX_STATUS_SUCCES or ZIX_STATUS_NOT_FOUND. +*/ +ZIX_API ZixStatus +zix_hash_remove(ZixHash* hash, + const void* value); -ZIX_API -ZixStatus -zix_hash_remove(ZixHash* hash, const void* key); +/** + Search for an item in @p hash. -ZIX_API -void* + @param hash The hash table. + @param value The value to search for. +*/ +ZIX_API const void* zix_hash_find(const ZixHash* hash, - const void* key); + const void* value); + +/** + Call @p f on each value in @p hash. -ZIX_API -void -zix_hash_foreach(const ZixHash* hash, - void (*f)(const void* key, void* value, void* user_data), - void* user_data); + @param hash The hash table. + @param f The function to call on each value. + @param user_data The user_data parameter passed to @p f. +*/ +ZIX_API void +zix_hash_foreach(const ZixHash* hash, + ZixHashVisitFunc f, + void* user_data); + +/** + @} + @} +*/ #ifdef __cplusplus } /* extern "C" */ diff --git a/zix/patree.c b/zix/patree.c new file mode 100644 index 0000000..f3603a2 --- /dev/null +++ b/zix/patree.c @@ -0,0 +1,373 @@ +/* + 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/zix/ring.c b/zix/ring.c new file mode 100644 index 0000000..b701497 --- /dev/null +++ b/zix/ring.c @@ -0,0 +1,225 @@ +/* + 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/zix/sorted_array.c b/zix/sorted_array.c new file mode 100644 index 0000000..f8e785d --- /dev/null +++ b/zix/sorted_array.c @@ -0,0 +1,205 @@ +/* + 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/zix/strindex.c b/zix/strindex.c new file mode 100644 index 0000000..bd97db5 --- /dev/null +++ b/zix/strindex.c @@ -0,0 +1,253 @@ +/* + 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/zix/tree.c b/zix/tree.c new file mode 100644 index 0000000..844adb9 --- /dev/null +++ b/zix/tree.c @@ -0,0 +1,716 @@ +/* + 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; +} + +ZIX_PRIVATE 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); + } +} + +ZIX_API size_t +zix_tree_size(const ZixTree* t) +{ + return t->size; +} + +ZIX_PRIVATE 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 + */ +ZIX_PRIVATE 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 + * + */ +ZIX_PRIVATE 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 + * + */ +ZIX_PRIVATE 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 + * + */ +ZIX_PRIVATE 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; +} + +ZIX_PRIVATE 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; +} @@ -45,8 +45,7 @@ typedef struct ZixTreeNodeImpl ZixTreeIter; /** Create a new (empty) tree. */ -ZIX_API -ZixTree* +ZIX_API ZixTree* zix_tree_new(bool allow_duplicates, ZixComparator cmp, void* cmp_data, @@ -55,100 +54,86 @@ zix_tree_new(bool allow_duplicates, /** Free @a t. */ -ZIX_API -void +ZIX_API void zix_tree_free(ZixTree* t); /** Return the number of elements in @a t. */ -ZIX_API -size_t +ZIX_API size_t zix_tree_size(const ZixTree* t); /** Insert the element @a e into @a t and point @a ti at the new element. */ -ZIX_API -ZixStatus +ZIX_API ZixStatus zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti); /** Remove the item pointed at by @a ti from @a t. */ -ZIX_API -ZixStatus +ZIX_API 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. */ -ZIX_API -ZixStatus +ZIX_API ZixStatus zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti); /** Return the data associated with the given tree item. */ -ZIX_API -void* +ZIX_API void* zix_tree_get(ZixTreeIter* ti); /** Return an iterator to the first (smallest) element in @a t. */ -ZIX_API -ZixTreeIter* +ZIX_API ZixTreeIter* zix_tree_begin(ZixTree* t); /** Return an iterator the the element one past the last element in @a t. */ -ZIX_API -ZixTreeIter* +ZIX_API ZixTreeIter* zix_tree_end(ZixTree* t); /** Return true iff @a i is an iterator to the end of its tree. */ -ZIX_API -bool +ZIX_API bool zix_tree_iter_is_end(ZixTreeIter* i); /** Return an iterator to the last (largest) element in @a t. */ -ZIX_API -ZixTreeIter* +ZIX_API ZixTreeIter* zix_tree_rbegin(ZixTree* t); /** Return an iterator the the element one before the first element in @a t. */ -ZIX_API -ZixTreeIter* +ZIX_API ZixTreeIter* zix_tree_rend(ZixTree* t); /** Return true iff @a i is an iterator to the reverse end of its tree. */ -ZIX_API -bool +ZIX_API bool zix_tree_iter_is_rend(ZixTreeIter* i); /** Return an iterator that points to the element one past @a i. */ -ZIX_API -ZixTreeIter* +ZIX_API ZixTreeIter* zix_tree_iter_next(ZixTreeIter* i); /** Return an iterator that points to the element one before @a i. */ -ZIX_API -ZixTreeIter* +ZIX_API ZixTreeIter* zix_tree_iter_prev(ZixTreeIter* i); /** diff --git a/zix/tree_debug.h b/zix/tree_debug.h new file mode 100644 index 0000000..e903265 --- /dev/null +++ b/zix/tree_debug.h @@ -0,0 +1,159 @@ +/* + 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 |