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