git.mutantstargoat.com Git - meshfrac/blob - src/darray.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include "darray.h"
   5 #include "util.h"
   6
   7 /* The array descriptor keeps auxilliary information needed to manipulate
   8  * the dynamic array. It's allocated adjacent to the array buffer.
   9  */
  10 struct arrdesc {
  11         int nelem, szelem;
  12         int max_elem;
  13         int bufsz;      /* not including the descriptor */
  14 };
  15
  16 #define DESC(x)         ((struct arrdesc*)((char*)(x) - sizeof(struct arrdesc)))
  17
  18 void *darr_alloc(int elem, int szelem)
  19 {
  20         struct arrdesc *desc;
  21
  22         desc = malloc_nf(elem * szelem + sizeof *desc);
  23         desc->nelem = desc->max_elem = elem;
  24         desc->szelem = szelem;
  25         desc->bufsz = elem * szelem;
  26         return (char*)desc + sizeof *desc;
  27 }
  28
  29 void darr_free(void *da)
  30 {
  31         if(da) {
  32                 free(DESC(da));
  33         }
  34 }
  35
  36 void *darr_resize_impl(void *da, int elem)
  37 {
  38         int newsz;
  39         struct arrdesc *desc;
  40
  41         if(!da) return 0;
  42         desc = DESC(da);
  43
  44         newsz = desc->szelem * elem;
  45         desc = realloc_nf(desc, newsz + sizeof *desc);
  46
  47         desc->nelem = desc->max_elem = elem;
  48         desc->bufsz = newsz;
  49         return (char*)desc + sizeof *desc;
  50 }
  51
  52 int darr_empty(void *da)
  53 {
  54         return DESC(da)->nelem ? 0 : 1;
  55 }
  56
  57 int darr_size(void *da)
  58 {
  59         return DESC(da)->nelem;
  60 }
  61
  62
  63 void *darr_clear_impl(void *da)
  64 {
  65         return darr_resize_impl(da, 0);
  66 }
  67
  68 /* stack semantics */
  69 void *darr_push_impl(void *da, void *item)
  70 {
  71         struct arrdesc *desc;
  72         int nelem;
  73
  74         desc = DESC(da);
  75         nelem = desc->nelem;
  76
  77         if(nelem >= desc->max_elem) {
  78                 /* need to resize */
  79                 int newsz = desc->max_elem ? desc->max_elem * 2 : 1;
  80
  81                 da = darr_resize_impl(da, newsz);
  82                 desc = DESC(da);
  83                 desc->nelem = nelem;
  84         }
  85
  86         if(item) {
  87                 memcpy((char*)da + desc->nelem * desc->szelem, item, desc->szelem);
  88         }
  89         desc->nelem++;
  90         return da;
  91 }
  92
  93 void *darr_pop_impl(void *da)
  94 {
  95         struct arrdesc *desc;
  96         int nelem;
  97
  98         desc = DESC(da);
  99         nelem = desc->nelem;
 100
 101         if(!nelem) return da;
 102
 103         if(nelem <= desc->max_elem / 3) {
 104                 /* reclaim space */
 105                 int newsz = desc->max_elem / 2;
 106
 107                 da = darr_resize_impl(da, newsz);
 108                 desc = DESC(da);
 109                 desc->nelem = nelem;
 110         }
 111         desc->nelem--;
 112
 113         return da;
 114 }
 115
 116 void *darr_finalize(void *da)
 117 {
 118         struct arrdesc *desc = DESC(da);
 119         memmove(desc, da, desc->bufsz);
 120         return desc;
 121 }