garray.c 62.5 KB
Newer Older
Owen Taylor's avatar
Owen Taylor committed
1 2 3 4
/* GLIB - Library of useful routines for C programming
 * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
 *
 * This library is free software; you can redistribute it and/or
5
 * modify it under the terms of the GNU Lesser General Public
Owen Taylor's avatar
Owen Taylor committed
6
 * License as published by the Free Software Foundation; either
7
 * version 2.1 of the License, or (at your option) any later version.
Owen Taylor's avatar
Owen Taylor committed
8 9 10 11
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12
 * Lesser General Public License for more details.
Owen Taylor's avatar
Owen Taylor committed
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/>.
Owen Taylor's avatar
Owen Taylor committed
16
 */
17

18
/*
19
 * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
20 21 22 23 24
 * file for a list of people on the GLib Team.  See the ChangeLog
 * files for a list of changes.  These files are distributed with
 * GLib at ftp://ftp.gtk.org/pub/gtk/. 
 */

25 26 27 28
/* 
 * MT safe
 */

29
#include "config.h"
30

Owen Taylor's avatar
Owen Taylor committed
31
#include <string.h>
32
#include <stdlib.h>
33 34 35

#include "garray.h"

36
#include "gbytes.h"
37
#include "ghash.h"
38
#include "gslice.h"
39
#include "gmem.h"
40
#include "gtestutils.h"
41 42 43
#include "gthread.h"
#include "gmessages.h"
#include "gqsort.h"
44
#include "grefcount.h"
Owen Taylor's avatar
Owen Taylor committed
45

46
/**
47
 * SECTION:arrays
48 49
 * @title: Arrays
 * @short_description: arrays of arbitrary elements which grow
50
 *     automatically as elements are added
51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
 *
 * Arrays are similar to standard C arrays, except that they grow
 * automatically as elements are added.
 *
 * Array elements can be of any size (though all elements of one array
 * are the same size), and the array can be automatically cleared to
 * '0's and zero-terminated.
 *
 * To create a new array use g_array_new().
 *
 * To add elements to an array, use g_array_append_val(),
 * g_array_append_vals(), g_array_prepend_val(), and
 * g_array_prepend_vals().
 *
 * To access an element of an array, use g_array_index().
 *
 * To set the size of an array, use g_array_set_size().
 *
 * To free an array, use g_array_free().
 *
71
 * Here is an example that stores integers in a #GArray:
72
 * |[<!-- language="C" -->
73 74
 *   GArray *garray;
 *   gint i;
Matthias Clasen's avatar
Matthias Clasen committed
75 76
 *   // We create a new array to store gint values.
 *   // 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 < 10000; i++)
79
 *     g_array_append_val (garray, i);
80
 *   for (i = 0; i < 10000; i++)
81
 *     if (g_array_index (garray, gint, i) != i)
82
 *       g_print ("ERROR: got %d instead of %d\n",
83 84
 *                g_array_index (garray, gint, i), i);
 *   g_array_free (garray, TRUE);
85
 * ]|
86
 */
Owen Taylor's avatar
Owen Taylor committed
87 88 89 90 91

#define MIN_ARRAY_SIZE  16

typedef struct _GRealArray  GRealArray;

92 93 94
/**
 * GArray:
 * @data: a pointer to the element data. The data may be moved as
95
 *     elements are added to the #GArray.
96
 * @len: the number of elements in the #GArray not including the
97
 *     possible terminating zero element.
98
 *
99
 * Contains the public fields of a GArray.
100
 */
Owen Taylor's avatar
Owen Taylor committed
101 102 103 104 105
struct _GRealArray
{
  guint8 *data;
  guint   len;
  guint   alloc;
106 107 108
  guint   elt_size;
  guint   zero_terminated : 1;
  guint   clear : 1;
109
  gatomicrefcount ref_count;
110
  GDestroyNotify clear_func;
Owen Taylor's avatar
Owen Taylor committed
111 112
};

113 114
/**
 * g_array_index:
115 116 117
 * @a: a #GArray
 * @t: the type of the elements
 * @i: the index of the element to return
118 119 120 121
 *
 * Returns the element of a #GArray at the given index. The return
 * value is cast to the given type.
 *
122
 * This example gets a pointer to an element in a #GArray:
123
 * |[<!-- language="C" -->
124
 *   EDayViewEvent *event;
Matthias Clasen's avatar
Matthias Clasen committed
125 126
 *   // This gets a pointer to the 4th element in the array of
 *   // EDayViewEvent structs.
127
 *   event = &g_array_index (events, EDayViewEvent, 3);
128
 * ]|
129
 *
130 131
 * Returns: the element of the #GArray at the index given by @i
 */
132

133 134
#define g_array_elt_len(array,i) ((array)->elt_size * (i))
#define g_array_elt_pos(array,i) ((array)->data + g_array_elt_len((array),(i)))
135
#define g_array_elt_zero(array, pos, len)                               \
136
  (memset (g_array_elt_pos ((array), pos), 0,  g_array_elt_len ((array), len)))
137 138 139
#define g_array_zero_terminate(array) G_STMT_START{                     \
  if ((array)->zero_terminated)                                         \
    g_array_elt_zero ((array), (array)->len, 1);                        \
140
}G_STMT_END
Owen Taylor's avatar
Owen Taylor committed
141

142
static guint g_nearest_pow        (guint       num) G_GNUC_CONST;
143
static void  g_array_maybe_expand (GRealArray *array,
144
                                   guint       len);
Owen Taylor's avatar
Owen Taylor committed
145

146 147 148
/**
 * g_array_new:
 * @zero_terminated: %TRUE if the array should have an extra element at
149
 *     the end which is set to 0
150
 * @clear_: %TRUE if #GArray elements should be automatically cleared
151 152
 *     to 0 when they are allocated
 * @element_size: the size of each element in bytes
153 154
 *
 * Creates a new #GArray with a reference count of 1.
155
 *
156 157
 * Returns: the new #GArray
 */
