xref: /freebsd/contrib/bc/src/vector.c (revision 3332f1b444d4a73238e9f59cca27bfc95fe936bd)
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 #include <stdbool.h>
40 
41 #include <vector.h>
42 #include <lang.h>
43 #include <vm.h>
44 
45 void bc_vec_grow(BcVec *restrict v, size_t n) {
46 
47 	size_t cap, len;
48 	sig_atomic_t lock;
49 
50 	cap = v->cap;
51 	len = v->len + n;
52 
53 	// If this is true, we might overflow.
54 	if (len > SIZE_MAX / 2) cap = len;
55 	else {
56 		// Keep doubling until larger.
57 		while (cap < len) cap += cap;
58 	}
59 
60 	BC_SIG_TRYLOCK(lock);
61 
62 	v->v = bc_vm_realloc(v->v, bc_vm_arraySize(cap, v->size));
63 	v->cap = cap;
64 
65 	BC_SIG_TRYUNLOCK(lock);
66 }
67 
68 void bc_vec_init(BcVec *restrict v, size_t esize, BcDtorType dtor) {
69 
70 	BC_SIG_ASSERT_LOCKED;
71 
72 	assert(v != NULL && esize);
73 
74 	v->v = bc_vm_malloc(bc_vm_arraySize(BC_VEC_START_CAP, esize));
75 
76 	v->size = (BcSize) esize;
77 	v->cap = BC_VEC_START_CAP;
78 	v->len = 0;
79 	v->dtor = (BcSize) dtor;
80 }
81 
82 void bc_vec_expand(BcVec *restrict v, size_t req) {
83 
84 	assert(v != NULL);
85 
86 	// Only expand if necessary.
87 	if (v->cap < req) {
88 
89 		sig_atomic_t lock;
90 
91 		BC_SIG_TRYLOCK(lock);
92 
93 		v->v = bc_vm_realloc(v->v, bc_vm_arraySize(req, v->size));
94 		v->cap = req;
95 
96 		BC_SIG_TRYUNLOCK(lock);
97 	}
98 }
99 
100 void bc_vec_npop(BcVec *restrict v, size_t n) {
101 
102 	sig_atomic_t lock;
103 
104 	assert(v != NULL && n <= v->len);
105 
106 	BC_SIG_TRYLOCK(lock);
107 
108 	if (!v->dtor) v->len -= n;
109 	else {
110 
111 		const BcVecFree d = bc_vec_dtors[v->dtor];
112 		size_t esize = v->size;
113 		size_t len = v->len - n;
114 
115 		// Loop through and manually destruct every element.
116 		while (v->len > len) d(v->v + (esize * --v->len));
117 	}
118 
119 	BC_SIG_TRYUNLOCK(lock);
120 }
121 
122 void bc_vec_npopAt(BcVec *restrict v, size_t n, size_t idx) {
123 
124 	char* ptr, *data;
125 	sig_atomic_t lock;
126 
127 	assert(v != NULL);
128 	assert(idx + n < v->len);
129 
130 	// Grab start and end pointers.
131 	ptr = bc_vec_item(v, idx);
132 	data = bc_vec_item(v, idx + n);
133 
134 	BC_SIG_TRYLOCK(lock);
135 
136 	if (v->dtor) {
137 
138 		size_t i;
139 		const BcVecFree d = bc_vec_dtors[v->dtor];
140 
141 		// Destroy every popped item.
142 		for (i = 0; i < n; ++i) d(bc_vec_item(v, idx + i));
143 	}
144 
145 	v->len -= n;
146 	memmove(ptr, data, (v->len - idx) * v->size);
147 
148 	BC_SIG_TRYUNLOCK(lock);
149 }
150 
151 void bc_vec_npush(BcVec *restrict v, size_t n, const void *data) {
152 
153 	sig_atomic_t lock;
154 	size_t esize;
155 
156 	assert(v != NULL && data != NULL);
157 
158 	BC_SIG_TRYLOCK(lock);
159 
160 	// Grow if necessary.
161 	if (v->len + n > v->cap) bc_vec_grow(v, n);
162 
163 	esize = v->size;
164 
165 	// Copy the elements in.
166 	memcpy(v->v + (esize * v->len), data, esize * n);
167 	v->len += n;
168 
169 	BC_SIG_TRYUNLOCK(lock);
170 }
171 
172 inline void bc_vec_push(BcVec *restrict v, const void *data) {
173 	bc_vec_npush(v, 1, data);
174 }
175 
176 void* bc_vec_pushEmpty(BcVec *restrict v) {
177 
178 	sig_atomic_t lock;
179 	void *ptr;
180 
181 	assert(v != NULL);
182 
183 	BC_SIG_TRYLOCK(lock);
184 
185 	// Grow if necessary.
186 	if (v->len + 1 > v->cap) bc_vec_grow(v, 1);
187 
188 	ptr = v->v + v->size * v->len;
189 	v->len += 1;
190 
191 	BC_SIG_TRYUNLOCK(lock);
192 
193 	return ptr;
194 }
195 
196 inline void bc_vec_pushByte(BcVec *restrict v, uchar data) {
197 	assert(v != NULL && v->size == sizeof(uchar));
198 	bc_vec_npush(v, 1, &data);
199 }
200 
201 void bc_vec_pushIndex(BcVec *restrict v, size_t idx) {
202 
203 	uchar amt, nums[sizeof(size_t) + 1];
204 
205 	assert(v != NULL);
206 	assert(v->size == sizeof(uchar));
207 
208 	// Encode the index.
209 	for (amt = 0; idx; ++amt) {
210 		nums[amt + 1] = (uchar) idx;
211 		idx &= ((size_t) ~(UCHAR_MAX));
212 		idx >>= sizeof(uchar) * CHAR_BIT;
213 	}
214 
215 	nums[0] = amt;
216 
217 	// Push the index onto the vector.
218 	bc_vec_npush(v, amt + 1, nums);
219 }
220 
221 void bc_vec_pushAt(BcVec *restrict v, const void *data, size_t idx) {
222 
223 	assert(v != NULL && data != NULL && idx <= v->len);
224 
225 	BC_SIG_ASSERT_LOCKED;
226 
227 	// Do the easy case.
228 	if (idx == v->len) bc_vec_push(v, data);
229 	else {
230 
231 		char *ptr;
232 		size_t esize;
233 
234 		// Grow if necessary.
235 		if (v->len == v->cap) bc_vec_grow(v, 1);
236 
237 		esize = v->size;
238 
239 		ptr = v->v + esize * idx;
240 
241 		memmove(ptr + esize, ptr, esize * (v->len++ - idx));
242 		memcpy(ptr, data, esize);
243 	}
244 }
245 
246 void bc_vec_string(BcVec *restrict v, size_t len, const char *restrict str) {
247 
248 	sig_atomic_t lock;
249 
250 	assert(v != NULL && v->size == sizeof(char));
251 	assert(!v->dtor);
252 	assert(!v->len || !v->v[v->len - 1]);
253 	assert(v->v != str);
254 
255 	BC_SIG_TRYLOCK(lock);
256 
257 	bc_vec_popAll(v);
258 	bc_vec_expand(v, bc_vm_growSize(len, 1));
259 	memcpy(v->v, str, len);
260 	v->len = len;
261 
262 	bc_vec_pushByte(v, '\0');
263 
264 	BC_SIG_TRYUNLOCK(lock);
265 }
266 
267 void bc_vec_concat(BcVec *restrict v, const char *restrict str) {
268 
269 	sig_atomic_t lock;
270 
271 	assert(v != NULL && v->size == sizeof(char));
272 	assert(!v->dtor);
273 	assert(!v->len || !v->v[v->len - 1]);
274 	assert(v->v != str);
275 
276 	BC_SIG_TRYLOCK(lock);
277 
278 	// If there is already a string, erase its nul byte.
279 	if (v->len) v->len -= 1;
280 
281 	bc_vec_npush(v, strlen(str) + 1, str);
282 
283 	BC_SIG_TRYUNLOCK(lock);
284 }
285 
286 void bc_vec_empty(BcVec *restrict v) {
287 
288 	sig_atomic_t lock;
289 
290 	assert(v != NULL && v->size == sizeof(char));
291 	assert(!v->dtor);
292 
293 	BC_SIG_TRYLOCK(lock);
294 
295 	bc_vec_popAll(v);
296 	bc_vec_pushByte(v, '\0');
297 
298 	BC_SIG_TRYUNLOCK(lock);
299 }
300 
301 #if BC_ENABLE_HISTORY
302 void bc_vec_replaceAt(BcVec *restrict v, size_t idx, const void *data) {
303 
304 	char *ptr;
305 
306 	BC_SIG_ASSERT_LOCKED;
307 
308 	assert(v != NULL);
309 
310 	ptr = bc_vec_item(v, idx);
311 
312 	if (v->dtor) bc_vec_dtors[v->dtor](ptr);
313 
314 	memcpy(ptr, data, v->size);
315 }
316 #endif // BC_ENABLE_HISTORY
317 
318 inline void* bc_vec_item(const BcVec *restrict v, size_t idx) {
319 	assert(v != NULL && v->len && idx < v->len);
320 	return v->v + v->size * idx;
321 }
322 
323 inline void* bc_vec_item_rev(const BcVec *restrict v, size_t idx) {
324 	assert(v != NULL && v->len && idx < v->len);
325 	return v->v + v->size * (v->len - idx - 1);
326 }
327 
328 inline void bc_vec_clear(BcVec *restrict v) {
329 	BC_SIG_ASSERT_LOCKED;
330 	v->v = NULL;
331 	v->len = 0;
332 	v->dtor = BC_DTOR_NONE;
333 }
334 
335 void bc_vec_free(void *vec) {
336 	BcVec *v = (BcVec*) vec;
337 	BC_SIG_ASSERT_LOCKED;
338 	bc_vec_popAll(v);
339 	free(v->v);
340 }
341 
342 #if !BC_ENABLE_LIBRARY
343 
344 /**
345  * Finds a name in a map by binary search. Returns the index where the item
346  * *would* be if it doesn't exist. Callers are responsible for checking that the
347  * item exists at the index.
348  * @param v     The map.
349  * @param name  The name to find.
350  * @return      The index of the item with @a name, or where the item would be
351  *              if it does not exist.
352  */
353 static size_t bc_map_find(const BcVec *restrict v, const char *name) {
354 
355 	size_t low = 0, high = v->len;
356 
357 	while (low < high) {
358 
359 		size_t mid = (low + high) / 2;
360 		const BcId *id = bc_vec_item(v, mid);
361 		int result = strcmp(name, id->name);
362 
363 		if (!result) return mid;
364 		else if (result < 0) high = mid;
365 		else low = mid + 1;
366 	}
367 
368 	return low;
369 }
370 
371 bool bc_map_insert(BcVec *restrict v, const char *name,
372                    size_t idx, size_t *restrict i)
373 {
374 	BcId id;
375 	BcVec *slabs;
376 
377 	BC_SIG_ASSERT_LOCKED;
378 
379 	assert(v != NULL && name != NULL && i != NULL);
380 
381 	*i = bc_map_find(v, name);
382 
383 	assert(*i <= v->len);
384 
385 	if (*i != v->len && !strcmp(name, ((BcId*) bc_vec_item(v, *i))->name))
386 		return false;
387 
388 #if BC_ENABLED
389 	slabs = BC_IS_DC ? &vm.main_slabs : &vm.other_slabs;
390 #else // BC_ENABLED
391 	slabs = &vm.main_slabs;
392 #endif // BC_ENABLED
393 
394 	id.name = bc_slabvec_strdup(slabs, name);
395 	id.idx = idx;
396 
397 	bc_vec_pushAt(v, &id, *i);
398 
399 	return true;
400 }
401 
402 size_t bc_map_index(const BcVec *restrict v, const char *name) {
403 
404 	size_t i;
405 
406 	assert(v != NULL && name != NULL);
407 
408 	i = bc_map_find(v, name);
409 
410 	// If out of range, return invalid.
411 	if (i >= v->len) return BC_VEC_INVALID_IDX;
412 
413 	// Make sure the item exists.
414 	return strcmp(name, ((BcId*) bc_vec_item(v, i))->name) ?
415 	    BC_VEC_INVALID_IDX : i;
416 }
417 
418 #if DC_ENABLED
419 const char* bc_map_name(const BcVec *restrict v, size_t idx) {
420 
421 	size_t i, len = v->len;
422 
423 	for (i = 0; i < len; ++i) {
424 		BcId* id = (BcId*) bc_vec_item(v, i);
425 		if (id->idx == idx) return id->name;
426 	}
427 
428 	BC_UNREACHABLE
429 
430 	return "";
431 }
432 #endif // DC_ENABLED
433 
434 /**
435  * Initializes a single slab.
436  * @param s  The slab to initialize.
437  */
438 static void bc_slab_init(BcSlab *s) {
439 	s->s = bc_vm_malloc(BC_SLAB_SIZE);
440 	s->len = 0;
441 }
442 
443 /**
444  * Adds a string to a slab and returns a pointer to it, or NULL if it could not
445  * be added.
446  * @param s    The slab to add to.
447  * @param str  The string to add.
448  * @param len  The length of the string, including its nul byte.
449  * @return     A pointer to the new string in the slab, or NULL if it could not
450  *             be added.
451  */
452 static char* bc_slab_add(BcSlab *s, const char *str, size_t len) {
453 
454 	char *ptr;
455 
456 	assert(s != NULL);
457 	assert(str != NULL);
458 	assert(len == strlen(str) + 1);
459 
460 	if (s->len + len > BC_SLAB_SIZE) return NULL;
461 
462 	ptr = (char*) (s->s + s->len);
463 
464 	bc_strcpy(ptr, len, str);
465 
466 	s->len += len;
467 
468 	return ptr;
469 }
470 
471 void bc_slab_free(void *slab) {
472 	free(((BcSlab*) slab)->s);
473 }
474 
475 void bc_slabvec_init(BcVec* v) {
476 
477 	BcSlab *slab;
478 
479 	assert(v != NULL);
480 
481 	bc_vec_init(v, sizeof(BcSlab), BC_DTOR_SLAB);
482 
483 	// We always want to have at least one slab.
484 	slab = bc_vec_pushEmpty(v);
485 	bc_slab_init(slab);
486 }
487 
488 char* bc_slabvec_strdup(BcVec *v, const char *str) {
489 
490 	char *s;
491 	size_t len;
492 	BcSlab slab;
493 	BcSlab *slab_ptr;
494 
495 	BC_SIG_ASSERT_LOCKED;
496 
497 	assert(v != NULL && v->len);
498 
499 	assert(str != NULL);
500 
501 	len = strlen(str) + 1;
502 
503 	// If the len is greater than 128, then just allocate it with malloc.
504 	if (BC_UNLIKELY(len >= BC_SLAB_SIZE)) {
505 
506 		// SIZE_MAX is a marker for these standalone allocations.
507 		slab.len = SIZE_MAX;
508 		slab.s = bc_vm_strdup(str);
509 
510 		// Push the standalone slab.
511 		bc_vec_pushAt(v, &slab, v->len - 1);
512 
513 		return slab.s;
514 	}
515 
516 	// Add to a slab.
517 	slab_ptr = bc_vec_top(v);
518 	s = bc_slab_add(slab_ptr, str, len);
519 
520 	// If it couldn't be added, add a slab and try again.
521 	if (BC_UNLIKELY(s == NULL)) {
522 
523 		slab_ptr = bc_vec_pushEmpty(v);
524 		bc_slab_init(slab_ptr);
525 
526 		s = bc_slab_add(slab_ptr, str, len);
527 
528 		assert(s != NULL);
529 	}
530 
531 	return s;
532 }
533 
534 void bc_slabvec_clear(BcVec *v) {
535 
536 	BcSlab *s;
537 	bool again;
538 
539 	// This complicated loop exists because of standalone allocations over 128
540 	// bytes.
541 	do {
542 
543 		// Get the first slab.
544 		s = bc_vec_item(v, 0);
545 
546 		// Either the slab must be valid (not standalone), or there must be
547 		// another slab.
548 		assert(s->len != SIZE_MAX || v->len > 1);
549 
550 		// Do we have to loop again? We do if it's a standalone allocation.
551 		again = (s->len == SIZE_MAX);
552 
553 		// Pop the standalone allocation, not the one after it.
554 		if (again) bc_vec_npopAt(v, 1, 0);
555 
556 	} while(again);
557 
558 	// If we get here, we know that the first slab is a valid slab. We want to
559 	// pop all of the other slabs.
560 	if (v->len > 1) bc_vec_npop(v, v->len - 1);
561 
562 	// Empty the first slab.
563 	s->len = 0;
564 }
565 #endif // !BC_ENABLE_LIBRARY
566 
567 #if BC_DEBUG_CODE
568 
569 void bc_slabvec_print(BcVec *v, const char *func) {
570 
571 	size_t i;
572 	BcSlab *s;
573 
574 	bc_file_printf(&vm.ferr, "%s\n", func);
575 
576 	for (i = 0; i < v->len; ++i) {
577 		s = bc_vec_item(v, i);
578 		bc_file_printf(&vm.ferr, "%zu { s = %zu, len = %zu }\n",
579 		               i, (uintptr_t) s->s, s->len);
580 	}
581 
582 	bc_file_puts(&vm.ferr, bc_flush_none, "\n");
583 	bc_file_flush(&vm.ferr, bc_flush_none);
584 }
585 
586 #endif // BC_DEBUG_CODE
587