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

   1 /*
   2 Deep Runner - 6dof shooter game for the SGI O2.
   3 Copyright (C) 2023  John Tsiombikas <nuclear@mutantstargoat.com>
   4
   5 This program is free software: you can redistribute it and/or modify
   6 it under the terms of the GNU General Public License as published by
   7 the Free Software Foundation, either version 3 of the License, or
   8 (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License
  16 along with this program.  If not, see <https://www.gnu.org/licenses/>.
  17 */
  18 #include <stdio.h>
  19 #include <stdlib.h>
  20 #include <string.h>
  21 #include "darray.h"
  22 #include "util.h"
  23
  24
  25 /* The array descriptor keeps auxilliary information needed to manipulate
  26  * the dynamic array. It's allocated adjacent to the array buffer.
  27  */
  28 struct arrdesc {
  29         int nelem, szelem;
  30         int max_elem;
  31         int bufsz;      /* not including the descriptor */
  32 };
  33
  34 #define DESC(x)         ((struct arrdesc*)((char*)(x) - sizeof(struct arrdesc)))
  35
  36 void *darr_alloc(int elem, int szelem)
  37 {
  38         struct arrdesc *desc;
  39
  40         desc = malloc_nf(elem * szelem + sizeof *desc);
  41         desc->nelem = desc->max_elem = elem;
  42         desc->szelem = szelem;
  43         desc->bufsz = elem * szelem;
  44         return (char*)desc + sizeof *desc;
  45 }
  46
  47 void darr_free(void *da)
  48 {
  49         if(da) {
  50                 free(DESC(da));
  51         }
  52 }
  53
  54 void *darr_resize_impl(void *da, int elem)
  55 {
  56         int newsz;
  57         struct arrdesc *desc;
  58
  59         if(!da) return 0;
  60         desc = DESC(da);
  61
  62         newsz = desc->szelem * elem;
  63         desc = realloc_nf(desc, newsz + sizeof *desc);
  64
  65         desc->nelem = desc->max_elem = elem;
  66         desc->bufsz = newsz;
  67         return (char*)desc + sizeof *desc;
  68 }
  69
  70 int darr_empty(void *da)
  71 {
  72         return DESC(da)->nelem ? 0 : 1;
  73 }
  74
  75 int darr_size(void *da)
  76 {
  77         return DESC(da)->nelem;
  78 }
  79
  80
  81 void *darr_clear_impl(void *da)
  82 {
  83         return darr_resize_impl(da, 0);
  84 }
  85
  86 /* stack semantics */
  87 void *darr_push_impl(void *da, void *item)
  88 {
  89         struct arrdesc *desc;
  90         int nelem;
  91
  92         desc = DESC(da);
  93         nelem = desc->nelem;
  94
  95         if(nelem >= desc->max_elem) {
  96                 /* need to resize */
  97                 int newsz = desc->max_elem ? desc->max_elem * 2 : 1;
  98
  99                 da = darr_resize_impl(da, newsz);
 100                 desc = DESC(da);
 101                 desc->nelem = nelem;
 102         }
 103
 104         if(item) {
 105                 memcpy((char*)da + desc->nelem * desc->szelem, item, desc->szelem);
 106         }
 107         desc->nelem++;
 108         return da;
 109 }
 110
 111 void *darr_pop_impl(void *da)
 112 {
 113         struct arrdesc *desc;
 114         int nelem;
 115
 116         desc = DESC(da);
 117         nelem = desc->nelem;
 118
 119         if(!nelem) return da;
 120
 121         if(nelem <= desc->max_elem / 3) {
 122                 /* reclaim space */
 123                 int newsz = desc->max_elem / 2;
 124
 125                 da = darr_resize_impl(da, newsz);
 126                 desc = DESC(da);
 127                 desc->nelem = nelem;
 128         }
 129         desc->nelem--;
 130
 131         return da;
 132 }
 133
 134 void *darr_finalize(void *da)
 135 {
 136         struct arrdesc *desc = DESC(da);
 137         memmove(desc, da, desc->bufsz);
 138         return desc;
 139 }