diff options
| -rw-r--r-- | include/zix/btree.h | 176 | ||||
| -rw-r--r-- | include/zix/hash.h | 92 | ||||
| -rw-r--r-- | include/zix/ring.h | 2 | ||||
| -rw-r--r-- | include/zix/thread.h | 8 | ||||
| -rw-r--r-- | include/zix/tree.h | 70 |
5 files changed, 222 insertions, 126 deletions
diff --git a/include/zix/btree.h b/include/zix/btree.h index f3b365a..3161817 100644 --- a/include/zix/btree.h +++ b/include/zix/btree.h @@ -21,6 +21,11 @@ ZIX_BEGIN_DECLS */ /** + @defgroup zix_btree_setup Setup + @{ +*/ + +/** The maximum height of a ZixBTree. This is exposed because it determines the size of iterators, which are @@ -36,9 +41,6 @@ ZIX_BEGIN_DECLS /// A B-Tree typedef struct ZixBTreeImpl ZixBTree; -/// A B-Tree node (opaque) -typedef struct ZixBTreeNodeImpl ZixBTreeNode; - /// Function for comparing two B-Tree elements typedef int (*ZixBTreeCompareFunc)(const void* ZIX_UNSPECIFIED a, const void* ZIX_UNSPECIFIED b, @@ -49,27 +51,6 @@ typedef void (*ZixBTreeDestroyFunc)(void* ZIX_UNSPECIFIED ptr, const void* ZIX_UNSPECIFIED user_data); /** - An iterator over a B-Tree. - - Note that modifying the tree invalidates all iterators. - - The contents of this type are considered an implementation detail and should - not be used directly by clients. They are nevertheless exposed here so that - iterators can be allocated on the stack. -*/ -typedef struct { - ZixBTreeNode* ZIX_NULLABLE nodes[ZIX_BTREE_MAX_HEIGHT]; ///< Node stack - uint16_t indexes[ZIX_BTREE_MAX_HEIGHT]; ///< Index stack - uint16_t level; ///< Current level -} ZixBTreeIter; - -/// A static end iterator for convenience -static const ZixBTreeIter zix_btree_end_iter = { - {NULL, NULL, NULL, NULL, NULL, NULL}, - {0U, 0U, 0U, 0U, 0U, 0U}, - 0U}; - -/** Create a new (empty) B-Tree. The given comparator must be a total ordering and is used to internally @@ -92,13 +73,13 @@ zix_btree_new(ZixAllocator* ZIX_NULLABLE allocator, @param destroy Function to call once for every value in the tree. This can be used to free values if they are dynamically allocated. - @param destroy_user_data Opaque pointer to pass to `destroy`. + @param destroy_data Opaque user data pointer to pass to `destroy`. */ ZIX_API void zix_btree_free(ZixBTree* ZIX_NULLABLE t, ZixBTreeDestroyFunc ZIX_NULLABLE destroy, - const void* ZIX_NULLABLE destroy_user_data); + const void* ZIX_NULLABLE destroy_data); /** Clear everything from `t`, leaving it empty. @@ -108,26 +89,105 @@ zix_btree_free(ZixBTree* ZIX_NULLABLE t, @param destroy Function called exactly once for every value in the tree, just before that value is removed from the tree. - @param destroy_user_data Opaque pointer to pass to `destroy`. + @param destroy_data Opaque user data pointer to pass to `destroy`. */ ZIX_API void zix_btree_clear(ZixBTree* ZIX_NONNULL t, ZixBTreeDestroyFunc ZIX_NULLABLE destroy, - const void* ZIX_NULLABLE destroy_user_data); + const void* ZIX_NULLABLE destroy_data); /// Return the number of elements in `t` ZIX_PURE_API size_t zix_btree_size(const ZixBTree* ZIX_NONNULL t); -/// Insert the element `e` into `t` +/** + @} + @defgroup zix_btree_iteration Iteration + @{ +*/ + +/// An opaque node in a B-Tree +typedef struct ZixBTreeNodeImpl ZixBTreeNode; + +/** + An iterator over a B-Tree. + + Note that modifying the tree invalidates all iterators. + + The contents of this type are considered an implementation detail and should + not be used directly by clients. They are nevertheless exposed here so that + iterators can be allocated on the stack. +*/ +typedef struct { + ZixBTreeNode* ZIX_NULLABLE nodes[ZIX_BTREE_MAX_HEIGHT]; ///< Node stack + uint16_t indexes[ZIX_BTREE_MAX_HEIGHT]; ///< Index stack + uint16_t level; ///< Current level +} ZixBTreeIter; + +/// A static end iterator for convenience +static const ZixBTreeIter zix_btree_end_iter = { + {NULL, NULL, NULL, NULL, NULL, NULL}, + {0U, 0U, 0U, 0U, 0U, 0U}, + 0U, +}; + +/// Return the data at the given position in the tree +ZIX_PURE_API +void* ZIX_UNSPECIFIED +zix_btree_get(ZixBTreeIter ti); + +/// Return an iterator to the first (smallest) element in `t` +ZIX_PURE_API +ZixBTreeIter +zix_btree_begin(const ZixBTree* ZIX_NONNULL t); + +/// Return an iterator to the end of `t` (one past the last element) +ZIX_CONST_API +ZixBTreeIter +zix_btree_end(const ZixBTree* ZIX_NULLABLE t); + +/// Return true iff `lhs` is equal to `rhs` +ZIX_CONST_API +bool +zix_btree_iter_equals(ZixBTreeIter lhs, ZixBTreeIter rhs); + +/// Return true iff `i` is an iterator at the end of a tree +static inline bool +zix_btree_iter_is_end(const ZixBTreeIter i) +{ + return i.level == 0 && !i.nodes[0]; +} + +/// Increment `i` to point to the next element in the tree +ZIX_API +ZixStatus +zix_btree_iter_increment(ZixBTreeIter* ZIX_NONNULL i); + +/// Return an iterator one past `iter` +ZIX_API +ZixBTreeIter +zix_btree_iter_next(ZixBTreeIter iter); + +/** + @} + @defgroup zix_btree_modification Modification + @{ +*/ + +/** + Insert the element `e` into `t`. + + @return #ZIX_STATUS_SUCCESS on success, #ZIX_STATUS_EXISTS, or + #ZIX_STATUS_NO_MEM. +*/ ZIX_API ZixStatus zix_btree_insert(ZixBTree* ZIX_NONNULL t, void* ZIX_UNSPECIFIED e); /** - Remove the value `e` from `t`. + Remove the element `e` from `t`. @param t Tree to remove from. @@ -135,8 +195,10 @@ zix_btree_insert(ZixBTree* ZIX_NONNULL t, void* ZIX_UNSPECIFIED e); @param out Set to point to the removed pointer (which may not equal `e`). - @param next On successful return, set to point at the value that immediately - followed `e`. + @param next On successful return, set to point at element immediately + following `e`. + + @return #ZIX_STATUS_SUCCESS on success, or #ZIX_STATUS_NOT_FOUND. */ ZIX_API ZixStatus @@ -146,9 +208,17 @@ zix_btree_remove(ZixBTree* ZIX_NONNULL t, ZixBTreeIter* ZIX_NONNULL next); /** + @} + @defgroup zix_btree_searching Searching + @{ +*/ + +/** Set `ti` to an element exactly equal to `e` in `t`. If no such item exists, `ti` is set to the end. + + @return #ZIX_STATUS_SUCCESS on success, or #ZIX_STATUS_NOT_FOUND. */ ZIX_API ZixStatus @@ -169,54 +239,20 @@ zix_btree_find(const ZixBTree* ZIX_NONNULL t, The comparator is always called with an actual value in the tree as the first argument, and `key` as the second argument. + + @return #ZIX_STATUS_SUCCESS. */ ZIX_API ZixStatus zix_btree_lower_bound(const ZixBTree* ZIX_NONNULL t, ZixBTreeCompareFunc ZIX_NULLABLE compare_key, - const void* ZIX_NULLABLE compare_key_user_data, + const void* ZIX_NULLABLE compare_key_data, const void* ZIX_UNSPECIFIED key, ZixBTreeIter* ZIX_NONNULL ti); -/// Return the data at the given position in the tree -ZIX_PURE_API -void* ZIX_UNSPECIFIED -zix_btree_get(ZixBTreeIter ti); - -/// Return an iterator to the first (smallest) element in `t` -ZIX_PURE_API -ZixBTreeIter -zix_btree_begin(const ZixBTree* ZIX_NONNULL t); - -/// Return an iterator to the end of `t` (one past the last element) -ZIX_CONST_API -ZixBTreeIter -zix_btree_end(const ZixBTree* ZIX_NULLABLE t); - -/// Return true iff `lhs` is equal to `rhs` -ZIX_CONST_API -bool -zix_btree_iter_equals(ZixBTreeIter lhs, ZixBTreeIter rhs); - -/// Return true iff `i` is an iterator at the end of a tree -static inline bool -zix_btree_iter_is_end(const ZixBTreeIter i) -{ - return i.level == 0 && !i.nodes[0]; -} - -/// Increment `i` to point to the next element in the tree -ZIX_API -ZixStatus -zix_btree_iter_increment(ZixBTreeIter* ZIX_NONNULL i); - -/// Return an iterator one past `iter` -ZIX_API -ZixBTreeIter -zix_btree_iter_next(ZixBTreeIter iter); - /** @} + @} */ ZIX_END_DECLS diff --git a/include/zix/hash.h b/include/zix/hash.h index 026662c..e425b9f 100644 --- a/include/zix/hash.h +++ b/include/zix/hash.h @@ -19,6 +19,11 @@ ZIX_BEGIN_DECLS @{ */ +/** + @defgroup zix_hash_datatypes Datatypes + @{ +*/ + // ZIX_HASH_KEY_TYPE can be defined to make the API more type-safe #if defined(ZIX_HASH_KEY_TYPE) typedef ZIX_HASH_KEY_TYPE ZixHashKey; @@ -73,12 +78,14 @@ typedef struct ZixHashImpl ZixHash; typedef size_t ZixHashCode; /** - An iterator to an entry in a hash table. - - This is really just an index, but should be considered opaque to the user - and only used via the provided API and equality comparison. + @} + @defgroup zix_hash_setup Setup + @{ */ -typedef size_t ZixHashIter; + +/// User function for getting the key of a record +typedef const ZixHashKey* ZIX_NONNULL (*ZixKeyFunc)( + const ZixHashRecord* ZIX_NONNULL record); /// User function for computing the hash of a key typedef ZixHashCode (*ZixHashFunc)(const ZixHashKey* ZIX_NONNULL key); @@ -87,28 +94,6 @@ typedef ZixHashCode (*ZixHashFunc)(const ZixHashKey* ZIX_NONNULL key); typedef bool (*ZixKeyEqualFunc)(const ZixHashKey* ZIX_NONNULL a, const ZixHashKey* ZIX_NONNULL b); -/// User function for determining if a key matches in a custom search -typedef bool (*ZixKeyMatchFunc)(const ZixHashKey* ZIX_NONNULL key, - const ZixHashSearchData* ZIX_NULLABLE - user_data); - -/// User function for getting the key of a record -typedef const ZixHashKey* ZIX_NONNULL (*ZixKeyFunc)( - const ZixHashRecord* ZIX_NONNULL record); - -/** - A "plan" (position) to insert a record in a hash table. - - This contains everything necessary to insert a record, except the record - itself. It is exposed to split up insertion so that records only need to be - allocated if an existing record is not found, but the contents should be - considered opaque to the user. -*/ -typedef struct { - ZixHashCode code; ///< Hash code used to find this position - ZixHashIter index; ///< Index into hash table -} ZixHashInsertPlan; - /** Create a new hash table. @@ -129,6 +114,25 @@ ZIX_API void zix_hash_free(ZixHash* ZIX_NULLABLE hash); +/// Return the number of elements in the hash +ZIX_PURE_API +size_t +zix_hash_size(const ZixHash* ZIX_NONNULL hash); + +/** + @} + @defgroup zix_hash_iteration Iteration + @{ +*/ + +/** + An iterator to an entry in a hash table. + + This is really just an index, but should be considered opaque to the user + and only used via the provided API and equality comparison. +*/ +typedef size_t ZixHashIter; + /// Return an iterator to the first record in a hash, or the end if it is empty ZIX_PURE_API ZixHashIter @@ -149,10 +153,29 @@ ZIX_PURE_API ZixHashIter zix_hash_next(const ZixHash* ZIX_NONNULL hash, ZixHashIter i); -/// Return the number of elements in a hash -ZIX_PURE_API -size_t -zix_hash_size(const ZixHash* ZIX_NONNULL hash); +/** + @} + @defgroup zix_hash_modification Modification + @{ +*/ + +/// User function for determining if a key matches in a custom search +typedef bool (*ZixKeyMatchFunc)(const ZixHashKey* ZIX_NONNULL key, + const ZixHashSearchData* ZIX_NULLABLE + user_data); + +/** + A "plan" (position) to insert a record in a hash table. + + This contains everything necessary to insert a record, except the record + itself. It is exposed to split up insertion so that records only need to be + allocated if an existing record is not found, but the contents should be + considered opaque to the user. +*/ +typedef struct { + ZixHashCode code; ///< Hash code used to find this position + ZixHashIter index; ///< Index into hash table +} ZixHashInsertPlan; /** Find the best position to insert a record with the given key. @@ -284,6 +307,12 @@ zix_hash_remove(ZixHash* ZIX_NONNULL hash, ZixHashRecord* ZIX_NULLABLE* ZIX_NONNULL removed); /** + @} + @defgroup zix_hash_searching Searching + @{ +*/ + +/** Find the position of a record with a given key. @param hash The hash table to search. @@ -317,6 +346,7 @@ zix_hash_find_record(const ZixHash* ZIX_NONNULL hash, /** @} + @} */ ZIX_END_DECLS diff --git a/include/zix/ring.h b/include/zix/ring.h index 181a7a3..61c99be 100644 --- a/include/zix/ring.h +++ b/include/zix/ring.h @@ -19,7 +19,7 @@ ZIX_BEGIN_DECLS */ /** - @defgroup zix_ring_definition Definition + @defgroup zix_ring_setup Setup @{ */ diff --git a/include/zix/thread.h b/include/zix/thread.h index d3b5021..2493ed3 100644 --- a/include/zix/thread.h +++ b/include/zix/thread.h @@ -59,6 +59,8 @@ typedef ZixThreadResult(ZIX_THREAD_FUNC* ZixThreadFunc)(void*); The thread will immediately be launched, calling `function` with `arg` as the only parameter. + + @return #ZIX_STATUS_SUCCESS on success, or #ZIX_STATUS_ERROR. */ ZIX_API ZixStatus @@ -67,7 +69,11 @@ zix_thread_create(ZixThread* thread, ZixThreadFunc function, void* arg); -/// Join `thread` (block until `thread` exits) +/** + Join `thread` (block until `thread` exits). + + @return #ZIX_STATUS_SUCCESS on success, or #ZIX_STATUS_ERROR. +*/ ZIX_API ZixStatus zix_thread_join(ZixThread thread); diff --git a/include/zix/tree.h b/include/zix/tree.h index 1b5c4ec..0ad37f2 100644 --- a/include/zix/tree.h +++ b/include/zix/tree.h @@ -19,12 +19,14 @@ ZIX_BEGIN_DECLS @{ */ +/** + @defgroup zix_tree_setup Setup + @{ +*/ + /// A balanced binary search tree typedef struct ZixTreeImpl ZixTree; -/// An iterator over a @ref ZixTree -typedef struct ZixTreeNodeImpl ZixTreeIter; - /// Function for comparing two Tree elements typedef int (*ZixTreeCompareFunc)(const void* ZIX_UNSPECIFIED a, const void* ZIX_UNSPECIFIED b, @@ -54,28 +56,14 @@ ZIX_PURE_API size_t zix_tree_size(const ZixTree* ZIX_NONNULL t); -/// Insert the element `e` into `t` and point `ti` at the new element -ZIX_API -ZixStatus -zix_tree_insert(ZixTree* ZIX_NONNULL t, - void* ZIX_UNSPECIFIED e, - ZixTreeIter* ZIX_NULLABLE* ZIX_NULLABLE ti); - -/// Remove the item pointed at by `ti` from `t` -ZIX_API -ZixStatus -zix_tree_remove(ZixTree* ZIX_NONNULL t, ZixTreeIter* ZIX_NONNULL ti); - /** - Set `ti` to an element equal to `e` in `t`. - - If no such item exists, `ti` is set to NULL. + @} + @defgroup zix_tree_iteration Iteration + @{ */ -ZIX_API -ZixStatus -zix_tree_find(const ZixTree* ZIX_NONNULL t, - const void* ZIX_UNSPECIFIED e, - ZixTreeIter* ZIX_NULLABLE* ZIX_NONNULL ti); + +/// An iterator over a @ref ZixTree +typedef struct ZixTreeNodeImpl ZixTreeIter; /// Return the data associated with the given tree item ZIX_PURE_API @@ -124,6 +112,42 @@ zix_tree_iter_prev(ZixTreeIter* ZIX_NULLABLE i); /** @} + @defgroup zix_tree_modification Modification + @{ +*/ + +/// Insert the element `e` into `t` and point `ti` at the new element +ZIX_API +ZixStatus +zix_tree_insert(ZixTree* ZIX_NONNULL t, + void* ZIX_UNSPECIFIED e, + ZixTreeIter* ZIX_NULLABLE* ZIX_NULLABLE ti); + +/// Remove the item pointed at by `ti` from `t` +ZIX_API +ZixStatus +zix_tree_remove(ZixTree* ZIX_NONNULL t, ZixTreeIter* ZIX_NONNULL ti); + +/** + @} + @defgroup zix_tree_searching Searching + @{ +*/ + +/** + 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* ZIX_NONNULL t, + const void* ZIX_UNSPECIFIED e, + ZixTreeIter* ZIX_NULLABLE* ZIX_NONNULL ti); + +/** + @} + @} */ ZIX_END_DECLS |