tinygi

annotate src/dynarr.c @ 0:16fdca2a1ef5

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