1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
4 * SPDX-License-Identifier: LGPL-2.1-or-later
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2.1 of the License, or (at your option) any later version.
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library; if not, see <http://www.gnu.org/licenses/>.
21 * Modified by the GLib Team and others 1997-2000. See the AUTHORS
22 * file for a list of people on the GLib Team. See the ChangeLog
23 * files for a list of changes. These files are distributed with
24 * GLib at ftp://ftp.gtk.org/pub/gtk/.
42 #include "gtestutils.h"
44 #include "gmessages.h"
46 #include "grefcount.h"
47 #include "gutilsprivate.h"
52 * @short_description: arrays of arbitrary elements which grow
53 * automatically as elements are added
55 * Arrays are similar to standard C arrays, except that they grow
56 * automatically as elements are added.
58 * Array elements can be of any size (though all elements of one array
59 * are the same size), and the array can be automatically cleared to
60 * '0's and zero-terminated.
62 * To create a new array use g_array_new().
64 * To add elements to an array with a cost of O(n) at worst, use
65 * g_array_append_val(), g_array_append_vals(), g_array_prepend_val(),
66 * g_array_prepend_vals(), g_array_insert_val() and g_array_insert_vals().
68 * To access an element of an array in O(1) (to read it or to write it),
69 * use g_array_index().
71 * To set the size of an array, use g_array_set_size().
73 * To free an array, use g_array_unref() or g_array_free().
75 * All the sort functions are internally calling a quick-sort (or similar)
76 * function with an average cost of O(n log(n)) and a worst case
79 * Here is an example that stores integers in a #GArray:
80 * |[<!-- language="C" -->
83 * // We create a new array to store gint values.
84 * // We don't want it zero-terminated or cleared to 0's.
85 * garray = g_array_new (FALSE, FALSE, sizeof (gint));
86 * for (i = 0; i < 10000; i++)
87 * g_array_append_val (garray, i);
88 * for (i = 0; i < 10000; i++)
89 * if (g_array_index (garray, gint, i) != i)
90 * g_print ("ERROR: got %d instead of %d\n",
91 * g_array_index (garray, gint, i), i);
92 * g_array_free (garray, TRUE);
96 #define MIN_ARRAY_SIZE 16
98 typedef struct _GRealArray GRealArray;
102 * @data: a pointer to the element data. The data may be moved as
103 * elements are added to the #GArray.
104 * @len: the number of elements in the #GArray not including the
105 * possible terminating zero element.
107 * Contains the public fields of a GArray.
115 guint zero_terminated : 1;
117 gatomicrefcount ref_count;
118 GDestroyNotify clear_func;
124 * @t: the type of the elements
125 * @i: the index of the element to return
127 * Returns the element of a #GArray at the given index. The return
128 * value is cast to the given type. This is the main way to read or write an
129 * element in a #GArray.
131 * Writing an element is typically done by reference, as in the following
132 * example. This example gets a pointer to an element in a #GArray, and then
133 * writes to a field in it:
134 * |[<!-- language="C" -->
135 * EDayViewEvent *event;
136 * // This gets a pointer to the 4th element in the array of
137 * // EDayViewEvent structs.
138 * event = &g_array_index (events, EDayViewEvent, 3);
139 * event->start_time = g_get_current_time ();
142 * This example reads from and writes to an array of integers:
143 * |[<!-- language="C" -->
144 * g_autoptr(GArray) int_array = g_array_new (FALSE, FALSE, sizeof (guint));
145 * for (guint i = 0; i < 10; i++)
146 * g_array_append_val (int_array, i);
148 * guint *my_int = &g_array_index (int_array, guint, 1);
149 * g_print ("Int at index 1 is %u; decrementing it\n", *my_int);
150 * *my_int = *my_int - 1;
153 * Returns: the element of the #GArray at the index given by @i
156 #define g_array_elt_len(array,i) ((gsize)(array)->elt_size * (i))
157 #define g_array_elt_pos(array,i) ((array)->data + g_array_elt_len((array),(i)))
158 #define g_array_elt_zero(array, pos, len) \
159 (memset (g_array_elt_pos ((array), pos), 0, g_array_elt_len ((array), len)))
160 #define g_array_zero_terminate(array) G_STMT_START{ \
161 if ((array)->zero_terminated) \
162 g_array_elt_zero ((array), (array)->len, 1); \
165 static void g_array_maybe_expand (GRealArray *array,
170 * @zero_terminated: %TRUE if the array should have an extra element at
171 * the end which is set to 0
172 * @clear_: %TRUE if #GArray elements should be automatically cleared
173 * to 0 when they are allocated
174 * @element_size: the size of each element in bytes
176 * Creates a new #GArray with a reference count of 1.
178 * Returns: the new #GArray
181 g_array_new (gboolean zero_terminated,
185 g_return_val_if_fail (elt_size > 0, NULL);
186 #if (UINT_WIDTH / 8) >= GLIB_SIZEOF_SIZE_T
187 g_return_val_if_fail (elt_size <= G_MAXSIZE / 2 - 1, NULL);
190 return g_array_sized_new (zero_terminated, clear, elt_size, 0);
196 * @len: (optional) (out): pointer to retrieve the number of
197 * elements of the original array
199 * Frees the data in the array and resets the size to zero, while
200 * the underlying array is preserved for use elsewhere and returned
203 * If the array was created with the @zero_terminate property
204 * set to %TRUE, the returned data is zero terminated too.
206 * If array elements contain dynamically-allocated memory,
207 * the array elements should also be freed by the caller.
209 * A short example of use:
210 * |[<!-- language="C" -->
214 * data = g_array_steal (some_array, &data_len);
218 * Returns: (transfer full): the element data, which should be
219 * freed using g_free().
224 g_array_steal (GArray *array,
230 g_return_val_if_fail (array != NULL, NULL);
232 rarray = (GRealArray *) array;
233 segment = (gpointer) rarray->data;
240 rarray->elt_capacity = 0;
246 * @zero_terminated: %TRUE if the array should have an extra element at
247 * the end with all bits cleared
248 * @clear_: %TRUE if all bits in the array should be cleared to 0 on
250 * @element_size: size of each element in the array
251 * @reserved_size: number of elements preallocated
253 * Creates a new #GArray with @reserved_size elements preallocated and
254 * a reference count of 1. This avoids frequent reallocation, if you
255 * are going to add many elements to the array. Note however that the
256 * size of the array is still 0.
258 * Returns: the new #GArray
261 g_array_sized_new (gboolean zero_terminated,
268 g_return_val_if_fail (elt_size > 0, NULL);
269 #if (UINT_WIDTH / 8) >= GLIB_SIZEOF_SIZE_T
270 g_return_val_if_fail (elt_size <= G_MAXSIZE / 2 - 1, NULL);
273 array = g_slice_new (GRealArray);
277 array->elt_capacity = 0;
278 array->zero_terminated = (zero_terminated ? 1 : 0);
279 array->clear = (clear ? 1 : 0);
280 array->elt_size = elt_size;
281 array->clear_func = NULL;
283 g_atomic_ref_count_init (&array->ref_count);
285 if (array->zero_terminated || reserved_size != 0)
287 g_array_maybe_expand (array, reserved_size);
288 g_array_zero_terminate(array);
291 return (GArray*) array;
295 * g_array_set_clear_func:
297 * @clear_func: a function to clear an element of @array
299 * Sets a function to clear an element of @array.
301 * The @clear_func will be called when an element in the array
302 * data segment is removed and when the array is freed and data
303 * segment is deallocated as well. @clear_func will be passed a
304 * pointer to the element to clear, rather than the element itself.
306 * Note that in contrast with other uses of #GDestroyNotify
307 * functions, @clear_func is expected to clear the contents of
308 * the array element it is given, but not free the element itself.
310 * |[<!-- language="C" -->
318 * array_element_clear (ArrayElement *element)
320 * g_clear_pointer (&element->str, g_free);
321 * g_clear_object (&element->obj);
325 * GArray *garray = g_array_new (FALSE, FALSE, sizeof (ArrayElement));
326 * g_array_set_clear_func (garray, (GDestroyNotify) array_element_clear);
327 * // assign data to the structure
328 * g_array_free (garray, TRUE);
334 g_array_set_clear_func (GArray *array,
335 GDestroyNotify clear_func)
337 GRealArray *rarray = (GRealArray *) array;
339 g_return_if_fail (array != NULL);
341 rarray->clear_func = clear_func;
348 * Atomically increments the reference count of @array by one.
349 * This function is thread-safe and may be called from any thread.
351 * Returns: The passed in #GArray
356 g_array_ref (GArray *array)
358 GRealArray *rarray = (GRealArray*) array;
359 g_return_val_if_fail (array, NULL);
361 g_atomic_ref_count_inc (&rarray->ref_count);
368 FREE_SEGMENT = 1 << 0,
369 PRESERVE_WRAPPER = 1 << 1
372 static gchar *array_free (GRealArray *, ArrayFreeFlags);
378 * Atomically decrements the reference count of @array by one. If the
379 * reference count drops to 0, all memory allocated by the array is
380 * released. This function is thread-safe and may be called from any
386 g_array_unref (GArray *array)
388 GRealArray *rarray = (GRealArray*) array;
389 g_return_if_fail (array);
391 if (g_atomic_ref_count_dec (&rarray->ref_count))
392 array_free (rarray, FREE_SEGMENT);
396 * g_array_get_element_size:
399 * Gets the size of the elements in @array.
401 * Returns: Size of each element, in bytes
406 g_array_get_element_size (GArray *array)
408 GRealArray *rarray = (GRealArray*) array;
410 g_return_val_if_fail (array, 0);
412 return rarray->elt_size;
418 * @free_segment: if %TRUE the actual element data is freed as well
420 * Frees the memory allocated for the #GArray. If @free_segment is
421 * %TRUE it frees the memory block holding the elements as well. Pass
422 * %FALSE if you want to free the #GArray wrapper but preserve the
423 * underlying array for use elsewhere. If the reference count of
424 * @array is greater than one, the #GArray wrapper is preserved but
425 * the size of @array will be set to zero.
427 * If array contents point to dynamically-allocated memory, they should
428 * be freed separately if @free_seg is %TRUE and no @clear_func
429 * function has been set for @array.
431 * This function is not thread-safe. If using a #GArray from multiple
432 * threads, use only the atomic g_array_ref() and g_array_unref()
435 * Returns: the element data if @free_segment is %FALSE, otherwise
436 * %NULL. The element data should be freed using g_free().
439 g_array_free (GArray *farray,
440 gboolean free_segment)
442 GRealArray *array = (GRealArray*) farray;
443 ArrayFreeFlags flags;
445 g_return_val_if_fail (array, NULL);
447 flags = (free_segment ? FREE_SEGMENT : 0);
449 /* if others are holding a reference, preserve the wrapper but do free/return the data */
450 if (!g_atomic_ref_count_dec (&array->ref_count))
451 flags |= PRESERVE_WRAPPER;
453 return array_free (array, flags);
457 array_free (GRealArray *array,
458 ArrayFreeFlags flags)
462 if (flags & FREE_SEGMENT)
464 if (array->clear_func != NULL)
468 for (i = 0; i < array->len; i++)
469 array->clear_func (g_array_elt_pos (array, i));
472 g_free (array->data);
476 segment = (gchar*) array->data;
478 if (flags & PRESERVE_WRAPPER)
482 array->elt_capacity = 0;
486 g_slice_free1 (sizeof (GRealArray), array);
493 * g_array_append_vals:
495 * @data: (not nullable): a pointer to the elements to append to the end of the array
496 * @len: the number of elements to append
498 * Adds @len elements onto the end of the array.
500 * Returns: the #GArray
503 * g_array_append_val:
505 * @v: the value to append to the #GArray
507 * Adds the value on to the end of the array. The array will grow in
508 * size automatically if necessary.
510 * g_array_append_val() is a macro which uses a reference to the value
511 * parameter @v. This means that you cannot use it with literal values
512 * such as "27". You must use variables.
514 * Returns: the #GArray
517 g_array_append_vals (GArray *farray,
521 GRealArray *array = (GRealArray*) farray;
523 g_return_val_if_fail (array, NULL);
528 g_array_maybe_expand (array, len);
530 memcpy (g_array_elt_pos (array, array->len), data,
531 g_array_elt_len (array, len));
535 g_array_zero_terminate (array);
541 * g_array_prepend_vals:
543 * @data: (nullable): a pointer to the elements to prepend to the start of the array
544 * @len: the number of elements to prepend, which may be zero
546 * Adds @len elements onto the start of the array.
548 * @data may be %NULL if (and only if) @len is zero. If @len is zero, this
549 * function is a no-op.
551 * This operation is slower than g_array_append_vals() since the
552 * existing elements in the array have to be moved to make space for
555 * Returns: the #GArray
558 * g_array_prepend_val:
560 * @v: the value to prepend to the #GArray
562 * Adds the value on to the start of the array. The array will grow in
563 * size automatically if necessary.
565 * This operation is slower than g_array_append_val() since the
566 * existing elements in the array have to be moved to make space for
569 * g_array_prepend_val() is a macro which uses a reference to the value
570 * parameter @v. This means that you cannot use it with literal values
571 * such as "27". You must use variables.
573 * Returns: the #GArray
576 g_array_prepend_vals (GArray *farray,
580 GRealArray *array = (GRealArray*) farray;
582 g_return_val_if_fail (array, NULL);
587 g_array_maybe_expand (array, len);
589 memmove (g_array_elt_pos (array, len), g_array_elt_pos (array, 0),
590 g_array_elt_len (array, array->len));
592 memcpy (g_array_elt_pos (array, 0), data, g_array_elt_len (array, len));
596 g_array_zero_terminate (array);
602 * g_array_insert_vals:
604 * @index_: the index to place the elements at
605 * @data: (nullable): a pointer to the elements to insert
606 * @len: the number of elements to insert
608 * Inserts @len elements into a #GArray at the given index.
610 * If @index_ is greater than the array’s current length, the array is expanded.
611 * The elements between the old end of the array and the newly inserted elements
612 * will be initialised to zero if the array was configured to clear elements;
613 * otherwise their values will be undefined.
615 * If @index_ is less than the array’s current length, new entries will be
616 * inserted into the array, and the existing entries above @index_ will be moved
619 * @data may be %NULL if (and only if) @len is zero. If @len is zero, this
620 * function is a no-op.
622 * Returns: the #GArray
625 * g_array_insert_val:
627 * @i: the index to place the element at
628 * @v: the value to insert into the array
630 * Inserts an element into an array at the given index.
632 * g_array_insert_val() is a macro which uses a reference to the value
633 * parameter @v. This means that you cannot use it with literal values
634 * such as "27". You must use variables.
636 * Returns: the #GArray
639 g_array_insert_vals (GArray *farray,
644 GRealArray *array = (GRealArray*) farray;
646 g_return_val_if_fail (array, NULL);
651 /* Is the index off the end of the array, and hence do we need to over-allocate
652 * and clear some elements? */
653 if (index_ >= array->len)
655 g_array_maybe_expand (array, index_ - array->len + len);
656 return g_array_append_vals (g_array_set_size (farray, index_), data, len);
659 g_array_maybe_expand (array, len);
661 memmove (g_array_elt_pos (array, len + index_),
662 g_array_elt_pos (array, index_),
663 g_array_elt_len (array, array->len - index_));
665 memcpy (g_array_elt_pos (array, index_), data, g_array_elt_len (array, len));
669 g_array_zero_terminate (array);
677 * @length: the new size of the #GArray
679 * Sets the size of the array, expanding it if necessary. If the array
680 * was created with @clear_ set to %TRUE, the new elements are set to 0.
682 * Returns: the #GArray
685 g_array_set_size (GArray *farray,
688 GRealArray *array = (GRealArray*) farray;
690 g_return_val_if_fail (array, NULL);
692 if (length > array->len)
694 g_array_maybe_expand (array, length - array->len);
697 g_array_elt_zero (array, array->len, length - array->len);
699 else if (length < array->len)
700 g_array_remove_range (farray, length, array->len - length);
704 g_array_zero_terminate (array);
710 * g_array_remove_index:
712 * @index_: the index of the element to remove
714 * Removes the element at the given index from a #GArray. The following
715 * elements are moved down one place.
717 * Returns: the #GArray
720 g_array_remove_index (GArray *farray,
723 GRealArray* array = (GRealArray*) farray;
725 g_return_val_if_fail (array, NULL);
727 g_return_val_if_fail (index_ < array->len, NULL);
729 if (array->clear_func != NULL)
730 array->clear_func (g_array_elt_pos (array, index_));
732 if (index_ != array->len - 1)
733 memmove (g_array_elt_pos (array, index_),
734 g_array_elt_pos (array, index_ + 1),
735 g_array_elt_len (array, array->len - index_ - 1));
739 if (G_UNLIKELY (g_mem_gc_friendly))
740 g_array_elt_zero (array, array->len, 1);
742 g_array_zero_terminate (array);
748 * g_array_remove_index_fast:
750 * @index_: the index of the element to remove
752 * Removes the element at the given index from a #GArray. The last
753 * element in the array is used to fill in the space, so this function
754 * does not preserve the order of the #GArray. But it is faster than
755 * g_array_remove_index().
757 * Returns: the #GArray
760 g_array_remove_index_fast (GArray *farray,
763 GRealArray* array = (GRealArray*) farray;
765 g_return_val_if_fail (array, NULL);
767 g_return_val_if_fail (index_ < array->len, NULL);
769 if (array->clear_func != NULL)
770 array->clear_func (g_array_elt_pos (array, index_));
772 if (index_ != array->len - 1)
773 memcpy (g_array_elt_pos (array, index_),
774 g_array_elt_pos (array, array->len - 1),
775 g_array_elt_len (array, 1));
779 if (G_UNLIKELY (g_mem_gc_friendly))
780 g_array_elt_zero (array, array->len, 1);
782 g_array_zero_terminate (array);
788 * g_array_remove_range:
790 * @index_: the index of the first element to remove
791 * @length: the number of elements to remove
793 * Removes the given number of elements starting at the given index
794 * from a #GArray. The following elements are moved to close the gap.
796 * Returns: the #GArray
801 g_array_remove_range (GArray *farray,
805 GRealArray *array = (GRealArray*) farray;
807 g_return_val_if_fail (array, NULL);
808 g_return_val_if_fail (index_ <= array->len, NULL);
809 g_return_val_if_fail (index_ + length <= array->len, NULL);
811 if (array->clear_func != NULL)
815 for (i = 0; i < length; i++)
816 array->clear_func (g_array_elt_pos (array, index_ + i));
819 if (index_ + length != array->len)
820 memmove (g_array_elt_pos (array, index_),
821 g_array_elt_pos (array, index_ + length),
822 (array->len - (index_ + length)) * array->elt_size);
824 array->len -= length;
825 if (G_UNLIKELY (g_mem_gc_friendly))
826 g_array_elt_zero (array, array->len, length);
828 g_array_zero_terminate (array);
836 * @compare_func: comparison function
838 * Sorts a #GArray using @compare_func which should be a qsort()-style
839 * comparison function (returns less than zero for first arg is less
840 * than second arg, zero for equal, greater zero if first arg is
841 * greater than second arg).
843 * This is guaranteed to be a stable sort since version 2.32.
846 g_array_sort (GArray *farray,
847 GCompareFunc compare_func)
849 GRealArray *array = (GRealArray*) farray;
851 g_return_if_fail (array != NULL);
853 /* Don't use qsort as we want a guaranteed stable sort */
855 g_qsort_with_data (array->data,
858 (GCompareDataFunc)compare_func,
863 * g_array_sort_with_data:
865 * @compare_func: comparison function
866 * @user_data: data to pass to @compare_func
868 * Like g_array_sort(), but the comparison function receives an extra
869 * user data argument.
871 * This is guaranteed to be a stable sort since version 2.32.
873 * There used to be a comment here about making the sort stable by
874 * using the addresses of the elements in the comparison function.
875 * This did not actually work, so any such code should be removed.
878 g_array_sort_with_data (GArray *farray,
879 GCompareDataFunc compare_func,
882 GRealArray *array = (GRealArray*) farray;
884 g_return_if_fail (array != NULL);
887 g_qsort_with_data (array->data,
895 * g_array_binary_search:
897 * @target: a pointer to the item to look up.
898 * @compare_func: A #GCompareFunc used to locate @target.
899 * @out_match_index: (optional) (out): return location
900 * for the index of the element, if found.
902 * Checks whether @target exists in @array by performing a binary
903 * search based on the given comparison function @compare_func which
904 * get pointers to items as arguments. If the element is found, %TRUE
905 * is returned and the element’s index is returned in @out_match_index
906 * (if non-%NULL). Otherwise, %FALSE is returned and @out_match_index
907 * is undefined. If @target exists multiple times in @array, the index
908 * of the first instance is returned. This search is using a binary
909 * search, so the @array must absolutely be sorted to return a correct
910 * result (if not, the function may produce false-negative).
912 * This example defines a comparison function and search an element in a #GArray:
913 * |[<!-- language="C" -->
915 * cmpint (gconstpointer a, gconstpointer b)
917 * const gint *_a = a;
918 * const gint *_b = b;
924 * guint matched_index;
925 * gboolean result = g_array_binary_search (garray, &i, cmpint, &matched_index);
929 * Returns: %TRUE if @target is one of the elements of @array, %FALSE otherwise.
934 g_array_binary_search (GArray *array,
935 gconstpointer target,
936 GCompareFunc compare_func,
937 guint *out_match_index)
939 gboolean result = FALSE;
940 GRealArray *_array = (GRealArray *) array;
941 guint left, middle = 0, right;
944 g_return_val_if_fail (_array != NULL, FALSE);
945 g_return_val_if_fail (compare_func != NULL, FALSE);
947 if (G_LIKELY(_array->len))
950 right = _array->len - 1;
952 while (left <= right)
954 middle = left + (right - left) / 2;
956 val = compare_func (_array->data + (_array->elt_size * middle), target);
964 else if (/* val > 0 && */ middle > 0)
967 break; /* element not found */
971 if (result && out_match_index != NULL)
972 *out_match_index = middle;
978 g_array_maybe_expand (GRealArray *array,
981 guint max_len, want_len;
983 /* The maximum array length is derived from following constraints:
984 * - The number of bytes must fit into a gsize / 2.
985 * - The number of elements must fit into guint.
986 * - zero terminated arrays must leave space for the terminating element
988 max_len = MIN (G_MAXSIZE / 2 / array->elt_size, G_MAXUINT) - array->zero_terminated;
990 /* Detect potential overflow */
991 if G_UNLIKELY ((max_len - array->len) < len)
992 g_error ("adding %u to array would overflow", len);
994 want_len = array->len + len + array->zero_terminated;
995 if (want_len > array->elt_capacity)
997 gsize want_alloc = g_nearest_pow (g_array_elt_len (array, want_len));
998 want_alloc = MAX (want_alloc, MIN_ARRAY_SIZE);
1000 array->data = g_realloc (array->data, want_alloc);
1002 if (G_UNLIKELY (g_mem_gc_friendly))
1003 memset (g_array_elt_pos (array, array->elt_capacity), 0,
1004 g_array_elt_len (array, want_len - array->elt_capacity));
1006 array->elt_capacity = MIN (want_alloc / array->elt_size, G_MAXUINT);
1011 * SECTION:arrays_pointer
1012 * @title: Pointer Arrays
1013 * @short_description: arrays of pointers to any type of data, which
1014 * grow automatically as new elements are added
1016 * Pointer Arrays are similar to Arrays but are used only for storing
1019 * If you remove elements from the array, elements at the end of the
1020 * array are moved into the space previously occupied by the removed
1021 * element. This means that you should not rely on the index of particular
1022 * elements remaining the same. You should also be careful when deleting
1023 * elements while iterating over the array.
1025 * To create a pointer array, use g_ptr_array_new().
1027 * To add elements to a pointer array, use g_ptr_array_add().
1029 * To remove elements from a pointer array, use g_ptr_array_remove(),
1030 * g_ptr_array_remove_index() or g_ptr_array_remove_index_fast().
1032 * To access an element of a pointer array, use g_ptr_array_index().
1034 * To set the size of a pointer array, use g_ptr_array_set_size().
1036 * To free a pointer array, use g_ptr_array_free().
1038 * An example using a #GPtrArray:
1039 * |[<!-- language="C" -->
1041 * gchar *string1 = "one";
1042 * gchar *string2 = "two";
1043 * gchar *string3 = "three";
1045 * array = g_ptr_array_new ();
1046 * g_ptr_array_add (array, (gpointer) string1);
1047 * g_ptr_array_add (array, (gpointer) string2);
1048 * g_ptr_array_add (array, (gpointer) string3);
1050 * if (g_ptr_array_index (array, 0) != (gpointer) string1)
1051 * g_print ("ERROR: got %p instead of %p\n",
1052 * g_ptr_array_index (array, 0), string1);
1054 * g_ptr_array_free (array, TRUE);
1058 typedef struct _GRealPtrArray GRealPtrArray;
1062 * @pdata: points to the array of pointers, which may be moved when the
1064 * @len: number of pointers in the array
1066 * Contains the public fields of a pointer array.
1068 struct _GRealPtrArray
1073 gatomicrefcount ref_count;
1074 guint8 null_terminated; /* always either 0 or 1, so it can be added to array lengths */
1075 GDestroyNotify element_free_func;
1079 * g_ptr_array_index:
1080 * @array: a #GPtrArray
1081 * @index_: the index of the pointer to return
1083 * Returns the pointer at the given index of the pointer array.
1085 * This does not perform bounds checking on the given @index_,
1086 * so you are responsible for checking it against the array length.
1088 * Returns: the pointer at the given index
1091 static void g_ptr_array_maybe_expand (GRealPtrArray *array,
1095 ptr_array_maybe_null_terminate (GRealPtrArray *rarray)
1097 if (G_UNLIKELY (rarray->null_terminated))
1098 rarray->pdata[rarray->len] = NULL;
1102 ptr_array_new (guint reserved_size,
1103 GDestroyNotify element_free_func,
1104 gboolean null_terminated)
1106 GRealPtrArray *array;
1108 array = g_slice_new (GRealPtrArray);
1110 array->pdata = NULL;
1113 array->null_terminated = null_terminated ? 1 : 0;
1114 array->element_free_func = element_free_func;
1116 g_atomic_ref_count_init (&array->ref_count);
1118 if (reserved_size != 0)
1120 if (G_LIKELY (reserved_size < G_MAXUINT) &&
1123 g_ptr_array_maybe_expand (array, reserved_size);
1124 if (null_terminated)
1126 /* don't use ptr_array_maybe_null_terminate(). It helps the compiler
1127 * to see when @null_terminated is false and thereby inline
1128 * ptr_array_new() and possibly remove the code entirely. */
1129 array->pdata[0] = NULL;
1133 return (GPtrArray *) array;
1139 * Creates a new #GPtrArray with a reference count of 1.
1141 * Returns: the new #GPtrArray
1144 g_ptr_array_new (void)
1146 return ptr_array_new (0, NULL, FALSE);
1150 * g_ptr_array_steal:
1151 * @array: a #GPtrArray.
1152 * @len: (optional) (out): pointer to retrieve the number of
1153 * elements of the original array
1155 * Frees the data in the array and resets the size to zero, while
1156 * the underlying array is preserved for use elsewhere and returned
1159 * Note that if the array is %NULL terminated this may still return
1160 * %NULL if the length of the array was zero and pdata was not yet
1163 * Even if set, the #GDestroyNotify function will never be called
1164 * on the current contents of the array and the caller is
1165 * responsible for freeing the array elements.
1167 * An example of use:
1168 * |[<!-- language="C" -->
1169 * g_autoptr(GPtrArray) chunk_buffer = g_ptr_array_new_with_free_func (g_bytes_unref);
1171 * // Some part of your application appends a number of chunks to the pointer array.
1172 * g_ptr_array_add (chunk_buffer, g_bytes_new_static ("hello", 5));
1173 * g_ptr_array_add (chunk_buffer, g_bytes_new_static ("world", 5));
1177 * // Periodically, the chunks need to be sent as an array-and-length to some
1178 * // other part of the program.
1182 * chunks = g_ptr_array_steal (chunk_buffer, &n_chunks);
1183 * for (gsize i = 0; i < n_chunks; i++)
1185 * // Do something with each chunk here, and then free them, since
1186 * // g_ptr_array_steal() transfers ownership of all the elements and the
1187 * // array to the caller.
1190 * g_bytes_unref (chunks[i]);
1195 * // After calling g_ptr_array_steal(), the pointer array can be reused for the
1196 * // next set of chunks.
1197 * g_assert (chunk_buffer->len == 0);
1200 * Returns: (transfer full) (nullable): the element data, which should be
1201 * freed using g_free(). This may be %NULL if the array doesn’t have any
1202 * elements (i.e. if `*len` is zero).
1207 g_ptr_array_steal (GPtrArray *array,
1210 GRealPtrArray *rarray;
1213 g_return_val_if_fail (array != NULL, NULL);
1215 rarray = (GRealPtrArray *) array;
1216 segment = (gpointer *) rarray->pdata;
1221 rarray->pdata = NULL;
1229 * @array: #GPtrArray to duplicate
1230 * @func: (nullable): a copy function used to copy every element in the array
1231 * @user_data: user data passed to the copy function @func, or %NULL
1233 * Makes a full (deep) copy of a #GPtrArray.
1235 * @func, as a #GCopyFunc, takes two arguments, the data to be copied
1236 * and a @user_data pointer. On common processor architectures, it's safe to
1237 * pass %NULL as @user_data if the copy function takes only one argument. You
1238 * may get compiler warnings from this though if compiling with GCC’s
1239 * `-Wcast-function-type` warning.
1241 * If @func is %NULL, then only the pointers (and not what they are
1242 * pointing to) are copied to the new #GPtrArray.
1244 * The copy of @array will have the same #GDestroyNotify for its elements as
1245 * @array. The copy will also be %NULL terminated if (and only if) the source
1248 * Returns: (transfer full): a deep copy of the initial #GPtrArray.
1253 g_ptr_array_copy (GPtrArray *array,
1257 GRealPtrArray *rarray = (GRealPtrArray *) array;
1258 GPtrArray *new_array;
1260 g_return_val_if_fail (array != NULL, NULL);
1262 new_array = ptr_array_new (0,
1263 rarray->element_free_func,
1264 rarray->null_terminated);
1266 if (rarray->alloc > 0)
1268 g_ptr_array_maybe_expand ((GRealPtrArray *) new_array, array->len + rarray->null_terminated);
1276 for (i = 0; i < array->len; i++)
1277 new_array->pdata[i] = func (array->pdata[i], user_data);
1281 memcpy (new_array->pdata, array->pdata,
1282 array->len * sizeof (*array->pdata));
1285 new_array->len = array->len;
1288 ptr_array_maybe_null_terminate ((GRealPtrArray *) new_array);
1295 * g_ptr_array_sized_new:
1296 * @reserved_size: number of pointers preallocated
1298 * Creates a new #GPtrArray with @reserved_size pointers preallocated
1299 * and a reference count of 1. This avoids frequent reallocation, if
1300 * you are going to add many pointers to the array. Note however that
1301 * the size of the array is still 0.
1303 * Returns: the new #GPtrArray
1306 g_ptr_array_sized_new (guint reserved_size)
1308 return ptr_array_new (reserved_size, NULL, FALSE);
1313 * @array: A #GArray.
1315 * Create a shallow copy of a #GArray. If the array elements consist of
1316 * pointers to data, the pointers are copied but the actual data is not.
1318 * Returns: (transfer container): A copy of @array.
1323 g_array_copy (GArray *array)
1325 GRealArray *rarray = (GRealArray *) array;
1326 GRealArray *new_rarray;
1328 g_return_val_if_fail (rarray != NULL, NULL);
1331 (GRealArray *) g_array_sized_new (rarray->zero_terminated, rarray->clear,
1332 rarray->elt_size, rarray->elt_capacity);
1333 new_rarray->len = rarray->len;
1334 if (rarray->len > 0)
1335 memcpy (new_rarray->data, rarray->data, rarray->len * rarray->elt_size);
1337 g_array_zero_terminate (new_rarray);
1339 return (GArray *) new_rarray;
1343 * g_ptr_array_new_with_free_func:
1344 * @element_free_func: (nullable): A function to free elements with
1345 * destroy @array or %NULL
1347 * Creates a new #GPtrArray with a reference count of 1 and use
1348 * @element_free_func for freeing each element when the array is destroyed
1349 * either via g_ptr_array_unref(), when g_ptr_array_free() is called with
1350 * @free_segment set to %TRUE or when removing elements.
1352 * Returns: (transfer full): A new #GPtrArray
1357 g_ptr_array_new_with_free_func (GDestroyNotify element_free_func)
1359 return ptr_array_new (0, element_free_func, FALSE);
1363 * g_ptr_array_new_full:
1364 * @reserved_size: number of pointers preallocated
1365 * @element_free_func: (nullable): A function to free elements with
1366 * destroy @array or %NULL
1368 * Creates a new #GPtrArray with @reserved_size pointers preallocated
1369 * and a reference count of 1. This avoids frequent reallocation, if
1370 * you are going to add many pointers to the array. Note however that
1371 * the size of the array is still 0. It also set @element_free_func
1372 * for freeing each element when the array is destroyed either via
1373 * g_ptr_array_unref(), when g_ptr_array_free() is called with
1374 * @free_segment set to %TRUE or when removing elements.
1376 * Returns: (transfer full): A new #GPtrArray
1381 g_ptr_array_new_full (guint reserved_size,
1382 GDestroyNotify element_free_func)
1384 return ptr_array_new (reserved_size, element_free_func, FALSE);
1388 * g_ptr_array_new_null_terminated:
1389 * @reserved_size: number of pointers preallocated.
1390 * If @null_terminated is %TRUE, the actually allocated
1391 * buffer size is @reserved_size plus 1, unless @reserved_size
1392 * is zero, in which case no initial buffer gets allocated.
1393 * @element_free_func: (nullable): A function to free elements with
1394 * destroy @array or %NULL
1395 * @null_terminated: whether to make the array as %NULL terminated.
1397 * Like g_ptr_array_new_full() but also allows to set the array to
1398 * be %NULL terminated. A %NULL terminated pointer array has an
1399 * additional %NULL pointer after the last element, beyond the
1402 * #GPtrArray created by other constructors are not automatically %NULL
1405 * Note that if the @array's length is zero and currently no
1406 * data array is allocated, then pdata will still be %NULL.
1407 * %GPtrArray will only %NULL terminate pdata, if an actual
1408 * array is allocated. It does not guarantee that an array
1409 * is always allocated. In other words, if the length is zero,
1410 * then pdata may either point to a %NULL terminated array of length
1413 * Returns: (transfer full): A new #GPtrArray
1418 g_ptr_array_new_null_terminated (guint reserved_size,
1419 GDestroyNotify element_free_func,
1420 gboolean null_terminated)
1422 return ptr_array_new (reserved_size, element_free_func, null_terminated);
1426 * g_ptr_array_set_free_func:
1427 * @array: A #GPtrArray
1428 * @element_free_func: (nullable): A function to free elements with
1429 * destroy @array or %NULL
1431 * Sets a function for freeing each element when @array is destroyed
1432 * either via g_ptr_array_unref(), when g_ptr_array_free() is called
1433 * with @free_segment set to %TRUE or when removing elements.
1438 g_ptr_array_set_free_func (GPtrArray *array,
1439 GDestroyNotify element_free_func)
1441 GRealPtrArray *rarray = (GRealPtrArray *)array;
1443 g_return_if_fail (array);
1445 rarray->element_free_func = element_free_func;
1449 * g_ptr_array_is_null_terminated:
1450 * @array: the #GPtrArray
1452 * Gets whether the @array was constructed as %NULL-terminated.
1454 * This will only return %TRUE for arrays constructed by passing %TRUE to the
1455 * `null_terminated` argument of g_ptr_array_new_null_terminated(). It will not
1456 * return %TRUE for normal arrays which have had a %NULL element appended to
1459 * Returns: %TRUE if the array is made to be %NULL terminated.
1464 g_ptr_array_is_null_terminated (GPtrArray *array)
1466 g_return_val_if_fail (array, FALSE);
1468 return ((GRealPtrArray *) array)->null_terminated;
1473 * @array: a #GPtrArray
1475 * Atomically increments the reference count of @array by one.
1476 * This function is thread-safe and may be called from any thread.
1478 * Returns: The passed in #GPtrArray
1483 g_ptr_array_ref (GPtrArray *array)
1485 GRealPtrArray *rarray = (GRealPtrArray *)array;
1487 g_return_val_if_fail (array, NULL);
1489 g_atomic_ref_count_inc (&rarray->ref_count);
1494 static gpointer *ptr_array_free (GPtrArray *, ArrayFreeFlags);
1497 * g_ptr_array_unref:
1498 * @array: A #GPtrArray
1500 * Atomically decrements the reference count of @array by one. If the
1501 * reference count drops to 0, the effect is the same as calling
1502 * g_ptr_array_free() with @free_segment set to %TRUE. This function
1503 * is thread-safe and may be called from any thread.
1508 g_ptr_array_unref (GPtrArray *array)
1510 GRealPtrArray *rarray = (GRealPtrArray *)array;
1512 g_return_if_fail (array);
1514 if (g_atomic_ref_count_dec (&rarray->ref_count))
1515 ptr_array_free (array, FREE_SEGMENT);
1520 * @array: a #GPtrArray
1521 * @free_seg: if %TRUE the actual pointer array is freed as well
1523 * Frees the memory allocated for the #GPtrArray. If @free_seg is %TRUE
1524 * it frees the memory block holding the elements as well. Pass %FALSE
1525 * if you want to free the #GPtrArray wrapper but preserve the
1526 * underlying array for use elsewhere. If the reference count of @array
1527 * is greater than one, the #GPtrArray wrapper is preserved but the
1528 * size of @array will be set to zero.
1530 * If array contents point to dynamically-allocated memory, they should
1531 * be freed separately if @free_seg is %TRUE and no #GDestroyNotify
1532 * function has been set for @array.
1534 * Note that if the array is %NULL terminated and @free_seg is %FALSE
1535 * then this will always return an allocated %NULL terminated buffer.
1536 * If pdata is previously %NULL, a new buffer will be allocated.
1538 * This function is not thread-safe. If using a #GPtrArray from multiple
1539 * threads, use only the atomic g_ptr_array_ref() and g_ptr_array_unref()
1542 * Returns: (transfer full) (nullable): the pointer array if @free_seg is
1543 * %FALSE, otherwise %NULL. The pointer array should be freed using g_free().
1546 g_ptr_array_free (GPtrArray *array,
1547 gboolean free_segment)
1549 GRealPtrArray *rarray = (GRealPtrArray *)array;
1550 ArrayFreeFlags flags;
1552 g_return_val_if_fail (rarray, NULL);
1554 flags = (free_segment ? FREE_SEGMENT : 0);
1556 /* if others are holding a reference, preserve the wrapper but
1557 * do free/return the data
1559 * Coverity doesn’t understand this and assumes it’s a leak, so comment this
1562 #ifndef __COVERITY__
1563 if (!g_atomic_ref_count_dec (&rarray->ref_count))
1564 flags |= PRESERVE_WRAPPER;
1567 return ptr_array_free (array, flags);
1571 ptr_array_free (GPtrArray *array,
1572 ArrayFreeFlags flags)
1574 GRealPtrArray *rarray = (GRealPtrArray *)array;
1577 if (flags & FREE_SEGMENT)
1579 /* Data here is stolen and freed manually. It is an
1580 * error to attempt to access the array data (including
1581 * mutating the array bounds) during destruction).
1583 * https://bugzilla.gnome.org/show_bug.cgi?id=769064
1585 gpointer *stolen_pdata = g_steal_pointer (&rarray->pdata);
1586 if (rarray->element_free_func != NULL)
1590 for (i = 0; i < rarray->len; ++i)
1591 rarray->element_free_func (stolen_pdata[i]);
1594 g_free (stolen_pdata);
1599 segment = rarray->pdata;
1600 if (!segment && rarray->null_terminated)
1601 segment = (gpointer *) g_new0 (char *, 1);
1604 if (flags & PRESERVE_WRAPPER)
1606 rarray->pdata = NULL;
1612 g_slice_free1 (sizeof (GRealPtrArray), rarray);
1619 g_ptr_array_maybe_expand (GRealPtrArray *array,
1624 /* The maximum array length is derived from following constraints:
1625 * - The number of bytes must fit into a gsize / 2.
1626 * - The number of elements must fit into guint.
1628 max_len = MIN (G_MAXSIZE / 2 / sizeof (gpointer), G_MAXUINT);
1630 /* Detect potential overflow */
1631 if G_UNLIKELY ((max_len - array->len) < len)
1632 g_error ("adding %u to array would overflow", len);
1634 if ((array->len + len) > array->alloc)
1636 guint old_alloc = array->alloc;
1637 gsize want_alloc = g_nearest_pow (sizeof (gpointer) * (array->len + len));
1638 want_alloc = MAX (want_alloc, MIN_ARRAY_SIZE);
1639 array->alloc = MIN (want_alloc / sizeof (gpointer), G_MAXUINT);
1640 array->pdata = g_realloc (array->pdata, want_alloc);
1641 if (G_UNLIKELY (g_mem_gc_friendly))
1642 for ( ; old_alloc < array->alloc; old_alloc++)
1643 array->pdata [old_alloc] = NULL;
1648 * g_ptr_array_set_size:
1649 * @array: a #GPtrArray
1650 * @length: the new length of the pointer array
1652 * Sets the size of the array. When making the array larger,
1653 * newly-added elements will be set to %NULL. When making it smaller,
1654 * if @array has a non-%NULL #GDestroyNotify function then it will be
1655 * called for the removed elements.
1658 g_ptr_array_set_size (GPtrArray *array,
1661 GRealPtrArray *rarray = (GRealPtrArray *)array;
1662 guint length_unsigned;
1664 g_return_if_fail (rarray);
1665 g_return_if_fail (rarray->len == 0 || (rarray->len != 0 && rarray->pdata != NULL));
1666 g_return_if_fail (length >= 0);
1668 length_unsigned = (guint) length;
1670 if (length_unsigned > rarray->len)
1674 if (G_UNLIKELY (rarray->null_terminated) &&
1675 length_unsigned - rarray->len > G_MAXUINT - 1)
1676 g_error ("array would overflow");
1678 g_ptr_array_maybe_expand (rarray, (length_unsigned - rarray->len) + rarray->null_terminated);
1681 * memset (array->pdata + array->len, 0,
1682 * sizeof (gpointer) * (length_unsigned - array->len));
1683 * to make it really portable. Remember (void*)NULL needn't be
1684 * bitwise zero. It of course is silly not to use memset (..,0,..).
1686 for (i = rarray->len; i < length_unsigned; i++)
1687 rarray->pdata[i] = NULL;
1689 rarray->len = length_unsigned;
1691 ptr_array_maybe_null_terminate (rarray);
1693 else if (length_unsigned < rarray->len)
1694 g_ptr_array_remove_range (array, length_unsigned, rarray->len - length_unsigned);
1698 ptr_array_remove_index (GPtrArray *array,
1701 gboolean free_element)
1703 GRealPtrArray *rarray = (GRealPtrArray *) array;
1706 g_return_val_if_fail (rarray, NULL);
1707 g_return_val_if_fail (rarray->len == 0 || (rarray->len != 0 && rarray->pdata != NULL), NULL);
1709 g_return_val_if_fail (index_ < rarray->len, NULL);
1711 result = rarray->pdata[index_];
1713 if (rarray->element_free_func != NULL && free_element)
1714 rarray->element_free_func (rarray->pdata[index_]);
1716 if (index_ != rarray->len - 1 && !fast)
1717 memmove (rarray->pdata + index_, rarray->pdata + index_ + 1,
1718 sizeof (gpointer) * (rarray->len - index_ - 1));
1719 else if (index_ != rarray->len - 1)
1720 rarray->pdata[index_] = rarray->pdata[rarray->len - 1];
1724 if (rarray->null_terminated || G_UNLIKELY (g_mem_gc_friendly))
1725 rarray->pdata[rarray->len] = NULL;
1731 * g_ptr_array_remove_index:
1732 * @array: a #GPtrArray
1733 * @index_: the index of the pointer to remove
1735 * Removes the pointer at the given index from the pointer array.
1736 * The following elements are moved down one place. If @array has
1737 * a non-%NULL #GDestroyNotify function it is called for the removed
1738 * element. If so, the return value from this function will potentially point
1739 * to freed memory (depending on the #GDestroyNotify implementation).
1741 * Returns: (nullable): the pointer which was removed
1744 g_ptr_array_remove_index (GPtrArray *array,
1747 return ptr_array_remove_index (array, index_, FALSE, TRUE);
1751 * g_ptr_array_remove_index_fast:
1752 * @array: a #GPtrArray
1753 * @index_: the index of the pointer to remove
1755 * Removes the pointer at the given index from the pointer array.
1756 * The last element in the array is used to fill in the space, so
1757 * this function does not preserve the order of the array. But it
1758 * is faster than g_ptr_array_remove_index(). If @array has a non-%NULL
1759 * #GDestroyNotify function it is called for the removed element. If so, the
1760 * return value from this function will potentially point to freed memory
1761 * (depending on the #GDestroyNotify implementation).
1763 * Returns: (nullable): the pointer which was removed
1766 g_ptr_array_remove_index_fast (GPtrArray *array,
1769 return ptr_array_remove_index (array, index_, TRUE, TRUE);
1773 * g_ptr_array_steal_index:
1774 * @array: a #GPtrArray
1775 * @index_: the index of the pointer to steal
1777 * Removes the pointer at the given index from the pointer array.
1778 * The following elements are moved down one place. The #GDestroyNotify for
1779 * @array is *not* called on the removed element; ownership is transferred to
1780 * the caller of this function.
1782 * Returns: (transfer full) (nullable): the pointer which was removed
1786 g_ptr_array_steal_index (GPtrArray *array,
1789 return ptr_array_remove_index (array, index_, FALSE, FALSE);
1793 * g_ptr_array_steal_index_fast:
1794 * @array: a #GPtrArray
1795 * @index_: the index of the pointer to steal
1797 * Removes the pointer at the given index from the pointer array.
1798 * The last element in the array is used to fill in the space, so
1799 * this function does not preserve the order of the array. But it
1800 * is faster than g_ptr_array_steal_index(). The #GDestroyNotify for @array is
1801 * *not* called on the removed element; ownership is transferred to the caller
1804 * Returns: (transfer full) (nullable): the pointer which was removed
1808 g_ptr_array_steal_index_fast (GPtrArray *array,
1811 return ptr_array_remove_index (array, index_, TRUE, FALSE);
1815 * g_ptr_array_remove_range:
1816 * @array: a @GPtrArray
1817 * @index_: the index of the first pointer to remove
1818 * @length: the number of pointers to remove
1820 * Removes the given number of pointers starting at the given index
1821 * from a #GPtrArray. The following elements are moved to close the
1822 * gap. If @array has a non-%NULL #GDestroyNotify function it is
1823 * called for the removed elements.
1825 * Returns: the @array
1830 g_ptr_array_remove_range (GPtrArray *array,
1834 GRealPtrArray *rarray = (GRealPtrArray *)array;
1837 g_return_val_if_fail (rarray != NULL, NULL);
1838 g_return_val_if_fail (rarray->len == 0 || (rarray->len != 0 && rarray->pdata != NULL), NULL);
1839 g_return_val_if_fail (index_ <= rarray->len, NULL);
1840 g_return_val_if_fail (length == 0 || index_ + length <= rarray->len, NULL);
1845 if (rarray->element_free_func != NULL)
1847 for (i = index_; i < index_ + length; i++)
1848 rarray->element_free_func (rarray->pdata[i]);
1851 if (index_ + length != rarray->len)
1853 memmove (&rarray->pdata[index_],
1854 &rarray->pdata[index_ + length],
1855 (rarray->len - (index_ + length)) * sizeof (gpointer));
1858 rarray->len -= length;
1859 if (G_UNLIKELY (g_mem_gc_friendly))
1861 for (i = 0; i < length; i++)
1862 rarray->pdata[rarray->len + i] = NULL;
1865 ptr_array_maybe_null_terminate (rarray);
1871 * g_ptr_array_remove:
1872 * @array: a #GPtrArray
1873 * @data: the pointer to remove
1875 * Removes the first occurrence of the given pointer from the pointer
1876 * array. The following elements are moved down one place. If @array
1877 * has a non-%NULL #GDestroyNotify function it is called for the
1880 * It returns %TRUE if the pointer was removed, or %FALSE if the
1881 * pointer was not found.
1883 * Returns: %TRUE if the pointer is removed, %FALSE if the pointer
1884 * is not found in the array
1887 g_ptr_array_remove (GPtrArray *array,
1892 g_return_val_if_fail (array, FALSE);
1893 g_return_val_if_fail (array->len == 0 || (array->len != 0 && array->pdata != NULL), FALSE);
1895 for (i = 0; i < array->len; i += 1)
1897 if (array->pdata[i] == data)
1899 g_ptr_array_remove_index (array, i);
1908 * g_ptr_array_remove_fast:
1909 * @array: a #GPtrArray
1910 * @data: the pointer to remove
1912 * Removes the first occurrence of the given pointer from the pointer
1913 * array. The last element in the array is used to fill in the space,
1914 * so this function does not preserve the order of the array. But it
1915 * is faster than g_ptr_array_remove(). If @array has a non-%NULL
1916 * #GDestroyNotify function it is called for the removed element.
1918 * It returns %TRUE if the pointer was removed, or %FALSE if the
1919 * pointer was not found.
1921 * Returns: %TRUE if the pointer was found in the array
1924 g_ptr_array_remove_fast (GPtrArray *array,
1927 GRealPtrArray *rarray = (GRealPtrArray *)array;
1930 g_return_val_if_fail (rarray, FALSE);
1931 g_return_val_if_fail (rarray->len == 0 || (rarray->len != 0 && rarray->pdata != NULL), FALSE);
1933 for (i = 0; i < rarray->len; i += 1)
1935 if (rarray->pdata[i] == data)
1937 g_ptr_array_remove_index_fast (array, i);
1947 * @array: a #GPtrArray
1948 * @data: the pointer to add
1950 * Adds a pointer to the end of the pointer array. The array will grow
1951 * in size automatically if necessary.
1954 g_ptr_array_add (GPtrArray *array,
1957 GRealPtrArray *rarray = (GRealPtrArray *)array;
1959 g_return_if_fail (rarray);
1960 g_return_if_fail (rarray->len == 0 || (rarray->len != 0 && rarray->pdata != NULL));
1962 g_ptr_array_maybe_expand (rarray, 1u + rarray->null_terminated);
1964 rarray->pdata[rarray->len++] = data;
1966 ptr_array_maybe_null_terminate (rarray);
1970 * g_ptr_array_extend:
1971 * @array_to_extend: a #GPtrArray.
1972 * @array: (transfer none): a #GPtrArray to add to the end of @array_to_extend.
1973 * @func: (nullable): a copy function used to copy every element in the array
1974 * @user_data: user data passed to the copy function @func, or %NULL
1976 * Adds all pointers of @array to the end of the array @array_to_extend.
1977 * The array will grow in size automatically if needed. @array_to_extend is
1978 * modified in-place.
1980 * @func, as a #GCopyFunc, takes two arguments, the data to be copied
1981 * and a @user_data pointer. On common processor architectures, it's safe to
1982 * pass %NULL as @user_data if the copy function takes only one argument. You
1983 * may get compiler warnings from this though if compiling with GCC’s
1984 * `-Wcast-function-type` warning.
1986 * If @func is %NULL, then only the pointers (and not what they are
1987 * pointing to) are copied to the new #GPtrArray.
1989 * Whether @array_to_extend is %NULL terminated stays unchanged by this function.
1994 g_ptr_array_extend (GPtrArray *array_to_extend,
1999 GRealPtrArray *rarray_to_extend = (GRealPtrArray *) array_to_extend;
2001 g_return_if_fail (array_to_extend != NULL);
2002 g_return_if_fail (array != NULL);
2004 if (array->len == 0u)
2007 if (G_UNLIKELY (array->len == G_MAXUINT) &&
2008 rarray_to_extend->null_terminated)
2009 g_error ("adding %u to array would overflow", array->len);
2011 g_ptr_array_maybe_expand (rarray_to_extend, array->len + rarray_to_extend->null_terminated);
2017 for (i = 0; i < array->len; i++)
2018 rarray_to_extend->pdata[i + rarray_to_extend->len] =
2019 func (array->pdata[i], user_data);
2021 else if (array->len > 0)
2023 memcpy (rarray_to_extend->pdata + rarray_to_extend->len, array->pdata,
2024 array->len * sizeof (*array->pdata));
2027 rarray_to_extend->len += array->len;
2029 ptr_array_maybe_null_terminate (rarray_to_extend);
2033 * g_ptr_array_extend_and_steal:
2034 * @array_to_extend: (transfer none): a #GPtrArray.
2035 * @array: (transfer container): a #GPtrArray to add to the end of
2038 * Adds all the pointers in @array to the end of @array_to_extend, transferring
2039 * ownership of each element from @array to @array_to_extend and modifying
2040 * @array_to_extend in-place. @array is then freed.
2042 * As with g_ptr_array_free(), @array will be destroyed if its reference count
2043 * is 1. If its reference count is higher, it will be decremented and the
2044 * length of @array set to zero.
2049 g_ptr_array_extend_and_steal (GPtrArray *array_to_extend,
2054 g_ptr_array_extend (array_to_extend, array, NULL, NULL);
2056 /* Get rid of @array without triggering the GDestroyNotify attached
2057 * to the elements moved from @array to @array_to_extend. */
2058 pdata = g_steal_pointer (&array->pdata);
2060 ((GRealPtrArray *) array)->alloc = 0;
2061 g_ptr_array_unref (array);
2066 * g_ptr_array_insert:
2067 * @array: a #GPtrArray
2068 * @index_: the index to place the new element at, or -1 to append
2069 * @data: the pointer to add.
2071 * Inserts an element into the pointer array at the given index. The
2072 * array will grow in size automatically if necessary.
2077 g_ptr_array_insert (GPtrArray *array,
2081 GRealPtrArray *rarray = (GRealPtrArray *)array;
2083 g_return_if_fail (rarray);
2084 g_return_if_fail (index_ >= -1);
2085 g_return_if_fail (index_ <= (gint)rarray->len);
2087 g_ptr_array_maybe_expand (rarray, 1u + rarray->null_terminated);
2090 index_ = rarray->len;
2092 if ((guint) index_ < rarray->len)
2093 memmove (&(rarray->pdata[index_ + 1]),
2094 &(rarray->pdata[index_]),
2095 (rarray->len - index_) * sizeof (gpointer));
2098 rarray->pdata[index_] = data;
2100 ptr_array_maybe_null_terminate (rarray);
2103 /* Please keep this doc-comment in sync with pointer_array_sort_example()
2104 * in glib/tests/array-test.c */
2107 * @array: a #GPtrArray
2108 * @compare_func: comparison function
2110 * Sorts the array, using @compare_func which should be a qsort()-style
2111 * comparison function (returns less than zero for first arg is less
2112 * than second arg, zero for equal, greater than zero if irst arg is
2113 * greater than second arg).
2115 * Note that the comparison function for g_ptr_array_sort() doesn't
2116 * take the pointers from the array as arguments, it takes pointers to
2117 * the pointers in the array. Here is a full example of usage:
2119 * |[<!-- language="C" -->
2127 * sort_filelist (gconstpointer a, gconstpointer b)
2129 * const FileListEntry *entry1 = *((FileListEntry **) a);
2130 * const FileListEntry *entry2 = *((FileListEntry **) b);
2132 * return g_ascii_strcasecmp (entry1->name, entry2->name);
2136 * g_autoptr (GPtrArray) file_list = NULL;
2138 * // initialize file_list array and load with many FileListEntry entries
2140 * // now sort it with
2141 * g_ptr_array_sort (file_list, sort_filelist);
2144 * This is guaranteed to be a stable sort since version 2.32.
2147 g_ptr_array_sort (GPtrArray *array,
2148 GCompareFunc compare_func)
2150 g_return_if_fail (array != NULL);
2152 /* Don't use qsort as we want a guaranteed stable sort */
2154 g_qsort_with_data (array->pdata,
2157 (GCompareDataFunc)compare_func,
2161 /* Please keep this doc-comment in sync with
2162 * pointer_array_sort_with_data_example() in glib/tests/array-test.c */
2164 * g_ptr_array_sort_with_data:
2165 * @array: a #GPtrArray
2166 * @compare_func: comparison function
2167 * @user_data: data to pass to @compare_func
2169 * Like g_ptr_array_sort(), but the comparison function has an extra
2170 * user data argument.
2172 * Note that the comparison function for g_ptr_array_sort_with_data()
2173 * doesn't take the pointers from the array as arguments, it takes
2174 * pointers to the pointers in the array. Here is a full example of use:
2176 * |[<!-- language="C" -->
2177 * typedef enum { SORT_NAME, SORT_SIZE } SortMode;
2186 * sort_filelist (gconstpointer a, gconstpointer b, gpointer user_data)
2189 * const SortMode sort_mode = GPOINTER_TO_INT (user_data);
2190 * const FileListEntry *entry1 = *((FileListEntry **) a);
2191 * const FileListEntry *entry2 = *((FileListEntry **) b);
2193 * switch (sort_mode)
2196 * order = g_ascii_strcasecmp (entry1->name, entry2->name);
2199 * order = entry1->size - entry2->size;
2209 * g_autoptr (GPtrArray) file_list = NULL;
2210 * SortMode sort_mode;
2212 * // initialize file_list array and load with many FileListEntry entries
2214 * // now sort it with
2215 * sort_mode = SORT_NAME;
2216 * g_ptr_array_sort_with_data (file_list,
2218 * GINT_TO_POINTER (sort_mode));
2221 * This is guaranteed to be a stable sort since version 2.32.
2224 g_ptr_array_sort_with_data (GPtrArray *array,
2225 GCompareDataFunc compare_func,
2228 g_return_if_fail (array != NULL);
2231 g_qsort_with_data (array->pdata,
2239 * g_ptr_array_foreach:
2240 * @array: a #GPtrArray
2241 * @func: the function to call for each array element
2242 * @user_data: user data to pass to the function
2244 * Calls a function for each element of a #GPtrArray. @func must not
2245 * add elements to or remove elements from the array.
2250 g_ptr_array_foreach (GPtrArray *array,
2256 g_return_if_fail (array);
2258 for (i = 0; i < array->len; i++)
2259 (*func) (array->pdata[i], user_data);
2263 * g_ptr_array_find: (skip)
2264 * @haystack: pointer array to be searched
2265 * @needle: pointer to look for
2266 * @index_: (optional) (out): return location for the index of
2267 * the element, if found
2269 * Checks whether @needle exists in @haystack. If the element is found, %TRUE is
2270 * returned and the element’s index is returned in @index_ (if non-%NULL).
2271 * Otherwise, %FALSE is returned and @index_ is undefined. If @needle exists
2272 * multiple times in @haystack, the index of the first instance is returned.
2274 * This does pointer comparisons only. If you want to use more complex equality
2275 * checks, such as string comparisons, use g_ptr_array_find_with_equal_func().
2277 * Returns: %TRUE if @needle is one of the elements of @haystack
2281 g_ptr_array_find (GPtrArray *haystack,
2282 gconstpointer needle,
2285 return g_ptr_array_find_with_equal_func (haystack, needle, NULL, index_);
2289 * g_ptr_array_find_with_equal_func: (skip)
2290 * @haystack: pointer array to be searched
2291 * @needle: pointer to look for
2292 * @equal_func: (nullable): the function to call for each element, which should
2293 * return %TRUE when the desired element is found; or %NULL to use pointer
2295 * @index_: (optional) (out): return location for the index of
2296 * the element, if found
2298 * Checks whether @needle exists in @haystack, using the given @equal_func.
2299 * If the element is found, %TRUE is returned and the element’s index is
2300 * returned in @index_ (if non-%NULL). Otherwise, %FALSE is returned and @index_
2301 * is undefined. If @needle exists multiple times in @haystack, the index of
2302 * the first instance is returned.
2304 * @equal_func is called with the element from the array as its first parameter,
2305 * and @needle as its second parameter. If @equal_func is %NULL, pointer
2308 * Returns: %TRUE if @needle is one of the elements of @haystack
2312 g_ptr_array_find_with_equal_func (GPtrArray *haystack,
2313 gconstpointer needle,
2314 GEqualFunc equal_func,
2319 g_return_val_if_fail (haystack != NULL, FALSE);
2321 if (equal_func == NULL)
2322 equal_func = g_direct_equal;
2324 for (i = 0; i < haystack->len; i++)
2326 if (equal_func (g_ptr_array_index (haystack, i), needle))
2338 * SECTION:arrays_byte
2339 * @title: Byte Arrays
2340 * @short_description: arrays of bytes
2342 * #GByteArray is a mutable array of bytes based on #GArray, to provide arrays
2343 * of bytes which grow automatically as elements are added.
2345 * To create a new #GByteArray use g_byte_array_new(). To add elements to a
2346 * #GByteArray, use g_byte_array_append(), and g_byte_array_prepend().
2348 * To set the size of a #GByteArray, use g_byte_array_set_size().
2350 * To free a #GByteArray, use g_byte_array_free().
2352 * An example for using a #GByteArray:
2353 * |[<!-- language="C" -->
2354 * GByteArray *gbarray;
2357 * gbarray = g_byte_array_new ();
2358 * for (i = 0; i < 10000; i++)
2359 * g_byte_array_append (gbarray, (guint8*) "abcd", 4);
2361 * for (i = 0; i < 10000; i++)
2363 * g_assert (gbarray->data[4*i] == 'a');
2364 * g_assert (gbarray->data[4*i+1] == 'b');
2365 * g_assert (gbarray->data[4*i+2] == 'c');
2366 * g_assert (gbarray->data[4*i+3] == 'd');
2369 * g_byte_array_free (gbarray, TRUE);
2372 * See #GBytes if you are interested in an immutable object representing a
2373 * sequence of bytes.
2378 * @data: a pointer to the element data. The data may be moved as
2379 * elements are added to the #GByteArray
2380 * @len: the number of elements in the #GByteArray
2382 * Contains the public fields of a GByteArray.
2388 * Creates a new #GByteArray with a reference count of 1.
2390 * Returns: (transfer full): the new #GByteArray
2393 g_byte_array_new (void)
2395 return (GByteArray *)g_array_sized_new (FALSE, FALSE, 1, 0);
2399 * g_byte_array_steal:
2400 * @array: a #GByteArray.
2401 * @len: (optional) (out): pointer to retrieve the number of
2402 * elements of the original array
2404 * Frees the data in the array and resets the size to zero, while
2405 * the underlying array is preserved for use elsewhere and returned
2408 * Returns: (transfer full): the element data, which should be
2409 * freed using g_free().
2414 g_byte_array_steal (GByteArray *array,
2417 return (guint8 *) g_array_steal ((GArray *) array, len);
2421 * g_byte_array_new_take:
2422 * @data: (transfer full) (array length=len): byte data for the array
2423 * @len: length of @data
2425 * Create byte array containing the data. The data will be owned by the array
2426 * and will be freed with g_free(), i.e. it could be allocated using g_strdup().
2428 * Do not use it if @len is greater than %G_MAXUINT. #GByteArray
2429 * stores the length of its data in #guint, which may be shorter than
2434 * Returns: (transfer full): a new #GByteArray
2437 g_byte_array_new_take (guint8 *data,
2443 g_return_val_if_fail (len <= G_MAXUINT, NULL);
2444 array = g_byte_array_new ();
2445 real = (GRealArray *)array;
2446 g_assert (real->data == NULL);
2447 g_assert (real->len == 0);
2451 real->elt_capacity = len;
2457 * g_byte_array_sized_new:
2458 * @reserved_size: number of bytes preallocated
2460 * Creates a new #GByteArray with @reserved_size bytes preallocated.
2461 * This avoids frequent reallocation, if you are going to add many
2462 * bytes to the array. Note however that the size of the array is still
2465 * Returns: the new #GByteArray
2468 g_byte_array_sized_new (guint reserved_size)
2470 return (GByteArray *)g_array_sized_new (FALSE, FALSE, 1, reserved_size);
2474 * g_byte_array_free:
2475 * @array: a #GByteArray
2476 * @free_segment: if %TRUE the actual byte data is freed as well
2478 * Frees the memory allocated by the #GByteArray. If @free_segment is
2479 * %TRUE it frees the actual byte data. If the reference count of
2480 * @array is greater than one, the #GByteArray wrapper is preserved but
2481 * the size of @array will be set to zero.
2483 * Returns: the element data if @free_segment is %FALSE, otherwise
2484 * %NULL. The element data should be freed using g_free().
2487 g_byte_array_free (GByteArray *array,
2488 gboolean free_segment)
2490 return (guint8 *)g_array_free ((GArray *)array, free_segment);
2494 * g_byte_array_free_to_bytes:
2495 * @array: (transfer full): a #GByteArray
2497 * Transfers the data from the #GByteArray into a new immutable #GBytes.
2499 * The #GByteArray is freed unless the reference count of @array is greater
2500 * than one, the #GByteArray wrapper is preserved but the size of @array
2501 * will be set to zero.
2503 * This is identical to using g_bytes_new_take() and g_byte_array_free()
2508 * Returns: (transfer full): a new immutable #GBytes representing same
2509 * byte data that was in the array
2512 g_byte_array_free_to_bytes (GByteArray *array)
2516 g_return_val_if_fail (array != NULL, NULL);
2518 length = array->len;
2519 return g_bytes_new_take (g_byte_array_free (array, FALSE), length);
2524 * @array: A #GByteArray
2526 * Atomically increments the reference count of @array by one.
2527 * This function is thread-safe and may be called from any thread.
2529 * Returns: The passed in #GByteArray
2534 g_byte_array_ref (GByteArray *array)
2536 return (GByteArray *)g_array_ref ((GArray *)array);
2540 * g_byte_array_unref:
2541 * @array: A #GByteArray
2543 * Atomically decrements the reference count of @array by one. If the
2544 * reference count drops to 0, all memory allocated by the array is
2545 * released. This function is thread-safe and may be called from any
2551 g_byte_array_unref (GByteArray *array)
2553 g_array_unref ((GArray *)array);
2557 * g_byte_array_append:
2558 * @array: a #GByteArray
2559 * @data: the byte data to be added
2560 * @len: the number of bytes to add
2562 * Adds the given bytes to the end of the #GByteArray.
2563 * The array will grow in size automatically if necessary.
2565 * Returns: the #GByteArray
2568 g_byte_array_append (GByteArray *array,
2572 g_array_append_vals ((GArray *)array, (guint8 *)data, len);
2578 * g_byte_array_prepend:
2579 * @array: a #GByteArray
2580 * @data: the byte data to be added
2581 * @len: the number of bytes to add
2583 * Adds the given data to the start of the #GByteArray.
2584 * The array will grow in size automatically if necessary.
2586 * Returns: the #GByteArray
2589 g_byte_array_prepend (GByteArray *array,
2593 g_array_prepend_vals ((GArray *)array, (guint8 *)data, len);
2599 * g_byte_array_set_size:
2600 * @array: a #GByteArray
2601 * @length: the new size of the #GByteArray
2603 * Sets the size of the #GByteArray, expanding it if necessary.
2605 * Returns: the #GByteArray
2608 g_byte_array_set_size (GByteArray *array,
2611 g_array_set_size ((GArray *)array, length);
2617 * g_byte_array_remove_index:
2618 * @array: a #GByteArray
2619 * @index_: the index of the byte to remove
2621 * Removes the byte at the given index from a #GByteArray.
2622 * The following bytes are moved down one place.
2624 * Returns: the #GByteArray
2627 g_byte_array_remove_index (GByteArray *array,
2630 g_array_remove_index ((GArray *)array, index_);
2636 * g_byte_array_remove_index_fast:
2637 * @array: a #GByteArray
2638 * @index_: the index of the byte to remove
2640 * Removes the byte at the given index from a #GByteArray. The last
2641 * element in the array is used to fill in the space, so this function
2642 * does not preserve the order of the #GByteArray. But it is faster
2643 * than g_byte_array_remove_index().
2645 * Returns: the #GByteArray
2648 g_byte_array_remove_index_fast (GByteArray *array,
2651 g_array_remove_index_fast ((GArray *)array, index_);
2657 * g_byte_array_remove_range:
2658 * @array: a @GByteArray
2659 * @index_: the index of the first byte to remove
2660 * @length: the number of bytes to remove
2662 * Removes the given number of bytes starting at the given index from a
2663 * #GByteArray. The following elements are moved to close the gap.
2665 * Returns: the #GByteArray
2670 g_byte_array_remove_range (GByteArray *array,
2674 g_return_val_if_fail (array, NULL);
2675 g_return_val_if_fail (index_ <= array->len, NULL);
2676 g_return_val_if_fail (index_ + length <= array->len, NULL);
2678 return (GByteArray *)g_array_remove_range ((GArray *)array, index_, length);
2682 * g_byte_array_sort:
2683 * @array: a #GByteArray
2684 * @compare_func: comparison function
2686 * Sorts a byte array, using @compare_func which should be a
2687 * qsort()-style comparison function (returns less than zero for first
2688 * arg is less than second arg, zero for equal, greater than zero if
2689 * first arg is greater than second arg).
2691 * If two array elements compare equal, their order in the sorted array
2692 * is undefined. If you want equal elements to keep their order (i.e.
2693 * you want a stable sort) you can write a comparison function that,
2694 * if two elements would otherwise compare equal, compares them by
2698 g_byte_array_sort (GByteArray *array,
2699 GCompareFunc compare_func)
2701 g_array_sort ((GArray *)array, compare_func);
2705 * g_byte_array_sort_with_data:
2706 * @array: a #GByteArray
2707 * @compare_func: comparison function
2708 * @user_data: data to pass to @compare_func
2710 * Like g_byte_array_sort(), but the comparison function takes an extra
2711 * user data argument.
2714 g_byte_array_sort_with_data (GByteArray *array,
2715 GCompareDataFunc compare_func,
2718 g_array_sort_with_data ((GArray *)array, compare_func, user_data);