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