base/array.c

   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     for (n = 0; n < array->len; n++)
 259         fn(array->val[n], ctx);
 260 }
 261
 262 #ifdef __BLOCKS__
 263 /**
 264  * Iterate over all objects in array
 265  *
 266  * @param array array to iterate over
 267  * @param fn block to call on each object
 268  */
 269
 270 void
 271 heim_array_iterate(heim_array_t array, void (^fn)(heim_object_t))
 272 {
 273     size_t n;
 274     for (n = 0; n < array->len; n++)
 275         fn(array->val[n]);
 276 }
 277 #endif
 278
 279 /**
 280  * Iterate over all objects in array, backwards
 281  *
 282  * @param array array to iterate over
 283  * @param ctx context passed to fn
 284  * @param fn function to call on each object
 285  */
 286
 287 void
 288 heim_array_iterate_reverse_f(heim_array_t array, void *ctx, heim_array_iterator_f_t fn)
 289 {
 290     size_t n;
 291     for (n = array->len; n > 0; n--)
 292         fn(array->val[n - 1], ctx);
 293 }
 294
 295 #ifdef __BLOCKS__
 296 /**
 297  * Iterate over all objects in array, backwards
 298  *
 299  * @param array array to iterate over
 300  * @param fn block to call on each object
 301  */
 302
 303 void
 304 heim_array_iterate_reverse(heim_array_t array, void (^fn)(heim_object_t))
 305 {
 306     size_t n;
 307     for (n = array->len; n > 0; n--)
 308         fn(array->val[n - 1]);
 309 }
 310 #endif
 311
 312 /**
 313  * Get length of array
 314  *
 315  * @param array array to get length of
 316  *
 317  * @return length of array
 318  */
 319
 320 size_t
 321 heim_array_get_length(heim_array_t array)
 322 {
 323     return array->len;
 324 }
 325
 326 /**
 327  * Get value of element at array index
 328  *
 329  * @param array array copy object from
 330  * @param idx index of object, 0 based, must be smaller then
 331  *        heim_array_get_length()
 332  *
 333  * @return a not-retained copy of the object
 334  */
 335
 336 heim_object_t
 337 heim_array_get_value(heim_array_t array, size_t idx)
 338 {
 339     if (idx >= array->len)
 340         heim_abort("index too large");
 341     return array->val[idx];
 342 }
 343
 344 /**
 345  * Get value of element at array index
 346  *
 347  * @param array array copy object from
 348  * @param idx index of object, 0 based, must be smaller then
 349  *        heim_array_get_length()
 350  *
 351  * @return a retained copy of the object
 352  */
 353
 354 heim_object_t
 355 heim_array_copy_value(heim_array_t array, size_t idx)
 356 {
 357     if (idx >= array->len)
 358         heim_abort("index too large");
 359     return heim_retain(array->val[idx]);
 360 }
 361
 362 /**
 363  * Set value at array index
 364  *
 365  * @param array array copy object from
 366  * @param idx index of object, 0 based, must be smaller then
 367  *        heim_array_get_length()
 368  * @param value value to set
 369  *
 370  */
 371
 372 void
 373 heim_array_set_value(heim_array_t array, size_t idx, heim_object_t value)
 374 {
 375     if (idx >= array->len)
 376         heim_abort("index too large");
 377     heim_release(array->val[idx]);
 378     array->val[idx] = heim_retain(value);
 379 }
 380
 381 /**
 382  * Delete value at idx
 383  *
 384  * @param array the array to modify
 385  * @param idx the key to delete
 386  */
 387
 388 void
 389 heim_array_delete_value(heim_array_t array, size_t idx)
 390 {
 391     heim_object_t obj;
 392     if (idx >= array->len)
 393         heim_abort("index too large");
 394     obj = array->val[idx];
 395
 396     array->len--;
 397
 398     /*
 399      * Deleting the first or last elements is cheap, as we leave
 400      * allocated space for opportunistic reuse later; no realloc(), no
 401      * memmove().  All others require a memmove().
 402      *
 403      * If we ever need to optimize deletion of non-last/ non-first
 404      * element we can use a tagged object type to signify "deleted
 405      * value" so we can leave holes in the array, avoid memmove()s on
 406      * delete, and opportunistically re-use those holes on insert.
 407      */
 408     if (idx == 0)
 409         array->val++;
 410     else if (idx < array->len)
 411         (void) memmove(&array->val[idx], &array->val[idx + 1],
 412                        (array->len - idx) * sizeof(array->val[0]));
 413
 414     heim_release(obj);
 415 }
 416
 417 #ifdef __BLOCKS__
 418 /**
 419  * Get value at idx
 420  *
 421  * @param array the array to modify
 422  * @param idx the key to delete
 423  */
 424
 425 void
 426 heim_array_filter(heim_array_t array, int (^block)(heim_object_t))
 427 {
 428     size_t n = 0;
 429
 430     while (n < array->len) {
 431         if (block(array->val[n])) {
 432             heim_array_delete_value(array, n);
 433         } else {
 434             n++;
 435         }
 436     }
 437 }
 438
 439 #endif /* __BLOCKS__ */