diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | lib/cbit/htab.h | 15 | ||||
| -rw-r--r-- | lib/cbit/misc.h | 6 | ||||
| -rw-r--r-- | lib/cbit/vec.c | 23 | ||||
| -rw-r--r-- | lib/cbit/vec.h | 121 | ||||
| -rw-r--r-- | test/test-vec.cpp | 23 |
6 files changed, 181 insertions, 9 deletions
@@ -70,6 +70,7 @@ LIB_OBJS := \ out/darwin/read.o \ out/darwin/substrate-compat.o \ out/darwin/execmem.o \ + out/cbit/vec.o \ out/jump-dis.o \ out/transform-dis.o \ out/hook-functions.o \ @@ -143,6 +144,7 @@ $(eval $(call define_test,execmem,execmem,$(CC) -std=c11 out/darwin/execmem.o -s $(eval $(call define_test,hook-functions,hook-functions,$(CC) -std=c11 -lsubstitute -segprot __TEST rwx rx)) $(eval $(call define_test,posixspawn-hook,posixspawn-hook,$(CC) -std=c11)) $(eval $(call define_test,htab,htab,$(CC) -std=c11)) +$(eval $(call define_test,vec,vec,$(CXX) -std=c++98 out/cbit/vec.o)) 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 index 5c9b993..ccb40b9 100644 --- a/lib/cbit/htab.h +++ b/lib/cbit/htab.h @@ -12,8 +12,6 @@ struct htab_internal { 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( \ @@ -188,7 +186,6 @@ struct htab_internal { }; \ htab_ty { \ union { \ - char h[0]; \ struct htab_internal hi; \ struct { \ size_t length; \ @@ -273,11 +270,13 @@ struct htab_internal { } 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)) \ + LET(struct htab_##name *__htfe_ht = (ht)) \ + for (size_t __htfe_bucket = 0; \ + __htfe_bucket < __htfe_ht->capacity; \ + __htfe_bucket++) \ + if(__htab_is_null_##name(&__htfe_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) + LET_LOOP(key_var = &__htfe_ht->base[__htfe_bucket].key) \ + LET_LOOP(val_var = &__htfe_ht->base[__htfe_bucket].value) diff --git a/lib/cbit/misc.h b/lib/cbit/misc.h index 52835b1..7c558ce 100644 --- a/lib/cbit/misc.h +++ b/lib/cbit/misc.h @@ -1,5 +1,7 @@ #pragma once +#define UNUSED_STATIC_INLINE __attribute__((unused)) static inline + #define LET_LOOP__(expr, ctr) \ if (0) \ __done_##ctr: continue; \ @@ -40,5 +42,7 @@ #define LET_(expr, ctr) LET__(expr, ctr) #define LET(expr) LET_(expr, __COUNTER__) -#define safe_mul(a, b) ((a) * (b)) /* XXX */ +/* XXX */ +#define safe_mul(a, b) ((a) * (b)) +#define safe_add(a, b) ((a) + (b)) diff --git a/lib/cbit/vec.c b/lib/cbit/vec.c new file mode 100644 index 0000000..21038a2 --- /dev/null +++ b/lib/cbit/vec.c @@ -0,0 +1,23 @@ +#include "cbit/vec.h" +#include <stdio.h> + +void vec_realloc_internal(struct vec_internal *vi, size_t new_capacity, + size_t esize) { + size_t new_size = safe_mul(new_capacity, esize); + if (vi->els == vi->storage) { + void *new = malloc(new_size); + memcpy(new, vi->els, vi->capacity * esize); + vi->els = new; + } else { + vi->els = realloc(vi->els, new_size); + } + vi->capacity = new_capacity; +} +void vec_realloc_internal_as_necessary(struct vec_internal *vi, + size_t min_capacity, + size_t esize) { + if (min_capacity > vi->capacity) + vec_realloc_internal(vi, safe_mul(vi->capacity, 2), esize); + else if (min_capacity < vi->capacity / 3) + vec_realloc_internal(vi, vi->capacity / 3, esize); +} diff --git a/lib/cbit/vec.h b/lib/cbit/vec.h new file mode 100644 index 0000000..87e4c28 --- /dev/null +++ b/lib/cbit/vec.h @@ -0,0 +1,121 @@ +#pragma once +#include "misc.h" +#include <stdlib.h> +#include <string.h> + +struct vec_internal { + size_t length; + size_t capacity; + void *els; + char storage[1]; // must be at least one byte so vec_free works correctly +}; + +#ifdef __cplusplus +extern "C" { +#endif + +void vec_realloc_internal(struct vec_internal *vi, size_t new_capacity, + size_t esize); +void vec_realloc_internal_as_necessary(struct vec_internal *vi, + size_t min_capacity, + size_t esize); +#ifdef __cplusplus +} +#endif + +#define DECL_VEC(ty, name) \ + typedef ty __VEC_TY_##name; \ + struct vec_##name { \ + union { \ + struct vec_internal vi; \ + struct { \ + size_t length; \ + size_t capacity; \ + VEC_TY(name) *els; \ + VEC_TY(name) storage[1]; \ + }; \ + }; \ + }; \ + UNUSED_STATIC_INLINE \ + void vec_free_storage(struct vec_##name *v) { \ + if (v->els != v->storage) \ + free(v->els); \ + } \ + UNUSED_STATIC_INLINE \ + struct vec_##name vec_borrow(VEC_TY(name) *els, size_t length) { \ + struct vec_##name v; \ + v.length = v.capacity = length; \ + v.els = els; \ + return v; \ + } \ + UNUSED_STATIC_INLINE \ + void vec_realloc_##name(struct vec_##name *v, size_t new_capacity) { \ + vec_realloc_internal(&v->vi, new_capacity, sizeof(v->els[0])); \ + } \ + UNUSED_STATIC_INLINE \ + void vec_resize_##name(struct vec_##name *v, size_t new_length) { \ + if (new_length >= v->capacity || new_length < v->capacity / 3) \ + vec_realloc_internal_as_necessary(&v->vi, new_length, sizeof(v->els[0])); \ + v->length = new_length; \ + } \ + UNUSED_STATIC_INLINE \ + VEC_TY(name) *vec_appendp_##name(struct vec_##name *v) { \ + size_t i = v->length++; \ + if (i == v->capacity) \ + vec_realloc_internal_as_necessary(&v->vi, i + 1, sizeof(v->els[0])); \ + return &v->els[i]; \ + } \ + UNUSED_STATIC_INLINE \ + void vec_append_##name(struct vec_##name *v, VEC_TY(name) val) { \ + *vec_appendp_##name(v) = val; \ + } \ + UNUSED_STATIC_INLINE \ + void vec_concat_##name(struct vec_##name *v1, const struct vec_##name *v2) { \ + size_t l1 = v1->length, l2 = v2->length; \ + vec_resize_##name(v1, safe_add(l1, l2)); \ + memcpy(&v1->els[l1], v2->els, l2 * sizeof(v1->els[0])); \ + } \ + UNUSED_STATIC_INLINE \ + void vec_add_space_##name(struct vec_##name *v, size_t idx, size_t num) { \ + /* todo optimize */ \ + size_t orig = v->length; \ + vec_resize_##name(v, orig + num); \ + memmove(&v->els[idx + num], &v->els[idx], \ + (orig - idx) * sizeof(v->els[0])); \ + } \ + UNUSED_STATIC_INLINE \ + void vec_remove_##name(struct vec_##name *v, size_t idx, size_t num) { \ + /* todo optimize */ \ + size_t orig = v->length; \ + memmove(&v->els[idx], &v->els[idx + num], \ + (orig - (idx + num)) * sizeof(v->els[0])); \ + vec_resize_##name(v, orig - num); \ + } \ + + +#define VEC_TY(name) __VEC_TY_##name + +#define VEC_STORAGE_CAPA(name, n) \ + struct { \ + struct vec_##name v; \ + VEC_TY(name) rest[(n)-1]; \ + } + +#define VEC_STORAGE(ty) \ + VEC_STORAGE_CAPA(ty, 5) + +#define VEC_STORAGE_INIT(vs, name) do { \ + struct vec_##name *v = &(vs)->v; \ + v->length = 0; \ + v->capacity = (sizeof((vs)->rest) / sizeof(VEC_TY(name))) + 1; \ + v->els = v->storage; \ +} while (0) + + +/* guaranteed to *not* cache vec->length - pretty simple */ + +#define VEC_FOREACH(vec, idx_var, ptr_var, name) \ + LET(struct vec_##name *__vfe_v = (vec)) \ + for (size_t idx_var = 0; idx_var < __vfe_v->length; idx_var++) \ + LET_LOOP(ptr_var = &__vfe_v->els[idx_var]) + diff --git a/test/test-vec.cpp b/test/test-vec.cpp new file mode 100644 index 0000000..f587c1b --- /dev/null +++ b/test/test-vec.cpp @@ -0,0 +1,23 @@ +#include "cbit/vec.h" +#include <stdio.h> +DECL_VEC(const char *, ccp); + +int main() { + VEC_STORAGE(ccp) stor; + VEC_STORAGE_INIT(&stor, ccp); + struct vec_ccp *vec = &stor.v; + for (int i = 0; i < 20; i++) { + char *x; + asprintf(&x, "el%d", i); + vec_append_ccp(vec, x); + } + vec_remove_ccp(vec, 5, 4); + vec_add_space_ccp(vec, 9, 2); + for (int i = 9; i <= 10; i++) + vec->els[i] = "TILT"; + vec_concat_ccp(vec, vec); + VEC_FOREACH(vec, i, const char **c, ccp) { + printf("%zd->%s\n", i, *c); + } + +} |