1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/doorbelld/src/dynarr.c	Sun Mar 13 07:56:03 2016 +0200
     1.3 @@ -0,0 +1,128 @@
     1.4 +/* dynarr - dynamic resizable C array data structure
     1.5 + * author: John Tsiombikas <nuclear@member.fsf.org>
     1.6 + * license: public domain
     1.7 + */
     1.8 +#include <stdio.h>
     1.9 +#include <stdlib.h>
    1.10 +#include <string.h>
    1.11 +#include "dynarr.h"
    1.12 +
    1.13 +/* The array descriptor keeps auxilliary information needed to manipulate
    1.14 + * the dynamic array. It's allocated adjacent to the array buffer.
    1.15 + */
    1.16 +struct arrdesc {
    1.17 +	int nelem, szelem;
    1.18 +	int max_elem;
    1.19 +	int bufsz;	/* not including the descriptor */
    1.20 +};
    1.21 +
    1.22 +#define DESC(x)		((struct arrdesc*)((char*)(x) - sizeof(struct arrdesc)))
    1.23 +
    1.24 +void *dynarr_alloc(int elem, int szelem)
    1.25 +{
    1.26 +	struct arrdesc *desc;
    1.27 +
    1.28 +	if(!(desc = malloc(elem * szelem + sizeof *desc))) {
    1.29 +		return 0;
    1.30 +	}
    1.31 +	desc->nelem = desc->max_elem = elem;
    1.32 +	desc->szelem = szelem;
    1.33 +	desc->bufsz = elem * szelem;
    1.34 +	return (char*)desc + sizeof *desc;
    1.35 +}
    1.36 +
    1.37 +void dynarr_free(void *da)
    1.38 +{
    1.39 +	if(da) {
    1.40 +		free(DESC(da));
    1.41 +	}
    1.42 +}
    1.43 +
    1.44 +void *dynarr_resize(void *da, int elem)
    1.45 +{
    1.46 +	int newsz;
    1.47 +	void *tmp;
    1.48 +	struct arrdesc *desc;
    1.49 +
    1.50 +	if(!da) return 0;
    1.51 +	desc = DESC(da);
    1.52 +
    1.53 +	newsz = desc->szelem * elem;
    1.54 +
    1.55 +	if(!(tmp = realloc(desc, newsz + sizeof *desc))) {
    1.56 +		return 0;
    1.57 +	}
    1.58 +	desc = tmp;
    1.59 +
    1.60 +	desc->nelem = desc->max_elem = elem;
    1.61 +	desc->bufsz = newsz;
    1.62 +	return (char*)desc + sizeof *desc;
    1.63 +}
    1.64 +
    1.65 +int dynarr_empty(void *da)
    1.66 +{
    1.67 +	return DESC(da)->nelem ? 0 : 1;
    1.68 +}
    1.69 +
    1.70 +int dynarr_size(void *da)
    1.71 +{
    1.72 +	return DESC(da)->nelem;
    1.73 +}
    1.74 +
    1.75 +
    1.76 +/* stack semantics */
    1.77 +void *dynarr_push(void *da, void *item)
    1.78 +{
    1.79 +	struct arrdesc *desc;
    1.80 +	int nelem;
    1.81 +
    1.82 +	desc = DESC(da);
    1.83 +	nelem = desc->nelem;
    1.84 +
    1.85 +	if(nelem >= desc->max_elem) {
    1.86 +		/* need to resize */
    1.87 +		struct arrdesc *tmp;
    1.88 +		int newsz = desc->max_elem ? desc->max_elem * 2 : 1;
    1.89 +
    1.90 +		if(!(tmp = dynarr_resize(da, newsz))) {
    1.91 +			fprintf(stderr, "failed to resize\n");
    1.92 +			return da;
    1.93 +		}
    1.94 +		da = tmp;
    1.95 +		desc = DESC(da);
    1.96 +		desc->nelem = nelem;
    1.97 +	}
    1.98 +
    1.99 +	if(item) {
   1.100 +		memcpy((char*)da + desc->nelem++ * desc->szelem, item, desc->szelem);
   1.101 +	}
   1.102 +	return da;
   1.103 +}
   1.104 +
   1.105 +void *dynarr_pop(void *da)
   1.106 +{
   1.107 +	struct arrdesc *desc;
   1.108 +	int nelem;
   1.109 +
   1.110 +	desc = DESC(da);
   1.111 +	nelem = desc->nelem;
   1.112 +
   1.113 +	if(!nelem) return da;
   1.114 +
   1.115 +	if(nelem <= desc->max_elem / 3) {
   1.116 +		/* reclaim space */
   1.117 +		struct arrdesc *tmp;
   1.118 +		int newsz = desc->max_elem / 2;
   1.119 +
   1.120 +		if(!(tmp = dynarr_resize(da, newsz))) {
   1.121 +			fprintf(stderr, "failed to resize\n");
   1.122 +			return da;
   1.123 +		}
   1.124 +		da = tmp;
   1.125 +		desc = DESC(da);
   1.126 +		desc->nelem = nelem;
   1.127 +	}
   1.128 +	desc->nelem--;
   1.129 +
   1.130 +	return da;
   1.131 +}