gkdbus: Fix underflow and unreachable code bug
[platform/upstream/glib.git] / glib / garray.c
1 /* GLIB - Library of useful routines for C programming
2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
3  *
4  * SPDX-License-Identifier: LGPL-2.1-or-later
5  *
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.
10  *
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.
15  *
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/>.
18  */
19
20 /*
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/. 
25  */
26
27 /* 
28  * MT safe
29  */
30
31 #include "config.h"
32
33 #include <string.h>
34 #include <stdlib.h>
35
36 #include "garray.h"
37
38 #include "galloca.h"
39 #include "gbytes.h"
40 #include "ghash.h"
41 #include "gslice.h"
42 #include "gmem.h"
43 #include "gtestutils.h"
44 #include "gthread.h"
45 #include "gmessages.h"
46 #include "gqsort.h"
47 #include "grefcount.h"
48 #include "gutilsprivate.h"
49
50 /**
51  * SECTION:arrays
52  * @title: Arrays
53  * @short_description: arrays of arbitrary elements which grow
54  *     automatically as elements are added
55  *
56  * Arrays are similar to standard C arrays, except that they grow
57  * automatically as elements are added.
58  *
59  * Array elements can be of any size (though all elements of one array
60  * are the same size), and the array can be automatically cleared to
61  * '0's and zero-terminated.
62  *
63  * To create a new array use g_array_new().
64  *
65  * To add elements to an array with a cost of O(n) at worst, use
66  * g_array_append_val(), g_array_append_vals(), g_array_prepend_val(),
67  * g_array_prepend_vals(), g_array_insert_val() and g_array_insert_vals().
68  *
69  * To access an element of an array in O(1) (to read it or to write it),
70  * use g_array_index().
71  *
72  * To set the size of an array, use g_array_set_size().
73  *
74  * To free an array, use g_array_unref() or g_array_free().
75  *
76  * All the sort functions are internally calling a quick-sort (or similar)
77  * function with an average cost of O(n log(n)) and a worst case
78  * cost of O(n^2).
79  *
80  * Here is an example that stores integers in a #GArray:
81  * |[<!-- language="C" -->
82  *   GArray *garray;
83  *   gint i;
84  *   // We create a new array to store gint values.
85  *   // We don't want it zero-terminated or cleared to 0's.
86  *   garray = g_array_new (FALSE, FALSE, sizeof (gint));
87  *   for (i = 0; i < 10000; i++)
88  *     g_array_append_val (garray, i);
89  *   for (i = 0; i < 10000; i++)
90  *     if (g_array_index (garray, gint, i) != i)
91  *       g_print ("ERROR: got %d instead of %d\n",
92  *                g_array_index (garray, gint, i), i);
93  *   g_array_free (garray, TRUE);
94  * ]|
95  */
96
97 #define MIN_ARRAY_SIZE  16
98
99 typedef struct _GRealArray  GRealArray;
100
101 /**
102  * GArray:
103  * @data: a pointer to the element data. The data may be moved as
104  *     elements are added to the #GArray.
105  * @len: the number of elements in the #GArray not including the
106  *     possible terminating zero element.
107  *
108  * Contains the public fields of a GArray.
109  */
110 struct _GRealArray
111 {
112   guint8 *data;
113   guint   len;
114   guint   elt_capacity;
115   guint   elt_size;
116   guint   zero_terminated : 1;
117   guint   clear : 1;
118   gatomicrefcount ref_count;
119   GDestroyNotify clear_func;
120 };
121
122 /**
123  * g_array_index:
124  * @a: a #GArray
125  * @t: the type of the elements
126  * @i: the index of the element to return
127  *
128  * Returns the element of a #GArray at the given index. The return
129  * value is cast to the given type. This is the main way to read or write an
130  * element in a #GArray.
131  *
132  * Writing an element is typically done by reference, as in the following
133  * example. This example gets a pointer to an element in a #GArray, and then
134  * writes to a field in it:
135  * |[<!-- language="C" -->
136  *   EDayViewEvent *event;
137  *   // This gets a pointer to the 4th element in the array of
138  *   // EDayViewEvent structs.
139  *   event = &g_array_index (events, EDayViewEvent, 3);
140  *   event->start_time = g_get_current_time ();
141  * ]|
142  *
143  * This example reads from and writes to an array of integers:
144  * |[<!-- language="C" -->
145  *   g_autoptr(GArray) int_array = g_array_new (FALSE, FALSE, sizeof (guint));
146  *   for (guint i = 0; i < 10; i++)
147  *     g_array_append_val (int_array, i);
148  *
149  *   guint *my_int = &g_array_index (int_array, guint, 1);
150  *   g_print ("Int at index 1 is %u; decrementing it\n", *my_int);
151  *   *my_int = *my_int - 1;
152  * ]|
153  *
154  * Returns: the element of the #GArray at the index given by @i
155  */
156
157 #define g_array_elt_len(array,i) ((gsize)(array)->elt_size * (i))
158 #define g_array_elt_pos(array,i) ((array)->data + g_array_elt_len((array),(i)))
159 #define g_array_elt_zero(array, pos, len)                               \
160   (memset (g_array_elt_pos ((array), pos), 0,  g_array_elt_len ((array), len)))
161 #define g_array_zero_terminate(array) G_STMT_START{                     \
162   if ((array)->zero_terminated)                                         \
163     g_array_elt_zero ((array), (array)->len, 1);                        \
164 }G_STMT_END
165
166 static void  g_array_maybe_expand (GRealArray *array,
167                                    guint       len);
168
169 /**
170  * g_array_new:
171  * @zero_terminated: %TRUE if the array should have an extra element at
172  *     the end which is set to 0
173  * @clear_: %TRUE if #GArray elements should be automatically cleared
174  *     to 0 when they are allocated
175  * @element_size: the size of each element in bytes
176  *
177  * Creates a new #GArray with a reference count of 1.
178  *
179  * Returns: the new #GArray
180  */
181 GArray*
182 g_array_new (gboolean zero_terminated,
183              gboolean clear,
184              guint    elt_size)
185 {
186   g_return_val_if_fail (elt_size > 0, NULL);
187 #if (UINT_WIDTH / 8) >= GLIB_SIZEOF_SIZE_T
188   g_return_val_if_fail (elt_size <= G_MAXSIZE / 2 - 1, NULL);
189 #endif
190
191   return g_array_sized_new (zero_terminated, clear, elt_size, 0);
192 }
193
194 /**
195  * g_array_new_take: (skip)
196  * @data: (array length=len) (transfer full) (nullable): an array of
197  *   elements of @element_size, or %NULL for an empty array
198  * @len: the number of elements in @data
199  * @clear: %TRUE if #GArray elements should be automatically cleared
200  *     to 0 when they are allocated
201  * @element_size: the size of each element in bytes
202  *
203  * Creates a new #GArray with @data as array data, @len as length and a
204  * reference count of 1.
205  *
206  * This avoids having to copy the data manually, when it can just be
207  * inherited.
208  * After this call, @data belongs to the #GArray and may no longer be
209  * modified by the caller. The memory of @data has to be dynamically
210  * allocated and will eventually be freed with g_free().
211  *
212  * In case the elements need to be cleared when the array is freed, use
213  * g_array_set_clear_func() to set a #GDestroyNotify function to perform
214  * such task.
215  *
216  * Do not use it if @len or @element_size are greater than %G_MAXUINT.
217  * #GArray stores the length of its data in #guint, which may be shorter
218  * than #gsize.
219  *
220  * Returns: (transfer full): A new #GArray
221  *
222  * Since: 2.76
223  */
224 GArray *
225 g_array_new_take (gpointer  data,
226                   gsize     len,
227                   gboolean  clear,
228                   gsize     element_size)
229 {
230   GRealArray *rarray;
231   GArray *array;
232
233   g_return_val_if_fail (data != NULL || len == 0, NULL);
234   g_return_val_if_fail (len <= G_MAXUINT, NULL);
235   g_return_val_if_fail (element_size <= G_MAXUINT, NULL);
236
237   array = g_array_sized_new (FALSE, clear, element_size, 0);
238   rarray = (GRealArray *) array;
239   rarray->data = (guint8 *) g_steal_pointer (&data);
240   rarray->len = len;
241   rarray->elt_capacity = len;
242
243   return array;
244 }
245
246 /**
247  * g_array_new_take_zero_terminated: (skip)
248  * @data: (array zero-terminated=1): an array of elements of @element_size
249  * @clear: %TRUE if #GArray elements should be automatically cleared
250  *     to 0 when they are allocated
251  * @element_size: the size of each element in bytes
252  *
253  * Creates a new #GArray with @data as array data, computing the length of it
254  * and setting the reference count to 1.
255  *
256  * This avoids having to copy the data manually, when it can just be
257  * inherited.
258  * After this call, @data belongs to the #GArray and may no longer be
259  * modified by the caller. The memory of @data has to be dynamically
260  * allocated and will eventually be freed with g_free().
261  *
262  * The length is calculated by iterating through @data until the first %NULL
263  * element is found.
264  *
265  * In case the elements need to be cleared when the array is freed, use
266  * g_array_set_clear_func() to set a #GDestroyNotify function to perform
267  * such task.
268  *
269  * Do not use it if @data length or @element_size are greater than %G_MAXUINT.
270  * #GArray stores the length of its data in #guint, which may be shorter
271  * than #gsize.
272  *
273  * Returns: (transfer full): A new #GArray
274  *
275  * Since: 2.76
276  */
277 GArray *
278 g_array_new_take_zero_terminated (gpointer  data,
279                                   gboolean  clear,
280                                   gsize     element_size)
281 {
282   GArray *array;
283   gsize len = 0;
284
285   g_return_val_if_fail (element_size <= G_MAXUINT, NULL);
286
287   if (data != NULL)
288     {
289       guint8 *array_data = data;
290
291       for (gsize i = 0; ; ++i)
292         {
293           const guint8 *element_start = array_data + (i * element_size);
294
295           if (*element_start == 0 &&
296               memcmp (element_start, element_start + 1, element_size - 1) == 0)
297             break;
298
299           len += 1;
300         }
301     }
302
303   g_return_val_if_fail (len <= G_MAXUINT, NULL);
304
305   array = g_array_new_take (data, len, clear, element_size);
306   ((GRealArray *)array)->zero_terminated = TRUE;
307
308   return array;
309 }
310
311 /**
312  * g_array_steal:
313  * @array: a #GArray.
314  * @len: (optional) (out): pointer to retrieve the number of
315  *    elements of the original array
316  *
317  * Frees the data in the array and resets the size to zero, while
318  * the underlying array is preserved for use elsewhere and returned
319  * to the caller.
320  *
321  * If the array was created with the @zero_terminate property
322  * set to %TRUE, the returned data is zero terminated too.
323  *
324  * If array elements contain dynamically-allocated memory,
325  * the array elements should also be freed by the caller.
326  *
327  * A short example of use:
328  * |[<!-- language="C" -->
329  * ...
330  * gpointer data;
331  * gsize data_len;
332  * data = g_array_steal (some_array, &data_len);
333  * ...
334  * ]|
335
336  * Returns: (transfer full): the element data, which should be
337  *     freed using g_free().
338  *
339  * Since: 2.64
340  */
341 gpointer
342 g_array_steal (GArray *array,
343                gsize *len)
344 {
345   GRealArray *rarray;
346   gpointer segment;
347
348   g_return_val_if_fail (array != NULL, NULL);
349
350   rarray = (GRealArray *) array;
351   segment = (gpointer) rarray->data;
352
353   if (len != NULL)
354     *len = rarray->len;
355
356   rarray->data  = NULL;
357   rarray->len   = 0;
358   rarray->elt_capacity = 0;
359   return segment;
360 }
361
362 /**
363  * g_array_sized_new:
364  * @zero_terminated: %TRUE if the array should have an extra element at
365  *     the end with all bits cleared
366  * @clear_: %TRUE if all bits in the array should be cleared to 0 on
367  *     allocation
368  * @element_size: size of each element in the array
369  * @reserved_size: number of elements preallocated
370  *
371  * Creates a new #GArray with @reserved_size elements preallocated and
372  * a reference count of 1. This avoids frequent reallocation, if you
373  * are going to add many elements to the array. Note however that the
374  * size of the array is still 0.
375  *
376  * Returns: the new #GArray
377  */
378 GArray*
379 g_array_sized_new (gboolean zero_terminated,
380                    gboolean clear,
381                    guint    elt_size,
382                    guint    reserved_size)
383 {
384   GRealArray *array;
385   
386   g_return_val_if_fail (elt_size > 0, NULL);
387 #if (UINT_WIDTH / 8) >= GLIB_SIZEOF_SIZE_T
388   g_return_val_if_fail (elt_size <= G_MAXSIZE / 2 - 1, NULL);
389 #endif
390
391   array = g_slice_new (GRealArray);
392
393   array->data            = NULL;
394   array->len             = 0;
395   array->elt_capacity = 0;
396   array->zero_terminated = (zero_terminated ? 1 : 0);
397   array->clear           = (clear ? 1 : 0);
398   array->elt_size        = elt_size;
399   array->clear_func      = NULL;
400
401   g_atomic_ref_count_init (&array->ref_count);
402
403   if (array->zero_terminated || reserved_size != 0)
404     {
405       g_array_maybe_expand (array, reserved_size);
406       g_assert (array->data != NULL);
407       g_array_zero_terminate (array);
408     }
409
410   return (GArray*) array;
411 }
412
413 /**
414  * g_array_set_clear_func:
415  * @array: A #GArray
416  * @clear_func: a function to clear an element of @array
417  *
418  * Sets a function to clear an element of @array.
419  *
420  * The @clear_func will be called when an element in the array
421  * data segment is removed and when the array is freed and data
422  * segment is deallocated as well. @clear_func will be passed a
423  * pointer to the element to clear, rather than the element itself.
424  *
425  * Note that in contrast with other uses of #GDestroyNotify
426  * functions, @clear_func is expected to clear the contents of
427  * the array element it is given, but not free the element itself.
428  *
429  * |[<!-- language="C" -->
430  * typedef struct
431  * {
432  *   gchar *str;
433  *   GObject *obj;
434  * } ArrayElement;
435  *
436  * static void
437  * array_element_clear (ArrayElement *element)
438  * {
439  *   g_clear_pointer (&element->str, g_free);
440  *   g_clear_object (&element->obj);
441  * }
442  *
443  * // main code
444  * GArray *garray = g_array_new (FALSE, FALSE, sizeof (ArrayElement));
445  * g_array_set_clear_func (garray, (GDestroyNotify) array_element_clear);
446  * // assign data to the structure
447  * g_array_free (garray, TRUE);
448  * ]|
449  *
450  * Since: 2.32
451  */
452 void
453 g_array_set_clear_func (GArray         *array,
454                         GDestroyNotify  clear_func)
455 {
456   GRealArray *rarray = (GRealArray *) array;
457
458   g_return_if_fail (array != NULL);
459
460   rarray->clear_func = clear_func;
461 }
462
463 /**
464  * g_array_ref:
465  * @array: A #GArray
466  *
467  * Atomically increments the reference count of @array by one.
468  * This function is thread-safe and may be called from any thread.
469  *
470  * Returns: The passed in #GArray
471  *
472  * Since: 2.22
473  */
474 GArray *
475 g_array_ref (GArray *array)
476 {
477   GRealArray *rarray = (GRealArray*) array;
478   g_return_val_if_fail (array, NULL);
479
480   g_atomic_ref_count_inc (&rarray->ref_count);
481
482   return array;
483 }
484
485 typedef enum
486 {
487   FREE_SEGMENT = 1 << 0,
488   PRESERVE_WRAPPER = 1 << 1
489 } ArrayFreeFlags;
490
491 static gchar *array_free (GRealArray *, ArrayFreeFlags);
492
493 /**
494  * g_array_unref:
495  * @array: A #GArray
496  *
497  * Atomically decrements the reference count of @array by one. If the
498  * reference count drops to 0, all memory allocated by the array is
499  * released. This function is thread-safe and may be called from any
500  * thread.
501  *
502  * Since: 2.22
503  */
504 void
505 g_array_unref (GArray *array)
506 {
507   GRealArray *rarray = (GRealArray*) array;
508   g_return_if_fail (array);
509
510   if (g_atomic_ref_count_dec (&rarray->ref_count))
511     array_free (rarray, FREE_SEGMENT);
512 }
513
514 /**
515  * g_array_get_element_size:
516  * @array: A #GArray
517  *
518  * Gets the size of the elements in @array.
519  *
520  * Returns: Size of each element, in bytes
521  *
522  * Since: 2.22
523  */
524 guint
525 g_array_get_element_size (GArray *array)
526 {
527   GRealArray *rarray = (GRealArray*) array;
528
529   g_return_val_if_fail (array, 0);
530
531   return rarray->elt_size;
532 }
533
534 /**
535  * g_array_free:
536  * @array: a #GArray
537  * @free_segment: if %TRUE the actual element data is freed as well
538  *
539  * Frees the memory allocated for the #GArray. If @free_segment is
540  * %TRUE it frees the memory block holding the elements as well. Pass
541  * %FALSE if you want to free the #GArray wrapper but preserve the
542  * underlying array for use elsewhere. If the reference count of
543  * @array is greater than one, the #GArray wrapper is preserved but
544  * the size of  @array will be set to zero.
545  *
546  * If array contents point to dynamically-allocated memory, they should
547  * be freed separately if @free_seg is %TRUE and no @clear_func
548  * function has been set for @array.
549  *
550  * This function is not thread-safe. If using a #GArray from multiple
551  * threads, use only the atomic g_array_ref() and g_array_unref()
552  * functions.
553  *
554  * Returns: the element data if @free_segment is %FALSE, otherwise
555  *     %NULL. The element data should be freed using g_free().
556  */
557 gchar*
558 g_array_free (GArray   *farray,
559               gboolean  free_segment)
560 {
561   GRealArray *array = (GRealArray*) farray;
562   ArrayFreeFlags flags;
563
564   g_return_val_if_fail (array, NULL);
565
566   flags = (free_segment ? FREE_SEGMENT : 0);
567
568   /* if others are holding a reference, preserve the wrapper but do free/return the data */
569   if (!g_atomic_ref_count_dec (&array->ref_count))
570     flags |= PRESERVE_WRAPPER;
571
572   return array_free (array, flags);
573 }
574
575 static gchar *
576 array_free (GRealArray     *array,
577             ArrayFreeFlags  flags)
578 {
579   gchar *segment;
580
581   if (flags & FREE_SEGMENT)
582     {
583       if (array->clear_func != NULL)
584         {
585           guint i;
586
587           for (i = 0; i < array->len; i++)
588             array->clear_func (g_array_elt_pos (array, i));
589         }
590
591       g_free (array->data);
592       segment = NULL;
593     }
594   else
595     segment = (gchar*) array->data;
596
597   if (flags & PRESERVE_WRAPPER)
598     {
599       array->data            = NULL;
600       array->len             = 0;
601       array->elt_capacity = 0;
602     }
603   else
604     {
605       g_slice_free1 (sizeof (GRealArray), array);
606     }
607
608   return segment;
609 }
610
611 /**
612  * g_array_append_vals:
613  * @array: a #GArray
614  * @data: (not nullable): a pointer to the elements to append to the end of the array
615  * @len: the number of elements to append
616  *
617  * Adds @len elements onto the end of the array.
618  *
619  * Returns: the #GArray
620  */
621 /**
622  * g_array_append_val:
623  * @a: a #GArray
624  * @v: the value to append to the #GArray
625  *
626  * Adds the value on to the end of the array. The array will grow in
627  * size automatically if necessary.
628  *
629  * g_array_append_val() is a macro which uses a reference to the value
630  * parameter @v. This means that you cannot use it with literal values
631  * such as "27". You must use variables.
632  *
633  * Returns: the #GArray
634  */
635 GArray*
636 g_array_append_vals (GArray       *farray,
637                      gconstpointer data,
638                      guint         len)
639 {
640   GRealArray *array = (GRealArray*) farray;
641
642   g_return_val_if_fail (array, NULL);
643
644   if (len == 0)
645     return farray;
646
647   g_array_maybe_expand (array, len);
648
649   memcpy (g_array_elt_pos (array, array->len), data, 
650           g_array_elt_len (array, len));
651
652   array->len += len;
653
654   g_array_zero_terminate (array);
655
656   return farray;
657 }
658
659 /**
660  * g_array_prepend_vals:
661  * @array: a #GArray
662  * @data: (nullable): a pointer to the elements to prepend to the start of the array
663  * @len: the number of elements to prepend, which may be zero
664  *
665  * Adds @len elements onto the start of the array.
666  *
667  * @data may be %NULL if (and only if) @len is zero. If @len is zero, this
668  * function is a no-op.
669  *
670  * This operation is slower than g_array_append_vals() since the
671  * existing elements in the array have to be moved to make space for
672  * the new elements.
673  *
674  * Returns: the #GArray
675  */
676 /**
677  * g_array_prepend_val:
678  * @a: a #GArray
679  * @v: the value to prepend to the #GArray
680  *
681  * Adds the value on to the start of the array. The array will grow in
682  * size automatically if necessary.
683  *
684  * This operation is slower than g_array_append_val() since the
685  * existing elements in the array have to be moved to make space for
686  * the new element.
687  *
688  * g_array_prepend_val() is a macro which uses a reference to the value
689  * parameter @v. This means that you cannot use it with literal values
690  * such as "27". You must use variables.
691  *
692  * Returns: the #GArray
693  */
694 GArray*
695 g_array_prepend_vals (GArray        *farray,
696                       gconstpointer  data,
697                       guint          len)
698 {
699   GRealArray *array = (GRealArray*) farray;
700
701   g_return_val_if_fail (array, NULL);
702
703   if (len == 0)
704     return farray;
705
706   g_array_maybe_expand (array, len);
707
708   memmove (g_array_elt_pos (array, len), g_array_elt_pos (array, 0),
709            g_array_elt_len (array, array->len));
710
711   memcpy (g_array_elt_pos (array, 0), data, g_array_elt_len (array, len));
712
713   array->len += len;
714
715   g_array_zero_terminate (array);
716
717   return farray;
718 }
719
720 /**
721  * g_array_insert_vals:
722  * @array: a #GArray
723  * @index_: the index to place the elements at
724  * @data: (nullable): a pointer to the elements to insert
725  * @len: the number of elements to insert
726  *
727  * Inserts @len elements into a #GArray at the given index.
728  *
729  * If @index_ is greater than the array’s current length, the array is expanded.
730  * The elements between the old end of the array and the newly inserted elements
731  * will be initialised to zero if the array was configured to clear elements;
732  * otherwise their values will be undefined.
733  *
734  * If @index_ is less than the array’s current length, new entries will be
735  * inserted into the array, and the existing entries above @index_ will be moved
736  * upwards.
737  *
738  * @data may be %NULL if (and only if) @len is zero. If @len is zero, this
739  * function is a no-op.
740  *
741  * Returns: the #GArray
742  */
743 /**
744  * g_array_insert_val:
745  * @a: a #GArray
746  * @i: the index to place the element at
747  * @v: the value to insert into the array
748  *
749  * Inserts an element into an array at the given index.
750  *
751  * g_array_insert_val() is a macro which uses a reference to the value
752  * parameter @v. This means that you cannot use it with literal values
753  * such as "27". You must use variables.
754  *
755  * Returns: the #GArray
756  */
757 GArray*
758 g_array_insert_vals (GArray        *farray,
759                      guint          index_,
760                      gconstpointer  data,
761                      guint          len)
762 {
763   GRealArray *array = (GRealArray*) farray;
764
765   g_return_val_if_fail (array, NULL);
766
767   if (len == 0)
768     return farray;
769
770   /* Is the index off the end of the array, and hence do we need to over-allocate
771    * and clear some elements? */
772   if (index_ >= array->len)
773     {
774       g_array_maybe_expand (array, index_ - array->len + len);
775       return g_array_append_vals (g_array_set_size (farray, index_), data, len);
776     }
777
778   g_array_maybe_expand (array, len);
779
780   memmove (g_array_elt_pos (array, len + index_),
781            g_array_elt_pos (array, index_),
782            g_array_elt_len (array, array->len - index_));
783
784   memcpy (g_array_elt_pos (array, index_), data, g_array_elt_len (array, len));
785
786   array->len += len;
787
788   g_array_zero_terminate (array);
789
790   return farray;
791 }
792
793 /**
794  * g_array_set_size:
795  * @array: a #GArray
796  * @length: the new size of the #GArray
797  *
798  * Sets the size of the array, expanding it if necessary. If the array
799  * was created with @clear_ set to %TRUE, the new elements are set to 0.
800  *
801  * Returns: the #GArray
802  */
803 GArray*
804 g_array_set_size (GArray *farray,
805                   guint   length)
806 {
807   GRealArray *array = (GRealArray*) farray;
808
809   g_return_val_if_fail (array, NULL);
810
811   if (length > array->len)
812     {
813       g_array_maybe_expand (array, length - array->len);
814       
815       if (array->clear)
816         g_array_elt_zero (array, array->len, length - array->len);
817     }
818   else if (length < array->len)
819     g_array_remove_range (farray, length, array->len - length);
820   
821   array->len = length;
822   
823   g_array_zero_terminate (array);
824   
825   return farray;
826 }
827
828 /**
829  * g_array_remove_index:
830  * @array: a #GArray
831  * @index_: the index of the element to remove
832  *
833  * Removes the element at the given index from a #GArray. The following
834  * elements are moved down one place.
835  *
836  * Returns: the #GArray
837  */
838 GArray*
839 g_array_remove_index (GArray *farray,
840                       guint   index_)
841 {
842   GRealArray* array = (GRealArray*) farray;
843
844   g_return_val_if_fail (array, NULL);
845
846   g_return_val_if_fail (index_ < array->len, NULL);
847
848   if (array->clear_func != NULL)
849     array->clear_func (g_array_elt_pos (array, index_));
850
851   if (index_ != array->len - 1)
852     memmove (g_array_elt_pos (array, index_),
853              g_array_elt_pos (array, index_ + 1),
854              g_array_elt_len (array, array->len - index_ - 1));
855
856   array->len -= 1;
857
858   if (G_UNLIKELY (g_mem_gc_friendly))
859     g_array_elt_zero (array, array->len, 1);
860   else
861     g_array_zero_terminate (array);
862
863   return farray;
864 }
865
866 /**
867  * g_array_remove_index_fast:
868  * @array: a @GArray
869  * @index_: the index of the element to remove
870  *
871  * Removes the element at the given index from a #GArray. The last
872  * element in the array is used to fill in the space, so this function
873  * does not preserve the order of the #GArray. But it is faster than
874  * g_array_remove_index().
875  *
876  * Returns: the #GArray
877  */
878 GArray*
879 g_array_remove_index_fast (GArray *farray,
880                            guint   index_)
881 {
882   GRealArray* array = (GRealArray*) farray;
883
884   g_return_val_if_fail (array, NULL);
885
886   g_return_val_if_fail (index_ < array->len, NULL);
887
888   if (array->clear_func != NULL)
889     array->clear_func (g_array_elt_pos (array, index_));
890
891   if (index_ != array->len - 1)
892     memcpy (g_array_elt_pos (array, index_),
893             g_array_elt_pos (array, array->len - 1),
894             g_array_elt_len (array, 1));
895   
896   array->len -= 1;
897
898   if (G_UNLIKELY (g_mem_gc_friendly))
899     g_array_elt_zero (array, array->len, 1);
900   else
901     g_array_zero_terminate (array);
902
903   return farray;
904 }
905
906 /**
907  * g_array_remove_range:
908  * @array: a @GArray
909  * @index_: the index of the first element to remove
910  * @length: the number of elements to remove
911  *
912  * Removes the given number of elements starting at the given index
913  * from a #GArray.  The following elements are moved to close the gap.
914  *
915  * Returns: the #GArray
916  *
917  * Since: 2.4
918  */
919 GArray*
920 g_array_remove_range (GArray *farray,
921                       guint   index_,
922                       guint   length)
923 {
924   GRealArray *array = (GRealArray*) farray;
925
926   g_return_val_if_fail (array, NULL);
927   g_return_val_if_fail (index_ <= array->len, NULL);
928   g_return_val_if_fail (index_ + length <= array->len, NULL);
929
930   if (array->clear_func != NULL)
931     {
932       guint i;
933
934       for (i = 0; i < length; i++)
935         array->clear_func (g_array_elt_pos (array, index_ + i));
936     }
937
938   if (index_ + length != array->len)
939     memmove (g_array_elt_pos (array, index_),
940              g_array_elt_pos (array, index_ + length),
941              (array->len - (index_ + length)) * array->elt_size);
942
943   array->len -= length;
944   if (G_UNLIKELY (g_mem_gc_friendly))
945     g_array_elt_zero (array, array->len, length);
946   else
947     g_array_zero_terminate (array);
948
949   return farray;
950 }
951
952 /**
953  * g_array_sort:
954  * @array: a #GArray
955  * @compare_func: comparison function
956  *
957  * Sorts a #GArray using @compare_func which should be a qsort()-style
958  * comparison function (returns less than zero for first arg is less
959  * than second arg, zero for equal, greater zero if first arg is
960  * greater than second arg).
961  *
962  * This is guaranteed to be a stable sort since version 2.32.
963  */
964 void
965 g_array_sort (GArray       *farray,
966               GCompareFunc  compare_func)
967 {
968   GRealArray *array = (GRealArray*) farray;
969
970   g_return_if_fail (array != NULL);
971
972   /* Don't use qsort as we want a guaranteed stable sort */
973   if (array->len > 0)
974     g_qsort_with_data (array->data,
975                        array->len,
976                        array->elt_size,
977                        (GCompareDataFunc)compare_func,
978                        NULL);
979 }
980
981 /**
982  * g_array_sort_with_data:
983  * @array: a #GArray
984  * @compare_func: comparison function
985  * @user_data: data to pass to @compare_func
986  *
987  * Like g_array_sort(), but the comparison function receives an extra
988  * user data argument.
989  *
990  * This is guaranteed to be a stable sort since version 2.32.
991  *
992  * There used to be a comment here about making the sort stable by
993  * using the addresses of the elements in the comparison function.
994  * This did not actually work, so any such code should be removed.
995  */
996 void
997 g_array_sort_with_data (GArray           *farray,
998                         GCompareDataFunc  compare_func,
999                         gpointer          user_data)
1000 {
1001   GRealArray *array = (GRealArray*) farray;
1002
1003   g_return_if_fail (array != NULL);
1004
1005   if (array->len > 0)
1006     g_qsort_with_data (array->data,
1007                        array->len,
1008                        array->elt_size,
1009                        compare_func,
1010                        user_data);
1011 }
1012
1013 /**
1014  * g_array_binary_search:
1015  * @array: a #GArray.
1016  * @target: a pointer to the item to look up.
1017  * @compare_func: A #GCompareFunc used to locate @target.
1018  * @out_match_index: (optional) (out): return location
1019  *    for the index of the element, if found.
1020  *
1021  * Checks whether @target exists in @array by performing a binary
1022  * search based on the given comparison function @compare_func which
1023  * get pointers to items as arguments. If the element is found, %TRUE
1024  * is returned and the element’s index is returned in @out_match_index
1025  * (if non-%NULL). Otherwise, %FALSE is returned and @out_match_index
1026  * is undefined. If @target exists multiple times in @array, the index
1027  * of the first instance is returned. This search is using a binary
1028  * search, so the @array must absolutely be sorted to return a correct
1029  * result (if not, the function may produce false-negative).
1030  *
1031  * This example defines a comparison function and search an element in a #GArray:
1032  * |[<!-- language="C" -->
1033  * static gint
1034  * cmpint (gconstpointer a, gconstpointer b)
1035  * {
1036  *   const gint *_a = a;
1037  *   const gint *_b = b;
1038  *
1039  *   return *_a - *_b;
1040  * }
1041  * ...
1042  * gint i = 424242;
1043  * guint matched_index;
1044  * gboolean result = g_array_binary_search (garray, &i, cmpint, &matched_index);
1045  * ...
1046  * ]|
1047  *
1048  * Returns: %TRUE if @target is one of the elements of @array, %FALSE otherwise.
1049  *
1050  * Since: 2.62
1051  */
1052 gboolean
1053 g_array_binary_search (GArray        *array,
1054                        gconstpointer  target,
1055                        GCompareFunc   compare_func,
1056                        guint         *out_match_index)
1057 {
1058   gboolean result = FALSE;
1059   GRealArray *_array = (GRealArray *) array;
1060   guint left, middle = 0, right;
1061   gint val;
1062
1063   g_return_val_if_fail (_array != NULL, FALSE);
1064   g_return_val_if_fail (compare_func != NULL, FALSE);
1065
1066   if (G_LIKELY(_array->len))
1067     {
1068       left = 0;
1069       right = _array->len - 1;
1070
1071       while (left <= right)
1072         {
1073           middle = left + (right - left) / 2;
1074
1075           val = compare_func (_array->data + (_array->elt_size * middle), target);
1076           if (val == 0)
1077             {
1078               result = TRUE;
1079               break;
1080             }
1081           else if (val < 0)
1082             left = middle + 1;
1083           else if (/* val > 0 && */ middle > 0)
1084             right = middle - 1;
1085           else
1086             break;  /* element not found */
1087         }
1088     }
1089
1090   if (result && out_match_index != NULL)
1091     *out_match_index = middle;
1092
1093   return result;
1094 }
1095
1096 static void
1097 g_array_maybe_expand (GRealArray *array,
1098                       guint       len)
1099 {
1100   guint max_len, want_len;
1101  
1102   /* The maximum array length is derived from following constraints:
1103    * - The number of bytes must fit into a gsize / 2.
1104    * - The number of elements must fit into guint.
1105    * - zero terminated arrays must leave space for the terminating element
1106    */
1107   max_len = MIN (G_MAXSIZE / 2 / array->elt_size, G_MAXUINT) - array->zero_terminated;
1108
1109   /* Detect potential overflow */
1110   if G_UNLIKELY ((max_len - array->len) < len)
1111     g_error ("adding %u to array would overflow", len);
1112
1113   want_len = array->len + len + array->zero_terminated;
1114   if (want_len > array->elt_capacity)
1115     {
1116       gsize want_alloc = g_nearest_pow (g_array_elt_len (array, want_len));
1117       want_alloc = MAX (want_alloc, MIN_ARRAY_SIZE);
1118
1119       array->data = g_realloc (array->data, want_alloc);
1120
1121       if (G_UNLIKELY (g_mem_gc_friendly))
1122         memset (g_array_elt_pos (array, array->elt_capacity), 0,
1123                 g_array_elt_len (array, want_len - array->elt_capacity));
1124
1125       array->elt_capacity = MIN (want_alloc / array->elt_size, G_MAXUINT);
1126     }
1127 }
1128
1129 /**
1130  * SECTION:arrays_pointer
1131  * @title: Pointer Arrays
1132  * @short_description: arrays of pointers to any type of data, which
1133  *     grow automatically as new elements are added
1134  *
1135  * Pointer Arrays are similar to Arrays but are used only for storing
1136  * pointers.
1137  *
1138  * If you remove elements from the array, elements at the end of the
1139  * array are moved into the space previously occupied by the removed
1140  * element. This means that you should not rely on the index of particular
1141  * elements remaining the same. You should also be careful when deleting
1142  * elements while iterating over the array.
1143  *
1144  * To create a pointer array, use g_ptr_array_new().
1145  *
1146  * To add elements to a pointer array, use g_ptr_array_add().
1147  *
1148  * To remove elements from a pointer array, use g_ptr_array_remove(),
1149  * g_ptr_array_remove_index() or g_ptr_array_remove_index_fast().
1150  *
1151  * To access an element of a pointer array, use g_ptr_array_index().
1152  *
1153  * To set the size of a pointer array, use g_ptr_array_set_size().
1154  *
1155  * To free a pointer array, use g_ptr_array_free().
1156  *
1157  * An example using a #GPtrArray:
1158  * |[<!-- language="C" -->
1159  *   GPtrArray *array;
1160  *   gchar *string1 = "one";
1161  *   gchar *string2 = "two";
1162  *   gchar *string3 = "three";
1163  *
1164  *   array = g_ptr_array_new ();
1165  *   g_ptr_array_add (array, (gpointer) string1);
1166  *   g_ptr_array_add (array, (gpointer) string2);
1167  *   g_ptr_array_add (array, (gpointer) string3);
1168  *
1169  *   if (g_ptr_array_index (array, 0) != (gpointer) string1)
1170  *     g_print ("ERROR: got %p instead of %p\n",
1171  *              g_ptr_array_index (array, 0), string1);
1172  *
1173  *   g_ptr_array_free (array, TRUE);
1174  * ]|
1175  */
1176
1177 typedef struct _GRealPtrArray  GRealPtrArray;
1178
1179 /**
1180  * GPtrArray:
1181  * @pdata: points to the array of pointers, which may be moved when the
1182  *     array grows
1183  * @len: number of pointers in the array
1184  *
1185  * Contains the public fields of a pointer array.
1186  */
1187 struct _GRealPtrArray
1188 {
1189   gpointer       *pdata;
1190   guint           len;
1191   guint           alloc;
1192   gatomicrefcount ref_count;
1193   guint8          null_terminated : 1; /* always either 0 or 1, so it can be added to array lengths */
1194   GDestroyNotify  element_free_func;
1195 };
1196
1197 /**
1198  * g_ptr_array_index:
1199  * @array: a #GPtrArray
1200  * @index_: the index of the pointer to return
1201  *
1202  * Returns the pointer at the given index of the pointer array.
1203  *
1204  * This does not perform bounds checking on the given @index_,
1205  * so you are responsible for checking it against the array length.
1206  *
1207  * Returns: the pointer at the given index
1208  */
1209
1210 static void g_ptr_array_maybe_expand (GRealPtrArray *array,
1211                                       guint          len);
1212
1213 static void
1214 ptr_array_maybe_null_terminate (GRealPtrArray *rarray)
1215 {
1216   if (G_UNLIKELY (rarray->null_terminated))
1217     rarray->pdata[rarray->len] = NULL;
1218 }
1219
1220 static GPtrArray *
1221 ptr_array_new (guint reserved_size,
1222                GDestroyNotify element_free_func,
1223                gboolean null_terminated)
1224 {
1225   GRealPtrArray *array;
1226
1227   array = g_slice_new (GRealPtrArray);
1228
1229   array->pdata = NULL;
1230   array->len = 0;
1231   array->alloc = 0;
1232   array->null_terminated = null_terminated ? 1 : 0;
1233   array->element_free_func = element_free_func;
1234
1235   g_atomic_ref_count_init (&array->ref_count);
1236
1237   if (reserved_size != 0)
1238     {
1239       if (G_LIKELY (reserved_size < G_MAXUINT) &&
1240           null_terminated)
1241         reserved_size++;
1242
1243       g_ptr_array_maybe_expand (array, reserved_size);
1244       g_assert (array->pdata != NULL);
1245
1246       if (null_terminated)
1247         {
1248           /* don't use ptr_array_maybe_null_terminate(). It helps the compiler
1249            * to see when @null_terminated is false and thereby inline
1250            * ptr_array_new() and possibly remove the code entirely. */
1251           array->pdata[0] = NULL;
1252         }
1253     }
1254
1255   return (GPtrArray *) array;
1256 }
1257
1258 /**
1259  * g_ptr_array_new:
1260  *
1261  * Creates a new #GPtrArray with a reference count of 1.
1262  *
1263  * Returns: the new #GPtrArray
1264  */
1265 GPtrArray*
1266 g_ptr_array_new (void)
1267 {
1268   return ptr_array_new (0, NULL, FALSE);
1269 }
1270
1271 /**
1272  * g_ptr_array_new_take: (skip)
1273  * @data: (array length=len) (transfer full) (nullable): an array of pointers,
1274  *    or %NULL for an empty array
1275  * @len: the number of pointers in @data
1276  * @element_free_func: (nullable): A function to free elements on @array
1277  *   destruction or %NULL
1278  *
1279  * Creates a new #GPtrArray with @data as pointers, @len as length and a
1280  * reference count of 1.
1281  *
1282  * This avoids having to copy such data manually.
1283  * After this call, @data belongs to the #GPtrArray and may no longer be
1284  * modified by the caller. The memory of @data has to be dynamically
1285  * allocated and will eventually be freed with g_free().
1286  *
1287  * It also sets @element_free_func for freeing each element when the array is
1288  * destroyed either via g_ptr_array_unref(), when g_ptr_array_free() is called
1289  * with @free_segment set to %TRUE or when removing elements.
1290  *
1291  * Do not use it if @len is greater than %G_MAXUINT. #GPtrArray
1292  * stores the length of its data in #guint, which may be shorter than
1293  * #gsize.
1294  *
1295  * Returns: (transfer full): A new #GPtrArray
1296  *
1297  * Since: 2.76
1298  */
1299 GPtrArray *
1300 g_ptr_array_new_take (gpointer       *data,
1301                       gsize           len,
1302                       GDestroyNotify  element_free_func)
1303 {
1304   GPtrArray *array;
1305   GRealPtrArray *rarray;
1306
1307   g_return_val_if_fail (data != NULL || len == 0, NULL);
1308   g_return_val_if_fail (len <= G_MAXUINT, NULL);
1309
1310   array = ptr_array_new (0, element_free_func, FALSE);
1311   rarray = (GRealPtrArray *)array;
1312
1313   rarray->pdata = g_steal_pointer (&data);
1314   rarray->len = len;
1315   rarray->alloc = len;
1316
1317   return array;
1318 }
1319
1320 /**
1321  * g_ptr_array_new_take_null_terminated: (skip)
1322  * @data: (array zero-terminated=1) (transfer full) (nullable): an array
1323  *  of pointers, %NULL terminated, or %NULL for an empty array
1324  * @element_free_func: (nullable): a function to free elements on @array
1325  *   destruction or %NULL
1326  *
1327  * Creates a new #GPtrArray with @data as pointers, computing the length of it
1328  * and setting the reference count to 1.
1329  *
1330  * This avoids having to copy such data manually.
1331  * After this call, @data belongs to the #GPtrArray and may no longer be
1332  * modified by the caller. The memory of @data has to be dynamically
1333  * allocated and will eventually be freed with g_free().
1334  *
1335  * The length is calculated by iterating through @data until the first %NULL
1336  * element is found.
1337  *
1338  * It also sets @element_free_func for freeing each element when the array is
1339  * destroyed either via g_ptr_array_unref(), when g_ptr_array_free() is called
1340  * with @free_segment set to %TRUE or when removing elements.
1341  *
1342  * Do not use it if the @data length is greater than %G_MAXUINT. #GPtrArray
1343  * stores the length of its data in #guint, which may be shorter than
1344  * #gsize.
1345  *
1346  * Returns: (transfer full): A new #GPtrArray
1347  *
1348  * Since: 2.76
1349  */
1350 GPtrArray *
1351 g_ptr_array_new_take_null_terminated (gpointer       *data,
1352                                       GDestroyNotify  element_free_func)
1353 {
1354   GPtrArray *array;
1355   gsize len = 0;
1356
1357   if (data != NULL)
1358     {
1359       for (gsize i = 0; data[i] != NULL; ++i)
1360         len += 1;
1361     }
1362
1363   g_return_val_if_fail (len <= G_MAXUINT, NULL);
1364
1365   array = g_ptr_array_new_take (g_steal_pointer (&data), len, element_free_func);
1366   ((GRealPtrArray *)array)->null_terminated = TRUE;
1367
1368   return array;
1369 }
1370
1371 static GPtrArray *
1372 ptr_array_new_from_array (gpointer       *data,
1373                           gsize           len,
1374                           GCopyFunc       copy_func,
1375                           gpointer        copy_func_user_data,
1376                           GDestroyNotify  element_free_func,
1377                           gboolean        null_terminated)
1378 {
1379   GPtrArray *array;
1380   GRealPtrArray *rarray;
1381
1382   g_assert (data != NULL || len == 0);
1383   g_assert (len <= G_MAXUINT);
1384
1385   array = ptr_array_new (len, element_free_func, null_terminated);
1386   rarray = (GRealPtrArray *)array;
1387
1388   if (copy_func != NULL)
1389     {
1390       for (gsize i = 0; i < len; i++)
1391         rarray->pdata[i] = copy_func (data[i], copy_func_user_data);
1392     }
1393   else if (len != 0)
1394     {
1395       memcpy (rarray->pdata, data, len * sizeof (gpointer));
1396     }
1397
1398   if (null_terminated && rarray->pdata != NULL)
1399     rarray->pdata[len] = NULL;
1400
1401   rarray->len = len;
1402
1403   return array;
1404 }
1405
1406 /**
1407  * g_ptr_array_new_from_array: (skip)
1408  * @data: (array length=len) (transfer none) (nullable): an array of pointers,
1409  * or %NULL for an empty array
1410  * @len: the number of pointers in @data
1411  * @copy_func: (nullable): a copy function used to copy every element in the
1412  *   array or %NULL.
1413  * @copy_func_user_data: user data passed to @copy_func, or %NULL
1414  * @element_free_func: (nullable): a function to free elements on @array
1415  *   destruction or %NULL
1416  *
1417  * Creates a new #GPtrArray, copying @len pointers from @data, and setting
1418  * the array’s reference count to 1.
1419  *
1420  * This avoids having to manually add each element one by one.
1421  *
1422  * If @copy_func is provided, then it is used to copy each element before
1423  * adding them to the new array. If it is %NULL then the pointers are copied
1424  * directly.
1425  *
1426  * It also sets @element_free_func for freeing each element when the array is
1427  * destroyed either via g_ptr_array_unref(), when g_ptr_array_free() is called
1428  * with @free_segment set to %TRUE or when removing elements.
1429  *
1430  * Do not use it if @len is greater than %G_MAXUINT. #GPtrArray
1431  * stores the length of its data in #guint, which may be shorter than
1432  * #gsize.
1433  *
1434  * Returns: (transfer full): A new #GPtrArray
1435  *
1436  * Since: 2.76
1437  */
1438 GPtrArray *
1439 g_ptr_array_new_from_array (gpointer       *data,
1440                             gsize           len,
1441                             GCopyFunc       copy_func,
1442                             gpointer        copy_func_user_data,
1443                             GDestroyNotify  element_free_func)
1444 {
1445   g_return_val_if_fail (data != NULL || len == 0, NULL);
1446   g_return_val_if_fail (len <= G_MAXUINT, NULL);
1447
1448   return ptr_array_new_from_array (
1449     data, len, copy_func, copy_func_user_data, element_free_func, FALSE);
1450 }
1451
1452 /**
1453  * g_ptr_array_new_from_null_terminated_array: (skip)
1454  * @data: (array zero-terminated=1) (transfer none) (nullable): an array of
1455  *   pointers, %NULL terminated; or %NULL for an empty array
1456  * @copy_func: (nullable): a copy function used to copy every element in the
1457  *   array or %NULL.
1458  * @copy_func_user_data: user data passed to @copy_func, or %NULL
1459  * @element_free_func: (nullable): a function to free elements on @array
1460  *   destruction or %NULL
1461  *
1462  * Creates a new #GPtrArray copying the pointers from @data after having
1463  * computed the length of it and with a reference count of 1.
1464  * This avoids having to manually add each element one by one.
1465  * If @copy_func is provided, then it is used to copy the data in the new
1466  * array.
1467  * It also set @element_free_func for freeing each element when the array is
1468  * destroyed either via g_ptr_array_unref(), when g_ptr_array_free() is called
1469  * with @free_segment set to %TRUE or when removing elements.
1470  *
1471  * Do not use it if the @data has more than %G_MAXUINT elements. #GPtrArray
1472  * stores the length of its data in #guint, which may be shorter than
1473  * #gsize.
1474  *
1475  * Returns: (transfer full): A new #GPtrArray
1476  *
1477  * Since: 2.76
1478  */
1479 GPtrArray *
1480 g_ptr_array_new_from_null_terminated_array (gpointer       *data,
1481                                             GCopyFunc       copy_func,
1482                                             gpointer        copy_func_user_data,
1483                                             GDestroyNotify  element_free_func)
1484 {
1485   gsize len = 0;
1486
1487   if (data != NULL)
1488     {
1489       for (gsize i = 0; data[i] != NULL; ++i)
1490         len += 1;
1491     }
1492
1493   g_assert (data != NULL || len == 0);
1494   g_return_val_if_fail (len <= G_MAXUINT, NULL);
1495
1496   return ptr_array_new_from_array (
1497     data, len, copy_func, copy_func_user_data, element_free_func, TRUE);
1498 }
1499
1500 /**
1501  * g_ptr_array_steal:
1502  * @array: a #GPtrArray.
1503  * @len: (optional) (out): pointer to retrieve the number of
1504  *    elements of the original array
1505  *
1506  * Frees the data in the array and resets the size to zero, while
1507  * the underlying array is preserved for use elsewhere and returned
1508  * to the caller.
1509  *
1510  * Note that if the array is %NULL terminated this may still return
1511  * %NULL if the length of the array was zero and pdata was not yet
1512  * allocated.
1513  *
1514  * Even if set, the #GDestroyNotify function will never be called
1515  * on the current contents of the array and the caller is
1516  * responsible for freeing the array elements.
1517  *
1518  * An example of use:
1519  * |[<!-- language="C" -->
1520  * g_autoptr(GPtrArray) chunk_buffer = g_ptr_array_new_with_free_func (g_bytes_unref);
1521  *
1522  * // Some part of your application appends a number of chunks to the pointer array.
1523  * g_ptr_array_add (chunk_buffer, g_bytes_new_static ("hello", 5));
1524  * g_ptr_array_add (chunk_buffer, g_bytes_new_static ("world", 5));
1525  *
1526  * â€¦
1527  *
1528  * // Periodically, the chunks need to be sent as an array-and-length to some
1529  * // other part of the program.
1530  * GBytes **chunks;
1531  * gsize n_chunks;
1532  *
1533  * chunks = g_ptr_array_steal (chunk_buffer, &n_chunks);
1534  * for (gsize i = 0; i < n_chunks; i++)
1535  *   {
1536  *     // Do something with each chunk here, and then free them, since
1537  *     // g_ptr_array_steal() transfers ownership of all the elements and the
1538  *     // array to the caller.
1539  *     â€¦
1540  *
1541  *     g_bytes_unref (chunks[i]);
1542  *   }
1543  *
1544  * g_free (chunks);
1545  *
1546  * // After calling g_ptr_array_steal(), the pointer array can be reused for the
1547  * // next set of chunks.
1548  * g_assert (chunk_buffer->len == 0);
1549  * ]|
1550  *
1551  * Returns: (transfer full) (nullable): the element data, which should be
1552  *     freed using g_free(). This may be %NULL if the array doesn’t have any
1553  *     elements (i.e. if `*len` is zero).
1554  *
1555  * Since: 2.64
1556  */
1557 gpointer *
1558 g_ptr_array_steal (GPtrArray *array,
1559                    gsize *len)
1560 {
1561   GRealPtrArray *rarray;
1562   gpointer *segment;
1563
1564   g_return_val_if_fail (array != NULL, NULL);
1565
1566   rarray = (GRealPtrArray *) array;
1567   segment = (gpointer *) rarray->pdata;
1568
1569   if (len != NULL)
1570     *len = rarray->len;
1571
1572   rarray->pdata = NULL;
1573   rarray->len   = 0;
1574   rarray->alloc = 0;
1575   return segment;
1576 }
1577
1578 /**
1579  * g_ptr_array_copy:
1580  * @array: #GPtrArray to duplicate
1581  * @func: (nullable): a copy function used to copy every element in the array
1582  * @user_data: user data passed to the copy function @func, or %NULL
1583  *
1584  * Makes a full (deep) copy of a #GPtrArray.
1585  *
1586  * @func, as a #GCopyFunc, takes two arguments, the data to be copied
1587  * and a @user_data pointer. On common processor architectures, it's safe to
1588  * pass %NULL as @user_data if the copy function takes only one argument. You
1589  * may get compiler warnings from this though if compiling with GCC’s
1590  * `-Wcast-function-type` warning.
1591  *
1592  * If @func is %NULL, then only the pointers (and not what they are
1593  * pointing to) are copied to the new #GPtrArray.
1594  *
1595  * The copy of @array will have the same #GDestroyNotify for its elements as
1596  * @array. The copy will also be %NULL terminated if (and only if) the source
1597  * array is.
1598  *
1599  * Returns: (transfer full): a deep copy of the initial #GPtrArray.
1600  *
1601  * Since: 2.62
1602  **/
1603 GPtrArray *
1604 g_ptr_array_copy (GPtrArray *array,
1605                   GCopyFunc  func,
1606                   gpointer   user_data)
1607 {
1608   GRealPtrArray *rarray = (GRealPtrArray *) array;
1609   GPtrArray *new_array;
1610
1611   g_return_val_if_fail (array != NULL, NULL);
1612
1613   new_array = ptr_array_new (0,
1614                              rarray->element_free_func,
1615                              rarray->null_terminated);
1616
1617   if (rarray->alloc > 0)
1618     {
1619       g_ptr_array_maybe_expand ((GRealPtrArray *) new_array, array->len + rarray->null_terminated);
1620
1621       if (array->len > 0)
1622         {
1623           if (func != NULL)
1624             {
1625               guint i;
1626
1627               for (i = 0; i < array->len; i++)
1628                 new_array->pdata[i] = func (array->pdata[i], user_data);
1629             }
1630           else
1631             {
1632               memcpy (new_array->pdata, array->pdata,
1633                       array->len * sizeof (*array->pdata));
1634             }
1635
1636           new_array->len = array->len;
1637         }
1638
1639       ptr_array_maybe_null_terminate ((GRealPtrArray *) new_array);
1640     }
1641
1642   return new_array;
1643 }
1644
1645 /**
1646  * g_ptr_array_sized_new:
1647  * @reserved_size: number of pointers preallocated
1648  *
1649  * Creates a new #GPtrArray with @reserved_size pointers preallocated
1650  * and a reference count of 1. This avoids frequent reallocation, if
1651  * you are going to add many pointers to the array. Note however that
1652  * the size of the array is still 0.
1653  *
1654  * Returns: the new #GPtrArray
1655  */
1656 GPtrArray*
1657 g_ptr_array_sized_new (guint reserved_size)
1658 {
1659   return ptr_array_new (reserved_size, NULL, FALSE);
1660 }
1661
1662 /**
1663  * g_array_copy:
1664  * @array: A #GArray.
1665  *
1666  * Create a shallow copy of a #GArray. If the array elements consist of
1667  * pointers to data, the pointers are copied but the actual data is not.
1668  *
1669  * Returns: (transfer container): A copy of @array.
1670  *
1671  * Since: 2.62
1672  **/
1673 GArray *
1674 g_array_copy (GArray *array)
1675 {
1676   GRealArray *rarray = (GRealArray *) array;
1677   GRealArray *new_rarray;
1678
1679   g_return_val_if_fail (rarray != NULL, NULL);
1680
1681   new_rarray =
1682     (GRealArray *) g_array_sized_new (rarray->zero_terminated, rarray->clear,
1683                                       rarray->elt_size, rarray->elt_capacity);
1684   new_rarray->len = rarray->len;
1685   if (rarray->len > 0)
1686     memcpy (new_rarray->data, rarray->data, rarray->len * rarray->elt_size);
1687
1688   g_array_zero_terminate (new_rarray);
1689
1690   return (GArray *) new_rarray;
1691 }
1692
1693 /**
1694  * g_ptr_array_new_with_free_func:
1695  * @element_free_func: (nullable): A function to free elements with
1696  *     destroy @array or %NULL
1697  *
1698  * Creates a new #GPtrArray with a reference count of 1 and use
1699  * @element_free_func for freeing each element when the array is destroyed
1700  * either via g_ptr_array_unref(), when g_ptr_array_free() is called with
1701  * @free_segment set to %TRUE or when removing elements.
1702  *
1703  * Returns: (transfer full): A new #GPtrArray
1704  *
1705  * Since: 2.22
1706  */
1707 GPtrArray*
1708 g_ptr_array_new_with_free_func (GDestroyNotify element_free_func)
1709 {
1710   return ptr_array_new (0, element_free_func, FALSE);
1711 }
1712
1713 /**
1714  * g_ptr_array_new_full:
1715  * @reserved_size: number of pointers preallocated
1716  * @element_free_func: (nullable): A function to free elements with
1717  *     destroy @array or %NULL
1718  *
1719  * Creates a new #GPtrArray with @reserved_size pointers preallocated
1720  * and a reference count of 1. This avoids frequent reallocation, if
1721  * you are going to add many pointers to the array. Note however that
1722  * the size of the array is still 0. It also set @element_free_func
1723  * for freeing each element when the array is destroyed either via
1724  * g_ptr_array_unref(), when g_ptr_array_free() is called with
1725  * @free_segment set to %TRUE or when removing elements.
1726  *
1727  * Returns: (transfer full): A new #GPtrArray
1728  *
1729  * Since: 2.30
1730  */
1731 GPtrArray*
1732 g_ptr_array_new_full (guint          reserved_size,
1733                       GDestroyNotify element_free_func)
1734 {
1735   return ptr_array_new (reserved_size, element_free_func, FALSE);
1736 }
1737
1738 /**
1739  * g_ptr_array_new_null_terminated:
1740  * @reserved_size: number of pointers preallocated.
1741  *     If @null_terminated is %TRUE, the actually allocated
1742  *     buffer size is @reserved_size plus 1, unless @reserved_size
1743  *     is zero, in which case no initial buffer gets allocated.
1744  * @element_free_func: (nullable): A function to free elements with
1745  *     destroy @array or %NULL
1746  * @null_terminated: whether to make the array as %NULL terminated.
1747  *
1748  * Like g_ptr_array_new_full() but also allows to set the array to
1749  * be %NULL terminated. A %NULL terminated pointer array has an
1750  * additional %NULL pointer after the last element, beyond the
1751  * current length.
1752  *
1753  * #GPtrArray created by other constructors are not automatically %NULL
1754  * terminated.
1755  *
1756  * Note that if the @array's length is zero and currently no
1757  * data array is allocated, then pdata will still be %NULL.
1758  * %GPtrArray will only %NULL terminate pdata, if an actual
1759  * array is allocated. It does not guarantee that an array
1760  * is always allocated. In other words, if the length is zero,
1761  * then pdata may either point to a %NULL terminated array of length
1762  * zero or be %NULL.
1763  *
1764  * Returns: (transfer full): A new #GPtrArray
1765  *
1766  * Since: 2.74
1767  */
1768 GPtrArray *
1769 g_ptr_array_new_null_terminated (guint          reserved_size,
1770                                  GDestroyNotify element_free_func,
1771                                  gboolean       null_terminated)
1772 {
1773   return ptr_array_new (reserved_size, element_free_func, null_terminated);
1774 }
1775
1776 /**
1777  * g_ptr_array_set_free_func:
1778  * @array: A #GPtrArray
1779  * @element_free_func: (nullable): A function to free elements with
1780  *     destroy @array or %NULL
1781  *
1782  * Sets a function for freeing each element when @array is destroyed
1783  * either via g_ptr_array_unref(), when g_ptr_array_free() is called
1784  * with @free_segment set to %TRUE or when removing elements.
1785  *
1786  * Since: 2.22
1787  */
1788 void
1789 g_ptr_array_set_free_func (GPtrArray      *array,
1790                            GDestroyNotify  element_free_func)
1791 {
1792   GRealPtrArray *rarray = (GRealPtrArray *)array;
1793
1794   g_return_if_fail (array);
1795
1796   rarray->element_free_func = element_free_func;
1797 }
1798
1799 /**
1800  * g_ptr_array_is_null_terminated:
1801  * @array: the #GPtrArray
1802  *
1803  * Gets whether the @array was constructed as %NULL-terminated.
1804  *
1805  * This will only return %TRUE for arrays constructed by passing %TRUE to the
1806  * `null_terminated` argument of g_ptr_array_new_null_terminated(). It will not
1807  * return %TRUE for normal arrays which have had a %NULL element appended to
1808  * them.
1809  *
1810  * Returns: %TRUE if the array is made to be %NULL terminated.
1811  *
1812  * Since: 2.74
1813  */
1814 gboolean
1815 g_ptr_array_is_null_terminated (GPtrArray *array)
1816 {
1817   g_return_val_if_fail (array, FALSE);
1818
1819   return ((GRealPtrArray *) array)->null_terminated;
1820 }
1821
1822 /**
1823  * g_ptr_array_ref:
1824  * @array: a #GPtrArray
1825  *
1826  * Atomically increments the reference count of @array by one.
1827  * This function is thread-safe and may be called from any thread.
1828  *
1829  * Returns: The passed in #GPtrArray
1830  *
1831  * Since: 2.22
1832  */
1833 GPtrArray*
1834 g_ptr_array_ref (GPtrArray *array)
1835 {
1836   GRealPtrArray *rarray = (GRealPtrArray *)array;
1837
1838   g_return_val_if_fail (array, NULL);
1839
1840   g_atomic_ref_count_inc (&rarray->ref_count);
1841
1842   return array;
1843 }
1844
1845 static gpointer *ptr_array_free (GPtrArray *, ArrayFreeFlags);
1846
1847 /**
1848  * g_ptr_array_unref:
1849  * @array: A #GPtrArray
1850  *
1851  * Atomically decrements the reference count of @array by one. If the
1852  * reference count drops to 0, the effect is the same as calling
1853  * g_ptr_array_free() with @free_segment set to %TRUE. This function
1854  * is thread-safe and may be called from any thread.
1855  *
1856  * Since: 2.22
1857  */
1858 void
1859 g_ptr_array_unref (GPtrArray *array)
1860 {
1861   GRealPtrArray *rarray = (GRealPtrArray *)array;
1862
1863   g_return_if_fail (array);
1864
1865   if (g_atomic_ref_count_dec (&rarray->ref_count))
1866     ptr_array_free (array, FREE_SEGMENT);
1867 }
1868
1869 /**
1870  * g_ptr_array_free:
1871  * @array: a #GPtrArray
1872  * @free_seg: if %TRUE the actual pointer array is freed as well
1873  *
1874  * Frees the memory allocated for the #GPtrArray. If @free_seg is %TRUE
1875  * it frees the memory block holding the elements as well. Pass %FALSE
1876  * if you want to free the #GPtrArray wrapper but preserve the
1877  * underlying array for use elsewhere. If the reference count of @array
1878  * is greater than one, the #GPtrArray wrapper is preserved but the
1879  * size of @array will be set to zero.
1880  *
1881  * If array contents point to dynamically-allocated memory, they should
1882  * be freed separately if @free_seg is %TRUE and no #GDestroyNotify
1883  * function has been set for @array.
1884  *
1885  * Note that if the array is %NULL terminated and @free_seg is %FALSE
1886  * then this will always return an allocated %NULL terminated buffer.
1887  * If pdata is previously %NULL, a new buffer will be allocated.
1888  *
1889  * This function is not thread-safe. If using a #GPtrArray from multiple
1890  * threads, use only the atomic g_ptr_array_ref() and g_ptr_array_unref()
1891  * functions.
1892  *
1893  * Returns: (transfer full) (nullable): the pointer array if @free_seg is
1894  *     %FALSE, otherwise %NULL. The pointer array should be freed using g_free().
1895  */
1896 gpointer*
1897 g_ptr_array_free (GPtrArray *array,
1898                   gboolean   free_segment)
1899 {
1900   GRealPtrArray *rarray = (GRealPtrArray *)array;
1901   ArrayFreeFlags flags;
1902
1903   g_return_val_if_fail (rarray, NULL);
1904
1905   flags = (free_segment ? FREE_SEGMENT : 0);
1906
1907   /* if others are holding a reference, preserve the wrapper but
1908    * do free/return the data
1909    *
1910    * Coverity doesn’t understand this and assumes it’s a leak, so comment this
1911    * out.
1912    */
1913 #ifndef __COVERITY__
1914   if (!g_atomic_ref_count_dec (&rarray->ref_count))
1915     flags |= PRESERVE_WRAPPER;
1916 #endif
1917
1918   return ptr_array_free (array, flags);
1919 }
1920
1921 static gpointer *
1922 ptr_array_free (GPtrArray      *array,
1923                 ArrayFreeFlags  flags)
1924 {
1925   GRealPtrArray *rarray = (GRealPtrArray *)array;
1926   gpointer *segment;
1927
1928   if (flags & FREE_SEGMENT)
1929     {
1930       /* Data here is stolen and freed manually. It is an
1931        * error to attempt to access the array data (including
1932        * mutating the array bounds) during destruction).
1933        *
1934        * https://bugzilla.gnome.org/show_bug.cgi?id=769064
1935        */
1936       gpointer *stolen_pdata = g_steal_pointer (&rarray->pdata);
1937       if (rarray->element_free_func != NULL)
1938         {
1939           guint i;
1940
1941           for (i = 0; i < rarray->len; ++i)
1942             rarray->element_free_func (stolen_pdata[i]);
1943         }
1944
1945       g_free (stolen_pdata);
1946       segment = NULL;
1947     }
1948   else
1949     {
1950       segment = rarray->pdata;
1951       if (!segment && rarray->null_terminated)
1952         segment = (gpointer *) g_new0 (char *, 1);
1953     }
1954
1955   if (flags & PRESERVE_WRAPPER)
1956     {
1957       rarray->pdata = NULL;
1958       rarray->len = 0;
1959       rarray->alloc = 0;
1960     }
1961   else
1962     {
1963       g_slice_free1 (sizeof (GRealPtrArray), rarray);
1964     }
1965
1966   return segment;
1967 }
1968
1969 static void
1970 g_ptr_array_maybe_expand (GRealPtrArray *array,
1971                           guint          len)
1972 {
1973   guint max_len;
1974
1975   /* The maximum array length is derived from following constraints:
1976    * - The number of bytes must fit into a gsize / 2.
1977    * - The number of elements must fit into guint.
1978    */
1979   max_len = MIN (G_MAXSIZE / 2 / sizeof (gpointer), G_MAXUINT);
1980
1981   /* Detect potential overflow */
1982   if G_UNLIKELY ((max_len - array->len) < len)
1983     g_error ("adding %u to array would overflow", len);
1984
1985   if ((array->len + len) > array->alloc)
1986     {
1987       guint old_alloc = array->alloc;
1988       gsize want_alloc = g_nearest_pow (sizeof (gpointer) * (array->len + len));
1989       want_alloc = MAX (want_alloc, MIN_ARRAY_SIZE);
1990       array->alloc = MIN (want_alloc / sizeof (gpointer), G_MAXUINT);
1991       array->pdata = g_realloc (array->pdata, want_alloc);
1992       if (G_UNLIKELY (g_mem_gc_friendly))
1993         for ( ; old_alloc < array->alloc; old_alloc++)
1994           array->pdata [old_alloc] = NULL;
1995     }
1996 }
1997
1998 /**
1999  * g_ptr_array_set_size:
2000  * @array: a #GPtrArray
2001  * @length: the new length of the pointer array
2002  *
2003  * Sets the size of the array. When making the array larger,
2004  * newly-added elements will be set to %NULL. When making it smaller,
2005  * if @array has a non-%NULL #GDestroyNotify function then it will be
2006  * called for the removed elements.
2007  */
2008 void
2009 g_ptr_array_set_size  (GPtrArray *array,
2010                        gint       length)
2011 {
2012   GRealPtrArray *rarray = (GRealPtrArray *)array;
2013   guint length_unsigned;
2014
2015   g_return_if_fail (rarray);
2016   g_return_if_fail (rarray->len == 0 || (rarray->len != 0 && rarray->pdata != NULL));
2017   g_return_if_fail (length >= 0);
2018
2019   length_unsigned = (guint) length;
2020
2021   if (length_unsigned > rarray->len)
2022     {
2023       guint i;
2024
2025       if (G_UNLIKELY (rarray->null_terminated) &&
2026           length_unsigned - rarray->len > G_MAXUINT - 1)
2027         g_error ("array would overflow");
2028
2029       g_ptr_array_maybe_expand (rarray, (length_unsigned - rarray->len) + rarray->null_terminated);
2030
2031       /* This is not
2032        *     memset (array->pdata + array->len, 0,
2033        *            sizeof (gpointer) * (length_unsigned - array->len));
2034        * to make it really portable. Remember (void*)NULL needn't be
2035        * bitwise zero. It of course is silly not to use memset (..,0,..).
2036        */
2037       for (i = rarray->len; i < length_unsigned; i++)
2038         rarray->pdata[i] = NULL;
2039
2040       rarray->len = length_unsigned;
2041
2042       ptr_array_maybe_null_terminate (rarray);
2043     }
2044   else if (length_unsigned < rarray->len)
2045     g_ptr_array_remove_range (array, length_unsigned, rarray->len - length_unsigned);
2046 }
2047
2048 static gpointer
2049 ptr_array_remove_index (GPtrArray *array,
2050                         guint      index_,
2051                         gboolean   fast,
2052                         gboolean   free_element)
2053 {
2054   GRealPtrArray *rarray = (GRealPtrArray *) array;
2055   gpointer result;
2056
2057   g_return_val_if_fail (rarray, NULL);
2058   g_return_val_if_fail (rarray->len == 0 || (rarray->len != 0 && rarray->pdata != NULL), NULL);
2059
2060   g_return_val_if_fail (index_ < rarray->len, NULL);
2061
2062   result = rarray->pdata[index_];
2063
2064   if (rarray->element_free_func != NULL && free_element)
2065     rarray->element_free_func (rarray->pdata[index_]);
2066
2067   if (index_ != rarray->len - 1 && !fast)
2068     memmove (rarray->pdata + index_, rarray->pdata + index_ + 1,
2069              sizeof (gpointer) * (rarray->len - index_ - 1));
2070   else if (index_ != rarray->len - 1)
2071     rarray->pdata[index_] = rarray->pdata[rarray->len - 1];
2072
2073   rarray->len -= 1;
2074
2075   if (rarray->null_terminated || G_UNLIKELY (g_mem_gc_friendly))
2076     rarray->pdata[rarray->len] = NULL;
2077
2078   return result;
2079 }
2080
2081 /**
2082  * g_ptr_array_remove_index:
2083  * @array: a #GPtrArray
2084  * @index_: the index of the pointer to remove
2085  *
2086  * Removes the pointer at the given index from the pointer array.
2087  * The following elements are moved down one place. If @array has
2088  * a non-%NULL #GDestroyNotify function it is called for the removed
2089  * element. If so, the return value from this function will potentially point
2090  * to freed memory (depending on the #GDestroyNotify implementation).
2091  *
2092  * Returns: (nullable): the pointer which was removed
2093  */
2094 gpointer
2095 g_ptr_array_remove_index (GPtrArray *array,
2096                           guint      index_)
2097 {
2098   return ptr_array_remove_index (array, index_, FALSE, TRUE);
2099 }
2100
2101 /**
2102  * g_ptr_array_remove_index_fast:
2103  * @array: a #GPtrArray
2104  * @index_: the index of the pointer to remove
2105  *
2106  * Removes the pointer at the given index from the pointer array.
2107  * The last element in the array is used to fill in the space, so
2108  * this function does not preserve the order of the array. But it
2109  * is faster than g_ptr_array_remove_index(). If @array has a non-%NULL
2110  * #GDestroyNotify function it is called for the removed element. If so, the
2111  * return value from this function will potentially point to freed memory
2112  * (depending on the #GDestroyNotify implementation).
2113  *
2114  * Returns: (nullable): the pointer which was removed
2115  */
2116 gpointer
2117 g_ptr_array_remove_index_fast (GPtrArray *array,
2118                                guint      index_)
2119 {
2120   return ptr_array_remove_index (array, index_, TRUE, TRUE);
2121 }
2122
2123 /**
2124  * g_ptr_array_steal_index:
2125  * @array: a #GPtrArray
2126  * @index_: the index of the pointer to steal
2127  *
2128  * Removes the pointer at the given index from the pointer array.
2129  * The following elements are moved down one place. The #GDestroyNotify for
2130  * @array is *not* called on the removed element; ownership is transferred to
2131  * the caller of this function.
2132  *
2133  * Returns: (transfer full) (nullable): the pointer which was removed
2134  * Since: 2.58
2135  */
2136 gpointer
2137 g_ptr_array_steal_index (GPtrArray *array,
2138                          guint      index_)
2139 {
2140   return ptr_array_remove_index (array, index_, FALSE, FALSE);
2141 }
2142
2143 /**
2144  * g_ptr_array_steal_index_fast:
2145  * @array: a #GPtrArray
2146  * @index_: the index of the pointer to steal
2147  *
2148  * Removes the pointer at the given index from the pointer array.
2149  * The last element in the array is used to fill in the space, so
2150  * this function does not preserve the order of the array. But it
2151  * is faster than g_ptr_array_steal_index(). The #GDestroyNotify for @array is
2152  * *not* called on the removed element; ownership is transferred to the caller
2153  * of this function.
2154  *
2155  * Returns: (transfer full) (nullable): the pointer which was removed
2156  * Since: 2.58
2157  */
2158 gpointer
2159 g_ptr_array_steal_index_fast (GPtrArray *array,
2160                               guint      index_)
2161 {
2162   return ptr_array_remove_index (array, index_, TRUE, FALSE);
2163 }
2164
2165 /**
2166  * g_ptr_array_remove_range:
2167  * @array: a @GPtrArray
2168  * @index_: the index of the first pointer to remove
2169  * @length: the number of pointers to remove
2170  *
2171  * Removes the given number of pointers starting at the given index
2172  * from a #GPtrArray. The following elements are moved to close the
2173  * gap. If @array has a non-%NULL #GDestroyNotify function it is
2174  * called for the removed elements.
2175  *
2176  * Returns: the @array
2177  *
2178  * Since: 2.4
2179  */
2180 GPtrArray*
2181 g_ptr_array_remove_range (GPtrArray *array,
2182                           guint      index_,
2183                           guint      length)
2184 {
2185   GRealPtrArray *rarray = (GRealPtrArray *)array;
2186   guint i;
2187
2188   g_return_val_if_fail (rarray != NULL, NULL);
2189   g_return_val_if_fail (rarray->len == 0 || (rarray->len != 0 && rarray->pdata != NULL), NULL);
2190   g_return_val_if_fail (index_ <= rarray->len, NULL);
2191   g_return_val_if_fail (length == 0 || index_ + length <= rarray->len, NULL);
2192
2193   if (length == 0)
2194     return array;
2195
2196   if (rarray->element_free_func != NULL)
2197     {
2198       for (i = index_; i < index_ + length; i++)
2199         rarray->element_free_func (rarray->pdata[i]);
2200     }
2201
2202   if (index_ + length != rarray->len)
2203     {
2204       memmove (&rarray->pdata[index_],
2205                &rarray->pdata[index_ + length],
2206                (rarray->len - (index_ + length)) * sizeof (gpointer));
2207     }
2208
2209   rarray->len -= length;
2210   if (G_UNLIKELY (g_mem_gc_friendly))
2211     {
2212       for (i = 0; i < length; i++)
2213         rarray->pdata[rarray->len + i] = NULL;
2214     }
2215   else
2216     ptr_array_maybe_null_terminate (rarray);
2217
2218   return array;
2219 }
2220
2221 /**
2222  * g_ptr_array_remove:
2223  * @array: a #GPtrArray
2224  * @data: the pointer to remove
2225  *
2226  * Removes the first occurrence of the given pointer from the pointer
2227  * array. The following elements are moved down one place. If @array
2228  * has a non-%NULL #GDestroyNotify function it is called for the
2229  * removed element.
2230  *
2231  * It returns %TRUE if the pointer was removed, or %FALSE if the
2232  * pointer was not found.
2233  *
2234  * Returns: %TRUE if the pointer is removed, %FALSE if the pointer
2235  *     is not found in the array
2236  */
2237 gboolean
2238 g_ptr_array_remove (GPtrArray *array,
2239                     gpointer   data)
2240 {
2241   guint i;
2242
2243   g_return_val_if_fail (array, FALSE);
2244   g_return_val_if_fail (array->len == 0 || (array->len != 0 && array->pdata != NULL), FALSE);
2245
2246   for (i = 0; i < array->len; i += 1)
2247     {
2248       if (array->pdata[i] == data)
2249         {
2250           g_ptr_array_remove_index (array, i);
2251           return TRUE;
2252         }
2253     }
2254
2255   return FALSE;
2256 }
2257
2258 /**
2259  * g_ptr_array_remove_fast:
2260  * @array: a #GPtrArray
2261  * @data: the pointer to remove
2262  *
2263  * Removes the first occurrence of the given pointer from the pointer
2264  * array. The last element in the array is used to fill in the space,
2265  * so this function does not preserve the order of the array. But it
2266  * is faster than g_ptr_array_remove(). If @array has a non-%NULL
2267  * #GDestroyNotify function it is called for the removed element.
2268  *
2269  * It returns %TRUE if the pointer was removed, or %FALSE if the
2270  * pointer was not found.
2271  *
2272  * Returns: %TRUE if the pointer was found in the array
2273  */
2274 gboolean
2275 g_ptr_array_remove_fast (GPtrArray *array,
2276                          gpointer   data)
2277 {
2278   GRealPtrArray *rarray = (GRealPtrArray *)array;
2279   guint i;
2280
2281   g_return_val_if_fail (rarray, FALSE);
2282   g_return_val_if_fail (rarray->len == 0 || (rarray->len != 0 && rarray->pdata != NULL), FALSE);
2283
2284   for (i = 0; i < rarray->len; i += 1)
2285     {
2286       if (rarray->pdata[i] == data)
2287         {
2288           g_ptr_array_remove_index_fast (array, i);
2289           return TRUE;
2290         }
2291     }
2292
2293   return FALSE;
2294 }
2295
2296 /**
2297  * g_ptr_array_add:
2298  * @array: a #GPtrArray
2299  * @data: the pointer to add
2300  *
2301  * Adds a pointer to the end of the pointer array. The array will grow
2302  * in size automatically if necessary.
2303  */
2304 void
2305 g_ptr_array_add (GPtrArray *array,
2306                  gpointer   data)
2307 {
2308   GRealPtrArray *rarray = (GRealPtrArray *)array;
2309
2310   g_return_if_fail (rarray);
2311   g_return_if_fail (rarray->len == 0 || (rarray->len != 0 && rarray->pdata != NULL));
2312
2313   g_ptr_array_maybe_expand (rarray, 1u + rarray->null_terminated);
2314
2315   rarray->pdata[rarray->len++] = data;
2316
2317   ptr_array_maybe_null_terminate (rarray);
2318 }
2319
2320 /**
2321  * g_ptr_array_extend:
2322  * @array_to_extend: a #GPtrArray.
2323  * @array: (transfer none): a #GPtrArray to add to the end of @array_to_extend.
2324  * @func: (nullable): a copy function used to copy every element in the array
2325  * @user_data: user data passed to the copy function @func, or %NULL
2326  *
2327  * Adds all pointers of @array to the end of the array @array_to_extend.
2328  * The array will grow in size automatically if needed. @array_to_extend is
2329  * modified in-place.
2330  *
2331  * @func, as a #GCopyFunc, takes two arguments, the data to be copied
2332  * and a @user_data pointer. On common processor architectures, it's safe to
2333  * pass %NULL as @user_data if the copy function takes only one argument. You
2334  * may get compiler warnings from this though if compiling with GCC’s
2335  * `-Wcast-function-type` warning.
2336  *
2337  * If @func is %NULL, then only the pointers (and not what they are
2338  * pointing to) are copied to the new #GPtrArray.
2339  *
2340  * Whether @array_to_extend is %NULL terminated stays unchanged by this function.
2341  *
2342  * Since: 2.62
2343  **/
2344 void
2345 g_ptr_array_extend (GPtrArray  *array_to_extend,
2346                     GPtrArray  *array,
2347                     GCopyFunc   func,
2348                     gpointer    user_data)
2349 {
2350   GRealPtrArray *rarray_to_extend = (GRealPtrArray *) array_to_extend;
2351
2352   g_return_if_fail (array_to_extend != NULL);
2353   g_return_if_fail (array != NULL);
2354
2355   if (array->len == 0u)
2356     return;
2357
2358   if (G_UNLIKELY (array->len == G_MAXUINT) &&
2359       rarray_to_extend->null_terminated)
2360     g_error ("adding %u to array would overflow", array->len);
2361
2362   g_ptr_array_maybe_expand (rarray_to_extend, array->len + rarray_to_extend->null_terminated);
2363
2364   if (func != NULL)
2365     {
2366       guint i;
2367
2368       for (i = 0; i < array->len; i++)
2369         rarray_to_extend->pdata[i + rarray_to_extend->len] =
2370           func (array->pdata[i], user_data);
2371     }
2372   else if (array->len > 0)
2373     {
2374       memcpy (rarray_to_extend->pdata + rarray_to_extend->len, array->pdata,
2375               array->len * sizeof (*array->pdata));
2376     }
2377
2378   rarray_to_extend->len += array->len;
2379
2380   ptr_array_maybe_null_terminate (rarray_to_extend);
2381 }
2382
2383 /**
2384  * g_ptr_array_extend_and_steal:
2385  * @array_to_extend: (transfer none): a #GPtrArray.
2386  * @array: (transfer container): a #GPtrArray to add to the end of
2387  *     @array_to_extend.
2388  *
2389  * Adds all the pointers in @array to the end of @array_to_extend, transferring
2390  * ownership of each element from @array to @array_to_extend and modifying
2391  * @array_to_extend in-place. @array is then freed.
2392  *
2393  * As with g_ptr_array_free(), @array will be destroyed if its reference count
2394  * is 1. If its reference count is higher, it will be decremented and the
2395  * length of @array set to zero.
2396  *
2397  * Since: 2.62
2398  **/
2399 void
2400 g_ptr_array_extend_and_steal (GPtrArray  *array_to_extend,
2401                               GPtrArray  *array)
2402 {
2403   gpointer *pdata;
2404
2405   g_ptr_array_extend (array_to_extend, array, NULL, NULL);
2406
2407   /* Get rid of @array without triggering the GDestroyNotify attached
2408    * to the elements moved from @array to @array_to_extend. */
2409   pdata = g_steal_pointer (&array->pdata);
2410   array->len = 0;
2411   ((GRealPtrArray *) array)->alloc = 0;
2412   g_ptr_array_unref (array);
2413   g_free (pdata);
2414 }
2415
2416 /**
2417  * g_ptr_array_insert:
2418  * @array: a #GPtrArray
2419  * @index_: the index to place the new element at, or -1 to append
2420  * @data: the pointer to add.
2421  *
2422  * Inserts an element into the pointer array at the given index. The 
2423  * array will grow in size automatically if necessary.
2424  *
2425  * Since: 2.40
2426  */
2427 void
2428 g_ptr_array_insert (GPtrArray *array,
2429                     gint       index_,
2430                     gpointer   data)
2431 {
2432   GRealPtrArray *rarray = (GRealPtrArray *)array;
2433
2434   g_return_if_fail (rarray);
2435   g_return_if_fail (index_ >= -1);
2436   g_return_if_fail (index_ <= (gint)rarray->len);
2437
2438   g_ptr_array_maybe_expand (rarray, 1u + rarray->null_terminated);
2439
2440   if (index_ < 0)
2441     index_ = rarray->len;
2442
2443   if ((guint) index_ < rarray->len)
2444     memmove (&(rarray->pdata[index_ + 1]),
2445              &(rarray->pdata[index_]),
2446              (rarray->len - index_) * sizeof (gpointer));
2447
2448   rarray->len++;
2449   rarray->pdata[index_] = data;
2450
2451   ptr_array_maybe_null_terminate (rarray);
2452 }
2453
2454 /* Please keep this doc-comment in sync with pointer_array_sort_example()
2455  * in glib/tests/array-test.c */
2456 /**
2457  * g_ptr_array_sort:
2458  * @array: a #GPtrArray
2459  * @compare_func: comparison function
2460  *
2461  * Sorts the array, using @compare_func which should be a qsort()-style
2462  * comparison function (returns less than zero for first arg is less
2463  * than second arg, zero for equal, greater than zero if first arg is
2464  * greater than second arg).
2465  *
2466  * Note that the comparison function for g_ptr_array_sort() doesn't
2467  * take the pointers from the array as arguments, it takes pointers to
2468  * the pointers in the array.
2469  *
2470  * Use g_ptr_array_sort_values() if you want to use normal
2471  * #GCompareFuncs, otherwise here is a full example of use:
2472  *
2473  * |[<!-- language="C" -->
2474  * typedef struct
2475  * {
2476  *   gchar *name;
2477  *   gint size;
2478  * } FileListEntry;
2479  *
2480  * static gint
2481  * sort_filelist (gconstpointer a, gconstpointer b)
2482  * {
2483  *   const FileListEntry *entry1 = *((FileListEntry **) a);
2484  *   const FileListEntry *entry2 = *((FileListEntry **) b);
2485  *
2486  *   return g_ascii_strcasecmp (entry1->name, entry2->name);
2487  * }
2488  *
2489  * â€¦
2490  * g_autoptr (GPtrArray) file_list = NULL;
2491  *
2492  * // initialize file_list array and load with many FileListEntry entries
2493  * ...
2494  * // now sort it with
2495  * g_ptr_array_sort (file_list, sort_filelist);
2496  * ]|
2497  *
2498  * This is guaranteed to be a stable sort since version 2.32.
2499  */
2500 void
2501 g_ptr_array_sort (GPtrArray    *array,
2502                   GCompareFunc  compare_func)
2503 {
2504   g_return_if_fail (array != NULL);
2505
2506   /* Don't use qsort as we want a guaranteed stable sort */
2507   if (array->len > 0)
2508     g_qsort_with_data (array->pdata,
2509                        array->len,
2510                        sizeof (gpointer),
2511                        (GCompareDataFunc)compare_func,
2512                        NULL);
2513 }
2514
2515 /* Please keep this doc-comment in sync with
2516  * pointer_array_sort_with_data_example() in glib/tests/array-test.c */
2517 /**
2518  * g_ptr_array_sort_with_data:
2519  * @array: a #GPtrArray
2520  * @compare_func: comparison function
2521  * @user_data: data to pass to @compare_func
2522  *
2523  * Like g_ptr_array_sort(), but the comparison function has an extra
2524  * user data argument.
2525  *
2526  * Note that the comparison function for g_ptr_array_sort_with_data()
2527  * doesn't take the pointers from the array as arguments, it takes
2528  * pointers to the pointers in the array.
2529  *
2530  * Use g_ptr_array_sort_values_with_data() if you want to use normal
2531  * #GCompareDataFuncs, otherwise here is a full example of use:
2532  *
2533  * |[<!-- language="C" -->
2534  * typedef enum { SORT_NAME, SORT_SIZE } SortMode;
2535  *
2536  * typedef struct
2537  * {
2538  *   gchar *name;
2539  *   gint size;
2540  * } FileListEntry;
2541  *
2542  * static gint
2543  * sort_filelist (gconstpointer a, gconstpointer b, gpointer user_data)
2544  * {
2545  *   gint order;
2546  *   const SortMode sort_mode = GPOINTER_TO_INT (user_data);
2547  *   const FileListEntry *entry1 = *((FileListEntry **) a);
2548  *   const FileListEntry *entry2 = *((FileListEntry **) b);
2549  *
2550  *   switch (sort_mode)
2551  *     {
2552  *     case SORT_NAME:
2553  *       order = g_ascii_strcasecmp (entry1->name, entry2->name);
2554  *       break;
2555  *     case SORT_SIZE:
2556  *       order = entry1->size - entry2->size;
2557  *       break;
2558  *     default:
2559  *       order = 0;
2560  *       break;
2561  *     }
2562  *   return order;
2563  * }
2564  *
2565  * ...
2566  * g_autoptr (GPtrArray) file_list = NULL;
2567  * SortMode sort_mode;
2568  *
2569  * // initialize file_list array and load with many FileListEntry entries
2570  * ...
2571  * // now sort it with
2572  * sort_mode = SORT_NAME;
2573  * g_ptr_array_sort_with_data (file_list,
2574  *                             sort_filelist,
2575  *                             GINT_TO_POINTER (sort_mode));
2576  * ]|
2577  *
2578  * This is guaranteed to be a stable sort since version 2.32.
2579  */
2580 void
2581 g_ptr_array_sort_with_data (GPtrArray        *array,
2582                             GCompareDataFunc  compare_func,
2583                             gpointer          user_data)
2584 {
2585   g_return_if_fail (array != NULL);
2586
2587   if (array->len > 0)
2588     g_qsort_with_data (array->pdata,
2589                        array->len,
2590                        sizeof (gpointer),
2591                        compare_func,
2592                        user_data);
2593 }
2594
2595 static inline gint
2596 compare_ptr_array_values (gconstpointer a, gconstpointer b, gpointer user_data)
2597 {
2598   gconstpointer aa = *((gconstpointer *) a);
2599   gconstpointer bb = *((gconstpointer *) b);
2600   GCompareFunc compare_func = user_data;
2601
2602   return compare_func (aa, bb);
2603 }
2604
2605 /**
2606  * g_ptr_array_sort_values:
2607  * @array: a #GPtrArray
2608  * @compare_func: a #GCompareFunc comparison function
2609  *
2610  * Sorts the array, using @compare_func which should be a qsort()-style
2611  * comparison function (returns less than zero for first arg is less
2612  * than second arg, zero for equal, greater than zero if first arg is
2613  * greater than second arg).
2614  *
2615  * This is guaranteed to be a stable sort.
2616  *
2617  * Since: 2.76
2618  */
2619 void
2620 g_ptr_array_sort_values (GPtrArray    *array,
2621                          GCompareFunc  compare_func)
2622 {
2623   g_ptr_array_sort_with_data (array, compare_ptr_array_values, compare_func);
2624 }
2625
2626 typedef struct
2627 {
2628   GCompareDataFunc compare_func;
2629   gpointer user_data;
2630 } GPtrArraySortValuesData;
2631
2632 static inline gint
2633 compare_ptr_array_values_with_data (gconstpointer a,
2634                                     gconstpointer b,
2635                                     gpointer      user_data)
2636 {
2637   gconstpointer aa = *((gconstpointer *) a);
2638   gconstpointer bb = *((gconstpointer *) b);
2639   GPtrArraySortValuesData *data = user_data;
2640
2641   return data->compare_func (aa, bb, data->user_data);
2642 }
2643
2644 /**
2645  * g_ptr_array_sort_values_with_data:
2646  * @array: a #GPtrArray
2647  * @compare_func: a #GCompareDataFunc comparison function
2648  * @user_data: data to pass to @compare_func
2649  *
2650  * Like g_ptr_array_sort_values(), but the comparison function has an extra
2651  * user data argument.
2652  *
2653  * This is guaranteed to be a stable sort.
2654  *
2655  * Since: 2.76
2656  */
2657 void
2658 g_ptr_array_sort_values_with_data (GPtrArray        *array,
2659                                    GCompareDataFunc  compare_func,
2660                                    gpointer          user_data)
2661 {
2662   g_ptr_array_sort_with_data (array, compare_ptr_array_values_with_data,
2663                               &(GPtrArraySortValuesData){
2664                                   .compare_func = compare_func,
2665                                   .user_data = user_data,
2666                               });
2667 }
2668
2669 /**
2670  * g_ptr_array_foreach:
2671  * @array: a #GPtrArray
2672  * @func: the function to call for each array element
2673  * @user_data: user data to pass to the function
2674  * 
2675  * Calls a function for each element of a #GPtrArray. @func must not
2676  * add elements to or remove elements from the array.
2677  *
2678  * Since: 2.4
2679  */
2680 void
2681 g_ptr_array_foreach (GPtrArray *array,
2682                      GFunc      func,
2683                      gpointer   user_data)
2684 {
2685   guint i;
2686
2687   g_return_if_fail (array);
2688
2689   for (i = 0; i < array->len; i++)
2690     (*func) (array->pdata[i], user_data);
2691 }
2692
2693 /**
2694  * g_ptr_array_find: (skip)
2695  * @haystack: pointer array to be searched
2696  * @needle: pointer to look for
2697  * @index_: (optional) (out): return location for the index of
2698  *    the element, if found
2699  *
2700  * Checks whether @needle exists in @haystack. If the element is found, %TRUE is
2701  * returned and the element’s index is returned in @index_ (if non-%NULL).
2702  * Otherwise, %FALSE is returned and @index_ is undefined. If @needle exists
2703  * multiple times in @haystack, the index of the first instance is returned.
2704  *
2705  * This does pointer comparisons only. If you want to use more complex equality
2706  * checks, such as string comparisons, use g_ptr_array_find_with_equal_func().
2707  *
2708  * Returns: %TRUE if @needle is one of the elements of @haystack
2709  * Since: 2.54
2710  */
2711 gboolean
2712 g_ptr_array_find (GPtrArray     *haystack,
2713                   gconstpointer  needle,
2714                   guint         *index_)
2715 {
2716   return g_ptr_array_find_with_equal_func (haystack, needle, NULL, index_);
2717 }
2718
2719 /**
2720  * g_ptr_array_find_with_equal_func: (skip)
2721  * @haystack: pointer array to be searched
2722  * @needle: pointer to look for
2723  * @equal_func: (nullable): the function to call for each element, which should
2724  *    return %TRUE when the desired element is found; or %NULL to use pointer
2725  *    equality
2726  * @index_: (optional) (out): return location for the index of
2727  *    the element, if found
2728  *
2729  * Checks whether @needle exists in @haystack, using the given @equal_func.
2730  * If the element is found, %TRUE is returned and the element’s index is
2731  * returned in @index_ (if non-%NULL). Otherwise, %FALSE is returned and @index_
2732  * is undefined. If @needle exists multiple times in @haystack, the index of
2733  * the first instance is returned.
2734  *
2735  * @equal_func is called with the element from the array as its first parameter,
2736  * and @needle as its second parameter. If @equal_func is %NULL, pointer
2737  * equality is used.
2738  *
2739  * Returns: %TRUE if @needle is one of the elements of @haystack
2740  * Since: 2.54
2741  */
2742 gboolean
2743 g_ptr_array_find_with_equal_func (GPtrArray     *haystack,
2744                                   gconstpointer  needle,
2745                                   GEqualFunc     equal_func,
2746                                   guint         *index_)
2747 {
2748   guint i;
2749
2750   g_return_val_if_fail (haystack != NULL, FALSE);
2751
2752   if (equal_func == NULL)
2753     equal_func = g_direct_equal;
2754
2755   for (i = 0; i < haystack->len; i++)
2756     {
2757       if (equal_func (g_ptr_array_index (haystack, i), needle))
2758         {
2759           if (index_ != NULL)
2760             *index_ = i;
2761           return TRUE;
2762         }
2763     }
2764
2765   return FALSE;
2766 }
2767
2768 /**
2769  * SECTION:arrays_byte
2770  * @title: Byte Arrays
2771  * @short_description: arrays of bytes
2772  *
2773  * #GByteArray is a mutable array of bytes based on #GArray, to provide arrays
2774  * of bytes which grow automatically as elements are added.
2775  *
2776  * To create a new #GByteArray use g_byte_array_new(). To add elements to a
2777  * #GByteArray, use g_byte_array_append(), and g_byte_array_prepend().
2778  *
2779  * To set the size of a #GByteArray, use g_byte_array_set_size().
2780  *
2781  * To free a #GByteArray, use g_byte_array_free().
2782  *
2783  * An example for using a #GByteArray:
2784  * |[<!-- language="C" -->
2785  *   GByteArray *gbarray;
2786  *   gint i;
2787  *
2788  *   gbarray = g_byte_array_new ();
2789  *   for (i = 0; i < 10000; i++)
2790  *     g_byte_array_append (gbarray, (guint8*) "abcd", 4);
2791  *
2792  *   for (i = 0; i < 10000; i++)
2793  *     {
2794  *       g_assert (gbarray->data[4*i] == 'a');
2795  *       g_assert (gbarray->data[4*i+1] == 'b');
2796  *       g_assert (gbarray->data[4*i+2] == 'c');
2797  *       g_assert (gbarray->data[4*i+3] == 'd');
2798  *     }
2799  *
2800  *   g_byte_array_free (gbarray, TRUE);
2801  * ]|
2802  *
2803  * See #GBytes if you are interested in an immutable object representing a
2804  * sequence of bytes.
2805  */
2806
2807 /**
2808  * GByteArray:
2809  * @data: a pointer to the element data. The data may be moved as
2810  *     elements are added to the #GByteArray
2811  * @len: the number of elements in the #GByteArray
2812  *
2813  * Contains the public fields of a GByteArray.
2814  */
2815
2816 /**
2817  * g_byte_array_new:
2818  *
2819  * Creates a new #GByteArray with a reference count of 1.
2820  *
2821  * Returns: (transfer full): the new #GByteArray
2822  */
2823 GByteArray*
2824 g_byte_array_new (void)
2825 {
2826   return (GByteArray *)g_array_sized_new (FALSE, FALSE, 1, 0);
2827 }
2828
2829 /**
2830  * g_byte_array_steal:
2831  * @array: a #GByteArray.
2832  * @len: (optional) (out): pointer to retrieve the number of
2833  *    elements of the original array
2834  *
2835  * Frees the data in the array and resets the size to zero, while
2836  * the underlying array is preserved for use elsewhere and returned
2837  * to the caller.
2838  *
2839  * Returns: (transfer full): the element data, which should be
2840  *     freed using g_free().
2841  *
2842  * Since: 2.64
2843  */
2844 guint8 *
2845 g_byte_array_steal (GByteArray *array,
2846                     gsize *len)
2847 {
2848   return (guint8 *) g_array_steal ((GArray *) array, len);
2849 }
2850
2851 /**
2852  * g_byte_array_new_take:
2853  * @data: (transfer full) (array length=len): byte data for the array
2854  * @len: length of @data
2855  *
2856  * Creates a byte array containing the @data.
2857  * After this call, @data belongs to the #GByteArray and may no longer be
2858  * modified by the caller. The memory of @data has to be dynamically
2859  * allocated and will eventually be freed with g_free().
2860  *
2861  * Do not use it if @len is greater than %G_MAXUINT. #GByteArray
2862  * stores the length of its data in #guint, which may be shorter than
2863  * #gsize.
2864  *
2865  * Since: 2.32
2866  *
2867  * Returns: (transfer full): a new #GByteArray
2868  */
2869 GByteArray*
2870 g_byte_array_new_take (guint8 *data,
2871                        gsize   len)
2872 {
2873   GByteArray *array;
2874   GRealArray *real;
2875
2876   g_return_val_if_fail (len <= G_MAXUINT, NULL);
2877   array = g_byte_array_new ();
2878   real = (GRealArray *)array;
2879   g_assert (real->data == NULL);
2880   g_assert (real->len == 0);
2881
2882   real->data = data;
2883   real->len = len;
2884   real->elt_capacity = len;
2885
2886   return array;
2887 }
2888
2889 /**
2890  * g_byte_array_sized_new:
2891  * @reserved_size: number of bytes preallocated
2892  *
2893  * Creates a new #GByteArray with @reserved_size bytes preallocated.
2894  * This avoids frequent reallocation, if you are going to add many
2895  * bytes to the array. Note however that the size of the array is still
2896  * 0.
2897  *
2898  * Returns: the new #GByteArray
2899  */
2900 GByteArray*
2901 g_byte_array_sized_new (guint reserved_size)
2902 {
2903   return (GByteArray *)g_array_sized_new (FALSE, FALSE, 1, reserved_size);
2904 }
2905
2906 /**
2907  * g_byte_array_free:
2908  * @array: a #GByteArray
2909  * @free_segment: if %TRUE the actual byte data is freed as well
2910  *
2911  * Frees the memory allocated by the #GByteArray. If @free_segment is
2912  * %TRUE it frees the actual byte data. If the reference count of
2913  * @array is greater than one, the #GByteArray wrapper is preserved but
2914  * the size of @array will be set to zero.
2915  *
2916  * Returns: the element data if @free_segment is %FALSE, otherwise
2917  *          %NULL.  The element data should be freed using g_free().
2918  */
2919 guint8*
2920 g_byte_array_free (GByteArray *array,
2921                    gboolean    free_segment)
2922 {
2923   return (guint8 *)g_array_free ((GArray *)array, free_segment);
2924 }
2925
2926 /**
2927  * g_byte_array_free_to_bytes:
2928  * @array: (transfer full): a #GByteArray
2929  *
2930  * Transfers the data from the #GByteArray into a new immutable #GBytes.
2931  *
2932  * The #GByteArray is freed unless the reference count of @array is greater
2933  * than one, the #GByteArray wrapper is preserved but the size of @array
2934  * will be set to zero.
2935  *
2936  * This is identical to using g_bytes_new_take() and g_byte_array_free()
2937  * together.
2938  *
2939  * Since: 2.32
2940  *
2941  * Returns: (transfer full): a new immutable #GBytes representing same
2942  *     byte data that was in the array
2943  */
2944 GBytes*
2945 g_byte_array_free_to_bytes (GByteArray *array)
2946 {
2947   gsize length;
2948
2949   g_return_val_if_fail (array != NULL, NULL);
2950
2951   length = array->len;
2952   return g_bytes_new_take (g_byte_array_free (array, FALSE), length);
2953 }
2954
2955 /**
2956  * g_byte_array_ref:
2957  * @array: A #GByteArray
2958  *
2959  * Atomically increments the reference count of @array by one.
2960  * This function is thread-safe and may be called from any thread.
2961  *
2962  * Returns: The passed in #GByteArray
2963  *
2964  * Since: 2.22
2965  */
2966 GByteArray*
2967 g_byte_array_ref (GByteArray *array)
2968 {
2969   return (GByteArray *)g_array_ref ((GArray *)array);
2970 }
2971
2972 /**
2973  * g_byte_array_unref:
2974  * @array: A #GByteArray
2975  *
2976  * Atomically decrements the reference count of @array by one. If the
2977  * reference count drops to 0, all memory allocated by the array is
2978  * released. This function is thread-safe and may be called from any
2979  * thread.
2980  *
2981  * Since: 2.22
2982  */
2983 void
2984 g_byte_array_unref (GByteArray *array)
2985 {
2986   g_array_unref ((GArray *)array);
2987 }
2988
2989 /**
2990  * g_byte_array_append:
2991  * @array: a #GByteArray
2992  * @data: the byte data to be added
2993  * @len: the number of bytes to add
2994  *
2995  * Adds the given bytes to the end of the #GByteArray.
2996  * The array will grow in size automatically if necessary.
2997  *
2998  * Returns: the #GByteArray
2999  */
3000 GByteArray*
3001 g_byte_array_append (GByteArray   *array,
3002                      const guint8 *data,
3003                      guint         len)
3004 {
3005   g_array_append_vals ((GArray *)array, (guint8 *)data, len);
3006
3007   return array;
3008 }
3009
3010 /**
3011  * g_byte_array_prepend:
3012  * @array: a #GByteArray
3013  * @data: the byte data to be added
3014  * @len: the number of bytes to add
3015  *
3016  * Adds the given data to the start of the #GByteArray.
3017  * The array will grow in size automatically if necessary.
3018  *
3019  * Returns: the #GByteArray
3020  */
3021 GByteArray*
3022 g_byte_array_prepend (GByteArray   *array,
3023                       const guint8 *data,
3024                       guint         len)
3025 {
3026   g_array_prepend_vals ((GArray *)array, (guint8 *)data, len);
3027
3028   return array;
3029 }
3030
3031 /**
3032  * g_byte_array_set_size:
3033  * @array: a #GByteArray
3034  * @length: the new size of the #GByteArray
3035  *
3036  * Sets the size of the #GByteArray, expanding it if necessary.
3037  *
3038  * Returns: the #GByteArray
3039  */
3040 GByteArray*
3041 g_byte_array_set_size (GByteArray *array,
3042                        guint       length)
3043 {
3044   g_array_set_size ((GArray *)array, length);
3045
3046   return array;
3047 }
3048
3049 /**
3050  * g_byte_array_remove_index:
3051  * @array: a #GByteArray
3052  * @index_: the index of the byte to remove
3053  *
3054  * Removes the byte at the given index from a #GByteArray.
3055  * The following bytes are moved down one place.
3056  *
3057  * Returns: the #GByteArray
3058  **/
3059 GByteArray*
3060 g_byte_array_remove_index (GByteArray *array,
3061                            guint       index_)
3062 {
3063   g_array_remove_index ((GArray *)array, index_);
3064
3065   return array;
3066 }
3067
3068 /**
3069  * g_byte_array_remove_index_fast:
3070  * @array: a #GByteArray
3071  * @index_: the index of the byte to remove
3072  *
3073  * Removes the byte at the given index from a #GByteArray. The last
3074  * element in the array is used to fill in the space, so this function
3075  * does not preserve the order of the #GByteArray. But it is faster
3076  * than g_byte_array_remove_index().
3077  *
3078  * Returns: the #GByteArray
3079  */
3080 GByteArray*
3081 g_byte_array_remove_index_fast (GByteArray *array,
3082                                 guint       index_)
3083 {
3084   g_array_remove_index_fast ((GArray *)array, index_);
3085
3086   return array;
3087 }
3088
3089 /**
3090  * g_byte_array_remove_range:
3091  * @array: a @GByteArray
3092  * @index_: the index of the first byte to remove
3093  * @length: the number of bytes to remove
3094  *
3095  * Removes the given number of bytes starting at the given index from a
3096  * #GByteArray.  The following elements are moved to close the gap.
3097  *
3098  * Returns: the #GByteArray
3099  *
3100  * Since: 2.4
3101  */
3102 GByteArray*
3103 g_byte_array_remove_range (GByteArray *array,
3104                            guint       index_,
3105                            guint       length)
3106 {
3107   g_return_val_if_fail (array, NULL);
3108   g_return_val_if_fail (index_ <= array->len, NULL);
3109   g_return_val_if_fail (index_ + length <= array->len, NULL);
3110
3111   return (GByteArray *)g_array_remove_range ((GArray *)array, index_, length);
3112 }
3113
3114 /**
3115  * g_byte_array_sort:
3116  * @array: a #GByteArray
3117  * @compare_func: comparison function
3118  *
3119  * Sorts a byte array, using @compare_func which should be a
3120  * qsort()-style comparison function (returns less than zero for first
3121  * arg is less than second arg, zero for equal, greater than zero if
3122  * first arg is greater than second arg).
3123  *
3124  * If two array elements compare equal, their order in the sorted array
3125  * is undefined. If you want equal elements to keep their order (i.e.
3126  * you want a stable sort) you can write a comparison function that,
3127  * if two elements would otherwise compare equal, compares them by
3128  * their addresses.
3129  */
3130 void
3131 g_byte_array_sort (GByteArray   *array,
3132                    GCompareFunc  compare_func)
3133 {
3134   g_array_sort ((GArray *)array, compare_func);
3135 }
3136
3137 /**
3138  * g_byte_array_sort_with_data:
3139  * @array: a #GByteArray
3140  * @compare_func: comparison function
3141  * @user_data: data to pass to @compare_func
3142  *
3143  * Like g_byte_array_sort(), but the comparison function takes an extra
3144  * user data argument.
3145  */
3146 void
3147 g_byte_array_sort_with_data (GByteArray       *array,
3148                              GCompareDataFunc  compare_func,
3149                              gpointer          user_data)
3150 {
3151   g_array_sort_with_data ((GArray *)array, compare_func, user_data);
3152 }