1 files changed, 121 insertions, 101 deletions

diff --git a/data_structures.c b/data_structures.c
index 9bab854..e16ea0d 100644
--- a/data_structures.c
+++ b/data_structures.c
@@ -23,7 +23,6 @@ OTHER DEALINGS IN THE SOFTWARE.
 For more information, please refer to <http://unlicense.org/>
 */
 
-/* OPTIM: is it faster to store void *end? */
 typedef struct ArrHeader {
 	size_t len;
 	size_t cap;
@@ -31,8 +30,7 @@ typedef struct ArrHeader {
 } ArrHeader;
 
 static inline ArrHeader *arr_hdr(void *arr) {
-	ArrHeader *hdr = (ArrHeader *)((char *)arr - offsetof(ArrHeader, data));
-	return hdr;
+	return (ArrHeader *)((char *)arr - offsetof(ArrHeader, data));
 }
 
 static inline size_t arr_len(void *arr) {
@@ -44,96 +42,114 @@ static inline void arr_zero_(void *arr, size_t item_sz) {
 	memset(arr, 0, item_sz * arr_len(arr));
 }
 
-static void arr_resv_(void **arr, size_t n, size_t item_sz) {
-	if (*arr == NULL) {
-		ArrHeader *hdr = err_malloc(item_sz * n + sizeof(ArrHeader) + 1); /* +1 => prevent ptr overflow */
+static WarnUnusedResult void *arr_resv_(void *arr, size_t n, size_t item_sz) {
+	ArrHeader *hdr;
+	if (arr == NULL) {
+		hdr = err_malloc(item_sz * n + sizeof(ArrHeader));
 		hdr->len = 0;
 		hdr->cap = n;
-		*arr = hdr->data;
 	} else {
-		ArrHeader *hdr = arr_hdr(*arr);
+		hdr = arr_hdr(arr);
 		hdr->cap = n;
-		hdr = err_realloc(hdr, item_sz * n + sizeof(ArrHeader) + 1);
+		hdr = err_realloc(hdr, item_sz * n + sizeof(ArrHeader));
 		if (hdr->len > hdr->cap) hdr->len = hdr->cap;
-		*arr = hdr->data;
 	}		
+	return hdr->data;
 }
-static void arr_resva_(void **arr, size_t n, size_t item_sz, Allocator *a) {
-	if (*arr == NULL) {
-		ArrHeader *hdr = allocr_malloc(a, item_sz * n + sizeof(ArrHeader));
+static WarnUnusedResult void *arr_resva_(void *arr, size_t n, size_t item_sz, Allocator *a) {
+	ArrHeader *hdr;
+	if (arr == NULL) {
+		hdr = allocr_malloc(a, item_sz * n + sizeof(ArrHeader));
 		hdr->len = 0;
 		hdr->cap = n;
-		*arr = hdr->data;
 	} else {
-		ArrHeader *hdr = arr_hdr(*arr);
+		hdr = arr_hdr(arr);
 		hdr = allocr_realloc(a, hdr, item_sz * hdr->cap + sizeof(ArrHeader), item_sz * n + sizeof(ArrHeader));
 		hdr->cap = n;
 		if (hdr->len > hdr->cap) hdr->len = hdr->cap;
-		*arr = hdr->data;
-	}		
+	}
+	return hdr->data;
 }
 
-static void arr_clear_(void **arr) {
-	if (*arr) {
-		free(arr_hdr(*arr));
-		*arr = NULL;
+
+/* accommodate one more element if necessary */
+static WarnUnusedResult void *arr_grow(void *arr, size_t item_sz) {
+	ArrHeader *hdr;
+	if (arr == NULL) {
+		hdr = err_malloc(sizeof *hdr + item_sz);
+		hdr->len = 0;
+		hdr->cap = 1;
+	} else {
+		hdr = arr_hdr(arr);
+		if (hdr->len >= hdr->cap) {
+			size_t new_size = sizeof *hdr + item_sz * (hdr->cap *= 2);
+			hdr = err_realloc(hdr, new_size);
+		}
 	}
+	return hdr->data;
 }
 
-static void arr_cleara_(void **arr, size_t size, Allocator *allocr) {
-	if (*arr) {
-		ArrHeader *header = arr_hdr(*arr);
+static WarnUnusedResult void *arr_growa(void *arr, size_t item_sz, Allocator *allocr) {
+	ArrHeader *hdr;
+	if (arr == NULL) {
+		hdr = allocr_malloc(allocr, sizeof *hdr + item_sz);
+		hdr->len = 0;
+		hdr->cap = 1;
+	} else {
+		hdr = arr_hdr(arr);
+		if (hdr->len >= hdr->cap) {
+			size_t old_size = sizeof *hdr + item_sz * hdr->cap;
+			size_t new_size = sizeof *hdr + item_sz * hdr->cap * 2;
+			hdr = allocr_realloc(allocr, hdr, old_size, new_size);
+			hdr->cap *= 2;
+		}
+	}
+	return hdr->data;
+}
+
+static WarnUnusedResult void *arr_clear_(void *arr) {
+	if (arr) {
+		free(arr_hdr(arr));
+	}
+	return NULL;
+}
+
+static WarnUnusedResult void *arr_cleara_(void *arr, size_t size, Allocator *allocr) {
+	if (arr) {
+		ArrHeader *header = arr_hdr(arr);
 		allocr_free(allocr, header, header->cap * size);
-		*arr = NULL;
 	}
+	return NULL;
 }
 
-static void arr_set_len_(void **arr, size_t n, size_t item_sz) {
+static WarnUnusedResult void *arr_set_len_(void *arr, size_t n, size_t item_sz) {
 	if (n == 0) {
-		arr_clear_(arr);
-		return;
+		return arr_clear_(arr);
 	}
-	if (n > arr_len(*arr)) {
-		arr_resv_(arr, n, item_sz);
+	if (n > arr_len(arr)) {
+		arr = arr_resv_(arr, n, item_sz);
 	}
-	arr_hdr(*arr)->len = n;
-	/* OPTIM: shrink */
+	arr_hdr(arr)->len = n;
+	/* @OPTIM: shrink */
+	return arr;
 }
-static void arr_set_lena_(void **arr, size_t n, size_t item_sz, Allocator *a) {
+static WarnUnusedResult void *arr_set_lena_(void *arr, size_t n, size_t item_sz, Allocator *a) {
 	if (n == 0) {
-		arr_cleara_(arr, item_sz, a);
-		return;
+		return arr_cleara_(arr, item_sz, a);
 	}
-	arr_resva_(arr, n, item_sz, a);
-	arr_hdr(*arr)->len = n;
+	arr = arr_resva_(arr, n, item_sz, a);
+	arr_hdr(arr)->len = n;
+	return arr;
 }
 
-static void *arr_add_(void **arr, size_t item_sz) {
-	ArrHeader *hdr;
-	if (*arr == NULL) {
-		arr_resv_(arr, 1, item_sz);
-		hdr = arr_hdr(*arr);
-	} else {
-		hdr = arr_hdr(*arr);
-		if (hdr->len >= hdr->cap) {
-			arr_resv_(arr, hdr->len * 2 + 1, item_sz);
-			hdr = arr_hdr(*arr);
-		}
-	}
+static void *arr_add_ptr_(void **arr, size_t item_sz) {
+	*arr = arr_grow(*arr, item_sz);
+	ArrHeader *hdr = arr_hdr(*arr);
 	return &(((char *)hdr->data)[(hdr->len++) * item_sz]);
 }
-static void *arr_adda_(void **arr, size_t item_sz, Allocator *a) {
-	ArrHeader *hdr;
-	if (*arr == NULL) {
-		arr_resva_(arr, 10, item_sz, a);
-		hdr = arr_hdr(*arr);
-	} else {
-		hdr = arr_hdr(*arr);
-		if (hdr->len >= hdr->cap) {
-			arr_resva_(arr, hdr->len * 2 + 1, item_sz, a);
-			hdr = arr_hdr(*arr);
-		}
-	}
+static void *arr_adda_ptr_(void **arr, size_t item_sz, Allocator *a) {
+	*arr = arr_growa(*arr, item_sz, a);
+	ArrHeader *hdr = arr_hdr(*arr);
 	return &(((char *)hdr->data)[(hdr->len++) * item_sz]);
 }
 
@@ -156,35 +172,35 @@ static void *arr_end_(void *arr, size_t item_sz) {
 	}
 }
 
-/* OPTIM: shrink array */
-static void arr_remove_last_(void **arr) {
-	assert(arr_hdr(*arr)->len);
-	if (--arr_hdr(*arr)->len == 0) {
-		arr_clear_(arr);
+/* @OPTIM: shrink array */
+static WarnUnusedResult void *arr_remove_last_(void *arr) {
+	assert(arr_hdr(arr)->len);
+	if (--arr_hdr(arr)->len == 0) {
+		return arr_clear_(arr);
 	}
+	return arr;
 }
 
-static void arr_remove_lasta_(void **arr, size_t item_sz, Allocator *a) {
-	assert(arr_hdr(*arr)->len);
-	if (--arr_hdr(*arr)->len == 0) {
-		arr_cleara_(arr, item_sz, a);
+static WarnUnusedResult void *arr_remove_lasta_(void *arr, size_t item_sz, Allocator *a) {
+	assert(arr_hdr(arr)->len);
+	if (--arr_hdr(arr)->len == 0) {
+		return arr_cleara_(arr, item_sz, a);
 	}
+	return arr;
 }
 
 
 
-static void arr_copya_(void **out, void *in, size_t item_sz, Allocator *a) {
+static WarnUnusedResult void *arr_copya_(void *out, void *in, size_t item_sz, Allocator *a) {
 	size_t len = arr_len(in);
-	arr_resva_(out, len, item_sz, a);
-	memcpy(*out, in, len * item_sz);
+	out = arr_resva_(out, len, item_sz, a);
+	memcpy(out, in, len * item_sz);
+	return out;
 }
 
-#ifdef __GNUC__
-#define typeof __typeof__
-#endif
-
 #if defined(__GNUC__) || defined(__TINYC__)
 #define HAS_TYPEOF 1
+#define typeof __typeof__
 #endif
 
 #if HAS_TYPEOF
@@ -193,38 +209,42 @@ this is to cast the return value of arr_add so that gcc produces a warning if yo
 do something like:
 float *arr = NULL;
 // ...
-int *x = arr_add(&arr);
+int *x = arr_add_ptr(&arr);
 You shouldn't rely on this, though, e.g. by doing
-*arr_add(&arr) = 17;
+*arr_add_ptr(&arr) = 17;
  */
-#define arr_ptr_type(arr) __typeof__(*(arr))
+#define arr_ptr_type(arr) typeof(arr)
 #else
 #define arr_ptr_type(arr) void *
 #endif
 
 #define arr_zero(arr) arr_zero_(arr, sizeof *(arr))
-#define arr_add(arr) (arr_ptr_type(arr))arr_add_((void **)(arr), sizeof **(arr))
-#define arr_adda(arr, allocr) (arr_ptr_type(arr))arr_adda_((void **)(arr), sizeof **(arr), (allocr))
-#define arr_resv(arr, n) arr_resv_((void **)(arr), n, sizeof **(arr))
-#define arr_resva(arr, n, allocr) arr_resva_((void **)(arr), n, sizeof **(arr), (allocr))
-#define arr_set_len(arr, n) arr_set_len_((void **)(arr), n, sizeof **(arr))
-#define arr_set_lena(arr, n, a) arr_set_lena_((void **)(arr), n, sizeof **(arr), (a))
-#define arr_clear(arr) arr_clear_((void **)(arr)), (void)sizeof **arr /* second part makes sure most of the time that you don't accidentally call it without taking the address */
-#define arr_cleara(arr, allocr) arr_cleara_((void **)(arr), sizeof **(arr), (allocr))
-#define arr_last(arr) arr_last_((void *)(arr), sizeof *(arr))
+#define arr_add(arr, x) arr = arr_grow((arr), sizeof *(arr)), (arr)[arr_hdr(arr)->len++] = x
+#define arr_add_ptr(arr) (arr_ptr_type(arr))arr_add_ptr_((void **)(&arr), sizeof *(arr))
+#define arr_adda(arr, x, allocr) arr = arr_growa((arr), sizeof *(arr), (allocr)), (arr)[arr_hdr(arr)->len++] = x
+#define arr_adda_ptr(arr, allocr) (arr_ptr_type(arr))arr_adda_ptr_((void **)(&arr), sizeof *(arr), (allocr))
+#define arr_resv(arr, n) arr = arr_resv_((arr), n, sizeof *(arr))
+#define arr_resva(arr, n, allocr) arr = arr_resva_((arr), n, sizeof *(arr), (allocr))
+#define arr_set_len(arr, n) arr = arr_set_len_((arr), n, sizeof *(arr))
+#define arr_set_lena(arr, n, allocr) arr = arr_set_lena_((arr), n, sizeof *(arr), (allocr))
+#define arr_clear(arr) arr = arr_clear_(arr)
+#define arr_cleara(arr, allocr) arr = arr_cleara_((arr), sizeof *(arr), (allocr))
+#define arr_last(arr) arr[arr_len(arr)-1]
+#define arr_last_ptr(arr) arr_last_((arr), sizeof *(arr))
 /* one past last, or NULL if empty */
-#define arr_end(arr) arr_end_((void *)(arr), sizeof *(arr))
+#define arr_end(arr) arr_end_((arr), sizeof *(arr))
 #define arr_foreach(arr, type, var) for (type *var = (arr), *var##_foreach_end = arr_end(arr); var != var##_foreach_end; ++var)
-#define arr_foreach_reversed(arr, type, var) for (type *var = arr_last(arr), *var##_foreach_last = arr; var; var = var == var##_foreach_last ? NULL : (var-1))
-#define arr_remove_last(arr) arr_remove_last_((void **)(arr)), (void)sizeof **(arr)
-#define arr_remove_lasta(arr, a) arr_remove_lasta_((void **)(arr), sizeof **(arr), (a))
-#define arr_copya(out, in, a) do { assert(sizeof *(in) == sizeof **(out)); arr_copya_((void **)(out), (in), sizeof **(out), (a)); } while(0)
+#define arr_foreach_reversed(arr, type, var) for (type *var = arr_last_ptr(arr), *var##_foreach_last = arr; var; var = var == var##_foreach_last ? NULL : (var-1))
+#define arr_remove_last(arr) arr = arr_remove_last_(arr)
+#define arr_remove_lasta(arr, allocr) arr = arr_remove_lasta_((arr), sizeof *(arr), (allocr))
+#define arr_copya(out, in, allocr) do { assert(sizeof *(in) == sizeof *(out)); out = arr_copya_((out), (in), sizeof *(out), (allocr)); } while(0)
 
-#ifdef RUN_TESTS
+#if RUN_TESTS
+/* @TODO(eventually): more extensive test? */
 static void arr_test(void) {
 	int *foos = NULL;
 	for (int i = 0; i < 10; ++i) {
-		*(int *)arr_add(&foos) = i;
+		arr_add(foos, i);
 	}
 	for (int i = 0; i < (int)arr_len(foos); ++i) {
 		assert(foos[i] == i);
@@ -234,7 +254,7 @@ static void arr_test(void) {
 		assert(*x == lastx + 1);
 		lastx = *x;
 	}
-	arr_clear(&foos);
+	arr_clear(foos);
 }
 #endif
 
@@ -281,7 +301,7 @@ static void str_hash_table_grow(StrHashTable *t) {
 	if (slots_cap <= 2 * t->nentries) {
 		StrHashTableSlot **new_slots = NULL;
 		size_t new_slots_cap = slots_cap * 2 + 10;
-		arr_set_lena(&new_slots, new_slots_cap, t->allocr);
+		arr_set_lena(new_slots, new_slots_cap, t->allocr);
 		arr_zero(new_slots);
 		arr_foreach(t->slots, StrHashTableSlotPtr, slotp) {
 			StrHashTableSlot *slot = *slotp;
@@ -291,7 +311,7 @@ static void str_hash_table_grow(StrHashTable *t) {
 				*new_slot = slot;
 			}
 		}
-		arr_cleara(&t->slots, t->allocr);
+		arr_cleara(t->slots, t->allocr);
 		t->slots = new_slots;
 	}
 }
@@ -341,7 +361,7 @@ static void str_hash_table_free(StrHashTable *t) {
 	arr_foreach(t->slots, StrHashTableSlotPtr, slotp) {
 		allocr_free(t->allocr, *slotp, str_hash_table_slot_size(t));
 	}
-	arr_cleara(&t->slots, t->allocr);
+	arr_cleara(t->slots, t->allocr);
 }
 
 static StrHashTableSlot *str_hash_table_get_(StrHashTable *t, const char *str, size_t len) {
@@ -357,7 +377,7 @@ static inline void *str_hash_table_get(StrHashTable *t, const char *str, size_t
 	return slot->data;
 }
 
-#ifdef RUN_TESTS
+#if RUN_TESTS
 static void str_hash_table_test(void) {
 	StrHashTable t;
 	str_hash_table_create(&t, sizeof(int), NULL);