aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/hash_table.c20
-rw-r--r--src/hash_table.h16
-rw-r--r--src/rb_tree.c80
-rw-r--r--src/rb_tree.h20
4 files changed, 68 insertions, 68 deletions
diff --git a/src/hash_table.c b/src/hash_table.c
index e738a9b..376d712 100644
--- a/src/hash_table.c
+++ b/src/hash_table.c
@@ -8,8 +8,8 @@
#define HTFL_DEL 2
-static void rebuild(hash_table_t *ht) {
- hash_table_t newht;
+static void rebuild(HashTable *ht) {
+ HashTable newht;
init_hash_table(&newht, ht->elemsz, ht->size * 6, ht->hash, ht->eq);
void *iter = hash_table_begin(ht);
while (iter != NULL) {
@@ -21,7 +21,7 @@ static void rebuild(hash_table_t *ht) {
*ht = newht;
}
-void init_hash_table(hash_table_t *ht, int64_t elemsz, int64_t cap,
+void init_hash_table(HashTable *ht, int64_t elemsz, int64_t cap,
uint64_t (*hash)(void *), bool (*eq)(void *, void *)) {
if (cap < 16) cap = 16;
ht->buf = malloc(cap * elemsz);
@@ -36,7 +36,7 @@ void init_hash_table(hash_table_t *ht, int64_t elemsz, int64_t cap,
ht->eq = eq;
}
-bool hash_table_insert(hash_table_t *ht, void *elem) {
+bool hash_table_insert(HashTable *ht, void *elem) {
if (ht->taken + 1 > ht->cap / 2) {
rebuild(ht);
}
@@ -58,17 +58,17 @@ bool hash_table_insert(hash_table_t *ht, void *elem) {
return true;
}
-void hash_table_remove(hash_table_t *ht, void * ptr) {
+void hash_table_remove(HashTable *ht, void * ptr) {
ht->size--;
int64_t pos = (ptr - ht->buf) / ht->elemsz;
ht->flagbuf[pos] = HTFL_DEL;
}
-void *hash_table_ref(hash_table_t *ht, int64_t pos) {
+void *hash_table_ref(HashTable *ht, int64_t pos) {
return ht->buf + pos * ht->elemsz;
}
-void *hash_table_find(hash_table_t *ht, void *elem) {
+void *hash_table_find(HashTable *ht, void *elem) {
int64_t pos = ht->hash(elem) % ht->cap;
while (ht->flagbuf[pos] != HTFL_NUL) {
if (ht->flagbuf[pos] == HTFL_VAL
@@ -83,7 +83,7 @@ void *hash_table_find(hash_table_t *ht, void *elem) {
return NULL;
}
-void* hash_table_begin(hash_table_t *ht) {
+void* hash_table_begin(HashTable *ht) {
if (ht->size <= 0) return NULL;
for (int64_t i = 0; i < ht->cap; i++) {
if (ht->flagbuf[i] == HTFL_VAL) {
@@ -93,7 +93,7 @@ void* hash_table_begin(hash_table_t *ht) {
return NULL;
}
-void *hash_table_next(hash_table_t *ht, void *iter) {
+void *hash_table_next(HashTable *ht, void *iter) {
int64_t pos = (iter - ht->buf) / ht->elemsz;
do {
pos++;
@@ -104,7 +104,7 @@ void *hash_table_next(hash_table_t *ht, void *iter) {
return hash_table_ref(ht, pos);
}
-void destroy_hash_table(hash_table_t *ht) {
+void destroy_hash_table(HashTable *ht) {
free(ht->buf);
free(ht->flagbuf);
}
diff --git a/src/hash_table.h b/src/hash_table.h
index 3e18be6..549e261 100644
--- a/src/hash_table.h
+++ b/src/hash_table.h
@@ -14,17 +14,17 @@ struct hash_table {
uint64_t (*hash)(void *);
bool (*eq)(void *, void *);
};
-typedef struct hash_table hash_table_t;
+typedef struct hash_table HashTable;
-void init_hash_table(hash_table_t *ht, int64_t elemsz, int64_t cap,
+void init_hash_table(HashTable *ht, int64_t elemsz, int64_t cap,
uint64_t (*hash)(void *), bool (*eq)(void *, void *));
-bool hash_table_insert(hash_table_t *ht, void *elem);
-void hash_table_remove(hash_table_t *ht, void *iter);
+bool hash_table_insert(HashTable *ht, void *elem);
+void hash_table_remove(HashTable *ht, void *iter);
// return a iterator
-void *hash_table_find(hash_table_t *ht, void *elem);
-void *hash_table_begin(hash_table_t *ht);
-void *hash_table_next(hash_table_t *ht, void *iter);
-void destroy_hash_table(hash_table_t *ht);
+void *hash_table_find(HashTable *ht, void *elem);
+void *hash_table_begin(HashTable *ht);
+void *hash_table_next(HashTable *ht, void *iter);
+void destroy_hash_table(HashTable *ht);
#endif
diff --git a/src/rb_tree.c b/src/rb_tree.c
index f2bcd0c..10c4418 100644
--- a/src/rb_tree.c
+++ b/src/rb_tree.c
@@ -28,36 +28,36 @@
#define RED 1
#define BLACK 0
-static rb_node_t *rb_tree_minmax(rb_tree_t *, int);
-void *rb_tree_min(rb_tree_t *head) { return rb_tree_minmax(head, -1); }
-void *rb_tree_max(rb_tree_t *head) { return rb_tree_minmax(head, 1); }
+static RBNode *rb_tree_minmax(RBTree *, int);
+void *rb_tree_min(RBTree *head) { return rb_tree_minmax(head, -1); }
+void *rb_tree_max(RBTree *head) { return rb_tree_minmax(head, 1); }
void *rb_tree_left(void *node) {
- rb_node_t *elm = node;
+ RBNode *elm = node;
if (node == NULL) return NULL;
return elm->entry.rbe_left;
}
void *rb_tree_right(void *node) {
- rb_node_t *elm = node;
+ RBNode *elm = node;
if (node == NULL) return NULL;
return elm->entry.rbe_right;
}
void *rb_tree_parent(void *node) {
- rb_node_t *elm = node;
+ RBNode *elm = node;
if (node == NULL) return NULL;
return elm->entry.rbe_parent;
}
-static void augment(rb_tree_t *head, rb_node_t *elm) {
+static void augment(RBTree *head, RBNode *elm) {
if (head->augment != NULL) head->augment(elm);
}
-static void rb_tree_insert_color(rb_tree_t *head, rb_node_t *elm);
-static void rb_tree_remove_color(rb_tree_t *head, rb_node_t *parent,
- rb_node_t *elm);
+static void rb_tree_insert_color(RBTree *head, RBNode *elm);
+static void rb_tree_remove_color(RBTree *head, RBNode *parent,
+ RBNode *elm);
-static void rotate_left(rb_tree_t *head, rb_node_t *elm) {
- rb_node_t *tmp = elm->entry.rbe_right;
+static void rotate_left(RBTree *head, RBNode *elm) {
+ RBNode *tmp = elm->entry.rbe_right;
if ((elm->entry.rbe_right = tmp->entry.rbe_left)) {
tmp->entry.rbe_left->entry.rbe_parent = elm;
}
@@ -78,8 +78,8 @@ static void rotate_left(rb_tree_t *head, rb_node_t *elm) {
}
}
-static void rotate_right(rb_tree_t *head, rb_node_t *elm) {
- rb_node_t *tmp = elm->entry.rbe_left;
+static void rotate_right(RBTree *head, RBNode *elm) {
+ RBNode *tmp = elm->entry.rbe_left;
if ((elm->entry.rbe_left = tmp->entry.rbe_right)) {
tmp->entry.rbe_right->entry.rbe_parent = elm;
}
@@ -100,8 +100,8 @@ static void rotate_right(rb_tree_t *head, rb_node_t *elm) {
}
}
-static void rb_tree_insert_color(rb_tree_t *head, rb_node_t *elm) {
- rb_node_t *parent, *gparent, *tmp;
+static void rb_tree_insert_color(RBTree *head, RBNode *elm) {
+ RBNode *parent, *gparent, *tmp;
while ((parent = elm->entry.rbe_parent) && parent->entry.rbe_color == 1) {
gparent = parent->entry.rbe_parent;
if (parent == gparent->entry.rbe_left) {
@@ -146,9 +146,9 @@ static void rb_tree_insert_color(rb_tree_t *head, rb_node_t *elm) {
head->rbh_root->entry.rbe_color = BLACK;
}
-static void rb_tree_remove_color(rb_tree_t *head, rb_node_t *parent,
- rb_node_t *elm) {
- rb_node_t *tmp;
+static void rb_tree_remove_color(RBTree *head, RBNode *parent,
+ RBNode *elm) {
+ RBNode *tmp;
while ((elm == NULL || elm->entry.rbe_color == 0) &&
elm != head->rbh_root) {
if (parent->entry.rbe_left == elm) {
@@ -169,7 +169,7 @@ static void rb_tree_remove_color(rb_tree_t *head, rb_node_t *parent,
} else {
if (tmp->entry.rbe_right == NULL ||
tmp->entry.rbe_right->entry.rbe_color == 0) {
- rb_node_t *oleft;
+ RBNode *oleft;
if ((oleft = tmp->entry.rbe_left))
oleft->entry.rbe_color = BLACK;
tmp->entry.rbe_color = RED;
@@ -202,7 +202,7 @@ static void rb_tree_remove_color(rb_tree_t *head, rb_node_t *parent,
} else {
if (tmp->entry.rbe_left == NULL ||
tmp->entry.rbe_left->entry.rbe_color == 0) {
- rb_node_t *oright;
+ RBNode *oright;
if ((oright = tmp->entry.rbe_right))
oright->entry.rbe_color = BLACK;
tmp->entry.rbe_color = RED;
@@ -222,16 +222,16 @@ static void rb_tree_remove_color(rb_tree_t *head, rb_node_t *parent,
if (elm) elm->entry.rbe_color = BLACK;
}
-void rb_tree_remove(rb_tree_t *head, void *elmv) {
- rb_node_t *elm = elmv;
- rb_node_t *child, *parent;
+void rb_tree_remove(RBTree *head, void *elmv) {
+ RBNode *elm = elmv;
+ RBNode *child, *parent;
int color;
if (elm->entry.rbe_left == NULL)
child = elm->entry.rbe_right;
else if (elm->entry.rbe_right == NULL)
child = elm->entry.rbe_left;
else {
- rb_node_t *old = elm, *left;
+ RBNode *old = elm, *left;
elm = elm->entry.rbe_right;
while ((left = elm->entry.rbe_left))
elm = left;
@@ -277,7 +277,7 @@ void rb_tree_remove(rb_tree_t *head, void *elmv) {
parent->entry.rbe_left = child;
else
parent->entry.rbe_right = child;
- rb_node_t *goback = parent;
+ RBNode *goback = parent;
if (head->augment != NULL) {
do {
augment(head, goback);
@@ -289,10 +289,10 @@ color:
if (color == 0) rb_tree_remove_color(head, parent, child);
}
-void *rb_tree_insert(rb_tree_t *head, void *elmv) {
- rb_node_t *elm = elmv;
- rb_node_t *tmp;
- rb_node_t *parent = NULL;
+void *rb_tree_insert(RBTree *head, void *elmv) {
+ RBNode *elm = elmv;
+ RBNode *tmp;
+ RBNode *parent = NULL;
int comp = 0;
tmp = head->rbh_root;
while (tmp) {
@@ -313,7 +313,7 @@ void *rb_tree_insert(rb_tree_t *head, void *elmv) {
parent->entry.rbe_left = elm;
else
parent->entry.rbe_right = elm;
- rb_node_t *goback = parent;
+ RBNode *goback = parent;
if (head->augment != NULL) {
do {
augment(head, goback);
@@ -325,8 +325,8 @@ void *rb_tree_insert(rb_tree_t *head, void *elmv) {
return (NULL);
}
-void *rb_tree_find(rb_tree_t *head, void *key) {
- rb_node_t *tmp = head->rbh_root;
+void *rb_tree_find(RBTree *head, void *key) {
+ RBNode *tmp = head->rbh_root;
int comp;
while (tmp) {
comp = head->cmp(key, (void *)tmp->content);
@@ -340,8 +340,8 @@ void *rb_tree_find(rb_tree_t *head, void *key) {
return (NULL);
}
-void *rb_tree_next(rb_tree_t *head, void *elmv) {
- rb_node_t *elm = elmv;
+void *rb_tree_next(RBTree *head, void *elmv) {
+ RBNode *elm = elmv;
if (elm->entry.rbe_right) {
elm = elm->entry.rbe_right;
while (elm->entry.rbe_left)
@@ -360,9 +360,9 @@ void *rb_tree_next(rb_tree_t *head, void *elmv) {
return elm;
}
-static rb_node_t *rb_tree_minmax(rb_tree_t *head, int val) {
- rb_node_t *tmp = head->rbh_root;
- rb_node_t *parent = NULL;
+static RBNode *rb_tree_minmax(RBTree *head, int val) {
+ RBNode *tmp = head->rbh_root;
+ RBNode *parent = NULL;
while (tmp) {
parent = tmp;
if (val < 0)
@@ -373,7 +373,7 @@ static rb_node_t *rb_tree_minmax(rb_tree_t *head, int val) {
return parent;
};
-static void destroy_rb_tree_impl(rb_node_t *node, void (*free_cb)(void *)) {
+static void destroy_rb_tree_impl(RBNode *node, void (*free_cb)(void *)) {
if (node == NULL) return;
if (free_cb != NULL) free_cb(node->content);
destroy_rb_tree_impl(node->entry.rbe_left, free_cb);
@@ -381,6 +381,6 @@ static void destroy_rb_tree_impl(rb_node_t *node, void (*free_cb)(void *)) {
free(node);
}
-void destroy_rb_tree(rb_tree_t *head, void (*free_cb)(void *)) {
+void destroy_rb_tree(RBTree *head, void (*free_cb)(void *)) {
destroy_rb_tree_impl(head->rbh_root, free_cb);
}
diff --git a/src/rb_tree.h b/src/rb_tree.h
index 936cd34..2f00bf0 100644
--- a/src/rb_tree.h
+++ b/src/rb_tree.h
@@ -37,28 +37,28 @@ struct rb_node {
} entry;
char content[0];
};
-typedef struct rb_node rb_node_t;
+typedef struct rb_node RBNode;
struct rb_tree {
- rb_node_t *rbh_root;
+ RBNode *rbh_root;
int (*cmp)(void *k1, void *k2);
void (*augment)(void *elm);
};
-typedef struct rb_tree rb_tree_t;
+typedef struct rb_tree RBTree;
-void rb_tree_remove(rb_tree_t *, void *iter);
+void rb_tree_remove(RBTree *, void *iter);
// return a iterator
-void *rb_tree_insert(rb_tree_t *, void *treenode);
-void *rb_tree_find(rb_tree_t *, void *val);
-void *rb_tree_next(rb_tree_t *, void *iter);
-void *rb_tree_min(rb_tree_t *);
-void *rb_tree_max(rb_tree_t *);
+void *rb_tree_insert(RBTree *, void *treenode);
+void *rb_tree_find(RBTree *, void *val);
+void *rb_tree_next(RBTree *, void *iter);
+void *rb_tree_min(RBTree *);
+void *rb_tree_max(RBTree *);
void *rb_tree_left(void *node);
void *rb_tree_right(void *node);
void *rb_tree_parent(void *node);
-void destroy_rb_tree(rb_tree_t *, void (*freeCb)(void *));
+void destroy_rb_tree(RBTree *, void (*freeCb)(void *));
#endif
generated by cgit v1.0 at 2025-12-29 15:21:06 +0000