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