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 };
  68
  69 /**
  70  * Allocate an array
  71  *
  72  * @return A new allocated array, free with heim_release()
  73  */
  74
  75 heim_array_t
  76 heim_array_create(void)
  77 {
  78     heim_array_t array;
  79
  80     array = _heim_alloc_object(&array_object, sizeof(*array));
  81     if (array == NULL)
  82         return NULL;
  83
  84     array->allocated = NULL;
  85     array->allocated_len = 0;
  86     array->val = NULL;
  87     array->len = 0;
  88
  89     return array;
  90 }
  91
  92 /**
  93  * Get type id of an dict
  94  *
  95  * @return the type id
  96  */
  97
  98 heim_tid_t
  99 heim_array_get_type_id(void)
 100 {
 101     return HEIM_TID_ARRAY;
 102 }
 103
 104 /**
 105  * Append object to array
 106  *
 107  * @param array array to add too
 108  * @param object the object to add
 109  *
 110  * @return zero if added, errno otherwise
 111  */
 112
 113 int
 114 heim_array_append_value(heim_array_t array, heim_object_t object)
 115 {
 116     heim_object_t *ptr;
 117     size_t leading = array->val - array->allocated; /* unused leading slots */
 118     size_t trailing = array->allocated_len - array->len - leading;
 119     size_t new_len;
 120
 121     if (trailing > 0) {
 122         /* We have pre-allocated space; use it */
 123         array->val[array->len++] = heim_retain(object);
 124         return 0;
 125     }
 126
 127     if (leading > (array->len + 1)) {
 128         /*
 129          * We must have appending to, and deleting at index 0 from this
 130          * array a lot; don't want to grow forever!
 131          */
 132         (void) memmove(&array->allocated[0], &array->val[0],
 133                        array->len * sizeof(array->val[0]));
 134         array->val = array->allocated;
 135
 136         /* We have pre-allocated space; use it */
 137         array->val[array->len++] = heim_retain(object);
 138         return 0;
 139     }
 140
 141     /* Pre-allocate extra .5 times number of used slots */
 142     new_len = leading + array->len + 1 + (array->len >> 1);
 143     ptr = realloc(array->allocated, new_len * sizeof(array->val[0]));
 144     if (ptr == NULL)
 145         return ENOMEM;
 146     array->allocated = ptr;
 147     array->allocated_len = new_len;
 148     array->val = &ptr[leading];
 149     array->val[array->len++] = heim_retain(object);
 150
 151     return 0;
 152 }
 153
 154 /*
 155  * Internal function to insert at index 0, taking care to optimize the
 156  * case where we're always inserting at index 0, particularly the case
 157  * where we insert at index 0 and delete from the right end.
 158  */
 159 static int
 160 heim_array_prepend_value(heim_array_t array, heim_object_t object)
 161 {
 162     heim_object_t *ptr;
 163     size_t leading = array->val - array->allocated; /* unused leading slots */
 164     size_t trailing = array->allocated_len - array->len - leading;
 165     size_t new_len;
 166
 167     if (leading > 0) {
 168         /* We have pre-allocated space; use it */
 169         array->val--;
 170         array->val[0] = heim_retain(object);
 171         array->len++;
 172         return 0;
 173     }
 174     if (trailing > (array->len + 1)) {
 175         /*
 176          * We must have prepending to, and deleting at index
 177          * array->len - 1 from this array a lot; don't want to grow
 178          * forever!
 179          */
 180         (void) memmove(&array->allocated[array->len], &array->val[0],
 181                        array->len * sizeof(array->val[0]));
 182         array->val = &array->allocated[array->len];
 183
 184         /* We have pre-allocated space; use it */
 185         array->val--;
 186         array->val[0] = heim_retain(object);
 187         array->len++;
 188         return 0;
 189     }
 190     /* Pre-allocate extra .5 times number of used slots */
 191     new_len = array->len + 1 + trailing + (array->len >> 1);
 192     ptr = realloc(array->allocated, new_len * sizeof(array->val[0]));
 193     if (ptr == NULL)
 194         return ENOMEM;
 195     (void) memmove(&ptr[1], &ptr[0], array->len * sizeof (array->val[0]));
 196     array->allocated = ptr;
 197     array->allocated_len = new_len;
 198     array->val = &ptr[0];
 199     array->val[0] = heim_retain(object);
 200     array->len++;
 201
 202     return 0;
 203 }
 204
 205 /**
 206  * Insert an object at a given index in an array
 207  *
 208  * @param array array to add too
 209  * @param idx index where to add element (-1 == append, -2 next to last, ...)
 210  * @param object the object to add
 211  *
 212  * @return zero if added, errno otherwise
 213  */
 214
 215 int
 216 heim_array_insert_value(heim_array_t array, size_t idx, heim_object_t object)
 217 {
 218     int ret;
 219
 220     if (idx == 0)
 221         return heim_array_prepend_value(array, object);
 222     else if (idx > array->len)
 223         heim_abort("index too large");
 224
 225     /*
 226      * We cheat: append this element then rotate elements around so we
 227      * have this new element at the desired location, unless we're truly
 228      * appending the new element.  This means reusing array growth in
 229      * heim_array_append_value() instead of duplicating that here.
 230      */
 231     ret = heim_array_append_value(array, object);
 232     if (ret != 0 || idx == (array->len - 1))
 233         return ret;
 234     /*
 235      * Shift to the right by one all the elements after idx, then set
 236      * [idx] to the new object.
 237      */
 238     (void) memmove(&array->val[idx + 1], &array->val[idx],
 239                    (array->len - idx - 1) * sizeof(array->val[0]));
 240     array->val[idx] = heim_retain(object);
 241
 242     return 0;
 243 }
 244
 245 /**
 246  * Iterate over all objects in array
 247  *
 248  * @param array array to iterate over
 249  * @param ctx context passed to fn
 250  * @param fn function to call on each object
 251  */
 252
 253 void
 254 heim_array_iterate_f(heim_array_t array, void *ctx, heim_array_iterator_f_t fn)
 255 {
 256     size_t n;
 257     for (n = 0; n < array->len; n++)
 258         fn(array->val[n], ctx);
 259 }
 260
 261 #ifdef __BLOCKS__
 262 /**
 263  * Iterate over all objects in array
 264  *
 265  * @param array array to iterate over
 266  * @param fn block to call on each object
 267  */
 268
 269 void
 270 heim_array_iterate(heim_array_t array, void (^fn)(heim_object_t))
 271 {
 272     size_t n;
 273     for (n = 0; n < array->len; n++)
 274         fn(array->val[n]);
 275 }
 276 #endif
 277
 278 /**
 279  * Iterate over all objects in array, backwards
 280  *
 281  * @param array array to iterate over
 282  * @param ctx context passed to fn
 283  * @param fn function to call on each object
 284  */
 285
 286 void
 287 heim_array_iterate_reverse_f(heim_array_t array, void *ctx, heim_array_iterator_f_t fn)
 288 {
 289     size_t n;
 290     for (n = array->len; n > 0; n--)
 291         fn(array->val[n - 1], ctx);
 292 }
 293
 294 #ifdef __BLOCKS__
 295 /**
 296  * Iterate over all objects in array, backwards
 297  *
 298  * @param array array to iterate over
 299  * @param fn block to call on each object
 300  */
 301
 302 void
 303 heim_array_iterate_reverse(heim_array_t array, void (^fn)(heim_object_t))
 304 {
 305     size_t n;
 306     for (n = array->len; n > 0; n--)
 307         fn(array->val[n - 1]);
 308 }
 309 #endif
 310
 311 /**
 312  * Get length of array
 313  *
 314  * @param array array to get length of
 315  *
 316  * @return length of array
 317  */
 318
 319 size_t
 320 heim_array_get_length(heim_array_t array)
 321 {
 322     return array->len;
 323 }
 324
 325 /**
 326  * Get value of element at array index
 327  *
 328  * @param array array copy object from
 329  * @param idx index of object, 0 based, must be smaller then
 330  *        heim_array_get_length()
 331  *
 332  * @return a not-retained copy of the object
 333  */
 334
 335 heim_object_t
 336 heim_array_get_value(heim_array_t array, size_t idx)
 337 {
 338     if (idx >= array->len)
 339         heim_abort("index too large");
 340     return array->val[idx];
 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 retained copy of the object
 351  */
 352
 353 heim_object_t
 354 heim_array_copy_value(heim_array_t array, size_t idx)
 355 {
 356     if (idx >= array->len)
 357         heim_abort("index too large");
 358     return heim_retain(array->val[idx]);
 359 }
 360
 361 /**
 362  * Set value 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  * @param value value to set
 368  *
 369  */
 370
 371 void
 372 heim_array_set_value(heim_array_t array, size_t idx, heim_object_t value)
 373 {
 374     if (idx >= array->len)
 375         heim_abort("index too large");
 376     heim_release(array->val[idx]);
 377     array->val[idx] = heim_retain(value);
 378 }
 379
 380 /**
 381  * Delete value at idx
 382  *
 383  * @param array the array to modify
 384  * @param idx the key to delete
 385  */
 386
 387 void
 388 heim_array_delete_value(heim_array_t array, size_t idx)
 389 {
 390     heim_object_t obj;
 391     if (idx >= array->len)
 392         heim_abort("index too large");
 393     obj = array->val[idx];
 394
 395     array->len--;
 396
 397     /*
 398      * Deleting the first or last elements is cheap, as we leave
 399      * allocated space for opportunistic reuse later; no realloc(), no
 400      * memmove().  All others require a memmove().
 401      *
 402      * If we ever need to optimize deletion of non-last/ non-first
 403      * element we can use a tagged object type to signify "deleted
 404      * value" so we can leave holes in the array, avoid memmove()s on
 405      * delete, and opportunistically re-use those holes on insert.
 406      */
 407     if (idx == 0)
 408         array->val++;
 409     else if (idx < array->len)
 410         (void) memmove(&array->val[idx], &array->val[idx + 1],
 411                        (array->len - idx) * sizeof(array->val[0]));
 412
 413     heim_release(obj);
 414 }
 415
 416 #ifdef __BLOCKS__
 417 /**
 418  * Get value at idx
 419  *
 420  * @param array the array to modify
 421  * @param idx the key to delete
 422  */
 423
 424 void
 425 heim_array_filter(heim_array_t array, int (^block)(heim_object_t))
 426 {
 427     size_t n = 0;
 428
 429     while (n < array->len) {
 430         if (block(array->val[n])) {
 431             heim_array_delete_value(array, n);
 432         } else {
 433             n++;
 434         }
 435     }
 436 }
 437
 438 #endif /* __BLOCKS__ */