source/libs/cairo/cairo-src/src/cairo-array.c

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