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