aboutsummaryrefslogtreecommitdiff
path: root/src/common/libalgo
diff options
context:
space:
mode:
Diffstat (limited to 'src/common/libalgo')
-rw-r--r--src/common/libalgo/btree.c343
-rw-r--r--src/common/libalgo/hashtbl.c177
-rw-r--r--src/common/libalgo/keyval.c51
3 files changed, 0 insertions, 571 deletions
diff --git a/src/common/libalgo/btree.c b/src/common/libalgo/btree.c
deleted file mode 100644
index d1bfd18..0000000
--- a/src/common/libalgo/btree.c
+++ /dev/null
@@ -1,343 +0,0 @@
-#include <malloc.h>
-#include <debug.h>
-
-#include <btree.h>
-
-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/libalgo/hashtbl.c b/src/common/libalgo/hashtbl.c
deleted file mode 100644
index 0284d75..0000000
--- a/src/common/libalgo/hashtbl.c
+++ /dev/null
@@ -1,177 +0,0 @@
-#include <debug.h>
-#include <malloc.h>
-
-#include <hashtbl.h>
-
-#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/libalgo/keyval.c b/src/common/libalgo/keyval.c
deleted file mode 100644
index 528fa90..0000000
--- a/src/common/libalgo/keyval.c
+++ /dev/null
@@ -1,51 +0,0 @@
-#include <malloc.h>
-#include <string.h>
-
-#include <algo.h>
-
-// 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 :*/
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-22 11:18:58 +0000