• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * *****************************************************************************
3  *
4  * SPDX-License-Identifier: BSD-2-Clause
5  *
6  * Copyright (c) 2018-2021 Gavin D. Howard and contributors.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions are met:
10  *
11  * * Redistributions of source code must retain the above copyright notice, this
12  *   list of conditions and the following disclaimer.
13  *
14  * * Redistributions in binary form must reproduce the above copyright notice,
15  *   this list of conditions and the following disclaimer in the documentation
16  *   and/or other materials provided with the distribution.
17  *
18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
22  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
26  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
28  * POSSIBILITY OF SUCH DAMAGE.
29  *
30  * *****************************************************************************
31  *
32  * Code to manipulate vectors (resizable arrays).
33  *
34  */
35 
36 #include <assert.h>
37 #include <stdlib.h>
38 #include <string.h>
39 
40 #include <vector.h>
41 #include <lang.h>
42 #include <vm.h>
43 
bc_vec_grow(BcVec * restrict v,size_t n)44 void bc_vec_grow(BcVec *restrict v, size_t n) {
45 
46 	size_t len, cap = v->cap;
47 	sig_atomic_t lock;
48 
49 	len = bc_vm_growSize(v->len, n);
50 
51 	while (cap < len) cap = bc_vm_growSize(cap, cap);
52 
53 	BC_SIG_TRYLOCK(lock);
54 	v->v = bc_vm_realloc(v->v, bc_vm_arraySize(cap, v->size));
55 	v->cap = cap;
56 	BC_SIG_TRYUNLOCK(lock);
57 }
58 
bc_vec_init(BcVec * restrict v,size_t esize,BcVecFree dtor)59 void bc_vec_init(BcVec *restrict v, size_t esize, BcVecFree dtor) {
60 	BC_SIG_ASSERT_LOCKED;
61 	assert(v != NULL && esize);
62 	v->size = esize;
63 	v->cap = BC_VEC_START_CAP;
64 	v->len = 0;
65 	v->dtor = dtor;
66 	v->v = bc_vm_malloc(bc_vm_arraySize(BC_VEC_START_CAP, esize));
67 }
68 
bc_vec_expand(BcVec * restrict v,size_t req)69 void bc_vec_expand(BcVec *restrict v, size_t req) {
70 
71 	assert(v != NULL);
72 
73 	if (v->cap < req) {
74 
75 		sig_atomic_t lock;
76 
77 		BC_SIG_TRYLOCK(lock);
78 
79 		v->v = bc_vm_realloc(v->v, bc_vm_arraySize(req, v->size));
80 		v->cap = req;
81 
82 		BC_SIG_TRYUNLOCK(lock);
83 	}
84 }
85 
bc_vec_npop(BcVec * restrict v,size_t n)86 void bc_vec_npop(BcVec *restrict v, size_t n) {
87 
88 	sig_atomic_t lock;
89 
90 	assert(v != NULL && n <= v->len);
91 
92 	BC_SIG_TRYLOCK(lock);
93 
94 	if (v->dtor == NULL) v->len -= n;
95 	else {
96 		size_t len = v->len - n;
97 		while (v->len > len) v->dtor(v->v + (v->size * --v->len));
98 	}
99 
100 	BC_SIG_TRYUNLOCK(lock);
101 }
102 
bc_vec_npopAt(BcVec * restrict v,size_t n,size_t idx)103 void bc_vec_npopAt(BcVec *restrict v, size_t n, size_t idx) {
104 
105 	char* ptr, *data;
106 
107 	assert(v != NULL);
108 	assert(idx + n < v->len);
109 
110 	ptr = bc_vec_item(v, idx);
111 	data = bc_vec_item(v, idx + n);
112 
113 	BC_SIG_LOCK;
114 
115 	if (v->dtor != NULL) {
116 
117 		size_t i;
118 
119 		for (i = 0; i < n; ++i) v->dtor(bc_vec_item(v, idx + i));
120 	}
121 
122 	v->len -= n;
123 	memmove(ptr, data, (v->len - idx) * v->size);
124 
125 	BC_SIG_UNLOCK;
126 }
127 
bc_vec_npush(BcVec * restrict v,size_t n,const void * data)128 void bc_vec_npush(BcVec *restrict v, size_t n, const void *data) {
129 
130 	sig_atomic_t lock;
131 
132 	assert(v != NULL && data != NULL);
133 
134 	BC_SIG_TRYLOCK(lock);
135 
136 	if (v->len + n > v->cap) bc_vec_grow(v, n);
137 
138 	memcpy(v->v + (v->size * v->len), data, v->size * n);
139 	v->len += n;
140 
141 	BC_SIG_TRYUNLOCK(lock);
142 }
143 
bc_vec_push(BcVec * restrict v,const void * data)144 inline void bc_vec_push(BcVec *restrict v, const void *data) {
145 	bc_vec_npush(v, 1, data);
146 }
147 
bc_vec_pushByte(BcVec * restrict v,uchar data)148 void bc_vec_pushByte(BcVec *restrict v, uchar data) {
149 	assert(v != NULL && v->size == sizeof(uchar));
150 	bc_vec_npush(v, 1, &data);
151 }
152 
bc_vec_pushIndex(BcVec * restrict v,size_t idx)153 void bc_vec_pushIndex(BcVec *restrict v, size_t idx) {
154 
155 	uchar amt, nums[sizeof(size_t) + 1];
156 
157 	assert(v != NULL);
158 	assert(v->size == sizeof(uchar));
159 
160 	for (amt = 0; idx; ++amt) {
161 		nums[amt + 1] = (uchar) idx;
162 		idx &= ((size_t) ~(UCHAR_MAX));
163 		idx >>= sizeof(uchar) * CHAR_BIT;
164 	}
165 
166 	nums[0] = amt;
167 
168 	bc_vec_npush(v, amt + 1, nums);
169 }
170 
bc_vec_pushAt(BcVec * restrict v,const void * data,size_t idx)171 static void bc_vec_pushAt(BcVec *restrict v, const void *data, size_t idx) {
172 
173 	sig_atomic_t lock;
174 
175 	assert(v != NULL && data != NULL && idx <= v->len);
176 
177 	BC_SIG_TRYLOCK(lock);
178 
179 	if (idx == v->len) bc_vec_push(v, data);
180 	else {
181 
182 		char *ptr;
183 
184 		if (v->len == v->cap) bc_vec_grow(v, 1);
185 
186 		ptr = v->v + v->size * idx;
187 
188 		memmove(ptr + v->size, ptr, v->size * (v->len++ - idx));
189 		memmove(ptr, data, v->size);
190 	}
191 
192 	BC_SIG_TRYUNLOCK(lock);
193 }
194 
bc_vec_string(BcVec * restrict v,size_t len,const char * restrict str)195 void bc_vec_string(BcVec *restrict v, size_t len, const char *restrict str) {
196 
197 	sig_atomic_t lock;
198 
199 	assert(v != NULL && v->size == sizeof(char));
200 	assert(v->dtor == NULL);
201 	assert(!v->len || !v->v[v->len - 1]);
202 	assert(v->v != str);
203 
204 	BC_SIG_TRYLOCK(lock);
205 
206 	bc_vec_popAll(v);
207 	bc_vec_expand(v, bc_vm_growSize(len, 1));
208 	memcpy(v->v, str, len);
209 	v->len = len;
210 
211 	bc_vec_pushByte(v, '\0');
212 
213 	BC_SIG_TRYUNLOCK(lock);
214 }
215 
bc_vec_concat(BcVec * restrict v,const char * restrict str)216 void bc_vec_concat(BcVec *restrict v, const char *restrict str) {
217 
218 	sig_atomic_t lock;
219 
220 	assert(v != NULL && v->size == sizeof(char));
221 	assert(v->dtor == NULL);
222 	assert(!v->len || !v->v[v->len - 1]);
223 	assert(v->v != str);
224 
225 	BC_SIG_TRYLOCK(lock);
226 
227 	if (v->len) v->len -= 1;
228 
229 	bc_vec_npush(v, strlen(str) + 1, str);
230 
231 	BC_SIG_TRYUNLOCK(lock);
232 }
233 
bc_vec_empty(BcVec * restrict v)234 void bc_vec_empty(BcVec *restrict v) {
235 
236 	sig_atomic_t lock;
237 
238 	assert(v != NULL && v->size == sizeof(char));
239 	assert(v->dtor == NULL);
240 
241 	BC_SIG_TRYLOCK(lock);
242 
243 	bc_vec_popAll(v);
244 	bc_vec_pushByte(v, '\0');
245 
246 	BC_SIG_TRYUNLOCK(lock);
247 }
248 
249 #if BC_ENABLE_HISTORY
bc_vec_replaceAt(BcVec * restrict v,size_t idx,const void * data)250 void bc_vec_replaceAt(BcVec *restrict v, size_t idx, const void *data) {
251 
252 	char *ptr;
253 
254 	BC_SIG_ASSERT_LOCKED;
255 
256 	assert(v != NULL);
257 
258 	ptr = bc_vec_item(v, idx);
259 
260 	if (v->dtor != NULL) v->dtor(ptr);
261 
262 	memcpy(ptr, data, v->size);
263 }
264 #endif // BC_ENABLE_HISTORY
265 
bc_vec_item(const BcVec * restrict v,size_t idx)266 inline void* bc_vec_item(const BcVec *restrict v, size_t idx) {
267 	assert(v != NULL && v->len && idx < v->len);
268 	return v->v + v->size * idx;
269 }
270 
bc_vec_item_rev(const BcVec * restrict v,size_t idx)271 inline void* bc_vec_item_rev(const BcVec *restrict v, size_t idx) {
272 	assert(v != NULL && v->len && idx < v->len);
273 	return v->v + v->size * (v->len - idx - 1);
274 }
275 
bc_vec_clear(BcVec * restrict v)276 inline void bc_vec_clear(BcVec *restrict v) {
277 	BC_SIG_ASSERT_LOCKED;
278 	v->v = NULL;
279 	v->len = 0;
280 	v->dtor = NULL;
281 }
282 
bc_vec_free(void * vec)283 void bc_vec_free(void *vec) {
284 	BcVec *v = (BcVec*) vec;
285 	BC_SIG_ASSERT_LOCKED;
286 	bc_vec_popAll(v);
287 	free(v->v);
288 }
289 
bc_map_find(const BcVec * restrict v,const char * name)290 static size_t bc_map_find(const BcVec *restrict v, const char *name) {
291 
292 	size_t low = 0, high = v->len;
293 
294 	while (low < high) {
295 
296 		size_t mid = (low + high) / 2;
297 		const BcId *id = bc_vec_item(v, mid);
298 		int result = strcmp(name, id->name);
299 
300 		if (!result) return mid;
301 		else if (result < 0) high = mid;
302 		else low = mid + 1;
303 	}
304 
305 	return low;
306 }
307 
bc_map_insert(BcVec * restrict v,const char * name,size_t idx,size_t * restrict i)308 bool bc_map_insert(BcVec *restrict v, const char *name,
309                    size_t idx, size_t *restrict i)
310 {
311 	BcId id;
312 
313 	BC_SIG_ASSERT_LOCKED;
314 
315 	assert(v != NULL && name != NULL && i != NULL);
316 
317 	*i = bc_map_find(v, name);
318 
319 	assert(*i <= v->len);
320 
321 	if (*i != v->len && !strcmp(name, ((BcId*) bc_vec_item(v, *i))->name))
322 		return false;
323 
324 	id.name = bc_vm_strdup(name);
325 	id.idx = idx;
326 
327 	bc_vec_pushAt(v, &id, *i);
328 
329 	return true;
330 }
331 
bc_map_index(const BcVec * restrict v,const char * name)332 size_t bc_map_index(const BcVec *restrict v, const char *name) {
333 
334 	size_t i;
335 
336 	assert(v != NULL && name != NULL);
337 
338 	i = bc_map_find(v, name);
339 
340 	if (i >= v->len) return BC_VEC_INVALID_IDX;
341 
342 	return strcmp(name, ((BcId*) bc_vec_item(v, i))->name) ?
343 	    BC_VEC_INVALID_IDX : i;
344 }
345