1 /* varray - a variable sized array
2 * Copyright (c) 2003 Michael B. Allen <mba2000 ioplex.com>
3 *
4 * The MIT License
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the "Software"),
8 * to deal in the Software without restriction, including without limitation
9 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
10 * and/or sell copies of the Software, and to permit persons to whom the
11 * Software is furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included
14 * in all copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
20 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
21 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
22 * OTHER DEALINGS IN THE SOFTWARE.
23 */
24
25 #include <stdlib.h>
26 #include <string.h>
27 #include <errno.h>
28
29 #include "mba/iterator.h"
30 #include "mba/varray.h"
31 #include "mba/msgno.h"
32
33 #define VAAL(va) ((struct allocator *)((va)->al ? (char *)(va) - (ptrdiff_t)(va)->al : NULL))
34 #define BINSIZ(i) ((i) ? 1 << ((i) + (VARRAY_INIT_SIZE - 1)) : (1 << VARRAY_INIT_SIZE))
35
36 int
varray_init(struct varray * va,size_t membsize,struct allocator * al)37 varray_init(struct varray *va, size_t membsize, struct allocator *al)
38 {
39 if (va == NULL || membsize == 0) {
40 PMNO(errno = EINVAL);
41 return -1;
42 }
43
44 memset(va, 0, sizeof *va);
45 va->size = membsize;
46 if (al && al->tail) { /* al is a suba allocator */
47 va->al = (char *)va - (char *)al;
48 }
49
50 return 0;
51 }
52 int
varray_deinit(struct varray * va)53 varray_deinit(struct varray *va)
54 {
55 if (varray_release(va, 0) == -1) {
56 AMSG("");
57 return -1;
58 }
59 return 0;
60 }
61 struct varray *
varray_new(size_t membsize,struct allocator * al)62 varray_new(size_t membsize, struct allocator *al)
63 {
64 struct varray *va;
65
66 if ((va = allocator_alloc(al, sizeof *va, 0)) == NULL) {
67 AMSG("");
68 return NULL;
69 }
70 if (varray_init(va, membsize, al) == -1) {
71 AMSG("");
72 allocator_free(al, va);
73 return NULL;
74 }
75
76 return va;
77 }
78 int
varray_del(void * va)79 varray_del(void *va)
80 {
81 int ret = 0;
82
83 if (va) {
84 ret += varray_release(va, 0);
85 ret += allocator_free(VAAL((struct varray *)va), va);
86 }
87
88 if (ret) {
89 AMSG("");
90 return -1;
91 }
92
93 return 0;
94 }
95 int
varray_release(struct varray * va,unsigned int from)96 varray_release(struct varray *va, unsigned int from)
97 {
98 unsigned int r, i;
99 int ret = 0;
100
101 if (va == NULL) {
102 return 0;
103 }
104
105 r = (1 << VARRAY_INIT_SIZE);
106 for (i = 0; i < 16; i++) {
107 if (from <= r) {
108 break;
109 }
110 r *= 2;
111 }
112 if (from != 0) i++;
113 for ( ; i < 16; i++) {
114 if (va->bins[i]) {
115 struct allocator *al = VAAL(va);
116 ret += allocator_free(al, ALADR(al, va->bins[i]));
117 va->bins[i] = 0;
118 }
119 }
120
121 if (ret) {
122 AMSG("");
123 return -1;
124 }
125
126 return 0;
127 }
128 void *
varray_get(struct varray * va,unsigned int idx)129 varray_get(struct varray *va, unsigned int idx)
130 {
131 unsigned int r, i, n;
132 struct allocator *al;
133
134 if (va == NULL) {
135 PMNO(errno = EINVAL);
136 return NULL;
137 }
138
139 r = (1 << VARRAY_INIT_SIZE); /* First and second bins hold 32 then 64,128,256,... */
140 for (i = 0; i < 16; i++) {
141 if (r > idx) {
142 break;
143 }
144 r *= 2;
145 }
146 if (i == 16) {
147 PMNO(errno = ERANGE);
148 return NULL;
149 }
150
151 al = VAAL(va);
152 n = BINSIZ(i); /* n is nmemb in bin i */
153
154 if (va->bins[i] == 0) {
155 char *mem = allocator_alloc(al, n * va->size, 1);
156 if (mem == NULL) {
157 AMSG("");
158 return NULL;
159 }
160 va->bins[i] = ALREF(al, mem);
161 }
162
163 return (char *)ALADR(al, va->bins[i]) + (i ? idx - n : idx) * va->size;
164 }
165 int
varray_index(struct varray * va,void * elem)166 varray_index(struct varray *va, void *elem)
167 {
168 ref_t er = ALREF(VAAL(va), elem);
169 int i;
170
171 for (i = 0; i < 16; i++) {
172 if (va->bins[i]) {
173 size_t n = BINSIZ(i);
174 ref_t start = va->bins[i];
175 ref_t end = start + n * va->size;
176 if (er >= start && er < end) {
177 return (i ? n : 0) + ((er - start) / va->size);
178 }
179 }
180 }
181
182 PMNO(errno = EFAULT);
183 return -1;
184 }
185 void
varray_iterate(void * va,iter_t * iter)186 varray_iterate(void *va, iter_t *iter)
187 {
188 if (va && iter) {
189 iter->i1 = iter->i2 = 0;
190 }
191 }
192 void *
varray_next(void * va0,iter_t * iter)193 varray_next(void *va0, iter_t *iter)
194 {
195 struct varray *va = va0;
196 unsigned int n;
197
198 if (va == NULL || iter == NULL) {
199 PMNO(errno = EINVAL);
200 return NULL;
201 }
202
203 /* n is nmemb in iter->i1 */
204 n = iter->i1 == 0 ? (1 << VARRAY_INIT_SIZE) :
205 1 << (iter->i1 + (VARRAY_INIT_SIZE - 1));
206
207 if (iter->i2 == n) {
208 iter->i2 = 0;
209 iter->i1++;
210 }
211 while (va->bins[iter->i1] == 0) {
212 iter->i1++;
213 if (iter->i1 == 16) {
214 return NULL;
215 }
216 }
217
218 return (char *)ALADR(VAAL(va), va->bins[iter->i1]) + iter->i2++ * va->size;
219 }
220
221