lib/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     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__ */