From ed9a6e98b8e4e010117e1228333569aa31c51d9e Mon Sep 17 00:00:00 2001 From: David Robillard Date: Thu, 31 Dec 2020 15:34:15 +0100 Subject: Separate source from headers --- include/zix/bitset.h | 106 +++++ include/zix/btree.h | 187 +++++++++ include/zix/chunk.h | 50 +++ include/zix/common.h | 150 +++++++ include/zix/digest.h | 67 ++++ include/zix/hash.h | 138 +++++++ include/zix/ring.h | 141 +++++++ include/zix/sem.h | 242 ++++++++++++ include/zix/sorted_array.h | 147 +++++++ include/zix/strindex.h | 59 +++ include/zix/thread.h | 132 +++++++ include/zix/tree.h | 164 ++++++++ include/zix/zix.h | 35 ++ src/bitset.c | 124 ++++++ src/btree.c | 957 +++++++++++++++++++++++++++++++++++++++++++++ src/chunk.c | 33 ++ src/digest.c | 141 +++++++ src/hash.c | 230 +++++++++++ src/ring.c | 222 +++++++++++ src/sorted_array.c | 193 +++++++++ src/strindex.c | 261 +++++++++++++ src/tree.c | 735 ++++++++++++++++++++++++++++++++++ src/tree_debug.h | 175 +++++++++ test/inline_test.c | 31 -- wscript | 36 +- zix/bitset.c | 124 ------ zix/bitset.h | 106 ----- zix/btree.c | 957 --------------------------------------------- zix/btree.h | 187 --------- zix/chunk.c | 33 -- zix/chunk.h | 50 --- zix/common.h | 150 ------- zix/digest.c | 141 ------- zix/digest.h | 67 ---- zix/hash.c | 230 ----------- zix/hash.h | 138 ------- zix/ring.c | 222 ----------- zix/ring.h | 141 ------- zix/sem.h | 242 ------------ zix/sorted_array.c | 193 --------- zix/sorted_array.h | 147 ------- zix/strindex.c | 261 ------------- zix/strindex.h | 59 --- zix/thread.h | 132 ------- zix/tree.c | 735 ---------------------------------- zix/tree.h | 164 -------- zix/tree_debug.h | 175 --------- zix/zix.h | 35 -- 48 files changed, 4707 insertions(+), 4738 deletions(-) create mode 100644 include/zix/bitset.h create mode 100644 include/zix/btree.h create mode 100644 include/zix/chunk.h create mode 100644 include/zix/common.h create mode 100644 include/zix/digest.h create mode 100644 include/zix/hash.h create mode 100644 include/zix/ring.h create mode 100644 include/zix/sem.h create mode 100644 include/zix/sorted_array.h create mode 100644 include/zix/strindex.h create mode 100644 include/zix/thread.h create mode 100644 include/zix/tree.h create mode 100644 include/zix/zix.h create mode 100644 src/bitset.c create mode 100644 src/btree.c create mode 100644 src/chunk.c create mode 100644 src/digest.c create mode 100644 src/hash.c create mode 100644 src/ring.c create mode 100644 src/sorted_array.c create mode 100644 src/strindex.c create mode 100644 src/tree.c create mode 100644 src/tree_debug.h delete mode 100644 test/inline_test.c delete mode 100644 zix/bitset.c delete mode 100644 zix/bitset.h delete mode 100644 zix/btree.c delete mode 100644 zix/btree.h delete mode 100644 zix/chunk.c delete mode 100644 zix/chunk.h delete mode 100644 zix/common.h delete mode 100644 zix/digest.c delete mode 100644 zix/digest.h delete mode 100644 zix/hash.c delete mode 100644 zix/hash.h delete mode 100644 zix/ring.c delete mode 100644 zix/ring.h delete mode 100644 zix/sem.h delete mode 100644 zix/sorted_array.c delete mode 100644 zix/sorted_array.h delete mode 100644 zix/strindex.c delete mode 100644 zix/strindex.h delete mode 100644 zix/thread.h delete mode 100644 zix/tree.c delete mode 100644 zix/tree.h delete mode 100644 zix/tree_debug.h delete mode 100644 zix/zix.h diff --git a/include/zix/bitset.h b/include/zix/bitset.h new file mode 100644 index 0000000..68dd344 --- /dev/null +++ b/include/zix/bitset.h @@ -0,0 +1,106 @@ +/* + Copyright 2014-2016 David Robillard + + 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 +#include +#include +#include + +/** + @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/include/zix/btree.h b/include/zix/btree.h new file mode 100644 index 0000000..dde659f --- /dev/null +++ b/include/zix/btree.h @@ -0,0 +1,187 @@ +/* + Copyright 2011-2016 David Robillard + + 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 +#include + +#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/include/zix/chunk.h b/include/zix/chunk.h new file mode 100644 index 0000000..3646718 --- /dev/null +++ b/include/zix/chunk.h @@ -0,0 +1,50 @@ +/* + Copyright 2012 David Robillard + + 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 +#include +#include + +#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/include/zix/common.h b/include/zix/common.h new file mode 100644 index 0000000..865d232 --- /dev/null +++ b/include/zix/common.h @@ -0,0 +1,150 @@ +/* + Copyright 2016 David Robillard + + 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 + +/** + @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/include/zix/digest.h b/include/zix/digest.h new file mode 100644 index 0000000..7d44c3d --- /dev/null +++ b/include/zix/digest.h @@ -0,0 +1,67 @@ +/* + Copyright 2012-2020 David Robillard + + 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 +#include + +#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/include/zix/hash.h b/include/zix/hash.h new file mode 100644 index 0000000..bef1568 --- /dev/null +++ b/include/zix/hash.h @@ -0,0 +1,138 @@ +/* + Copyright 2011-2015 David Robillard + + 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 +#include + +#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/include/zix/ring.h b/include/zix/ring.h new file mode 100644 index 0000000..a64d227 --- /dev/null +++ b/include/zix/ring.h @@ -0,0 +1,141 @@ +/* + Copyright 2011-2014 David Robillard + + 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 + +#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/include/zix/sem.h b/include/zix/sem.h new file mode 100644 index 0000000..ae59f10 --- /dev/null +++ b/include/zix/sem.h @@ -0,0 +1,242 @@ +/* + Copyright 2012-2014 David Robillard + + 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 +#elif defined(_WIN32) +# include +# include +#else +# include +# include +#endif + +#ifdef __cplusplus +extern "C" { +#endif + +#include + +/** + @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/include/zix/sorted_array.h b/include/zix/sorted_array.h new file mode 100644 index 0000000..92f13e6 --- /dev/null +++ b/include/zix/sorted_array.h @@ -0,0 +1,147 @@ +/* + Copyright 2011-2014 David Robillard + + 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 +#include + +#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/include/zix/strindex.h b/include/zix/strindex.h new file mode 100644 index 0000000..beb4646 --- /dev/null +++ b/include/zix/strindex.h @@ -0,0 +1,59 @@ +/* + Copyright 2011-2014 David Robillard + + 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/include/zix/thread.h b/include/zix/thread.h new file mode 100644 index 0000000..8fa562d --- /dev/null +++ b/include/zix/thread.h @@ -0,0 +1,132 @@ +/* + Copyright 2012-2014 David Robillard + + 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 +#else +# include +# include +#endif + +#include + +#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/include/zix/tree.h b/include/zix/tree.h new file mode 100644 index 0000000..c340fc0 --- /dev/null +++ b/include/zix/tree.h @@ -0,0 +1,164 @@ +/* + Copyright 2011-2014 David Robillard + + 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 +#include + +#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/include/zix/zix.h b/include/zix/zix.h new file mode 100644 index 0000000..96d9e10 --- /dev/null +++ b/include/zix/zix.h @@ -0,0 +1,35 @@ +/* + Copyright 2011 David Robillard + + 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 */ diff --git a/src/bitset.c b/src/bitset.c new file mode 100644 index 0000000..cf82ad0 --- /dev/null +++ b/src/bitset.c @@ -0,0 +1,124 @@ +/* + Copyright 2014-2016 David Robillard + + 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 +#endif + +#include + +/** 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/src/btree.c b/src/btree.c new file mode 100644 index 0000000..7435445 --- /dev/null +++ b/src/btree.c @@ -0,0 +1,957 @@ +/* + Copyright 2011-2020 David Robillard + + 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 +#include +#include +#include + +// #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/src/chunk.c b/src/chunk.c new file mode 100644 index 0000000..bf80f88 --- /dev/null +++ b/src/chunk.c @@ -0,0 +1,33 @@ +/* + Copyright 2012 David Robillard + + 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 + +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/src/digest.c b/src/digest.c new file mode 100644 index 0000000..941b05c --- /dev/null +++ b/src/digest.c @@ -0,0 +1,141 @@ +/* + Copyright 2012-2020 David Robillard + + 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 +#endif + +#include +#include + +#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/src/hash.c b/src/hash.c new file mode 100644 index 0000000..34464d4 --- /dev/null +++ b/src/hash.c @@ -0,0 +1,230 @@ +/* + Copyright 2011-2018 David Robillard + + 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 +#include +#include + +/** + 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/src/ring.c b/src/ring.c new file mode 100644 index 0000000..0607a18 --- /dev/null +++ b/src/ring.c @@ -0,0 +1,222 @@ +/* + Copyright 2011 David Robillard + + 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 +#include + +#ifdef HAVE_MLOCK +# include +# define ZIX_MLOCK(ptr, size) mlock((ptr), (size)) +#elif defined(_WIN32) +# include +# 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 +# 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/src/sorted_array.c b/src/sorted_array.c new file mode 100644 index 0000000..0f84227 --- /dev/null +++ b/src/sorted_array.c @@ -0,0 +1,193 @@ +/* + Copyright 2011 David Robillard + + 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 +#include +#include +#include + +// #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/src/strindex.c b/src/strindex.c new file mode 100644 index 0000000..8cb05c9 --- /dev/null +++ b/src/strindex.c @@ -0,0 +1,261 @@ +/* + Copyright 2011 David Robillard + + 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 +#include +#include +#include + +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/src/tree.c b/src/tree.c new file mode 100644 index 0000000..a204baf --- /dev/null +++ b/src/tree.c @@ -0,0 +1,735 @@ +/* + Copyright 2011-2014 David Robillard + + 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 +#include +#include +#include + +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/src/tree_debug.h b/src/tree_debug.h new file mode 100644 index 0000000..68e37b6 --- /dev/null +++ b/src/tree_debug.h @@ -0,0 +1,175 @@ +/* + Copyright 2011 David Robillard + + 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 + +#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/test/inline_test.c b/test/inline_test.c deleted file mode 100644 index b07f28a..0000000 --- a/test/inline_test.c +++ /dev/null @@ -1,31 +0,0 @@ -/* - Copyright 2012 David Robillard - - 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 ZIX_INLINE - -#include "zix/common.h" -#include "zix/hash.c" -#include "zix/tree.c" - -#include - -ZIX_CONST_FUNC int -main(void) -{ - zix_hash_free(NULL); - zix_tree_free(NULL); - return 0; -} diff --git a/wscript b/wscript index 3e3faf1..c67e844 100644 --- a/wscript +++ b/wscript @@ -119,21 +119,20 @@ def configure(conf): sources = [ - 'zix/chunk.c', - 'zix/digest.c', - 'zix/hash.c', - 'zix/ring.c', - 'zix/sorted_array.c', - 'zix/strindex.c', - 'zix/tree.c', - 'zix/btree.c', - 'zix/bitset.c', + 'src/chunk.c', + 'src/digest.c', + 'src/hash.c', + 'src/ring.c', + 'src/sorted_array.c', + 'src/strindex.c', + 'src/tree.c', + 'src/btree.c', + 'src/bitset.c', ] tests = [ 'digest_test', 'hash_test', - 'inline_test', 'ring_test', 'sem_test', 'sorted_array_test', @@ -146,7 +145,8 @@ tests = [ def build(bld): # C Headers - bld.install_files('${INCLUDEDIR}/zix', bld.path.ant_glob('zix/*.h')) + includedir = '${INCLUDEDIR}/zix-%s/zix' % ZIX_MAJOR_VERSION + bld.install_files(includedir, bld.path.ant_glob('include/zix/*.h')) # Pkgconfig file autowaf.build_pc(bld, 'ZIX', ZIX_VERSION, ZIX_MAJOR_VERSION, [], @@ -162,9 +162,9 @@ def build(bld): # Library bld(features = 'c cshlib', - export_includes = ['.'], + export_includes = ['.', 'include'], source = sources, - includes = ['.'], + includes = ['.', 'include'], name = 'libzix', target = 'zix', vnum = ZIX_VERSION, @@ -174,9 +174,9 @@ def build(bld): if bld.env.BUILD_STATIC or bld.env.BUILD_BENCH: bld(features = 'c cstlib', - export_includes = ['.'], + export_includes = ['.', 'include'], source = sources, - includes = ['.'], + includes = ['.', 'include'], name = 'libzix_static', target = 'zix', vnum = ZIX_VERSION, @@ -199,7 +199,7 @@ def build(bld): # Profiled static library (for unit test code coverage) bld(features = 'c cstlib', source = sources, - includes = ['.'], + includes = ['.', 'include'], lib = test_libs, name = 'libzix_profiled', target = 'zix_profiled', @@ -218,7 +218,7 @@ def build(bld): for i in tests: bld(features = 'c cprogram', source = ['test/%s.c' % i] + test_malloc, - includes = ['.'], + includes = ['.', 'include'], use = 'libzix_profiled', lib = test_libs, target = 'test/%s' % i, @@ -232,7 +232,7 @@ def build(bld): for i in ['tree_bench', 'dict_bench']: bld(features = 'c cprogram', source = 'benchmark/%s.c' % i, - includes = ['.'], + includes = ['.', 'include'], use = 'libzix_static', uselib = 'GLIB', lib = ['rt'], 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 - - 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 -#endif - -#include - -/** 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 - - 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 -#include -#include -#include - -/** - @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 - - 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 -#include -#include -#include - -// #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 - - 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 -#include - -#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 - - 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 - -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 - - 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 -#include -#include - -#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 - - 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 - -/** - @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 - - 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 -#endif - -#include -#include - -#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 - - 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 -#include - -#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 - - 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 -#include -#include - -/** - 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 - - 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 -#include - -#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 - - 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 -#include - -#ifdef HAVE_MLOCK -# include -# define ZIX_MLOCK(ptr, size) mlock((ptr), (size)) -#elif defined(_WIN32) -# include -# 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 -# 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 - - 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 - -#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 - - 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 -#elif defined(_WIN32) -# include -# include -#else -# include -# include -#endif - -#ifdef __cplusplus -extern "C" { -#endif - -#include - -/** - @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 - - 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 -#include -#include -#include - -// #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 - - 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 -#include - -#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 - - 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 -#include -#include -#include - -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 - - 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 - - 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 -#else -# include -# include -#endif - -#include - -#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 - - 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 -#include -#include -#include - -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 - - 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 -#include - -#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 - - 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 - -#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 - - 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 */ -- cgit v1.2.1