From ab35e5fac02f11f0bd742020b112a09e5b1f2de5 Mon Sep 17 00:00:00 2001 From: Alex Auvolat Date: Tue, 16 Dec 2014 21:21:46 +0100 Subject: Add simple hash table implementation. --- kernel/Makefile | 2 +- kernel/config.h | 2 + kernel/include/hashtbl.h | 31 +++++++++ kernel/l0/kmain.c | 61 ++++++++++++++--- kernel/lib/hashtbl.c | 166 +++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 251 insertions(+), 11 deletions(-) create mode 100644 kernel/include/hashtbl.h create mode 100644 kernel/lib/hashtbl.c diff --git a/kernel/Makefile b/kernel/Makefile index 5571543..a981c72 100644 --- a/kernel/Makefile +++ b/kernel/Makefile @@ -9,7 +9,7 @@ CFLAGS = -ffreestanding -O2 -std=gnu99 -Wall -Wextra -I . -I ./include -g -Wno-u LD = i586-elf-gcc LDFLAGS = -T linker.ld -ffreestanding -O2 -nostdlib -lgcc -Xlinker -Map=kernel.map -OBJ = lib/string.o lib/printf.o lib/slab_alloc.o lib/mutex.o \ +OBJ = lib/string.o lib/printf.o lib/slab_alloc.o lib/mutex.o lib/hashtbl.o \ l0/loader.o l0/kmain.o l0/dbglog.o l0/sys.o \ l0/gdt.o l0/idt.o l0/interrupt.o l0/context_switch.o l0/thread.o \ l0/frame.o l0/paging.o l0/region.o l0/kmalloc.o diff --git a/kernel/config.h b/kernel/config.h index 2de43af..a0e59d3 100644 --- a/kernel/config.h +++ b/kernel/config.h @@ -13,6 +13,8 @@ #error "This kernel needs to be compiled with a ix86-elf compiler" #endif +#define IN_KERNEL + #define K_HIGHHALF_ADDR ((size_t)0xC0000000) #define OS_NAME "macrO.Scope" diff --git a/kernel/include/hashtbl.h b/kernel/include/hashtbl.h new file mode 100644 index 0000000..984aa70 --- /dev/null +++ b/kernel/include/hashtbl.h @@ -0,0 +1,31 @@ +#pragma once + +#include +#include +#include + +// Simple hashtable structure (key -> void*) +// Supports adding, seeking, removing +// When adding a binding to the table, the previous binding for same key (if exists) is removed + +struct hashtbl; +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*); + +hashtbl_t* create_hashtbl(key_eq_fun_t ef, hash_fun_t hf, size_t initial_size); // 0 -> default size +void delete_hashtbl(hashtbl_t* ht); + +int hashtbl_add(hashtbl_t* ht, void* key, void* v); // non-null on error (OOM for instance) +void* hashtbl_find(hashtbl_t* ht, void* key); // null when not found +void hashtbl_remove(hashtbl_t* ht, void* key); +size_t hashtbl_count(hashtbl_t* ht); + +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); + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/l0/kmain.c b/kernel/l0/kmain.c index 140a09f..f0ce014 100644 --- a/kernel/l0/kmain.c +++ b/kernel/l0/kmain.c @@ -13,6 +13,7 @@ #include #include +#include extern const void k_end_addr; // defined in linker script : 0xC0000000 plus kernel stuff @@ -100,25 +101,65 @@ void kmalloc_test(void* kernel_data_end) { dbg_print_region_info(); } +void test_hashtbl_1() { + // hashtable test + hashtbl_t *ht = create_hashtbl(str_key_eq_fun, str_hash_fun, 0); + hashtbl_add(ht, "test1", "Hello, world [test1]"); + hashtbl_add(ht, "test2", "Hello, world [test2]"); + dbg_printf("ht[test1] = %s\n", hashtbl_find(ht, "test1")); + dbg_printf("ht[test] = %s\n", hashtbl_find(ht, "test")); + dbg_printf("ht[test2] = %s\n", hashtbl_find(ht, "test2")); + dbg_printf("adding test...\n"); + hashtbl_add(ht, "test", "Forever alone"); + dbg_printf("ht[test1] = %s\n", hashtbl_find(ht, "test1")); + dbg_printf("ht[test] = %s\n", hashtbl_find(ht, "test")); + dbg_printf("ht[test2] = %s\n", hashtbl_find(ht, "test2")); + dbg_printf("removing test1...\n"); + hashtbl_remove(ht, "test1"); + dbg_printf("ht[test1] = %s\n", hashtbl_find(ht, "test1")); + dbg_printf("ht[test] = %s\n", hashtbl_find(ht, "test")); + dbg_printf("ht[test2] = %s\n", hashtbl_find(ht, "test2")); + delete_hashtbl(ht); +} + +void test_hashtbl_2() { + hashtbl_t *ht = create_hashtbl(id_key_eq_fun, id_hash_fun, 0); + hashtbl_add(ht, (void*)12, "Hello, world [12]"); + hashtbl_add(ht, (void*)777, "Hello, world [777]"); + dbg_printf("ht[12] = %s\n", hashtbl_find(ht, (void*)12)); + dbg_printf("ht[144] = %s\n", hashtbl_find(ht, (void*)144)); + dbg_printf("ht[777] = %s\n", hashtbl_find(ht, (void*)777)); + dbg_printf("adding 144...\n"); + hashtbl_add(ht, (void*)144, "Forever alone"); + dbg_printf("ht[12] = %s\n", hashtbl_find(ht, (void*)12)); + dbg_printf("ht[144] = %s\n", hashtbl_find(ht, (void*)144)); + dbg_printf("ht[777] = %s\n", hashtbl_find(ht, (void*)777)); + dbg_printf("removing 12...\n"); + hashtbl_remove(ht, (void*)12); + dbg_printf("ht[12] = %s\n", hashtbl_find(ht, (void*)12)); + dbg_printf("ht[144] = %s\n", hashtbl_find(ht, (void*)144)); + dbg_printf("ht[777] = %s\n", hashtbl_find(ht, (void*)777)); + delete_hashtbl(ht); +} + void test_thread(void* a) { - int i = 0; - while(1) { + for(int i = 0; i < 120; i++) { dbg_printf("b"); for (int x = 0; x < 100000; x++) asm volatile("xor %%ebx, %%ebx":::"%ebx"); - if (++i == 8) { - yield(); - i = 0; - } + if (i % 8 == 0) yield(); } } void kernel_init_stage2(void* data) { - thread_t *tb = new_thread(test_thread); - resume_thread_with_result(tb, 0, false); - dbg_print_region_info(); dbg_print_frame_stats(); - while(1) { + test_hashtbl_1(); + test_hashtbl_2(); + + thread_t *tb = new_thread(test_thread); + resume_thread_with_result(tb, 0, false); + + for (int i = 0; i < 120; i++) { dbg_printf("a"); for (int x = 0; x < 100000; x++) asm volatile("xor %%ebx, %%ebx":::"%ebx"); } diff --git a/kernel/lib/hashtbl.c b/kernel/lib/hashtbl.c new file mode 100644 index 0000000..91fb3cb --- /dev/null +++ b/kernel/lib/hashtbl.c @@ -0,0 +1,166 @@ +#include +#include +#include + +#define DEFAULT_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; + size_t size, nitems; + hashtbl_item_t **items; +}; + +hashtbl_t *create_hashtbl(key_eq_fun_t ef, hash_fun_t hf, size_t initial_size) { + hashtbl_t *ht = (hashtbl_t*)kmalloc(sizeof(hashtbl_t)); + if (ht == 0) return 0; + + ht->ef = ef; + ht->hf = hf; + + ht->size = (initial_size == 0 ? DEFAULT_INIT_SIZE : initial_size); + ht->nitems = 0; + + ht->items = (hashtbl_item_t**)kmalloc(ht->size * sizeof(hashtbl_item_t*)); + if (ht->items == 0) { + kfree(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 *n = ht->items[i]->next; + kfree(ht->items[i]); + ht->items[i] = n; + } + } + + // Free table + kfree(ht->items); + kfree(ht); +} + +static 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) { + hashtbl_item_t **nitems = (hashtbl_item_t**)kmalloc(nsize * sizeof(hashtbl_item_t*)); + if (nitems == 0) return; // if we can't realloc, too bad, we just lose space + + 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; + } + } + kfree(ht->items); + ht->size = nsize; + ht->items = nitems; + } +} + +int hashtbl_add(hashtbl_t *ht, void* key, void* v) { + size_t slot = SLOT_OF_HASH(ht->hf(key), ht->size); + + hashtbl_item_t *i = (hashtbl_item_t*)kmalloc(sizeof(hashtbl_item_t)); + if (i == 0) return 1; // OOM + + // make sure item is not already present + hashtbl_remove(ht, key); + + i->key = key; + i->val = v; + i->next = ht->items[slot]; + ht->items[slot] = i; + ht->nitems++; + + hashtbl_check_size(ht); + + return 0; +} + +void* hashtbl_find(hashtbl_t* ht, 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_remove(hashtbl_t* ht, void* key) { + size_t slot = SLOT_OF_HASH(ht->hf(key), ht->size); + + if (ht->items[slot] == 0) return; + + if (ht->ef(ht->items[slot]->key, key)) { + hashtbl_item_t *x = ht->items[slot]; + ht->items[slot] = x->next; + kfree(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; + i->next = x->next; + kfree(x); + ht->nitems--; + break; + } + } + } + + hashtbl_check_size(ht); +} + +size_t hashtbl_count(hashtbl_t* ht) { + return ht->nitems; +} + +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; +} + +/* vim: set ts=4 sw=4 tw=0 noet :*/ -- cgit v1.2.3