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