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/.
39 #define MIN_ARRAY_SIZE 16
41 typedef struct _GRealArray GRealArray;
49 guint zero_terminated : 1;
53 #define g_array_elt_len(array,i) ((array)->elt_size * (i))
54 #define g_array_elt_pos(array,i) ((array)->data + g_array_elt_len((array),(i)))
55 #define g_array_elt_zero(array, pos, len) \
56 (memset (g_array_elt_pos ((array), pos), 0, g_array_elt_len ((array), len)))
57 #define g_array_zero_terminate(array) G_STMT_START{ \
58 if ((array)->zero_terminated) \
59 g_array_elt_zero ((array), (array)->len, 1); \
62 static gint g_nearest_pow (gint num) G_GNUC_CONST;
63 static void g_array_maybe_expand (GRealArray *array,
66 static GMemChunk *array_mem_chunk = NULL;
67 G_LOCK_DEFINE_STATIC (array_mem_chunk);
70 g_array_new (gboolean zero_terminated,
74 return (GArray*) g_array_sized_new (zero_terminated, clear, elt_size, 0);
77 GArray* g_array_sized_new (gboolean zero_terminated,
84 G_LOCK (array_mem_chunk);
86 array_mem_chunk = g_mem_chunk_new ("array mem chunk",
88 1024, G_ALLOC_AND_FREE);
90 array = g_chunk_new (GRealArray, array_mem_chunk);
91 G_UNLOCK (array_mem_chunk);
96 array->zero_terminated = (zero_terminated ? 1 : 0);
97 array->clear = (clear ? 1 : 0);
98 array->elt_size = elt_size;
100 if (array->zero_terminated || reserved_size != 0)
102 g_array_maybe_expand (array, reserved_size);
103 g_array_zero_terminate(array);
106 return (GArray*) array;
110 g_array_free (GArray *array,
111 gboolean free_segment)
115 g_return_val_if_fail (array, NULL);
119 g_free (array->data);
123 segment = array->data;
125 G_LOCK (array_mem_chunk);
126 g_mem_chunk_free (array_mem_chunk, array);
127 G_UNLOCK (array_mem_chunk);
133 g_array_append_vals (GArray *farray,
137 GRealArray *array = (GRealArray*) farray;
139 g_array_maybe_expand (array, len);
141 memcpy (g_array_elt_pos (array, array->len), data,
142 g_array_elt_len (array, len));
146 g_array_zero_terminate (array);
152 g_array_prepend_vals (GArray *farray,
156 GRealArray *array = (GRealArray*) farray;
158 g_array_maybe_expand (array, len);
160 g_memmove (g_array_elt_pos (array, len), g_array_elt_pos (array, 0),
161 g_array_elt_len (array, array->len));
163 memcpy (g_array_elt_pos (array, 0), data, g_array_elt_len (array, len));
167 g_array_zero_terminate (array);
173 g_array_insert_vals (GArray *farray,
178 GRealArray *array = (GRealArray*) farray;
180 g_array_maybe_expand (array, len);
182 g_memmove (g_array_elt_pos (array, len + index),
183 g_array_elt_pos (array, index),
184 g_array_elt_len (array, array->len - index));
186 memcpy (g_array_elt_pos (array, index), data, g_array_elt_len (array, len));
190 g_array_zero_terminate (array);
196 g_array_set_size (GArray *farray,
199 GRealArray *array = (GRealArray*) farray;
200 if (length > array->len)
202 g_array_maybe_expand (array, length - array->len);
205 g_array_elt_zero (array, array->len, length - array->len);
207 #ifdef ENABLE_GC_FRIENDLY
208 else if (length < array->len)
209 g_array_elt_zero (array, length, array->len - length);
210 #endif /* ENABLE_GC_FRIENDLY */
214 g_array_zero_terminate (array);
220 g_array_remove_index (GArray* farray,
223 GRealArray* array = (GRealArray*) farray;
225 g_return_val_if_fail (array, NULL);
227 g_return_val_if_fail (index < array->len, NULL);
229 if (index != array->len - 1)
230 g_memmove (g_array_elt_pos (array, index),
231 g_array_elt_pos (array, index + 1),
232 g_array_elt_len (array, array->len - index - 1));
236 #ifdef ENABLE_GC_FRIENDLY
237 g_array_elt_zero (array, array->len, 1);
238 #else /* !ENABLE_GC_FRIENDLY */
239 g_array_zero_terminate (array);
240 #endif /* ENABLE_GC_FRIENDLY */
246 g_array_remove_index_fast (GArray* farray,
249 GRealArray* array = (GRealArray*) farray;
251 g_return_val_if_fail (array, NULL);
253 g_return_val_if_fail (index < array->len, NULL);
255 if (index != array->len - 1)
256 memcpy (g_array_elt_pos (array, index),
257 g_array_elt_pos (array, array->len - 1),
258 g_array_elt_len (array, 1));
262 #ifdef ENABLE_GC_FRIENDLY
263 g_array_elt_zero (array, array->len, 1);
264 #else /* !ENABLE_GC_FRIENDLY */
265 g_array_zero_terminate (array);
266 #endif /* ENABLE_GC_FRIENDLY */
272 g_array_remove_range (GArray *farray,
276 GRealArray *array = (GRealArray*) farray;
278 g_return_val_if_fail (array, NULL);
279 g_return_val_if_fail (index_ < array->len, NULL);
280 g_return_val_if_fail (index_ + length <= array->len, NULL);
282 if (index_ + length != array->len)
283 g_memmove (g_array_elt_pos (array, index_),
284 g_array_elt_pos (array, index_ + length),
285 (array->len - (index_ + length)) * array->elt_size);
287 array->len -= length;
288 #ifdef ENABLE_GC_FRIENDLY
289 g_array_elt_zero (array, array->len, length);
290 #else /* !ENABLE_GC_FRIENDLY */
291 g_array_zero_terminate (array);
292 #endif /* ENABLE_GC_FRIENDLY */
298 g_array_sort (GArray *farray,
299 GCompareFunc compare_func)
301 GRealArray *array = (GRealArray*) farray;
303 g_return_if_fail (array != NULL);
312 g_array_sort_with_data (GArray *farray,
313 GCompareDataFunc compare_func,
316 GRealArray *array = (GRealArray*) farray;
318 g_return_if_fail (array != NULL);
320 g_qsort_with_data (array->data,
329 g_nearest_pow (gint num)
340 g_array_maybe_expand (GRealArray *array,
343 guint want_alloc = g_array_elt_len (array, array->len + len +
344 array->zero_terminated);
346 if (want_alloc > array->alloc)
348 want_alloc = g_nearest_pow (want_alloc);
349 want_alloc = MAX (want_alloc, MIN_ARRAY_SIZE);
351 array->data = g_realloc (array->data, want_alloc);
353 #ifdef ENABLE_GC_FRIENDLY
354 memset (array->data + array->alloc, 0, want_alloc - array->alloc);
355 #endif /* ENABLE_GC_FRIENDLY */
357 array->alloc = want_alloc;
364 typedef struct _GRealPtrArray GRealPtrArray;
366 struct _GRealPtrArray
373 static void g_ptr_array_maybe_expand (GRealPtrArray *array,
376 static GMemChunk *ptr_array_mem_chunk = NULL;
377 G_LOCK_DEFINE_STATIC (ptr_array_mem_chunk);
381 g_ptr_array_new (void)
383 return g_ptr_array_sized_new (0);
387 g_ptr_array_sized_new (guint reserved_size)
389 GRealPtrArray *array;
391 G_LOCK (ptr_array_mem_chunk);
392 if (!ptr_array_mem_chunk)
393 ptr_array_mem_chunk = g_mem_chunk_new ("array mem chunk",
394 sizeof (GRealPtrArray),
395 1024, G_ALLOC_AND_FREE);
397 array = g_chunk_new (GRealPtrArray, ptr_array_mem_chunk);
398 G_UNLOCK (ptr_array_mem_chunk);
404 if (reserved_size != 0)
405 g_ptr_array_maybe_expand (array, reserved_size);
407 return (GPtrArray*) array;
411 g_ptr_array_free (GPtrArray *array,
412 gboolean free_segment)
416 g_return_val_if_fail (array, NULL);
420 g_free (array->pdata);
424 segment = array->pdata;
426 G_LOCK (ptr_array_mem_chunk);
427 g_mem_chunk_free (ptr_array_mem_chunk, array);
428 G_UNLOCK (ptr_array_mem_chunk);
434 g_ptr_array_maybe_expand (GRealPtrArray *array,
437 if ((array->len + len) > array->alloc)
439 #ifdef ENABLE_GC_FRIENDLY
440 guint old_alloc = array->alloc;
441 #endif /* ENABLE_GC_FRIENDLY */
442 array->alloc = g_nearest_pow (array->len + len);
443 array->alloc = MAX (array->alloc, MIN_ARRAY_SIZE);
444 array->pdata = g_realloc (array->pdata, sizeof (gpointer) * array->alloc);
445 #ifdef ENABLE_GC_FRIENDLY
446 for ( ; old_alloc < array->alloc; old_alloc++)
447 array->pdata [old_alloc] = NULL;
448 #endif /* ENABLE_GC_FRIENDLY */
453 g_ptr_array_set_size (GPtrArray *farray,
456 GRealPtrArray* array = (GRealPtrArray*) farray;
458 g_return_if_fail (array);
460 if (length > array->len)
463 g_ptr_array_maybe_expand (array, (length - array->len));
465 * memset (array->pdata + array->len, 0,
466 * sizeof (gpointer) * (length - array->len));
467 * to make it really portable. Remember (void*)NULL needn't be
468 * bitwise zero. It of course is silly not to use memset (..,0,..).
470 for (i = array->len; i < length; i++)
471 array->pdata[i] = NULL;
473 #ifdef ENABLE_GC_FRIENDLY
474 else if (length < array->len)
477 for (i = length; i < array->len; i++)
478 array->pdata[i] = NULL;
480 #endif /* ENABLE_GC_FRIENDLY */
486 g_ptr_array_remove_index (GPtrArray* farray,
489 GRealPtrArray* array = (GRealPtrArray*) farray;
492 g_return_val_if_fail (array, NULL);
494 g_return_val_if_fail (index < array->len, NULL);
496 result = array->pdata[index];
498 if (index != array->len - 1)
499 g_memmove (array->pdata + index, array->pdata + index + 1,
500 sizeof (gpointer) * (array->len - index - 1));
504 #ifdef ENABLE_GC_FRIENDLY
505 array->pdata[array->len] = NULL;
506 #endif /* ENABLE_GC_FRIENDLY */
512 g_ptr_array_remove_index_fast (GPtrArray* farray,
515 GRealPtrArray* array = (GRealPtrArray*) farray;
518 g_return_val_if_fail (array, NULL);
520 g_return_val_if_fail (index < array->len, NULL);
522 result = array->pdata[index];
524 if (index != array->len - 1)
525 array->pdata[index] = array->pdata[array->len - 1];
529 #ifdef ENABLE_GC_FRIENDLY
530 array->pdata[array->len] = NULL;
531 #endif /* ENABLE_GC_FRIENDLY */
537 g_ptr_array_remove_range (GPtrArray* farray,
541 GRealPtrArray* array = (GRealPtrArray*) farray;
543 g_return_if_fail (array);
544 g_return_if_fail (index_ < array->len);
545 g_return_if_fail (index_ + length <= array->len);
547 if (index_ + length != array->len)
548 g_memmove (&array->pdata[index_],
549 &array->pdata[index_ + length],
550 (array->len - (index_ + length)) * sizeof (gpointer));
552 array->len -= length;
553 #ifdef ENABLE_GC_FRIENDLY
556 for (i = 0; i < length; i++)
557 array->pdata[array->len + i] = NULL;
559 #endif /* ENABLE_GC_FRIENDLY */
563 g_ptr_array_remove (GPtrArray* farray,
566 GRealPtrArray* array = (GRealPtrArray*) farray;
569 g_return_val_if_fail (array, FALSE);
571 for (i = 0; i < array->len; i += 1)
573 if (array->pdata[i] == data)
575 g_ptr_array_remove_index (farray, i);
584 g_ptr_array_remove_fast (GPtrArray* farray,
587 GRealPtrArray* array = (GRealPtrArray*) farray;
590 g_return_val_if_fail (array, FALSE);
592 for (i = 0; i < array->len; i += 1)
594 if (array->pdata[i] == data)
596 g_ptr_array_remove_index_fast (farray, i);
605 g_ptr_array_add (GPtrArray* farray,
608 GRealPtrArray* array = (GRealPtrArray*) farray;
610 g_return_if_fail (array);
612 g_ptr_array_maybe_expand (array, 1);
614 array->pdata[array->len++] = data;
618 g_ptr_array_sort (GPtrArray *array,
619 GCompareFunc compare_func)
621 g_return_if_fail (array != NULL);
630 g_ptr_array_sort_with_data (GPtrArray *array,
631 GCompareDataFunc compare_func,
634 g_return_if_fail (array != NULL);
636 g_qsort_with_data (array->pdata,
644 * g_ptr_array_foreach:
645 * @array: a #GPtrArray
646 * @func: the function to call for each array element
647 * @user_data: user data to pass to the function
649 * Calls a function for each element of a #GPtrArray.
654 g_ptr_array_foreach (GPtrArray *array,
660 g_return_if_fail (array);
662 for (i = 0; i < array->len; i++)
663 (*func) (array->pdata[i], user_data);
669 GByteArray* g_byte_array_new (void)
671 return (GByteArray*) g_array_sized_new (FALSE, FALSE, 1, 0);
674 GByteArray* g_byte_array_sized_new (guint reserved_size)
676 return (GByteArray*) g_array_sized_new (FALSE, FALSE, 1, reserved_size);
679 guint8* g_byte_array_free (GByteArray *array,
680 gboolean free_segment)
682 return (guint8*) g_array_free ((GArray*) array, free_segment);
685 GByteArray* g_byte_array_append (GByteArray *array,
689 g_array_append_vals ((GArray*) array, (guint8*)data, len);
694 GByteArray* g_byte_array_prepend (GByteArray *array,
698 g_array_prepend_vals ((GArray*) array, (guint8*)data, len);
703 GByteArray* g_byte_array_set_size (GByteArray *array,
706 g_array_set_size ((GArray*) array, length);
711 GByteArray* g_byte_array_remove_index (GByteArray *array,
714 g_array_remove_index((GArray*) array, index);
719 GByteArray* g_byte_array_remove_index_fast (GByteArray *array,
722 g_array_remove_index_fast((GArray*) array, index);
728 g_byte_array_remove_range (GByteArray *array,
732 g_return_val_if_fail (array, NULL);
733 g_return_val_if_fail (index_ < array->len, NULL);
734 g_return_val_if_fail (index_ + length <= array->len, NULL);
736 return (GByteArray *)g_array_remove_range ((GArray*) array, index_, length);
740 g_byte_array_sort (GByteArray *array,
741 GCompareFunc compare_func)
743 g_array_sort ((GArray *) array, compare_func);
747 g_byte_array_sort_with_data (GByteArray *array,
748 GCompareDataFunc compare_func,
751 g_array_sort_with_data ((GArray *) array, compare_func, user_data);