From 32407e728971006ed3d0885e01c22fb66c8adc57 Mon Sep 17 00:00:00 2001 From: Alex Auvolat Date: Fri, 15 Jul 2016 23:12:14 +0200 Subject: Move stuff around, again --- src/common/libkogata/btree.c | 343 ++++++++++++++++++++++++++++++++++++ src/common/libkogata/hashtbl.c | 177 +++++++++++++++++++ src/common/libkogata/keyval.c | 51 ++++++ src/common/libkogata/mutex.c | 2 +- src/common/libkogata/region_alloc.c | 6 +- src/common/libkogata/slab_alloc.c | 2 +- 6 files changed, 576 insertions(+), 5 deletions(-) create mode 100644 src/common/libkogata/btree.c create mode 100644 src/common/libkogata/hashtbl.c create mode 100644 src/common/libkogata/keyval.c (limited to 'src/common/libkogata') diff --git a/src/common/libkogata/btree.c b/src/common/libkogata/btree.c new file mode 100644 index 0000000..dc5f11f --- /dev/null +++ b/src/common/libkogata/btree.c @@ -0,0 +1,343 @@ +#include +#include + +#include + +typedef struct btree_item { + void *key, *val; + + int height; + struct btree_item *left, *right; +} btree_item_t; + +struct btree { + key_cmp_fun_t cf; + kv_iter_fun_t releasef; + + btree_item_t *root; + int nitems; +}; + +btree_t* create_btree(key_cmp_fun_t cf, kv_iter_fun_t relf) { + btree_t* t = (btree_t*)malloc(sizeof(btree_t)); + + if (t == 0) return 0; + + t->cf = cf; + t->releasef = relf; + + t->root = 0; + t->nitems = 0; + + return t; +} + +void _btree_delete_item_rec(btree_item_t *i,kv_iter_fun_t relf) { + if (i == 0) return; + + _btree_delete_item_rec(i->left, relf); + _btree_delete_item_rec(i->right, relf); + + if (relf) relf(i->key, i->val); + free(i); +} +void delete_btree(btree_t *t) { + _btree_delete_item_rec(t->root, t->releasef); + + free(t); +} + +size_t btree_count(btree_t *i) { + return i->nitems; +} + +// ============== // +// TREE ROTATIONS // +// ============== // + +static inline int height(btree_item_t *i) { + if (i == 0) return 0; + return i->height; +} + +void btree_recalc_height(btree_item_t *i) { + if (i == 0) return; + + i->height = MAX(height(i->left), height(i->right)) + 1; +} + +btree_item_t* btree_rotate_left(btree_item_t *i) { + // I(X(a, b), Y) -> a X b I Y -> X(a, I(b, Y)) + + btree_item_t *x = i->left; + if (x == 0) return i; + btree_item_t *b = x->right; + + x->right = i; + i->left = b; + + btree_recalc_height(i); + btree_recalc_height(x); + + return x; +} + +btree_item_t* btree_rotate_right(btree_item_t *i) { + // I(X, Y(a,b)) -> X I a Y b -> Y(I(X, a), b) + + btree_item_t *y = i->right; + if (y == 0) return i; + btree_item_t *a = y->left; + + y->left = i; + i->right = a; + + btree_recalc_height(i); + btree_recalc_height(y); + + return y; +} + +btree_item_t* btree_equilibrate(btree_item_t *i) { + if (i == 0) return 0; + + while (height(i->left) - height(i->right) >= 2) + i = btree_rotate_left(i); + + while (height(i->right) - height(i->left) >= 2) + i = btree_rotate_right(i); + + return i; +} + +// =================== // +// ADDING AND DELETING // +// =================== // + +btree_item_t* _btree_insert(btree_t *t, btree_item_t *root, btree_item_t *i) { + if (root == 0) return i; + + if (t->cf(i->key, root->key) <= 0) { + root->left = _btree_insert(t, root->left, i); + } else { + root->right = _btree_insert(t, root->right, i); + } + btree_recalc_height(root); + + return btree_equilibrate(root); +} +bool btree_add(btree_t *t, void* key, void* val) { + btree_item_t *x = (btree_item_t*)malloc(sizeof(btree_item_t)); + if (x == 0) return false; + + x->key = key; + x->val = val; + x->left = x->right = 0; + btree_recalc_height(x); + + t->root = _btree_insert(t, t->root, x); + t->nitems++; + + return true; +} + +btree_item_t *_btree_extract_smallest(btree_item_t *i, btree_item_t **out_smallest) { + ASSERT(i != 0); + if (i->left == 0) { + *out_smallest = i; + return i->right; + } else { + i->left = _btree_extract_smallest(i->left, out_smallest); + btree_recalc_height(i); + return btree_equilibrate(i); + } +} +btree_item_t *_btree_remove_aux(btree_t *t, btree_item_t *i, const void* key) { + if (i == 0) return 0; + + int c = t->cf(key, i->key); + if (c < 0) { + i->left = _btree_remove_aux(t, i->left, key); + return btree_equilibrate(i); + } else if (c > 0) { + i->right = _btree_remove_aux(t, i->right, key); + return btree_equilibrate(i); + } else { + // remove item i + + btree_item_t *new_i; + if (i->right == 0 || i->left == 0) { + new_i = (i->right == 0 ? i->left : i->right); + } else { + btree_item_t *new_i_right = _btree_extract_smallest(i->right, &new_i); + + new_i->left = i->left; + new_i->right = new_i_right; + + btree_recalc_height(new_i); + new_i = btree_equilibrate(new_i); + } + + if (t->releasef) t->releasef(i->key, i->val); + free(i); + t->nitems--; + + return _btree_remove_aux(t, new_i, key); // loop because several elements may correspond + } +} +void btree_remove(btree_t *t, const void* key) { + t->root = _btree_remove_aux(t, t->root, key); +} + +btree_item_t *_btree_extract_smallest_v(btree_item_t *i, btree_item_t **out_smallest) { + ASSERT(i != 0); + if (i->left == 0) { + *out_smallest = i; + return i->right; + } else { + i->left = _btree_extract_smallest_v(i->left, out_smallest); + btree_recalc_height(i); + return btree_equilibrate(i); + } +} +btree_item_t *_btree_remove_aux_v(btree_t *t, btree_item_t *i, const void* key, const void* val) { + if (i == 0) return 0; + + int c = t->cf(key, i->key); + if (c < 0) { + i->left = _btree_remove_aux_v(t, i->left, key, val); + return btree_equilibrate(i); + } else if (c > 0) { + i->right = _btree_remove_aux_v(t, i->right, key, val); + return btree_equilibrate(i); + } else if (i->val == val) { + // remove item i + + btree_item_t *new_i; + if (i->right == 0 || i->left == 0) { + new_i = (i->right == 0 ? i->left : i->right); + } else { + btree_item_t *new_i_right = _btree_extract_smallest_v(i->right, &new_i); + + new_i->left = i->left; + new_i->right = new_i_right; + + btree_recalc_height(new_i); + new_i = btree_equilibrate(new_i); + } + + if (t->releasef) t->releasef(i->key, i->val); + free(i); + t->nitems--; + + return _btree_remove_aux_v(t, new_i, key, val); // loop because several elements may correspond + } else { + i->left = _btree_remove_aux_v(t, i->left, key, val); + i->right = _btree_remove_aux_v(t, i->right, key, val); + btree_recalc_height(i); + return btree_equilibrate(i); + } +} +void btree_remove_v(btree_t *t, const void* key, const void* val) { + t->root = _btree_remove_aux_v(t, t->root, key, val); +} + +// ======================== // +// LOOKING UP AND ITERATING // +// ======================== // + +btree_item_t *_btree_find_aux(btree_t *t, btree_item_t *i, const void* key) { + if (i == 0) return 0; + + int c = t->cf(key, i->key); + if (c == 0) { + return i; + } else if (c < 0) { + return _btree_find_aux(t, i->left, key); + } else { + return _btree_find_aux(t, i->right, key); + } +} +void* btree_find(btree_t *t, const void* key) { + + btree_item_t *i = _btree_find_aux(t, t->root, key); + + if (i == 0) return 0; + return i->val; +} + +btree_item_t *_btree_lower_aux(btree_t *t, btree_item_t *i, const void* key) { + if (i == 0) return 0; + + int c = t->cf(key, i->key); + if (c == 0) { + return i; + } else if (c < 0) { + return _btree_lower_aux(t, i->left, key); + } else { + btree_item_t *r = _btree_lower_aux(t, i->right, key); + if (r == 0) r = i; + return r; + } +} +void* btree_lower(btree_t *t, const void* key, void** actual_key) { + btree_item_t *i = _btree_lower_aux(t, t->root, key); + + if (i == 0) return 0; + if (actual_key != 0) *actual_key = i->key; + return i->val; +} + +btree_item_t *_btree_upper_aux(btree_t *t, btree_item_t *i, const void* key) { + if (i == 0) return 0; + + int c = t->cf(key, i->key); + if (c == 0) { + return i; + } else if (c < 0) { + btree_item_t *r = _btree_upper_aux(t, i->left, key); + if (r == 0) r = i; + return r; + } else { + return _btree_upper_aux(t, i->right, key); + } +} +void* btree_upper(btree_t *t, const void* key, void** actual_key) { + btree_item_t *i = _btree_upper_aux(t, t->root, key); + + if (i == 0) return 0; + if (actual_key != 0) *actual_key = i->key; + return i->val; +} + + +void _btree_iter_aux(btree_item_t *i, kv_iter_fun_t f) { + if (i == 0) return; + + _btree_iter_aux(i->left, f); + f(i->key, i->val); + _btree_iter_aux(i->right, f); +} +void btree_iter(btree_t *t, kv_iter_fun_t f) { + _btree_iter_aux(t->root, f); +} + +void _btree_iter_on_aux(btree_t *t, btree_item_t *i, const void* key, kv_iter_fun_t f) { + if (i == 0) return; + + int c = t->cf(key, i->key); + if (c == 0) { + _btree_iter_on_aux(t, i->left, key, f); + f(i->key, i->val); + _btree_iter_on_aux(t, i->right, key, f); + } else if (c < 0) { + _btree_iter_on_aux(t, i->left, key, f); + } else { + _btree_iter_on_aux(t, i->right, key, f); + } +} +void btree_iter_on(btree_t *t, const void* key, kv_iter_fun_t f) { + _btree_iter_on_aux(t, t->root, key, f); +} + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/libkogata/hashtbl.c b/src/common/libkogata/hashtbl.c new file mode 100644 index 0000000..b0097cd --- /dev/null +++ b/src/common/libkogata/hashtbl.c @@ -0,0 +1,177 @@ +#include +#include + +#include + +#define DEFAULT_HT_INIT_SIZE 16 +#define SLOT_OF_HASH(k, nslots) (((size_t)(k)*21179)%(size_t)(nslots)) + +typedef struct hashtbl_item { + void* key; + void* val; + struct hashtbl_item *next; +} hashtbl_item_t; + +// When nitems > size * 3/4, size is multiplied by two +// When nitems < size * 1/4, size is divided by two +struct hashtbl { + key_eq_fun_t ef; + hash_fun_t hf; + kv_iter_fun_t releasef; + size_t size, nitems; + hashtbl_item_t **items; +}; + +hashtbl_t *create_hashtbl(key_eq_fun_t ef, hash_fun_t hf, kv_iter_fun_t on_release) { + hashtbl_t *ht = (hashtbl_t*)malloc(sizeof(hashtbl_t)); + if (ht == 0) return 0; + + ht->ef = ef; + ht->hf = hf; + ht->releasef = on_release; + + ht->size = DEFAULT_HT_INIT_SIZE; + ht->nitems = 0; + + ht->items = (hashtbl_item_t**)malloc(ht->size * sizeof(hashtbl_item_t*)); + if (ht->items == 0) { + free(ht); + return 0; + } + + for (size_t i = 0; i < ht->size; i++) ht->items[i] = 0; + + return ht; +} + +void delete_hashtbl(hashtbl_t *ht) { + // Free items + for (size_t i = 0; i < ht->size; i++) { + while (ht->items[i] != 0) { + hashtbl_item_t *x = ht->items[i]; + ht->items[i] = x->next; + + if (ht->releasef) ht->releasef(x->key, x->val); + + free(x); + } + } + + // Free table + free(ht->items); + free(ht); +} + +void hashtbl_check_size(hashtbl_t *ht) { + size_t nsize = 0; + if (4 * ht->nitems < ht->size) nsize = ht->size / 2; + if (4 * ht->nitems > 3 * ht->size) nsize = ht->size * 2; + + if (nsize != 0 && nsize >= DEFAULT_HT_INIT_SIZE) { + hashtbl_item_t **nitems = (hashtbl_item_t**)malloc(nsize * sizeof(hashtbl_item_t*)); + if (nitems == 0) return; // if we can't realloc, too bad, we just lose space/efficienty + + for (size_t i = 0; i < nsize; i++) nitems[i] = 0; + + // rehash + for (size_t i = 0; i < ht->size; i++) { + while (ht->items[i] != 0) { + hashtbl_item_t *x = ht->items[i]; + ht->items[i] = x->next; + + size_t slot = SLOT_OF_HASH(ht->hf(x->key), nsize); + x->next = nitems[slot]; + nitems[slot] = x; + } + } + free(ht->items); + ht->size = nsize; + ht->items = nitems; + } +} + +bool hashtbl_add(hashtbl_t *ht, void* key, void* v) { + hashtbl_item_t *i = (hashtbl_item_t*)malloc(sizeof(hashtbl_item_t)); + if (i == 0) return false; // OOM + + // make sure item is not already present + hashtbl_remove(ht, key); + + size_t slot = SLOT_OF_HASH(ht->hf(key), ht->size); + + i->key = key; + i->val = v; + i->next = ht->items[slot]; + ht->items[slot] = i; + ht->nitems++; + + hashtbl_check_size(ht); + + return true; +} + +void hashtbl_remove(hashtbl_t* ht, const void* key) { + size_t slot = SLOT_OF_HASH(ht->hf(key), ht->size); + + if (ht->items[slot] == 0) return; + + hashtbl_item_t *x = 0; + + if (ht->ef(ht->items[slot]->key, key)) { + x = ht->items[slot]; + ht->items[slot] = x->next; + } else { + for (hashtbl_item_t *i = ht->items[slot]; i->next != 0; i = i->next) { + if (ht->ef(i->next->key, key)) { + x = i->next; + i->next = x->next; + break; + } + } + } + + if (x != 0) { + ht->nitems--; + if (ht->releasef) ht->releasef(x->key, x->val); + free(x); + } + + hashtbl_check_size(ht); +} + +void* hashtbl_find(hashtbl_t* ht, const void* key) { + size_t slot = SLOT_OF_HASH(ht->hf(key), ht->size); + + for (hashtbl_item_t *i = ht->items[slot]; i != 0; i = i->next) { + if (ht->ef(i->key, key)) return i->val; + } + + return 0; +} + +void hashtbl_iter(hashtbl_t *ht, kv_iter_fun_t f) { + for (size_t s = 0; s < ht->size; s++) { + for (hashtbl_item_t *i = ht->items[s]; i != 0; i = i->next) { + f(i->key, i->val); + } + } +} + +size_t hashtbl_count(hashtbl_t* ht) { + return ht->nitems; +} + +bool hashtbl_change(hashtbl_t* ht, void* key, void* newval) { + size_t slot = SLOT_OF_HASH(ht->hf(key), ht->size); + + for (hashtbl_item_t *i = ht->items[slot]; i != 0; i = i->next) { + if (ht->ef(i->key, key)) { + i->val = newval; + return true; + } + } + + return false; +} + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/libkogata/keyval.c b/src/common/libkogata/keyval.c new file mode 100644 index 0000000..9541c72 --- /dev/null +++ b/src/common/libkogata/keyval.c @@ -0,0 +1,51 @@ +#include + +#include +#include + +// Hashing and comparing + +hash_t id_hash_fun(const void* v) { + return (hash_t)v; +} + +hash_t str_hash_fun(const void* v) { + hash_t h = 712; + for (char* s = (char*)v; *s != 0; s++) { + h = h * 101 + *s; + } + return h; +} + +bool id_key_eq_fun(const void* a, const void* b) { + return a == b; +} + +bool str_key_eq_fun(const void* a, const void* b) { + return strcmp((const char*)a, (const char*)b) == 0; +} + +int id_key_cmp_fun(const void* a, const void* b) { + return (a == b ? 0 : (a < b ? -1 : 1)); +} + +int str_key_cmp_fun(const void* a, const void* b) { + return strcmp((const char*)a, (const char*)b); +} + +// Freeing functions + +void free_key(void* key, void* val) { + free(key); +} + +void free_val(void* key, void* val) { + free(val); +} + +void free_key_val(void* key, void* val) { + free(key); + free(val); +} + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/libkogata/mutex.c b/src/common/libkogata/mutex.c index b345ee5..e521330 100644 --- a/src/common/libkogata/mutex.c +++ b/src/common/libkogata/mutex.c @@ -1,4 +1,4 @@ -#include +#include /* Internal use only. This function is atomic, meaning it cannot be interrupted by a system task switch. */ static uint32_t atomic_exchange(uint32_t* ptr, uint32_t newval) { diff --git a/src/common/libkogata/region_alloc.c b/src/common/libkogata/region_alloc.c index 1f2fe0f..85c437a 100644 --- a/src/common/libkogata/region_alloc.c +++ b/src/common/libkogata/region_alloc.c @@ -1,6 +1,6 @@ -#include -#include -#include +#include +#include +#include // we cannot include sys... diff --git a/src/common/libkogata/slab_alloc.c b/src/common/libkogata/slab_alloc.c index 0736655..6362207 100644 --- a/src/common/libkogata/slab_alloc.c +++ b/src/common/libkogata/slab_alloc.c @@ -1,4 +1,4 @@ -#include +#include typedef struct object { struct object *next; -- cgit v1.2.3