broguht over the 3D pipeline from the demo

[eradicate] / src / dynarr.c

diff --git a/src/dynarr.c b/src/dynarr.c
new file mode 100644 (file)
index 0000000..09a5e45
--- /dev/null
+++ b/src/dynarr.c
@@ -0,0 +1,140 @@
+/* dynarr - dynamic resizable C array data structure
+ * author: John Tsiombikas <nuclear@member.fsf.org>
+ * license: public domain
+ */
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "dynarr.h"
+
+/* The array descriptor keeps auxilliary information needed to manipulate
+ * the dynamic array. It's allocated adjacent to the array buffer.
+ */
+struct arrdesc {
+       int nelem, szelem;
+       int max_elem;
+       int bufsz;      /* not including the descriptor */
+};
+
+#define DESC(x)                ((struct arrdesc*)((char*)(x) - sizeof(struct arrdesc)))
+
+void *dynarr_alloc(int elem, int szelem)
+{
+       struct arrdesc *desc;
+
+       if(!(desc = malloc(elem * szelem + sizeof *desc))) {
+               return 0;
+       }
+       desc->nelem = desc->max_elem = elem;
+       desc->szelem = szelem;
+       desc->bufsz = elem * szelem;
+       return (char*)desc + sizeof *desc;
+}
+
+void dynarr_free(void *da)
+{
+       if(da) {
+               free(DESC(da));
+       }
+}
+
+void *dynarr_resize(void *da, int elem)
+{
+       int newsz;
+       void *tmp;
+       struct arrdesc *desc;
+
+       if(!da) return 0;
+       desc = DESC(da);
+
+       newsz = desc->szelem * elem;
+
+       if(!(tmp = realloc(desc, newsz + sizeof *desc))) {
+               return 0;
+       }
+       desc = tmp;
+
+       desc->nelem = desc->max_elem = elem;
+       desc->bufsz = newsz;
+       return (char*)desc + sizeof *desc;
+}
+
+int dynarr_empty(void *da)
+{
+       return DESC(da)->nelem ? 0 : 1;
+}
+
+int dynarr_size(void *da)
+{
+       return DESC(da)->nelem;
+}
+
+
+void *dynarr_clear(void *da)
+{
+       return dynarr_resize(da, 0);
+}
+
+/* stack semantics */
+void *dynarr_push(void *da, void *item)
+{
+       struct arrdesc *desc;
+       int nelem;
+
+       desc = DESC(da);
+       nelem = desc->nelem;
+
+       if(nelem >= desc->max_elem) {
+               /* need to resize */
+               struct arrdesc *tmp;
+               int newsz = desc->max_elem ? desc->max_elem * 2 : 1;
+
+               if(!(tmp = dynarr_resize(da, newsz))) {
+                       fprintf(stderr, "failed to resize\n");
+                       return da;
+               }
+               da = tmp;
+               desc = DESC(da);
+               desc->nelem = nelem;
+       }
+
+       if(item) {
+               memcpy((char*)da + desc->nelem++ * desc->szelem, item, desc->szelem);
+       }
+       return da;
+}
+
+void *dynarr_pop(void *da)
+{
+       struct arrdesc *desc;
+       int nelem;
+
+       desc = DESC(da);
+       nelem = desc->nelem;
+
+       if(!nelem) return da;
+
+       if(nelem <= desc->max_elem / 3) {
+               /* reclaim space */
+               struct arrdesc *tmp;
+               int newsz = desc->max_elem / 2;
+
+               if(!(tmp = dynarr_resize(da, newsz))) {
+                       fprintf(stderr, "failed to resize\n");
+                       return da;
+               }
+               da = tmp;
+               desc = DESC(da);
+               desc->nelem = nelem;
+       }
+       desc->nelem--;
+
+       return da;
+}
+
+void *dynarr_finalize(void *da)
+{
+       struct arrdesc *desc = DESC(da);
+       memmove(desc, da, desc->bufsz);
+       return desc;
+}