diff options
| -rw-r--r-- | include/zix/bitset.h | 36 | ||||
| -rw-r--r-- | include/zix/btree.h | 49 | ||||
| -rw-r--r-- | include/zix/common.h | 12 | ||||
| -rw-r--r-- | include/zix/digest.h | 4 | ||||
| -rw-r--r-- | include/zix/hash.h | 16 | ||||
| -rw-r--r-- | include/zix/ring.h | 32 | ||||
| -rw-r--r-- | include/zix/sem.h | 12 | ||||
| -rw-r--r-- | include/zix/sorted_array.h | 53 | ||||
| -rw-r--r-- | include/zix/strindex.h | 6 | ||||
| -rw-r--r-- | include/zix/thread.h | 4 | ||||
| -rw-r--r-- | include/zix/tree.h | 65 | ||||
| -rw-r--r-- | src/bitset.c | 2 | ||||
| -rw-r--r-- | src/btree.c | 22 | ||||
| -rw-r--r-- | test/btree_test.c | 2 |
14 files changed, 91 insertions, 224 deletions
diff --git a/include/zix/bitset.h b/include/zix/bitset.h index 2abf578..07f133f 100644 --- a/include/zix/bitset.h +++ b/include/zix/bitset.h @@ -31,59 +31,41 @@ @{ */ -/** - A bitset (always referred to by pointer, actually an array). -*/ +/// A bitset (always referred to by pointer, actually an array) typedef unsigned long ZixBitset; -/** - Tally of the number of bits in one ZixBitset element. -*/ +/// Tally of the number of bits in one ZixBitset element typedef uint8_t ZixBitsetTally; -/** - The number of bits per ZixBitset array element. -*/ +/// 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. -*/ +/// 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. -*/ +/// Clear a Bitset ZIX_API void zix_bitset_clear(ZixBitset* b, ZixBitsetTally* t, size_t n_bits); -/** - Set bit `i` in `t` to 1. -*/ +/// 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). -*/ +/// 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`. -*/ +/// 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). -*/ +/// 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); diff --git a/include/zix/btree.h b/include/zix/btree.h index bec0698..bce3068 100644 --- a/include/zix/btree.h +++ b/include/zix/btree.h @@ -33,14 +33,10 @@ extern "C" { @{ */ -/** - A B-Tree. -*/ +/// A B-Tree typedef struct ZixBTreeImpl ZixBTree; -/** - A B-Tree node (opaque). -*/ +/// A B-Tree node (opaque) typedef struct ZixBTreeNodeImpl ZixBTreeNode; /** @@ -51,30 +47,22 @@ typedef struct ZixBTreeNodeImpl ZixBTreeNode; */ typedef struct ZixBTreeIterImpl ZixBTreeIter; -/** - Create a new (empty) B-Tree. -*/ +/// Create a new (empty) B-Tree ZIX_API ZixBTree* zix_btree_new(ZixComparator cmp, const void* cmp_data, ZixDestroyFunc destroy); -/** - Free `t`. -*/ +/// Free `t` ZIX_API void zix_btree_free(ZixBTree* t); -/** - Return the number of elements in `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`. -*/ +/// Insert the element `e` into `t` ZIX_API ZixStatus zix_btree_insert(ZixBTree* t, void* e); @@ -98,6 +86,7 @@ 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 @@ -115,9 +104,7 @@ ZIX_API ZixStatus zix_btree_lower_bound(const ZixBTree* t, const void* e, ZixBTreeIter** ti); -/** - Return the data associated with the given tree item. -*/ +/// Return the data associated with the given tree item ZIX_PURE_API void* zix_btree_get(const ZixBTreeIter* ti); @@ -140,37 +127,27 @@ ZIX_API ZixBTreeIter* zix_btree_end(const ZixBTree* t); -/** - Return a new copy of `i`. -*/ +/// Return a new copy of `i` ZIX_API ZixBTreeIter* zix_btree_iter_copy(const ZixBTreeIter* i); -/** - Return true iff `lhs` is equal to `rhs`. -*/ +/// 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. -*/ +/// 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. -*/ +/// Increment `i` to point to the next element in the tree ZIX_API void zix_btree_iter_increment(ZixBTreeIter* i); -/** - Free `i`. -*/ +/// Free `i` ZIX_API void zix_btree_iter_free(ZixBTreeIter* i); diff --git a/include/zix/common.h b/include/zix/common.h index 02481ff..926e281 100644 --- a/include/zix/common.h +++ b/include/zix/common.h @@ -112,21 +112,15 @@ zix_strerror(const ZixStatus status) return "Unknown error"; } -/** - Function for comparing two elements. -*/ +/// 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. -*/ +/// Function for testing equality of two elements typedef bool (*ZixEqualFunc)(const void* a, const void* b); -/** - Function to destroy an element. -*/ +/// Function to destroy an element typedef void (*ZixDestroyFunc)(void* ptr); /** diff --git a/include/zix/digest.h b/include/zix/digest.h index 1fde77a..41db20f 100644 --- a/include/zix/digest.h +++ b/include/zix/digest.h @@ -26,9 +26,7 @@ extern "C" { #endif -/** - Return an initial empty digest value. -*/ +/// Return an initial empty digest value ZIX_CONST_API uint32_t zix_digest_start(void); diff --git a/include/zix/hash.h b/include/zix/hash.h index 3905038..6312d7b 100644 --- a/include/zix/hash.h +++ b/include/zix/hash.h @@ -35,14 +35,10 @@ extern "C" { typedef struct ZixHashImpl ZixHash; -/** - Function for computing the hash of an element. -*/ +/// Function for computing the hash of an element typedef uint32_t (*ZixHashFunc)(const void* value); -/** - Function to visit a hash element. -*/ +/// Function to visit a hash element typedef void (*ZixHashVisitFunc)(void* value, void* user_data); /** @@ -62,16 +58,12 @@ ZIX_API ZixHash* zix_hash_new(ZixHashFunc hash_func, ZixEqualFunc equal_func, size_t value_size); -/** - Free `hash`. -*/ +/// Free `hash` ZIX_API void zix_hash_free(ZixHash* hash); -/** - Return the number of elements in `hash`. -*/ +/// Return the number of elements in `hash` ZIX_PURE_API size_t zix_hash_size(const ZixHash* hash); diff --git a/include/zix/ring.h b/include/zix/ring.h index a375cac..2650f07 100644 --- a/include/zix/ring.h +++ b/include/zix/ring.h @@ -50,9 +50,7 @@ ZIX_MALLOC_API ZixRing* zix_ring_new(uint32_t size); -/** - Destroy a ring. -*/ +/// Destroy a ring ZIX_API void zix_ring_free(ZixRing* ring); @@ -80,51 +78,37 @@ ZIX_API void zix_ring_reset(ZixRing* ring); -/** - Return the number of bytes of space available for reading. -*/ +/// 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. -*/ +/// 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). -*/ +/// 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. -*/ +/// 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. -*/ +/// 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). -*/ +/// 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. -*/ +/// Write data to the ring ZIX_API uint32_t zix_ring_write(ZixRing* ring, const void* src, uint32_t size); diff --git a/include/zix/sem.h b/include/zix/sem.h index d42fd08..5b018fc 100644 --- a/include/zix/sem.h +++ b/include/zix/sem.h @@ -63,20 +63,17 @@ struct ZixSemImpl; */ typedef struct ZixSemImpl ZixSem; -/** - Create and initialize `sem` to `initial`. -*/ +/// Create and initialize `sem` to `initial` static inline ZixStatus zix_sem_init(ZixSem* sem, unsigned initial); -/** - Destroy `sem`. -*/ +/// Destroy `sem` static inline void zix_sem_destroy(ZixSem* sem); /** - Increment (and signal any waiters). + Increment and signal any waiters. + Realtime safe. */ static inline void @@ -84,6 +81,7 @@ zix_sem_post(ZixSem* sem); /** Wait until count is > 0, then decrement. + Obviously not realtime safe. */ static inline ZixStatus diff --git a/include/zix/sorted_array.h b/include/zix/sorted_array.h index df0a97c..580551e 100644 --- a/include/zix/sorted_array.h +++ b/include/zix/sorted_array.h @@ -33,19 +33,13 @@ extern "C" { @{ */ -/** - A sorted array. -*/ +/// A sorted array typedef struct ZixSortedArrayImpl ZixSortedArray; -/** - An iterator over a ZixSortedArray. -*/ +/// An iterator over a ZixSortedArray typedef void* ZixSortedArrayIter; -/** - Create a new (empty) sorted array. -*/ +/// Create a new (empty) sorted array ZIX_API ZixSortedArray* zix_sorted_array_new(bool allow_duplicates, @@ -53,38 +47,31 @@ zix_sorted_array_new(bool allow_duplicates, void* cmp_data, size_t elem_size); -/** - Free `a`. -*/ +/// Free `a` ZIX_API void zix_sorted_array_free(ZixSortedArray* a); -/** - Return the number of elements in `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. -*/ +/// 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`. -*/ +/// 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 @@ -93,44 +80,32 @@ zix_sorted_array_find(const ZixSortedArray* a, const void* e, ZixSortedArrayIter* ai); -/** - Return the element at index `index`. -*/ +/// 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. -*/ +/// 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`. -*/ +/// 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`. -*/ +/// 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. -*/ +/// 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`. -*/ +/// Return an iterator that points to the element one past `a` ZIX_PURE_API ZixSortedArrayIter zix_sorted_array_iter_next(ZixSortedArray* a, ZixSortedArrayIter i); diff --git a/include/zix/strindex.h b/include/zix/strindex.h index f596079..8493b8c 100644 --- a/include/zix/strindex.h +++ b/include/zix/strindex.h @@ -30,21 +30,21 @@ typedef struct ZixStrindexImpl 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`. -*/ +/// 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 diff --git a/include/zix/thread.h b/include/zix/thread.h index 77eeb1b..baf1fde 100644 --- a/include/zix/thread.h +++ b/include/zix/thread.h @@ -57,9 +57,7 @@ zix_thread_create(ZixThread* thread, void* (*function)(void*), void* arg); -/** - Join `thread` (block until `thread` exits). -*/ +/// Join `thread` (block until `thread` exits) static inline ZixStatus zix_thread_join(ZixThread thread, void** retval); diff --git a/include/zix/tree.h b/include/zix/tree.h index a2d5fe7..d7d2cce 100644 --- a/include/zix/tree.h +++ b/include/zix/tree.h @@ -33,19 +33,13 @@ extern "C" { @{ */ -/** - A balanced binary search tree. -*/ +/// A balanced binary search tree typedef struct ZixTreeImpl ZixTree; -/** - An iterator over a @ref ZixTree. -*/ +/// An iterator over a @ref ZixTree typedef struct ZixTreeNodeImpl ZixTreeIter; -/** - Create a new (empty) tree. -*/ +/// Create a new (empty) tree ZIX_API ZixTree* zix_tree_new(bool allow_duplicates, @@ -53,101 +47,76 @@ zix_tree_new(bool allow_duplicates, void* cmp_data, ZixDestroyFunc destroy); -/** - Free `t`. -*/ +/// Free `t` ZIX_API void zix_tree_free(ZixTree* t); -/** - Return the number of elements in `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. -*/ +/// 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`. -*/ +/// 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. -*/ +/// 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`. -*/ +/// 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`. -*/ +/// 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. -*/ +/// 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`. -*/ +/// 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`. -*/ +/// 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. -*/ +/// 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`. -*/ +/// 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`. -*/ +/// Return an iterator that points to the element one before `i` ZIX_PURE_API ZixTreeIter* zix_tree_iter_prev(ZixTreeIter* i); diff --git a/src/bitset.c b/src/bitset.c index f4293bf..e818225 100644 --- a/src/bitset.c +++ b/src/bitset.c @@ -22,7 +22,7 @@ #include <string.h> -/** Number of bits per ZixBitset element (ala CHAR_BIT). */ +/// Number of bits per ZixBitset element (ala CHAR_BIT) #define ZIX_BITSET_ELEM_BIT (CHAR_BIT * sizeof(ZixBitset)) static inline size_t diff --git a/src/btree.c b/src/btree.c index 56c9767..9e6d285 100644 --- a/src/btree.c +++ b/src/btree.c @@ -1,5 +1,5 @@ /* - Copyright 2011-2020 David Robillard <d@drobilla.net> + Copyright 2011-2021 David Robillard <d@drobilla.net> Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted, provided that the above @@ -216,7 +216,7 @@ 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`. */ +/// Shift pointers in `array` of length `n` right starting at `i` static void zix_btree_ainsert(void** const array, const unsigned n, @@ -227,7 +227,7 @@ zix_btree_ainsert(void** const array, array[i] = e; } -/** Erase element `i` in `array` of length `n` and return erased element. */ +/// Erase element `i` in `array` of length `n` and return erased element static void* zix_btree_aerase(void** const array, const unsigned n, const unsigned i) { @@ -236,7 +236,7 @@ zix_btree_aerase(void** const array, const unsigned n, const unsigned i) return ret; } -/** Split lhs, the i'th child of `n`, into two nodes. */ +/// Split lhs, the i'th child of `n`, into two nodes static ZixBTreeNode* zix_btree_split_child(ZixBTreeNode* const n, const unsigned i, @@ -287,7 +287,7 @@ zix_btree_split_child(ZixBTreeNode* const n, } #ifdef ZIX_BTREE_SORTED_CHECK -/** Check that `n` is sorted with respect to search key `e`. */ +/// Check that `n` is sorted with respect to search key `e` static bool zix_btree_node_is_sorted_with_respect_to(const ZixBTree* const t, const ZixBTreeNode* const n, @@ -310,7 +310,7 @@ zix_btree_node_is_sorted_with_respect_to(const ZixBTree* const t, } #endif -/** Find the first value in `n` that is not less than `e` (lower bound). */ +/// Find the first value in `n` that is not less than `e` (lower bound) static unsigned zix_btree_node_find(const ZixBTree* const t, const ZixBTreeNode* const n, @@ -434,7 +434,7 @@ zix_btree_node_is_minimal(ZixBTreeNode* const n) return n->n_vals == zix_btree_min_vals(n); } -/** Enlarge left child by stealing a value from its right sibling. */ +/// Enlarge left child by stealing a value from its right sibling static ZixBTreeNode* zix_btree_rotate_left(ZixBTreeNode* const parent, const unsigned i) { @@ -468,7 +468,7 @@ zix_btree_rotate_left(ZixBTreeNode* const parent, const unsigned i) return lhs; } -/** Enlarge right child by stealing a value from its left sibling. */ +/// Enlarge right child by stealing a value from its left sibling static ZixBTreeNode* zix_btree_rotate_right(ZixBTreeNode* const parent, const unsigned i) { @@ -502,7 +502,7 @@ zix_btree_rotate_right(ZixBTreeNode* const parent, const unsigned i) return rhs; } -/** Move n[i] down, merge the left and right child, return the merged node. */ +/// Move n[i] down, merge the left and right child, return the merged node static ZixBTreeNode* zix_btree_merge(ZixBTree* const t, ZixBTreeNode* const n, const unsigned i) { @@ -552,7 +552,7 @@ zix_btree_merge(ZixBTree* const t, ZixBTreeNode* const n, const unsigned i) return lhs; } -/** Remove and return the min value from the subtree rooted at `n`. */ +/// Remove and return the min value from the subtree rooted at `n` static void* zix_btree_remove_min(ZixBTree* const t, ZixBTreeNode* n) { @@ -574,7 +574,7 @@ zix_btree_remove_min(ZixBTree* const t, ZixBTreeNode* n) return zix_btree_aerase(n->data.leaf.vals, --n->n_vals, 0); } -/** Remove and return the max value from the subtree rooted at `n`. */ +/// Remove and return the max value from the subtree rooted at `n` static void* zix_btree_remove_max(ZixBTree* const t, ZixBTreeNode* n) { diff --git a/test/btree_test.c b/test/btree_test.c index 7738397..d4dd6b4 100644 --- a/test/btree_test.c +++ b/test/btree_test.c @@ -86,7 +86,7 @@ wildcard_cut(unsigned test_num, size_t n_elems) return ith_elem(test_num, n_elems, n_elems / 3); } -/** Wildcard comparator where 0 matches anything >= wildcard_cut(n_elems). */ +/// Wildcard comparator where 0 matches anything >= wildcard_cut(n_elems) static int wildcard_cmp(const void* a, const void* b, const void* user_data) { |