1 /* -*- coding: utf-8 -*-
2 * ----------------------------------------------------------------------
3 * Copyright © 2011-2013, RedJack, LLC.
4 * All rights reserved.
5 *
6 * Please see the COPYING file in this distribution for license details.
7 * ----------------------------------------------------------------------
8 */
9
10 #include <assert.h>
11 #include <stdlib.h>
12 #include <string.h>
13
14 #include "libcork/core/types.h"
15 #include "libcork/ds/array.h"
16 #include "libcork/helpers/errors.h"
17
18 #ifndef CORK_ARRAY_DEBUG
19 #define CORK_ARRAY_DEBUG 0
20 #endif
21
22 #if CORK_ARRAY_DEBUG
23 #include <stdio.h>
24 #define DEBUG(...) \
25 do { \
26 fprintf(stderr, __VA_ARGS__); \
27 fprintf(stderr, "\n"); \
28 } while (0)
29 #else
30 #define DEBUG(...) /* nothing */
31 #endif
32
33
34 /*-----------------------------------------------------------------------
35 * Resizable arrays
36 */
37
38 struct cork_array_priv {
39 size_t allocated_count;
40 size_t allocated_size;
41 size_t element_size;
42 size_t initialized_count;
43 void *user_data;
44 cork_free_f free_user_data;
45 cork_init_f init;
46 cork_done_f done;
47 cork_init_f reuse;
48 cork_done_f remove;
49 };
50
51 void
cork_raw_array_init(struct cork_raw_array * array,size_t element_size)52 cork_raw_array_init(struct cork_raw_array *array, size_t element_size)
53 {
54 array->items = NULL;
55 array->size = 0;
56 array->priv = cork_new(struct cork_array_priv);
57 array->priv->allocated_count = 0;
58 array->priv->allocated_size = 0;
59 array->priv->element_size = element_size;
60 array->priv->initialized_count = 0;
61 array->priv->user_data = NULL;
62 array->priv->free_user_data = NULL;
63 array->priv->init = NULL;
64 array->priv->done = NULL;
65 array->priv->reuse = NULL;
66 array->priv->remove = NULL;
67 }
68
69 void
cork_raw_array_done(struct cork_raw_array * array)70 cork_raw_array_done(struct cork_raw_array *array)
71 {
72 if (array->priv->done != NULL) {
73 size_t i;
74 char *element = array->items;
75 for (i = 0; i < array->priv->initialized_count; i++) {
76 array->priv->done(array->priv->user_data, element);
77 element += array->priv->element_size;
78 }
79 }
80 if (array->items != NULL) {
81 cork_free(array->items, array->priv->allocated_size);
82 }
83 cork_free_user_data(array->priv);
84 cork_delete(struct cork_array_priv, array->priv);
85 }
86
87 void
cork_raw_array_set_callback_data(struct cork_raw_array * array,void * user_data,cork_free_f free_user_data)88 cork_raw_array_set_callback_data(struct cork_raw_array *array,
89 void *user_data, cork_free_f free_user_data)
90 {
91 array->priv->user_data = user_data;
92 array->priv->free_user_data = free_user_data;
93 }
94
95 void
cork_raw_array_set_init(struct cork_raw_array * array,cork_init_f init)96 cork_raw_array_set_init(struct cork_raw_array *array, cork_init_f init)
97 {
98 array->priv->init = init;
99 }
100
101 void
cork_raw_array_set_done(struct cork_raw_array * array,cork_done_f done)102 cork_raw_array_set_done(struct cork_raw_array *array, cork_done_f done)
103 {
104 array->priv->done = done;
105 }
106
107 void
cork_raw_array_set_reuse(struct cork_raw_array * array,cork_init_f reuse)108 cork_raw_array_set_reuse(struct cork_raw_array *array, cork_init_f reuse)
109 {
110 array->priv->reuse = reuse;
111 }
112
113 void
cork_raw_array_set_remove(struct cork_raw_array * array,cork_done_f remove)114 cork_raw_array_set_remove(struct cork_raw_array *array, cork_done_f remove)
115 {
116 array->priv->remove = remove;
117 }
118
119 size_t
cork_raw_array_element_size(const struct cork_raw_array * array)120 cork_raw_array_element_size(const struct cork_raw_array *array)
121 {
122 return array->priv->element_size;
123 }
124
125 void
cork_raw_array_clear(struct cork_raw_array * array)126 cork_raw_array_clear(struct cork_raw_array *array)
127 {
128 if (array->priv->remove != NULL) {
129 size_t i;
130 char *element = array->items;
131 for (i = 0; i < array->priv->initialized_count; i++) {
132 array->priv->remove(array->priv->user_data, element);
133 element += array->priv->element_size;
134 }
135 }
136 array->size = 0;
137 }
138
139 void *
cork_raw_array_elements(const struct cork_raw_array * array)140 cork_raw_array_elements(const struct cork_raw_array *array)
141 {
142 return array->items;
143 }
144
145 void *
cork_raw_array_at(const struct cork_raw_array * array,size_t index)146 cork_raw_array_at(const struct cork_raw_array *array, size_t index)
147 {
148 return ((char *) array->items) + (array->priv->element_size * index);
149 }
150
151 size_t
cork_raw_array_size(const struct cork_raw_array * array)152 cork_raw_array_size(const struct cork_raw_array *array)
153 {
154 return array->size;
155 }
156
157 bool
cork_raw_array_is_empty(const struct cork_raw_array * array)158 cork_raw_array_is_empty(const struct cork_raw_array *array)
159 {
160 return (array->size == 0);
161 }
162
163 void
cork_raw_array_ensure_size(struct cork_raw_array * array,size_t desired_count)164 cork_raw_array_ensure_size(struct cork_raw_array *array, size_t desired_count)
165 {
166 size_t desired_size;
167
168 DEBUG("--- Array %p: Ensure %zu %zu-byte elements",
169 array, desired_count, array->priv->element_size);
170 desired_size = desired_count * array->priv->element_size;
171
172 if (desired_size > array->priv->allocated_size) {
173 size_t new_count = array->priv->allocated_count * 2;
174 size_t new_size = array->priv->allocated_size * 2;
175 if (desired_size > new_size) {
176 new_count = desired_count;
177 new_size = desired_size;
178 }
179
180 DEBUG("--- Array %p: Reallocating %zu->%zu bytes",
181 array, array->priv->allocated_size, new_size);
182 array->items =
183 cork_realloc(array->items, array->priv->allocated_size, new_size);
184
185 array->priv->allocated_count = new_count;
186 array->priv->allocated_size = new_size;
187 }
188 }
189
190 void *
cork_raw_array_append(struct cork_raw_array * array)191 cork_raw_array_append(struct cork_raw_array *array)
192 {
193 size_t index;
194 void *element;
195 index = array->size++;
196 cork_raw_array_ensure_size(array, array->size);
197 element = cork_raw_array_at(array, index);
198
199 /* Call the init or reset callback, depending on whether this entry has been
200 * initialized before. */
201
202 /* Since we can currently only add elements by appending them one at a time,
203 * then this entry is either already initialized, or is the first
204 * uninitialized entry. */
205 assert(index <= array->priv->initialized_count);
206
207 if (index == array->priv->initialized_count) {
208 /* This element has not been initialized yet. */
209 array->priv->initialized_count++;
210 if (array->priv->init != NULL) {
211 array->priv->init(array->priv->user_data, element);
212 }
213 } else {
214 /* This element has already been initialized. */
215 if (array->priv->reuse != NULL) {
216 array->priv->reuse(array->priv->user_data, element);
217 }
218 }
219
220 return element;
221 }
222
223 int
cork_raw_array_copy(struct cork_raw_array * dest,const struct cork_raw_array * src,cork_copy_f copy,void * user_data)224 cork_raw_array_copy(struct cork_raw_array *dest,
225 const struct cork_raw_array *src,
226 cork_copy_f copy, void *user_data)
227 {
228 size_t i;
229 size_t reuse_count;
230 char *dest_element;
231
232 DEBUG("--- Copying %zu elements (%zu bytes) from %p to %p",
233 src->size, src->size * dest->priv->element_size, src, dest);
234 assert(dest->priv->element_size == src->priv->element_size);
235 cork_array_clear(dest);
236 cork_array_ensure_size(dest, src->size);
237
238 /* Initialize enough elements to hold the contents of src */
239 reuse_count = dest->priv->initialized_count;
240 if (src->size < reuse_count) {
241 reuse_count = src->size;
242 }
243
244 dest_element = dest->items;
245 if (dest->priv->reuse != NULL) {
246 DEBUG(" Calling reuse on elements 0-%zu", reuse_count);
247 for (i = 0; i < reuse_count; i++) {
248 dest->priv->reuse(dest->priv->user_data, dest_element);
249 dest_element += dest->priv->element_size;
250 }
251 } else {
252 dest_element += reuse_count * dest->priv->element_size;
253 }
254
255 if (dest->priv->init != NULL) {
256 DEBUG(" Calling init on elements %zu-%zu", reuse_count, src->size);
257 for (i = reuse_count; i < src->size; i++) {
258 dest->priv->init(dest->priv->user_data, dest_element);
259 dest_element += dest->priv->element_size;
260 }
261 }
262
263 if (src->size > dest->priv->initialized_count) {
264 dest->priv->initialized_count = src->size;
265 }
266
267 /* If the caller provided a copy function, let it copy each element in turn.
268 * Otherwise, bulk copy everything using memcpy. */
269 if (copy == NULL) {
270 memcpy(dest->items, src->items, src->size * dest->priv->element_size);
271 } else {
272 const char *src_element = src->items;
273 dest_element = dest->items;
274 for (i = 0; i < src->size; i++) {
275 rii_check(copy(user_data, dest_element, src_element));
276 dest_element += dest->priv->element_size;
277 src_element += dest->priv->element_size;
278 }
279 }
280
281 dest->size = src->size;
282 return 0;
283 }
284
285
286 /*-----------------------------------------------------------------------
287 * Pointer arrays
288 */
289
290 struct cork_pointer_array {
291 cork_free_f free;
292 };
293
294 static void
pointer__init(void * user_data,void * vvalue)295 pointer__init(void *user_data, void *vvalue)
296 {
297 void **value = vvalue;
298 *value = NULL;
299 }
300
301 static void
pointer__done(void * user_data,void * vvalue)302 pointer__done(void *user_data, void *vvalue)
303 {
304 struct cork_pointer_array *ptr_array = user_data;
305 void **value = vvalue;
306 if (*value != NULL) {
307 ptr_array->free(*value);
308 }
309 }
310
311 static void
pointer__remove(void * user_data,void * vvalue)312 pointer__remove(void *user_data, void *vvalue)
313 {
314 struct cork_pointer_array *ptr_array = user_data;
315 void **value = vvalue;
316 if (*value != NULL) {
317 ptr_array->free(*value);
318 }
319 *value = NULL;
320 }
321
322 static void
pointer__free(void * user_data)323 pointer__free(void *user_data)
324 {
325 struct cork_pointer_array *ptr_array = user_data;
326 cork_delete(struct cork_pointer_array, ptr_array);
327 }
328
329 void
cork_raw_pointer_array_init(struct cork_raw_array * array,cork_free_f free_ptr)330 cork_raw_pointer_array_init(struct cork_raw_array *array, cork_free_f free_ptr)
331 {
332 struct cork_pointer_array *ptr_array = cork_new(struct cork_pointer_array);
333 ptr_array->free = free_ptr;
334 cork_raw_array_init(array, sizeof(void *));
335 cork_array_set_callback_data(array, ptr_array, pointer__free);
336 cork_array_set_init(array, pointer__init);
337 cork_array_set_done(array, pointer__done);
338 cork_array_set_remove(array, pointer__remove);
339 }
340
341
342 /*-----------------------------------------------------------------------
343 * String arrays
344 */
345
346 void
cork_string_array_init(struct cork_string_array * array)347 cork_string_array_init(struct cork_string_array *array)
348 {
349 cork_raw_pointer_array_init
350 ((struct cork_raw_array *) array, (cork_free_f) cork_strfree);
351 }
352
353 void
cork_string_array_append(struct cork_string_array * array,const char * str)354 cork_string_array_append(struct cork_string_array *array, const char *str)
355 {
356 const char *copy = cork_strdup(str);
357 cork_array_append(array, copy);
358 }
359
360 static int
string__copy(void * user_data,void * vdest,const void * vsrc)361 string__copy(void *user_data, void *vdest, const void *vsrc)
362 {
363 const char **dest = vdest;
364 const char **src = (const char **) vsrc;
365 *dest = cork_strdup(*src);
366 return 0;
367 }
368
369 void
cork_string_array_copy(struct cork_string_array * dest,const struct cork_string_array * src)370 cork_string_array_copy(struct cork_string_array *dest,
371 const struct cork_string_array *src)
372 {
373 CORK_ATTR_UNUSED int rc;
374 rc = cork_array_copy(dest, src, string__copy, NULL);
375 /* cork_array_copy can only fail if the copy callback fails, and ours
376 * doesn't! */
377 assert(rc == 0);
378 }
379