1 /* ______ ___ ___
2 * /\ _ \ /\_ \ /\_ \
3 * \ \ \L\ \\//\ \ \//\ \ __ __ _ __ ___
4 * \ \ __ \ \ \ \ \ \ \ /'__`\ /'_ `\/\`'__\/ __`\
5 * \ \ \/\ \ \_\ \_ \_\ \_/\ __//\ \L\ \ \ \//\ \L\ \
6 * \ \_\ \_\/\____\/\____\ \____\ \____ \ \_\\ \____/
7 * \/_/\/_/\/____/\/____/\/____/\/___L\ \/_/ \/___/
8 * /\____/
9 * \_/__/
10 *
11 * Vectors, aka growing arrays.
12 *
13 * By Peter Wang.
14 *
15 * See readme.txt for copyright information.
16 *
17 *
18 * This is a simple growing array to hold objects of various sizes,
19 * growing by powers of two as needed. At the moment the vector never
20 * shrinks, except when it is freed. Usually the vector would hold
21 * pointers to objects, not the objects themselves, as the vector is
22 * allowed to move the objects around.
23 *
24 * This module is NOT thread-safe.
25 */
26
27 /* Internal Title: Vectors
28 */
29
30
31 #include <stdlib.h>
32 #include <string.h>
33
34 #include "allegro5/allegro.h"
35 #include "allegro5/internal/aintern.h"
36 #include "allegro5/internal/aintern_vector.h"
37
38
39 /* return the given item's starting address in the vector */
40 #define ITEM_START(vec, idx) (vec->_items + ((idx) * vec->_itemsize))
41
42
43
44 /* Internal function: _al_vector_init
45 *
46 * Initialise a vector. ITEMSIZE is the number of bytes to allocate for
47 * each item in the vector.
48 *
49 * Alternatively, you can statically initialise a vector using
50 * _AL_VECTOR vec = _AL_VECTOR_INITIALIZER(itemtype);
51 */
_al_vector_init(_AL_VECTOR * vec,size_t itemsize)52 void _al_vector_init(_AL_VECTOR *vec, size_t itemsize)
53 {
54 ASSERT(vec);
55 ASSERT(itemsize > 0);
56
57 vec->_itemsize = itemsize;
58 vec->_items = NULL;
59 vec->_size = 0;
60 vec->_unused = 0;
61 }
62
63
64
65 /*
66 * Simple inline functions:
67 *
68 * size_t _al_vector_size(const _AL_VECTOR *vec);
69 * bool _al_vector_is_empty(const _AL_VECTOR*);
70 */
71
72
73
74 /* Internal function: _al_vector_ref
75 *
76 * Return a pointer to the SLOT in the vector given by INDEX. The returned
77 * address should only be used while the vector is not modified; after that
78 * it is invalid.
79 *
80 * Tip: If you are storing pointers in the vector, you need to dereference
81 * the returned value!
82 */
_al_vector_ref(const _AL_VECTOR * vec,unsigned int idx)83 void *_al_vector_ref(const _AL_VECTOR *vec, unsigned int idx)
84 {
85 ASSERT(vec);
86 ASSERT(idx < vec->_size);
87
88 return ITEM_START(vec, idx);
89 }
90
91
92
93 /* Internal function: _al_vector_ref_front
94 * Convenience function.
95 */
_al_vector_ref_front(const _AL_VECTOR * vec)96 void* _al_vector_ref_front(const _AL_VECTOR *vec)
97 {
98 return _al_vector_ref(vec, 0);
99 }
100
101
102
103 /* Internal function: _al_vector_ref_back
104 * Convenience function.
105 */
_al_vector_ref_back(const _AL_VECTOR * vec)106 void* _al_vector_ref_back(const _AL_VECTOR *vec)
107 {
108 ASSERT(vec);
109
110 return _al_vector_ref(vec, vec->_size-1);
111 }
112
113
114
115 /* Internal function: _al_vector_append_array
116 * Append `num` elements from `arr` array to _AL_VECTOR `vec`
117 */
_al_vector_append_array(_AL_VECTOR * vec,unsigned int num,const void * arr)118 bool _al_vector_append_array(_AL_VECTOR *vec, unsigned int num, const void *arr)
119 {
120 ASSERT(vec);
121 ASSERT(arr);
122 ASSERT(num);
123
124 if (vec->_items == NULL) {
125 ASSERT(vec->_size == 0);
126 ASSERT(vec->_unused == 0);
127
128 vec->_items = al_malloc(vec->_itemsize * num);
129 ASSERT(vec->_items);
130 if (!vec->_items)
131 return false;
132
133 vec->_unused = num;
134 }
135 else if (vec->_unused < num) {
136 char *new_items;
137 new_items = al_realloc(vec->_items, (vec->_size + num) * vec->_itemsize);
138 ASSERT(new_items);
139 if (!new_items)
140 return false;
141
142 vec->_items = new_items;
143 vec->_unused = num;
144 }
145
146 memcpy(vec->_items + (vec->_size * vec->_itemsize),
147 arr, vec->_itemsize * num);
148
149 vec->_size += num;
150 vec->_unused -= num;
151
152 return true;
153 }
154
155
156
157 /* Internal function: _al_vector_alloc_back
158 *
159 * Allocate a block of memory at the back of the vector of the vector's item
160 * size (see _AL_VECTOR_INITIALIZER and _al_vector_init). Returns a pointer
161 * to the start of this block. This address should only be used while the
162 * vector is not modified; after that it is invalid. You may fill the block
163 * with whatever you want.
164 *
165 * Example:
166 * _AL_VECTOR vec = _AL_VECTOR_INITIALIZER(struct boo);
167 * struct boo *thing = _al_vector_alloc_back(&vec);
168 * thing->aaa = 100;
169 * thing->bbb = "a string";
170 */
_al_vector_alloc_back(_AL_VECTOR * vec)171 void* _al_vector_alloc_back(_AL_VECTOR *vec)
172 {
173 ASSERT(vec);
174 ASSERT(vec->_itemsize > 0);
175 {
176 if (vec->_items == NULL) {
177 ASSERT(vec->_size == 0);
178 ASSERT(vec->_unused == 0);
179
180 vec->_items = al_malloc(vec->_itemsize);
181 ASSERT(vec->_items);
182 if (!vec->_items)
183 return NULL;
184
185 vec->_unused = 1;
186 }
187 else if (vec->_unused == 0) {
188 char *new_items = al_realloc(vec->_items, 2 * vec->_size * vec->_itemsize);
189 ASSERT(new_items);
190 if (!new_items)
191 return NULL;
192
193 vec->_items = new_items;
194 vec->_unused = vec->_size;
195 }
196
197 vec->_size++;
198 vec->_unused--;
199
200 return ITEM_START(vec, vec->_size-1);
201 }
202 }
203
204
205
206 /* Internal function: _al_vector_alloc_mid
207 *
208 * Allocate a block of memory in the middle of the vector of the vector's
209 * item
210 * size (see _AL_VECTOR_INITIALIZER and _al_vector_init). Returns a pointer
211 * to the start of this block. This address should only be used while the
212 * vector is not modified; after that it is invalid. You may fill the block
213 * with whatever you want.
214 */
_al_vector_alloc_mid(_AL_VECTOR * vec,unsigned int index)215 void* _al_vector_alloc_mid(_AL_VECTOR *vec, unsigned int index)
216 {
217 ASSERT(vec);
218 ASSERT(vec->_itemsize > 0);
219 {
220 if (vec->_items == NULL) {
221 ASSERT(index == 0);
222 return _al_vector_alloc_back(vec);
223 }
224
225 if (vec->_unused == 0) {
226 char *new_items = al_realloc(vec->_items, 2 * vec->_size * vec->_itemsize);
227 ASSERT(new_items);
228 if (!new_items)
229 return NULL;
230
231 vec->_items = new_items;
232 vec->_unused = vec->_size;
233 }
234
235 memmove(ITEM_START(vec, index + 1), ITEM_START(vec, index),
236 vec->_itemsize * (vec->_size - index));
237
238 vec->_size++;
239 vec->_unused--;
240
241 return ITEM_START(vec, index);
242 }
243 }
244
245
246
247 /* Internal function: _al_vector_find
248 *
249 * Find the slot in the vector where the contents of the slot
250 * match whatever PTR_ITEM points to, bit-for-bit. If no such
251 * slot is found, a negative number is returned (currently -1).
252 */
_al_vector_find(const _AL_VECTOR * vec,const void * ptr_item)253 int _al_vector_find(const _AL_VECTOR *vec, const void *ptr_item)
254 {
255 ASSERT(vec);
256 ASSERT(ptr_item);
257
258 if (vec->_itemsize == sizeof(void *)) {
259 /* fast path for pointers */
260 void **items = (void **)vec->_items;
261 unsigned int i;
262
263 for (i = 0; i < vec->_size; i++)
264 if (items[i] == *(void **)ptr_item)
265 return i;
266 }
267 else {
268 /* slow path */
269 unsigned int i;
270 for (i = 0; i < vec->_size; i++)
271 if (memcmp(ITEM_START(vec, i), ptr_item, vec->_itemsize) == 0)
272 return i;
273 }
274
275 return -1;
276 }
277
278
279
280 /* Internal function: _al_vector_contains
281 * A simple wrapper over _al_vector_find.
282 */
_al_vector_contains(const _AL_VECTOR * vec,const void * ptr_item)283 bool _al_vector_contains(const _AL_VECTOR *vec, const void *ptr_item)
284 {
285 return _al_vector_find(vec, ptr_item) >= 0;
286 }
287
288
289
290 /* Internal function: _al_vector_delete_at
291 *
292 * Delete the slot given by index. Deleting from the start or middle of the
293 * vector requires moving the rest of the vector towards the front, so it is
294 * better to delete from the tail of the vector.
295 *
296 * Example:
297 * while (!_al_vector_is_empty(&v))
298 * _al_vector_delete_at(&v, _al_vector_size(&v)-1);
299 */
_al_vector_delete_at(_AL_VECTOR * vec,unsigned int idx)300 void _al_vector_delete_at(_AL_VECTOR *vec, unsigned int idx)
301 {
302 ASSERT(vec);
303 ASSERT(idx < vec->_size);
304 {
305 int to_move = vec->_size - idx - 1;
306 if (to_move > 0)
307 memmove(ITEM_START(vec, idx),
308 ITEM_START(vec, idx+1),
309 to_move * vec->_itemsize);
310 vec->_size--;
311 vec->_unused++;
312 memset(ITEM_START(vec, vec->_size), 0, vec->_itemsize);
313 }
314 }
315
316
317
318 /* Internal function: _al_vector_find_and_delete
319 *
320 * Similar to _al_vector_delete_at(_al_vector_find(vec, ptr_item)) but is
321 * lenient if the item is not found. Returns true if the item was found and
322 * deleted.
323 */
_al_vector_find_and_delete(_AL_VECTOR * vec,const void * ptr_item)324 bool _al_vector_find_and_delete(_AL_VECTOR *vec, const void *ptr_item)
325 {
326 int idx = _al_vector_find(vec, ptr_item);
327 if (idx >= 0) {
328 _al_vector_delete_at(vec, idx);
329 return true;
330 }
331 else
332 return false;
333 }
334
335
336
337 /* Internal function: _al_vector_free
338 *
339 * Free the space used by the vector. You really must do this at some
340 * stage. It is not enough to delete all the items in the vector (which you
341 * should usually do also).
342 */
_al_vector_free(_AL_VECTOR * vec)343 void _al_vector_free(_AL_VECTOR *vec)
344 {
345 ASSERT(vec);
346
347 if (vec->_items != NULL) {
348 al_free(vec->_items);
349 vec->_items = NULL;
350 }
351 vec->_size = 0;
352 vec->_unused = 0;
353 }
354
355
356
357 /*
358 * Local Variables:
359 * c-basic-offset: 3
360 * indent-tabs-mode: nil
361 * End:
362 */
363