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 +++++++ 13 files changed, 1618 insertions(+) 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 (limited to 'include') 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 */ -- cgit v1.2.1