Owen Taylor's avatar
Owen Taylor committed
158
GArray*
159
g_array_new (gboolean zero_terminated,
160 161
             gboolean clear,
             guint    elt_size)
162
{
163 164 165
  g_return_val_if_fail (elt_size > 0, NULL);

  return g_array_sized_new (zero_terminated, clear, elt_size, 0);
166 167
}

168 169 170
/**
 * g_array_sized_new:
 * @zero_terminated: %TRUE if the array should have an extra element at
171
 *     the end with all bits cleared
172
 * @clear_: %TRUE if all bits in the array should be cleared to 0 on
173 174 175
 *     allocation
 * @element_size: size of each element in the array
 * @reserved_size: number of elements preallocated
176 177 178 179 180
 *
 * Creates a new #GArray with @reserved_size elements preallocated and
 * a reference count of 1. This avoids frequent reallocation, if you
 * are going to add many elements to the array. Note however that the
 * size of the array is still 0.
181
 *
182 183 184 185 186 187 188
 * Returns: the new #GArray
 */
GArray*
g_array_sized_new (gboolean zero_terminated,
                   gboolean clear,
                   guint    elt_size,
                   guint    reserved_size)
Owen Taylor's avatar
Owen Taylor committed
189
{
190 191 192 193 194
  GRealArray *array;
  
  g_return_val_if_fail (elt_size > 0, NULL);

  array = g_slice_new (GRealArray);
Owen Taylor's avatar
Owen Taylor committed
195

196 197 198
  array->data            = NULL;
  array->len             = 0;
  array->alloc           = 0;
Owen Taylor's avatar
Owen Taylor committed
199
  array->zero_terminated = (zero_terminated ? 1 : 0);
200 201
  array->clear           = (clear ? 1 : 0);
  array->elt_size        = elt_size;
202
  array->clear_func      = NULL;
Owen Taylor's avatar
Owen Taylor committed
203

204 205
  g_atomic_ref_count_init (&array->ref_count);

206
  if (array->zero_terminated || reserved_size != 0)
207
    {
208 209
      g_array_maybe_expand (array, reserved_size);
      g_array_zero_terminate(array);
210 211
    }

Owen Taylor's avatar
Owen Taylor committed
212 213 214
  return (GArray*) array;
}

215 216 217 218 219 220 221 222 223
/**
 * g_array_set_clear_func:
 * @array: A #GArray
 * @clear_func: a function to clear an element of @array
 *
 * Sets a function to clear an element of @array.
 *
 * The @clear_func will be called when an element in the array
 * data segment is removed and when the array is freed and data
224 225
 * segment is deallocated as well. @clear_func will be passed a
 * pointer to the element to clear, rather than the element itself.
226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243
 *
 * Note that in contrast with other uses of #GDestroyNotify
 * functions, @clear_func is expected to clear the contents of
 * the array element it is given, but not free the element itself.
 *
 * Since: 2.32
 */
void
g_array_set_clear_func (GArray         *array,
                        GDestroyNotify  clear_func)
{
  GRealArray *rarray = (GRealArray *) array;

  g_return_if_fail (array != NULL);

  rarray->clear_func = clear_func;
}

244 245
/**
 * g_array_ref:
246
 * @array: A #GArray
247
 *
248
 * Atomically increments the reference count of @array by one.
249
 * This function is thread-safe and may be called from any thread.
250
 *
251
 * Returns: The passed in #GArray
252 253
 *
 * Since: 2.22
254
 */
255 256 257 258
GArray *
g_array_ref (GArray *array)
{
  GRealArray *rarray = (GRealArray*) array;
259
  g_return_val_if_fail (array, NULL);
260

261
  g_atomic_ref_count_inc (&rarray->ref_count);
262

263 264 265
  return array;
}

266 267 268 269 270 271 272 273
typedef enum
{
  FREE_SEGMENT = 1 << 0,
  PRESERVE_WRAPPER = 1 << 1
} ArrayFreeFlags;

static gchar *array_free (GRealArray *, ArrayFreeFlags);

274 275
/**
 * g_array_unref:
276
 * @array: A #GArray
277 278 279
 *
 * Atomically decrements the reference count of @array by one. If the
 * reference count drops to 0, all memory allocated by the array is
280
 * released. This function is thread-safe and may be called from any
281 282 283
 * thread.
 *
 * Since: 2.22
284
 */
285 286 287 288
void
g_array_unref (GArray *array)
{
  GRealArray *rarray = (GRealArray*) array;
289
  g_return_if_fail (array);
290

291
  if (g_atomic_ref_count_dec (&rarray->ref_count))
292
    array_free (rarray, FREE_SEGMENT);
293 294 295 296
}

/**
 * g_array_get_element_size:
297
 * @array: A #GArray
298 299 300
 *
 * Gets the size of the elements in @array.
 *
301
 * Returns: Size of each element, in bytes
302 303
 *
 * Since: 2.22
304
 */
305 306 307 308
guint
g_array_get_element_size (GArray *array)
{
  GRealArray *rarray = (GRealArray*) array;
309 310 311

  g_return_val_if_fail (array, 0);

312 313 314
  return rarray->elt_size;
}

