1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
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.
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.
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, write to the
16 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17 * Boston, MA 02111-1307, USA.
21 * Modified by the GLib Team and others 1997-2000. See the AUTHORS
22 * file for a list of people on the GLib Team. See the ChangeLog
23 * files for a list of changes. These files are distributed with
24 * GLib at ftp://ftp.gtk.org/pub/gtk/.
40 #include "gmessages.h"
46 #define MIN_ARRAY_SIZE 16
48 typedef struct _GRealArray GRealArray;
56 guint zero_terminated : 1;
60 #define g_array_elt_len(array,i) ((array)->elt_size * (i))
61 #define g_array_elt_pos(array,i) ((array)->data + g_array_elt_len((array),(i)))
62 #define g_array_elt_zero(array, pos, len) \
63 (memset (g_array_elt_pos ((array), pos), 0, g_array_elt_len ((array), len)))
64 #define g_array_zero_terminate(array) G_STMT_START{ \
65 if ((array)->zero_terminated) \
66 g_array_elt_zero ((array), (array)->len, 1); \
69 static gint g_nearest_pow (gint num) G_GNUC_CONST;
70 static void g_array_maybe_expand (GRealArray *array,
74 g_array_new (gboolean zero_terminated,
78 return (GArray*) g_array_sized_new (zero_terminated, clear, elt_size, 0);
81 GArray* g_array_sized_new (gboolean zero_terminated,
86 GRealArray *array = g_slice_new (GRealArray);
91 array->zero_terminated = (zero_terminated ? 1 : 0);
92 array->clear = (clear ? 1 : 0);
93 array->elt_size = elt_size;
95 if (array->zero_terminated || reserved_size != 0)
97 g_array_maybe_expand (array, reserved_size);
98 g_array_zero_terminate(array);
101 return (GArray*) array;
105 g_array_free (GArray *array,
106 gboolean free_segment)
110 g_return_val_if_fail (array, NULL);
114 g_free (array->data);
118 segment = array->data;
120 g_slice_free1 (sizeof (GRealArray), array);
126 g_array_append_vals (GArray *farray,
130 GRealArray *array = (GRealArray*) farray;
132 g_array_maybe_expand (array, len);
134 memcpy (g_array_elt_pos (array, array->len), data,
135 g_array_elt_len (array, len));
139 g_array_zero_terminate (array);
145 g_array_prepend_vals (GArray *farray,
149 GRealArray *array = (GRealArray*) farray;
151 g_array_maybe_expand (array, len);
153 g_memmove (g_array_elt_pos (array, len), g_array_elt_pos (array, 0),
154 g_array_elt_len (array, array->len));
156 memcpy (g_array_elt_pos (array, 0), data, g_array_elt_len (array, len));
160 g_array_zero_terminate (array);
166 g_array_insert_vals (GArray *farray,
171 GRealArray *array = (GRealArray*) farray;
173 g_array_maybe_expand (array, len);
175 g_memmove (g_array_elt_pos (array, len + index_),
176 g_array_elt_pos (array, index_),
177 g_array_elt_len (array, array->len - index_));
179 memcpy (g_array_elt_pos (array, index_), data, g_array_elt_len (array, len));
183 g_array_zero_terminate (array);
189 g_array_set_size (GArray *farray,
192 GRealArray *array = (GRealArray*) farray;
193 if (length > array->len)
195 g_array_maybe_expand (array, length - array->len);
198 g_array_elt_zero (array, array->len, length - array->len);
200 else if (G_UNLIKELY (g_mem_gc_friendly) && length < array->len)
201 g_array_elt_zero (array, length, array->len - length);
205 g_array_zero_terminate (array);
211 g_array_remove_index (GArray *farray,
214 GRealArray* array = (GRealArray*) farray;
216 g_return_val_if_fail (array, NULL);
218 g_return_val_if_fail (index_ < array->len, NULL);
220 if (index_ != array->len - 1)
221 g_memmove (g_array_elt_pos (array, index_),
222 g_array_elt_pos (array, index_ + 1),
223 g_array_elt_len (array, array->len - index_ - 1));
227 if (G_UNLIKELY (g_mem_gc_friendly))
228 g_array_elt_zero (array, array->len, 1);
230 g_array_zero_terminate (array);
236 g_array_remove_index_fast (GArray *farray,
239 GRealArray* array = (GRealArray*) farray;
241 g_return_val_if_fail (array, NULL);
243 g_return_val_if_fail (index_ < array->len, NULL);
245 if (index_ != array->len - 1)
246 memcpy (g_array_elt_pos (array, index_),
247 g_array_elt_pos (array, array->len - 1),
248 g_array_elt_len (array, 1));
252 if (G_UNLIKELY (g_mem_gc_friendly))
253 g_array_elt_zero (array, array->len, 1);
255 g_array_zero_terminate (array);
261 g_array_remove_range (GArray *farray,
265 GRealArray *array = (GRealArray*) farray;
267 g_return_val_if_fail (array, NULL);
268 g_return_val_if_fail (index_ < array->len, NULL);
269 g_return_val_if_fail (index_ + length <= array->len, NULL);
271 if (index_ + length != array->len)
272 g_memmove (g_array_elt_pos (array, index_),
273 g_array_elt_pos (array, index_ + length),
274 (array->len - (index_ + length)) * array->elt_size);
276 array->len -= length;
277 if (G_UNLIKELY (g_mem_gc_friendly))
278 g_array_elt_zero (array, array->len, length);
280 g_array_zero_terminate (array);
286 g_array_sort (GArray *farray,
287 GCompareFunc compare_func)
289 GRealArray *array = (GRealArray*) farray;
291 g_return_if_fail (array != NULL);
300 g_array_sort_with_data (GArray *farray,
301 GCompareDataFunc compare_func,
304 GRealArray *array = (GRealArray*) farray;
306 g_return_if_fail (array != NULL);
308 g_qsort_with_data (array->data,
317 g_nearest_pow (gint num)
328 g_array_maybe_expand (GRealArray *array,
331 guint want_alloc = g_array_elt_len (array, array->len + len +
332 array->zero_terminated);
334 if (want_alloc > array->alloc)
336 want_alloc = g_nearest_pow (want_alloc);
337 want_alloc = MAX (want_alloc, MIN_ARRAY_SIZE);
339 array->data = g_realloc (array->data, want_alloc);
341 if (G_UNLIKELY (g_mem_gc_friendly))
342 memset (array->data + array->alloc, 0, want_alloc - array->alloc);
344 array->alloc = want_alloc;
351 typedef struct _GRealPtrArray GRealPtrArray;
353 struct _GRealPtrArray
360 static void g_ptr_array_maybe_expand (GRealPtrArray *array,
364 g_ptr_array_new (void)
366 return g_ptr_array_sized_new (0);
370 g_ptr_array_sized_new (guint reserved_size)
372 GRealPtrArray *array = g_slice_new (GRealPtrArray);
378 if (reserved_size != 0)
379 g_ptr_array_maybe_expand (array, reserved_size);
381 return (GPtrArray*) array;
385 g_ptr_array_free (GPtrArray *array,
386 gboolean free_segment)
390 g_return_val_if_fail (array, NULL);
394 g_free (array->pdata);
398 segment = array->pdata;
400 g_slice_free1 (sizeof (GRealPtrArray), array);
406 g_ptr_array_maybe_expand (GRealPtrArray *array,
409 if ((array->len + len) > array->alloc)
411 guint old_alloc = array->alloc;
412 array->alloc = g_nearest_pow (array->len + len);
413 array->alloc = MAX (array->alloc, MIN_ARRAY_SIZE);
414 array->pdata = g_realloc (array->pdata, sizeof (gpointer) * array->alloc);
415 if (G_UNLIKELY (g_mem_gc_friendly))
416 for ( ; old_alloc < array->alloc; old_alloc++)
417 array->pdata [old_alloc] = NULL;
422 g_ptr_array_set_size (GPtrArray *farray,
425 GRealPtrArray* array = (GRealPtrArray*) farray;
427 g_return_if_fail (array);
429 if (length > array->len)
432 g_ptr_array_maybe_expand (array, (length - array->len));
434 * memset (array->pdata + array->len, 0,
435 * sizeof (gpointer) * (length - array->len));
436 * to make it really portable. Remember (void*)NULL needn't be
437 * bitwise zero. It of course is silly not to use memset (..,0,..).
439 for (i = array->len; i < length; i++)
440 array->pdata[i] = NULL;
442 if (G_UNLIKELY (g_mem_gc_friendly) && length < array->len)
445 for (i = length; i < array->len; i++)
446 array->pdata[i] = NULL;
453 g_ptr_array_remove_index (GPtrArray *farray,
456 GRealPtrArray* array = (GRealPtrArray*) farray;
459 g_return_val_if_fail (array, NULL);
461 g_return_val_if_fail (index_ < array->len, NULL);
463 result = array->pdata[index_];
465 if (index_ != array->len - 1)
466 g_memmove (array->pdata + index_, array->pdata + index_ + 1,
467 sizeof (gpointer) * (array->len - index_ - 1));
471 if (G_UNLIKELY (g_mem_gc_friendly))
472 array->pdata[array->len] = NULL;
478 g_ptr_array_remove_index_fast (GPtrArray *farray,
481 GRealPtrArray* array = (GRealPtrArray*) farray;
484 g_return_val_if_fail (array, NULL);
486 g_return_val_if_fail (index_ < array->len, NULL);
488 result = array->pdata[index_];
490 if (index_ != array->len - 1)
491 array->pdata[index_] = array->pdata[array->len - 1];
495 if (G_UNLIKELY (g_mem_gc_friendly))
496 array->pdata[array->len] = NULL;
502 g_ptr_array_remove_range (GPtrArray *farray,
506 GRealPtrArray* array = (GRealPtrArray*) farray;
508 g_return_if_fail (array);
509 g_return_if_fail (index_ < array->len);
510 g_return_if_fail (index_ + length <= array->len);
512 if (index_ + length != array->len)
513 g_memmove (&array->pdata[index_],
514 &array->pdata[index_ + length],
515 (array->len - (index_ + length)) * sizeof (gpointer));
517 array->len -= length;
518 if (G_UNLIKELY (g_mem_gc_friendly))
521 for (i = 0; i < length; i++)
522 array->pdata[array->len + i] = NULL;
527 g_ptr_array_remove (GPtrArray *farray,
530 GRealPtrArray* array = (GRealPtrArray*) farray;
533 g_return_val_if_fail (array, FALSE);
535 for (i = 0; i < array->len; i += 1)
537 if (array->pdata[i] == data)
539 g_ptr_array_remove_index (farray, i);
548 g_ptr_array_remove_fast (GPtrArray *farray,
551 GRealPtrArray* array = (GRealPtrArray*) farray;
554 g_return_val_if_fail (array, FALSE);
556 for (i = 0; i < array->len; i += 1)
558 if (array->pdata[i] == data)
560 g_ptr_array_remove_index_fast (farray, i);
569 g_ptr_array_add (GPtrArray *farray,
572 GRealPtrArray* array = (GRealPtrArray*) farray;
574 g_return_if_fail (array);
576 g_ptr_array_maybe_expand (array, 1);
578 array->pdata[array->len++] = data;
582 g_ptr_array_sort (GPtrArray *array,
583 GCompareFunc compare_func)
585 g_return_if_fail (array != NULL);
594 g_ptr_array_sort_with_data (GPtrArray *array,
595 GCompareDataFunc compare_func,
598 g_return_if_fail (array != NULL);
600 g_qsort_with_data (array->pdata,
608 * g_ptr_array_foreach:
609 * @array: a #GPtrArray
610 * @func: the function to call for each array element
611 * @user_data: user data to pass to the function
613 * Calls a function for each element of a #GPtrArray.
618 g_ptr_array_foreach (GPtrArray *array,
624 g_return_if_fail (array);
626 for (i = 0; i < array->len; i++)
627 (*func) (array->pdata[i], user_data);
633 GByteArray* g_byte_array_new (void)
635 return (GByteArray*) g_array_sized_new (FALSE, FALSE, 1, 0);
638 GByteArray* g_byte_array_sized_new (guint reserved_size)
640 return (GByteArray*) g_array_sized_new (FALSE, FALSE, 1, reserved_size);
643 guint8* g_byte_array_free (GByteArray *array,
644 gboolean free_segment)
646 return (guint8*) g_array_free ((GArray*) array, free_segment);
649 GByteArray* g_byte_array_append (GByteArray *array,
653 g_array_append_vals ((GArray*) array, (guint8*)data, len);
658 GByteArray* g_byte_array_prepend (GByteArray *array,
662 g_array_prepend_vals ((GArray*) array, (guint8*)data, len);
667 GByteArray* g_byte_array_set_size (GByteArray *array,
670 g_array_set_size ((GArray*) array, length);
675 GByteArray* g_byte_array_remove_index (GByteArray *array,
678 g_array_remove_index ((GArray*) array, index_);
683 GByteArray* g_byte_array_remove_index_fast (GByteArray *array,
686 g_array_remove_index_fast ((GArray*) array, index_);
692 g_byte_array_remove_range (GByteArray *array,
696 g_return_val_if_fail (array, NULL);
697 g_return_val_if_fail (index_ < array->len, NULL);
698 g_return_val_if_fail (index_ + length <= array->len, NULL);
700 return (GByteArray *)g_array_remove_range ((GArray*) array, index_, length);
704 g_byte_array_sort (GByteArray *array,
705 GCompareFunc compare_func)
707 g_array_sort ((GArray *) array, compare_func);
711 g_byte_array_sort_with_data (GByteArray *array,
712 GCompareDataFunc compare_func,
715 g_array_sort_with_data ((GArray *) array, compare_func, user_data);
718 #define __G_ARRAY_C__
719 #include "galiasdef.c"