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  * 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 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 "gslice.h"
  38 #include "gmem.h"
  39 #include "gtestutils.h"
  40 #include "gthread.h"
  41 #include "gmessages.h"
  42 #include "gqsort.h"
  43
  44
  45 /**
  46  * SECTION:arrays
  47  * @title: Arrays
  48  * @short_description: arrays of arbitrary elements which grow
  49  *     automatically as elements are added
  50  *
  51  * Arrays are similar to standard C arrays, except that they grow
  52  * automatically as elements are added.
  53  *
  54  * Array elements can be of any size (though all elements of one array
  55  * are the same size), and the array can be automatically cleared to
  56  * '0's and zero-terminated.
  57  *
  58  * To create a new array use g_array_new().
  59  *
  60  * To add elements to an array, use g_array_append_val(),
  61  * g_array_append_vals(), g_array_prepend_val(), and
  62  * g_array_prepend_vals().
  63  *
  64  * To access an element of an array, use g_array_index().
  65  *
  66  * To set the size of an array, use g_array_set_size().
  67  *
  68  * To free an array, use g_array_free().
  69  *
  70  * <example>
  71  *  <title>Using a #GArray to store #gint values</title>
  72  *  <programlisting>
  73  *   GArray *garray;
  74  *   gint i;
  75  *   /<!-- -->* We create a new array to store gint values.
  76  *      We don't want it zero-terminated or cleared to 0's. *<!-- -->/
  77  *   garray = g_array_new (FALSE, FALSE, sizeof (gint));
  78  *   for (i = 0; i &lt; 10000; i++)
  79  *     g_array_append_val (garray, i);
  80  *   for (i = 0; i &lt; 10000; i++)
  81  *     if (g_array_index (garray, gint, i) != i)
  82  *       g_print ("ERROR: got &percnt;d instead of &percnt;d\n",
  83  *                g_array_index (garray, gint, i), i);
  84  *   g_array_free (garray, TRUE);
  85  *  </programlisting>
  86  * </example>
  87  */
  88
  89 #define MIN_ARRAY_SIZE  16
  90
  91 typedef struct _GRealArray  GRealArray;
  92
  93 /**
  94  * GArray:
  95  * @data: a pointer to the element data. The data may be moved as
  96  *     elements are added to the #GArray.
  97  * @len: the number of elements in the #GArray not including the
  98  *     possible terminating zero element.
  99  *
 100  * Contains the public fields of a #GArray.
 101  */
 102 struct _GRealArray
 103 {
 104   guint8 *data;
 105   guint   len;
 106   guint   alloc;
 107   guint   elt_size;
 108   guint   zero_terminated : 1;
 109   guint   clear : 1;
 110   gint    ref_count;
 111   GDestroyNotify clear_func;
 112 };
 113
 114 /**
 115  * g_array_index:
 116  * @a: a #GArray
 117  * @t: the type of the elements
 118  * @i: the index of the element to return
 119  *
 120  * Returns the element of a #GArray at the given index. The return
 121  * value is cast to the given type.
 122  *
 123  * <example>
 124  *  <title>Getting a pointer to an element in a #GArray</title>
 125  *  <programlisting>
 126  *   EDayViewEvent *event;
 127  *   /<!-- -->* This gets a pointer to the 4th element
 128  *      in the array of EDayViewEvent structs. *<!-- -->/
 129  *   event = &amp;g_array_index (events, EDayViewEvent, 3);
 130  *  </programlisting>
 131  * </example>
 132  *
 133  * Returns: the element of the #GArray at the index given by @i
 134  */
 135
 136 #define g_array_elt_len(array,i) ((array)->elt_size * (i))
 137 #define g_array_elt_pos(array,i) ((array)->data + g_array_elt_len((array),(i)))
 138 #define g_array_elt_zero(array, pos, len)                               \
 139   (memset (g_array_elt_pos ((array), pos), 0,  g_array_elt_len ((array), len)))
 140 #define g_array_zero_terminate(array) G_STMT_START{                     \
 141   if ((array)->zero_terminated)                                         \
 142     g_array_elt_zero ((array), (array)->len, 1);                        \
 143 }G_STMT_END
 144
 145 static guint g_nearest_pow        (gint        num) G_GNUC_CONST;
 146 static void  g_array_maybe_expand (GRealArray *array,
 147                                    gint        len);
 148
 149 /**
 150  * g_array_new:
 151  * @zero_terminated: %TRUE if the array should have an extra element at
 152  *     the end which is set to 0
 153  * @clear_: %TRUE if #GArray elements should be automatically cleared
 154  *     to 0 when they are allocated
 155  * @element_size: the size of each element in bytes
 156  *
 157  * Creates a new #GArray with a reference count of 1.
 158  *
 159  * Returns: the new #GArray
 160  */
 161 GArray*
 162 g_array_new (gboolean zero_terminated,
 163              gboolean clear,
 164              guint    elt_size)
 165 {
 166   g_return_val_if_fail (elt_size > 0, NULL);
 167
 168   return g_array_sized_new (zero_terminated, clear, elt_size, 0);
 169 }
 170
 171 /**
 172  * g_array_sized_new:
 173  * @zero_terminated: %TRUE if the array should have an extra element at
 174  *     the end with all bits cleared
 175  * @clear_: %TRUE if all bits in the array should be cleared to 0 on
 176  *     allocation
 177  * @element_size: size of each element in the array
 178  * @reserved_size: number of elements preallocated
 179  *
 180  * Creates a new #GArray with @reserved_size elements preallocated and
 181  * a reference count of 1. This avoids frequent reallocation, if you
 182  * are going to add many elements to the array. Note however that the
 183  * size of the array is still 0.
 184  *
 185  * Returns: the new #GArray
 186  */
 187 GArray*
 188 g_array_sized_new (gboolean zero_terminated,
 189                    gboolean clear,
 190                    guint    elt_size,
 191                    guint    reserved_size)
 192 {
 193   GRealArray *array;
 194
 195   g_return_val_if_fail (elt_size > 0, NULL);
 196
 197   array = g_slice_new (GRealArray);
 198
 199   array->data            = NULL;
 200   array->len             = 0;
 201   array->alloc           = 0;
 202   array->zero_terminated = (zero_terminated ? 1 : 0);
 203   array->clear           = (clear ? 1 : 0);
 204   array->elt_size        = elt_size;
 205   array->ref_count       = 1;
 206   array->clear_func      = NULL;
 207
 208   if (array->zero_terminated || reserved_size != 0)
 209     {
 210       g_array_maybe_expand (array, reserved_size);
 211       g_array_zero_terminate(array);
 212     }
 213
 214   return (GArray*) array;
 215 }
 216
 217 /**
 218  * g_array_set_clear_func:
 219  * @array: A #GArray
 220  * @clear_func: a function to clear an element of @array
 221  *
 222  * Sets a function to clear an element of @array.
 223  *
 224  * The @clear_func will be called when an element in the array
 225  * data segment is removed and when the array is freed and data
 226  * segment is deallocated as well.
 227  *
 228  * Note that in contrast with other uses of #GDestroyNotify
 229  * functions, @clear_func is expected to clear the contents of
 230  * the array element it is given, but not free the element itself.
 231  *
 232  * Since: 2.32
 233  */
 234 void
 235 g_array_set_clear_func (GArray         *array,
 236                         GDestroyNotify  clear_func)
 237 {
 238   GRealArray *rarray = (GRealArray *) array;
 239
 240   g_return_if_fail (array != NULL);
 241
 242   rarray->clear_func = clear_func;
 243 }
 244
 245 /**
 246  * g_array_ref:
 247  * @array: A #GArray
 248  *
 249  * Atomically increments the reference count of @array by one.
 250  * This function is MT-safe and may be called from any thread.
 251  *
 252  * Returns: The passed in #GArray
 253  *
 254  * Since: 2.22
 255  */
 256 GArray *
 257 g_array_ref (GArray *array)
 258 {
 259   GRealArray *rarray = (GRealArray*) array;
 260   g_return_val_if_fail (array, NULL);
 261
 262   g_atomic_int_inc (&rarray->ref_count);
 263
 264   return array;
 265 }
 266
 267 typedef enum
 268 {
 269   FREE_SEGMENT = 1 << 0,
 270   PRESERVE_WRAPPER = 1 << 1
 271 } ArrayFreeFlags;
 272
 273 static gchar *array_free (GRealArray *, ArrayFreeFlags);
 274
 275 /**
 276  * g_array_unref:
 277  * @array: A #GArray
 278  *
 279  * Atomically decrements the reference count of @array by one. If the
 280  * reference count drops to 0, all memory allocated by the array is
 281  * released. This function is MT-safe and may be called from any
 282  * thread.
 283  *
 284  * Since: 2.22
 285  */
 286 void
 287 g_array_unref (GArray *array)
 288 {
 289   GRealArray *rarray = (GRealArray*) array;
 290   g_return_if_fail (array);
 291
 292   if (g_atomic_int_dec_and_test (&rarray->ref_count))
 293     array_free (rarray, FREE_SEGMENT);
 294 }
 295
 296 /**
 297  * g_array_get_element_size:
 298  * @array: A #GArray
 299  *
 300  * Gets the size of the elements in @array.
 301  *
 302  * Returns: Size of each element, in bytes
 303  *
 304  * Since: 2.22
 305  */
 306 guint
 307 g_array_get_element_size (GArray *array)
 308 {
 309   GRealArray *rarray = (GRealArray*) array;
 310
 311   g_return_val_if_fail (array, 0);
 312
 313   return rarray->elt_size;
 314 }
 315
 316 /**
 317  * g_array_free:
 318  * @array: a #GArray
 319  * @free_segment: if %TRUE the actual element data is freed as well
 320  *
 321  * Frees the memory allocated for the #GArray. If @free_segment is
 322  * %TRUE it frees the memory block holding the elements as well and
 323  * also each element if @array has a @element_free_func set. Pass
 324  * %FALSE if you want to free the #GArray wrapper but preserve the
 325  * underlying array for use elsewhere. If the reference count of @array
 326  * is greater than one, the #GArray wrapper is preserved but the size
 327  * of @array will be set to zero.
 328  *
 329  * If array elements contain dynamically-allocated memory, they should
 330  * be freed separately.
 331  *
 332  * Returns: the element data if @free_segment is %FALSE, otherwise
 333  *     %NULL. The element data should be freed using g_free().
 334  */
 335 gchar*
 336 g_array_free (GArray   *farray,
 337               gboolean  free_segment)
 338 {
 339   GRealArray *array = (GRealArray*) farray;
 340   ArrayFreeFlags flags;
 341
 342   g_return_val_if_fail (array, NULL);
 343
 344   flags = (free_segment ? FREE_SEGMENT : 0);
 345
 346   /* if others are holding a reference, preserve the wrapper but do free/return the data */
 347   if (!g_atomic_int_dec_and_test (&array->ref_count))
 348     flags |= PRESERVE_WRAPPER;
 349
 350   return array_free (array, flags);
 351 }
 352
 353 static gchar *
 354 array_free (GRealArray     *array,
 355             ArrayFreeFlags  flags)
 356 {
 357   gchar *segment;
 358
 359   if (flags & FREE_SEGMENT)
 360     {
 361       if (array->clear_func != NULL)
 362         {
 363           guint i;
 364
 365           for (i = 0; i < array->len; i++)
 366             array->clear_func (g_array_elt_pos (array, i));
 367         }
 368
 369       g_free (array->data);
 370       segment = NULL;
 371     }
 372   else
 373     segment = (gchar*) array->data;
 374
 375   if (flags & PRESERVE_WRAPPER)
 376     {
 377       array->data            = NULL;
 378       array->len             = 0;
 379       array->alloc           = 0;
 380     }
 381   else
 382     {
 383       g_slice_free1 (sizeof (GRealArray), array);
 384     }
 385
 386   return segment;
 387 }
 388
 389 /**
 390  * g_array_append_vals:
 391  * @array: a #GArray
 392  * @data: a pointer to the elements to append to the end of the array
 393  * @len: the number of elements to append
 394  *
 395  * Adds @len elements onto the end of the array.
 396  *
 397  * Returns: the #GArray
 398  */
 399 /**
 400  * g_array_append_val:
 401  * @a: a #GArray
 402  * @v: the value to append to the #GArray
 403  *
 404  * Adds the value on to the end of the array. The array will grow in
 405  * size automatically if necessary.
 406  *
 407  * g_array_append_val() is a macro which uses a reference to the value
 408  * parameter @v. This means that you cannot use it with literal values
 409  * such as "27". You must use variables.
 410  *
 411  * Returns: the #GArray
 412  */
 413 GArray*
 414 g_array_append_vals (GArray       *farray,
 415                      gconstpointer data,
 416                      guint         len)
 417 {
 418   GRealArray *array = (GRealArray*) farray;
 419
 420   g_return_val_if_fail (array, NULL);
 421
 422   g_array_maybe_expand (array, len);
 423
 424   memcpy (g_array_elt_pos (array, array->len), data,
 425           g_array_elt_len (array, len));
 426
 427   array->len += len;
 428
 429   g_array_zero_terminate (array);
 430
 431   return farray;
 432 }
 433
 434 /**
 435  * g_array_prepend_vals:
 436  * @array: a #GArray
 437  * @data: a pointer to the elements to prepend to the start of the array
 438  * @len: the number of elements to prepend
 439  *
 440  * Adds @len elements onto the start of the array.
 441  *
 442  * This operation is slower than g_array_append_vals() since the
 443  * existing elements in the array have to be moved to make space for
 444  * the new elements.
 445  *
 446  * Returns: the #GArray
 447  */
 448 /**
 449  * g_array_prepend_val:
 450  * @a: a #GArray
 451  * @v: the value to prepend to the #GArray
 452  *
 453  * Adds the value on to the start of the array. The array will grow in
 454  * size automatically if necessary.
 455  *
 456  * This operation is slower than g_array_append_val() since the
 457  * existing elements in the array have to be moved to make space for
 458  * the new element.
 459  *
 460  * g_array_prepend_val() is a macro which uses a reference to the value
 461  * parameter @v. This means that you cannot use it with literal values
 462  * such as "27". You must use variables.
 463  *
 464  * Returns: the #GArray
 465  */
 466 GArray*
 467 g_array_prepend_vals (GArray        *farray,
 468                       gconstpointer  data,
 469                       guint          len)
 470 {
 471   GRealArray *array = (GRealArray*) farray;
 472
 473   g_return_val_if_fail (array, NULL);
 474
 475   g_array_maybe_expand (array, len);
 476
 477   memmove (g_array_elt_pos (array, len), g_array_elt_pos (array, 0),
 478            g_array_elt_len (array, array->len));
 479
 480   memcpy (g_array_elt_pos (array, 0), data, g_array_elt_len (array, len));
 481
 482   array->len += len;
 483
 484   g_array_zero_terminate (array);
 485
 486   return farray;
 487 }
 488
 489 /**
 490  * g_array_insert_vals:
 491  * @array: a #GArray
 492  * @index_: the index to place the elements at
 493  * @data: a pointer to the elements to insert
 494  * @len: the number of elements to insert
 495  *
 496  * Inserts @len elements into a #GArray at the given index.
 497  *
 498  * Returns: the #GArray
 499  */
 500 /**
 501  * g_array_insert_val:
 502  * @a: a #GArray
 503  * @i: the index to place the element at
 504  * @v: the value to insert into the array
 505  *
 506  * Inserts an element into an array at the given index.
 507  *
 508  * g_array_insert_val() is a macro which uses a reference to the value
 509  * parameter @v. This means that you cannot use it with literal values
 510  * such as "27". You must use variables.
 511  *
 512  * Returns: the #GArray
 513  */
 514 GArray*
 515 g_array_insert_vals (GArray        *farray,
 516                      guint          index_,
 517                      gconstpointer  data,
 518                      guint          len)
 519 {
 520   GRealArray *array = (GRealArray*) farray;
 521
 522   g_return_val_if_fail (array, NULL);
 523
 524   g_array_maybe_expand (array, len);
 525
 526   memmove (g_array_elt_pos (array, len + index_),
 527            g_array_elt_pos (array, index_),
 528            g_array_elt_len (array, array->len - index_));
 529
 530   memcpy (g_array_elt_pos (array, index_), data, g_array_elt_len (array, len));
 531
 532   array->len += len;
 533
 534   g_array_zero_terminate (array);
 535
 536   return farray;
 537 }
 538
 539 /**
 540  * g_array_set_size:
 541  * @array: a #GArray
 542  * @length: the new size of the #GArray
 543  *
 544  * Sets the size of the array, expanding it if necessary. If the array
 545  * was created with @clear_ set to %TRUE, the new elements are set to 0.
 546  *
 547  * Returns: the #GArray
 548  */
 549 GArray*
 550 g_array_set_size (GArray *farray,
 551                   guint   length)
 552 {
 553   GRealArray *array = (GRealArray*) farray;
 554
 555   g_return_val_if_fail (array, NULL);
 556
 557   if (length > array->len)
 558     {
 559       g_array_maybe_expand (array, length - array->len);
 560
 561       if (array->clear)
 562         g_array_elt_zero (array, array->len, length - array->len);
 563     }
 564   else if (length < array->len)
 565     g_array_remove_range (farray, length, array->len - length);
 566
 567   array->len = length;
 568
 569   g_array_zero_terminate (array);
 570
 571   return farray;
 572 }
 573
 574 /**
 575  * g_array_remove_index:
 576  * @array: a #GArray
 577  * @index_: the index of the element to remove
 578  *
 579  * Removes the element at the given index from a #GArray. The following
 580  * elements are moved down one place.
 581  *
 582  * Returns: the #GArray
 583  */
 584 GArray*
 585 g_array_remove_index (GArray *farray,
 586                       guint   index_)
 587 {
 588   GRealArray* array = (GRealArray*) farray;
 589
 590   g_return_val_if_fail (array, NULL);
 591
 592   g_return_val_if_fail (index_ < array->len, NULL);
 593
 594   if (array->clear_func != NULL)
 595     array->clear_func (g_array_elt_pos (array, index_));
 596
 597   if (index_ != array->len - 1)
 598     memmove (g_array_elt_pos (array, index_),
 599              g_array_elt_pos (array, index_ + 1),
 600              g_array_elt_len (array, array->len - index_ - 1));
 601
 602   array->len -= 1;
 603
 604   if (G_UNLIKELY (g_mem_gc_friendly))
 605     g_array_elt_zero (array, array->len, 1);
 606   else
 607     g_array_zero_terminate (array);
 608
 609   return farray;
 610 }
 611
 612 /**
 613  * g_array_remove_index_fast:
 614  * @array: a @GArray
 615  * @index_: the index of the element to remove
 616  *
 617  * Removes the element at the given index from a #GArray. The last
 618  * element in the array is used to fill in the space, so this function
 619  * does not preserve the order of the #GArray. But it is faster than
 620  * g_array_remove_index().
 621  *
 622  * Returns: the #GArray
 623  */
 624 GArray*
 625 g_array_remove_index_fast (GArray *farray,
 626                            guint   index_)
 627 {
 628   GRealArray* array = (GRealArray*) farray;
 629
 630   g_return_val_if_fail (array, NULL);
 631
 632   g_return_val_if_fail (index_ < array->len, NULL);
 633
 634   if (array->clear_func != NULL)
 635     array->clear_func (g_array_elt_pos (array, index_));
 636
 637   if (index_ != array->len - 1)
 638     memcpy (g_array_elt_pos (array, index_),
 639             g_array_elt_pos (array, array->len - 1),
 640             g_array_elt_len (array, 1));
 641
 642   array->len -= 1;
 643
 644   if (G_UNLIKELY (g_mem_gc_friendly))
 645     g_array_elt_zero (array, array->len, 1);
 646   else
 647     g_array_zero_terminate (array);
 648
 649   return farray;
 650 }
 651
 652 /**
 653  * g_array_remove_range:
 654  * @array: a @GArray
 655  * @index_: the index of the first element to remove
 656  * @length: the number of elements to remove
 657  *
 658  * Removes the given number of elements starting at the given index
 659  * from a #GArray.  The following elements are moved to close the gap.
 660  *
 661  * Returns: the #GArray
 662  *
 663  * Since: 2.4
 664  */
 665 GArray*
 666 g_array_remove_range (GArray *farray,
 667                       guint   index_,
 668                       guint   length)
 669 {
 670   GRealArray *array = (GRealArray*) farray;
 671
 672   g_return_val_if_fail (array, NULL);
 673   g_return_val_if_fail (index_ < array->len, NULL);
 674   g_return_val_if_fail (index_ + length <= array->len, NULL);
 675
 676   if (array->clear_func != NULL)
 677     {
 678       guint i;
 679
 680       for (i = 0; i < length; i++)
 681         array->clear_func (g_array_elt_pos (array, index_ + i));
 682     }
 683
 684   if (index_ + length != array->len)
 685     memmove (g_array_elt_pos (array, index_),
 686              g_array_elt_pos (array, index_ + length),
 687              (array->len - (index_ + length)) * array->elt_size);
 688
 689   array->len -= length;
 690   if (G_UNLIKELY (g_mem_gc_friendly))
 691     g_array_elt_zero (array, array->len, length);
 692   else
 693     g_array_zero_terminate (array);
 694
 695   return farray;
 696 }
 697
 698 /**
 699  * g_array_sort:
 700  * @array: a #GArray
 701  * @compare_func: comparison function
 702  *
 703  * Sorts a #GArray using @compare_func which should be a qsort()-style
 704  * comparison function (returns less than zero for first arg is less
 705  * than second arg, zero for equal, greater zero if first arg is
 706  * greater than second arg).
 707  *
 708  * This is guaranteed to be a stable sort since version 2.32.
 709  */
 710 void
 711 g_array_sort (GArray       *farray,
 712               GCompareFunc  compare_func)
 713 {
 714   GRealArray *array = (GRealArray*) farray;
 715
 716   g_return_if_fail (array != NULL);
 717
 718   /* Don't use qsort as we want a guaranteed stable sort */
 719   g_qsort_with_data (array->data,
 720                      array->len,
 721                      array->elt_size,
 722                      (GCompareDataFunc)compare_func,
 723                      NULL);
 724 }
 725
 726 /**
 727  * g_array_sort_with_data:
 728  * @array: a #GArray
 729  * @compare_func: comparison function
 730  * @user_data: data to pass to @compare_func
 731  *
 732  * Like g_array_sort(), but the comparison function receives an extra
 733  * user data argument.
 734  *
 735  * This is guaranteed to be a stable sort since version 2.32.
 736  *
 737  * There used to be a comment here about making the sort stable by
 738  * using the addresses of the elements in the comparison function.
 739  * This did not actually work, so any such code should be removed.
 740  */
 741 void
 742 g_array_sort_with_data (GArray           *farray,
 743                         GCompareDataFunc  compare_func,
 744                         gpointer          user_data)
 745 {
 746   GRealArray *array = (GRealArray*) farray;
 747
 748   g_return_if_fail (array != NULL);
 749
 750   g_qsort_with_data (array->data,
 751                      array->len,
 752                      array->elt_size,
 753                      compare_func,
 754                      user_data);
 755 }
 756
 757 /* Returns the smallest power of 2 greater than n, or n if
 758  * such power does not fit in a guint
 759  */
 760 static guint
 761 g_nearest_pow (gint num)
 762 {
 763   guint n = 1;
 764
 765   while (n < num && n > 0)
 766     n <<= 1;
 767
 768   return n ? n : num;
 769 }
 770
 771 static void
 772 g_array_maybe_expand (GRealArray *array,
 773                       gint        len)
 774 {
 775   guint want_alloc = g_array_elt_len (array, array->len + len +
 776                                       array->zero_terminated);
 777
 778   if (want_alloc > array->alloc)
 779     {
 780       want_alloc = g_nearest_pow (want_alloc);
 781       want_alloc = MAX (want_alloc, MIN_ARRAY_SIZE);
 782
 783       array->data = g_realloc (array->data, want_alloc);
 784
 785       if (G_UNLIKELY (g_mem_gc_friendly))
 786         memset (array->data + array->alloc, 0, want_alloc - array->alloc);
 787
 788       array->alloc = want_alloc;
 789     }
 790 }
 791
 792 /**
 793  * SECTION:arrays_pointer
 794  * @title: Pointer Arrays
 795  * @short_description: arrays of pointers to any type of data, which
 796  *     grow automatically as new elements are added
 797  *
 798  * Pointer Arrays are similar to Arrays but are used only for storing
 799  * pointers.
 800  *
 801  * If you remove elements from the array, elements at the end of the
 802  * array are moved into the space previously occupied by the removed
 803  * element. This means that you should not rely on the index of particular
 804  * elements remaining the same. You should also be careful when deleting
 805  * elements while iterating over the array.
 806  *
 807  * To create a pointer array, use g_ptr_array_new().
 808  *
 809  * To add elements to a pointer array, use g_ptr_array_add().
 810  *
 811  * To remove elements from a pointer array, use g_ptr_array_remove(),
 812  * g_ptr_array_remove_index() or g_ptr_array_remove_index_fast().
 813  *
 814  * To access an element of a pointer array, use g_ptr_array_index().
 815  *
 816  * To set the size of a pointer array, use g_ptr_array_set_size().
 817  *
 818  * To free a pointer array, use g_ptr_array_free().
 819  *
 820  * <example>
 821  *  <title>Using a #GPtrArray</title>
 822  *  <programlisting>
 823  *   GPtrArray *gparray;
 824  *   gchar *string1 = "one", *string2 = "two", *string3 = "three";
 825  *
 826  *   gparray = g_ptr_array_new (<!-- -->);
 827  *   g_ptr_array_add (gparray, (gpointer) string1);
 828  *   g_ptr_array_add (gparray, (gpointer) string2);
 829  *   g_ptr_array_add (gparray, (gpointer) string3);
 830  *
 831  *   if (g_ptr_array_index (gparray, 0) != (gpointer) string1)
 832  *     g_print ("ERROR: got &percnt;p instead of &percnt;p\n",
 833  *              g_ptr_array_index (gparray, 0), string1);
 834  *
 835  *   g_ptr_array_free (gparray, TRUE);
 836  *  </programlisting>
 837  * </example>
 838  **/
 839
 840 typedef struct _GRealPtrArray  GRealPtrArray;
 841
 842 /**
 843  * GPtrArray:
 844  * @pdata: points to the array of pointers, which may be moved when the
 845  *     array grows
 846  * @len: number of pointers in the array
 847  *
 848  * Contains the public fields of a pointer array.
 849  */
 850 struct _GRealPtrArray
 851 {
 852   gpointer     *pdata;
 853   guint         len;
 854   guint         alloc;
 855   gint          ref_count;
 856   GDestroyNotify element_free_func;
 857 };
 858
 859 /**
 860  * g_ptr_array_index:
 861  * @array: a #GPtrArray
 862  * @index_: the index of the pointer to return
 863  *
 864  * Returns the pointer at the given index of the pointer array.
 865  *
 866  * This does not perform bounds checking on the given @index_,
 867  * so you are responsible for checking it against the array length.
 868  *
 869  * Returns: the pointer at the given index
 870  */
 871
 872 static void g_ptr_array_maybe_expand (GRealPtrArray *array,
 873                                       gint           len);
 874
 875 /**
 876  * g_ptr_array_new:
 877  *
 878  * Creates a new #GPtrArray with a reference count of 1.
 879  *
 880  * Returns: the new #GPtrArray
 881  */
 882 GPtrArray*
 883 g_ptr_array_new (void)
 884 {
 885   return g_ptr_array_sized_new (0);
 886 }
 887
 888 /**
 889  * g_ptr_array_sized_new:
 890  * @reserved_size: number of pointers preallocated
 891  *
 892  * Creates a new #GPtrArray with @reserved_size pointers preallocated
 893  * and a reference count of 1. This avoids frequent reallocation, if
 894  * you are going to add many pointers to the array. Note however that
 895  * the size of the array is still 0.
 896  *
 897  * Returns: the new #GPtrArray
 898  */
 899 GPtrArray*
 900 g_ptr_array_sized_new (guint reserved_size)
 901 {
 902   GRealPtrArray *array = g_slice_new (GRealPtrArray);
 903
 904   array->pdata = NULL;
 905   array->len = 0;
 906   array->alloc = 0;
 907   array->ref_count = 1;
 908   array->element_free_func = NULL;
 909
 910   if (reserved_size != 0)
 911     g_ptr_array_maybe_expand (array, reserved_size);
 912
 913   return (GPtrArray*) array;
 914 }
 915
 916 /**
 917  * g_ptr_array_new_with_free_func:
 918  * @element_free_func: (allow-none): A function to free elements with
 919  *     destroy @array or %NULL
 920  *
 921  * Creates a new #GPtrArray with a reference count of 1 and use
 922  * @element_free_func for freeing each element when the array is destroyed
 923  * either via g_ptr_array_unref(), when g_ptr_array_free() is called with
 924  * @free_segment set to %TRUE or when removing elements.
 925  *
 926  * Returns: A new #GPtrArray
 927  *
 928  * Since: 2.22
 929  */
 930 GPtrArray *
 931 g_ptr_array_new_with_free_func (GDestroyNotify element_free_func)
 932 {
 933   GPtrArray *array;
 934
 935   array = g_ptr_array_new ();
 936   g_ptr_array_set_free_func (array, element_free_func);
 937   return array;
 938 }
 939
 940 /**
 941  * g_ptr_array_new_full:
 942  * @reserved_size: number of pointers preallocated
 943  * @element_free_func: (allow-none): A function to free elements with
 944  *     destroy @array or %NULL
 945  *
 946  * Creates a new #GPtrArray with @reserved_size pointers preallocated
 947  * and a reference count of 1. This avoids frequent reallocation, if
 948  * you are going to add many pointers to the array. Note however that
 949  * the size of the array is still 0. It also set @element_free_func
 950  * for freeing each element when the array is destroyed either via
 951  * g_ptr_array_unref(), when g_ptr_array_free() is called with
 952  * @free_segment set to %TRUE or when removing elements.
 953  *
 954  * Returns: A new #GPtrArray
 955  *
 956  * Since: 2.30
 957  */
 958 GPtrArray *
 959 g_ptr_array_new_full (guint          reserved_size,
 960                       GDestroyNotify element_free_func)
 961 {
 962   GPtrArray *array;
 963
 964   array = g_ptr_array_sized_new (reserved_size);
 965   g_ptr_array_set_free_func (array, element_free_func);
 966   return array;
 967 }
 968
 969 /**
 970  * g_ptr_array_set_free_func:
 971  * @array: A #GPtrArray
 972  * @element_free_func: (allow-none): A function to free elements with
 973  *     destroy @array or %NULL
 974  *
 975  * Sets a function for freeing each element when @array is destroyed
 976  * either via g_ptr_array_unref(), when g_ptr_array_free() is called
 977  * with @free_segment set to %TRUE or when removing elements.
 978  *
 979  * Since: 2.22
 980  */
 981 void
 982 g_ptr_array_set_free_func (GPtrArray        *array,
 983                            GDestroyNotify    element_free_func)
 984 {
 985   GRealPtrArray* rarray = (GRealPtrArray*) array;
 986
 987   g_return_if_fail (array);
 988
 989   rarray->element_free_func = element_free_func;
 990 }
 991
 992 /**
 993  * g_ptr_array_ref:
 994  * @array: a #GPtrArray
 995  *
 996  * Atomically increments the reference count of @array by one.
 997  * This function is thread-safe and may be called from any thread.
 998  *
 999  * Returns: The passed in #GPtrArray
1000  *
1001  * Since: 2.22
1002  */
1003 GPtrArray *
1004 g_ptr_array_ref (GPtrArray *array)
1005 {
1006   GRealPtrArray *rarray = (GRealPtrArray*) array;
1007
1008   g_return_val_if_fail (array, NULL);
1009
1010   g_atomic_int_inc (&rarray->ref_count);
1011
1012   return array;
1013 }
1014
1015 static gpointer *ptr_array_free (GPtrArray *, ArrayFreeFlags);
1016
1017 /**
1018  * g_ptr_array_unref:
1019  * @array: A #GPtrArray
1020  *
1021  * Atomically decrements the reference count of @array by one. If the
1022  * reference count drops to 0, the effect is the same as calling
1023  * g_ptr_array_free() with @free_segment set to %TRUE. This function
1024  * is MT-safe and may be called from any thread.
1025  *
1026  * Since: 2.22
1027  */
1028 void
1029 g_ptr_array_unref (GPtrArray *array)
1030 {
1031   GRealPtrArray *rarray = (GRealPtrArray*) array;
1032   g_return_if_fail (array);
1033
1034   if (g_atomic_int_dec_and_test (&rarray->ref_count))
1035     ptr_array_free (array, FREE_SEGMENT);
1036 }
1037
1038 /**
1039  * g_ptr_array_free:
1040  * @array: a #GPtrArray
1041  * @free_seg: if %TRUE the actual pointer array is freed as well
1042  *
1043  * Frees the memory allocated for the #GPtrArray. If @free_seg is %TRUE
1044  * it frees the memory block holding the elements as well. Pass %FALSE
1045  * if you want to free the #GPtrArray wrapper but preserve the
1046  * underlying array for use elsewhere. If the reference count of @array
1047  * is greater than one, the #GPtrArray wrapper is preserved but the
1048  * size of @array will be set to zero.
1049  *
1050  * If array contents point to dynamically-allocated memory, they should
1051  * be freed separately if @free_seg is %TRUE and no #GDestroyNotify
1052  * function has been set for @array.
1053  *
1054  * Returns: the pointer array if @free_seg is %FALSE, otherwise %NULL.
1055  *     The pointer array should be freed using g_free().
1056  */
1057 gpointer*
1058 g_ptr_array_free (GPtrArray *farray,
1059                   gboolean   free_segment)
1060 {
1061   GRealPtrArray *array = (GRealPtrArray*) farray;
1062   ArrayFreeFlags flags;
1063
1064   g_return_val_if_fail (array, NULL);
1065
1066   flags = (free_segment ? FREE_SEGMENT : 0);
1067
1068   /* if others are holding a reference, preserve the wrapper but
1069    * do free/return the data
1070    */
1071   if (!g_atomic_int_dec_and_test (&array->ref_count))
1072     flags |= PRESERVE_WRAPPER;
1073
1074   return ptr_array_free (farray, flags);
1075 }
1076
1077 static gpointer *
1078 ptr_array_free (GPtrArray      *farray,
1079                 ArrayFreeFlags  flags)
1080 {
1081   GRealPtrArray *array = (GRealPtrArray*) farray;
1082   gpointer *segment;
1083
1084   if (flags & FREE_SEGMENT)
1085     {
1086       if (array->element_free_func != NULL)
1087         g_ptr_array_foreach (farray, (GFunc) array->element_free_func, NULL);
1088       g_free (array->pdata);
1089       segment = NULL;
1090     }
1091   else
1092     segment = array->pdata;
1093
1094   if (flags & PRESERVE_WRAPPER)
1095     {
1096       array->pdata = NULL;
1097       array->len = 0;
1098       array->alloc = 0;
1099     }
1100   else
1101     {
1102       g_slice_free1 (sizeof (GRealPtrArray), array);
1103     }
1104
1105   return segment;
1106 }
1107
1108 static void
1109 g_ptr_array_maybe_expand (GRealPtrArray *array,
1110                           gint           len)
1111 {
1112   if ((array->len + len) > array->alloc)
1113     {
1114       guint old_alloc = array->alloc;
1115       array->alloc = g_nearest_pow (array->len + len);
1116       array->alloc = MAX (array->alloc, MIN_ARRAY_SIZE);
1117       array->pdata = g_realloc (array->pdata, sizeof (gpointer) * array->alloc);
1118       if (G_UNLIKELY (g_mem_gc_friendly))
1119         for ( ; old_alloc < array->alloc; old_alloc++)
1120           array->pdata [old_alloc] = NULL;
1121     }
1122 }
1123
1124 /**
1125  * g_ptr_array_set_size:
1126  * @array: a #GPtrArray
1127  * @length: the new length of the pointer array
1128  *
1129  * Sets the size of the array. When making the array larger,
1130  * newly-added elements will be set to %NULL. When making it smaller,
1131  * if @array has a non-%NULL #GDestroyNotify function then it will be
1132  * called for the removed elements.
1133  */
1134 void
1135 g_ptr_array_set_size  (GPtrArray *farray,
1136                        gint       length)
1137 {
1138   GRealPtrArray* array = (GRealPtrArray*) farray;
1139
1140   g_return_if_fail (array);
1141
1142   if (length > array->len)
1143     {
1144       int i;
1145       g_ptr_array_maybe_expand (array, (length - array->len));
1146       /* This is not
1147        *     memset (array->pdata + array->len, 0,
1148        *            sizeof (gpointer) * (length - array->len));
1149        * to make it really portable. Remember (void*)NULL needn't be
1150        * bitwise zero. It of course is silly not to use memset (..,0,..).
1151        */
1152       for (i = array->len; i < length; i++)
1153         array->pdata[i] = NULL;
1154     }
1155   else if (length < array->len)
1156     g_ptr_array_remove_range (farray, length, array->len - length);
1157
1158   array->len = length;
1159 }
1160
1161 /**
1162  * g_ptr_array_remove_index:
1163  * @array: a #GPtrArray
1164  * @index_: the index of the pointer to remove
1165  *
1166  * Removes the pointer at the given index from the pointer array.
1167  * The following elements are moved down one place. If @array has
1168  * a non-%NULL #GDestroyNotify function it is called for the removed
1169  * element.
1170  *
1171  * Returns: the pointer which was removed
1172  */
1173 gpointer
1174 g_ptr_array_remove_index (GPtrArray *farray,
1175                           guint      index_)
1176 {
1177   GRealPtrArray* array = (GRealPtrArray*) farray;
1178   gpointer result;
1179
1180   g_return_val_if_fail (array, NULL);
1181
1182   g_return_val_if_fail (index_ < array->len, NULL);
1183
1184   result = array->pdata[index_];
1185
1186   if (array->element_free_func != NULL)
1187     array->element_free_func (array->pdata[index_]);
1188
1189   if (index_ != array->len - 1)
1190     memmove (array->pdata + index_, array->pdata + index_ + 1,
1191              sizeof (gpointer) * (array->len - index_ - 1));
1192
1193   array->len -= 1;
1194
1195   if (G_UNLIKELY (g_mem_gc_friendly))
1196     array->pdata[array->len] = NULL;
1197
1198   return result;
1199 }
1200
1201 /**
1202  * g_ptr_array_remove_index_fast:
1203  * @array: a #GPtrArray
1204  * @index_: the index of the pointer to remove
1205  *
1206  * Removes the pointer at the given index from the pointer array.
1207  * The last element in the array is used to fill in the space, so
1208  * this function does not preserve the order of the array. But it
1209  * is faster than g_ptr_array_remove_index(). If @array has a non-%NULL
1210  * #GDestroyNotify function it is called for the removed element.
1211  *
1212  * Returns: the pointer which was removed
1213  */
1214 gpointer
1215 g_ptr_array_remove_index_fast (GPtrArray *farray,
1216                                guint      index_)
1217 {
1218   GRealPtrArray* array = (GRealPtrArray*) farray;
1219   gpointer result;
1220
1221   g_return_val_if_fail (array, NULL);
1222
1223   g_return_val_if_fail (index_ < array->len, NULL);
1224
1225   result = array->pdata[index_];
1226
1227   if (array->element_free_func != NULL)
1228     array->element_free_func (array->pdata[index_]);
1229
1230   if (index_ != array->len - 1)
1231     array->pdata[index_] = array->pdata[array->len - 1];
1232
1233   array->len -= 1;
1234
1235   if (G_UNLIKELY (g_mem_gc_friendly))
1236     array->pdata[array->len] = NULL;
1237
1238   return result;
1239 }
1240
1241 /**
1242  * g_ptr_array_remove_range:
1243  * @array: a @GPtrArray
1244  * @index_: the index of the first pointer to remove
1245  * @length: the number of pointers to remove
1246  *
1247  * Removes the given number of pointers starting at the given index
1248  * from a #GPtrArray.  The following elements are moved to close the
1249  * gap. If @array has a non-%NULL #GDestroyNotify function it is called
1250  * for the removed elements.
1251  *
1252  * Returns: the @array
1253  *
1254  * Since: 2.4
1255  */
1256 GPtrArray *
1257 g_ptr_array_remove_range (GPtrArray *farray,
1258                           guint      index_,
1259                           guint      length)
1260 {
1261   GRealPtrArray* array = (GRealPtrArray*) farray;
1262   guint n;
1263
1264   g_return_val_if_fail (array != NULL, NULL);
1265   g_return_val_if_fail (index_ < array->len, NULL);
1266   g_return_val_if_fail (index_ + length <= array->len, NULL);
1267
1268   if (array->element_free_func != NULL)
1269     {
1270       for (n = index_; n < index_ + length; n++)
1271         array->element_free_func (array->pdata[n]);
1272     }
1273
1274   if (index_ + length != array->len)
1275     {
1276       memmove (&array->pdata[index_],
1277                &array->pdata[index_ + length],
1278                (array->len - (index_ + length)) * sizeof (gpointer));
1279     }
1280
1281   array->len -= length;
1282   if (G_UNLIKELY (g_mem_gc_friendly))
1283     {
1284       guint i;
1285       for (i = 0; i < length; i++)
1286         array->pdata[array->len + i] = NULL;
1287     }
1288
1289   return farray;
1290 }
1291
1292 /**
1293  * g_ptr_array_remove:
1294  * @array: a #GPtrArray
1295  * @data: the pointer to remove
1296  *
1297  * Removes the first occurrence of the given pointer from the pointer
1298  * array. The following elements are moved down one place. If @array
1299  * has a non-%NULL #GDestroyNotify function it is called for the
1300  * removed element.
1301  *
1302  * It returns %TRUE if the pointer was removed, or %FALSE if the
1303  * pointer was not found.
1304  *
1305  * Returns: %TRUE if the pointer is removed, %FALSE if the pointer
1306  *     is not found in the array
1307  */
1308 gboolean
1309 g_ptr_array_remove (GPtrArray *farray,
1310                     gpointer   data)
1311 {
1312   GRealPtrArray* array = (GRealPtrArray*) farray;
1313   guint i;
1314
1315   g_return_val_if_fail (array, FALSE);
1316
1317   for (i = 0; i < array->len; i += 1)
1318     {
1319       if (array->pdata[i] == data)
1320         {
1321           g_ptr_array_remove_index (farray, i);
1322           return TRUE;
1323         }
1324     }
1325
1326   return FALSE;
1327 }
1328
1329 /**
1330  * g_ptr_array_remove_fast:
1331  * @array: a #GPtrArray
1332  * @data: the pointer to remove
1333  *
1334  * Removes the first occurrence of the given pointer from the pointer
1335  * array. The last element in the array is used to fill in the space,
1336  * so this function does not preserve the order of the array. But it
1337  * is faster than g_ptr_array_remove(). If @array has a non-%NULL
1338  * #GDestroyNotify function it is called for the removed element.
1339  *
1340  * It returns %TRUE if the pointer was removed, or %FALSE if the
1341  * pointer was not found.
1342  *
1343  * Returns: %TRUE if the pointer was found in the array
1344  */
1345 gboolean
1346 g_ptr_array_remove_fast (GPtrArray *farray,
1347                          gpointer   data)
1348 {
1349   GRealPtrArray* array = (GRealPtrArray*) farray;
1350   guint i;
1351
1352   g_return_val_if_fail (array, FALSE);
1353
1354   for (i = 0; i < array->len; i += 1)
1355     {
1356       if (array->pdata[i] == data)
1357         {
1358           g_ptr_array_remove_index_fast (farray, i);
1359           return TRUE;
1360         }
1361     }
1362
1363   return FALSE;
1364 }
1365
1366 /**
1367  * g_ptr_array_add:
1368  * @array: a #GPtrArray
1369  * @data: the pointer to add
1370  *
1371  * Adds a pointer to the end of the pointer array. The array will grow
1372  * in size automatically if necessary.
1373  */
1374 void
1375 g_ptr_array_add (GPtrArray *farray,
1376                  gpointer   data)
1377 {
1378   GRealPtrArray* array = (GRealPtrArray*) farray;
1379
1380   g_return_if_fail (array);
1381
1382   g_ptr_array_maybe_expand (array, 1);
1383
1384   array->pdata[array->len++] = data;
1385 }
1386
1387 /**
1388  * g_ptr_array_insert:
1389  * @array: a #GPtrArray
1390  * @index_: the index to place the new element at, or -1 to append
1391  * @data: the pointer to add.
1392  *
1393  * Inserts an element into the pointer array at the given index. The
1394  * array will grow in size automatically if necessary.
1395  *
1396  * Since: 2.40
1397  */
1398 void
1399 g_ptr_array_insert (GPtrArray *farray,
1400                     gint       index_,
1401                     gpointer   data)
1402 {
1403   GRealPtrArray* array = (GRealPtrArray*) farray;
1404
1405   g_return_if_fail (array);
1406   g_return_if_fail (index_ >= -1);
1407   g_return_if_fail (index_ <= (gint)array->len);
1408
1409   g_ptr_array_maybe_expand (array, 1);
1410
1411   if (index_ < 0)
1412     index_ = array->len;
1413
1414   if (index_ < array->len)
1415     memmove (&(array->pdata[index_ + 1]),
1416              &(array->pdata[index_]),
1417              (array->len - index_) * sizeof (gpointer));
1418
1419   array->len++;
1420   array->pdata[index_] = data;
1421 }
1422
1423 /**
1424  * g_ptr_array_sort:
1425  * @array: a #GPtrArray
1426  * @compare_func: comparison function
1427  *
1428  * Sorts the array, using @compare_func which should be a qsort()-style
1429  * comparison function (returns less than zero for first arg is less
1430  * than second arg, zero for equal, greater than zero if irst arg is
1431  * greater than second arg).
1432  *
1433  * Note that the comparison function for g_ptr_array_sort() doesn't
1434  * take the pointers from the array as arguments, it takes pointers to
1435  * the pointers in the array.
1436  *
1437  * This is guaranteed to be a stable sort since version 2.32.
1438  */
1439 void
1440 g_ptr_array_sort (GPtrArray    *array,
1441                   GCompareFunc  compare_func)
1442 {
1443   g_return_if_fail (array != NULL);
1444
1445   /* Don't use qsort as we want a guaranteed stable sort */
1446   g_qsort_with_data (array->pdata,
1447                      array->len,
1448                      sizeof (gpointer),
1449                      (GCompareDataFunc)compare_func,
1450                      NULL);
1451 }
1452
1453 /**
1454  * g_ptr_array_sort_with_data:
1455  * @array: a #GPtrArray
1456  * @compare_func: comparison function
1457  * @user_data: data to pass to @compare_func
1458  *
1459  * Like g_ptr_array_sort(), but the comparison function has an extra
1460  * user data argument.
1461  *
1462  * Note that the comparison function for g_ptr_array_sort_with_data()
1463  * doesn't take the pointers from the array as arguments, it takes
1464  * pointers to the pointers in the array.
1465  *
1466  * This is guaranteed to be a stable sort since version 2.32.
1467  */
1468 void
1469 g_ptr_array_sort_with_data (GPtrArray        *array,
1470                             GCompareDataFunc  compare_func,
1471                             gpointer          user_data)
1472 {
1473   g_return_if_fail (array != NULL);
1474
1475   g_qsort_with_data (array->pdata,
1476                      array->len,
1477                      sizeof (gpointer),
1478                      compare_func,
1479                      user_data);
1480 }
1481
1482 /**
1483  * g_ptr_array_foreach:
1484  * @array: a #GPtrArray
1485  * @func: the function to call for each array element
1486  * @user_data: user data to pass to the function
1487  *
1488  * Calls a function for each element of a #GPtrArray.
1489  *
1490  * Since: 2.4
1491  */
1492 void
1493 g_ptr_array_foreach (GPtrArray *array,
1494                      GFunc      func,
1495                      gpointer   user_data)
1496 {
1497   guint i;
1498
1499   g_return_if_fail (array);
1500
1501   for (i = 0; i < array->len; i++)
1502     (*func) (array->pdata[i], user_data);
1503 }
1504
1505 /**
1506  * SECTION:arrays_byte
1507  * @title: Byte Arrays
1508  * @short_description: arrays of bytes
1509  *
1510  * #GByteArray is a mutable array of bytes based on #GArray, to provide arrays
1511  * of bytes which grow automatically as elements are added.
1512  *
1513  * To create a new #GByteArray use g_byte_array_new(). To add elements to a
1514  * #GByteArray, use g_byte_array_append(), and g_byte_array_prepend().
1515  *
1516  * To set the size of a #GByteArray, use g_byte_array_set_size().
1517  *
1518  * To free a #GByteArray, use g_byte_array_free().
1519  *
1520  * <example>
1521  *  <title>Using a #GByteArray</title>
1522  *  <programlisting>
1523  *   GByteArray *gbarray;
1524  *   gint i;
1525  *
1526  *   gbarray = g_byte_array_new (<!-- -->);
1527  *   for (i = 0; i &lt; 10000; i++)
1528  *     g_byte_array_append (gbarray, (guint8*) "abcd", 4);
1529  *
1530  *   for (i = 0; i &lt; 10000; i++)
1531  *     {
1532  *       g_assert (gbarray->data[4*i] == 'a');
1533  *       g_assert (gbarray->data[4*i+1] == 'b');
1534  *       g_assert (gbarray->data[4*i+2] == 'c');
1535  *       g_assert (gbarray->data[4*i+3] == 'd');
1536  *     }
1537  *
1538  *   g_byte_array_free (gbarray, TRUE);
1539  *  </programlisting>
1540  * </example>
1541  *
1542  * See #GBytes if you are interested in an immutable object representing a
1543  * sequence of bytes.
1544  */
1545
1546 /**
1547  * GByteArray:
1548  * @data: a pointer to the element data. The data may be moved as
1549  *     elements are added to the #GByteArray
1550  * @len: the number of elements in the #GByteArray
1551  *
1552  * The #GByteArray-struct allows access to the public fields of
1553  * a #GByteArray.
1554  */
1555
1556 /**
1557  * g_byte_array_new:
1558  *
1559  * Creates a new #GByteArray with a reference count of 1.
1560  *
1561  * Returns: (transfer full): the new #GByteArray
1562  */
1563 GByteArray*
1564 g_byte_array_new (void)
1565 {
1566   return (GByteArray*) g_array_sized_new (FALSE, FALSE, 1, 0);
1567 }
1568
1569 /**
1570  * g_byte_array_new_take:
1571  * @data: (transfer full) (array length=len): byte data for the array
1572  * @len: length of @data
1573  *
1574  * Create byte array containing the data. The data will be owned by the array
1575  * and will be freed with g_free(), i.e. it could be allocated using g_strdup().
1576  *
1577  * Since: 2.32
1578  *
1579  * Returns: (transfer full): a new #GByteArray
1580  */
1581 GByteArray *
1582 g_byte_array_new_take (guint8 *data,
1583                        gsize   len)
1584 {
1585   GByteArray *array;
1586   GRealArray *real;
1587
1588   array = g_byte_array_new ();
1589   real = (GRealArray *)array;
1590   g_assert (real->data == NULL);
1591   g_assert (real->len == 0);
1592
1593   real->data = data;
1594   real->len = len;
1595
1596   return array;
1597 }
1598
1599 /**
1600  * g_byte_array_sized_new:
1601  * @reserved_size: number of bytes preallocated
1602  *
1603  * Creates a new #GByteArray with @reserved_size bytes preallocated.
1604  * This avoids frequent reallocation, if you are going to add many
1605  * bytes to the array. Note however that the size of the array is still
1606  * 0.
1607  *
1608  * Returns: the new #GByteArray
1609  */
1610 GByteArray*
1611 g_byte_array_sized_new (guint reserved_size)
1612 {
1613   return (GByteArray*) g_array_sized_new (FALSE, FALSE, 1, reserved_size);
1614 }
1615
1616 /**
1617  * g_byte_array_free:
1618  * @array: a #GByteArray
1619  * @free_segment: if %TRUE the actual byte data is freed as well
1620  *
1621  * Frees the memory allocated by the #GByteArray. If @free_segment is
1622  * %TRUE it frees the actual byte data. If the reference count of
1623  * @array is greater than one, the #GByteArray wrapper is preserved but
1624  * the size of @array will be set to zero.
1625  *
1626  * Returns: the element data if @free_segment is %FALSE, otherwise
1627  *          %NULL.  The element data should be freed using g_free().
1628  */
1629 guint8*
1630 g_byte_array_free (GByteArray *array,
1631                    gboolean    free_segment)
1632 {
1633   return (guint8*) g_array_free ((GArray*) array, free_segment);
1634 }
1635
1636 /**
1637  * g_byte_array_free_to_bytes:
1638  * @array: (transfer full): a #GByteArray
1639  *
1640  * Transfers the data from the #GByteArray into a new immutable #GBytes.
1641  *
1642  * The #GByteArray is freed unless the reference count of @array is greater
1643  * than one, the #GByteArray wrapper is preserved but the size of @array
1644  * will be set to zero.
1645  *
1646  * This is identical to using g_bytes_new_take() and g_byte_array_free()
1647  * together.
1648  *
1649  * Since: 2.32
1650  *
1651  * Returns: (transfer full): a new immutable #GBytes representing same
1652  *     byte data that was in the array
1653  */
1654 GBytes *
1655 g_byte_array_free_to_bytes (GByteArray *array)
1656 {
1657   gsize length;
1658
1659   g_return_val_if_fail (array != NULL, NULL);
1660
1661   length = array->len;
1662   return g_bytes_new_take (g_byte_array_free (array, FALSE), length);
1663 }
1664
1665 /**
1666  * g_byte_array_ref:
1667  * @array: A #GByteArray
1668  *
1669  * Atomically increments the reference count of @array by one. This
1670  * function is MT-safe and may be called from any thread.
1671  *
1672  * Returns: The passed in #GByteArray
1673  *
1674  * Since: 2.22
1675  */
1676 GByteArray *
1677 g_byte_array_ref (GByteArray *array)
1678 {
1679   return (GByteArray *) g_array_ref ((GArray *) array);
1680 }
1681
1682 /**
1683  * g_byte_array_unref:
1684  * @array: A #GByteArray
1685  *
1686  * Atomically decrements the reference count of @array by one. If the
1687  * reference count drops to 0, all memory allocated by the array is
1688  * released. This function is MT-safe and may be called from any
1689  * thread.
1690  *
1691  * Since: 2.22
1692  */
1693 void
1694 g_byte_array_unref (GByteArray *array)
1695 {
1696   g_array_unref ((GArray *) array);
1697 }
1698
1699 /**
1700  * g_byte_array_append:
1701  * @array: a #GByteArray
1702  * @data: the byte data to be added
1703  * @len: the number of bytes to add
1704  *
1705  * Adds the given bytes to the end of the #GByteArray. The array will
1706  * grow in size automatically if necessary.
1707  *
1708  * Returns: the #GByteArray
1709  */
1710 GByteArray*
1711 g_byte_array_append (GByteArray   *array,
1712                      const guint8 *data,
1713                      guint         len)
1714 {
1715   g_array_append_vals ((GArray*) array, (guint8*)data, len);
1716
1717   return array;
1718 }
1719
1720 /**
1721  * g_byte_array_prepend:
1722  * @array: a #GByteArray
1723  * @data: the byte data to be added
1724  * @len: the number of bytes to add
1725  *
1726  * Adds the given data to the start of the #GByteArray. The array will
1727  * grow in size automatically if necessary.
1728  *
1729  * Returns: the #GByteArray
1730  */
1731 GByteArray*
1732 g_byte_array_prepend (GByteArray   *array,
1733                       const guint8 *data,
1734                       guint         len)
1735 {
1736   g_array_prepend_vals ((GArray*) array, (guint8*)data, len);
1737
1738   return array;
1739 }
1740
1741 /**
1742  * g_byte_array_set_size:
1743  * @array: a #GByteArray
1744  * @length: the new size of the #GByteArray
1745  *
1746  * Sets the size of the #GByteArray, expanding it if necessary.
1747  *
1748  * Returns: the #GByteArray
1749  */
1750 GByteArray*
1751 g_byte_array_set_size (GByteArray *array,
1752                        guint       length)
1753 {
1754   g_array_set_size ((GArray*) array, length);
1755
1756   return array;
1757 }
1758
1759 /**
1760  * g_byte_array_remove_index:
1761  * @array: a #GByteArray
1762  * @index_: the index of the byte to remove
1763  *
1764  * Removes the byte at the given index from a #GByteArray. The
1765  * following bytes are moved down one place.
1766  *
1767  * Returns: the #GByteArray
1768  **/
1769 GByteArray*
1770 g_byte_array_remove_index (GByteArray *array,
1771                            guint       index_)
1772 {
1773   g_array_remove_index ((GArray*) array, index_);
1774
1775   return array;
1776 }
1777
1778 /**
1779  * g_byte_array_remove_index_fast:
1780  * @array: a #GByteArray
1781  * @index_: the index of the byte to remove
1782  *
1783  * Removes the byte at the given index from a #GByteArray. The last
1784  * element in the array is used to fill in the space, so this function
1785  * does not preserve the order of the #GByteArray. But it is faster
1786  * than g_byte_array_remove_index().
1787  *
1788  * Returns: the #GByteArray
1789  */
1790 GByteArray*
1791 g_byte_array_remove_index_fast (GByteArray *array,
1792                                 guint       index_)
1793 {
1794   g_array_remove_index_fast ((GArray*) array, index_);
1795
1796   return array;
1797 }
1798
1799 /**
1800  * g_byte_array_remove_range:
1801  * @array: a @GByteArray
1802  * @index_: the index of the first byte to remove
1803  * @length: the number of bytes to remove
1804  *
1805  * Removes the given number of bytes starting at the given index from a
1806  * #GByteArray.  The following elements are moved to close the gap.
1807  *
1808  * Returns: the #GByteArray
1809  *
1810  * Since: 2.4
1811  */
1812 GByteArray*
1813 g_byte_array_remove_range (GByteArray *array,
1814                            guint       index_,
1815                            guint       length)
1816 {
1817   g_return_val_if_fail (array, NULL);
1818   g_return_val_if_fail (index_ < array->len, NULL);
1819   g_return_val_if_fail (index_ + length <= array->len, NULL);
1820
1821   return (GByteArray *)g_array_remove_range ((GArray*) array, index_, length);
1822 }
1823
1824 /**
1825  * g_byte_array_sort:
1826  * @array: a #GByteArray
1827  * @compare_func: comparison function
1828  *
1829  * Sorts a byte array, using @compare_func which should be a
1830  * qsort()-style comparison function (returns less than zero for first
1831  * arg is less than second arg, zero for equal, greater than zero if
1832  * first arg is greater than second arg).
1833  *
1834  * If two array elements compare equal, their order in the sorted array
1835  * is undefined. If you want equal elements to keep their order (i.e.
1836  * you want a stable sort) you can write a comparison function that,
1837  * if two elements would otherwise compare equal, compares them by
1838  * their addresses.
1839  */
1840 void
1841 g_byte_array_sort (GByteArray   *array,
1842                    GCompareFunc  compare_func)
1843 {
1844   g_array_sort ((GArray *) array, compare_func);
1845 }
1846
1847 /**
1848  * g_byte_array_sort_with_data:
1849  * @array: a #GByteArray
1850  * @compare_func: comparison function
1851  * @user_data: data to pass to @compare_func
1852  *
1853  * Like g_byte_array_sort(), but the comparison function takes an extra
1854  * user data argument.
1855  */
1856 void
1857 g_byte_array_sort_with_data (GByteArray       *array,
1858                              GCompareDataFunc  compare_func,
1859                              gpointer          user_data)
1860 {
1861   g_array_sort_with_data ((GArray *) array, compare_func, user_data);
1862 }