moved all containers to a single header "container.h"

TODO: add linked list, hash map and other shit like this to the header

5 files changed, 236 insertions, 128 deletions

diff --git a/Makefile b/Makefile
index 0fb81ad..2bb58db 100644
--- a/Makefile
+++ b/Makefile
@@ -6,15 +6,17 @@ CFLAGS := -g -Wall -Wextra -Wpedantic -Werror -Wno-language-extension-token
 tests: dynarray
 
 
-dynarray: tests/dynarray.c
-	$(CC) $(CFLAGS) -o $@ $^ -DTT_CHAR
+dynarray: tests/dynarray.c tests/dynarray_struct.c
+	$(CC) $(CFLAGS) -o $@ $< -DTT_CHAR
 	./dynarray
-	$(CC) $(CFLAGS) -o $@ $^ -DTT_SHORT
+	$(CC) $(CFLAGS) -o $@ $< -DTT_SHORT
 	./dynarray
-	$(CC) $(CFLAGS) -o $@ $^ -DTT_INT
+	$(CC) $(CFLAGS) -o $@ $< -DTT_INT
 	./dynarray
-	$(CC) $(CFLAGS) -o $@ $^ -DTT_LONG
+	$(CC) $(CFLAGS) -o $@ $< -DTT_LONG
+	./dynarray
+	$(CC) $(CFLAGS) -o $@ tests/dynarray_struct.c
 	./dynarray
 
-	rm dynarray
+	rm $@
 
diff --git a/include/dynarray.h b/include/container.h
index 79b548e..775ffc2 100644
--- a/include/dynarray.h
+++ b/include/container.h
@@ -1,22 +1,65 @@
-#ifndef JUSTANOTHERCATGIRL_HEADERS_DYNARRAY
-#define JUSTANOTHERCATGIRL_HEADERS_DYNARRAY
-
-//! A dynamic array implementation
-//! As this is a header-only library, you have to define `DYNARRAY_IMPLEMENTATION` macro the first time you include this
-//! header. This implementation uses the idea of storing metadata to the left of the array data, so that the user can
-//! think of it (and use it) as normal array. Most of the API functions are defined as macros that either do some work
-//! or call the implementation. They are not all-caps because they are more like functions.
-//! As source is the best documentation, you should check yourself what is macro and what is not. generally, everything
-//! prefixed with `array_` is a macro. Some of the macros evaluate their arguments more than once (the multiline ones), 
-//! so as a rule of thumb, you should only ever pass evaluated identifiers or expressions with no side-effects (like `ptr+2`)
-//! to all of the macros in this library.
-
-#include "utility.h"
+#ifndef JUSTANOTHERCATGIRL_HEADERS_CONTAINER
+#define JUSTANOTHERCATGIRL_HEADERS_CONTAINER
+
 #include <assert.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 
+
+
+/* ----------------------------------------------------------------- */
+/* -----------------UTILITY HEADER---------------------------------- */
+/* ----------------------------------------------------------------- */
+#define stringify(val) _stringify_helper(val)
+#define _stringify_helper(val) #val
+#define string_concat_separator(first, ...) stringify(first) ";" string_concat_separator(__VA_ARGS__)
+
+#define struct_member_size(type, member) sizeof(( (type*)0 )->member)
+typedef unsigned char byte;
+
+#ifdef __GNUC__
+	#define upper_2_power_32(number) (32 - __builtin_clz(number))
+	#define upper_2_power_64(number) (64 - __builtin_clzl(number))
+#else
+	#include <intrin.h>
+	#include <stdint.h>
+	#define upper_2_power_32(number) __bit_scan_32(number)
+	#define upper_2_power_64(number) __bit_scan_64(number)
+	unsigned long __bit_scan_32(int32_t number);
+	unsigned long __bit_scan_64(int64_t number);
+#endif
+
+typedef int(*qsort_cmp_t)(const void*, const void*);
+#define get_qsort_cmp(type) __qsort_cmps[sizeof(type)]
+extern const qsort_cmp_t __qsort_cmps[64];
+
+#ifdef CONTAINER_EXPOSE_HELPERS
+	#define _CONTAINER_STATIC 
+	int __default_char_cmp(const void* a, const void* b);
+	int __default_short_cmp(const void* a, const void* b);
+	int __default_int_cmp(const void* a, const void* b);
+	int __default_long_cmp(const void* a, const void* b);
+	int __default_long_long_cmp(const void* a, const void* b);
+#else 
+	#define _CONTAINER_STATIC static
+#endif // CONTAINER_EXPOSE_HELPERS
+
+
+/* ----------------------------------------------------------------- */
+/* -------------------------ARRAY HEADER---------------------------- */
+/* ----------------------------------------------------------------- */
+/* A dynamic array implementation 
+ * As this is a header-only library, you have to define `CONTAINER_IMPLEMENTATION` macro the first time you include this
+ * header. This implementation uses the idea of storing metadata to the left of the array data, so that the user can
+ * think of it (and use it) as normal array. Most of the API functions are defined as macros that either do some work
+ * or call the implementation. They are not all-caps because they are more like functions.
+ * As source is the best documentation, you should check yourself what is macro and what is not. generally, everything
+ * prefixed with `array_` is a macro. Some of the macros evaluate their arguments more than once (the multiline ones), 
+ * so as a rule of thumb, you should only ever pass evaluated identifiers or expressions with no side-effects (like `ptr+2`)
+ * to all of the macros in this library.
+ */
+
 /// size of the array header. should not be used directly, unless you know what you are doing
 #define DYNARRAY_HEADER_SIZE sizeof(struct _dynarray_header)
 