315 316
/**
 * g_array_free:
317 318
 * @array: a #GArray
 * @free_segment: if %TRUE the actual element data is freed as well
319 320
 *
 * Frees the memory allocated for the #GArray. If @free_segment is
321 322 323 324 325 326 327 328 329
 * %TRUE it frees the memory block holding the elements as well. Pass
 * %FALSE if you want to free the #GArray wrapper but preserve the
 * underlying array for use elsewhere. If the reference count of
 * @array is greater than one, the #GArray wrapper is preserved but
 * the size of  @array will be set to zero.
 *
 * If array contents point to dynamically-allocated memory, they should
 * be freed separately if @free_seg is %TRUE and no @clear_func
 * function has been set for @array.
330
 *
331 332 333 334
 * This function is not thread-safe. If using a #GArray from multiple
 * threads, use only the atomic g_array_ref() and g_array_unref()
 * functions.
 *
335
 * Returns: the element data if @free_segment is %FALSE, otherwise
336 337
 *     %NULL. The element data should be freed using g_free().
 */
338
gchar*
339
g_array_free (GArray   *farray,
340
              gboolean  free_segment)
Owen Taylor's avatar
Owen Taylor committed
341
{
342
  GRealArray *array = (GRealArray*) farray;
343
  ArrayFreeFlags flags;
344 345 346

  g_return_val_if_fail (array, NULL);

347 348
  flags = (free_segment ? FREE_SEGMENT : 0);

349
  /* if others are holding a reference, preserve the wrapper but do free/return the data */
350
  if (!g_atomic_ref_count_dec (&array->ref_count))
351 352 353 354 355 356 357 358 359 360
    flags |= PRESERVE_WRAPPER;

  return array_free (array, flags);
}

static gchar *
array_free (GRealArray     *array,
            ArrayFreeFlags  flags)
{
  gchar *segment;
361

362
  if (flags & FREE_SEGMENT)
363
    {
364 365 366 367 368 369 370 371
      if (array->clear_func != NULL)
        {
          guint i;

          for (i = 0; i < array->len; i++)
            array->clear_func (g_array_elt_pos (array, i));
        }

372 373 374 375
      g_free (array->data);
      segment = NULL;
    }
  else
Dan Winship's avatar
Dan Winship committed
376
    segment = (gchar*) array->data;
Owen Taylor's avatar
Owen Taylor committed
377

378
  if (flags & PRESERVE_WRAPPER)
379 380 381 382 383 384 385 386 387
    {
      array->data            = NULL;
      array->len             = 0;
      array->alloc           = 0;
    }
  else
    {
      g_slice_free1 (sizeof (GRealArray), array);
    }
388 389

  return segment;
Owen Taylor's avatar
Owen Taylor committed
390 391
}

392 393
/**
 * g_array_append_vals:
394
 * @array: a #GArray
395
 * @data: (not nullable): a pointer to the elements to append to the end of the array
396
 * @len: the number of elements to append
397 398
 *
 * Adds @len elements onto the end of the array.
399
 *
400 401
 * Returns: the #GArray
 */
402 403
/**
 * g_array_append_val:
404 405
 * @a: a #GArray
 * @v: the value to append to the #GArray
406 407 408 409
 *
 * Adds the value on to the end of the array. The array will grow in
 * size automatically if necessary.
 *
410 411 412
 * g_array_append_val() is a macro which uses a reference to the value
 * parameter @v. This means that you cannot use it with literal values
 * such as "27". You must use variables.
413
 *
414 415
 * Returns: the #GArray
 */
Owen Taylor's avatar
Owen Taylor committed
416
GArray*
Owen Taylor's avatar
Owen Taylor committed
417
g_array_append_vals (GArray       *farray,
418 419
                     gconstpointer data,
                     guint         len)
Owen Taylor's avatar
Owen Taylor committed
420
{
421
  GRealArray *array = (GRealArray*) farray;
Owen Taylor's avatar
Owen Taylor committed
422

423 424
  g_return_val_if_fail (array, NULL);

425 426 427
  if (len == 0)
    return farray;

428
  g_array_maybe_expand (array, len);
Owen Taylor's avatar
Owen Taylor committed
429

430
  memcpy (g_array_elt_pos (array, array->len), data, 
431
          g_array_elt_len (array, len));
Owen Taylor's avatar
Owen Taylor committed
432

433 434
  array->len += len;

435 436
  g_array_zero_terminate (array);

437
  return farray;
Owen Taylor's avatar
Owen Taylor committed
438 439
}

440 441
/**
 * g_array_prepend_vals:
442
 * @array: a #GArray
443 444
 * @data: (nullable): a pointer to the elements to prepend to the start of the array
 * @len: the number of elements to prepend, which may be zero
445 446 447
 *
 * Adds @len elements onto the start of the array.
 *
448 449 450
 * @data may be %NULL if (and only if) @len is zero. If @len is zero, this
 * function is a no-op.
 *
451 452 453
 * This operation is slower than g_array_append_vals() since the
 * existing elements in the array have to be moved to make space for
 * the new elements.
454
 *
455 456
 * Returns: the #GArray
 */
457 458
/**
 * g_array_prepend_val:
459 460
 * @a: a #GArray
 * @v: the value to prepend to the #GArray
461 462 463 464 465 466 467 468
 *
 * Adds the value on to the start of the array. The array will grow in
 * size automatically if necessary.
 *
 * This operation is slower than g_array_append_val() since the
 * existing elements in the array have to be moved to make space for
 * the new element.
 *
469 470 471
 * g_array_prepend_val() is a macro which uses a reference to the value
 * parameter @v. This means that you cannot use it with literal values
 * such as "27". You must use variables.
472
 *
473 474
 * Returns: the #GArray
 */
Owen Taylor's avatar
Owen Taylor committed
475
GArray*
Owen Taylor's avatar
Owen Taylor committed
476
g_array_prepend_vals (GArray        *farray,
477 478
                      gconstpointer  data,
                      guint          len)
