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
_cairo_array_init(cairo_array_t * array,unsigned int element_size)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
_cairo_array_fini(cairo_array_t * array)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
_cairo_array_grow_by(cairo_array_t * array,unsigned int additional)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
_cairo_array_truncate(cairo_array_t * array,unsigned int num_elements)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 *
_cairo_array_index(cairo_array_t * array,unsigned int index)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 *
_cairo_array_index_const(const cairo_array_t * array,unsigned int index)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
_cairo_array_copy_element(const cairo_array_t * array,unsigned int index,void * dst)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
_cairo_array_append(cairo_array_t * array,const void * element)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
_cairo_array_append_multiple(cairo_array_t * array,const void * elements,unsigned int num_elements)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 uninitialized, 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
_cairo_array_allocate(cairo_array_t * array,unsigned int num_elements,void ** elements)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
_cairo_array_num_elements(const cairo_array_t * array)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
_cairo_array_size(const cairo_array_t * array)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
_cairo_user_data_array_init(cairo_user_data_array_t * array)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
_cairo_user_data_array_fini(cairo_user_data_array_t * array)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 *
_cairo_user_data_array_get_data(cairo_user_data_array_t * array,const cairo_user_data_key_t * key)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
_cairo_user_data_array_set_data(cairo_user_data_array_t * array,const cairo_user_data_key_t * key,void * user_data,cairo_destroy_func_t destroy)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
_cairo_user_data_array_copy(cairo_user_data_array_t * dst,const cairo_user_data_array_t * src)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 /* don't call _cairo_array_append_multiple if there's nothing to do,
509 * as it assumes at least 1 element is to be appended */
510 if (src->num_elements == 0)
511 return CAIRO_STATUS_SUCCESS;
512
513 return _cairo_array_append_multiple (dst,
514 _cairo_array_index_const (src, 0),
515 src->num_elements);
516 }
517
518 void
_cairo_user_data_array_foreach(cairo_user_data_array_t * array,void (* func)(const void * key,void * elt,void * closure),void * closure)519 _cairo_user_data_array_foreach (cairo_user_data_array_t *array,
520 void (*func) (const void *key,
521 void *elt,
522 void *closure),
523 void *closure)
524 {
525 cairo_user_data_slot_t *slots;
526 int i, num_slots;
527
528 num_slots = array->num_elements;
529 slots = _cairo_array_index (array, 0);
530 for (i = 0; i < num_slots; i++) {
531 if (slots[i].user_data != NULL)
532 func (slots[i].key, slots[i].user_data, closure);
533 }
534 }
535
536 void
_cairo_array_sort(const cairo_array_t * array,int (* compar)(const void *,const void *))537 _cairo_array_sort (const cairo_array_t *array, int (*compar)(const void *, const void *))
538 {
539 qsort (array->elements, array->num_elements, array->element_size, compar);
540 }
541