git.mutantstargoat.com Git - deeprace/blob - libs/treestor/src/dynarr.c

   1 /* dynarr - dynamic resizable C array data structure
   2  * author: John Tsiombikas <nuclear@member.fsf.org>
   3  * license: public domain
   4  */
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7 #include <string.h>
   8 #include "dynarr.h"
   9
  10 /* The array descriptor keeps auxilliary information needed to manipulate
  11  * the dynamic array. It's allocated adjacent to the array buffer.
  12  */
  13 struct arrdesc {
  14         int nelem, szelem;
  15         int max_elem;
  16         int bufsz;      /* not including the descriptor */
  17 };
  18
  19 #define DESC(x)         ((struct arrdesc*)((char*)(x) - sizeof(struct arrdesc)))
  20
  21 void *ts_dynarr_alloc(int elem, int szelem)
  22 {
  23         struct arrdesc *desc;
  24
  25         if(!(desc = malloc(elem * szelem + sizeof *desc))) {
  26                 return 0;
  27         }
  28         desc->nelem = desc->max_elem = elem;
  29         desc->szelem = szelem;
  30         desc->bufsz = elem * szelem;
  31         return (char*)desc + sizeof *desc;
  32 }
  33
  34 void ts_dynarr_free(void *da)
  35 {
  36         if(da) {
  37                 free(DESC(da));
  38         }
  39 }
  40
  41 void *ts_dynarr_resize(void *da, int elem)
  42 {
  43         int newsz;
  44         void *tmp;
  45         struct arrdesc *desc;
  46
  47         if(!da) return 0;
  48         desc = DESC(da);
  49
  50         newsz = desc->szelem * elem;
  51
  52         if(!(tmp = realloc(desc, newsz + sizeof *desc))) {
  53                 return 0;
  54         }
  55         desc = tmp;
  56
  57         desc->nelem = desc->max_elem = elem;
  58         desc->bufsz = newsz;
  59         return (char*)desc + sizeof *desc;
  60 }
  61
  62 int ts_dynarr_empty(void *da)
  63 {
  64         return DESC(da)->nelem ? 0 : 1;
  65 }
  66
  67 int ts_dynarr_size(void *da)
  68 {
  69         return DESC(da)->nelem;
  70 }
  71
  72
  73 void *ts_dynarr_clear(void *da)
  74 {
  75         return ts_dynarr_resize(da, 0);
  76 }
  77
  78 /* stack semantics */
  79 void *ts_dynarr_push(void *da, void *item)
  80 {
  81         struct arrdesc *desc;
  82         int nelem;
  83
  84         desc = DESC(da);
  85         nelem = desc->nelem;
  86
  87         if(nelem >= desc->max_elem) {
  88                 /* need to resize */
  89                 struct arrdesc *tmp;
  90                 int newsz = desc->max_elem ? desc->max_elem * 2 : 1;
  91
  92                 if(!(tmp = ts_dynarr_resize(da, newsz))) {
  93                         fprintf(stderr, "failed to resize\n");
  94                         return da;
  95                 }
  96                 da = tmp;
  97                 desc = DESC(da);
  98                 desc->nelem = nelem;
  99         }
 100
 101         if(item) {
 102                 memcpy((char*)da + desc->nelem++ * desc->szelem, item, desc->szelem);
 103         }
 104         return da;
 105 }
 106
 107 void *ts_dynarr_pop(void *da)
 108 {
 109         struct arrdesc *desc;
 110         int nelem;
 111
 112         desc = DESC(da);
 113         nelem = desc->nelem;
 114
 115         if(!nelem) return da;
 116
 117         if(nelem <= desc->max_elem / 3) {
 118                 /* reclaim space */
 119                 struct arrdesc *tmp;
 120                 int newsz = desc->max_elem / 2;
 121
 122                 if(!(tmp = ts_dynarr_resize(da, newsz))) {
 123                         fprintf(stderr, "failed to resize\n");
 124                         return da;
 125                 }
 126                 da = tmp;
 127                 desc = DESC(da);
 128                 desc->nelem = nelem;
 129         }
 130         desc->nelem--;
 131
 132         return da;
 133 }