Owen Taylor's avatar
Owen Taylor committed
479
{
480
  GRealArray *array = (GRealArray*) farray;
Owen Taylor's avatar
Owen Taylor committed
481

482 483
  g_return_val_if_fail (array, NULL);

484 485 486
  if (len == 0)
    return farray;

487
  g_array_maybe_expand (array, len);
Owen Taylor's avatar
Owen Taylor committed
488

Dan Winship's avatar
Dan Winship committed
489 490
  memmove (g_array_elt_pos (array, len), g_array_elt_pos (array, 0),
           g_array_elt_len (array, array->len));
Owen Taylor's avatar
Owen Taylor committed
491

492
  memcpy (g_array_elt_pos (array, 0), data, g_array_elt_len (array, len));
493 494 495

  array->len += len;

496 497
  g_array_zero_terminate (array);

498
  return farray;
Owen Taylor's avatar
Owen Taylor committed
499 500
}

501 502
/**
 * g_array_insert_vals:
503 504
 * @array: a #GArray
 * @index_: the index to place the elements at
505
 * @data: (nullable): a pointer to the elements to insert
506
 * @len: the number of elements to insert
507 508
 *
 * Inserts @len elements into a #GArray at the given index.
509
 *
510 511 512 513 514
 * If @index_ is greater than the array’s current length, the array is expanded.
 * The elements between the old end of the array and the newly inserted elements
 * will be initialised to zero if the array was configured to clear elements;
 * otherwise their values will be undefined.
 *
515 516 517
 * @data may be %NULL if (and only if) @len is zero. If @len is zero, this
 * function is a no-op.
 *
518 519
 * Returns: the #GArray
 */
520 521
/**
 * g_array_insert_val:
522 523 524
 * @a: a #GArray
 * @i: the index to place the element at
 * @v: the value to insert into the array
525 526 527
 *
 * Inserts an element into an array at the given index.
 *
528 529 530
 * g_array_insert_val() is a macro which uses a reference to the value
 * parameter @v. This means that you cannot use it with literal values
 * such as "27". You must use variables.
531
 *
532 533
 * Returns: the #GArray
 */
534 535
GArray*
g_array_insert_vals (GArray        *farray,
536 537 538
                     guint          index_,
                     gconstpointer  data,
                     guint          len)
539 540 541
{
  GRealArray *array = (GRealArray*) farray;

542 543
  g_return_val_if_fail (array, NULL);

544 545 546
  if (len == 0)
    return farray;

547 548 549
  /* Is the index off the end of the array, and hence do we need to over-allocate
   * and clear some elements? */
  if (index_ >= array->len)
550 551
    {
      g_array_maybe_expand (array, index_ - array->len + len);
552
      return g_array_append_vals (g_array_set_size (farray, index_), data, len);
553
    }
554

555 556
  g_array_maybe_expand (array, len);

Dan Winship's avatar
Dan Winship committed
557 558 559
  memmove (g_array_elt_pos (array, len + index_),
           g_array_elt_pos (array, index_),
           g_array_elt_len (array, array->len - index_));
560

561
  memcpy (g_array_elt_pos (array, index_), data, g_array_elt_len (array, len));
562 563 564

  array->len += len;

565 566
  g_array_zero_terminate (array);

567 568 569
  return farray;
}

570 571
/**
 * g_array_set_size:
572 573
 * @array: a #GArray
 * @length: the new size of the #GArray
574 575 576
 *
 * Sets the size of the array, expanding it if necessary. If the array
 * was created with @clear_ set to %TRUE, the new elements are set to 0.
577
 *
578 579
 * Returns: the #GArray
 */
Owen Taylor's avatar
Owen Taylor committed
580
GArray*
581
g_array_set_size (GArray *farray,
582
                  guint   length)
Owen Taylor's avatar
Owen Taylor committed
583
{
584
  GRealArray *array = (GRealArray*) farray;
585 586 587

  g_return_val_if_fail (array, NULL);

588
  if (length > array->len)
589 590 591 592
    {
      g_array_maybe_expand (array, length - array->len);
      
      if (array->clear)
593
        g_array_elt_zero (array, array->len, length - array->len);
594
    }
595 596
  else if (length < array->len)
    g_array_remove_range (farray, length, array->len - length);
597
  
598
  array->len = length;
599 600 601
  
  g_array_zero_terminate (array);
  
602 603
  return farray;
}
Owen Taylor's avatar
Owen Taylor committed
604

605 606
/**
 * g_array_remove_index:
607 608
 * @array: a #GArray
 * @index_: the index of the element to remove
609 610 611
 *
 * Removes the element at the given index from a #GArray. The following
 * elements are moved down one place.
612
 *
613 614
 * Returns: the #GArray
 */
615
GArray*
616
g_array_remove_index (GArray *farray,
617
                      guint   index_)
618 619 620 621 622
{
  GRealArray* array = (GRealArray*) farray;

  g_return_val_if_fail (array, NULL);

623
  g_return_val_if_fail (index_ < array->len, NULL);
624

625 626 627
  if (array->clear_func != NULL)
    array->clear_func (g_array_elt_pos (array, index_));

628
  if (index_ != array->len - 1)
Dan Winship's avatar
Dan Winship committed
629 630 631
    memmove (g_array_elt_pos (array, index_),
             g_array_elt_pos (array, index_ + 1),
             g_array_elt_len (array, array->len - index_ - 1));
632

633 634
  array->len -= 1;

635 636 637 638
  if (G_UNLIKELY (g_mem_gc_friendly))
    g_array_elt_zero (array, array->len, 1);
  else
    g_array_zero_terminate (array);
639

640 641 642
  return farray;
}

643 644
/**
 * g_array_remove_index_fast:
645 646
 * @array: a @GArray
 * @index_: the index of the element to remove
647 648 649 650 651
 *
 * Removes the element at the given index from a #GArray. The last
 * element in the array is used to fill in the space, so this function
 * does not preserve the order of the #GArray. But it is faster than
 * g_array_remove_index().
652
 *
653 654
 * Returns: the #GArray
 */
