aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/common/include/hashtbl.h11
-rw-r--r--src/common/libalgo/hashtbl.c58
-rw-r--r--src/kernel/core/kmain.c8
-rw-r--r--src/kernel/user/nullfs.c8
-rw-r--r--src/kernel/user/process.c4
-rw-r--r--src/kernel/user/vfs.c4
6 files changed, 59 insertions, 34 deletions
diff --git a/src/common/include/hashtbl.h b/src/common/include/hashtbl.h
index ecac0a8..46f2978 100644
--- a/src/common/include/hashtbl.h
+++ b/src/common/include/hashtbl.h
@@ -19,19 +19,24 @@ typedef struct hashtbl hashtbl_t;
typedef size_t hash_t;
typedef hash_t (*hash_fun_t)(const void*);
typedef bool (*key_eq_fun_t)(const void*, const void*);
-typedef void (*free_fun_t)(void*);
+typedef void (*kv_iter_fun_t)(void* key, void* value);
-hashtbl_t* create_hashtbl(key_eq_fun_t ef, hash_fun_t hf, free_fun_t key_ff, size_t initial_size); // 0 -> default size
-void delete_hashtbl(hashtbl_t* ht, free_fun_t data_free_fun);
+hashtbl_t* create_hashtbl(key_eq_fun_t ef, hash_fun_t hf, kv_iter_fun_t on_release); // 0 -> default size
+void delete_hashtbl(hashtbl_t* ht);
bool hashtbl_add(hashtbl_t* ht, void* key, void* v); // true = ok, false on error (OOM for instance)
void* hashtbl_find(hashtbl_t* ht, const void* key); // null when not found
void hashtbl_remove(hashtbl_t* ht, const void* key);
size_t hashtbl_count(hashtbl_t* ht);
+void hashtbl_iter(hashtbl_t* ht, kv_iter_fun_t f);
hash_t id_hash_fun(const void* v);
hash_t str_hash_fun(const void* v);
bool id_key_eq_fun(const void* a, const void* b);
bool str_key_eq_fun(const void* a, const void* b);
+void free_key(void* key, void* val);
+void free_val(void* key, void* val);
+void free_key_val(void* key, void* val);
+
/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/common/libalgo/hashtbl.c b/src/common/libalgo/hashtbl.c
index b87bcef..b4720c3 100644
--- a/src/common/libalgo/hashtbl.c
+++ b/src/common/libalgo/hashtbl.c
@@ -2,7 +2,7 @@
#include <malloc.h>
#include <string.h>
-#define DEFAULT_INIT_SIZE 16
+#define DEFAULT_HT_INIT_SIZE 16
#define SLOT_OF_HASH(k, nslots) (((size_t)(k)*21179)%(size_t)(nslots))
typedef struct hashtbl_item {
@@ -16,20 +16,20 @@ typedef struct hashtbl_item {
struct hashtbl {
key_eq_fun_t ef;
hash_fun_t hf;
- free_fun_t kff;
+ 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, free_fun_t kff, size_t initial_size) {
+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->kff = kff;
+ ht->releasef = on_release;
- ht->size = (initial_size == 0 ? DEFAULT_INIT_SIZE : initial_size);
+ ht->size = DEFAULT_HT_INIT_SIZE;
ht->nitems = 0;
ht->items = (hashtbl_item_t**)malloc(ht->size * sizeof(hashtbl_item_t*));
@@ -43,15 +43,16 @@ hashtbl_t *create_hashtbl(key_eq_fun_t ef, hash_fun_t hf, free_fun_t kff, size_t
return ht;
}
-void delete_hashtbl(hashtbl_t *ht, free_fun_t data_free_fun) {
+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 *n = ht->items[i]->next;
- if (data_free_fun) data_free_fun(ht->items[i]->val);
- if (ht->kff) ht->kff(ht->items[i]->key);
- free(ht->items[i]);
- ht->items[i] = n;
+ hashtbl_item_t *x = ht->items[i];
+ ht->items[i] = x->next;
+
+ if (ht->releasef) ht->releasef(x->key, x->val);
+
+ free(x);
}
}
@@ -123,24 +124,26 @@ void hashtbl_remove(hashtbl_t* ht, const void* key) {
if (ht->items[slot] == 0) return;
+ hashtbl_item_t *x = 0;
+
if (ht->ef(ht->items[slot]->key, key)) {
- hashtbl_item_t *x = ht->items[slot];
+ x = ht->items[slot];
ht->items[slot] = x->next;
- if (ht->kff) ht->kff(x->key);
- free(x);
- ht->nitems--;
} else {
for (hashtbl_item_t *i = ht->items[slot]; i->next != 0; i = i->next) {
if (ht->ef(i->next->key, key)) {
- hashtbl_item_t *x = i->next;
+ x = i->next;
i->next = x->next;
- if (ht->kff) ht->kff(x->key);
- free(x);
- ht->nitems--;
break;
}
}
}
+
+ if (x != 0) {
+ ht->nitems--;
+ if (ht->releasef) ht->releasef(x->key, x->val);
+ free(x);
+ }
hashtbl_check_size(ht);
}
@@ -149,6 +152,10 @@ size_t hashtbl_count(hashtbl_t* ht) {
return ht->nitems;
}
+// ================================== //
+// UTILITY FUNCTIONS (HASH, EQ, FREE) //
+// ================================== //
+
hash_t id_hash_fun(const void* v) {
return (hash_t)v;
}
@@ -169,4 +176,17 @@ bool str_key_eq_fun(const void* a, const void* b) {
return strcmp((const char*)a, (const char*)b) == 0;
}
+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/kernel/core/kmain.c b/src/kernel/core/kmain.c
index ee6d8b2..ce3f536 100644
--- a/src/kernel/core/kmain.c
+++ b/src/kernel/core/kmain.c
@@ -125,7 +125,7 @@ void kmalloc_test(void* kernel_data_end) {
void test_hashtbl_1() {
dbg_printf("(BEGIN-TEST 'test-hashtbl-1)\n");
// hashtable test
- hashtbl_t *ht = create_hashtbl(str_key_eq_fun, str_hash_fun, 0, 0);
+ hashtbl_t *ht = create_hashtbl(str_key_eq_fun, str_hash_fun, 0);
ASSERT(ht != 0);
ASSERT(hashtbl_add(ht, "test1", "STRTEST1"));
@@ -151,7 +151,7 @@ void test_hashtbl_1() {
ASSERT(hashtbl_find(ht, "test") != 0 &&
strcmp(hashtbl_find(ht, "test"), "Forever alone") == 0);
- delete_hashtbl(ht, 0);
+ delete_hashtbl(ht);
dbg_printf("(TEST-OK)\n");
}
@@ -159,7 +159,7 @@ void test_hashtbl_1() {
void test_hashtbl_2() {
dbg_printf("(BEGIN-TEST 'test-hashtbl-2)\n");
- hashtbl_t *ht = create_hashtbl(id_key_eq_fun, id_hash_fun, 0, 0);
+ hashtbl_t *ht = create_hashtbl(id_key_eq_fun, id_hash_fun, 0);
ASSERT(ht != 0);
ASSERT(hashtbl_add(ht, (void*)12, "TESTSTR12"));
@@ -187,7 +187,7 @@ void test_hashtbl_2() {
ASSERT(hashtbl_find(ht, (void*)777) != 0 &&
strcmp(hashtbl_find(ht, (void*)777), "TESTSTR777") == 0);
- delete_hashtbl(ht, 0);
+ delete_hashtbl(ht);
dbg_printf("(TEST-OK)\n");
}
diff --git a/src/kernel/user/nullfs.c b/src/kernel/user/nullfs.c
index 1685f4c..97f3d00 100644
--- a/src/kernel/user/nullfs.c
+++ b/src/kernel/user/nullfs.c
@@ -149,7 +149,7 @@ bool nullfs_fs_make(fs_handle_t *source, char* opts, fs_t *fs_s) {
root->fs = fs;
root->items_list = 0;
root->lock = MUTEX_UNLOCKED;
- root->items_idx = create_hashtbl(str_key_eq_fun, str_hash_fun, 0, 0);
+ root->items_idx = create_hashtbl(str_key_eq_fun, str_hash_fun, 0);
if (root->items_idx == 0) {
free(root);
free(fs);
@@ -308,7 +308,7 @@ bool nullfs_d_delete(fs_node_ptr n, const char* file) {
nullfs_dir_t* sd = (nullfs_dir_t*)i->data;
if (sd->items_list != 0) return false;
- delete_hashtbl(sd->items_idx, 0);
+ delete_hashtbl(sd->items_idx);
free(sd);
} else if (i->ops == &nullfs_f_ops) {
nullfs_file_t* f = (nullfs_file_t*)i->data;
@@ -384,7 +384,7 @@ bool nullfs_d_create(fs_node_ptr n, const char* file, int type) {
nullfs_dir_t *x = (nullfs_dir_t*)malloc(sizeof(nullfs_dir_t));
if (x == 0) return false;
- x->items_idx = create_hashtbl(str_key_eq_fun, str_hash_fun, 0, 0);
+ x->items_idx = create_hashtbl(str_key_eq_fun, str_hash_fun, 0);
if (x->items_idx == 0) goto d_error;
x->items_list = 0;
@@ -411,7 +411,7 @@ bool nullfs_d_create(fs_node_ptr n, const char* file, int type) {
d_error:
if (i != 0 && i->name != 0) free(i->name);
if (i != 0) free(i);
- if (x->items_idx != 0) delete_hashtbl(x->items_idx, 0);
+ if (x->items_idx != 0) delete_hashtbl(x->items_idx);
free(x);
return false;
} else {
diff --git a/src/kernel/user/process.c b/src/kernel/user/process.c
index d1fdf32..2f3cac1 100644
--- a/src/kernel/user/process.c
+++ b/src/kernel/user/process.c
@@ -35,7 +35,7 @@ process_t *new_process(process_t *parent) {
process_t *proc = (process_t*)malloc(sizeof(process_t));
if (proc == 0) return 0;
- proc->filesystems = create_hashtbl(str_key_eq_fun, str_hash_fun, free, 0);
+ proc->filesystems = create_hashtbl(str_key_eq_fun, str_hash_fun, free_key);
if (proc->filesystems == 0) {
free(proc);
return 0;
@@ -43,7 +43,7 @@ process_t *new_process(process_t *parent) {
proc->pd = create_pagedir(proc_usermem_pf, proc);
if (proc->pd == 0) {
- delete_hashtbl(proc->filesystems, 0);
+ delete_hashtbl(proc->filesystems);
free(proc);
return 0;
}
diff --git a/src/kernel/user/vfs.c b/src/kernel/user/vfs.c
index 0624a38..1f7bacd 100644
--- a/src/kernel/user/vfs.c
+++ b/src/kernel/user/vfs.c
@@ -95,7 +95,7 @@ void unref_fs_node(fs_node_t *n) {
unref_fs_node(n->parent);
unref_fs(n->fs);
- if (n->children != 0) delete_hashtbl(n->children, 0);
+ if (n->children != 0) delete_hashtbl(n->children);
free(n->name);
free(n);
}
@@ -126,7 +126,7 @@ fs_node_t* fs_walk_one(fs_node_t* from, const char* file) {
if (!walk_ok) goto error;
if (from->children == 0) {
- from->children = create_hashtbl(str_key_eq_fun, str_hash_fun, 0, 0);
+ from->children = create_hashtbl(str_key_eq_fun, str_hash_fun, 0);
if (from->children == 0) goto error;
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-25 02:26:15 +0000