1 /* $NetBSD: array.c,v 1.2 2017/01/28 21:31:45 christos Exp $ */
2
3 /*
4 * Copyright (c) 2010 Kungliga Tekniska Högskolan
5 * (Royal Institute of Technology, Stockholm, Sweden).
6 * All rights reserved.
7 *
8 * Portions Copyright (c) 2010 Apple Inc. All rights reserved.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 *
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 *
17 * 2. Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in the
19 * documentation and/or other materials provided with the distribution.
20 *
21 * 3. Neither the name of the Institute nor the names of its contributors
22 * may be used to endorse or promote products derived from this software
23 * without specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28 * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
29 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
30 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
31 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
32 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
34 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
35 * SUCH DAMAGE.
36 */
37
38 #include "baselocl.h"
39
40 /*
41 *
42 */
43
44 struct heim_array_data {
45 size_t len;
46 heim_object_t *val;
47 size_t allocated_len;
48 heim_object_t *allocated;
49 };
50
51 static void
array_dealloc(heim_object_t ptr)52 array_dealloc(heim_object_t ptr)
53 {
54 heim_array_t array = ptr;
55 size_t n;
56 for (n = 0; n < array->len; n++)
57 heim_release(array->val[n]);
58 free(array->allocated);
59 }
60
61 struct heim_type_data array_object = {
62 HEIM_TID_ARRAY,
63 "dict-object",
64 NULL,
65 array_dealloc,
66 NULL,
67 NULL,
68 NULL,
69 NULL
70 };
71
72 /**
73 * Allocate an array
74 *
75 * @return A new allocated array, free with heim_release()
76 */
77
78 heim_array_t
heim_array_create(void)79 heim_array_create(void)
80 {
81 heim_array_t array;
82
83 array = _heim_alloc_object(&array_object, sizeof(*array));
84 if (array == NULL)
85 return NULL;
86
87 array->allocated = NULL;
88 array->allocated_len = 0;
89 array->val = NULL;
90 array->len = 0;
91
92 return array;
93 }
94
95 /**
96 * Get type id of an dict
97 *
98 * @return the type id
99 */
100
101 heim_tid_t
heim_array_get_type_id(void)102 heim_array_get_type_id(void)
103 {
104 return HEIM_TID_ARRAY;
105 }
106
107 /**
108 * Append object to array
109 *
110 * @param array array to add too
111 * @param object the object to add
112 *
113 * @return zero if added, errno otherwise
114 */
115
116 int
heim_array_append_value(heim_array_t array,heim_object_t object)117 heim_array_append_value(heim_array_t array, heim_object_t object)
118 {
119 heim_object_t *ptr;
120 size_t leading = array->val - array->allocated; /* unused leading slots */
121 size_t trailing = array->allocated_len - array->len - leading;
122 size_t new_len;
123
124 if (trailing > 0) {
125 /* We have pre-allocated space; use it */
126 array->val[array->len++] = heim_retain(object);
127 return 0;
128 }
129
130 if (leading > (array->len + 1)) {
131 /*
132 * We must have appending to, and deleting at index 0 from this
133 * array a lot; don't want to grow forever!
134 */
135 (void) memmove(&array->allocated[0], &array->val[0],
136 array->len * sizeof(array->val[0]));
137 array->val = array->allocated;
138
139 /* We have pre-allocated space; use it */
140 array->val[array->len++] = heim_retain(object);
141 return 0;
142 }
143
144 /* Pre-allocate extra .5 times number of used slots */
145 new_len = leading + array->len + 1 + (array->len >> 1);
146 ptr = realloc(array->allocated, new_len * sizeof(array->val[0]));
147 if (ptr == NULL)
148 return ENOMEM;
149 array->allocated = ptr;
150 array->allocated_len = new_len;
151 array->val = &ptr[leading];
152 array->val[array->len++] = heim_retain(object);
153
154 return 0;
155 }
156
157 /*
158 * Internal function to insert at index 0, taking care to optimize the
159 * case where we're always inserting at index 0, particularly the case
160 * where we insert at index 0 and delete from the right end.
161 */
162 static int
heim_array_prepend_value(heim_array_t array,heim_object_t object)163 heim_array_prepend_value(heim_array_t array, heim_object_t object)
164 {
165 heim_object_t *ptr;
166 size_t leading = array->val - array->allocated; /* unused leading slots */
167 size_t trailing = array->allocated_len - array->len - leading;
168 size_t new_len;
169
170 if (leading > 0) {
171 /* We have pre-allocated space; use it */
172 array->val--;
173 array->val[0] = heim_retain(object);
174 array->len++;
175 return 0;
176 }
177 if (trailing > (array->len + 1)) {
178 /*
179 * We must have prepending to, and deleting at index
180 * array->len - 1 from this array a lot; don't want to grow
181 * forever!
182 */
183 (void) memmove(&array->allocated[array->len], &array->val[0],
184 array->len * sizeof(array->val[0]));
185 array->val = &array->allocated[array->len];
186
187 /* We have pre-allocated space; use it */
188 array->val--;
189 array->val[0] = heim_retain(object);
190 array->len++;
191 return 0;
192 }
193 /* Pre-allocate extra .5 times number of used slots */
194 new_len = array->len + 1 + trailing + (array->len >> 1);
195 ptr = realloc(array->allocated, new_len * sizeof(array->val[0]));
196 if (ptr == NULL)
197 return ENOMEM;
198 (void) memmove(&ptr[1], &ptr[0], array->len * sizeof (array->val[0]));
199 array->allocated = ptr;
200 array->allocated_len = new_len;
201 array->val = &ptr[0];
202 array->val[0] = heim_retain(object);
203 array->len++;
204
205 return 0;
206 }
207
208 /**
209 * Insert an object at a given index in an array
210 *
211 * @param array array to add too
212 * @param idx index where to add element (-1 == append, -2 next to last, ...)
213 * @param object the object to add
214 *
215 * @return zero if added, errno otherwise
216 */
217
218 int
heim_array_insert_value(heim_array_t array,size_t idx,heim_object_t object)219 heim_array_insert_value(heim_array_t array, size_t idx, heim_object_t object)
220 {
221 int ret;
222
223 if (idx == 0)
224 return heim_array_prepend_value(array, object);
225 else if (idx > array->len)
226 heim_abort("index too large");
227
228 /*
229 * We cheat: append this element then rotate elements around so we
230 * have this new element at the desired location, unless we're truly
231 * appending the new element. This means reusing array growth in
232 * heim_array_append_value() instead of duplicating that here.
233 */
234 ret = heim_array_append_value(array, object);
235 if (ret != 0 || idx == (array->len - 1))
236 return ret;
237 /*
238 * Shift to the right by one all the elements after idx, then set
239 * [idx] to the new object.
240 */
241 (void) memmove(&array->val[idx + 1], &array->val[idx],
242 (array->len - idx - 1) * sizeof(array->val[0]));
243 array->val[idx] = heim_retain(object);
244
245 return 0;
246 }
247
248 /**
249 * Iterate over all objects in array
250 *
251 * @param array array to iterate over
252 * @param ctx context passed to fn
253 * @param fn function to call on each object
254 */
255
256 void
heim_array_iterate_f(heim_array_t array,void * ctx,heim_array_iterator_f_t fn)257 heim_array_iterate_f(heim_array_t array, void *ctx, heim_array_iterator_f_t fn)
258 {
259 size_t n;
260 int stop = 0;
261 for (n = 0; n < array->len; n++) {
262 fn(array->val[n], ctx, &stop);
263 if (stop)
264 return;
265 }
266 }
267
268 #ifdef __BLOCKS__
269 /**
270 * Iterate over all objects in array
271 *
272 * @param array array to iterate over
273 * @param fn block to call on each object
274 */
275
276 void
277 heim_array_iterate(heim_array_t array, void (^fn)(heim_object_t, int *))
278 {
279 size_t n;
280 int stop = 0;
281 for (n = 0; n < array->len; n++) {
282 fn(array->val[n], &stop);
283 if (stop)
284 return;
285 }
286 }
287 #endif
288
289 /**
290 * Iterate over all objects in array, backwards
291 *
292 * @param array array to iterate over
293 * @param ctx context passed to fn
294 * @param fn function to call on each object
295 */
296
297 void
heim_array_iterate_reverse_f(heim_array_t array,void * ctx,heim_array_iterator_f_t fn)298 heim_array_iterate_reverse_f(heim_array_t array, void *ctx, heim_array_iterator_f_t fn)
299 {
300 size_t n;
301 int stop = 0;
302
303 for (n = array->len; n > 0; n--) {
304 fn(array->val[n - 1], ctx, &stop);
305 if (stop)
306 return;
307 }
308 }
309
310 #ifdef __BLOCKS__
311 /**
312 * Iterate over all objects in array, backwards
313 *
314 * @param array array to iterate over
315 * @param fn block to call on each object
316 */
317
318 void
319 heim_array_iterate_reverse(heim_array_t array, void (^fn)(heim_object_t, int *))
320 {
321 size_t n;
322 int stop = 0;
323 for (n = array->len; n > 0; n--) {
324 fn(array->val[n - 1], &stop);
325 if (stop)
326 return;
327 }
328 }
329 #endif
330
331 /**
332 * Get length of array
333 *
334 * @param array array to get length of
335 *
336 * @return length of array
337 */
338
339 size_t
heim_array_get_length(heim_array_t array)340 heim_array_get_length(heim_array_t array)
341 {
342 return array->len;
343 }
344
345 /**
346 * Get value of element at array index
347 *
348 * @param array array copy object from
349 * @param idx index of object, 0 based, must be smaller then
350 * heim_array_get_length()
351 *
352 * @return a not-retained copy of the object
353 */
354
355 heim_object_t
heim_array_get_value(heim_array_t array,size_t idx)356 heim_array_get_value(heim_array_t array, size_t idx)
357 {
358 if (idx >= array->len)
359 heim_abort("index too large");
360 return array->val[idx];
361 }
362
363 /**
364 * Get value of element at array index
365 *
366 * @param array array copy object from
367 * @param idx index of object, 0 based, must be smaller then
368 * heim_array_get_length()
369 *
370 * @return a retained copy of the object
371 */
372
373 heim_object_t
heim_array_copy_value(heim_array_t array,size_t idx)374 heim_array_copy_value(heim_array_t array, size_t idx)
375 {
376 if (idx >= array->len)
377 heim_abort("index too large");
378 return heim_retain(array->val[idx]);
379 }
380
381 /**
382 * Set value at array index
383 *
384 * @param array array copy object from
385 * @param idx index of object, 0 based, must be smaller then
386 * heim_array_get_length()
387 * @param value value to set
388 *
389 */
390
391 void
heim_array_set_value(heim_array_t array,size_t idx,heim_object_t value)392 heim_array_set_value(heim_array_t array, size_t idx, heim_object_t value)
393 {
394 if (idx >= array->len)
395 heim_abort("index too large");
396 heim_release(array->val[idx]);
397 array->val[idx] = heim_retain(value);
398 }
399
400 /**
401 * Delete value at idx
402 *
403 * @param array the array to modify
404 * @param idx the key to delete
405 */
406
407 void
heim_array_delete_value(heim_array_t array,size_t idx)408 heim_array_delete_value(heim_array_t array, size_t idx)
409 {
410 heim_object_t obj;
411 if (idx >= array->len)
412 heim_abort("index too large");
413 obj = array->val[idx];
414
415 array->len--;
416
417 /*
418 * Deleting the first or last elements is cheap, as we leave
419 * allocated space for opportunistic reuse later; no realloc(), no
420 * memmove(). All others require a memmove().
421 *
422 * If we ever need to optimize deletion of non-last/ non-first
423 * element we can use a tagged object type to signify "deleted
424 * value" so we can leave holes in the array, avoid memmove()s on
425 * delete, and opportunistically re-use those holes on insert.
426 */
427 if (idx == 0)
428 array->val++;
429 else if (idx < array->len)
430 (void) memmove(&array->val[idx], &array->val[idx + 1],
431 (array->len - idx) * sizeof(array->val[0]));
432
433 heim_release(obj);
434 }
435
436 /**
437 * Filter out entres of array when function return true
438 *
439 * @param array the array to modify
440 * @param fn filter function
441 */
442
443 void
heim_array_filter_f(heim_array_t array,void * ctx,heim_array_filter_f_t fn)444 heim_array_filter_f(heim_array_t array, void *ctx, heim_array_filter_f_t fn)
445 {
446 size_t n = 0;
447
448 while (n < array->len) {
449 if (fn(array->val[n], ctx)) {
450 heim_array_delete_value(array, n);
451 } else {
452 n++;
453 }
454 }
455 }
456
457 #ifdef __BLOCKS__
458
459 /**
460 * Filter out entres of array when block return true
461 *
462 * @param array the array to modify
463 * @param block filter block
464 */
465
466 void
467 heim_array_filter(heim_array_t array, int (^block)(heim_object_t))
468 {
469 size_t n = 0;
470
471 while (n < array->len) {
472 if (block(array->val[n])) {
473 heim_array_delete_value(array, n);
474 } else {
475 n++;
476 }
477 }
478 }
479
480 #endif /* __BLOCKS__ */
481