655
GArray*
656
g_array_remove_index_fast (GArray *farray,
657
                           guint   index_)
658 659 660 661 662
{
  GRealArray* array = (GRealArray*) farray;

  g_return_val_if_fail (array, NULL);

663
  g_return_val_if_fail (index_ < array->len, NULL);
664

665 666 667
  if (array->clear_func != NULL)
    array->clear_func (g_array_elt_pos (array, index_));

668
  if (index_ != array->len - 1)
669 670 671
    memcpy (g_array_elt_pos (array, index_),
            g_array_elt_pos (array, array->len - 1),
            g_array_elt_len (array, 1));
672 673 674
  
  array->len -= 1;

675 676 677 678
  if (G_UNLIKELY (g_mem_gc_friendly))
    g_array_elt_zero (array, array->len, 1);
  else
    g_array_zero_terminate (array);
679

680 681 682
  return farray;
}

683 684
/**
 * g_array_remove_range:
685 686 687
 * @array: a @GArray
 * @index_: the index of the first element to remove
 * @length: the number of elements to remove
688 689 690 691
 *
 * Removes the given number of elements starting at the given index
 * from a #GArray.  The following elements are moved to close the gap.
 *
692
 * Returns: the #GArray
693
 *
694
 * Since: 2.4
695
 */
696
GArray*
697 698 699
g_array_remove_range (GArray *farray,
                      guint   index_,
                      guint   length)
700 701 702 703
{
  GRealArray *array = (GRealArray*) farray;

  g_return_val_if_fail (array, NULL);
704
  g_return_val_if_fail (index_ <= array->len, NULL);
705 706
  g_return_val_if_fail (index_ + length <= array->len, NULL);

707 708 709 710 711 712 713 714
  if (array->clear_func != NULL)
    {
      guint i;

      for (i = 0; i < length; i++)
        array->clear_func (g_array_elt_pos (array, index_ + i));
    }

715
  if (index_ + length != array->len)
Dan Winship's avatar
Dan Winship committed
716 717 718
    memmove (g_array_elt_pos (array, index_),
             g_array_elt_pos (array, index_ + length),
             (array->len - (index_ + length)) * array->elt_size);
719 720

  array->len -= length;
721 722 723 724
  if (G_UNLIKELY (g_mem_gc_friendly))
    g_array_elt_zero (array, array->len, length);
  else
    g_array_zero_terminate (array);
725 726 727 728

  return farray;
}

729 730
/**
 * g_array_sort:
731 732
 * @array: a #GArray
 * @compare_func: comparison function
733 734 735 736 737 738
 *
 * Sorts a #GArray using @compare_func which should be a qsort()-style
 * comparison function (returns less than zero for first arg is less
 * than second arg, zero for equal, greater zero if first arg is
 * greater than second arg).
 *
739
 * This is guaranteed to be a stable sort since version 2.32.
740
 */
741 742
void
g_array_sort (GArray       *farray,
743
              GCompareFunc  compare_func)
744 745 746 747 748
{
  GRealArray *array = (GRealArray*) farray;

  g_return_if_fail (array != NULL);

749 750
  /* Don't use qsort as we want a guaranteed stable sort */
  g_qsort_with_data (array->data,
751 752 753 754
                     array->len,
                     array->elt_size,
                     (GCompareDataFunc)compare_func,
                     NULL);
755 756
}

757 758
/**
 * g_array_sort_with_data:
759 760 761
 * @array: a #GArray
 * @compare_func: comparison function
 * @user_data: data to pass to @compare_func
762 763 764
 *
 * Like g_array_sort(), but the comparison function receives an extra
 * user data argument.
765 766 767 768 769 770
 *
 * This is guaranteed to be a stable sort since version 2.32.
 *
 * There used to be a comment here about making the sort stable by
 * using the addresses of the elements in the comparison function.
 * This did not actually work, so any such code should be removed.
771
 */
772 773
void
g_array_sort_with_data (GArray           *farray,
774 775
                        GCompareDataFunc  compare_func,
                        gpointer          user_data)
776 777 778 779 780 781
{
  GRealArray *array = (GRealArray*) farray;

  g_return_if_fail (array != NULL);

  g_qsort_with_data (array->data,
782 783 784 785
                     array->len,
                     array->elt_size,
                     compare_func,
                     user_data);
786 787
}

788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868
/**
 * g_array_binary_search:
 * @array: a #GArray.
 * @target: a pointer to the item to look up.
 * @compare_func: A #GCompareFunc used to locate @target.
 * @out_match_index: (optional) (out caller-allocates): return location
 *    for the index of the element, if found.
 *
 * Checks whether @target exists in @array by performing a binary
 * search based on the given comparison function @compare_func which
 * get pointers to items as arguments. If the element is found, %TRUE
 * is returned and the element’s index is returned in @out_match_index
 * (if non-%NULL). Otherwise, %FALSE is returned and @out_match_index
 * is undefined. If @target exists multiple times in @array, the index
 * of the first instance is returned. This search is using a binary
 * search, so the @array must absolutely be sorted to return a correct
 * result (if not, the function may produce false-negative).
 *
 * This example defines a comparison function and search an element in a #GArray:
 * |[<!-- language="C" -->
 * static gint*
 * cmpint (gconstpointer a, gconstpointer b)
 * {
 *   const gint *_a = a;
 *   const gint *_b = b;
 *
 *   return *_a - *_b;
 * }
 * ...
 * gint i = 424242;
 * guint matched_index;
 * gboolean result = g_array_binary_search (garray, &i, cmpint, &matched_index);
 * ...
 * ]|
 *
 * Returns: %TRUE if @target is one of the elements of @array, %FALSE otherwise.
 *
 * Since: 2.62
 */
