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/include/algo.h | 37 -------------------------- src/common/include/btree.h | 33 ----------------------- src/common/include/debug.h | 18 ------------- src/common/include/hashtbl.h | 35 ------------------------- src/common/include/kogata/algo.h | 37 ++++++++++++++++++++++++++ src/common/include/kogata/btree.h | 33 +++++++++++++++++++++++ src/common/include/kogata/debug.h | 18 +++++++++++++ src/common/include/kogata/hashtbl.h | 35 +++++++++++++++++++++++++ src/common/include/kogata/malloc.h | 13 +++++++++ src/common/include/kogata/mutex.h | 22 ++++++++++++++++ src/common/include/kogata/printf.h | 10 +++++++ src/common/include/kogata/region_alloc.h | 32 +++++++++++++++++++++++ src/common/include/kogata/slab_alloc.h | 45 ++++++++++++++++++++++++++++++++ src/common/include/malloc.h | 13 --------- src/common/include/mutex.h | 22 ---------------- src/common/include/printf.h | 10 ------- src/common/include/region_alloc.h | 32 ----------------------- src/common/include/slab_alloc.h | 45 -------------------------------- 18 files changed, 245 insertions(+), 245 deletions(-) delete mode 100644 src/common/include/algo.h delete mode 100644 src/common/include/btree.h delete mode 100644 src/common/include/debug.h delete mode 100644 src/common/include/hashtbl.h create mode 100644 src/common/include/kogata/algo.h create mode 100644 src/common/include/kogata/btree.h create mode 100644 src/common/include/kogata/debug.h create mode 100644 src/common/include/kogata/hashtbl.h create mode 100644 src/common/include/kogata/malloc.h create mode 100644 src/common/include/kogata/mutex.h create mode 100644 src/common/include/kogata/printf.h create mode 100644 src/common/include/kogata/region_alloc.h create mode 100644 src/common/include/kogata/slab_alloc.h delete mode 100644 src/common/include/malloc.h delete mode 100644 src/common/include/mutex.h delete mode 100644 src/common/include/printf.h delete mode 100644 src/common/include/region_alloc.h delete mode 100644 src/common/include/slab_alloc.h (limited to 'src/common/include') diff --git a/src/common/include/algo.h b/src/common/include/algo.h deleted file mode 100644 index 80af052..0000000 --- a/src/common/include/algo.h +++ /dev/null @@ -1,37 +0,0 @@ -#pragma once - -#include -#include -#include - -#define MIN(a, b) ((a)<(b)?(a):(b)) -#define MAX(a, b) ((a)>(b)?(a):(b)) -#define ABS(a) ((a)<0?-(a):(a)) - -// ============================================================= // -// FUNCTION TYPES FOR KEY-VALUE DATA STRUCTURES (HASHTBL, BTREE) // - -typedef uint32_t hash_t; -typedef hash_t (*hash_fun_t)(const void*); - -typedef int (*key_cmp_fun_t)(const void*, const void*); -typedef bool (*key_eq_fun_t)(const void*, const void*); - -typedef void (*kv_iter_fun_t)(void* key, void* value); - -// void* is considered as an unsigned integer (and not a pointer) -hash_t id_hash_fun(const void* v); -bool id_key_eq_fun(const void* a, const void* b); -int id_key_cmp_fun(const void* a, const void* b); - -// void* considered as char* -hash_t str_hash_fun(const void* v); -bool str_key_eq_fun(const void* a, const void* b); -int str_key_cmp_fun(const void* a, const void* b); - -// Freeing functions (they are of type kv_iter_fun_t) -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/include/btree.h b/src/common/include/btree.h deleted file mode 100644 index a645d66..0000000 --- a/src/common/include/btree.h +++ /dev/null @@ -1,33 +0,0 @@ -#pragma once - -#include - -// A btree may contain several bindings for the same key (in that case they are not ordered) -// - btree_find returns any item with matching key, or null if none exists -// - btree_lower returns any item with matching key, or if none returns last item with smaller key -// - btree_upper returns any item with matching key, or if none returns first item with bigger key -// - btree_remove removes *all bindings* with matching key -// - btree_remove_v removes bindings with matching *key and value* -// - btree_iter_on calls iterator function on all bindings with matching key - -// Memory management is same as for hashtbl (a kv_iter_fun_t is called when an item is released) - -struct btree; -typedef struct btree btree_t; - -btree_t* create_btree(key_cmp_fun_t cf, kv_iter_fun_t on_release); -void delete_btree(btree_t *t); - -bool btree_add(btree_t *t, void* key, void* val); -void btree_remove(btree_t *t, const void* key); -void btree_remove_v(btree_t *t, const void* key, const void* value); - -void* btree_find(btree_t *i, const void* key); -void* btree_lower(btree_t *i, const void* key, void** actual_key); -void* btree_upper(btree_t *i, const void* key, void** actual_key); -void btree_iter(btree_t *i, kv_iter_fun_t f); -void btree_iter_on(btree_t *i, const void* key, kv_iter_fun_t f); - -size_t btree_count(btree_t *i); - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/include/debug.h b/src/common/include/debug.h deleted file mode 100644 index 2db5a80..0000000 --- a/src/common/include/debug.h +++ /dev/null @@ -1,18 +0,0 @@ -#pragma once - -#include -#include - -void sys_panic(const char* message, const char* file, int line) -__attribute__((__noreturn__)); - -void sys_panic_assert(const char* assertion, const char* file, int line) -__attribute__((__noreturn__)); - -#define PANIC(s) sys_panic(s, __FILE__, __LINE__); -#define ASSERT(s) { if (!(s)) sys_panic_assert(#s, __FILE__, __LINE__); } - -void dbg_print(const char* str); -void dbg_printf(const char* format, ...); - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/include/hashtbl.h b/src/common/include/hashtbl.h deleted file mode 100644 index b9c7178..0000000 --- a/src/common/include/hashtbl.h +++ /dev/null @@ -1,35 +0,0 @@ -#pragma once - -#include - -// Simple hashtable structure (key -> void*) -// Supports adding, seeking, removing, iterating -// When adding a binding to the table, the previous binding for same key (if exists) is removed - -// The hashtbl is allocated with malloc/free -// The keys/values are not copied by the hastbl, but when a key/value pair is removed from the -// table some operations may be required (freeing memory), so a kv_iter_fun_t is passed when the -// table is created which will be called whenever a k/v is released (on hashtbl_remove and delete_hashtbl) - -// A hashtbl may have only one binding for a given key (on add, previous binding is removed if necessary) - -struct hashtbl; -typedef struct hashtbl hashtbl_t; - -hashtbl_t* create_hashtbl(key_eq_fun_t ef, hash_fun_t hf, kv_iter_fun_t on_release); -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_remove(hashtbl_t* ht, const void* key); - -void* hashtbl_find(hashtbl_t* ht, const void* key); // null when not found -void hashtbl_iter(hashtbl_t* ht, kv_iter_fun_t f); - -// hashtbl_change is particular : -// - it does NOT call malloc and uses the existing hashtbl cell -// - it does NOT call the on_release fun on the previous element -bool hashtbl_change(hashtbl_t* ht, void* key, void* v); - -size_t hashtbl_count(hashtbl_t* ht); - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/include/kogata/algo.h b/src/common/include/kogata/algo.h new file mode 100644 index 0000000..80af052 --- /dev/null +++ b/src/common/include/kogata/algo.h @@ -0,0 +1,37 @@ +#pragma once + +#include +#include +#include + +#define MIN(a, b) ((a)<(b)?(a):(b)) +#define MAX(a, b) ((a)>(b)?(a):(b)) +#define ABS(a) ((a)<0?-(a):(a)) + +// ============================================================= // +// FUNCTION TYPES FOR KEY-VALUE DATA STRUCTURES (HASHTBL, BTREE) // + +typedef uint32_t hash_t; +typedef hash_t (*hash_fun_t)(const void*); + +typedef int (*key_cmp_fun_t)(const void*, const void*); +typedef bool (*key_eq_fun_t)(const void*, const void*); + +typedef void (*kv_iter_fun_t)(void* key, void* value); + +// void* is considered as an unsigned integer (and not a pointer) +hash_t id_hash_fun(const void* v); +bool id_key_eq_fun(const void* a, const void* b); +int id_key_cmp_fun(const void* a, const void* b); + +// void* considered as char* +hash_t str_hash_fun(const void* v); +bool str_key_eq_fun(const void* a, const void* b); +int str_key_cmp_fun(const void* a, const void* b); + +// Freeing functions (they are of type kv_iter_fun_t) +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/include/kogata/btree.h b/src/common/include/kogata/btree.h new file mode 100644 index 0000000..e796a2d --- /dev/null +++ b/src/common/include/kogata/btree.h @@ -0,0 +1,33 @@ +#pragma once + +#include + +// A btree may contain several bindings for the same key (in that case they are not ordered) +// - btree_find returns any item with matching key, or null if none exists +// - btree_lower returns any item with matching key, or if none returns last item with smaller key +// - btree_upper returns any item with matching key, or if none returns first item with bigger key +// - btree_remove removes *all bindings* with matching key +// - btree_remove_v removes bindings with matching *key and value* +// - btree_iter_on calls iterator function on all bindings with matching key + +// Memory management is same as for hashtbl (a kv_iter_fun_t is called when an item is released) + +struct btree; +typedef struct btree btree_t; + +btree_t* create_btree(key_cmp_fun_t cf, kv_iter_fun_t on_release); +void delete_btree(btree_t *t); + +bool btree_add(btree_t *t, void* key, void* val); +void btree_remove(btree_t *t, const void* key); +void btree_remove_v(btree_t *t, const void* key, const void* value); + +void* btree_find(btree_t *i, const void* key); +void* btree_lower(btree_t *i, const void* key, void** actual_key); +void* btree_upper(btree_t *i, const void* key, void** actual_key); +void btree_iter(btree_t *i, kv_iter_fun_t f); +void btree_iter_on(btree_t *i, const void* key, kv_iter_fun_t f); + +size_t btree_count(btree_t *i); + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/include/kogata/debug.h b/src/common/include/kogata/debug.h new file mode 100644 index 0000000..2db5a80 --- /dev/null +++ b/src/common/include/kogata/debug.h @@ -0,0 +1,18 @@ +#pragma once + +#include +#include + +void sys_panic(const char* message, const char* file, int line) +__attribute__((__noreturn__)); + +void sys_panic_assert(const char* assertion, const char* file, int line) +__attribute__((__noreturn__)); + +#define PANIC(s) sys_panic(s, __FILE__, __LINE__); +#define ASSERT(s) { if (!(s)) sys_panic_assert(#s, __FILE__, __LINE__); } + +void dbg_print(const char* str); +void dbg_printf(const char* format, ...); + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/include/kogata/hashtbl.h b/src/common/include/kogata/hashtbl.h new file mode 100644 index 0000000..e8f327c --- /dev/null +++ b/src/common/include/kogata/hashtbl.h @@ -0,0 +1,35 @@ +#pragma once + +#include + +// Simple hashtable structure (key -> void*) +// Supports adding, seeking, removing, iterating +// When adding a binding to the table, the previous binding for same key (if exists) is removed + +// The hashtbl is allocated with malloc/free +// The keys/values are not copied by the hastbl, but when a key/value pair is removed from the +// table some operations may be required (freeing memory), so a kv_iter_fun_t is passed when the +// table is created which will be called whenever a k/v is released (on hashtbl_remove and delete_hashtbl) + +// A hashtbl may have only one binding for a given key (on add, previous binding is removed if necessary) + +struct hashtbl; +typedef struct hashtbl hashtbl_t; + +hashtbl_t* create_hashtbl(key_eq_fun_t ef, hash_fun_t hf, kv_iter_fun_t on_release); +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_remove(hashtbl_t* ht, const void* key); + +void* hashtbl_find(hashtbl_t* ht, const void* key); // null when not found +void hashtbl_iter(hashtbl_t* ht, kv_iter_fun_t f); + +// hashtbl_change is particular : +// - it does NOT call malloc and uses the existing hashtbl cell +// - it does NOT call the on_release fun on the previous element +bool hashtbl_change(hashtbl_t* ht, void* key, void* v); + +size_t hashtbl_count(hashtbl_t* ht); + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/include/kogata/malloc.h b/src/common/include/kogata/malloc.h new file mode 100644 index 0000000..e55c25e --- /dev/null +++ b/src/common/include/kogata/malloc.h @@ -0,0 +1,13 @@ +#pragma once + +#include +#include + +// Header is in common/, but implementation is not. + +void* malloc(size_t sz); +void free(void* ptr); +void* calloc(size_t nmemb, size_t sz); +void* realloc(void* ptr, size_t sz); + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/include/kogata/mutex.h b/src/common/include/kogata/mutex.h new file mode 100644 index 0000000..88c077e --- /dev/null +++ b/src/common/include/kogata/mutex.h @@ -0,0 +1,22 @@ +#pragma once + +#include +#include + +#define MUTEX_LOCKED 1 +#define MUTEX_UNLOCKED 0 + + +typedef uint32_t mutex_t; + +void mutex_lock(mutex_t* mutex); //wait for mutex to be free +bool mutex_try_lock(mutex_t* mutex); //lock mutex only if free, returns true when locked, false when was busy +void mutex_unlock(mutex_t* mutex); + +// the mutex code assumes a yield() function is defined somewhere +void yield(); + +#define STATIC_MUTEX(name) static mutex_t name __attribute__((section("locks"))) = MUTEX_UNLOCKED; + + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/include/kogata/printf.h b/src/common/include/kogata/printf.h new file mode 100644 index 0000000..b4e1c1b --- /dev/null +++ b/src/common/include/kogata/printf.h @@ -0,0 +1,10 @@ +#pragma once + +#include +#include +#include + +int snprintf(char* s, size_t n, const char* format, ...); +int vsnprintf(char* s, size_t n, const char* format, va_list arg); + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/include/kogata/region_alloc.h b/src/common/include/kogata/region_alloc.h new file mode 100644 index 0000000..d314bd5 --- /dev/null +++ b/src/common/include/kogata/region_alloc.h @@ -0,0 +1,32 @@ +#pragma once + +// Virtual memory region allocator + +// This is entirely thread-safe + +#include +#include +#include + +struct region_info; + +typedef bool (*map_page_fun_t)(void* addr); // map a single page (used by region allocator) + +typedef struct region_info { + void* addr; + size_t size; + char* type; +} region_info_t; + +// rsvd_end : when used for kernel memory region management, a reserved region +// exists between begin (=K_HIGHHALF_ADDR) and the end of kernel static data +// for user processes, use rsvd_end = begin (no reserved region) +void region_allocator_init(void* begin, void* rsvd_end, void* end, map_page_fun_t map); + +void* region_alloc(size_t size, char* type); // returns 0 on error +region_info_t *find_region(void* addr); +void region_free(void* addr); + +void dbg_print_region_info(); + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/include/kogata/slab_alloc.h b/src/common/include/kogata/slab_alloc.h new file mode 100644 index 0000000..1191057 --- /dev/null +++ b/src/common/include/kogata/slab_alloc.h @@ -0,0 +1,45 @@ +#pragma once + +// Self-contained piece of library : a slab allocator... +// Depends on page_alloc_fun_t and page_free_fun_t : a couple of functions +// that can allocate/free multiples of one page at a time + +#include +#include +#include + + +#if defined(__linux__) +//redefine necessary stuff +#include // standard linux assert.h +#define ASSERT assert +#include +#define dbg_printf printf +#else +#include +#endif + +#define PAGE_SIZE 0x1000 + +// expected format for the array of slab_type_t given to slab_create : +// an array of slab_type descriptors, with last descriptor full of zeroes +// and with obj_size increasing (strictly) in the array +typedef struct slab_type { + const char *descr; + size_t obj_size; + size_t pages_per_cache; +} slab_type_t; + +struct mem_allocator; +typedef struct mem_allocator mem_allocator_t; + +typedef void* (*page_alloc_fun_t)(size_t bytes); +typedef void (*page_free_fun_t)(void* ptr); + +mem_allocator_t* create_slab_allocator(const slab_type_t *types, page_alloc_fun_t af, page_free_fun_t ff); +void destroy_slab_allocator(mem_allocator_t*); + +void* slab_alloc(mem_allocator_t* a, size_t sz); +void slab_free(mem_allocator_t* a, void* ptr); + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/include/malloc.h b/src/common/include/malloc.h deleted file mode 100644 index e55c25e..0000000 --- a/src/common/include/malloc.h +++ /dev/null @@ -1,13 +0,0 @@ -#pragma once - -#include -#include - -// Header is in common/, but implementation is not. - -void* malloc(size_t sz); -void free(void* ptr); -void* calloc(size_t nmemb, size_t sz); -void* realloc(void* ptr, size_t sz); - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/include/mutex.h b/src/common/include/mutex.h deleted file mode 100644 index 88c077e..0000000 --- a/src/common/include/mutex.h +++ /dev/null @@ -1,22 +0,0 @@ -#pragma once - -#include -#include - -#define MUTEX_LOCKED 1 -#define MUTEX_UNLOCKED 0 - - -typedef uint32_t mutex_t; - -void mutex_lock(mutex_t* mutex); //wait for mutex to be free -bool mutex_try_lock(mutex_t* mutex); //lock mutex only if free, returns true when locked, false when was busy -void mutex_unlock(mutex_t* mutex); - -// the mutex code assumes a yield() function is defined somewhere -void yield(); - -#define STATIC_MUTEX(name) static mutex_t name __attribute__((section("locks"))) = MUTEX_UNLOCKED; - - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/include/printf.h b/src/common/include/printf.h deleted file mode 100644 index b4e1c1b..0000000 --- a/src/common/include/printf.h +++ /dev/null @@ -1,10 +0,0 @@ -#pragma once - -#include -#include -#include - -int snprintf(char* s, size_t n, const char* format, ...); -int vsnprintf(char* s, size_t n, const char* format, va_list arg); - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/include/region_alloc.h b/src/common/include/region_alloc.h deleted file mode 100644 index d314bd5..0000000 --- a/src/common/include/region_alloc.h +++ /dev/null @@ -1,32 +0,0 @@ -#pragma once - -// Virtual memory region allocator - -// This is entirely thread-safe - -#include -#include -#include - -struct region_info; - -typedef bool (*map_page_fun_t)(void* addr); // map a single page (used by region allocator) - -typedef struct region_info { - void* addr; - size_t size; - char* type; -} region_info_t; - -// rsvd_end : when used for kernel memory region management, a reserved region -// exists between begin (=K_HIGHHALF_ADDR) and the end of kernel static data -// for user processes, use rsvd_end = begin (no reserved region) -void region_allocator_init(void* begin, void* rsvd_end, void* end, map_page_fun_t map); - -void* region_alloc(size_t size, char* type); // returns 0 on error -region_info_t *find_region(void* addr); -void region_free(void* addr); - -void dbg_print_region_info(); - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/include/slab_alloc.h b/src/common/include/slab_alloc.h deleted file mode 100644 index c8d5d6c..0000000 --- a/src/common/include/slab_alloc.h +++ /dev/null @@ -1,45 +0,0 @@ -#pragma once - -// Self-contained piece of library : a slab allocator... -// Depends on page_alloc_fun_t and page_free_fun_t : a couple of functions -// that can allocate/free multiples of one page at a time - -#include -#include -#include - - -#if defined(__linux__) -//redefine necessary stuff -#include // standard linux assert.h -#define ASSERT assert -#include -#define dbg_printf printf -#else -#include -#endif - -#define PAGE_SIZE 0x1000 - -// expected format for the array of slab_type_t given to slab_create : -// an array of slab_type descriptors, with last descriptor full of zeroes -// and with obj_size increasing (strictly) in the array -typedef struct slab_type { - const char *descr; - size_t obj_size; - size_t pages_per_cache; -} slab_type_t; - -struct mem_allocator; -typedef struct mem_allocator mem_allocator_t; - -typedef void* (*page_alloc_fun_t)(size_t bytes); -typedef void (*page_free_fun_t)(void* ptr); - -mem_allocator_t* create_slab_allocator(const slab_type_t *types, page_alloc_fun_t af, page_free_fun_t ff); -void destroy_slab_allocator(mem_allocator_t*); - -void* slab_alloc(mem_allocator_t* a, size_t sz); -void slab_free(mem_allocator_t* a, void* ptr); - -/* vim: set ts=4 sw=4 tw=0 noet :*/ -- cgit v1.2.3