diff options
| -rw-r--r-- | include/ucode/util.h | 198 | ||||
| -rw-r--r-- | types.c | 36 |
2 files changed, 144 insertions, 90 deletions
diff --git a/include/ucode/util.h b/include/ucode/util.h index a3692d5..cc92e33 100644 --- a/include/ucode/util.h +++ b/include/ucode/util.h @@ -30,6 +30,14 @@ #define __hidden __attribute__((visibility("hidden"))) #endif +#ifndef localfunc +# if defined(__GNUC__) || defined(__clang__) +# define localfunc static __attribute__((noinline,unused)) +# else +# define localfunc static inline +# endif +#endif + /* alignment & array size */ @@ -42,69 +50,6 @@ #endif -/* vector macros */ - -#define UC_VECTOR_CHUNK_SIZE 8 - -#define uc_declare_vector(name, type) \ - typedef struct { \ - size_t count; \ - type *entries; \ - } name - -#define uc_vector_grow(vec) \ - do { \ - if (((vec)->count % UC_VECTOR_CHUNK_SIZE) == 0) { \ - (vec)->entries = xrealloc((vec)->entries, sizeof((vec)->entries[0]) * ((vec)->count + UC_VECTOR_CHUNK_SIZE)); \ - memset(&(vec)->entries[(vec)->count], 0, sizeof((vec)->entries[0]) * UC_VECTOR_CHUNK_SIZE); \ - } \ - } while(0) - -#define uc_vector_clear(vec) \ - do { \ - free((vec)->entries); \ - (vec)->entries = NULL; \ - (vec)->count = 0; \ - } while(0) - -#define uc_vector_first(vec) \ - (&((vec)->entries[0])) - -#define uc_vector_last(vec) \ - (&((vec)->entries[(vec)->count - 1])) - -#define uc_vector_push(vec, val) do { \ - uc_vector_grow(vec); \ - (vec)->entries[(vec)->count++] = (val); \ -} while(0) - - -/* linked lists */ - -typedef struct uc_list { - struct uc_list *prev; - struct uc_list *next; -} uc_list_t; - -static inline void uc_list_insert(uc_list_t *list, uc_list_t *item) -{ - list->next->prev = item; - item->next = list->next; - item->prev = list; - list->next = item; -} - -static inline void uc_list_remove(uc_list_t *item) -{ - item->next->prev = item->prev; - item->prev->next = item->next; - item->prev = item->next = item; -} - -#define uc_list_foreach(item, list) \ - for (uc_list_t *item = (list)->next; item != (list); item = item->next) - - /* "failsafe" utility functions */ static inline void *xcalloc(size_t size, size_t nmemb) { @@ -195,4 +140,131 @@ static inline struct printbuf *xprintbuf_new(void) { return pb; } + +/* linked lists */ + +typedef struct uc_list { + struct uc_list *prev; + struct uc_list *next; +} uc_list_t; + +static inline void uc_list_insert(uc_list_t *list, uc_list_t *item) +{ + list->next->prev = item; + item->next = list->next; + item->prev = list; + list->next = item; +} + +static inline void uc_list_remove(uc_list_t *item) +{ + item->next->prev = item->prev; + item->prev->next = item->next; + item->prev = item->next = item; +} + +#define uc_list_foreach(item, list) \ + for (uc_list_t *item = (list)->next; item != (list); item = item->next) + + +/* vector macros */ + +#define UC_VECTOR_INIT_SIZE 8 + +#define uc_declare_vector(name, type) \ + typedef struct { \ + size_t count; \ + type *entries; \ + } name + +localfunc size_t +uc_vector_capacity(size_t init, size_t count) +{ + if (count == 0) + return init; + + size_t capacity = init; + + while (capacity <= count) + capacity += (capacity >> 1); + + return capacity; +} + +localfunc void +uc_vector_reduce_(char **base, size_t itemsize, size_t count, size_t remove) +{ + if (*base == NULL) + return; + + if (remove > count) + remove = count; + + size_t next_capacity = uc_vector_capacity(UC_VECTOR_INIT_SIZE, count - remove); + + if (uc_vector_capacity(next_capacity, count) != next_capacity) + *base = (__typeof__(*base))xrealloc(*base, itemsize * next_capacity); +} + +localfunc void * +uc_vector_extend_(char **base, size_t itemsize, size_t count, size_t add) +{ + size_t curr_capacity = uc_vector_capacity(UC_VECTOR_INIT_SIZE, count); + + if (*base == NULL || count + add >= curr_capacity) { + size_t next_capacity = uc_vector_capacity(curr_capacity, count + add); + + *base = (__typeof__(*base))xrealloc(*base, itemsize * next_capacity); + + memset(*base + itemsize * count, 0, + itemsize * (next_capacity - count)); + } + + return *base + itemsize * count; +} + +#define uc_vector_reduce(vec, remove) \ + uc_vector_reduce_((char **)&(vec)->entries, sizeof((vec)->entries[0]), (vec)->count, (remove)) + +#define uc_vector_extend(vec, add) \ + (__typeof__((vec)->entries + 0)) uc_vector_extend_( \ + (char **)&(vec)->entries, \ + sizeof((vec)->entries[0]), \ + (vec)->count, (add)) + +#define uc_vector_grow(vec) \ + uc_vector_extend_((char **)&(vec)->entries, sizeof((vec)->entries[0]), (vec)->count, 1) + +#define uc_vector_clear(vec) \ + do { \ + free((vec)->entries); \ + (vec)->entries = NULL; \ + (vec)->count = 0; \ + } while(0) + +#define uc_vector_first(vec) \ + (&((vec)->entries[0])) + +#define uc_vector_last(vec) \ + ((vec)->count ? &((vec)->entries[(vec)->count - 1]) : NULL) + +#define uc_vector_push(vec, ...) ({ \ + *uc_vector_extend((vec), 1) = ((__typeof__((vec)->entries[0]))__VA_ARGS__); \ + &(vec)->entries[(vec)->count++]; \ +}) + +#define uc_vector_pop(vec) \ + ((vec)->count ? &(vec)->entries[--(vec)->count] : NULL) + +#define uc_vector_foreach(vec, iter) \ + for (__typeof__((vec)->entries + 0) iter = (vec)->entries; \ + iter < (vec)->entries + (vec)->count; \ + iter++) + +#define uc_vector_foreach_reverse(vec, iter) \ + for (__typeof__((vec)->entries + 0) iter = (vec)->count \ + ? (vec)->entries + (vec)->count - 1 : NULL; \ + iter != NULL && iter >= (vec)->entries; \ + iter--) + #endif /* UCODE_UTIL_H */ @@ -705,17 +705,13 @@ ucv_array_new_length(uc_vm_t *vm, size_t length) { uc_array_t *array; - /* XXX */ - length = 0; - - array = xalloc(sizeof(*array) + length * sizeof(array->entries[0])); + array = xalloc(sizeof(*array)); array->header.type = UC_ARRAY; array->header.refcount = 1; - if (length > 0) - array->count = length; - - uc_vector_grow(array); + /* preallocate memory */ + if (length) + uc_vector_extend(array, length); if (vm) { ucv_ref(&vm->values, &array->ref); @@ -779,10 +775,9 @@ ucv_array_unshift(uc_value_t *uv, uc_value_t *item) if (ucv_type(uv) != UC_ARRAY) return NULL; - array->count++; - uc_vector_grow(array); + uc_vector_extend(array, 1); - for (i = array->count; i > 1; i--) + for (i = ++array->count; i > 1; i--) array->entries[i - 1] = array->entries[i - 2]; array->entries[0] = item; @@ -826,10 +821,9 @@ ucv_array_delete(uc_value_t *uv, size_t offset, size_t count) &array->entries[offset + count], (array->count - (offset + count)) * sizeof(array->entries[0])); + uc_vector_reduce(array, count); array->count -= count; - uc_vector_grow(array); - return true; } @@ -837,24 +831,13 @@ bool ucv_array_set(uc_value_t *uv, size_t index, uc_value_t *item) { uc_array_t *array = (uc_array_t *)uv; - size_t old_count, new_count; if (ucv_type(uv) != UC_ARRAY) return false; if (index >= array->count) { - old_count = array->count; - new_count = (index + 1) & ~(UC_VECTOR_CHUNK_SIZE - 1); - - if (new_count > old_count) { - array->count = new_count; - uc_vector_grow(array); - } - + uc_vector_extend(array, index + 1 - array->count); array->count = index + 1; - - while (old_count < array->count) - array->entries[old_count++] = NULL; } else { ucv_put(array->entries[index]); @@ -1116,8 +1099,7 @@ ucv_resource_type_add(uc_vm_t *vm, const char *name, uc_value_t *proto, void (*f type->proto = proto; type->free = freefn; - uc_vector_grow(&vm->restypes); - vm->restypes.entries[vm->restypes.count++] = type; + uc_vector_push(&vm->restypes, type); return type; } |