gboolean
g_array_binary_search (GArray        *array,
                       gconstpointer  target,
                       GCompareFunc   compare_func,
                       guint         *out_match_index)
{
  gboolean result = FALSE;
  GRealArray *_array = (GRealArray *) array;
  guint left, middle, right;
  gint val;

  g_return_val_if_fail (_array != NULL, FALSE);
  g_return_val_if_fail (compare_func != NULL, FALSE);

  if (G_LIKELY(_array->len))
    {
      left = 0;
      right = _array->len - 1;

      while (left <= right)
        {
          middle = (left + right) / 2;

          val = compare_func (_array->data + (_array->elt_size * middle), target);
          if (val < 0)
            left = middle + 1;
          else if (val > 0)
            right = middle - 1;
          else
            {
              result = TRUE;
              break;
            }
        }
    }

  if (result && out_match_index != NULL)
    *out_match_index = middle;

  return result;
}

869 870 871 872
/* Returns the smallest power of 2 greater than n, or n if
 * such power does not fit in a guint
 */
static guint
873
g_nearest_pow (guint num)
Owen Taylor's avatar
Owen Taylor committed
874
{
875
  guint n = 1;
Owen Taylor's avatar
Owen Taylor committed
876

877
  while (n < num && n > 0)
Owen Taylor's avatar
Owen Taylor committed
878 879
    n <<= 1;

880
  return n ? n : num;
Owen Taylor's avatar
Owen Taylor committed
881 882 883 884
}

static void
g_array_maybe_expand (GRealArray *array,
885
                      guint       len)
Owen Taylor's avatar
Owen Taylor committed
886
{
887 888 889 890 891 892 893 894
  guint want_alloc;

  /* Detect potential overflow */
  if G_UNLIKELY ((G_MAXUINT - array->len) < len)
    g_error ("adding %u to array would overflow", len);

  want_alloc = g_array_elt_len (array, array->len + len +
                                array->zero_terminated);
Owen Taylor's avatar
Owen Taylor committed
895

896
  if (want_alloc > array->alloc)
Owen Taylor's avatar
Owen Taylor committed
897
    {
898 899
      want_alloc = g_nearest_pow (want_alloc);
      want_alloc = MAX (want_alloc, MIN_ARRAY_SIZE);
900

901 902
      array->data = g_realloc (array->data, want_alloc);

903 904
      if (G_UNLIKELY (g_mem_gc_friendly))
        memset (array->data + array->alloc, 0, want_alloc - array->alloc);
905 906

      array->alloc = want_alloc;
Owen Taylor's avatar
Owen Taylor committed
907 908
    }
}
909

910
/**
911
 * SECTION:arrays_pointer
912 913
 * @title: Pointer Arrays
 * @short_description: arrays of pointers to any type of data, which
914
 *     grow automatically as new elements are added
915 916 917 918
 *
 * Pointer Arrays are similar to Arrays but are used only for storing
 * pointers.
 *
919 920 921 922 923
 * If you remove elements from the array, elements at the end of the
 * array are moved into the space previously occupied by the removed
 * element. This means that you should not rely on the index of particular
 * elements remaining the same. You should also be careful when deleting
 * elements while iterating over the array.
924 925 926 927 928 929 930 931 932 933 934 935 936 937
 *
 * To create a pointer array, use g_ptr_array_new().
 *
 * To add elements to a pointer array, use g_ptr_array_add().
 *
 * To remove elements from a pointer array, use g_ptr_array_remove(),
 * g_ptr_array_remove_index() or g_ptr_array_remove_index_fast().
 *
 * To access an element of a pointer array, use g_ptr_array_index().
 *
 * To set the size of a pointer array, use g_ptr_array_set_size().
 *
 * To free a pointer array, use g_ptr_array_free().
 *
938
 * An example using a #GPtrArray:
939
 * |[<!-- language="C" -->
940
 *   GPtrArray *array;
941 942 943
 *   gchar *string1 = "one";
 *   gchar *string2 = "two";
 *   gchar *string3 = "three";
944
 *
945
 *   array = g_ptr_array_new ();
946 947 948
 *   g_ptr_array_add (array, (gpointer) string1);
 *   g_ptr_array_add (array, (gpointer) string2);
 *   g_ptr_array_add (array, (gpointer) string3);
949
 *
950
 *   if (g_ptr_array_index (array, 0) != (gpointer) string1)
951
 *     g_print ("ERROR: got %p instead of %p\n",
952
 *              g_ptr_array_index (array, 0), string1);
953
 *
954
 *   g_ptr_array_free (array, TRUE);
955 956
 * ]|
 */
957 958 959

typedef struct _GRealPtrArray  GRealPtrArray;

960 961 962
/**
 * GPtrArray:
 * @pdata: points to the array of pointers, which may be moved when the
963 964
 *     array grows
 * @len: number of pointers in the array
965 966
 *
 * Contains the public fields of a pointer array.
967
 */
968 969
struct _GRealPtrArray
{
970 971 972
  gpointer       *pdata;
  guint           len;
  guint           alloc;
973
  gatomicrefcount ref_count;
974
  GDestroyNotify  element_free_func;
975 976
};

977 978
/**
 * g_ptr_array_index:
979 980
 * @array: a #GPtrArray
 * @index_: the index of the pointer to return
981 982
 *
 * Returns the pointer at the given index of the pointer array.
983
 *
984 985
 * This does not perform bounds checking on the given @index_,
 * so you are responsible for checking it against the array length.
986
 *
987 988
 * Returns: the pointer at the given index
 */
989

990
static void g_ptr_array_maybe_expand (GRealPtrArray *array,
991
                                      guint          len);
992

993 994 995 996
/**
 * g_ptr_array_new:
 *
 * Creates a new #GPtrArray with a reference count of 1.
997
 *
998 999
 * Returns: the new #GPtrArray
 */
