options/config
[demo_prior] / libs / treestore / 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 *ts_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 ts_dynarr_free(void *da)
35 {
36         if(da) {
37                 free(DESC(da));
38         }
39 }
40
41 void *ts_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 ts_dynarr_empty(void *da)
63 {
64         return DESC(da)->nelem ? 0 : 1;
65 }
66
67 int ts_dynarr_size(void *da)
68 {
69         return DESC(da)->nelem;
70 }
71
72
73 void *ts_dynarr_clear(void *da)
74 {
75         return ts_dynarr_resize(da, 0);
76 }
77
78 /* stack semantics */
79 void *ts_dynarr_push(void *da, void *item)
80 {
81         struct arrdesc *desc;
82         int nelem;
83
84         desc = DESC(da);
85         nelem = desc->nelem;
86
87         if(nelem >= desc->max_elem) {
88                 /* need to resize */
89                 struct arrdesc *tmp;
90                 int newsz = desc->max_elem ? desc->max_elem * 2 : 1;
91
92                 if(!(tmp = ts_dynarr_resize(da, newsz))) {
93                         fprintf(stderr, "failed to resize\n");
94                         return da;
95                 }
96                 da = tmp;
97                 desc = DESC(da);
98                 desc->nelem = nelem;
99         }
100
101         if(item) {
102                 memcpy((char*)da + desc->nelem++ * desc->szelem, item, desc->szelem);
103         }
104         return da;
105 }
106
107 void *ts_dynarr_pop(void *da)
108 {
109         struct arrdesc *desc;
110         int nelem;
111
112         desc = DESC(da);
113         nelem = desc->nelem;
114
115         if(!nelem) return da;
116
117         if(nelem <= desc->max_elem / 3) {
118                 /* reclaim space */
119                 struct arrdesc *tmp;
120                 int newsz = desc->max_elem / 2;
121
122                 if(!(tmp = ts_dynarr_resize(da, newsz))) {
123                         fprintf(stderr, "failed to resize\n");
124                         return da;
125                 }
126                 da = tmp;
127                 desc = DESC(da);
128                 desc->nelem = nelem;
129         }
130         desc->nelem--;
131
132         return da;
133 }