git.mutantstargoat.com Git - dosdemo/blob - 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 *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 dynarr_free(void *da)
  35 {
  36         if(da) {
  37                 free(DESC(da));
  38         }
  39 }
  40
  41 void *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 dynarr_empty(void *da)
  63 {
  64         return DESC(da)->nelem ? 0 : 1;
  65 }
  66
  67 int dynarr_size(void *da)
  68 {
  69         return DESC(da)->nelem;
  70 }
  71
  72
  73 /* stack semantics */
  74 void *dynarr_push(void *da, void *item)
  75 {
  76         struct arrdesc *desc;
  77         int nelem;
  78
  79         desc = DESC(da);
  80         nelem = desc->nelem;
  81
  82         if(nelem >= desc->max_elem) {
  83                 /* need to resize */
  84                 struct arrdesc *tmp;
  85                 int newsz = desc->max_elem ? desc->max_elem * 2 : 1;
  86
  87                 if(!(tmp = dynarr_resize(da, newsz))) {
  88                         fprintf(stderr, "failed to resize\n");
  89                         return da;
  90                 }
  91                 da = tmp;
  92                 desc = DESC(da);
  93                 desc->nelem = nelem;
  94         }
  95
  96         if(item) {
  97                 memcpy((char*)da + desc->nelem++ * desc->szelem, item, desc->szelem);
  98         }
  99         return da;
 100 }
 101
 102 void *dynarr_pop(void *da)
 103 {
 104         struct arrdesc *desc;
 105         int nelem;
 106
 107         desc = DESC(da);
 108         nelem = desc->nelem;
 109
 110         if(!nelem) return da;
 111
 112         if(nelem <= desc->max_elem / 3) {
 113                 /* reclaim space */
 114                 struct arrdesc *tmp;
 115                 int newsz = desc->max_elem / 2;
 116
 117                 if(!(tmp = dynarr_resize(da, newsz))) {
 118                         fprintf(stderr, "failed to resize\n");
 119                         return da;
 120                 }
 121                 da = tmp;
 122                 desc = DESC(da);
 123                 desc->nelem = nelem;
 124         }
 125         desc->nelem--;
 126
 127         return da;
 128 }