Line data Source code
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 HEIM_CALLCONV
50 1572173 : array_dealloc(heim_object_t ptr)
51 : {
52 1572173 : heim_array_t array = ptr;
53 47889 : size_t n;
54 2126831 : for (n = 0; n < array->len; n++)
55 554658 : heim_release(array->val[n]);
56 1572173 : free(array->allocated);
57 1572173 : }
58 :
59 : struct heim_type_data array_object = {
60 : HEIM_TID_ARRAY,
61 : "array-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 1604813 : heim_array_create(void)
78 : {
79 49170 : heim_array_t array;
80 :
81 1604813 : array = _heim_alloc_object(&array_object, sizeof(*array));
82 1604813 : if (array == NULL)
83 0 : return NULL;
84 :
85 1604813 : array->allocated = NULL;
86 1604813 : array->allocated_len = 0;
87 1604813 : array->val = NULL;
88 1604813 : array->len = 0;
89 :
90 1604813 : 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 0 : heim_array_get_type_id(void)
101 : {
102 0 : 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 632268 : heim_array_append_value(heim_array_t array, heim_object_t object)
116 : {
117 22840 : heim_object_t *ptr;
118 632268 : size_t leading = array->val - array->allocated; /* unused leading slots */
119 632268 : size_t trailing = array->allocated_len - array->len - leading;
120 22840 : size_t new_len;
121 :
122 632268 : if (trailing > 0) {
123 : /* We have pre-allocated space; use it */
124 0 : array->val[array->len++] = heim_retain(object);
125 0 : return 0;
126 : }
127 :
128 632268 : 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 0 : (void) memmove(&array->allocated[0], &array->val[0],
134 0 : array->len * sizeof(array->val[0]));
135 0 : array->val = array->allocated;
136 :
137 : /* We have pre-allocated space; use it */
138 0 : array->val[array->len++] = heim_retain(object);
139 0 : return 0;
140 : }
141 :
142 : /* Pre-allocate extra .5 times number of used slots */
143 632268 : new_len = leading + array->len + 1 + (array->len >> 1);
144 632268 : ptr = realloc(array->allocated, new_len * sizeof(array->val[0]));
145 632268 : if (ptr == NULL)
146 0 : return ENOMEM;
147 632268 : array->allocated = ptr;
148 632268 : array->allocated_len = new_len;
149 632268 : array->val = &ptr[leading];
150 632268 : array->val[array->len++] = heim_retain(object);
151 :
152 632268 : 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 0 : heim_array_prepend_value(heim_array_t array, heim_object_t object)
162 : {
163 0 : heim_object_t *ptr;
164 0 : size_t leading = array->val - array->allocated; /* unused leading slots */
165 0 : size_t trailing = array->allocated_len - array->len - leading;
166 0 : size_t new_len;
167 :
168 0 : if (leading > 0) {
169 : /* We have pre-allocated space; use it */
170 0 : array->val--;
171 0 : array->val[0] = heim_retain(object);
172 0 : array->len++;
173 0 : return 0;
174 : }
175 0 : 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 0 : (void) memmove(&array->allocated[array->len], &array->val[0],
182 0 : array->len * sizeof(array->val[0]));
183 0 : array->val = &array->allocated[array->len];
184 :
185 : /* We have pre-allocated space; use it */
186 0 : array->val--;
187 0 : array->val[0] = heim_retain(object);
188 0 : array->len++;
189 0 : return 0;
190 : }
191 : /* Pre-allocate extra .5 times number of used slots */
192 0 : new_len = array->len + 1 + trailing + (array->len >> 1);
193 0 : ptr = realloc(array->allocated, new_len * sizeof(array->val[0]));
194 0 : if (ptr == NULL)
195 0 : return ENOMEM;
196 0 : (void) memmove(&ptr[1], &ptr[0], array->len * sizeof (array->val[0]));
197 0 : array->allocated = ptr;
198 0 : array->allocated_len = new_len;
199 0 : array->val = &ptr[0];
200 0 : array->val[0] = heim_retain(object);
201 0 : array->len++;
202 :
203 0 : 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 0 : heim_array_insert_value(heim_array_t array, size_t idx, heim_object_t object)
218 : {
219 0 : int ret;
220 :
221 0 : if (idx == 0)
222 0 : return heim_array_prepend_value(array, object);
223 0 : else if (idx > array->len)
224 0 : 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 0 : ret = heim_array_append_value(array, object);
233 0 : if (ret != 0 || idx == (array->len - 1))
234 0 : 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 0 : (void) memmove(&array->val[idx + 1], &array->val[idx],
240 0 : (array->len - idx - 1) * sizeof(array->val[0]));
241 0 : array->val[idx] = heim_retain(object);
242 :
243 0 : 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 2087379 : heim_array_iterate_f(heim_array_t array, void *ctx, heim_array_iterator_f_t fn)
256 : {
257 67495 : size_t n;
258 2087379 : int stop = 0;
259 3000227 : for (n = 0; n < array->len; n++) {
260 1207327 : fn(array->val[n], ctx, &stop);
261 1207327 : if (stop)
262 294479 : 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 0 : heim_array_iterate_reverse_f(heim_array_t array, void *ctx, heim_array_iterator_f_t fn)
297 : {
298 0 : size_t n;
299 0 : int stop = 0;
300 :
301 0 : for (n = array->len; n > 0; n--) {
302 0 : fn(array->val[n - 1], ctx, &stop);
303 0 : if (stop)
304 0 : 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 143487 : heim_array_get_length(heim_array_t array)
339 : {
340 143487 : 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 0 : heim_array_get_value(heim_array_t array, size_t idx)
355 : {
356 0 : if (idx >= array->len)
357 0 : heim_abort("index too large");
358 0 : 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 44970 : heim_array_copy_value(heim_array_t array, size_t idx)
373 : {
374 44970 : if (idx >= array->len)
375 0 : heim_abort("index too large");
376 44970 : 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 0 : heim_array_set_value(heim_array_t array, size_t idx, heim_object_t value)
391 : {
392 0 : if (idx >= array->len)
393 0 : heim_abort("index too large");
394 0 : heim_release(array->val[idx]);
395 0 : array->val[idx] = heim_retain(value);
396 0 : }
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 44970 : heim_array_delete_value(heim_array_t array, size_t idx)
407 : {
408 1170 : heim_object_t obj;
409 44970 : if (idx >= array->len)
410 0 : heim_abort("index too large");
411 44970 : obj = array->val[idx];
412 :
413 44970 : 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 44970 : if (idx == 0)
426 44970 : array->val++;
427 0 : else if (idx < array->len)
428 1170 : (void) memmove(&array->val[idx], &array->val[idx + 1],
429 0 : (array->len - idx) * sizeof(array->val[0]));
430 :
431 44970 : heim_release(obj);
432 44970 : }
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 98517 : heim_array_filter_f(heim_array_t array, void *ctx, heim_array_filter_f_t fn)
443 : {
444 98517 : size_t n = 0;
445 :
446 189283 : while (n < array->len) {
447 90766 : if (fn(array->val[n], ctx)) {
448 0 : heim_array_delete_value(array, n);
449 : } else {
450 90766 : n++;
451 : }
452 : }
453 98517 : }
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__ */
|