@@ -49,36 +92,47 @@
 /// Note: `element` HAS to be of same type as the array during initialization. The expression has to be of the same type.
 /// That means calling `array_insert(arr, 0, 5)`, where array is of type `long`, WILL lead to errors. because typeof(0) is
 /// int, and it will put it in an `int` variable and copy 8 bytes from there, which will be some random stack garbage. 
-#define array_insert(array, element, idx)					\
-	do {									\
-		typeof(element) __tmp_el_var = (element);			\
-		array = _insert_to_index_dynarray(array, &__tmp_el_var, idx);	\
+#define array_insert(array, element, idx)								\
+	do {												\
+		typeof(element) __tmp_el_var = (element);						\
+		array = _insert_to_index_dynarray(array, &__tmp_el_var, sizeof(__tmp_el_var), idx);	\
 	} while(0)
 /// removes last element from the array
 #define array_pop(array) --array_header(array)->size
-/// reserve length elements so that subsequent (length - current_size) operations require no reallocation
+/// reserve length elements so that subsequent (length - current_size) pushes require no reallocation
 #define array_reserve(array, length) 	if (typeof(array) __tmp; (__tmp = _memreserve_dynarray(array, length)) != NULL) array = __tmp
-/// change size of an array. the capacity is set to lowest possible power of 2 that is greater than length
+/// change size of an array. the capacity is set to lowest power of 2 that is greater than length
 #define array_resize(array, length)	array = _force_resize_dynarray(array, length);
 /// set capacity to minimum possible value
 #define array_shrink(array)	array = _memshrink_array(array)
 /// bound-checks and returns a pointer to that element. on error returns NULL 
-#define array_at(array, idx)	(idx < array_size(array) ? (typeof(array))((byte*)array + idx*array_size(array)) : NULL)
+#define array_at(array, idx)	(idx < array_size(array) ? (void*)((byte*)array + idx*array_element_size(array)) : NULL)
 /// sorts the array using compare_func for comparison
 #define array_qsort(array, compare_func) qsort(array, array_size(array), array_element_size(array), compare_func)
 /// sorts the array using pre-defined compariton functions for signed integers based on size (1, 2, 4, 8)
 #define array_qsort_integral(array) array_qsort(array, __qsort_cmps[array_element_size(array)])
 /// Placed here because is not a macro. compares 2 arrays and returns the same way as `strcmp`
 int array_compare(const void *const a1, const void *const a2, qsort_cmp_t comp);
+/// Exact copy of the array. you have to free the pointer as well.
+void* array_copy(void* old);
+
+/* ----------------------------------------------------------------- */
+/* ----------------------LINKED LIST HEADER------------------------- */
+/* ----------------------------------------------------------------- */
+// TODO!
 
+/* ------------------------------------------------------------------------- */
+/* ------From now on, the rest of the header is implementation details------ */
+/* -------------------The API and documentation end here-------------------- */
+/* ------------------------------------------------------------------------- */
 
-/// for internal use
+// for internal use
 enum _dynarray_header_idx {
 	_dah_idx_member_size	= 0,
 	_dah_idx_capacity	= 1,
 	_dah_idx_size		= 2,
 };
-/// basically for structurization
+// for structurization
 struct _dynarray_header {
 	size_t memb_size;
 	size_t capacity;
@@ -92,10 +146,104 @@ void *_alloc_dynarray_buffer(size_t el_size, size_t alen, void *buffer, size_t b
 void *_force_resize_dynarray(void *dynarray, size_t new_size);
 void *_memreserve_dynarray(void *dynarray, size_t reserved);
 void *_memshrink_array(void *dynarray);
-void *_insert_to_index_dynarray(void *const dynarray, const void *const element, size_t index);
+void *_insert_to_index_dynarray(void *const dynarray, const void *const element, size_t el_size, size_t index);
+
+
+// uncomment in dev mode so that LSP highlights the code
+/*#define CONTAINER_IMPLEMENTATION*/
+#ifdef CONTAINER_IMPLEMENTATION
+
+/* ----------------------------------------------------------------- */
+/* ---------------------UTILITY IMPLEMENTATION---------------------- */
+/* ----------------------------------------------------------------- */
 
+#ifndef __GNUC__
+unsigned long __bit_scan_32(int32_t number) {
+	#ifdef _MSC_VER
+		unsigned long index;
+		if (_BitScanReverse(&index, number)) {
+			return index + 1;
+		} else {
+			return 1;
+		}
+	#else // _MSC_VER
+		unsigned long count;
+		for (count = 0; number; number >>= 1) { ++count; }
+		return count;
+	#endif // _MSC_VER
+}
+unsigned long __bit_scan_64(int64_t number) {
+	#ifdef _MSC_VER
+		unsigned long index;
+		if (_BitScanReverse64(&index, number)) {
+			return index + 1;
+		} else {
+			return 1;
+		}
+	#else // _MSC_VER
+		unsigned long count;
+		for (count = 0; number; number >>= 1) { ++count; }
+		return count;
+	#endif // _MSC_VER
+}
+#endif // __GNUC__
 
-#ifdef DYNARRAY_IMPLEMENTATION
+
+_CONTAINER_STATIC int __default_char_cmp(const void* a, const void* b) {
+	char x = *(char*)a, y = *(char*)b;
+	if (x < y) return -1;
+	if (x > y) return 1;
+	return 0;
+}
+_CONTAINER_STATIC int __default_short_cmp(const void* a, const void* b) {
+	short x = *(short*)a, y = *(short*)b;
+	if (x < y) return -1;
+	if (x > y) return 1;
+	return 0;
+}
+_CONTAINER_STATIC int __default_int_cmp(const void* a, const void* b) {
+	int x = *(int*)a, y = *(int*)b;
+	if (x < y) return -1;
+	if (x > y) return 1;
+	return 0;
+}
+_CONTAINER_STATIC  int __default_long_long_cmp(const void* a, const void* b) {
+	long long x = *(long long*)a, y = *(long long*)b;
+	if (x < y) return -1;
+	if (x > y) return 1;
+	return 0;
+}
+_CONTAINER_STATIC int __default_long_cmp(const void* a, const void* b) {
+	long x = *(long*)a, y = *(long*)b;
+	if (x < y) return -1;
+	if (x > y) return 1;
+	return 0;
+}
+
+#ifdef __GNUC__
+// cope
+#pragma GCC diagnostic ignored "-Woverride-init" // Is is meant to override it on different platforms
+const qsort_cmp_t __qsort_cmps[64] = {
+	[sizeof(char)] = __default_char_cmp,
+	[sizeof(short)] = __default_short_cmp,
+	[sizeof(int)] = __default_int_cmp,
+	[sizeof(long)] = __default_long_cmp,
+	[sizeof(long long)] = __default_long_long_cmp,
+	[63] = 0,
+};
+#pragma GCC diagnostic warning "-Woverride-init"
+#else 	// not __GNUC__
+const qsort_cmp_t __qsort_cmps[64] = {
+	0, 
+	__default_char_cmp, __default_short_cmp, 0, __default_int_cmp, 
+	0, 0, 0, __default_long_long_cmp,
+};
+#endif 	// __GNUC__
+
+
+/* ----------------------------------------------------------------- */
+/* ----------------------ARRAY IMPLEMENTATION----------------------- */
+/* ----------------------------------------------------------------- */
 
 void *_alloc_dynarray(size_t el_size, size_t len)
 {
@@ -158,13 +306,14 @@ void *_force_resize_dynarray(void * const dynarray, size_t new_size)
 	}
 }
 
-void *_insert_to_index_dynarray(void *const dynarray, const void *const element, size_t index) {
+void *_insert_to_index_dynarray(void *const dynarray, const void *const element, size_t el_size, size_t index) {
 	struct _dynarray_header* hdr = array_header(dynarray);
 	byte* array = (byte*) _memreserve_dynarray(dynarray, 1 << upper_2_power_64(hdr->size + 1));
 	hdr = array_header(array);
 	++hdr->size;
 	memmove(array + hdr->memb_size * (index+1), array + hdr->memb_size * (index), hdr->memb_size * (hdr->size - 1 - index));
-	memcpy(array + hdr->memb_size * index, element, hdr->memb_size);
+	if (el_size != hdr->memb_size) { /* TODO: warning? */ }
+	memcpy(array + hdr->memb_size * index, element, el_size);
 	return array;
 }
 
@@ -187,6 +336,11 @@ int array_compare(const void *const a1, const void *const a2, qsort_cmp_t comp)
 #undef 	NDEBUG
 }
 
-#endif // DYNARRAY_IMPLEMENTATION
+/*void* array_copy(void* old) {*/
+/*	//TODO!*/
+/*}*/
+
+
+#endif // CONTAINER_IMPLEMENTATION
 
-#endif // JUSTANOTHERCATGIRL_HEADERS_DYNARRAY
+#endif // JUSTANOTHERCATGIRL_HEADERS_CONTAINER
diff --git a/include/utility.h b/include/utility.h
deleted file mode 100644
index 85948cf..0000000
--- a/include/utility.h
+++ /dev/null
@@ -1,87 +0,0 @@
-#ifndef JUSTANOTHERCATGIRL_HEADERS_UTILITY
-#define JUSTANOTHERCATGIRL_HEADERS_UTILITY
-
-#define stringify(val) _stringify_helper(val)
-#define _stringify_helper(val) #val
-
-#define string_concat_separator(first, ...) stringify(first) ";" string_concat_separator(__VA_ARGS__)
-
-#define struct_member_size(type, member) sizeof(( (type*)0 )->member)
-typedef unsigned char byte;
-#define upper_2_power_32(number) (32 - __builtin_clz(number))
-#define upper_2_power_64(number) (64 - __builtin_clzl(number))
-
-typedef int(*qsort_cmp_t)(const void*, const void*);
-#define get_qsort_cmp(type) __qsort_cmps[sizeof(type)]
-extern const qsort_cmp_t __qsort_cmps[64];
-
-#ifdef UTILITY_EXPOSE_HELPERS
-	#define _UTILITY_STATIC 
-	int __default_char_cmp(const void* a, const void* b);
-	int __default_short_cmp(const void* a, const void* b);
-	int __default_int_cmp(const void* a, const void* b);
-	int __default_long_cmp(const void* a, const void* b);
-	int __default_long_long_cmp(const void* a, const void* b);
-#else 
-	#define _UTILITY_STATIC static
-#endif // UTILITY_EXPOSE_HELPERS
-
-
-#ifdef UTILITY_IMPLEMENTATION
-
-_UTILITY_STATIC int __default_char_cmp(const void* a, const void* b) {
-	char x = *(char*)a, y = *(char*)b;
-	if (x < y) return -1;
-	if (x > y) return 1;
-	return 0;
-}
-_UTILITY_STATIC int __default_short_cmp(const void* a, const void* b) {
-	short x = *(short*)a, y = *(short*)b;
-	if (x < y) return -1;
-	if (x > y) return 1;
-	return 0;
-}
-_UTILITY_STATIC int __default_int_cmp(const void* a, const void* b) {
-	int x = *(int*)a, y = *(int*)b;
-	if (x < y) return -1;
-	if (x > y) return 1;
-	return 0;
-}
-_UTILITY_STATIC  int __default_long_long_cmp(const void* a, const void* b) {
-	long long x = *(long long*)a, y = *(long long*)b;
-	if (x < y) return -1;
-	if (x > y) return 1;
-	return 0;
-}
-_UTILITY_STATIC int __default_long_cmp(const void* a, const void* b) {
-	long x = *(long*)a, y = *(long*)b;
-	if (x < y) return -1;
-	if (x > y) return 1;
-	return 0;
-}
-
-#ifdef __GNUC__
-// cope
-#pragma GCC diagnostic ignored "-Woverride-init" // Is is meant to override it on different platforms
-const qsort_cmp_t __qsort_cmps[64] = {
-	[sizeof(char)] = __default_char_cmp,
-	[sizeof(short)] = __default_short_cmp,
-	[sizeof(int)] = __default_int_cmp,
-	[sizeof(long)] = __default_long_cmp,
-	[sizeof(long long)] = __default_long_long_cmp,
-	[63] = 0,
-};
-#pragma GCC diagnostic warning "-Woverride-init"
-#else 	// not __GNUC__
-const qsort_cmp_t __qsort_cmps[64] = {
-	0, 
-	__default_char_cmp, __default_short_cmp, 0, __default_int_cmp, 
-	0, 0, 0, __default_long_long_cmp,
-};
-#endif 	// __GNUC__
-
-
-#endif // UTILITY_IMPLEMENTATION
-
-
-#endif //JUSTANOTHERCATGIRL_HEADERS_UTILITY
diff --git a/tests/dynarray.c b/tests/dynarray.c
index d7a79d7..2d9ea61 100644
--- a/tests/dynarray.c
+++ b/tests/dynarray.c
@@ -1,8 +1,6 @@
-#define DYNARRAY_IMPLEMENTATION
-#define UTILITY_IMPLEMENTATION
+#define CONTAINER_IMPLEMENTATION
 #define UTILTY_EXPOSE_HELPERS
-#include "../include/dynarray.h"
-#include "../include/utility.h"
+#include "../include/container.h"
 #include <stdio.h>
 #include <stdlib.h>
 
@@ -56,7 +54,8 @@ int main(void)
 	array_qsort_integral(arr);			// size: 5, cap: 5
 	/* qsort(arr, array_size(arr), array_element_size(arr), __default_int_cmp); */
 	print_arr(arr, __LINE__, "qsort");
-	array_insert(arr, 20, 1);			// size: 6, cap: 8
+	TEST_TYPE __inserted = 20;
+	array_insert(arr, __inserted, 1);			// size: 6, cap: 8
 	print_arr(arr, __LINE__, "1 insert");
 
 	for (size_t i = 0; i <= array_size(arr); i += 2) {
@@ -74,7 +73,7 @@ int main(void)
 		puts("\x1b[32mTest for \"" stringify(TEST_TYPE)"\" passed\x1b[0m");
 	}
 	TEST_TYPE* elem;
-	if ((elem = array_at(arr, 2)) != NULL) {
+	if ((elem = array_at(arr, 1)) != NULL) {
 		if (*elem == 42) {
 			puts("array_at(1) = 42");
 		}
diff --git a/tests/dynarray_struct.c b/tests/dynarray_struct.c
new file mode 100644
index 0000000..6cce97c
--- /dev/null
+++ b/tests/dynarray_struct.c
@@ -0,0 +1,40 @@
+
+#define CONTAINER_IMPLEMENTATION
+#include "../include/container.h"
+
+#include <stdio.h>
+
+struct point {
+	float x, y, z, w;
+};
+
+void print_point(struct point* p) {
+	printf("{ .x=%.2f, .y=%.2f, .z=%.2f, .w=%.2f };\n", p->x, p->y, p->z, p->w);
+}
+
+void print_array(struct point* p) {
+	for (size_t i = 0; i < array_size(p); ++i) {
+		printf("%zu: ", i);
+		print_point(p+i);
+	}
+}
+
+int point_abs(const void* a, const void* b) {
+	struct point* c = (struct point*) a;
+	struct point* d = (struct point*) b;
+	float absa = c->x * c->x + c->y * c->y + c->z * c->z + c->w * c->w;
+	float absb = d->x * d->x + d->y * d->y + d->z * d->z + d->w * d->w;
+	return absa-absb;
+}
+
+int main()
+{
+	struct point *points = array_new(struct point, 4);
+	for (size_t i = 0; i < array_size(points); ++i) points[i] = (struct point){.x = i, .y = 2 * i, .z = 4 * i, .w = 8 * i};
+	array_push(points, ((struct point){.0f, 2.5f, 3.0, 4.0}) );
+	array_insert(points, ((struct point){0}), 3);
+	array_qsort(points, point_abs);
+	print_array(points);
+	array_free(points);
+	return 0;
+}