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