1000
GPtrArray*
1001
g_ptr_array_new (void)
1002 1003 1004 1005
{
  return g_ptr_array_sized_new (0);
}

1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051
/**
 * g_ptr_array_copy:
 * @array: #GPtrArray to duplicate
 * @func: (nullable): a copy function used to copy every element in the array
 * @user_data: user data passed to the copy function @func, or %NULL
 *
 * Makes a full (deep) copy of a #GPtrArray.
 *
 * @func, as a #GCopyFunc, takes two arguments, the data to be copied
 * and a @user_data pointer. On common processor architectures, it's safe to
 * pass %NULL as @user_data if the copy function takes only one argument. You
 * may get compiler warnings from this though if compiling with GCC’s
 * `-Wcast-function-type` warning.
 *
 * If @func is %NULL, then only the pointers (and not what they are
 * pointing to) are copied to the new #GPtrArray.
 *
 * Returns: (transfer full): a deep copy of the initial #GPtrArray.
 *
 * Since: 2.62
 **/
GPtrArray *
g_ptr_array_copy (GPtrArray *array,
                  GCopyFunc  func,
                  gpointer   user_data)
{
  gsize i;
  GPtrArray *new_array;

  g_return_val_if_fail (array != NULL, NULL);

  new_array = g_ptr_array_sized_new (array->len);
  if (func != NULL)
    {
      for (i = 0; i < array->len; i++)
        new_array->pdata[i] = func (array->pdata[i], user_data);
    }
  else
    {
      memcpy (new_array->pdata, array->pdata,
              array->len * sizeof (*array->pdata));
    }

  return new_array;
}

1052 1053
/**
 * g_ptr_array_sized_new:
1054
 * @reserved_size: number of pointers preallocated
1055 1056 1057 1058 1059
 *
 * Creates a new #GPtrArray with @reserved_size pointers preallocated
 * and a reference count of 1. This avoids frequent reallocation, if
 * you are going to add many pointers to the array. Note however that
 * the size of the array is still 0.
1060
 *
1061 1062
 * Returns: the new #GPtrArray
 */
1063 1064
GPtrArray*  
g_ptr_array_sized_new (guint reserved_size)
1065
{
1066 1067 1068
  GRealPtrArray *array;

  array = g_slice_new (GRealPtrArray);
1069 1070 1071 1072

  array->pdata = NULL;
  array->len = 0;
  array->alloc = 0;
1073
  array->element_free_func = NULL;
1074

1075 1076
  g_atomic_ref_count_init (&array->ref_count);

1077 1078 1079 1080
  if (reserved_size != 0)
    g_ptr_array_maybe_expand (array, reserved_size);

  return (GPtrArray*) array;  
1081 1082
}

1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110
/**
 * g_array_copy:
 * @array: A #GArray.
 *
 * Create a shallow copy of a #GArray. If the array elements consist of
 * pointers to data, the pointers are copied but the actual data is not.
 *
 * Returns: (transfer container): A copy of @array.
 *
 * Since: 2.62
 **/
GArray *
g_array_copy (GArray *array)
{
  GRealArray *rarray = (GRealArray *) array;
  GRealArray *new_rarray;

  g_return_val_if_fail (rarray != NULL, NULL);

  new_rarray =
    (GRealArray *) g_array_sized_new (rarray->zero_terminated, rarray->clear,
                                      rarray->elt_size, rarray->len);
  new_rarray->len = rarray->len;
  memcpy (new_rarray->data, rarray->data, rarray->alloc);

  return (GArray *) new_rarray;
}

1111 1112
/**
 * g_ptr_array_new_with_free_func:
1113
 * @element_free_func: (nullable): A function to free elements with
1114
 *     destroy @array or %NULL
1115
 *
1116 1117 1118 1119
 * Creates a new #GPtrArray with a reference count of 1 and use
 * @element_free_func for freeing each element when the array is destroyed
 * either via g_ptr_array_unref(), when g_ptr_array_free() is called with
 * @free_segment set to %TRUE or when removing elements.
1120
 *
1121
 * Returns: A new #GPtrArray
1122 1123
 *
 * Since: 2.22
1124
 */
1125
GPtrArray*
1126 1127 1128 1129 1130 1131
g_ptr_array_new_with_free_func (GDestroyNotify element_free_func)
{
  GPtrArray *array;

  array = g_ptr_array_new ();
  g_ptr_array_set_free_func (array, element_free_func);
1132

1133 1134 1135
  return array;
}

1136 1137
/**
 * g_ptr_array_new_full:
1138
 * @reserved_size: number of pointers preallocated
1139
 * @element_free_func: (nullable): A function to free elements with
1140
 *     destroy @array or %NULL
1141 1142 1143 1144 1145 1146
 *
 * Creates a new #GPtrArray with @reserved_size pointers preallocated
 * and a reference count of 1. This avoids frequent reallocation, if
 * you are going to add many pointers to the array. Note however that
 * the size of the array is still 0. It also set @element_free_func
 * for freeing each element when the array is destroyed either via
1147 1148
 * g_ptr_array_unref(), when g_ptr_array_free() is called with
 * @free_segment set to %TRUE or when removing elements.
1149
 *
1150
 * Returns: A new #GPtrArray
1151 1152
 *
 * Since: 2.30
1153
 */
1154
GPtrArray*
1155 1156 1157 1158 1159 1160 1161
g_ptr_array_new_full (guint          reserved_size,
                      GDestroyNotify element_free_func)
{
  GPtrArray *array;

  array = g_ptr_array_sized_new (reserved_size);
  g_ptr_array_set_free_func (array, element_free_func);
1162

1163 1164 1165
  return array;
}

