summaryrefslogtreecommitdiffstats
path: root/zix
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2020-12-31 15:34:15 +0100
committerDavid Robillard <d@drobilla.net>2020-12-31 15:34:15 +0100
commited9a6e98b8e4e010117e1228333569aa31c51d9e (patch)
tree3c333f1c7ce2109222d06aa026b939e379e55b5d /zix
parentde27dcfe0bb72ef1ec937c4aaee26eef6ff7918e (diff)
downloadzix-ed9a6e98b8e4e010117e1228333569aa31c51d9e.tar.gz
zix-ed9a6e98b8e4e010117e1228333569aa31c51d9e.tar.bz2
zix-ed9a6e98b8e4e010117e1228333569aa31c51d9e.zip
Separate source from headers
Diffstat (limited to 'zix')
-rw-r--r--zix/bitset.c124
-rw-r--r--zix/bitset.h106
-rw-r--r--zix/btree.c957
-rw-r--r--zix/btree.h187
-rw-r--r--zix/chunk.c33
-rw-r--r--zix/chunk.h50
-rw-r--r--zix/common.h150
-rw-r--r--zix/digest.c141
-rw-r--r--zix/digest.h67
-rw-r--r--zix/hash.c230
-rw-r--r--zix/hash.h138
-rw-r--r--zix/ring.c222
-rw-r--r--zix/ring.h141
-rw-r--r--zix/sem.h242
-rw-r--r--zix/sorted_array.c193
-rw-r--r--zix/sorted_array.h147
-rw-r--r--zix/strindex.c261
-rw-r--r--zix/strindex.h59
-rw-r--r--zix/thread.h132
-rw-r--r--zix/tree.c735
-rw-r--r--zix/tree.h164
-rw-r--r--zix/tree_debug.h175
-rw-r--r--zix/zix.h35
23 files changed, 0 insertions, 4689 deletions
diff --git a/zix/bitset.c b/zix/bitset.c
deleted file mode 100644
index cf82ad0..0000000
--- a/zix/bitset.c
+++ /dev/null
@@ -1,124 +0,0 @@
-/*
- Copyright 2014-2016 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/bitset.h"
-
-#ifdef _MSC_VER
-# include <intrin.h>
-#endif
-
-#include <string.h>
-
-/** Number of bits per ZixBitset element (ala CHAR_BIT). */
-#define ZIX_BITSET_ELEM_BIT (CHAR_BIT * sizeof(ZixBitset))
-
-static inline size_t
-zix_bitset_popcount(const ZixBitset value)
-{
-#ifdef _MSC_VER
- return (size_t)__popcnt(value);
-#else
- return (size_t)__builtin_popcountl(value);
-#endif
-}
-
-void
-zix_bitset_clear(ZixBitset* b, ZixBitsetTally* t, size_t n_bits)
-{
- memset(b, 0, ZIX_BITSET_ELEMS(n_bits) * sizeof(ZixBitset));
- memset(t, 0, ZIX_BITSET_ELEMS(n_bits) * sizeof(ZixBitsetTally));
-}
-
-void
-zix_bitset_set(ZixBitset* b, ZixBitsetTally* t, size_t i)
-{
- const size_t e = i / ZIX_BITSET_ELEM_BIT;
- const size_t ebit = i & (ZIX_BITSET_ELEM_BIT - 1); // i % ELEM_BIT
- const ZixBitset mask = (ZixBitset)1 << ebit;
-
- if (!(b[e] & mask)) {
- ++t[e];
- }
-
- b[e] |= mask;
-}
-
-void
-zix_bitset_reset(ZixBitset* b, ZixBitsetTally* t, size_t i)
-{
- const size_t e = i / ZIX_BITSET_ELEM_BIT;
- const size_t ebit = i & (ZIX_BITSET_ELEM_BIT - 1); // i % ELEM_BIT
- const ZixBitset mask = (ZixBitset)1 << ebit;
-
- if (b[e] & mask) {
- --t[e];
- }
-
- b[e] &= ~mask;
-}
-
-bool
-zix_bitset_get(const ZixBitset* b, size_t i)
-{
- const size_t e = i / ZIX_BITSET_ELEM_BIT;
- const size_t ebit = i & (ZIX_BITSET_ELEM_BIT - 1); // i % ELEM_BIT
- const ZixBitset mask = (ZixBitset)1 << ebit;
-
- return b[e] & mask;
-}
-
-size_t
-zix_bitset_count_up_to(const ZixBitset* b, const ZixBitsetTally* t, size_t i)
-{
- const size_t full_elems = i / ZIX_BITSET_ELEM_BIT;
- const size_t extra = i & (ZIX_BITSET_ELEM_BIT - 1); // i % ELEM_BIT
-
- size_t count = 0;
- for (size_t e = 0; e < full_elems; ++e) {
- count += t[e];
- }
-
- if (extra) {
- const ZixBitset mask = ~(~(ZixBitset)0 << extra);
- count += zix_bitset_popcount(b[full_elems] & mask);
- }
-
- return count;
-}
-
-size_t
-zix_bitset_count_up_to_if(const ZixBitset* b, const ZixBitsetTally* t, size_t i)
-{
- const size_t full_elems = i / ZIX_BITSET_ELEM_BIT;
- const size_t extra = i & (ZIX_BITSET_ELEM_BIT - 1); // i % ELEM_BIT
-
- const ZixBitset get_mask = (ZixBitset)1 << extra;
- if (!(b[full_elems] & get_mask)) {
- return (size_t)-1;
- }
-
- size_t count = 0;
- for (size_t e = 0; e < full_elems; ++e) {
- count += t[e];
- }
-
- if (extra) {
- const ZixBitset mask = ~(~(ZixBitset)0 << extra);
- count += zix_bitset_popcount(b[full_elems] & mask);
- }
-
- return count;
-}
diff --git a/zix/bitset.h b/zix/bitset.h
deleted file mode 100644
index 68dd344..0000000
--- a/zix/bitset.h
+++ /dev/null
@@ -1,106 +0,0 @@
-/*
- Copyright 2014-2016 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_BITSET_H
-#define ZIX_BITSET_H
-
-#include "zix/common.h"
-
-#include <limits.h>
-#include <stdbool.h>
-#include <stddef.h>
-#include <stdint.h>
-
-/**
- @addtogroup zix
- @{
- @name Bitset
- @{
-*/
-
-/**
- A bitset (always referred to by pointer, actually an array).
-*/
-typedef unsigned long ZixBitset;
-
-/**
- Tally of the number of bits in one ZixBitset element.
-*/
-typedef uint8_t ZixBitsetTally;
-
-/**
- The number of bits per ZixBitset array element.
-*/
-#define ZIX_BITSET_BITS_PER_ELEM (CHAR_BIT * sizeof(ZixBitset))
-
-/**
- The number of bitset elements needed for the given number of bits.
-*/
-#define ZIX_BITSET_ELEMS(n_bits) \
- (((n_bits) / ZIX_BITSET_BITS_PER_ELEM) + \
- ((n_bits) % ZIX_BITSET_BITS_PER_ELEM ? 1 : 0))
-
-/**
- Clear a Bitset.
-*/
-ZIX_API
-void
-zix_bitset_clear(ZixBitset* b, ZixBitsetTally* t, size_t n_bits);
-
-/**
- Set bit `i` in `t` to 1.
-*/
-ZIX_API
-void
-zix_bitset_set(ZixBitset* b, ZixBitsetTally* t, size_t i);
-
-/**
- Clear bit `i` in `t` (set to 0).
-*/
-ZIX_API
-void
-zix_bitset_reset(ZixBitset* b, ZixBitsetTally* t, size_t i);
-
-/**
- Return the `i`th bit in `t`.
-*/
-ZIX_PURE_API
-bool
-zix_bitset_get(const ZixBitset* b, size_t i);
-
-/**
- Return the number of set bits in `b` up to bit `i` (non-inclusive).
-*/
-ZIX_PURE_API
-size_t
-zix_bitset_count_up_to(const ZixBitset* b, const ZixBitsetTally* t, size_t i);
-
-/**
- Return the number of set bits in `b` up to bit `i` (non-inclusive) if bit
- `i` is set, or (size_t)-1 otherwise.
-*/
-ZIX_PURE_API
-size_t
-zix_bitset_count_up_to_if(const ZixBitset* b,
- const ZixBitsetTally* t,
- size_t i);
-
-/**
- @}
- @}
-*/
-
-#endif /* ZIX_BITSET_H */
diff --git a/zix/btree.c b/zix/btree.c
deleted file mode 100644
index 7435445..0000000
--- a/zix/btree.c
+++ /dev/null
@@ -1,957 +0,0 @@
-/*
- Copyright 2011-2020 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/btree.h"
-
-#include <assert.h>
-#include <stdint.h>
-#include <stdlib.h>
-#include <string.h>
-
-// #define ZIX_BTREE_DEBUG 1
-// #define ZIX_BTREE_SORTED_CHECK 1
-
-#ifndef ZIX_BTREE_PAGE_SIZE
-# define ZIX_BTREE_PAGE_SIZE 4096
-#endif
-
-#define ZIX_BTREE_NODE_SPACE (ZIX_BTREE_PAGE_SIZE - 2 * sizeof(uint16_t))
-#define ZIX_BTREE_LEAF_VALS ((ZIX_BTREE_NODE_SPACE / sizeof(void*)) - 1)
-#define ZIX_BTREE_INODE_VALS (ZIX_BTREE_LEAF_VALS / 2)
-
-struct ZixBTreeImpl {
- ZixBTreeNode* root;
- ZixDestroyFunc destroy;
- ZixComparator cmp;
- const void* cmp_data;
- size_t size;
- unsigned height; ///< Number of levels, i.e. root only has height 1
-};
-
-struct ZixBTreeNodeImpl {
- uint16_t is_leaf;
- uint16_t n_vals;
- // On 64-bit we rely on some padding here to get page-sized nodes
- union {
- struct {
- void* vals[ZIX_BTREE_LEAF_VALS];
- } leaf;
-
- struct {
- void* vals[ZIX_BTREE_INODE_VALS];
- ZixBTreeNode* children[ZIX_BTREE_INODE_VALS + 1];
- } inode;
- } data;
-};
-
-#if (defined(__STDC_VERSION__) && __STDC_VERSION__ >= 201112l) || \
- (defined(__cplusplus) && __cplusplus >= 201103L)
-static_assert(sizeof(ZixBTreeNode) == ZIX_BTREE_PAGE_SIZE, "");
-#endif
-
-typedef struct {
- ZixBTreeNode* node;
- unsigned index;
-} ZixBTreeIterFrame;
-
-struct ZixBTreeIterImpl {
- unsigned n_levels; ///< Maximum depth of stack
- unsigned level; ///< Current level in stack
- ZixBTreeIterFrame stack[]; ///< Position stack
-};
-
-#ifdef ZIX_BTREE_DEBUG
-
-ZIX_PRIVATE
-void
-print_node(const ZixBTreeNode* n, const char* prefix)
-{
- printf("%s[", prefix);
- for (uint16_t v = 0; v < n->n_vals; ++v) {
- printf(" %lu", (uintptr_t)n->vals[v]);
- }
- printf(" ]\n");
-}
-
-ZIX_PRIVATE
-void
-print_tree(const ZixBTreeNode* parent, const ZixBTreeNode* node, int level)
-{
- if (node) {
- if (!parent) {
- printf("TREE {\n");
- }
- for (int i = 0; i < level + 1; ++i) {
- printf(" ");
- }
- print_node(node, "");
- if (!node->is_leaf) {
- for (uint16_t i = 0; i < node->n_vals + 1; ++i) {
- print_tree(node, node->data.inode.children[i], level + 1);
- }
- }
- if (!parent) {
- printf("}\n");
- }
- }
-}
-
-#endif // ZIX_BTREE_DEBUG
-
-ZIX_PRIVATE
-ZixBTreeNode*
-zix_btree_node_new(const bool leaf)
-{
-#if !((defined(__STDC_VERSION__) && __STDC_VERSION__ >= 201112l) || \
- (defined(__cplusplus) && __cplusplus >= 201103L))
- assert(sizeof(ZixBTreeNode) == ZIX_BTREE_PAGE_SIZE);
-#endif
-
- ZixBTreeNode* node = (ZixBTreeNode*)malloc(sizeof(ZixBTreeNode));
- if (node) {
- node->is_leaf = leaf;
- node->n_vals = 0;
- }
- return node;
-}
-
-ZIX_PRIVATE
-void*
-zix_btree_value(const ZixBTreeNode* const node, const unsigned i)
-{
- assert(i < node->n_vals);
- return node->is_leaf ? node->data.leaf.vals[i] : node->data.inode.vals[i];
-}
-
-ZIX_PRIVATE
-ZixBTreeNode*
-zix_btree_child(const ZixBTreeNode* const node, const unsigned i)
-{
- assert(!node->is_leaf);
- assert(i <= ZIX_BTREE_INODE_VALS);
- return node->data.inode.children[i];
-}
-
-ZixBTree*
-zix_btree_new(const ZixComparator cmp,
- const void* const cmp_data,
- const ZixDestroyFunc destroy)
-{
- ZixBTree* t = (ZixBTree*)malloc(sizeof(ZixBTree));
- if (t) {
- t->root = zix_btree_node_new(true);
- t->destroy = destroy;
- t->cmp = cmp;
- t->cmp_data = cmp_data;
- t->size = 0;
- t->height = 1;
- if (!t->root) {
- free(t);
- return NULL;
- }
- }
- return t;
-}
-
-ZIX_PRIVATE
-void
-zix_btree_free_rec(ZixBTree* const t, ZixBTreeNode* const n)
-{
- if (n) {
- if (n->is_leaf) {
- if (t->destroy) {
- for (uint16_t i = 0; i < n->n_vals; ++i) {
- t->destroy(n->data.leaf.vals[i]);
- }
- }
- } else {
- if (t->destroy) {
- for (uint16_t i = 0; i < n->n_vals; ++i) {
- t->destroy(n->data.inode.vals[i]);
- }
- }
-
- for (uint16_t i = 0; i < n->n_vals + 1; ++i) {
- zix_btree_free_rec(t, zix_btree_child(n, i));
- }
- }
-
- free(n);
- }
-}
-
-void
-zix_btree_free(ZixBTree* const t)
-{
- if (t) {
- zix_btree_free_rec(t, t->root);
- free(t);
- }
-}
-
-size_t
-zix_btree_size(const ZixBTree* const t)
-{
- return t->size;
-}
-
-ZIX_PRIVATE
-uint16_t
-zix_btree_max_vals(const ZixBTreeNode* const node)
-{
- return node->is_leaf ? ZIX_BTREE_LEAF_VALS : ZIX_BTREE_INODE_VALS;
-}
-
-ZIX_PRIVATE
-uint16_t
-zix_btree_min_vals(const ZixBTreeNode* const node)
-{
- return (uint16_t)(((zix_btree_max_vals(node) + 1U) / 2U) - 1U);
-}
-
-/** Shift pointers in `array` of length `n` right starting at `i`. */
-ZIX_PRIVATE
-void
-zix_btree_ainsert(void** const array,
- const unsigned n,
- const unsigned i,
- void* const e)
-{
- memmove(array + i + 1, array + i, (n - i) * sizeof(e));
- array[i] = e;
-}
-
-/** Erase element `i` in `array` of length `n` and return erased element. */
-ZIX_PRIVATE
-void*
-zix_btree_aerase(void** const array, const unsigned n, const unsigned i)
-{
- void* const ret = array[i];
- memmove(array + i, array + i + 1, (n - i) * sizeof(ret));
- return ret;
-}
-
-/** Split lhs, the i'th child of `n`, into two nodes. */
-ZIX_PRIVATE
-ZixBTreeNode*
-zix_btree_split_child(ZixBTreeNode* const n,
- const unsigned i,
- ZixBTreeNode* const lhs)
-{
- assert(lhs->n_vals == zix_btree_max_vals(lhs));
- assert(n->n_vals < ZIX_BTREE_INODE_VALS);
- assert(i < n->n_vals + 1U);
- assert(zix_btree_child(n, i) == lhs);
-
- const uint16_t max_n_vals = zix_btree_max_vals(lhs);
- ZixBTreeNode* rhs = zix_btree_node_new(lhs->is_leaf);
- if (!rhs) {
- return NULL;
- }
-
- // LHS and RHS get roughly half, less the middle value which moves up
- lhs->n_vals = max_n_vals / 2U;
- rhs->n_vals = (uint16_t)(max_n_vals - lhs->n_vals - 1);
-
- if (lhs->is_leaf) {
- // Copy large half from LHS to new RHS node
- memcpy(rhs->data.leaf.vals,
- lhs->data.leaf.vals + lhs->n_vals + 1,
- rhs->n_vals * sizeof(void*));
-
- // Move middle value up to parent
- zix_btree_ainsert(
- n->data.inode.vals, n->n_vals, i, lhs->data.leaf.vals[lhs->n_vals]);
- } else {
- // Copy large half from LHS to new RHS node
- memcpy(rhs->data.inode.vals,
- lhs->data.inode.vals + lhs->n_vals + 1,
- rhs->n_vals * sizeof(void*));
- memcpy(rhs->data.inode.children,
- lhs->data.inode.children + lhs->n_vals + 1,
- (rhs->n_vals + 1U) * sizeof(ZixBTreeNode*));
-
- // Move middle value up to parent
- zix_btree_ainsert(
- n->data.inode.vals, n->n_vals, i, lhs->data.inode.vals[lhs->n_vals]);
- }
-
- // Insert new RHS node in parent at position i
- zix_btree_ainsert((void**)n->data.inode.children, ++n->n_vals, i + 1U, rhs);
-
- return rhs;
-}
-
-#ifdef ZIX_BTREE_SORTED_CHECK
-/** Check that `n` is sorted with respect to search key `e`. */
-ZIX_PRIVATE
-bool
-zix_btree_node_is_sorted_with_respect_to(const ZixBTree* const t,
- const ZixBTreeNode* const n,
- const void* const e)
-{
- if (n->n_vals <= 1) {
- return true;
- }
-
- int cmp = t->cmp(zix_btree_value(n, 0), e, t->cmp_data);
- for (uint16_t i = 1; i < n->n_vals; ++i) {
- const int next_cmp = t->cmp(zix_btree_value(n, i), e, t->cmp_data);
- if ((cmp >= 0 && next_cmp < 0) || (cmp > 0 && next_cmp <= 0)) {
- return false;
- }
- cmp = next_cmp;
- }
-
- return true;
-}
-#endif
-
-/** Find the first value in `n` that is not less than `e` (lower bound). */
-ZIX_PRIVATE
-unsigned
-zix_btree_node_find(const ZixBTree* const t,
- const ZixBTreeNode* const n,
- const void* const e,
- bool* const equal)
-{
-#ifdef ZIX_BTREE_SORTED_CHECK
- assert(zix_btree_node_is_sorted_with_respect_to(t, n, e));
-#endif
-
- unsigned first = 0U;
- unsigned len = n->n_vals;
- while (len > 0) {
- const unsigned half = len >> 1U;
- const unsigned i = first + half;
- const int cmp = t->cmp(zix_btree_value(n, i), e, t->cmp_data);
- if (cmp == 0) {
- *equal = true;
- len = half; // Keep searching for wildcard matches
- } else if (cmp < 0) {
- const unsigned chop = half + 1U;
- first += chop;
- len -= chop;
- } else {
- len = half;
- }
- }
-
- assert(!*equal || t->cmp(zix_btree_value(n, first), e, t->cmp_data) == 0);
- return first;
-}
-
-ZixStatus
-zix_btree_insert(ZixBTree* const t, void* const e)
-{
- ZixBTreeNode* parent = NULL; // Parent of n
- ZixBTreeNode* n = t->root; // Current node
- unsigned i = 0; // Index of n in parent
- while (n) {
- if (n->n_vals == zix_btree_max_vals(n)) {
- // Node is full, split to ensure there is space for a leaf split
- if (!parent) {
- // Root is full, grow tree upwards
- if (!(parent = zix_btree_node_new(false))) {
- return ZIX_STATUS_NO_MEM;
- }
- t->root = parent;
- parent->data.inode.children[0] = n;
- ++t->height;
- }
-
- ZixBTreeNode* const rhs = zix_btree_split_child(parent, i, n);
- if (!rhs) {
- return ZIX_STATUS_NO_MEM;
- }
-
- const int cmp = t->cmp(parent->data.inode.vals[i], e, t->cmp_data);
- if (cmp == 0) {
- return ZIX_STATUS_EXISTS;
- }
-
- if (cmp < 0) {
- // Move to new RHS
- n = rhs;
- ++i;
- }
- }
-
- assert(!parent || zix_btree_child(parent, i) == n);
-
- bool equal = false;
- i = zix_btree_node_find(t, n, e, &equal);
- if (equal) {
- return ZIX_STATUS_EXISTS;
- }
-
- if (!n->is_leaf) {
- // Descend to child node left of value
- parent = n;
- n = zix_btree_child(n, i);
- } else {
- // Insert into internal node
- zix_btree_ainsert(n->data.leaf.vals, n->n_vals++, i, e);
- break;
- }
- }
-
- ++t->size;
-
- return ZIX_STATUS_SUCCESS;
-}
-
-ZIX_PRIVATE
-ZixBTreeIter*
-zix_btree_iter_new(const ZixBTree* const t)
-{
- const size_t s = t->height * sizeof(ZixBTreeIterFrame);
-
- ZixBTreeIter* i = (ZixBTreeIter*)calloc(1, sizeof(ZixBTreeIter) + s);
- if (i) {
- i->n_levels = t->height;
- }
- return i;
-}
-
-ZIX_PRIVATE
-void
-zix_btree_iter_set_frame(ZixBTreeIter* const ti,
- ZixBTreeNode* const n,
- const unsigned i)
-{
- if (ti) {
- ti->stack[ti->level].node = n;
- ti->stack[ti->level].index = i;
- }
-}
-
-ZIX_PRIVATE
-bool
-zix_btree_node_is_minimal(ZixBTreeNode* const n)
-{
- assert(n->n_vals >= zix_btree_min_vals(n));
- return n->n_vals == zix_btree_min_vals(n);
-}
-
-/** Enlarge left child by stealing a value from its right sibling. */
-ZIX_PRIVATE
-ZixBTreeNode*
-zix_btree_rotate_left(ZixBTreeNode* const parent, const unsigned i)
-{
- ZixBTreeNode* const lhs = zix_btree_child(parent, i);
- ZixBTreeNode* const rhs = zix_btree_child(parent, i + 1);
-
- assert(lhs->is_leaf == rhs->is_leaf);
-
- if (lhs->is_leaf) {
- // Move parent value to end of LHS
- lhs->data.leaf.vals[lhs->n_vals++] = parent->data.inode.vals[i];
-
- // Move first value in RHS to parent
- parent->data.inode.vals[i] =
- zix_btree_aerase(rhs->data.leaf.vals, rhs->n_vals, 0);
- } else {
- // Move parent value to end of LHS
- lhs->data.inode.vals[lhs->n_vals++] = parent->data.inode.vals[i];
-
- // Move first value in RHS to parent
- parent->data.inode.vals[i] =
- zix_btree_aerase(rhs->data.inode.vals, rhs->n_vals, 0);
-
- // Move first child pointer from RHS to end of LHS
- lhs->data.inode.children[lhs->n_vals] = (ZixBTreeNode*)zix_btree_aerase(
- (void**)rhs->data.inode.children, rhs->n_vals, 0);
- }
-
- --rhs->n_vals;
-
- return lhs;
-}
-
-/** Enlarge right child by stealing a value from its left sibling. */
-ZIX_PRIVATE
-ZixBTreeNode*
-zix_btree_rotate_right(ZixBTreeNode* const parent, const unsigned i)
-{
- ZixBTreeNode* const lhs = zix_btree_child(parent, i - 1);
- ZixBTreeNode* const rhs = zix_btree_child(parent, i);
-
- assert(lhs->is_leaf == rhs->is_leaf);
-
- if (lhs->is_leaf) {
- // Prepend parent value to RHS
- zix_btree_ainsert(
- rhs->data.leaf.vals, rhs->n_vals++, 0, parent->data.inode.vals[i - 1]);
-
- // Move last value from LHS to parent
- parent->data.inode.vals[i - 1] = lhs->data.leaf.vals[--lhs->n_vals];
- } else {
- // Prepend parent value to RHS
- zix_btree_ainsert(
- rhs->data.inode.vals, rhs->n_vals++, 0, parent->data.inode.vals[i - 1]);
-
- // Move last child pointer from LHS and prepend to RHS
- zix_btree_ainsert((void**)rhs->data.inode.children,
- rhs->n_vals,
- 0,
- lhs->data.inode.children[lhs->n_vals]);
-
- // Move last value from LHS to parent
- parent->data.inode.vals[i - 1] = lhs->data.inode.vals[--lhs->n_vals];
- }
-
- return rhs;
-}
-
-/** Move n[i] down, merge the left and right child, return the merged node. */
-ZIX_PRIVATE
-ZixBTreeNode*
-zix_btree_merge(ZixBTree* const t, ZixBTreeNode* const n, const unsigned i)
-{
- ZixBTreeNode* const lhs = zix_btree_child(n, i);
- ZixBTreeNode* const rhs = zix_btree_child(n, i + 1);
-
- assert(lhs->is_leaf == rhs->is_leaf);
- assert(zix_btree_node_is_minimal(lhs));
- assert(lhs->n_vals + rhs->n_vals < zix_btree_max_vals(lhs));
-
- // Move parent value to end of LHS
- if (lhs->is_leaf) {
- lhs->data.leaf.vals[lhs->n_vals++] =
- zix_btree_aerase(n->data.inode.vals, n->n_vals, i);
- } else {
- lhs->data.inode.vals[lhs->n_vals++] =
- zix_btree_aerase(n->data.inode.vals, n->n_vals, i);
- }
-
- // Erase corresponding child pointer (to RHS) in parent
- zix_btree_aerase((void**)n->data.inode.children, n->n_vals, i + 1U);
-
- // Add everything from RHS to end of LHS
- if (lhs->is_leaf) {
- memcpy(lhs->data.leaf.vals + lhs->n_vals,
- rhs->data.leaf.vals,
- rhs->n_vals * sizeof(void*));
- } else {
- memcpy(lhs->data.inode.vals + lhs->n_vals,
- rhs->data.inode.vals,
- rhs->n_vals * sizeof(void*));
- memcpy(lhs->data.inode.children + lhs->n_vals,
- rhs->data.inode.children,
- (rhs->n_vals + 1U) * sizeof(void*));
- }
-
- lhs->n_vals = (uint16_t)(lhs->n_vals + rhs->n_vals);
-
- if (--n->n_vals == 0) {
- // Root is now empty, replace it with its only child
- assert(n == t->root);
- t->root = lhs;
- free(n);
- }
-
- free(rhs);
- return lhs;
-}
-
-/** Remove and return the min value from the subtree rooted at `n`. */
-ZIX_PRIVATE
-void*
-zix_btree_remove_min(ZixBTree* const t, ZixBTreeNode* n)
-{
- while (!n->is_leaf) {
- if (zix_btree_node_is_minimal(zix_btree_child(n, 0))) {
- // Leftmost child is minimal, must expand
- if (!zix_btree_node_is_minimal(zix_btree_child(n, 1))) {
- // Child's right sibling has at least one key to steal
- n = zix_btree_rotate_left(n, 0);
- } else {
- // Both child and right sibling are minimal, merge
- n = zix_btree_merge(t, n, 0);
- }
- } else {
- n = zix_btree_child(n, 0);
- }
- }
-
- return zix_btree_aerase(n->data.leaf.vals, --n->n_vals, 0);
-}
-
-/** Remove and return the max value from the subtree rooted at `n`. */
-ZIX_PRIVATE
-void*
-zix_btree_remove_max(ZixBTree* const t, ZixBTreeNode* n)
-{
- while (!n->is_leaf) {
- if (zix_btree_node_is_minimal(zix_btree_child(n, n->n_vals))) {
- // Leftmost child is minimal, must expand
- if (!zix_btree_node_is_minimal(zix_btree_child(n, n->n_vals - 1))) {
- // Child's left sibling has at least one key to steal
- n = zix_btree_rotate_right(n, n->n_vals);
- } else {
- // Both child and left sibling are minimal, merge
- n = zix_btree_merge(t, n, n->n_vals - 1U);
- }
- } else {
- n = zix_btree_child(n, n->n_vals);
- }
- }
-
- return n->data.leaf.vals[--n->n_vals];
-}
-
-ZixStatus
-zix_btree_remove(ZixBTree* const t,
- const void* const e,
- void** const out,
- ZixBTreeIter** const next)
-{
- ZixBTreeNode* n = t->root;
- ZixBTreeIter* ti = NULL;
- const bool user_iter = next && *next;
- if (next) {
- if (!*next && !(*next = zix_btree_iter_new(t))) {
- return ZIX_STATUS_NO_MEM;
- }
- ti = *next;
- ti->level = 0;
- }
-
- while (true) {
- /* To remove in a single walk down, the tree is adjusted along the way
- so that the current node always has at least one more value than the
- minimum required in general. Thus, there is always room to remove
- without adjusting on the way back up. */
- assert(n == t->root || !zix_btree_node_is_minimal(n));
-
- bool equal = false;
- const unsigned i = zix_btree_node_find(t, n, e, &equal);
- zix_btree_iter_set_frame(ti, n, i);
- if (n->is_leaf) {
- if (equal) {
- // Found in leaf node
- *out = zix_btree_aerase(n->data.leaf.vals, --n->n_vals, i);
- if (ti && i == n->n_vals) {
- if (i == 0) {
- ti->level = 0;
- ti->stack[0].node = NULL;
- } else {
- --ti->stack[ti->level].index;
- zix_btree_iter_increment(ti);
- }
- }
- --t->size;
- return ZIX_STATUS_SUCCESS;
- }
-
- // Not found in leaf node, or tree
- if (ti && !user_iter) {
- zix_btree_iter_free(ti);
- *next = NULL;
- }
-
- return ZIX_STATUS_NOT_FOUND;
- }
-
- if (equal) {
- // Found in internal node
- ZixBTreeNode* const lhs = zix_btree_child(n, i);
- ZixBTreeNode* const rhs = zix_btree_child(n, i + 1);
- const size_t l_size = lhs->n_vals;
- const size_t r_size = rhs->n_vals;
- if (zix_btree_node_is_minimal(lhs) && zix_btree_node_is_minimal(rhs)) {
- // Both preceding and succeeding child are minimal
- n = zix_btree_merge(t, n, i);
- } else if (l_size >= r_size) {
- // Left child can remove without merge
- assert(!zix_btree_node_is_minimal(lhs));
- *out = n->data.inode.vals[i];
- n->data.inode.vals[i] = zix_btree_remove_max(t, lhs);
- --t->size;
- return ZIX_STATUS_SUCCESS;
- } else {
- // Right child can remove without merge
- assert(!zix_btree_node_is_minimal(rhs));
- *out = n->data.inode.vals[i];
- n->data.inode.vals[i] = zix_btree_remove_min(t, rhs);
- --t->size;
- return ZIX_STATUS_SUCCESS;
- }
- } else {
- // Not found in internal node, key is in/under children[i]
- if (zix_btree_node_is_minimal(zix_btree_child(n, i))) {
- if (i > 0 && !zix_btree_node_is_minimal(zix_btree_child(n, i - 1))) {
- // Steal a key from child's left sibling
- n = zix_btree_rotate_right(n, i);
- } else if (i < n->n_vals &&
- !zix_btree_node_is_minimal(zix_btree_child(n, i + 1))) {
- // Steal a key from child's right sibling
- n = zix_btree_rotate_left(n, i);
- } else if (n == t->root && n->n_vals == 1) {
- // Root has two children, both minimal, delete it
- assert(i == 0 || i == 1);
- const uint16_t counts[2] = {zix_btree_child(n, 0)->n_vals,
- zix_btree_child(n, 1)->n_vals};
-
- n = zix_btree_merge(t, n, 0);
- if (ti) {
- ti->stack[ti->level].node = n;
- ti->stack[ti->level].index = counts[i];
- }
- } else {
- // Both child's siblings are minimal, merge them
- if (i < n->n_vals) {
- n = zix_btree_merge(t, n, i);
- } else {
- n = zix_btree_merge(t, n, i - 1U);
- if (ti) {
- --ti->stack[ti->level].index;
- }
- }
- }
- } else {
- n = zix_btree_child(n, i);
- }
- }
- if (ti) {
- ++ti->level;
- }
- }
-
- assert(false); // Not reached
- return ZIX_STATUS_ERROR;
-}
-
-ZixStatus
-zix_btree_find(const ZixBTree* const t,
- const void* const e,
- ZixBTreeIter** const ti)
-{
- ZixBTreeNode* n = t->root;
- if (!(*ti = zix_btree_iter_new(t))) {
- return ZIX_STATUS_NO_MEM;
- }
-
- while (n) {
- bool equal = false;
- const unsigned i = zix_btree_node_find(t, n, e, &equal);
-
- zix_btree_iter_set_frame(*ti, n, i);
-
- if (equal) {
- return ZIX_STATUS_SUCCESS;
- }
-
- if (n->is_leaf) {
- break;
- }
-
- ++(*ti)->level;
- n = zix_btree_child(n, i);
- }
-
- zix_btree_iter_free(*ti);
- *ti = NULL;
- return ZIX_STATUS_NOT_FOUND;
-}
-
-ZixStatus
-zix_btree_lower_bound(const ZixBTree* const t,
- const void* const e,
- ZixBTreeIter** const ti)
-{
- if (!t) {
- *ti = NULL;
- return ZIX_STATUS_BAD_ARG;
- }
-
- if (!t->root) {
- *ti = NULL;
- return ZIX_STATUS_SUCCESS;
- }
-
- ZixBTreeNode* n = t->root;
- bool found = false;
- unsigned found_level = 0;
- if (!(*ti = zix_btree_iter_new(t))) {
- return ZIX_STATUS_NO_MEM;
- }
-
- while (n) {
- bool equal = false;
- const unsigned i = zix_btree_node_find(t, n, e, &equal);
-
- zix_btree_iter_set_frame(*ti, n, i);
-
- if (equal) {
- found_level = (*ti)->level;
- found = true;
- }
-
- if (n->is_leaf) {
- break;
- }
-
- ++(*ti)->level;
- n = zix_btree_child(n, i);
- assert(n);
- }
-
- const ZixBTreeIterFrame* const frame = &(*ti)->stack[(*ti)->level];
- assert(frame->node);
- if (frame->index == frame->node->n_vals) {
- if (found) {
- // Found on a previous level but went too far
- (*ti)->level = found_level;
- } else {
- // Reached end (key is greater than everything in tree)
- (*ti)->level = 0;
- (*ti)->stack[0].node = NULL;
- }
- }
-
- return ZIX_STATUS_SUCCESS;
-}
-
-void*
-zix_btree_get(const ZixBTreeIter* const ti)
-{
- const ZixBTreeIterFrame* const frame = &ti->stack[ti->level];
- assert(frame->node);
- assert(frame->index < frame->node->n_vals);
- return zix_btree_value(frame->node, frame->index);
-}
-
-ZixBTreeIter*
-zix_btree_begin(const ZixBTree* const t)
-{
- ZixBTreeIter* const i = zix_btree_iter_new(t);
- if (!i) {
- return NULL;
- }
-
- if (t->size == 0) {
- i->level = 0;
- i->stack[0].node = NULL;
- } else {
- ZixBTreeNode* n = t->root;
- i->stack[0].node = n;
- i->stack[0].index = 0;
- while (!n->is_leaf) {
- n = zix_btree_child(n, 0);
- ++i->level;
- i->stack[i->level].node = n;
- i->stack[i->level].index = 0;
- }
- }
-
- return i;
-}
-
-ZixBTreeIter*
-zix_btree_end(const ZixBTree* const t)
-{
- return zix_btree_iter_new(t);
-}
-
-ZixBTreeIter*
-zix_btree_iter_copy(const ZixBTreeIter* const i)
-{
- if (!i) {
- return NULL;
- }
-
- const size_t s = i->n_levels * sizeof(ZixBTreeIterFrame);
- ZixBTreeIter* j = (ZixBTreeIter*)calloc(1, sizeof(ZixBTreeIter) + s);
- if (j) {
- memcpy(j, i, sizeof(ZixBTreeIter) + s);
- }
-
- return j;
-}
-
-bool
-zix_btree_iter_is_end(const ZixBTreeIter* const i)
-{
- return !i || i->stack[0].node == NULL;
-}
-
-bool
-zix_btree_iter_equals(const ZixBTreeIter* const lhs,
- const ZixBTreeIter* const rhs)
-{
- if (zix_btree_iter_is_end(lhs) && zix_btree_iter_is_end(rhs)) {
- return true;
- }
-
- if (zix_btree_iter_is_end(lhs) || zix_btree_iter_is_end(rhs) ||
- lhs->level != rhs->level) {
- return false;
- }
-
- return !memcmp(lhs,
- rhs,
- sizeof(ZixBTreeIter) +
- (lhs->level + 1) * sizeof(ZixBTreeIterFrame));
-}
-
-void
-zix_btree_iter_increment(ZixBTreeIter* const i)
-{
- ZixBTreeIterFrame* f = &i->stack[i->level];
- if (f->node->is_leaf) {
- // Leaf, move right
- assert(f->index < f->node->n_vals);
- if (++f->index == f->node->n_vals) {
- // Reached end of leaf, move up
- f = &i->stack[i->level];
- while (i->level > 0 && f->index == f->node->n_vals) {
- f = &i->stack[--i->level];
- assert(f->index <= f->node->n_vals);
- }
-
- if (f->index == f->node->n_vals) {
- // Reached end of tree
- assert(i->level == 0);
- f->node = NULL;
- f->index = 0;
- }
- }
- } else {
- // Internal node, move down to next child
- assert(f->index < f->node->n_vals);
- ZixBTreeNode* child = zix_btree_child(f->node, ++f->index);
-
- f = &i->stack[++i->level];
- f->node = child;
- f->index = 0;
-
- // Move down and left until we hit a leaf
- while (!f->node->is_leaf) {
- child = zix_btree_child(f->node, 0);
- f = &i->stack[++i->level];
- f->node = child;
- f->index = 0;
- }
- }
-}
-
-void
-zix_btree_iter_free(ZixBTreeIter* const i)
-{
- free(i);
-}
diff --git a/zix/btree.h b/zix/btree.h
deleted file mode 100644
index dde659f..0000000
--- a/zix/btree.h
+++ /dev/null
@@ -1,187 +0,0 @@
-/*
- Copyright 2011-2016 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_BTREE_H
-#define ZIX_BTREE_H
-
-#include "zix/common.h"
-
-#include <stdbool.h>
-#include <stddef.h>
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-/**
- @addtogroup zix
- @{
- @name BTree
- @{
-*/
-
-/**
- A B-Tree.
-*/
-typedef struct ZixBTreeImpl ZixBTree;
-
-/**
- A B-Tree node (opaque).
-*/
-typedef struct ZixBTreeNodeImpl ZixBTreeNode;
-
-/**
- An iterator over a B-Tree.
-
- Note that modifying the trees invalidates all iterators, so all iterators
- are const iterators.
-*/
-typedef struct ZixBTreeIterImpl ZixBTreeIter;
-
-/**
- Create a new (empty) B-Tree.
-*/
-ZIX_API
-ZixBTree*
-zix_btree_new(ZixComparator cmp, const void* cmp_data, ZixDestroyFunc destroy);
-
-/**
- Free `t`.
-*/
-ZIX_API
-void
-zix_btree_free(ZixBTree* t);
-
-/**
- Return the number of elements in `t`.
-*/
-ZIX_PURE_API
-size_t
-zix_btree_size(const ZixBTree* t);
-
-/**
- Insert the element `e` into `t`.
-*/
-ZIX_API
-ZixStatus
-zix_btree_insert(ZixBTree* t, void* e);
-
-/**
- Remove the value `e` from `t`.
-
- @param t Tree to remove from.
-
- @param e Value to remove.
-
- @param out Set to point to the removed pointer (which may not equal `e`).
-
- @param next If non-NULL, pointed to the value following `e`. If *next is
- also non-NULL, the iterator is reused, otherwise a new one is allocated. To
- reuse an iterator, no items may have been added since its creation.
-*/
-ZIX_API
-ZixStatus
-zix_btree_remove(ZixBTree* t, const void* e, void** out, ZixBTreeIter** next);
-
-/**
- Set `ti` to an element equal to `e` in `t`.
- If no such item exists, `ti` is set to NULL.
-*/
-ZIX_API
-ZixStatus
-zix_btree_find(const ZixBTree* t, const void* e, ZixBTreeIter** ti);
-
-/**
- Set `ti` to the smallest element in `t` that is not less than `e`.
-
- Wildcards are supported, so if the search key `e` compares equal to many
- values in the tree, `ti` will be set to the least such element. The search
- key `e` is always passed as the second argument to the comparator.
-*/
-ZIX_API
-ZixStatus
-zix_btree_lower_bound(const ZixBTree* t, const void* e, ZixBTreeIter** ti);
-
-/**
- Return the data associated with the given tree item.
-*/
-ZIX_PURE_API
-void*
-zix_btree_get(const ZixBTreeIter* ti);
-
-/**
- Return an iterator to the first (smallest) element in `t`.
-
- The returned iterator must be freed with zix_btree_iter_free().
-*/
-ZIX_PURE_API
-ZixBTreeIter*
-zix_btree_begin(const ZixBTree* t);
-
-/**
- Return an iterator to the end of `t` (one past the last element).
-
- The returned iterator must be freed with zix_btree_iter_free().
-*/
-ZIX_API
-ZixBTreeIter*
-zix_btree_end(const ZixBTree* t);
-
-/**
- Return a new copy of `i`.
-*/
-ZIX_API
-ZixBTreeIter*
-zix_btree_iter_copy(const ZixBTreeIter* i);
-
-/**
- Return true iff `lhs` is equal to `rhs`.
-*/
-ZIX_PURE_API
-bool
-zix_btree_iter_equals(const ZixBTreeIter* lhs, const ZixBTreeIter* rhs);
-
-/**
- Return true iff `i` is an iterator to the end of its tree.
-*/
-ZIX_PURE_API
-bool
-zix_btree_iter_is_end(const ZixBTreeIter* i);
-
-/**
- Increment `i` to point to the next element in the tree.
-*/
-ZIX_API
-void
-zix_btree_iter_increment(ZixBTreeIter* i);
-
-/**
- Free `i`.
-*/
-ZIX_API
-void
-zix_btree_iter_free(ZixBTreeIter* i);
-
-/**
- @}
- @}
-*/
-
-#ifdef __cplusplus
-} /* extern "C" */
-#endif
-
-#endif /* ZIX_BTREE_H */
diff --git a/zix/chunk.c b/zix/chunk.c
deleted file mode 100644
index bf80f88..0000000
--- a/zix/chunk.c
+++ /dev/null
@@ -1,33 +0,0 @@
-/*
- 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/chunk.h"
-
-#include "zix/digest.h"
-
-#include <string.h>
-
-uint32_t
-zix_chunk_hash(const ZixChunk* const chunk)
-{
- return zix_digest_add(zix_digest_start(), chunk->buf, chunk->len);
-}
-
-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
deleted file mode 100644
index 3646718..0000000
--- a/zix/chunk.h
+++ /dev/null
@@ -1,50 +0,0 @@
-/*
- 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 "zix/common.h"
-
-#include <stdbool.h>
-#include <stddef.h>
-#include <stdint.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_PURE_API
-uint32_t
-zix_chunk_hash(const ZixChunk* chunk);
-
-ZIX_PURE_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
deleted file mode 100644
index 865d232..0000000
--- a/zix/common.h
+++ /dev/null
@@ -1,150 +0,0 @@
-/*
- Copyright 2016 David Robillard <http://drobilla.net>
-
- Permission to use, copy, modify, and/or distribute this software for any
- purpose with or without fee is hereby granted, provided that the above
- copyright notice and this permission notice appear in all copies.
-
- THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
- WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
- MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
- ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
- WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
- ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
- OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
-*/
-
-#ifndef ZIX_COMMON_H
-#define ZIX_COMMON_H
-
-#include <stdbool.h>
-
-/**
- @addtogroup zix
- @{
-*/
-
-/** @cond */
-#ifdef ZIX_SHARED
-# ifdef _WIN32
-# define ZIX_LIB_IMPORT __declspec(dllimport)
-# define ZIX_LIB_EXPORT __declspec(dllexport)
-# else
-# define ZIX_LIB_IMPORT __attribute__((visibility("default")))
-# define ZIX_LIB_EXPORT __attribute__((visibility("default")))
-# endif
-# ifdef ZIX_INTERNAL
-# define ZIX_API ZIX_LIB_EXPORT
-# else
-# define ZIX_API ZIX_LIB_IMPORT
-# endif
-# 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
-
-#ifdef __GNUC__
-# define ZIX_PURE_FUNC __attribute__((pure))
-# define ZIX_CONST_FUNC __attribute__((const))
-# define ZIX_MALLOC_FUNC __attribute__((malloc))
-#else
-# define ZIX_PURE_FUNC
-# define ZIX_CONST_FUNC
-# define ZIX_MALLOC_FUNC
-#endif
-
-#define ZIX_PURE_API \
- ZIX_API \
- ZIX_PURE_FUNC
-
-#define ZIX_CONST_API \
- ZIX_API \
- ZIX_CONST_FUNC
-
-#define ZIX_MALLOC_API \
- ZIX_API \
- ZIX_MALLOC_FUNC
-
-/** @endcond */
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-#ifdef __GNUC__
-# define ZIX_LOG_FUNC(fmt, arg1) __attribute__((format(printf, fmt, arg1)))
-#else
-# define ZIX_LOG_FUNC(fmt, arg1)
-#endif
-
-// Unused parameter macro to suppresses warnings and make it impossible to use
-#if defined(__cplusplus)
-# define ZIX_UNUSED(name)
-#elif defined(__GNUC__)
-# define ZIX_UNUSED(name) name##_unused __attribute__((__unused__))
-#else
-# define ZIX_UNUSED(name) name
-#endif
-
-typedef enum {
- ZIX_STATUS_SUCCESS,
- ZIX_STATUS_ERROR,
- ZIX_STATUS_NO_MEM,
- ZIX_STATUS_NOT_FOUND,
- ZIX_STATUS_EXISTS,
- ZIX_STATUS_BAD_ARG,
- ZIX_STATUS_BAD_PERMS
-} ZixStatus;
-
-static inline const char*
-zix_strerror(const ZixStatus status)
-{
- switch (status) {
- case ZIX_STATUS_SUCCESS:
- return "Success";
- case ZIX_STATUS_ERROR:
- return "Unknown error";
- case ZIX_STATUS_NO_MEM:
- return "Out of memory";
- case ZIX_STATUS_NOT_FOUND:
- return "Not found";
- case ZIX_STATUS_EXISTS:
- return "Exists";
- case ZIX_STATUS_BAD_ARG:
- return "Bad argument";
- case ZIX_STATUS_BAD_PERMS:
- return "Bad permissions";
- }
- return "Unknown error";
-}
-
-/**
- Function for comparing two elements.
-*/
-typedef int (*ZixComparator)(const void* a,
- const void* b,
- const void* user_data);
-
-/**
- Function for testing equality of two elements.
-*/
-typedef bool (*ZixEqualFunc)(const void* a, const void* b);
-
-/**
- Function to destroy an element.
-*/
-typedef void (*ZixDestroyFunc)(void* ptr);
-
-/**
- @}
-*/
-
-#ifdef __cplusplus
-} /* extern "C" */
-#endif
-
-#endif /* ZIX_COMMON_H */
diff --git a/zix/digest.c b/zix/digest.c
deleted file mode 100644
index 941b05c..0000000
--- a/zix/digest.c
+++ /dev/null
@@ -1,141 +0,0 @@
-/*
- Copyright 2012-2020 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
-
-#include <assert.h>
-#include <stdint.h>
-
-#ifdef __SSE4_2__
-
-// SSE 4.2 CRC32
-
-uint32_t
-zix_digest_start(void)
-{
- return 1;
-}
-
-uint32_t
-zix_digest_add(uint32_t hash, const void* const buf, const size_t len)
-{
- const uint8_t* str = (const uint8_t*)buf;
-
-# ifdef __x86_64__
- for (size_t i = 0; i < (len / sizeof(uint64_t)); ++i) {
- hash = (uint32_t)_mm_crc32_u64(hash, *(const uint64_t*)str);
- str += sizeof(uint64_t);
- }
- if (len & sizeof(uint32_t)) {
- hash = _mm_crc32_u32(hash, *(const uint32_t*)str);
- str += sizeof(uint32_t);
- }
-# else
- for (size_t i = 0; i < (len / sizeof(uint32_t)); ++i) {
- hash = _mm_crc32_u32(hash, *(const uint32_t*)str);
- str += sizeof(uint32_t);
- }
-# endif
- if (len & sizeof(uint16_t)) {
- hash = _mm_crc32_u16(hash, *(const uint16_t*)str);
- str += sizeof(uint16_t);
- }
- if (len & sizeof(uint8_t)) {
- hash = _mm_crc32_u8(hash, *(const uint8_t*)str);
- }
-
- return hash;
-}
-
-uint32_t
-zix_digest_add_64(uint32_t hash, const void* const buf, const size_t len)
-{
- assert((uintptr_t)buf % sizeof(uint64_t) == 0);
- assert(len % sizeof(uint64_t) == 0);
-
-# ifdef __x86_64__
- const uint64_t* ptr = (const uint64_t*)buf;
-
- for (size_t i = 0; i < (len / sizeof(uint64_t)); ++i) {
- hash = (uint32_t)_mm_crc32_u64(hash, *ptr);
- ++ptr;
- }
-
- return hash;
-# else
- const uint32_t* ptr = (const uint32_t*)buf;
-
- for (size_t i = 0; i < (len / sizeof(uint32_t)); ++i) {
- hash = _mm_crc32_u32(hash, *ptr);
- ++ptr;
- }
-
- return hash;
-# endif
-}
-
-uint32_t
-zix_digest_add_ptr(const uint32_t hash, const void* const ptr)
-{
-# ifdef __x86_64__
- return (uint32_t)_mm_crc32_u64(hash, (uintptr_t)ptr);
-# else
- return _mm_crc32_u32(hash, (uintptr_t)ptr);
-# endif
-}
-
-#else
-
-// Classic DJB hash
-
-uint32_t
-zix_digest_start(void)
-{
- return 5381;
-}
-
-uint32_t
-zix_digest_add(uint32_t hash, const void* const buf, const size_t len)
-{
- const uint8_t* str = (const uint8_t*)buf;
-
- for (size_t i = 0; i < len; ++i) {
- hash = (hash << 5u) + hash + str[i];
- }
-
- return hash;
-}
-
-uint32_t
-zix_digest_add_64(uint32_t hash, const void* const buf, const size_t len)
-{
- assert((uintptr_t)buf % sizeof(uint64_t) == 0);
- assert(len % sizeof(uint64_t) == 0);
-
- return zix_digest_add(hash, buf, len);
-}
-
-uint32_t
-zix_digest_add_ptr(const uint32_t hash, const void* const ptr)
-{
- return zix_digest_add(hash, &ptr, sizeof(ptr));
-}
-
-#endif
diff --git a/zix/digest.h b/zix/digest.h
deleted file mode 100644
index 7d44c3d..0000000
--- a/zix/digest.h
+++ /dev/null
@@ -1,67 +0,0 @@
-/*
- Copyright 2012-2020 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 "zix/common.h"
-
-#include <stddef.h>
-#include <stdint.h>
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-/**
- Return an initial empty digest value.
-*/
-ZIX_CONST_API
-uint32_t
-zix_digest_start(void);
-
-/**
- Update `hash` to include `buf`, a buffer of `len` bytes.
-
- This can be used for any size or alignment.
-*/
-ZIX_PURE_API
-uint32_t
-zix_digest_add(uint32_t hash, const void* buf, size_t len);
-
-/**
- Update `hash` to include `buf`, a 64-bit aligned buffer of `len` bytes.
-
- Both `buf` and `len` must be evenly divisible by 8 (64 bits).
-*/
-ZIX_PURE_API
-uint32_t
-zix_digest_add_64(uint32_t hash, const void* buf, size_t len);
-
-/**
- Update `hash` to include `ptr`.
-
- This hashes the value of the pointer itself, and does not dereference `ptr`.
-*/
-ZIX_CONST_API
-uint32_t
-zix_digest_add_ptr(uint32_t hash, const void* ptr);
-
-#ifdef __cplusplus
-} /* extern "C" */
-#endif
-
-#endif /* ZIX_DIGEST_H */
diff --git a/zix/hash.c b/zix/hash.c
deleted file mode 100644
index 34464d4..0000000
--- a/zix/hash.c
+++ /dev/null
@@ -1,230 +0,0 @@
-/*
- Copyright 2011-2018 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/hash.h"
-
-#include <assert.h>
-#include <stdlib.h>
-#include <string.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 void*
-zix_hash_value(ZixHashEntry* entry)
-{
- return entry + 1;
-}
-
-ZixHash*
-zix_hash_new(ZixHashFunc hash_func, ZixEqualFunc equal_func, size_t value_size)
-{
- ZixHash* hash = (ZixHash*)malloc(sizeof(ZixHash));
- if (hash) {
- hash->hash_func = hash_func;
- hash->equal_func = equal_func;
- hash->n_buckets = &sizes[0];
- hash->value_size = value_size;
- hash->count = 0;
- if (!(hash->buckets =
- (ZixHashEntry**)calloc(*hash->n_buckets, sizeof(ZixHashEntry*)))) {
- free(hash);
- return NULL;
- }
- }
- return hash;
-}
-
-void
-zix_hash_free(ZixHash* hash)
-{
- if (!hash) {
- return;
- }
-
- 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);
-}
-
-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;
-}
-
-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;
-}
-
-ZixStatus
-zix_hash_insert(ZixHash* hash, const void* value, 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;
-}
-
-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;
-}
-
-void
-zix_hash_foreach(ZixHash* hash, ZixHashVisitFunc f, void* user_data)
-{
- for (unsigned b = 0; b < *hash->n_buckets; ++b) {
- ZixHashEntry* bucket = hash->buckets[b];
- for (ZixHashEntry* e = bucket; e; e = e->next) {
- f(zix_hash_value(e), user_data);
- }
- }
-}
diff --git a/zix/hash.h b/zix/hash.h
deleted file mode 100644
index bef1568..0000000
--- a/zix/hash.h
+++ /dev/null
@@ -1,138 +0,0 @@
-/*
- Copyright 2011-2015 David Robillard <http://drobilla.net>
-
- Permission to use, copy, modify, and/or distribute this software for any
- purpose with or without fee is hereby granted, provided that the above
- copyright notice and this permission notice appear in all copies.
-
- THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
- WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
- MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
- ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
- WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
- ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
- OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
-*/
-
-#ifndef ZIX_HASH_H
-#define ZIX_HASH_H
-
-#include "zix/common.h"
-
-#include <stddef.h>
-#include <stdint.h>
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-/**
- @addtogroup zix
- @{
- @name Hash
- @{
-*/
-
-typedef struct ZixHashImpl ZixHash;
-
-/**
- Function for computing the hash of an element.
-*/
-typedef uint32_t (*ZixHashFunc)(const void* value);
-
-/**
- Function to visit a hash element.
-*/
-typedef void (*ZixHashVisitFunc)(void* value, void* user_data);
-
-/**
- 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 equal_func, size_t value_size);
-
-/**
- Free `hash`.
-*/
-ZIX_API
-void
-zix_hash_free(ZixHash* hash);
-
-/**
- Return the number of elements in `hash`.
-*/
-ZIX_PURE_API
-size_t
-zix_hash_size(const ZixHash* hash);
-
-/**
- Insert an item into `hash`.
-
- If no matching value is found, ZIX_STATUS_SUCCESS will be returned, and @p
- inserted will be pointed to the copy of `value` made in the new hash node.
-
- If a matching value already exists, ZIX_STATUS_EXISTS will be returned, and
- `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 `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, void** inserted);
-
-/**
- Remove an item from `hash`.
-
- @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);
-
-/**
- Search for an item in `hash`.
-
- @param hash The hash table.
- @param value The value to search for.
-*/
-ZIX_API
-void*
-zix_hash_find(const ZixHash* hash, const void* value);
-
-/**
- Call `f` on each value in `hash`.
-
- @param hash The hash table.
- @param f The function to call on each value.
- @param user_data The user_data parameter passed to `f`.
-*/
-ZIX_API
-void
-zix_hash_foreach(ZixHash* hash, ZixHashVisitFunc f, void* user_data);
-
-/**
- @}
- @}
-*/
-
-#ifdef __cplusplus
-} /* extern "C" */
-#endif
-
-#endif /* ZIX_HASH_H */
diff --git a/zix/ring.c b/zix/ring.c
deleted file mode 100644
index 0607a18..0000000
--- a/zix/ring.c
+++ /dev/null
@@ -1,222 +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 "zix/ring.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(_MSC_VER)
-# include <windows.h>
-# define ZIX_READ_BARRIER() MemoryBarrier()
-# define ZIX_WRITE_BARRIER() MemoryBarrier()
-#elif defined(__GNUC__)
-# define ZIX_READ_BARRIER() __atomic_thread_fence(__ATOMIC_ACQUIRE)
-# define ZIX_WRITE_BARRIER() __atomic_thread_fence(__ATOMIC_RELEASE)
-#else
-# pragma message("warning: No memory barriers, possible SMP bugs")
-# define ZIX_READ_BARRIER()
-# define ZIX_WRITE_BARRIER()
-#endif
-
-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 >> 1u;
- size |= size >> 2u;
- size |= size >> 4u;
- size |= size >> 8u;
- size |= size >> 16u;
- 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;
- }
-
- 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;
- }
-
- if (r < w) {
- return ((r - w + ring->size) & ring->size_mask) - 1;
- }
-
- 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)
-{
- return peek_internal(ring, ring->read_head, ring->write_head, 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;
- }
-
- 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/ring.h b/zix/ring.h
deleted file mode 100644
index a64d227..0000000
--- a/zix/ring.h
+++ /dev/null
@@ -1,141 +0,0 @@
-/*
- Copyright 2011-2014 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_RING_H
-#define ZIX_RING_H
-
-#include "zix/common.h"
-
-#include <stdint.h>
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-/**
- @addtogroup zix
- @{
- @name Ring
- @{
-*/
-
-/**
- A lock-free ring buffer.
-
- Thread-safe with a single reader and single writer, and realtime safe
- on both ends.
-*/
-typedef struct ZixRingImpl ZixRing;
-
-/**
- Create a new ring.
- @param size Size in bytes (note this may be rounded up).
-
- At most `size` - 1 bytes may be stored in the ring at once.
-*/
-ZIX_MALLOC_API
-ZixRing*
-zix_ring_new(uint32_t size);
-
-/**
- Destroy a ring.
-*/
-ZIX_API
-void
-zix_ring_free(ZixRing* ring);
-
-/**
- Lock the ring data into physical memory.
-
- This function is NOT thread safe or real-time safe, but it should be called
- after zix_ring_new() to lock all ring memory to avoid page faults while
- using the ring (i.e. this function MUST be called first in order for the
- ring to be truly real-time safe).
-
-*/
-ZIX_API
-void
-zix_ring_mlock(ZixRing* ring);
-
-/**
- Reset (empty) a ring.
-
- This function is NOT thread-safe, it may only be called when there are no
- readers or writers.
-*/
-ZIX_API
-void
-zix_ring_reset(ZixRing* ring);
-
-/**
- Return the number of bytes of space available for reading.
-*/
-ZIX_CONST_API
-uint32_t
-zix_ring_read_space(const ZixRing* ring);
-
-/**
- Return the number of bytes of space available for writing.
-*/
-ZIX_CONST_API
-uint32_t
-zix_ring_write_space(const ZixRing* ring);
-
-/**
- Return the capacity (i.e. total write space when empty).
-*/
-ZIX_CONST_API
-uint32_t
-zix_ring_capacity(const ZixRing* ring);
-
-/**
- Read from the ring without advancing the read head.
-*/
-ZIX_API
-uint32_t
-zix_ring_peek(ZixRing* ring, void* dst, uint32_t size);
-
-/**
- Read from the ring and advance the read head.
-*/
-ZIX_API
-uint32_t
-zix_ring_read(ZixRing* ring, void* dst, uint32_t size);
-
-/**
- Skip data in the ring (advance read head without reading).
-*/
-ZIX_API
-uint32_t
-zix_ring_skip(ZixRing* ring, uint32_t size);
-
-/**
- Write data to the ring.
-*/
-ZIX_API
-uint32_t
-zix_ring_write(ZixRing* ring, const void* src, uint32_t size);
-
-/**
- @}
- @}
-*/
-
-#ifdef __cplusplus
-} /* extern "C" */
-#endif
-
-#endif /* ZIX_RING_H */
diff --git a/zix/sem.h b/zix/sem.h
deleted file mode 100644
index ae59f10..0000000
--- a/zix/sem.h
+++ /dev/null
@@ -1,242 +0,0 @@
-/*
- Copyright 2012-2014 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_SEM_H
-#define ZIX_SEM_H
-
-#include "zix/common.h"
-
-#ifdef __APPLE__
-# include <mach/mach.h>
-#elif defined(_WIN32)
-# include <limits.h>
-# include <windows.h>
-#else
-# include <errno.h>
-# include <semaphore.h>
-#endif
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-#include <stdbool.h>
-
-/**
- @addtogroup zix
- @{
- @name Semaphore
- @{
-*/
-
-struct ZixSemImpl;
-
-/**
- A counting semaphore.
-
- This is an integer that is always positive, and has two main operations:
- increment (post) and decrement (wait). If a decrement can not be performed
- (i.e. the value is 0) the caller will be blocked until another thread posts
- and the operation can succeed.
-
- Semaphores can be created with any starting value, but typically this will
- be 0 so the semaphore can be used as a simple signal where each post
- corresponds to one wait.
-
- Semaphores are very efficient (much moreso than a mutex/cond pair). In
- particular, at least on Linux, post is async-signal-safe, which means it
- does not block and will not be interrupted. If you need to signal from
- a realtime thread, this is the most appropriate primitive to use.
-*/
-typedef struct ZixSemImpl ZixSem;
-
-/**
- Create and initialize `sem` to `initial`.
-*/
-static inline ZixStatus
-zix_sem_init(ZixSem* sem, unsigned initial);
-
-/**
- Destroy `sem`.
-*/
-static inline void
-zix_sem_destroy(ZixSem* sem);
-
-/**
- Increment (and signal any waiters).
- Realtime safe.
-*/
-static inline void
-zix_sem_post(ZixSem* sem);
-
-/**
- Wait until count is > 0, then decrement.
- Obviously not realtime safe.
-*/
-static inline ZixStatus
-zix_sem_wait(ZixSem* sem);
-
-/**
- Non-blocking version of wait().
-
- @return true if decrement was successful (lock was acquired).
-*/
-static inline bool
-zix_sem_try_wait(ZixSem* sem);
-
-/**
- @cond
-*/
-
-#ifdef __APPLE__
-
-struct ZixSemImpl {
- semaphore_t sem;
-};
-
-static inline ZixStatus
-zix_sem_init(ZixSem* sem, unsigned val)
-{
- return semaphore_create(mach_task_self(), &sem->sem, SYNC_POLICY_FIFO, val)
- ? ZIX_STATUS_ERROR
- : ZIX_STATUS_SUCCESS;
-}
-
-static inline void
-zix_sem_destroy(ZixSem* sem)
-{
- semaphore_destroy(mach_task_self(), sem->sem);
-}
-
-static inline void
-zix_sem_post(ZixSem* sem)
-{
- semaphore_signal(sem->sem);
-}
-
-static inline ZixStatus
-zix_sem_wait(ZixSem* sem)
-{
- if (semaphore_wait(sem->sem) != KERN_SUCCESS) {
- return ZIX_STATUS_ERROR;
- }
- return ZIX_STATUS_SUCCESS;
-}
-
-static inline bool
-zix_sem_try_wait(ZixSem* sem)
-{
- const mach_timespec_t zero = {0, 0};
- return semaphore_timedwait(sem->sem, zero) == KERN_SUCCESS;
-}
-
-#elif defined(_WIN32)
-
-struct ZixSemImpl {
- HANDLE sem;
-};
-
-static inline ZixStatus
-zix_sem_init(ZixSem* sem, unsigned initial)
-{
- sem->sem = CreateSemaphore(NULL, initial, LONG_MAX, NULL);
- return (sem->sem) ? ZIX_STATUS_SUCCESS : ZIX_STATUS_ERROR;
-}
-
-static inline void
-zix_sem_destroy(ZixSem* sem)
-{
- CloseHandle(sem->sem);
-}
-
-static inline void
-zix_sem_post(ZixSem* sem)
-{
- ReleaseSemaphore(sem->sem, 1, NULL);
-}
-
-static inline ZixStatus
-zix_sem_wait(ZixSem* sem)
-{
- if (WaitForSingleObject(sem->sem, INFINITE) != WAIT_OBJECT_0) {
- return ZIX_STATUS_ERROR;
- }
- return ZIX_STATUS_SUCCESS;
-}
-
-static inline bool
-zix_sem_try_wait(ZixSem* sem)
-{
- return WaitForSingleObject(sem->sem, 0) == WAIT_OBJECT_0;
-}
-
-#else /* !defined(__APPLE__) && !defined(_WIN32) */
-
-struct ZixSemImpl {
- sem_t sem;
-};
-
-static inline ZixStatus
-zix_sem_init(ZixSem* sem, unsigned initial)
-{
- return sem_init(&sem->sem, 0, initial) ? ZIX_STATUS_ERROR
- : ZIX_STATUS_SUCCESS;
-}
-
-static inline void
-zix_sem_destroy(ZixSem* sem)
-{
- sem_destroy(&sem->sem);
-}
-
-static inline void
-zix_sem_post(ZixSem* sem)
-{
- sem_post(&sem->sem);
-}
-
-static inline ZixStatus
-zix_sem_wait(ZixSem* sem)
-{
- while (sem_wait(&sem->sem)) {
- if (errno != EINTR) {
- return ZIX_STATUS_ERROR;
- }
- /* Otherwise, interrupted, so try again. */
- }
-
- return ZIX_STATUS_SUCCESS;
-}
-
-static inline bool
-zix_sem_try_wait(ZixSem* sem)
-{
- return (sem_trywait(&sem->sem) == 0);
-}
-
-#endif
-
-/**
- @endcond
- @}
- @}
-*/
-
-#ifdef __cplusplus
-} /* extern "C" */
-#endif
-
-#endif /* ZIX_SEM_H */
diff --git a/zix/sorted_array.c b/zix/sorted_array.c
deleted file mode 100644
index 0f84227..0000000
--- a/zix/sorted_array.c
+++ /dev/null
@@ -1,193 +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 "zix/sorted_array.h"
-
-#include "zix/common.h"
-
-#include <assert.h>
-#include <stdint.h>
-#include <stdlib.h>
-#include <string.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
-
-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;
-}
-
-void
-zix_sorted_array_free(ZixSortedArray* a)
-{
- free(a->array);
- free(a);
-}
-
-size_t
-zix_sorted_array_size(const ZixSortedArray* a)
-{
- return a->num_elems;
-}
-
-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 = (size_t)((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;
-}
-
-ZixStatus
-zix_sorted_array_remove(ZixSortedArray* a, ZixSortedArrayIter ai)
-{
- const size_t i = (size_t)((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);
-}
-
-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);
-}
-
-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;
- }
-
- if (cmp > 0) {
- upper = i - 1;
- } else {
- lower = i + 1;
- }
- }
-
- *ai = zix_sorted_array_index_unchecked(a, lower);
- return ZIX_STATUS_NOT_FOUND;
-}
-
-void*
-zix_sorted_array_get_data(ZixSortedArrayIter ai)
-{
- return ai;
-}
-
-ZixSortedArrayIter
-zix_sorted_array_begin(ZixSortedArray* a)
-{
- return a->array;
-}
-
-ZixSortedArrayIter
-zix_sorted_array_end(ZixSortedArray* a)
-{
- return (char*)a->array + (a->elem_size * a->num_elems);
-}
-
-bool
-zix_sorted_array_iter_is_end(ZixSortedArray* a, ZixSortedArrayIter i)
-{
- return i != zix_sorted_array_end(a);
-}
-
-ZixSortedArrayIter
-zix_sorted_array_iter_next(ZixSortedArray* a, ZixSortedArrayIter i)
-{
- return (char*)i + a->elem_size;
-}
diff --git a/zix/sorted_array.h b/zix/sorted_array.h
deleted file mode 100644
index 92f13e6..0000000
--- a/zix/sorted_array.h
+++ /dev/null
@@ -1,147 +0,0 @@
-/*
- Copyright 2011-2014 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_SORTED_ARRAY_H
-#define ZIX_SORTED_ARRAY_H
-
-#include "zix/common.h"
-
-#include <stdbool.h>
-#include <stddef.h>
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-/**
- @addtogroup zix
- @{
- @name SortedArray
- @{
-*/
-
-/**
- A sorted array.
-*/
-typedef struct ZixSortedArrayImpl ZixSortedArray;
-
-/**
- An iterator over a ZixSortedArray.
-*/
-typedef void* ZixSortedArrayIter;
-
-/**
- Create a new (empty) sorted array.
-*/
-ZIX_API
-ZixSortedArray*
-zix_sorted_array_new(bool allow_duplicates,
- ZixComparator cmp,
- void* cmp_data,
- size_t elem_size);
-
-/**
- Free `a`.
-*/
-ZIX_API
-void
-zix_sorted_array_free(ZixSortedArray* a);
-
-/**
- Return the number of elements in `a`.
-*/
-ZIX_PURE_API
-size_t
-zix_sorted_array_size(const ZixSortedArray* a);
-
-/**
- Insert the element `e` into `a` and point `ai` at the new element.
-*/
-ZIX_API
-ZixStatus
-zix_sorted_array_insert(ZixSortedArray* a,
- const void* e,
- ZixSortedArrayIter* ai);
-
-/**
- Remove the item pointed at by `ai` from `a`.
-*/
-ZIX_API
-ZixStatus
-zix_sorted_array_remove(ZixSortedArray* a, ZixSortedArrayIter ai);
-
-/**
- Set `ai` to be the largest element <= `e` in `a`.
- If no such item exists, `ai` is set to NULL.
-*/
-ZIX_API
-ZixStatus
-zix_sorted_array_find(const ZixSortedArray* a,
- const void* e,
- ZixSortedArrayIter* ai);
-
-/**
- Return the element at index `index`.
-*/
-ZIX_PURE_API
-void*
-zix_sorted_array_index(const ZixSortedArray* a, size_t index);
-
-/**
- Return the data associated with the given array item.
-*/
-ZIX_CONST_API
-void*
-zix_sorted_array_get_data(ZixSortedArrayIter ai);
-
-/**
- Return an iterator to the first (smallest) element in `a`.
-*/
-ZIX_PURE_API
-ZixSortedArrayIter
-zix_sorted_array_begin(ZixSortedArray* a);
-
-/**
- Return an iterator the the element one past the last element in `a`.
-*/
-ZIX_PURE_API
-ZixSortedArrayIter
-zix_sorted_array_end(ZixSortedArray* a);
-
-/**
- Return true iff `a` is an iterator to the end of its tree.
-*/
-ZIX_PURE_API
-bool
-zix_sorted_array_iter_is_end(ZixSortedArray* a, ZixSortedArrayIter i);
-
-/**
- Return an iterator that points to the element one past `a`.
-*/
-ZIX_PURE_API
-ZixSortedArrayIter
-zix_sorted_array_iter_next(ZixSortedArray* a, ZixSortedArrayIter i);
-
-/**
- @}
- @}
-*/
-
-#ifdef __cplusplus
-} /* extern "C" */
-#endif
-
-#endif /* ZIX_SORTED_ARRAY_H */
diff --git a/zix/strindex.c b/zix/strindex.c
deleted file mode 100644
index 8cb05c9..0000000
--- a/zix/strindex.c
+++ /dev/null
@@ -1,261 +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 "zix/strindex.h"
-
-#include "zix/common.h"
-
-#include <assert.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.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);
-
-ZixStrindex*
-zix_strindex_new(const char* s)
-{
- const size_t len = strlen(s);
-
- ZixStrindex* t = (ZixStrindex*)malloc(sizeof(ZixStrindex));
- memset(t, '\0', sizeof(struct _ZixStrindex));
-
- t->s = (char*)calloc(1, len + 1);
- memcpy(t->s, s, len);
-
- t->root = (ZixStrindexNode*)malloc(sizeof(ZixStrindexNode));
- memset(t->root, '\0', sizeof(ZixStrindexNode));
- t->root->num_children = 0;
- t->root->first = 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);
- }
-}
-
-void
-zix_strindex_free(ZixStrindex* strindex)
-{
- zix_strindex_free_rec(strindex->root);
- free(strindex->s);
- free(strindex->root);
- free(strindex);
-}
-
-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;
-}
-
-ZixStatus
-zix_strindex_find(ZixStrindex* strindex, const char* const str, char** match)
-{
- const char* p = str;
-
-#ifndef NDEBUG
- const char* orig_p = p;
-#endif
-
- ZixStrindexNode* n = strindex->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;
- }
-
- if (strindex_is_leaf(n)) {
- /* Hit leaf early, no match */
- return ZIX_STATUS_NOT_FOUND;
- }
-
- /* Match at this node, continue search downwards (or match) */
- p += label_len;
- n = &n->children[child_i];
- if (label_len >= p_len) {
- assert(strstr(strindex->s, orig_p) != NULL);
- assert(strncmp(orig_p, *match, max_len));
- return ZIX_STATUS_SUCCESS;
- }
-
- } else {
- assert(strstr(strindex->s, orig_p) == NULL);
- return ZIX_STATUS_NOT_FOUND;
- }
- }
-
- return ZIX_STATUS_NOT_FOUND;
-}
diff --git a/zix/strindex.h b/zix/strindex.h
deleted file mode 100644
index beb4646..0000000
--- a/zix/strindex.h
+++ /dev/null
@@ -1,59 +0,0 @@
-/*
- Copyright 2011-2014 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_STRINDEX_H
-#define ZIX_STRINDEX_H
-
-#include "zix/common.h"
-
-/**
- @addtogroup zix
- @{
- @name Strindex
- @{
-*/
-
-typedef struct _ZixStrindex ZixStrindex;
-
-/**
- Construct a new strindex that contains all suffixes of the string `s`.
- A copy of `s` is taken and stored for the lifetime of the strindex.
-*/
-ZIX_API
-ZixStrindex*
-zix_strindex_new(const char* s);
-
-/**
- Destroy `t`.
-*/
-ZIX_API
-void
-zix_strindex_free(ZixStrindex* strindex);
-
-/**
- Check if the string in `strindex` contains the substring `str`.
- If such a substring is found, `match` is pointed at an occurrence of it.
-*/
-ZIX_API
-ZixStatus
-zix_strindex_find(ZixStrindex* strindex, const char* str, char** match);
-
-/**
- @}
- @}
-*/
-
-#endif /* ZIX_STRINDEX_H */
diff --git a/zix/thread.h b/zix/thread.h
deleted file mode 100644
index 8fa562d..0000000
--- a/zix/thread.h
+++ /dev/null
@@ -1,132 +0,0 @@
-/*
- Copyright 2012-2014 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_THREAD_H
-#define ZIX_THREAD_H
-
-#include "zix/common.h"
-
-#ifdef _WIN32
-# include <windows.h>
-#else
-# include <errno.h>
-# include <pthread.h>
-#endif
-
-#include <stddef.h>
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-/**
- @addtogroup zix
- @{
- @name Thread
- @{
-*/
-
-#ifdef _WIN32
-typedef HANDLE ZixThread;
-#else
-typedef pthread_t ZixThread;
-#endif
-
-/**
- Initialize `thread` to a new thread.
-
- The thread will immediately be launched, calling `function` with `arg`
- as the only parameter.
-*/
-static inline ZixStatus
-zix_thread_create(ZixThread* thread,
- size_t stack_size,
- void* (*function)(void*),
- void* arg);
-
-/**
- Join `thread` (block until `thread` exits).
-*/
-static inline ZixStatus
-zix_thread_join(ZixThread thread, void** retval);
-
-#ifdef _WIN32
-
-static inline ZixStatus
-zix_thread_create(ZixThread* thread,
- size_t stack_size,
- void* (*function)(void*),
- void* arg)
-{
- *thread = CreateThread(
- NULL, stack_size, (LPTHREAD_START_ROUTINE)function, arg, 0, NULL);
- return *thread ? ZIX_STATUS_SUCCESS : ZIX_STATUS_ERROR;
-}
-
-static inline ZixStatus
-zix_thread_join(ZixThread thread, void** retval)
-{
- (void)retval;
-
- return WaitForSingleObject(thread, INFINITE) ? ZIX_STATUS_SUCCESS
- : ZIX_STATUS_ERROR;
-}
-
-#else /* !defined(_WIN32) */
-
-static inline ZixStatus
-zix_thread_create(ZixThread* thread,
- size_t stack_size,
- void* (*function)(void*),
- void* arg)
-{
- pthread_attr_t attr;
- pthread_attr_init(&attr);
- pthread_attr_setstacksize(&attr, stack_size);
-
- const int ret = pthread_create(thread, NULL, function, arg);
- pthread_attr_destroy(&attr);
-
- switch (ret) {
- case EAGAIN:
- return ZIX_STATUS_NO_MEM;
- case EINVAL:
- return ZIX_STATUS_BAD_ARG;
- case EPERM:
- return ZIX_STATUS_BAD_PERMS;
- }
-
- return ret ? ZIX_STATUS_ERROR : ZIX_STATUS_SUCCESS;
-}
-
-static inline ZixStatus
-zix_thread_join(ZixThread thread, void** retval)
-{
- return pthread_join(thread, retval) ? ZIX_STATUS_ERROR : ZIX_STATUS_SUCCESS;
-}
-
-#endif
-
-/**
- @}
- @}
-*/
-
-#ifdef __cplusplus
-} /* extern "C" */
-#endif
-
-#endif /* ZIX_THREAD_H */
diff --git a/zix/tree.c b/zix/tree.c
deleted file mode 100644
index a204baf..0000000
--- a/zix/tree.c
+++ /dev/null
@@ -1,735 +0,0 @@
-/*
- Copyright 2011-2014 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/tree.h"
-
-#include "zix/common.h"
-
-#include <assert.h>
-#include <stdint.h>
-#include <stdlib.h>
-#include <string.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
-
-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);
- }
-}
-
-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;
-}
-
-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 `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 `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 `p->left` then right about `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 `p->right` then right about `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;
-}
-
-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 || 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;
-}
-
-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 = (uint8_t)height_change * -1;
- } else {
- assert(i == i->parent->right);
- d_balance = (uint8_t)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;
-}
-
-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;
- }
-
- if (cmp < 0) {
- n = n->left;
- } else {
- n = n->right;
- }
- }
-
- *ti = n;
- return (n) ? ZIX_STATUS_SUCCESS : ZIX_STATUS_NOT_FOUND;
-}
-
-void*
-zix_tree_get(const ZixTreeIter* ti)
-{
- return ti ? ti->data : NULL;
-}
-
-ZixTreeIter*
-zix_tree_begin(ZixTree* t)
-{
- if (!t->root) {
- return NULL;
- }
-
- ZixTreeNode* n = t->root;
- while (n->left) {
- n = n->left;
- }
-
- return n;
-}
-
-ZixTreeIter*
-zix_tree_end(ZixTree* ZIX_UNUSED(t))
-{
- return NULL;
-}
-
-ZixTreeIter*
-zix_tree_rbegin(ZixTree* t)
-{
- if (!t->root) {
- return NULL;
- }
-
- ZixTreeNode* n = t->root;
- while (n->right) {
- n = n->right;
- }
-
- return n;
-}
-
-ZixTreeIter*
-zix_tree_rend(ZixTree* ZIX_UNUSED(t))
-{
- return NULL;
-}
-
-bool
-zix_tree_iter_is_end(const ZixTreeIter* i)
-{
- return !i;
-}
-
-bool
-zix_tree_iter_is_rend(const ZixTreeIter* i)
-{
- return !i;
-}
-
-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;
-}
-
-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/zix/tree.h b/zix/tree.h
deleted file mode 100644
index c340fc0..0000000
--- a/zix/tree.h
+++ /dev/null
@@ -1,164 +0,0 @@
-/*
- Copyright 2011-2014 David Robillard <http://drobilla.net>
-
- Permission to use, copy, modify, and/or distribute this software for any
- purpose with or without fee is hereby granted, provided that the above
- copyright notice and this permission notice appear in all copies.
-
- THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
- WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
- MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
- ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
- WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
- ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
- OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
-*/
-
-#ifndef ZIX_TREE_H
-#define ZIX_TREE_H
-
-#include "zix/common.h"
-
-#include <stdbool.h>
-#include <stddef.h>
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-/**
- @addtogroup zix
- @{
- @name Tree
- @{
-*/
-
-/**
- A balanced binary search tree.
-*/
-typedef struct ZixTreeImpl ZixTree;
-
-/**
- An iterator over a @ref ZixTree.
-*/
-typedef struct ZixTreeNodeImpl ZixTreeIter;
-
-/**
- Create a new (empty) tree.
-*/
-ZIX_API
-ZixTree*
-zix_tree_new(bool allow_duplicates,
- ZixComparator cmp,
- void* cmp_data,
- ZixDestroyFunc destroy);
-
-/**
- Free `t`.
-*/
-ZIX_API
-void
-zix_tree_free(ZixTree* t);
-
-/**
- Return the number of elements in `t`.
-*/
-ZIX_PURE_API
-size_t
-zix_tree_size(const ZixTree* t);
-
-/**
- Insert the element `e` into `t` and point `ti` at the new element.
-*/
-ZIX_API
-ZixStatus
-zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti);
-
-/**
- Remove the item pointed at by `ti` from `t`.
-*/
-ZIX_API
-ZixStatus
-zix_tree_remove(ZixTree* t, ZixTreeIter* ti);
-
-/**
- Set `ti` to an element equal to `e` in `t`.
- If no such item exists, `ti` is set to NULL.
-*/
-ZIX_API
-ZixStatus
-zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti);
-
-/**
- Return the data associated with the given tree item.
-*/
-ZIX_PURE_API
-void*
-zix_tree_get(const ZixTreeIter* ti);
-
-/**
- Return an iterator to the first (smallest) element in `t`.
-*/
-ZIX_PURE_API
-ZixTreeIter*
-zix_tree_begin(ZixTree* t);
-
-/**
- Return an iterator the the element one past the last element in `t`.
-*/
-ZIX_CONST_API
-ZixTreeIter*
-zix_tree_end(ZixTree* t);
-
-/**
- Return true iff `i` is an iterator to the end of its tree.
-*/
-ZIX_CONST_API
-bool
-zix_tree_iter_is_end(const ZixTreeIter* i);
-
-/**
- Return an iterator to the last (largest) element in `t`.
-*/
-ZIX_PURE_API
-ZixTreeIter*
-zix_tree_rbegin(ZixTree* t);
-
-/**
- Return an iterator the the element one before the first element in `t`.
-*/
-ZIX_CONST_API
-ZixTreeIter*
-zix_tree_rend(ZixTree* t);
-
-/**
- Return true iff `i` is an iterator to the reverse end of its tree.
-*/
-ZIX_CONST_API
-bool
-zix_tree_iter_is_rend(const ZixTreeIter* i);
-
-/**
- Return an iterator that points to the element one past `i`.
-*/
-ZIX_PURE_API
-ZixTreeIter*
-zix_tree_iter_next(ZixTreeIter* i);
-
-/**
- Return an iterator that points to the element one before `i`.
-*/
-ZIX_PURE_API
-ZixTreeIter*
-zix_tree_iter_prev(ZixTreeIter* i);
-
-/**
- @}
- @}
-*/
-
-#ifdef __cplusplus
-} /* extern "C" */
-#endif
-
-#endif /* ZIX_TREE_H */
diff --git a/zix/tree_debug.h b/zix/tree_debug.h
deleted file mode 100644
index 68e37b6..0000000
--- a/zix/tree_debug.h
+++ /dev/null
@@ -1,175 +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
-
-#include <inttypes.h>
-
-#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
diff --git a/zix/zix.h b/zix/zix.h
deleted file mode 100644
index 96d9e10..0000000
--- a/zix/zix.h
+++ /dev/null
@@ -1,35 +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_ZIX_H
-#define ZIX_ZIX_H
-
-/**
- @defgroup zix Zix
- A lightweight portability library.
- @{
-*/
-
-#include "zix/btree.h"
-#include "zix/common.h"
-#include "zix/sorted_array.h"
-#include "zix/tree.h"
-
-/**
- @}
-*/
-
-#endif /* ZIX_ZIX_H */