Merge pull request #213 from jow-/improve-vector-macros

utils: improve vector macros

1 files changed, 135 insertions, 63 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 */