diff options
| -rw-r--r-- | include/zix/allocator.h | 87 | ||||
| -rw-r--r-- | include/zix/btree.h | 2 | ||||
| -rw-r--r-- | include/zix/hash.h | 8 | ||||
| -rw-r--r-- | include/zix/ring.h | 2 | ||||
| -rw-r--r-- | include/zix/tree.h | 12 | ||||
| -rw-r--r-- | src/allocator.c | 29 | ||||
| -rw-r--r-- | src/btree.c | 26 | ||||
| -rw-r--r-- | src/hash.c | 24 | ||||
| -rw-r--r-- | src/ring.c | 14 | ||||
| -rw-r--r-- | src/tree.c | 28 | ||||
| -rw-r--r-- | test/allocator_test.c | 2 | ||||
| -rw-r--r-- | test/failing_allocator.c | 68 | ||||
| -rw-r--r-- | test/failing_allocator.h | 11 | ||||
| -rw-r--r-- | test/ring_test.c | 11 |
14 files changed, 162 insertions, 162 deletions
diff --git a/include/zix/allocator.h b/include/zix/allocator.h index 55bbe9b..aa7d820 100644 --- a/include/zix/allocator.h +++ b/include/zix/allocator.h @@ -19,8 +19,16 @@ extern "C" { @{ */ -/// Opaque user data for allocation functions -typedef void ZixAllocatorHandle; +/** + A memory allocator. + + This object-like structure provides an interface like the standard C + functions malloc(), calloc(), realloc(), and free(). It contains function + pointers that differ from their standard counterparts by taking a context + parameter (a pointer to this struct), which allows the user to implement + custom stateful allocators. +*/ +typedef struct ZixAllocatorImpl ZixAllocator; /** General malloc-like memory allocation function. @@ -29,7 +37,7 @@ typedef void ZixAllocatorHandle; parameter for implementing stateful allocators without static data. */ typedef void* ZIX_ALLOCATED ( - *ZixMallocFunc)(ZixAllocatorHandle* ZIX_NULLABLE handle, size_t size); + *ZixMallocFunc)(ZixAllocator* ZIX_NULLABLE allocator, size_t size); /** General calloc-like memory allocation function. @@ -37,8 +45,8 @@ typedef void* ZIX_ALLOCATED ( This works like the standard C calloc(), except has an additional handle parameter for implementing stateful allocators without static data. */ -typedef void* ZIX_ALLOCATED (*ZixCallocFunc)(ZixAllocatorHandle* ZIX_NULLABLE - handle, +typedef void* ZIX_ALLOCATED (*ZixCallocFunc)(ZixAllocator* ZIX_NULLABLE + allocator, size_t nmemb, size_t size); @@ -48,8 +56,8 @@ typedef void* ZIX_ALLOCATED (*ZixCallocFunc)(ZixAllocatorHandle* ZIX_NULLABLE This works like the standard C remalloc(), except has an additional handle parameter for implementing stateful allocators without static data. */ -typedef void* ZIX_ALLOCATED (*ZixReallocFunc)(ZixAllocatorHandle* ZIX_NULLABLE - handle, +typedef void* ZIX_ALLOCATED (*ZixReallocFunc)(ZixAllocator* ZIX_NULLABLE + allocator, void* ZIX_NULLABLE ptr, size_t size); @@ -59,72 +67,61 @@ typedef void* ZIX_ALLOCATED (*ZixReallocFunc)(ZixAllocatorHandle* ZIX_NULLABLE This works like the standard C remalloc(), except has an additional handle parameter for implementing stateful allocators without static data. */ -typedef void (*ZixFreeFunc)(ZixAllocatorHandle* ZIX_NULLABLE handle, - void* ZIX_NULLABLE ptr); +typedef void (*ZixFreeFunc)(ZixAllocator* ZIX_NULLABLE allocator, + void* ZIX_NULLABLE ptr); -/** - A memory allocator. - - This object-like structure provides an interface like the standard C - functions malloc(), calloc(), realloc(), and free(). It allows the user to - pass a custom allocator to be used by data structures. -*/ -typedef struct { - ZixAllocatorHandle* ZIX_NULLABLE handle; - ZixMallocFunc ZIX_NONNULL malloc; - ZixCallocFunc ZIX_NONNULL calloc; - ZixReallocFunc ZIX_NONNULL realloc; - ZixFreeFunc ZIX_NONNULL free; -} ZixAllocator; +/// Definition of ZixAllocator +struct ZixAllocatorImpl { + ZixMallocFunc ZIX_NONNULL malloc; + ZixCallocFunc ZIX_NONNULL calloc; + ZixReallocFunc ZIX_NONNULL realloc; + ZixFreeFunc ZIX_NONNULL free; +}; /// Return the default allocator which simply uses the system allocator ZIX_CONST_API -const ZixAllocator* ZIX_NONNULL +ZixAllocator* ZIX_NONNULL zix_default_allocator(void); /// Convenience wrapper that defers to malloc() if allocator is null static inline void* ZIX_ALLOCATED -zix_malloc(const ZixAllocator* const ZIX_NULLABLE allocator, const size_t size) +zix_malloc(ZixAllocator* const ZIX_NULLABLE allocator, const size_t size) { - const ZixAllocator* const actual = - allocator ? allocator : zix_default_allocator(); + ZixAllocator* const actual = allocator ? allocator : zix_default_allocator(); - return actual->malloc(actual->handle, size); + return actual->malloc(actual, size); } /// Convenience wrapper that defers to calloc() if allocator is null static inline void* ZIX_ALLOCATED -zix_calloc(const ZixAllocator* const ZIX_NULLABLE allocator, - const size_t nmemb, - const size_t size) +zix_calloc(ZixAllocator* const ZIX_NULLABLE allocator, + const size_t nmemb, + const size_t size) { - const ZixAllocator* const actual = - allocator ? allocator : zix_default_allocator(); + ZixAllocator* const actual = allocator ? allocator : zix_default_allocator(); - return actual->calloc(actual->handle, nmemb, size); + return actual->calloc(actual, nmemb, size); } /// Convenience wrapper that defers to realloc() if allocator is null static inline void* ZIX_ALLOCATED -zix_realloc(const ZixAllocator* const ZIX_NULLABLE allocator, - void* const ZIX_NULLABLE ptr, - const size_t size) +zix_realloc(ZixAllocator* const ZIX_NULLABLE allocator, + void* const ZIX_NULLABLE ptr, + const size_t size) { - const ZixAllocator* const actual = - allocator ? allocator : zix_default_allocator(); + ZixAllocator* const actual = allocator ? allocator : zix_default_allocator(); - return actual->realloc(actual->handle, ptr, size); + return actual->realloc(actual, ptr, size); } /// Convenience wrapper that defers to free() if allocator is null static inline void -zix_free(const ZixAllocator* const ZIX_NULLABLE allocator, - void* const ZIX_NULLABLE ptr) +zix_free(ZixAllocator* const ZIX_NULLABLE allocator, + void* const ZIX_NULLABLE ptr) { - const ZixAllocator* const actual = - allocator ? allocator : zix_default_allocator(); + ZixAllocator* const actual = allocator ? allocator : zix_default_allocator(); - actual->free(actual->handle, ptr); + actual->free(actual, ptr); } /** diff --git a/include/zix/btree.h b/include/zix/btree.h index 9a661d6..9c86a44 100644 --- a/include/zix/btree.h +++ b/include/zix/btree.h @@ -76,7 +76,7 @@ static const ZixBTreeIter zix_btree_end_iter = { */ ZIX_API ZixBTree* ZIX_ALLOCATED -zix_btree_new(const ZixAllocator* ZIX_NULLABLE allocator, +zix_btree_new(ZixAllocator* ZIX_NULLABLE allocator, ZixComparator ZIX_NONNULL cmp, const void* ZIX_NULLABLE cmp_data); diff --git a/include/zix/hash.h b/include/zix/hash.h index 7ec9f92..9716123 100644 --- a/include/zix/hash.h +++ b/include/zix/hash.h @@ -121,10 +121,10 @@ typedef struct { */ ZIX_API ZixHash* ZIX_ALLOCATED -zix_hash_new(const ZixAllocator* ZIX_NULLABLE allocator, - ZixKeyFunc ZIX_NONNULL key_func, - ZixHashFunc ZIX_NONNULL hash_func, - ZixKeyEqualFunc ZIX_NONNULL equal_func); +zix_hash_new(ZixAllocator* ZIX_NULLABLE allocator, + ZixKeyFunc ZIX_NONNULL key_func, + ZixHashFunc ZIX_NONNULL hash_func, + ZixKeyEqualFunc ZIX_NONNULL equal_func); /// Free `hash` ZIX_API diff --git a/include/zix/ring.h b/include/zix/ring.h index a060697..d7d9713 100644 --- a/include/zix/ring.h +++ b/include/zix/ring.h @@ -36,7 +36,7 @@ typedef struct ZixRingImpl ZixRing; */ ZIX_MALLOC_API ZixRing* ZIX_ALLOCATED -zix_ring_new(const ZixAllocator* ZIX_NULLABLE allocator, uint32_t size); +zix_ring_new(ZixAllocator* ZIX_NULLABLE allocator, uint32_t size); /// Destroy a ring ZIX_API diff --git a/include/zix/tree.h b/include/zix/tree.h index aaa0f25..53cb375 100644 --- a/include/zix/tree.h +++ b/include/zix/tree.h @@ -31,12 +31,12 @@ typedef struct ZixTreeNodeImpl ZixTreeIter; /// Create a new (empty) tree ZIX_API ZixTree* ZIX_ALLOCATED -zix_tree_new(const ZixAllocator* ZIX_NULLABLE allocator, - bool allow_duplicates, - ZixComparator ZIX_NONNULL cmp, - void* ZIX_NULLABLE cmp_data, - ZixDestroyFunc ZIX_NULLABLE destroy, - const void* ZIX_NULLABLE destroy_user_data); +zix_tree_new(ZixAllocator* ZIX_NULLABLE allocator, + bool allow_duplicates, + ZixComparator ZIX_NONNULL cmp, + void* ZIX_NULLABLE cmp_data, + ZixDestroyFunc ZIX_NULLABLE destroy, + const void* ZIX_NULLABLE destroy_user_data); /// Free `t` ZIX_API diff --git a/src/allocator.c b/src/allocator.c index e4a9f83..c998463 100644 --- a/src/allocator.c +++ b/src/allocator.c @@ -7,43 +7,42 @@ ZIX_MALLOC_FUNC static void* -zix_default_malloc(ZixAllocatorHandle* const handle, const size_t size) +zix_default_malloc(ZixAllocator* const allocator, const size_t size) { - (void)handle; + (void)allocator; return malloc(size); } ZIX_MALLOC_FUNC static void* -zix_default_calloc(ZixAllocatorHandle* const handle, - const size_t nmemb, - const size_t size) +zix_default_calloc(ZixAllocator* const allocator, + const size_t nmemb, + const size_t size) { - (void)handle; + (void)allocator; return calloc(nmemb, size); } static void* -zix_default_realloc(ZixAllocatorHandle* const handle, - void* const ptr, - const size_t size) +zix_default_realloc(ZixAllocator* const allocator, + void* const ptr, + const size_t size) { - (void)handle; + (void)allocator; return realloc(ptr, size); } static void -zix_default_free(ZixAllocatorHandle* const handle, void* const ptr) +zix_default_free(ZixAllocator* const allocator, void* const ptr) { - (void)handle; + (void)allocator; free(ptr); } -const ZixAllocator* +ZixAllocator* zix_default_allocator(void) { - static const ZixAllocator default_allocator = { - NULL, + static ZixAllocator default_allocator = { zix_default_malloc, zix_default_calloc, zix_default_realloc, diff --git a/src/btree.c b/src/btree.c index a73a2d0..869b98a 100644 --- a/src/btree.c +++ b/src/btree.c @@ -25,11 +25,11 @@ typedef uint16_t ZixShort; #define ZIX_BTREE_INODE_VALS (ZIX_BTREE_LEAF_VALS / 2u) struct ZixBTreeImpl { - const ZixAllocator* allocator; - ZixBTreeNode* root; - ZixComparator cmp; - const void* cmp_data; - size_t size; + ZixAllocator* allocator; + ZixBTreeNode* root; + ZixComparator cmp; + const void* cmp_data; + size_t size; }; struct ZixBTreeNodeImpl { @@ -57,7 +57,7 @@ static_assert(sizeof(ZixBTreeNode) >= #endif static ZixBTreeNode* -zix_btree_node_new(const ZixAllocator* const allocator, const bool leaf) +zix_btree_node_new(ZixAllocator* const allocator, const bool leaf) { #if !((defined(__STDC_VERSION__) && __STDC_VERSION__ >= 201112l) || \ (defined(__cplusplus) && __cplusplus >= 201103L)) @@ -87,9 +87,9 @@ zix_btree_child(const ZixBTreeNode* const node, const unsigned i) } ZixBTree* -zix_btree_new(const ZixAllocator* const allocator, - const ZixComparator cmp, - const void* const cmp_data) +zix_btree_new(ZixAllocator* const allocator, + const ZixComparator cmp, + const void* const cmp_data) { assert(cmp); @@ -203,10 +203,10 @@ zix_btree_aerase(void** const array, const unsigned n, const unsigned i) /// Split lhs, the i'th child of `n`, into two nodes static ZixBTreeNode* -zix_btree_split_child(const ZixAllocator* const allocator, - ZixBTreeNode* const n, - const unsigned i, - ZixBTreeNode* const lhs) +zix_btree_split_child(ZixAllocator* const allocator, + 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); @@ -13,24 +13,24 @@ typedef struct ZixHashEntry { } ZixHashEntry; struct ZixHashImpl { - const ZixAllocator* allocator; ///< User allocator - ZixKeyFunc key_func; ///< User key accessor - ZixHashFunc hash_func; ///< User hashing function - ZixKeyEqualFunc equal_func; ///< User equality comparison function - size_t count; ///< Number of records stored in the table - size_t mask; ///< Bit mask for fast modulo (n_entries - 1) - size_t n_entries; ///< Power of two table size - ZixHashEntry* entries; ///< Pointer to dynamically allocated table + ZixAllocator* allocator; ///< User allocator + ZixKeyFunc key_func; ///< User key accessor + ZixHashFunc hash_func; ///< User hashing function + ZixKeyEqualFunc equal_func; ///< User equality comparison function + size_t count; ///< Number of records stored in the table + size_t mask; ///< Bit mask for fast modulo (n_entries - 1) + size_t n_entries; ///< Power of two table size + ZixHashEntry* entries; ///< Pointer to dynamically allocated table }; static const size_t min_n_entries = 4u; static const size_t tombstone = 0xDEADu; ZixHash* -zix_hash_new(const ZixAllocator* const allocator, - const ZixKeyFunc key_func, - const ZixHashFunc hash_func, - const ZixKeyEqualFunc equal_func) +zix_hash_new(ZixAllocator* const allocator, + const ZixKeyFunc key_func, + const ZixHashFunc hash_func, + const ZixKeyEqualFunc equal_func) { assert(key_func); assert(hash_func); @@ -31,12 +31,12 @@ #endif struct ZixRingImpl { - const ZixAllocator* allocator; ///< User allocator - 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 + ZixAllocator* allocator; ///< User allocator + 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 @@ -54,7 +54,7 @@ next_power_of_two(uint32_t size) } ZixRing* -zix_ring_new(const ZixAllocator* const allocator, uint32_t size) +zix_ring_new(ZixAllocator* const allocator, uint32_t size) { ZixRing* ring = (ZixRing*)zix_malloc(allocator, sizeof(ZixRing)); @@ -11,14 +11,14 @@ typedef struct ZixTreeNodeImpl ZixTreeNode; struct ZixTreeImpl { - const ZixAllocator* allocator; - ZixTreeNode* root; - ZixDestroyFunc destroy; - const void* destroy_user_data; - ZixComparator cmp; - void* cmp_data; - size_t size; - bool allow_duplicates; + ZixAllocator* allocator; + ZixTreeNode* root; + ZixDestroyFunc destroy; + const void* destroy_user_data; + ZixComparator cmp; + void* cmp_data; + size_t size; + bool allow_duplicates; }; struct ZixTreeNodeImpl { @@ -54,12 +54,12 @@ struct ZixTreeNodeImpl { #endif ZixTree* -zix_tree_new(const ZixAllocator* const allocator, - bool allow_duplicates, - ZixComparator cmp, - void* cmp_data, - ZixDestroyFunc destroy, - const void* destroy_user_data) +zix_tree_new(ZixAllocator* const allocator, + bool allow_duplicates, + ZixComparator cmp, + void* cmp_data, + ZixDestroyFunc destroy, + const void* destroy_user_data) { ZixTree* t = (ZixTree*)zix_malloc(allocator, sizeof(ZixTree)); diff --git a/test/allocator_test.c b/test/allocator_test.c index 6850bdc..a6087e1 100644 --- a/test/allocator_test.c +++ b/test/allocator_test.c @@ -12,7 +12,7 @@ test_allocator(void) { // Just a basic smoke test to check that things seem to be working - const ZixAllocator* const allocator = zix_default_allocator(); + ZixAllocator* const allocator = zix_default_allocator(); char* const malloced = (char*)zix_malloc(allocator, 4); malloced[0] = 0; diff --git a/test/failing_allocator.c b/test/failing_allocator.c index d00f2f1..eda762b 100644 --- a/test/failing_allocator.c +++ b/test/failing_allocator.c @@ -8,73 +8,77 @@ #include <stdbool.h> #include <stddef.h> +#include <stdint.h> static bool -attempt(ZixFailingAllocatorState* const state) +attempt(ZixFailingAllocator* const allocator) { - ++state->n_allocations; + ++allocator->n_allocations; - if (!state->n_remaining) { + if (!allocator->n_remaining) { return false; } - --state->n_remaining; + --allocator->n_remaining; return true; } ZIX_MALLOC_FUNC static void* -zix_failing_malloc(ZixAllocatorHandle* const handle, const size_t size) +zix_failing_malloc(ZixAllocator* const allocator, const size_t size) { - ZixFailingAllocatorState* const state = (ZixFailingAllocatorState*)handle; - const ZixAllocator* const base = zix_default_allocator(); + ZixFailingAllocator* const state = (ZixFailingAllocator*)allocator; + ZixAllocator* const base = zix_default_allocator(); - return attempt(state) ? base->malloc(base->handle, size) : NULL; + return attempt(state) ? base->malloc(base, size) : NULL; } ZIX_MALLOC_FUNC static void* -zix_failing_calloc(ZixAllocatorHandle* const handle, - const size_t nmemb, - const size_t size) +zix_failing_calloc(ZixAllocator* const allocator, + const size_t nmemb, + const size_t size) { - ZixFailingAllocatorState* const state = (ZixFailingAllocatorState*)handle; - const ZixAllocator* const base = zix_default_allocator(); + ZixFailingAllocator* const state = (ZixFailingAllocator*)allocator; + ZixAllocator* const base = zix_default_allocator(); - return attempt(state) ? base->calloc(base->handle, nmemb, size) : NULL; + return attempt(state) ? base->calloc(base, nmemb, size) : NULL; } static void* -zix_failing_realloc(ZixAllocatorHandle* const handle, - void* const ptr, - const size_t size) +zix_failing_realloc(ZixAllocator* const allocator, + void* const ptr, + const size_t size) { - ZixFailingAllocatorState* const state = (ZixFailingAllocatorState*)handle; - const ZixAllocator* const base = zix_default_allocator(); + ZixFailingAllocator* const state = (ZixFailingAllocator*)allocator; + ZixAllocator* const base = zix_default_allocator(); - return attempt(state) ? base->realloc(base->handle, ptr, size) : NULL; + return attempt(state) ? base->realloc(base, ptr, size) : NULL; } static void -zix_failing_free(ZixAllocatorHandle* const handle, void* const ptr) +zix_failing_free(ZixAllocator* const allocator, void* const ptr) { - (void)handle; + (void)allocator; - const ZixAllocator* const base = zix_default_allocator(); + ZixAllocator* const base = zix_default_allocator(); - base->free(base->handle, ptr); + base->free(base, ptr); } ZIX_CONST_FUNC -ZixAllocator -zix_failing_allocator(ZixFailingAllocatorState* const state) +ZixFailingAllocator +zix_failing_allocator(void) { - const ZixAllocator failing_allocator = { - state, - zix_failing_malloc, - zix_failing_calloc, - zix_failing_realloc, - zix_failing_free, + ZixFailingAllocator failing_allocator = { + { + zix_failing_malloc, + zix_failing_calloc, + zix_failing_realloc, + zix_failing_free, + }, + 0, + SIZE_MAX, }; return failing_allocator; diff --git a/test/failing_allocator.h b/test/failing_allocator.h index 89bee88..982874d 100644 --- a/test/failing_allocator.h +++ b/test/failing_allocator.h @@ -10,11 +10,12 @@ /// An allocator that fails after some number of successes for testing typedef struct { - size_t n_allocations; ///< The number of allocations that have been attempted - size_t n_remaining; ///< The number of remaining successful allocations -} ZixFailingAllocatorState; + ZixAllocator base; ///< Base allocator instance + size_t n_allocations; ///< Number of attempted allocations + size_t n_remaining; ///< Number of remaining successful allocations +} ZixFailingAllocator; -ZixAllocator -zix_failing_allocator(ZixFailingAllocatorState* state); +ZixFailingAllocator +zix_failing_allocator(void); #endif // ZIX_FAILING_ALLOCATOR_H diff --git a/test/ring_test.c b/test/ring_test.c index b4fa5f1..ba2a4d1 100644 --- a/test/ring_test.c +++ b/test/ring_test.c @@ -161,18 +161,17 @@ test_ring(const unsigned size) static void test_failed_alloc(void) { - ZixFailingAllocatorState state = {0u, SIZE_MAX}; - ZixAllocator allocator = zix_failing_allocator(&state); + ZixFailingAllocator allocator = zix_failing_allocator(); // Successfully allocate a ring to count the number of allocations - ring = zix_ring_new(&allocator, 512); + ring = zix_ring_new(&allocator.base, 512); assert(ring); // Test that each allocation failing is handled gracefully - const size_t n_new_allocs = state.n_allocations; + const size_t n_new_allocs = allocator.n_allocations; for (size_t i = 0u; i < n_new_allocs; ++i) { - state.n_remaining = i; - assert(!zix_ring_new(&allocator, 512)); + allocator.n_remaining = i; + assert(!zix_ring_new(&allocator.base, 512)); } zix_ring_free(ring); |