src/cairo-array.c

   1 /* cairo - a vector graphics library with display and print output
   2  *
   3  * Copyright © 2004 Red Hat, Inc
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it either under the terms of the GNU Lesser General Public
   7  * License version 2.1 as published by the Free Software Foundation
   8  * (the "LGPL") or, at your option, under the terms of the Mozilla
   9  * Public License Version 1.1 (the "MPL"). If you do not alter this
  10  * notice, a recipient may use your version of this file under either
  11  * the MPL or the LGPL.
  12  *
  13  * You should have received a copy of the LGPL along with this library
  14  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  15  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  16  * You should have received a copy of the MPL along with this library
  17  * in the file COPYING-MPL-1.1
  18  *
  19  * The contents of this file are subject to the Mozilla Public License
  20  * Version 1.1 (the "License"); you may not use this file except in
  21  * compliance with the License. You may obtain a copy of the License at
  22  * http://www.mozilla.org/MPL/
  23  *
  24  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  25  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  26  * the specific language governing rights and limitations.
  27  *
  28  * The Original Code is the cairo graphics library.
  29  *
  30  * The Initial Developer of the Original Code is University of Southern
  31  * California.
  32  *
  33  * Contributor(s):
  34  *      Kristian Høgsberg <krh@redhat.com>
  35  *      Carl Worth <cworth@cworth.org>
  36  */
  37
  38 #include "cairoint.h"
  39
  40 /**
  41  * _cairo_array_init:
  42  *
  43  * Initialize a new #cairo_array_t object to store objects each of size
  44  * @element_size.
  45  *
  46  * The #cairo_array_t object provides grow-by-doubling storage. It
  47  * never interprets the data passed to it, nor does it provide any
  48  * sort of callback mechanism for freeing resources held onto by
  49  * stored objects.
  50  *
  51  * When finished using the array, _cairo_array_fini() should be
  52  * called to free resources allocated during use of the array.
  53  **/
  54 void
  55 _cairo_array_init (cairo_array_t *array, int element_size)
  56 {
  57     array->size = 0;
  58     array->num_elements = 0;
  59     array->element_size = element_size;
  60     array->elements = NULL;
  61
  62     array->is_snapshot = FALSE;
  63 }
  64
  65 /**
  66  * _cairo_array_init_snapshot:
  67  * @array: A #cairo_array_t to be initialized as a snapshot
  68  * @other: The #cairo_array_t from which to create the snapshot
  69  *
  70  * Initialize @array as an immutable copy of @other. It is an error to
  71  * call an array-modifying function (other than _cairo_array_fini) on
  72  * @array after calling this function.
  73  **/
  74 void
  75 _cairo_array_init_snapshot (cairo_array_t       *array,
  76                             const cairo_array_t *other)
  77 {
  78     array->size = other->size;
  79     array->num_elements = other->num_elements;
  80     array->element_size = other->element_size;
  81     array->elements = other->elements;
  82
  83     array->is_snapshot = TRUE;
  84 }
  85
  86 /**
  87  * _cairo_array_fini:
  88  * @array: A #cairo_array_t
  89  *
  90  * Free all resources associated with @array. After this call, @array
  91  * should not be used again without a subsequent call to
  92  * _cairo_array_init() again first.
  93  **/
  94 void
  95 _cairo_array_fini (cairo_array_t *array)
  96 {
  97     if (array->is_snapshot)
  98         return;
  99
 100     if (array->elements) {
 101         free (* array->elements);
 102         free (array->elements);
 103     }
 104 }
 105
 106 /**
 107  * _cairo_array_grow_by:
 108  * @array: a #cairo_array_t
 109  *
 110  * Increase the size of @array (if needed) so that there are at least
 111  * @additional free spaces in the array. The actual size of the array
 112  * is always increased by doubling as many times as necessary.
 113  **/
 114 cairo_status_t
 115 _cairo_array_grow_by (cairo_array_t *array, unsigned int additional)
 116 {
 117     char *new_elements;
 118     unsigned int old_size = array->size;
 119     unsigned int required_size = array->num_elements + additional;
 120     unsigned int new_size;
 121
 122     assert (! array->is_snapshot);
 123
 124     /* check for integer overflow */
 125     if (required_size > INT_MAX || required_size < array->num_elements)
 126         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 127
 128     if (CAIRO_INJECT_FAULT ())
 129         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 130
 131     if (required_size <= old_size)
 132         return CAIRO_STATUS_SUCCESS;
 133
 134     if (old_size == 0)
 135         new_size = 1;
 136     else
 137         new_size = old_size * 2;
 138
 139     while (new_size < required_size)
 140         new_size = new_size * 2;
 141
 142     if (array->elements == NULL) {
 143         array->elements = malloc (sizeof (char *));
 144         if (unlikely (array->elements == NULL))
 145             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 146
 147         *array->elements = NULL;
 148     }
 149
 150     array->size = new_size;
 151     new_elements = _cairo_realloc_ab (*array->elements,
 152                                       array->size, array->element_size);
 153
 154     if (unlikely (new_elements == NULL)) {
 155         array->size = old_size;
 156         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 157     }
 158
 159     *array->elements = new_elements;
 160
 161     return CAIRO_STATUS_SUCCESS;
 162 }
 163
 164 /**
 165  * _cairo_array_truncate:
 166  * @array: a #cairo_array_t
 167  *
 168  * Truncate size of the array to @num_elements if less than the
 169  * current size. No memory is actually freed. The stored objects
 170  * beyond @num_elements are simply "forgotten".
 171  **/
 172 void
 173 _cairo_array_truncate (cairo_array_t *array, unsigned int num_elements)
 174 {
 175     assert (! array->is_snapshot);
 176
 177     if (num_elements < array->num_elements)
 178         array->num_elements = num_elements;
 179 }
 180
 181 /**
 182  * _cairo_array_index:
 183  * @array: a #cairo_array_t
 184  * Returns: A pointer to the object stored at @index.
 185  *
 186  * If the resulting value is assigned to a pointer to an object of the same
 187  * element_size as initially passed to _cairo_array_init() then that
 188  * pointer may be used for further direct indexing with []. For
 189  * example:
 190  *
 191  * <informalexample><programlisting>
 192  *      cairo_array_t array;
 193  *      double *values;
 194  *
 195  *      _cairo_array_init (&array, sizeof(double));
 196  *      ... calls to _cairo_array_append() here ...
 197  *
 198  *      values = _cairo_array_index (&array, 0);
 199  *      for (i = 0; i < _cairo_array_num_elements (&array); i++)
 200  *          ... use values[i] here ...
 201  * </programlisting></informalexample>
 202  **/
 203 void *
 204 _cairo_array_index (cairo_array_t *array, unsigned int index)
 205 {
 206     /* We allow an index of 0 for the no-elements case.
 207      * This makes for cleaner calling code which will often look like:
 208      *
 209      *    elements = _cairo_array_index (array, num_elements);
 210      *    for (i=0; i < num_elements; i++) {
 211      *        ... use elements[i] here ...
 212      *    }
 213      *
 214      * which in the num_elements==0 case gets the NULL pointer here,
 215      * but never dereferences it.
 216      */
 217     if (index == 0 && array->num_elements == 0)
 218         return NULL;
 219
 220     assert (index < array->num_elements);
 221
 222     return (void *) &(*array->elements)[index * array->element_size];
 223 }
 224
 225 /**
 226  * _cairo_array_copy_element:
 227  * @array: a #cairo_array_t
 228  *
 229  * Copy a single element out of the array from index @index into the
 230  * location pointed to by @dst.
 231  **/
 232 void
 233 _cairo_array_copy_element (cairo_array_t *array, int index, void *dst)
 234 {
 235     memcpy (dst, _cairo_array_index (array, index), array->element_size);
 236 }
 237
 238 /**
 239  * _cairo_array_append:
 240  * @array: a #cairo_array_t
 241  *
 242  * Append a single item onto the array by growing the array by at
 243  * least one element, then copying element_size bytes from @element
 244  * into the array. The address of the resulting object within the
 245  * array can be determined with:
 246  *
 247  * _cairo_array_index (array, _cairo_array_num_elements (array) - 1);
 248  *
 249  * Return value: %CAIRO_STATUS_SUCCESS if successful or
 250  * %CAIRO_STATUS_NO_MEMORY if insufficient memory is available for the
 251  * operation.
 252  **/
 253 cairo_status_t
 254 _cairo_array_append (cairo_array_t      *array,
 255                      const void         *element)
 256 {
 257     assert (! array->is_snapshot);
 258
 259     return _cairo_array_append_multiple (array, element, 1);
 260 }
 261
 262 /**
 263  * _cairo_array_append:
 264  * @array: a #cairo_array_t
 265  *
 266  * Append one or more items onto the array by growing the array by
 267  * @num_elements, then copying @num_elements * element_size bytes from
 268  * @elements into the array.
 269  *
 270  * Return value: %CAIRO_STATUS_SUCCESS if successful or
 271  * %CAIRO_STATUS_NO_MEMORY if insufficient memory is available for the
 272  * operation.
 273  **/
 274 cairo_status_t
 275 _cairo_array_append_multiple (cairo_array_t     *array,
 276                               const void        *elements,
 277                               int                num_elements)
 278 {
 279     cairo_status_t status;
 280     void *dest;
 281
 282     assert (! array->is_snapshot);
 283
 284     status = _cairo_array_allocate (array, num_elements, &dest);
 285     if (unlikely (status))
 286         return status;
 287
 288     memcpy (dest, elements, num_elements * array->element_size);
 289
 290     return CAIRO_STATUS_SUCCESS;
 291 }
 292
 293 /**
 294  * _cairo_array_allocate:
 295  * @array: a #cairo_array_t
 296  *
 297  * Allocate space at the end of the array for @num_elements additional
 298  * elements, providing the address of the new memory chunk in
 299  * @elements. This memory will be unitialized, but will be accounted
 300  * for in the return value of _cairo_array_num_elements().
 301  *
 302  * Return value: %CAIRO_STATUS_SUCCESS if successful or
 303  * %CAIRO_STATUS_NO_MEMORY if insufficient memory is available for the
 304  * operation.
 305  **/
 306 cairo_status_t
 307 _cairo_array_allocate (cairo_array_t     *array,
 308                        unsigned int       num_elements,
 309                        void             **elements)
 310 {
 311     cairo_status_t status;
 312
 313     assert (! array->is_snapshot);
 314
 315     status = _cairo_array_grow_by (array, num_elements);
 316     if (unlikely (status))
 317         return status;
 318
 319     assert (array->num_elements + num_elements <= array->size);
 320
 321     *elements = &(*array->elements)[array->num_elements * array->element_size];
 322
 323     array->num_elements += num_elements;
 324
 325     return CAIRO_STATUS_SUCCESS;
 326 }
 327
 328 /**
 329  * _cairo_array_num_elements:
 330  * @array: a #cairo_array_t
 331  * Returns: The number of elements stored in @array.
 332  *
 333  * This space was left intentionally blank, but gtk-doc filled it.
 334  **/
 335 int
 336 _cairo_array_num_elements (cairo_array_t *array)
 337 {
 338     return array->num_elements;
 339 }
 340
 341 /**
 342  * _cairo_array_size:
 343  * @array: a #cairo_array_t
 344  * Returns: The number of elements for which there is currently space
 345  * allocated in @array.
 346  *
 347  * This space was left intentionally blank, but gtk-doc filled it.
 348  **/
 349 int
 350 _cairo_array_size (cairo_array_t *array)
 351 {
 352     return array->size;
 353 }
 354
 355 /**
 356  * _cairo_user_data_array_init:
 357  * @array: a #cairo_user_data_array_t
 358  *
 359  * Initializes a #cairo_user_data_array_t structure for future
 360  * use. After initialization, the array has no keys. Call
 361  * _cairo_user_data_array_fini() to free any allocated memory
 362  * when done using the array.
 363  **/
 364 void
 365 _cairo_user_data_array_init (cairo_user_data_array_t *array)
 366 {
 367     _cairo_array_init (array, sizeof (cairo_user_data_slot_t));
 368 }
 369
 370 /**
 371  * _cairo_user_data_array_fini:
 372  * @array: a #cairo_user_data_array_t
 373  *
 374  * Destroys all current keys in the user data array and deallocates
 375  * any memory allocated for the array itself.
 376  **/
 377 void
 378 _cairo_user_data_array_fini (cairo_user_data_array_t *array)
 379 {
 380     unsigned int num_slots;
 381
 382     num_slots = array->num_elements;
 383     if (num_slots) {
 384         cairo_user_data_slot_t *slots;
 385
 386         slots = _cairo_array_index (array, 0);
 387         do {
 388             if (slots->user_data != NULL && slots->destroy != NULL)
 389                 slots->destroy (slots->user_data);
 390             slots++;
 391         } while (--num_slots);
 392     }
 393
 394     _cairo_array_fini (array);
 395 }
 396
 397 /**
 398  * _cairo_user_data_array_get_data:
 399  * @array: a #cairo_user_data_array_t
 400  * @key: the address of the #cairo_user_data_key_t the user data was
 401  * attached to
 402  *
 403  * Returns user data previously attached using the specified
 404  * key.  If no user data has been attached with the given key this
 405  * function returns %NULL.
 406  *
 407  * Return value: the user data previously attached or %NULL.
 408  **/
 409 void *
 410 _cairo_user_data_array_get_data (cairo_user_data_array_t     *array,
 411                                  const cairo_user_data_key_t *key)
 412 {
 413     int i, num_slots;
 414     cairo_user_data_slot_t *slots;
 415
 416     /* We allow this to support degenerate objects such as cairo_surface_nil. */
 417     if (array == NULL)
 418         return NULL;
 419
 420     num_slots = array->num_elements;
 421     slots = _cairo_array_index (array, 0);
 422     for (i = 0; i < num_slots; i++) {
 423         if (slots[i].key == key)
 424             return slots[i].user_data;
 425     }
 426
 427     return NULL;
 428 }
 429
 430 /**
 431  * _cairo_user_data_array_set_data:
 432  * @array: a #cairo_user_data_array_t
 433  * @key: the address of a #cairo_user_data_key_t to attach the user data to
 434  * @user_data: the user data to attach
 435  * @destroy: a #cairo_destroy_func_t which will be called when the
 436  * user data array is destroyed or when new user data is attached using the
 437  * same key.
 438  *
 439  * Attaches user data to a user data array.  To remove user data,
 440  * call this function with the key that was used to set it and %NULL
 441  * for @data.
 442  *
 443  * Return value: %CAIRO_STATUS_SUCCESS or %CAIRO_STATUS_NO_MEMORY if a
 444  * slot could not be allocated for the user data.
 445  **/
 446 cairo_status_t
 447 _cairo_user_data_array_set_data (cairo_user_data_array_t     *array,
 448                                  const cairo_user_data_key_t *key,
 449                                  void                        *user_data,
 450                                  cairo_destroy_func_t         destroy)
 451 {
 452     cairo_status_t status;
 453     int i, num_slots;
 454     cairo_user_data_slot_t *slots, *slot, new_slot;
 455
 456     if (user_data) {
 457         new_slot.key = key;
 458         new_slot.user_data = user_data;
 459         new_slot.destroy = destroy;
 460     } else {
 461         new_slot.key = NULL;
 462         new_slot.user_data = NULL;
 463         new_slot.destroy = NULL;
 464     }
 465
 466     slot = NULL;
 467     num_slots = array->num_elements;
 468     slots = _cairo_array_index (array, 0);
 469     for (i = 0; i < num_slots; i++) {
 470         if (slots[i].key == key) {
 471             slot = &slots[i];
 472             if (slot->destroy && slot->user_data)
 473                 slot->destroy (slot->user_data);
 474             break;
 475         }
 476         if (user_data && slots[i].user_data == NULL) {
 477             slot = &slots[i];   /* Have to keep searching for an exact match */
 478         }
 479     }
 480
 481     if (slot) {
 482         *slot = new_slot;
 483         return CAIRO_STATUS_SUCCESS;
 484     }
 485
 486     status = _cairo_array_append (array, &new_slot);
 487     if (unlikely (status))
 488         return status;
 489
 490     return CAIRO_STATUS_SUCCESS;
 491 }
 492
 493 cairo_status_t
 494 _cairo_user_data_array_copy (cairo_user_data_array_t    *dst,
 495                              cairo_user_data_array_t    *src)
 496 {
 497     /* discard any existing user-data */
 498     if (dst->num_elements != 0) {
 499         _cairo_user_data_array_fini (dst);
 500         _cairo_user_data_array_init (dst);
 501     }
 502
 503     if (src->num_elements == 0)
 504         return CAIRO_STATUS_SUCCESS;
 505
 506     return _cairo_array_append_multiple (dst,
 507                                          _cairo_array_index (src, 0),
 508                                          src->num_elements);
 509 }
 510
 511 void
 512 _cairo_user_data_array_foreach (cairo_user_data_array_t     *array,
 513                                 void (*func) (const void *key,
 514                                               void *elt,
 515                                               void *closure),
 516                                 void *closure)
 517 {
 518     cairo_user_data_slot_t *slots;
 519     int i, num_slots;
 520
 521     num_slots = array->num_elements;
 522     slots = _cairo_array_index (array, 0);
 523     for (i = 0; i < num_slots; i++) {
 524         if (slots[i].user_data != NULL)
 525             func (slots[i].key, slots[i].user_data, closure);
 526     }
 527 }