utils: improve vector utilities

This commits introduces a number of new helper macros to deal with vectors
and refactors the existing code for better resource utilization.

The allocation strategy is changed from multiple of 8 to exponential growth
by factor 1.5 in order to minimize the number of reallocations and
potentially needed memory copies.

The newly introduced macros are:

 - uc_vector_capacity(init_capacity, add_items)
   Derive the resulting vector capacity from the given item count
   and initial capacity.

 - uc_vector_extend(vector, add_items)
   Increase vector capacity by given amount of items, zero-initialize
   added capacity and return pointer to first new item past the current
   length.

 - uc_vector_reduce(vector, remove_items)
   Reduce vector capacity by given amount of items.

 - uc_vector_pop(vector)
   Return pointer to last element and decrement count, or NULL if the
   vector is empty.

 - uc_vector_foreach(vector, itervar)
   A for() loop wrapper to iterate vectors, providing an iter variable
   to the loop body.

 - uc_vector_foreach_reverse(vector, itervar)
   A for() loop wrapper to iterate vectors backwards, providing an iter
   variable to the loop body.

The uc_vector_push() macro has been changed into a variadic macro which
internally prefixes the argument list with a cast to the vector element
type, allowing user to pass compound expressions like struct initializers
in order to simplify adding elements:

    uc_vector_push(&my_collection, {
        .foo = 1,
        .bar = "qrx"
    });

Like uc_vector_pop(), the uc_vector_last() macro has been made safe to
use on empty vectors, it'll now return NULL in this case.

Finally the vector realloc logic was moved into static functions within
the header file, allowing all vector using code of a compilation unit to
share the reallocation, shrinking the size of libucode.so by 1-2KB as a
side effect.

Signed-off-by: Jo-Philipp Wich <jo@mein.io>

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 */
diff --git a/types.c b/types.c
index 84a7b17..382e49a 100644
--- a/types.c
+++ b/types.c
@@ -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;
 }