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