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,
73 static GMemChunk *array_mem_chunk = NULL;
74 G_LOCK_DEFINE_STATIC (array_mem_chunk);
77 g_array_new (gboolean zero_terminated,
81 return (GArray*) g_array_sized_new (zero_terminated, clear, elt_size, 0);
84 GArray* g_array_sized_new (gboolean zero_terminated,
91 G_LOCK (array_mem_chunk);
93 array_mem_chunk = g_mem_chunk_new ("array mem chunk",
95 1024, G_ALLOC_AND_FREE);
97 array = g_chunk_new (GRealArray, array_mem_chunk);
98 G_UNLOCK (array_mem_chunk);
103 array->zero_terminated = (zero_terminated ? 1 : 0);
104 array->clear = (clear ? 1 : 0);
105 array->elt_size = elt_size;
107 if (array->zero_terminated || reserved_size != 0)
109 g_array_maybe_expand (array, reserved_size);
110 g_array_zero_terminate(array);
113 return (GArray*) array;
117 g_array_free (GArray *array,
118 gboolean free_segment)
122 g_return_val_if_fail (array, NULL);
126 g_free (array->data);
130 segment = array->data;
132 G_LOCK (array_mem_chunk);
133 g_mem_chunk_free (array_mem_chunk, array);
134 G_UNLOCK (array_mem_chunk);
140 g_array_append_vals (GArray *farray,
144 GRealArray *array = (GRealArray*) farray;
146 g_array_maybe_expand (array, len);
148 memcpy (g_array_elt_pos (array, array->len), data,
149 g_array_elt_len (array, len));
153 g_array_zero_terminate (array);
159 g_array_prepend_vals (GArray *farray,
163 GRealArray *array = (GRealArray*) farray;
165 g_array_maybe_expand (array, len);
167 g_memmove (g_array_elt_pos (array, len), g_array_elt_pos (array, 0),
168 g_array_elt_len (array, array->len));
170 memcpy (g_array_elt_pos (array, 0), data, g_array_elt_len (array, len));
174 g_array_zero_terminate (array);
180 g_array_insert_vals (GArray *farray,
185 GRealArray *array = (GRealArray*) farray;
187 g_array_maybe_expand (array, len);
189 g_memmove (g_array_elt_pos (array, len + index),
190 g_array_elt_pos (array, index),
191 g_array_elt_len (array, array->len - index));
193 memcpy (g_array_elt_pos (array, index), data, g_array_elt_len (array, len));
197 g_array_zero_terminate (array);
203 g_array_set_size (GArray *farray,
206 GRealArray *array = (GRealArray*) farray;
207 if (length > array->len)
209 g_array_maybe_expand (array, length - array->len);
212 g_array_elt_zero (array, array->len, length - array->len);
214 #ifdef ENABLE_GC_FRIENDLY
215 else if (length < array->len)
216 g_array_elt_zero (array, length, array->len - length);
217 #endif /* ENABLE_GC_FRIENDLY */
221 g_array_zero_terminate (array);
227 g_array_remove_index (GArray* farray,
230 GRealArray* array = (GRealArray*) farray;
232 g_return_val_if_fail (array, NULL);
234 g_return_val_if_fail (index < array->len, NULL);
236 if (index != array->len - 1)
237 g_memmove (g_array_elt_pos (array, index),
238 g_array_elt_pos (array, index + 1),
239 g_array_elt_len (array, array->len - index - 1));
243 #ifdef ENABLE_GC_FRIENDLY
244 g_array_elt_zero (array, array->len, 1);
245 #else /* !ENABLE_GC_FRIENDLY */
246 g_array_zero_terminate (array);
247 #endif /* ENABLE_GC_FRIENDLY */
253 g_array_remove_index_fast (GArray* farray,
256 GRealArray* array = (GRealArray*) farray;
258 g_return_val_if_fail (array, NULL);
260 g_return_val_if_fail (index < array->len, NULL);
262 if (index != array->len - 1)
263 memcpy (g_array_elt_pos (array, index),
264 g_array_elt_pos (array, array->len - 1),
265 g_array_elt_len (array, 1));
269 #ifdef ENABLE_GC_FRIENDLY
270 g_array_elt_zero (array, array->len, 1);
271 #else /* !ENABLE_GC_FRIENDLY */
272 g_array_zero_terminate (array);
273 #endif /* ENABLE_GC_FRIENDLY */
279 g_array_remove_range (GArray *farray,
283 GRealArray *array = (GRealArray*) farray;
285 g_return_val_if_fail (array, NULL);
286 g_return_val_if_fail (index_ < array->len, NULL);
287 g_return_val_if_fail (index_ + length <= array->len, NULL);
289 if (index_ + length != array->len)
290 g_memmove (g_array_elt_pos (array, index_),
291 g_array_elt_pos (array, index_ + length),
292 (array->len - (index_ + length)) * array->elt_size);
294 array->len -= length;
295 #ifdef ENABLE_GC_FRIENDLY
296 g_array_elt_zero (array, array->len, length);
297 #else /* !ENABLE_GC_FRIENDLY */
298 g_array_zero_terminate (array);
299 #endif /* ENABLE_GC_FRIENDLY */
305 g_array_sort (GArray *farray,
306 GCompareFunc compare_func)
308 GRealArray *array = (GRealArray*) farray;
310 g_return_if_fail (array != NULL);
319 g_array_sort_with_data (GArray *farray,
320 GCompareDataFunc compare_func,
323 GRealArray *array = (GRealArray*) farray;
325 g_return_if_fail (array != NULL);
327 g_qsort_with_data (array->data,
336 g_nearest_pow (gint num)
347 g_array_maybe_expand (GRealArray *array,
350 guint want_alloc = g_array_elt_len (array, array->len + len +
351 array->zero_terminated);
353 if (want_alloc > array->alloc)
355 want_alloc = g_nearest_pow (want_alloc);
356 want_alloc = MAX (want_alloc, MIN_ARRAY_SIZE);
358 array->data = g_realloc (array->data, want_alloc);
360 #ifdef ENABLE_GC_FRIENDLY
361 memset (array->data + array->alloc, 0, want_alloc - array->alloc);
362 #endif /* ENABLE_GC_FRIENDLY */
364 array->alloc = want_alloc;
371 typedef struct _GRealPtrArray GRealPtrArray;
373 struct _GRealPtrArray
380 static void g_ptr_array_maybe_expand (GRealPtrArray *array,
383 static GMemChunk *ptr_array_mem_chunk = NULL;
384 G_LOCK_DEFINE_STATIC (ptr_array_mem_chunk);
388 g_ptr_array_new (void)
390 return g_ptr_array_sized_new (0);
394 g_ptr_array_sized_new (guint reserved_size)
396 GRealPtrArray *array;
398 G_LOCK (ptr_array_mem_chunk);
399 if (!ptr_array_mem_chunk)
400 ptr_array_mem_chunk = g_mem_chunk_new ("array mem chunk",
401 sizeof (GRealPtrArray),
402 1024, G_ALLOC_AND_FREE);
404 array = g_chunk_new (GRealPtrArray, ptr_array_mem_chunk);
405 G_UNLOCK (ptr_array_mem_chunk);
411 if (reserved_size != 0)
412 g_ptr_array_maybe_expand (array, reserved_size);
414 return (GPtrArray*) array;
418 g_ptr_array_free (GPtrArray *array,
419 gboolean free_segment)
423 g_return_val_if_fail (array, NULL);
427 g_free (array->pdata);
431 segment = array->pdata;
433 G_LOCK (ptr_array_mem_chunk);
434 g_mem_chunk_free (ptr_array_mem_chunk, array);
435 G_UNLOCK (ptr_array_mem_chunk);
441 g_ptr_array_maybe_expand (GRealPtrArray *array,
444 if ((array->len + len) > array->alloc)
446 #ifdef ENABLE_GC_FRIENDLY
447 guint old_alloc = array->alloc;
448 #endif /* ENABLE_GC_FRIENDLY */
449 array->alloc = g_nearest_pow (array->len + len);
450 array->alloc = MAX (array->alloc, MIN_ARRAY_SIZE);
451 array->pdata = g_realloc (array->pdata, sizeof (gpointer) * array->alloc);
452 #ifdef ENABLE_GC_FRIENDLY
453 for ( ; old_alloc < array->alloc; old_alloc++)
454 array->pdata [old_alloc] = NULL;
455 #endif /* ENABLE_GC_FRIENDLY */
460 g_ptr_array_set_size (GPtrArray *farray,
463 GRealPtrArray* array = (GRealPtrArray*) farray;
465 g_return_if_fail (array);
467 if (length > array->len)
470 g_ptr_array_maybe_expand (array, (length - array->len));
472 * memset (array->pdata + array->len, 0,
473 * sizeof (gpointer) * (length - array->len));
474 * to make it really portable. Remember (void*)NULL needn't be
475 * bitwise zero. It of course is silly not to use memset (..,0,..).
477 for (i = array->len; i < length; i++)
478 array->pdata[i] = NULL;
480 #ifdef ENABLE_GC_FRIENDLY
481 else if (length < array->len)
484 for (i = length; i < array->len; i++)
485 array->pdata[i] = NULL;
487 #endif /* ENABLE_GC_FRIENDLY */
493 g_ptr_array_remove_index (GPtrArray* farray,
496 GRealPtrArray* array = (GRealPtrArray*) farray;
499 g_return_val_if_fail (array, NULL);
501 g_return_val_if_fail (index < array->len, NULL);
503 result = array->pdata[index];
505 if (index != array->len - 1)
506 g_memmove (array->pdata + index, array->pdata + index + 1,
507 sizeof (gpointer) * (array->len - index - 1));
511 #ifdef ENABLE_GC_FRIENDLY
512 array->pdata[array->len] = NULL;
513 #endif /* ENABLE_GC_FRIENDLY */
519 g_ptr_array_remove_index_fast (GPtrArray* farray,
522 GRealPtrArray* array = (GRealPtrArray*) farray;
525 g_return_val_if_fail (array, NULL);
527 g_return_val_if_fail (index < array->len, NULL);
529 result = array->pdata[index];
531 if (index != array->len - 1)
532 array->pdata[index] = array->pdata[array->len - 1];
536 #ifdef ENABLE_GC_FRIENDLY
537 array->pdata[array->len] = NULL;
538 #endif /* ENABLE_GC_FRIENDLY */
544 g_ptr_array_remove_range (GPtrArray* farray,
548 GRealPtrArray* array = (GRealPtrArray*) farray;
550 g_return_if_fail (array);
551 g_return_if_fail (index_ < array->len);
552 g_return_if_fail (index_ + length <= array->len);
554 if (index_ + length != array->len)
555 g_memmove (&array->pdata[index_],
556 &array->pdata[index_ + length],
557 (array->len - (index_ + length)) * sizeof (gpointer));
559 array->len -= length;
560 #ifdef ENABLE_GC_FRIENDLY
563 for (i = 0; i < length; i++)
564 array->pdata[array->len + i] = NULL;
566 #endif /* ENABLE_GC_FRIENDLY */
570 g_ptr_array_remove (GPtrArray* farray,
573 GRealPtrArray* array = (GRealPtrArray*) farray;
576 g_return_val_if_fail (array, FALSE);
578 for (i = 0; i < array->len; i += 1)
580 if (array->pdata[i] == data)
582 g_ptr_array_remove_index (farray, i);
591 g_ptr_array_remove_fast (GPtrArray* farray,
594 GRealPtrArray* array = (GRealPtrArray*) farray;
597 g_return_val_if_fail (array, FALSE);
599 for (i = 0; i < array->len; i += 1)
601 if (array->pdata[i] == data)
603 g_ptr_array_remove_index_fast (farray, i);
612 g_ptr_array_add (GPtrArray* farray,
615 GRealPtrArray* array = (GRealPtrArray*) farray;
617 g_return_if_fail (array);
619 g_ptr_array_maybe_expand (array, 1);
621 array->pdata[array->len++] = data;
625 g_ptr_array_sort (GPtrArray *array,
626 GCompareFunc compare_func)
628 g_return_if_fail (array != NULL);
637 g_ptr_array_sort_with_data (GPtrArray *array,
638 GCompareDataFunc compare_func,
641 g_return_if_fail (array != NULL);
643 g_qsort_with_data (array->pdata,
651 * g_ptr_array_foreach:
652 * @array: a #GPtrArray
653 * @func: the function to call for each array element
654 * @user_data: user data to pass to the function
656 * Calls a function for each element of a #GPtrArray.
661 g_ptr_array_foreach (GPtrArray *array,
667 g_return_if_fail (array);
669 for (i = 0; i < array->len; i++)
670 (*func) (array->pdata[i], user_data);
676 GByteArray* g_byte_array_new (void)
678 return (GByteArray*) g_array_sized_new (FALSE, FALSE, 1, 0);
681 GByteArray* g_byte_array_sized_new (guint reserved_size)
683 return (GByteArray*) g_array_sized_new (FALSE, FALSE, 1, reserved_size);
686 guint8* g_byte_array_free (GByteArray *array,
687 gboolean free_segment)
689 return (guint8*) g_array_free ((GArray*) array, free_segment);
692 GByteArray* g_byte_array_append (GByteArray *array,
696 g_array_append_vals ((GArray*) array, (guint8*)data, len);
701 GByteArray* g_byte_array_prepend (GByteArray *array,
705 g_array_prepend_vals ((GArray*) array, (guint8*)data, len);
710 GByteArray* g_byte_array_set_size (GByteArray *array,
713 g_array_set_size ((GArray*) array, length);
718 GByteArray* g_byte_array_remove_index (GByteArray *array,
721 g_array_remove_index((GArray*) array, index);
726 GByteArray* g_byte_array_remove_index_fast (GByteArray *array,
729 g_array_remove_index_fast((GArray*) array, index);
735 g_byte_array_remove_range (GByteArray *array,
739 g_return_val_if_fail (array, NULL);
740 g_return_val_if_fail (index_ < array->len, NULL);
741 g_return_val_if_fail (index_ + length <= array->len, NULL);
743 return (GByteArray *)g_array_remove_range ((GArray*) array, index_, length);
747 g_byte_array_sort (GByteArray *array,
748 GCompareFunc compare_func)
750 g_array_sort ((GArray *) array, compare_func);
754 g_byte_array_sort_with_data (GByteArray *array,
755 GCompareDataFunc compare_func,
758 g_array_sort_with_data ((GArray *) array, compare_func, user_data);
761 #define __G_ARRAY_C__
762 #include "galiasdef.c"