diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/allocator.c | 67 | ||||
| -rw-r--r-- | src/btree.c | 60 | ||||
| -rw-r--r-- | src/hash.c | 42 | ||||
| -rw-r--r-- | src/ring.c | 38 | ||||
| -rw-r--r-- | src/tree.c | 59 |
5 files changed, 182 insertions, 84 deletions
diff --git a/src/allocator.c b/src/allocator.c new file mode 100644 index 0000000..ccd48ea --- /dev/null +++ b/src/allocator.c @@ -0,0 +1,67 @@ +/* + 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 + copyright notice and this permission notice appear in all copies. + + THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. +*/ + +#include "zix/allocator.h" + +#include <stdlib.h> + +ZIX_MALLOC_FUNC +static void* +zix_default_malloc(ZixAllocatorHandle* const handle, const size_t size) +{ + (void)handle; + return malloc(size); +} + +ZIX_MALLOC_FUNC +static void* +zix_default_calloc(ZixAllocatorHandle* const handle, + const size_t nmemb, + const size_t size) +{ + (void)handle; + return calloc(nmemb, size); +} + +static void* +zix_default_realloc(ZixAllocatorHandle* const handle, + void* const ptr, + const size_t size) +{ + (void)handle; + return realloc(ptr, size); +} + +static void +zix_default_free(ZixAllocatorHandle* const handle, void* const ptr) +{ + (void)handle; + free(ptr); +} + +const ZixAllocator* +zix_default_allocator(void) +{ + static const ZixAllocator default_allocator = { + NULL, + zix_default_malloc, + zix_default_calloc, + zix_default_realloc, + zix_default_free, + }; + + return &default_allocator; +} diff --git a/src/btree.c b/src/btree.c index 7d967b8..b74eb92 100644 --- a/src/btree.c +++ b/src/btree.c @@ -18,7 +18,6 @@ #include <assert.h> #include <stdint.h> -#include <stdlib.h> #include <string.h> // #define ZIX_BTREE_SORTED_CHECK 1 @@ -39,10 +38,11 @@ typedef uint16_t ZixShort; #define ZIX_BTREE_INODE_VALS (ZIX_BTREE_LEAF_VALS / 2u) struct ZixBTreeImpl { - ZixBTreeNode* root; - ZixComparator cmp; - const void* cmp_data; - size_t size; + const ZixAllocator* allocator; + ZixBTreeNode* root; + ZixComparator cmp; + const void* cmp_data; + size_t size; }; struct ZixBTreeNodeImpl { @@ -67,7 +67,7 @@ static_assert(sizeof(ZixBTreeNode) == ZIX_BTREE_PAGE_SIZE, ""); #endif static ZixBTreeNode* -zix_btree_node_new(const bool leaf) +zix_btree_node_new(const ZixAllocator* const allocator, const bool leaf) { #if !((defined(__STDC_VERSION__) && __STDC_VERSION__ >= 201112l) || \ (defined(__cplusplus) && __cplusplus >= 201103L)) @@ -76,7 +76,9 @@ zix_btree_node_new(const bool leaf) ZIX_BTREE_PAGE_SIZE - 2u * sizeof(ZixBTreeNode*)); #endif - ZixBTreeNode* const node = (ZixBTreeNode*)malloc(sizeof(ZixBTreeNode)); + ZixBTreeNode* const node = + (ZixBTreeNode*)zix_malloc(allocator, sizeof(ZixBTreeNode)); + if (node) { node->is_leaf = leaf; node->n_vals = 0u; @@ -95,23 +97,26 @@ zix_btree_child(const ZixBTreeNode* const node, const unsigned i) } ZixBTree* -zix_btree_new(const ZixComparator cmp, const void* const cmp_data) +zix_btree_new(const ZixAllocator* const allocator, + const ZixComparator cmp, + const void* const cmp_data) { assert(cmp); - ZixBTree* const t = (ZixBTree*)malloc(sizeof(ZixBTree)); + ZixBTree* const t = (ZixBTree*)zix_malloc(allocator, sizeof(ZixBTree)); if (!t) { return NULL; } - if (!(t->root = zix_btree_node_new(true))) { - free(t); + if (!(t->root = zix_btree_node_new(allocator, true))) { + zix_free(allocator, t); return NULL; } - t->cmp = cmp; - t->cmp_data = cmp_data; - t->size = 0; + t->allocator = allocator; + t->cmp = cmp; + t->cmp_data = cmp_data; + t->size = 0; return t; } @@ -126,7 +131,7 @@ zix_btree_free_children(ZixBTree* const t, for (ZixShort i = 0; i < n->n_vals + 1u; ++i) { zix_btree_free_children( t, zix_btree_child(n, i), destroy, destroy_user_data); - free(zix_btree_child(n, i)); + zix_free(t->allocator, zix_btree_child(n, i)); } } @@ -150,8 +155,8 @@ zix_btree_free(ZixBTree* const t, { if (t) { zix_btree_clear(t, destroy, destroy_user_data); - free(t->root); - free(t); + zix_free(t->allocator, t->root); + zix_free(t->allocator, t); } } @@ -208,9 +213,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(ZixBTreeNode* const n, - const unsigned i, - ZixBTreeNode* const lhs) +zix_btree_split_child(const 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); @@ -218,7 +224,7 @@ zix_btree_split_child(ZixBTreeNode* const n, assert(zix_btree_child(n, i) == lhs); const ZixShort max_n_vals = zix_btree_max_vals(lhs); - ZixBTreeNode* rhs = zix_btree_node_new(lhs->is_leaf); + ZixBTreeNode* rhs = zix_btree_node_new(allocator, lhs->is_leaf); if (!rhs) { return NULL; } @@ -407,7 +413,7 @@ zix_btree_is_full(const ZixBTreeNode* const n) static ZixStatus zix_btree_grow_up(ZixBTree* const t) { - ZixBTreeNode* const new_root = zix_btree_node_new(false); + ZixBTreeNode* const new_root = zix_btree_node_new(t->allocator, false); if (!new_root) { return ZIX_STATUS_NO_MEM; } @@ -416,7 +422,7 @@ zix_btree_grow_up(ZixBTree* const t) new_root->data.inode.children[0] = t->root; // Split the old root to get two balanced siblings - zix_btree_split_child(new_root, 0, t->root); + zix_btree_split_child(t->allocator, new_root, 0, t->root); t->root = new_root; return ZIX_STATUS_SUCCESS; @@ -450,7 +456,9 @@ zix_btree_insert(ZixBTree* const t, void* const e) ZixBTreeNode* child = node->data.inode.children[i]; if (zix_btree_is_full(child)) { // The child is full, split it before continuing - ZixBTreeNode* const rhs = zix_btree_split_child(node, i, child); + ZixBTreeNode* const rhs = + zix_btree_split_child(t->allocator, node, i, child); + if (!rhs) { return ZIX_STATUS_NO_MEM; } @@ -620,10 +628,10 @@ zix_btree_merge(ZixBTree* const t, ZixBTreeNode* const n, const unsigned i) // Root is now empty, replace it with its only child assert(n == t->root); t->root = lhs; - free(n); + zix_free(t->allocator, n); } - free(rhs); + zix_free(t->allocator, rhs); return lhs; } @@ -19,7 +19,6 @@ #include <assert.h> #include <stdbool.h> #include <stdint.h> -#include <stdlib.h> typedef struct ZixHashEntry { ZixHashCode hash; ///< Non-folded hash value @@ -27,32 +26,35 @@ typedef struct ZixHashEntry { } ZixHashEntry; struct ZixHashImpl { - ZixKeyFunc key_func; ///< User-provided key accessor - ZixHashFunc hash_func; ///< User-provided hashing function - ZixKeyEqualFunc equal_func; ///< User-provided 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 + 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 }; static const size_t min_n_entries = 4u; static const size_t tombstone = 0xDEADu; ZixHash* -zix_hash_new(const ZixKeyFunc key_func, - const ZixHashFunc hash_func, - const ZixKeyEqualFunc equal_func) +zix_hash_new(const ZixAllocator* const allocator, + const ZixKeyFunc key_func, + const ZixHashFunc hash_func, + const ZixKeyEqualFunc equal_func) { assert(key_func); assert(hash_func); assert(equal_func); - ZixHash* const hash = (ZixHash*)malloc(sizeof(ZixHash)); + ZixHash* const hash = (ZixHash*)zix_malloc(allocator, sizeof(ZixHash)); if (!hash) { return NULL; } + hash->allocator = allocator; hash->key_func = key_func; hash->hash_func = hash_func; hash->equal_func = equal_func; @@ -60,9 +62,11 @@ zix_hash_new(const ZixKeyFunc key_func, hash->n_entries = min_n_entries; hash->mask = hash->n_entries - 1u; - hash->entries = (ZixHashEntry*)calloc(hash->n_entries, sizeof(ZixHashEntry)); + hash->entries = + (ZixHashEntry*)zix_calloc(allocator, hash->n_entries, sizeof(ZixHashEntry)); + if (!hash->entries) { - free(hash); + zix_free(allocator, hash); return NULL; } @@ -73,8 +77,8 @@ void zix_hash_free(ZixHash* const hash) { if (hash) { - free(hash->entries); - free(hash); + zix_free(hash->allocator, hash->entries); + zix_free(hash->allocator, hash); } } @@ -173,7 +177,9 @@ rehash(ZixHash* const hash, const size_t old_n_entries) const size_t new_n_entries = hash->n_entries; // Replace the array in the hash first so we can use find_entry() normally - hash->entries = (ZixHashEntry*)calloc(new_n_entries, sizeof(ZixHashEntry)); + hash->entries = (ZixHashEntry*)zix_calloc( + hash->allocator, new_n_entries, sizeof(ZixHashEntry)); + if (!hash->entries) { return ZIX_STATUS_NO_MEM; } @@ -191,7 +197,7 @@ rehash(ZixHash* const hash, const size_t old_n_entries) } } - free(old_entries); + zix_free(hash->allocator, old_entries); return ZIX_STATUS_SUCCESS; } @@ -44,11 +44,12 @@ #endif struct ZixRingImpl { - uint32_t write_head; ///< Read index into buf - uint32_t read_head; ///< Write index into buf - uint32_t size; ///< Size (capacity) in bytes - uint32_t size_mask; ///< Mask for fast modulo - char* buf; ///< Contents + 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 }; static inline uint32_t @@ -66,14 +67,23 @@ next_power_of_two(uint32_t size) } ZixRing* -zix_ring_new(uint32_t size) +zix_ring_new(const ZixAllocator* const allocator, uint32_t size) { - ZixRing* ring = (ZixRing*)malloc(sizeof(ZixRing)); - ring->write_head = 0; - ring->read_head = 0; - ring->size = next_power_of_two(size); - ring->size_mask = ring->size - 1; - ring->buf = (char*)malloc(ring->size); + ZixRing* ring = (ZixRing*)zix_malloc(allocator, sizeof(ZixRing)); + + if (ring) { + ring->allocator = allocator; + ring->write_head = 0; + ring->read_head = 0; + ring->size = next_power_of_two(size); + ring->size_mask = ring->size - 1; + + if (!(ring->buf = (char*)zix_malloc(allocator, ring->size))) { + zix_free(allocator, ring); + return NULL; + } + } + return ring; } @@ -81,8 +91,8 @@ void zix_ring_free(ZixRing* ring) { if (ring) { - free(ring->buf); - free(ring); + zix_free(ring->allocator, ring->buf); + zix_free(ring->allocator, ring); } } @@ -19,19 +19,19 @@ #include "zix/common.h" #include <assert.h> -#include <stdlib.h> #include <string.h> typedef struct ZixTreeNodeImpl ZixTreeNode; struct ZixTreeImpl { - ZixTreeNode* root; - ZixDestroyFunc destroy; - const void* destroy_user_data; - ZixComparator cmp; - void* cmp_data; - size_t size; - bool allow_duplicates; + const ZixAllocator* allocator; + ZixTreeNode* root; + ZixDestroyFunc destroy; + const void* destroy_user_data; + ZixComparator cmp; + void* cmp_data; + size_t size; + bool allow_duplicates; }; struct ZixTreeNodeImpl { @@ -67,20 +67,26 @@ struct ZixTreeNodeImpl { #endif ZixTree* -zix_tree_new(bool allow_duplicates, - ZixComparator cmp, - void* cmp_data, - ZixDestroyFunc destroy, - const void* destroy_user_data) +zix_tree_new(const ZixAllocator* const allocator, + bool allow_duplicates, + ZixComparator cmp, + void* cmp_data, + ZixDestroyFunc destroy, + const void* destroy_user_data) { - ZixTree* t = (ZixTree*)malloc(sizeof(ZixTree)); - t->root = NULL; - t->destroy = destroy; - t->destroy_user_data = destroy_user_data; - t->cmp = cmp; - t->cmp_data = cmp_data; - t->size = 0; - t->allow_duplicates = allow_duplicates; + ZixTree* t = (ZixTree*)zix_malloc(allocator, sizeof(ZixTree)); + + if (t) { + t->allocator = allocator; + t->root = NULL; + t->destroy = destroy; + t->destroy_user_data = destroy_user_data; + t->cmp = cmp; + t->cmp_data = cmp_data; + t->size = 0; + t->allow_duplicates = allow_duplicates; + } + return t; } @@ -93,7 +99,8 @@ zix_tree_free_rec(ZixTree* t, ZixTreeNode* n) if (t->destroy) { t->destroy(n->data, t->destroy_user_data); } - free(n); + + zix_free(t->allocator, n); } } @@ -102,7 +109,7 @@ zix_tree_free(ZixTree* t) { if (t) { zix_tree_free_rec(t, t->root); - free(t); + zix_free(t->allocator, t); } } @@ -370,7 +377,7 @@ zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti) } // Allocate a new node n - if (!(n = (ZixTreeNode*)malloc(sizeof(ZixTreeNode)))) { + if (!(n = (ZixTreeNode*)zix_malloc(t->allocator, sizeof(ZixTreeNode)))) { return ZIX_STATUS_NO_MEM; } memset(n, '\0', sizeof(ZixTreeNode)); @@ -456,7 +463,7 @@ zix_tree_remove(ZixTree* t, ZixTreeIter* ti) if (t->destroy) { t->destroy(n->data, t->destroy_user_data); } - free(n); + zix_free(t->allocator, n); --t->size; assert(t->size == 0); return ZIX_STATUS_SUCCESS; @@ -588,7 +595,7 @@ zix_tree_remove(ZixTree* t, ZixTreeIter* ti) if (t->destroy) { t->destroy(n->data, t->destroy_user_data); } - free(n); + zix_free(t->allocator, n); --t->size; |