Debian Codegraph @

lib/base/array.c

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