From 3abf4c09ce3ea173ac9840e97788ca4c477a8aa1 Mon Sep 17 00:00:00 2001 From: comex Date: Thu, 29 Jan 2015 01:21:15 -0500 Subject: port some old code --- Makefile | 1 + lib/cbit/htab.h | 274 ++++++++++++++++++++++++++++++++++++++++ lib/cbit/misc.h | 25 ++++ lib/darwin/stop-other-threads.c | 3 +- test/test-htab.c | 49 +++++++ 5 files changed, 351 insertions(+), 1 deletion(-) create mode 100644 lib/cbit/htab.h create mode 100644 lib/cbit/misc.h create mode 100644 test/test-htab.c diff --git a/Makefile b/Makefile index b11646e..6eb3118 100644 --- a/Makefile +++ b/Makefile @@ -133,6 +133,7 @@ $(eval $(call define_test,stop-threads,stop-threads,$(CC) -std=c11 out/darwin/st $(eval $(call define_test,execmem,execmem,$(CC) -std=c11 out/darwin/execmem.o -segprot __TEST rwx rx)) $(eval $(call define_test,hook-functions,hook-functions,$(CC) -std=c11 -lsubstitute)) $(eval $(call define_test,posixspawn-hook,posixspawn-hook,$(CC) -std=c11)) +$(eval $(call define_test,htab,htab,$(CC) -std=c11)) out/injected-test-dylib.dylib: test/injected-test-dylib.c Makefile $(CC) -std=c11 -dynamiclib -o $@ $< diff --git a/lib/cbit/htab.h b/lib/cbit/htab.h new file mode 100644 index 0000000..861a9be --- /dev/null +++ b/lib/cbit/htab.h @@ -0,0 +1,274 @@ +#pragma once +#include "misc.h" +#include +#include +#include +#include + +struct htab_internal { + size_t length; + size_t capacity; + void *base; + char hi_storage[1]; // see vec.h +}; + +#define UNUSED_STATIC_INLINE __attribute__((unused)) static inline + +/* Declare the helper functions for a htab key type without static - put this + * in the .h and IMPL_HTAB_KEY in a .c. */ +#define DECL_EXTERN_HTAB_KEY( \ + name, \ + /* The key type. */ \ + key_ty \ +) \ + DO_DECL_HTAB_KEY(name, key_ty, ) + +/* Declare and implement the helper functions static inline. For the argument + * meanings, see IMPL_HTAB_KEY. */ +#define DECL_STATIC_HTAB_KEY( \ + name, \ + key_ty, \ + hash_func, \ + eq_func, \ + null_func, \ + nil_byte \ +) \ + DO_DECL_HTAB_KEY(name, key_ty, UNUSED_STATIC_INLINE); \ + IMPL_HTAB_KEY(name, hash_func, eq_func, null_func, nil_byte) + +#define DO_DECL_HTAB_KEY(name, key_ty, func_decl) \ + typedef key_ty __htab_key_key_ty_##name; \ + DO_DECL_HTAB_KEY_(name, __htab_key_key_ty_##name, func_decl) +#define DO_DECL_HTAB_KEY_(name, key_ty, func_decl) \ + func_decl \ + void *__htab_key_lookup_##name(struct htab_internal *restrict hi, \ + const key_ty *restrict key, \ + size_t entry_size, \ + bool add, bool resize_if_necessary); \ + func_decl \ + bool __htab_key_remove_##name(struct htab_internal *restrict hi, \ + const key_ty *restrict key, \ + size_t entry_size); \ + func_decl \ + void __htab_key_memset_##name(void *ptr, size_t size); \ + func_decl \ + bool __htab_key_is_null_##name(const key_ty *bucket); \ + func_decl \ + void __htab_key_resize_##name(struct htab_internal *restrict hi, \ + size_t size, \ + size_t entry_size) \ + +#define IMPL_HTAB_KEY(name, \ + /* size_t hash_func(const ty *) - hash. \ + * May be a macro. */ \ + hash_func, \ + /* bool eq_func(const ty *stored, const ty *queried) - check whether the \ + * stored key is equal to the requested key (which is assumed to be valid). \ + * May be a macro. */ \ + eq_func, \ + /* bool null_func(const ty *) - check whether the stored key is a \ + * special invalid marker. \ + * May be a macro. */ \ + null_func, \ + /* uint8_t nil_byte - which byte to memset to initially. \ + * null_func() must be true. */ \ + nil_byte \ +) \ + DO_IMPL_HTAB_KEY(name, __htab_key_key_ty_##name, hash_func, \ + eq_func, null_func, nil_byte) +#define DO_IMPL_HTAB_KEY(name, key_ty, hash_func, eq_func, null_func, nil_byte) \ + void __htab_key_resize_##name(struct htab_internal *restrict hi, \ + size_t capacity, \ + size_t entry_size); \ + void *__htab_key_lookup_##name(struct htab_internal *restrict hi, \ + const key_ty *restrict key, \ + size_t entry_size, \ + bool add, bool resize_if_necessary) { \ + if (resize_if_necessary && \ + hi->capacity * 2 <= hi->length * 3) \ + __htab_key_resize_##name(hi, hi->capacity * 2, entry_size); \ + size_t capacity = hi->capacity; \ + size_t hash = (hash_func(key)) % capacity; \ + size_t i = hash; \ + char *buckets = hi->base; \ + do { \ + key_ty *bucket = (void *) (buckets + i * entry_size); \ + if (null_func(bucket)) { \ + if (add) { \ + *bucket = *key; \ + hi->length++; \ + return bucket; \ + } else { \ + return NULL; \ + } \ + } \ + if (eq_func(bucket, key)) \ + return bucket; \ + } while ((i = (i + 1) % capacity) != hash); \ + return NULL; \ + } \ + \ + /* slow but who cares */ \ + bool __htab_key_remove_##name(struct htab_internal *restrict hi, \ + const key_ty *restrict key, \ + size_t entry_size) { \ + void *op = __htab_key_lookup_##name(hi, key, entry_size, false, false); \ + if (!op) \ + return false; \ + key_ty *orig = op; \ + key_ty *end = (void *) ((char *) hi->base + hi->capacity * entry_size); \ + key_ty *cur = orig; \ + key_ty *prev; \ + do { \ + prev = cur; \ + cur = (void *) ((char *) cur + entry_size); \ + if (cur == end) \ + cur = hi->base; \ + if (null_func(cur)) \ + break; \ + memmove(prev, cur, entry_size); \ + prev = cur; \ + } while (cur != orig); \ + memset(cur, 0, entry_size); \ + hi->length--; \ + return true; \ + } \ + void __htab_key_memset_##name(void *ptr, size_t size) { \ + memset(ptr, (nil_byte), size); \ + } \ + bool __htab_key_is_null_##name(const key_ty *bucket) { \ + return null_func(bucket); \ + } \ + void __htab_key_resize_##name(struct htab_internal *restrict hi, \ + size_t size, \ + size_t entry_size) { \ + size_t old_size = hi->capacity * entry_size; \ + size_t new_size = safe_mul(size, entry_size); \ + void *new_buf = malloc(new_size); \ + memset(new_buf, (nil_byte), new_size); \ + struct htab_internal temp; \ + temp.length = 0; \ + temp.capacity = size; \ + temp.base = new_buf; \ + for (size_t i = 0; i < old_size; i += entry_size) { \ + key_ty *bucket = (void *) ((char *) hi->base + i); \ + if (!null_func(bucket)) { \ + memcpy( \ + __htab_key_lookup_##name(&temp, bucket, entry_size, \ + true, false), \ + bucket, \ + entry_size); \ + } \ + } \ + hi->capacity = size; \ + if (hi->base != hi->hi_storage) \ + free(hi->base); \ + hi->base = new_buf; \ + } \ + typedef char __htab_want_semicolon_here_##name + +#define DECL_HTAB( \ + name, \ + /* The name parameter to DECL_HTAB_KEY */ \ + key_name, \ + value_ty) \ + typedef __htab_key_key_ty_##key_name __htab_key_ty_##name; \ + typedef value_ty __htab_value_ty_##name; \ + \ + DO_DECL_HTAB(name, \ + __htab_key_ty_##name, \ + __htab_value_ty_##name, \ + struct htab_bucket_##name, \ + struct htab_##name, \ + key_name) + +#define DO_DECL_HTAB(name, key_ty, value_ty, bucket_ty, htab_ty, key_name) \ + bucket_ty { \ + key_ty key; \ + value_ty value; \ + }; \ + htab_ty { \ + union { \ + char h[0]; \ + struct htab_internal hi; \ + struct { \ + size_t length; \ + size_t capacity; \ + bucket_ty *base; \ + bucket_ty storage[1]; \ + }; \ + }; \ + }; \ + UNUSED_STATIC_INLINE \ + bucket_ty *htab_getbucket_##name(htab_ty *restrict ht, \ + const key_ty *restrict key) { \ + return __htab_key_lookup_##key_name(&ht->hi, key, sizeof(bucket_ty), \ + false, true); \ + } \ + UNUSED_STATIC_INLINE \ + value_ty *htab_getp_##name(const htab_ty *restrict ht, \ + const key_ty *restrict key) { \ + bucket_ty *bucket = htab_getbucket_##name((void *) ht, key); \ + return bucket ? &bucket->value : NULL; \ + } \ + UNUSED_STATIC_INLINE \ + bucket_ty *htab_setbucket_##name(htab_ty *restrict ht, \ + const key_ty *restrict key) { \ + return __htab_key_lookup_##key_name(&ht->hi, key, sizeof(bucket_ty), \ + true, true); \ + } \ + UNUSED_STATIC_INLINE \ + value_ty *htab_setp_##name(const htab_ty *restrict ht, \ + const key_ty *restrict key) { \ + bucket_ty *bucket = htab_setbucket_##name((void *) ht, key); \ + return bucket ? &bucket->value : NULL; \ + } \ + UNUSED_STATIC_INLINE \ + bool htab_remove_##name(htab_ty *restrict ht, const key_ty *restrict key) { \ + return __htab_key_remove_##key_name(&ht->hi, key, sizeof(bucket_ty)); \ + } \ + UNUSED_STATIC_INLINE \ + void __htab_memset_##name(void *ptr, size_t size) { \ + return __htab_key_memset_##key_name(ptr, size); \ + } \ + UNUSED_STATIC_INLINE \ + bool __htab_is_null_##name(const key_ty *bucket) { \ + return __htab_key_is_null_##key_name(bucket); \ + } \ + UNUSED_STATIC_INLINE \ + void htab_resize_##name(htab_ty *ht, size_t size) { \ + return __htab_key_resize_##key_name(&ht->hi, size, sizeof(bucket_ty)); \ + } \ + UNUSED_STATIC_INLINE \ + void htab_free_##name(htab_ty *ht) { \ + if (ht->base != ht->storage) \ + free(ht->base); \ + } + +#define HTAB_STORAGE_CAPA(name, n) \ + struct { \ + struct htab_##name h; \ + struct htab_bucket_##name rest[(n)-1]; \ + } + +#define HTAB_STORAGE(name) \ + HTAB_STORAGE_CAPA(name, 5) + +#define HTAB_STORAGE_INIT(hs, name) do { \ + struct htab_##name *h = &(hs)->h; \ + h->length = 0; \ + h->capacity = (sizeof((hs)->rest) / sizeof(__htab_key_ty_##name)) + 1; \ + h->base = h->storage; \ + __htab_memset_##name(h->base, \ + h->capacity * sizeof(__htab_key_ty_##name)); \ +} while (0) + +#define HTAB_FOREACH(ht, key_var, val_var, name) \ + LET(struct htab_##name *__ht = (ht)) \ + for (size_t __htfe_bucket = 0; __htfe_bucket < __ht->capacity; __htfe_bucket++) \ + if(__htab_is_null_##name(&__ht->base[__htfe_bucket].key)) \ + continue; \ + else \ + LET_LOOP(key_var = &__ht->base[__htfe_bucket].key) \ + LET_LOOP(val_var = &__ht->base[__htfe_bucket].value) + diff --git a/lib/cbit/misc.h b/lib/cbit/misc.h new file mode 100644 index 0000000..45876f9 --- /dev/null +++ b/lib/cbit/misc.h @@ -0,0 +1,25 @@ +#pragma once + +#define LET_LOOP__(expr, ctr) \ + if (0) \ + __done_##ctr: continue; \ + else if (0) \ + __break_##ctr: break; \ + else \ + for (; ; ({ goto __break_##ctr; })) \ + for (expr; ; ({ goto __done_##ctr; })) + +#define LET_LOOP_(expr, ctr) LET_LOOP__(expr, ctr) +#define LET_LOOP(expr) LET_LOOP_(expr, __COUNTER__) + +#define LET__(expr, ctr) \ + if (0) \ + __done_##ctr: ; \ + else \ + for (expr; ; ({ goto __done_##ctr; })) + +#define LET_(expr, ctr) LET__(expr, ctr) +#define LET(expr) LET_(expr, __COUNTER__) + +#define safe_mul(a, b) ((a) * (b)) /* XXX */ + diff --git a/lib/darwin/stop-other-threads.c b/lib/darwin/stop-other-threads.c index b35c04c..ee9e803 100644 --- a/lib/darwin/stop-other-threads.c +++ b/lib/darwin/stop-other-threads.c @@ -1,9 +1,9 @@ +#if 0 #include "substitute.h" #include "substitute-internal.h" #include "darwin/mach-decls.h" #include #include -#include static void release_port(UNUSED CFAllocatorRef allocator, const void *value) { mach_port_t thread = (mach_port_t) value; @@ -159,3 +159,4 @@ int resume_other_threads(void *token) { CFRelease(suspended_set); return SUBSTITUTE_OK; /* eh */ } +#endif diff --git a/test/test-htab.c b/test/test-htab.c new file mode 100644 index 0000000..2986de8 --- /dev/null +++ b/test/test-htab.c @@ -0,0 +1,49 @@ +#include "cbit/htab.h" +#include +#include +struct teststr { + bool valid; + const char *what; +}; +#define ts_null(ts) ({ if (0) printf("null? %p\n", *ts); !*ts; }) +#define ts_eq(ts, cp) ({ if (0) printf("eq? %p %p\n", *ts, *cp); !strcmp(*(ts), *(cp)); }) +#define ts_hash(strp) strlen(*(strp)) +DECL_EXTERN_HTAB_KEY(teststr, const char *); +DECL_HTAB(teststr_int, teststr, int); + +int main() { + struct htab_teststr_int *hp; + HTAB_STORAGE(teststr_int) stor; + HTAB_STORAGE_INIT(&stor, teststr_int); + hp = &stor.h; + for(int i = 0; i < 100; i++) { + const char *k; + asprintf((char **) &k, "foo%d", i); + *htab_setp_teststr_int(hp, &k) = i; + } + const char *to_remove = "foo31"; + htab_remove_teststr_int(hp, &to_remove); + HTAB_FOREACH(hp, const char **k, int *v, teststr_int) { + if(*v % 10 == 1) + printf("%s -> %d\n", *k, *v); + } + htab_free_teststr_int(hp); +} + +/* +expect-output<< +foo91 -> 91 +foo21 -> 21 +foo1 -> 1 +foo11 -> 11 +foo31 -> 31 +foo41 -> 41 +foo51 -> 51 +foo61 -> 61 +foo71 -> 71 +foo81 -> 81 +>> +expect-exit 0 +*/ + +IMPL_HTAB_KEY(teststr, ts_hash, ts_eq, ts_null, /*nil_byte*/ 0); -- cgit v1.2.3