1166 1167
/**
 * g_ptr_array_set_free_func:
1168
 * @array: A #GPtrArray
1169
 * @element_free_func: (nullable): A function to free elements with
1170
 *     destroy @array or %NULL
1171 1172 1173 1174 1175 1176
 *
 * Sets a function for freeing each element when @array is destroyed
 * either via g_ptr_array_unref(), when g_ptr_array_free() is called
 * with @free_segment set to %TRUE or when removing elements.
 *
 * Since: 2.22
1177
 */
1178
void
1179 1180
g_ptr_array_set_free_func (GPtrArray      *array,
                           GDestroyNotify  element_free_func)
1181
{
1182
  GRealPtrArray *rarray = (GRealPtrArray *)array;
1183 1184 1185

  g_return_if_fail (array);

1186 1187 1188 1189 1190
  rarray->element_free_func = element_free_func;
}

/**
 * g_ptr_array_ref:
1191
 * @array: a #GPtrArray
1192
 *
1193 1194
 * Atomically increments the reference count of @array by one.
 * This function is thread-safe and may be called from any thread.
1195
 *
1196
 * Returns: The passed in #GPtrArray
1197 1198
 *
 * Since: 2.22
1199
 */
1200
GPtrArray*
1201 1202
g_ptr_array_ref (GPtrArray *array)
{
1203
  GRealPtrArray *rarray = (GRealPtrArray *)array;
1204 1205

  g_return_val_if_fail (array, NULL);
1206

1207
  g_atomic_ref_count_inc (&rarray->ref_count);
1208

1209 1210 1211
  return array;
}

1212 1213
static gpointer *ptr_array_free (GPtrArray *, ArrayFreeFlags);

1214 1215
/**
 * g_ptr_array_unref:
1216
 * @array: A #GPtrArray
1217 1218 1219 1220
 *
 * Atomically decrements the reference count of @array by one. If the
 * reference count drops to 0, the effect is the same as calling
 * g_ptr_array_free() with @free_segment set to %TRUE. This function
1221
 * is thread-safe and may be called from any thread.
1222 1223
 *
 * Since: 2.22
1224
 */
1225 1226 1227
void
g_ptr_array_unref (GPtrArray *array)
{
1228 1229
  GRealPtrArray *rarray = (GRealPtrArray *)array;

1230
  g_return_if_fail (array);
1231

1232
  if (g_atomic_ref_count_dec (&rarray->ref_count))
1233
    ptr_array_free (array, FREE_SEGMENT);
1234 1235
}

1236 1237
/**
 * g_ptr_array_free:
1238 1239
 * @array: a #GPtrArray
 * @free_seg: if %TRUE the actual pointer array is freed as well
1240 1241 1242 1243 1244 1245 1246 1247
 *
 * Frees the memory allocated for the #GPtrArray. If @free_seg is %TRUE
 * it frees the memory block holding the elements as well. Pass %FALSE
 * if you want to free the #GPtrArray wrapper but preserve the
 * underlying array for use elsewhere. If the reference count of @array
 * is greater than one, the #GPtrArray wrapper is preserved but the
 * size of @array will be set to zero.
 *
1248 1249 1250
 * If array contents point to dynamically-allocated memory, they should
 * be freed separately if @free_seg is %TRUE and no #GDestroyNotify
 * function has been set for @array.
1251
 *
1252 1253 1254 1255
 * This function is not thread-safe. If using a #GPtrArray from multiple
 * threads, use only the atomic g_ptr_array_ref() and g_ptr_array_unref()
 * functions.
 *
1256
 * Returns: the pointer array if @free_seg is %FALSE, otherwise %NULL.
1257 1258
 *     The pointer array should be freed using g_free().
 */
1259
gpointer*
1260
g_ptr_array_free (GPtrArray *array,
1261
                  gboolean   free_segment)
1262
{
1263
  GRealPtrArray *rarray = (GRealPtrArray *)array;
1264
  ArrayFreeFlags flags;
1265

1266
  g_return_val_if_fail (rarray, NULL);
1267

1268 1269
  flags = (free_segment ? FREE_SEGMENT : 0);

1270 1271 1272
  /* if others are holding a reference, preserve the wrapper but
   * do free/return the data
   */
1273
  if (!g_atomic_ref_count_dec (&rarray->ref_count))
1274 1275
    flags |= PRESERVE_WRAPPER;

1276
  return ptr_array_free (array, flags);
1277 1278 1279
}

static gpointer *
1280
ptr_array_free (GPtrArray      *array,
1281 1282
                ArrayFreeFlags  flags)
{
1283
  GRealPtrArray *rarray = (GRealPtrArray *)array;
1284
  gpointer *segment;
1285

1286
  if (flags & FREE_SEGMENT)
1287
    {
1288 1289 1290 1291 1292 1293 1294
      /* Data here is stolen and freed manually. It is an
       * error to attempt to access the array data (including
       * mutating the array bounds) during destruction).
       *
       * https://bugzilla.gnome.org/show_bug.cgi?id=769064
       */
      gpointer *stolen_pdata = g_steal_pointer (&rarray->pdata);
1295
      if (rarray->element_free_func != NULL)
1296 1297 1298 1299 1300 1301 1302
        {
          gsize i;
          for (i = 0; i < rarray->len; ++i)
            rarray->element_free_func (stolen_pdata[i]);
        }

      g_free (stolen_pdata);
1303 1304 1305
      segment = NULL;
    }
  else
1306
    segment = rarray->pdata;
1307

1308
  if (flags & PRESERVE_WRAPPER)
1309
    {
1310 1311 1312
      rarray->pdata = NULL;
      rarray->len = 0;
      rarray->alloc = 0;
1313 1314 1315
    }
  else
    {
1316
      g_slice_free1 (sizeof (GRealPtrArray), rarray);
1317
    }
1318 1319

  return segment;
1320 1321 1322 1323
}

static void
g_ptr_array_maybe_expand (GRealPtrArray *array,
1324
                          guint          len)