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/.
36 #define MIN_ARRAY_SIZE 16
38 typedef struct _GRealArray GRealArray;
46 guint zero_terminated : 1;
50 #define g_array_elt_len(array,i) ((array)->elt_size * (i))
51 #define g_array_elt_pos(array,i) ((array)->data + g_array_elt_len((array),(i)))
52 #define g_array_elt_zero(array, pos, len) \
53 (memset (g_array_elt_pos ((array), pos), 0, g_array_elt_len ((array), len)))
54 #define g_array_zero_terminate(array) G_STMT_START{ \
55 if ((array)->zero_terminated) \
56 g_array_elt_zero ((array), (array)->len, 1); \
59 static gint g_nearest_pow (gint num) G_GNUC_CONST;
60 static void g_array_maybe_expand (GRealArray *array,
63 static GMemChunk *array_mem_chunk = NULL;
64 G_LOCK_DEFINE_STATIC (array_mem_chunk);
67 g_array_new (gboolean zero_terminated,
71 return (GArray*) g_array_sized_new (zero_terminated, clear, elt_size, 0);
74 GArray* g_array_sized_new (gboolean zero_terminated,
81 G_LOCK (array_mem_chunk);
83 array_mem_chunk = g_mem_chunk_new ("array mem chunk",
85 1024, G_ALLOC_AND_FREE);
87 array = g_chunk_new (GRealArray, array_mem_chunk);
88 G_UNLOCK (array_mem_chunk);
93 array->zero_terminated = (zero_terminated ? 1 : 0);
94 array->clear = (clear ? 1 : 0);
95 array->elt_size = elt_size;
97 if (array->zero_terminated || reserved_size != 0)
99 g_array_maybe_expand (array, reserved_size);
100 g_array_zero_terminate(array);
103 return (GArray*) array;
107 g_array_free (GArray *array,
108 gboolean free_segment)
112 g_return_val_if_fail (array, NULL);
116 g_free (array->data);
120 segment = array->data;
122 G_LOCK (array_mem_chunk);
123 g_mem_chunk_free (array_mem_chunk, array);
124 G_UNLOCK (array_mem_chunk);
130 g_array_append_vals (GArray *farray,
134 GRealArray *array = (GRealArray*) farray;
136 g_array_maybe_expand (array, len);
138 memcpy (g_array_elt_pos (array, array->len), data,
139 g_array_elt_len (array, len));
143 g_array_zero_terminate (array);
149 g_array_prepend_vals (GArray *farray,
153 GRealArray *array = (GRealArray*) farray;
155 g_array_maybe_expand (array, len);
157 g_memmove (g_array_elt_pos (array, len), g_array_elt_pos (array, 0),
158 g_array_elt_len (array, array->len));
160 memcpy (g_array_elt_pos (array, 0), data, g_array_elt_len (array, len));
164 g_array_zero_terminate (array);
170 g_array_insert_vals (GArray *farray,
175 GRealArray *array = (GRealArray*) farray;
177 g_array_maybe_expand (array, len);
179 g_memmove (g_array_elt_pos (array, len + index),
180 g_array_elt_pos (array, index),
181 g_array_elt_len (array, array->len - index));
183 memcpy (g_array_elt_pos (array, index), data, g_array_elt_len (array, len));
187 g_array_zero_terminate (array);
193 g_array_set_size (GArray *farray,
196 GRealArray *array = (GRealArray*) farray;
197 if (length > array->len)
199 g_array_maybe_expand (array, length - array->len);
202 g_array_elt_zero (array, array->len, length - array->len);
204 #ifdef ENABLE_GC_FRIENDLY
205 else if (length < array->len)
206 g_array_elt_zero (array, length, array->len - length);
207 #endif /* ENABLE_GC_FRIENDLY */
211 g_array_zero_terminate (array);
217 g_array_remove_index (GArray* farray,
220 GRealArray* array = (GRealArray*) farray;
222 g_return_val_if_fail (array, NULL);
224 g_return_val_if_fail (index < array->len, NULL);
226 if (index != array->len - 1)
227 g_memmove (g_array_elt_pos (array, index),
228 g_array_elt_pos (array, index + 1),
229 g_array_elt_len (array, array->len - index - 1));
233 #ifdef ENABLE_GC_FRIENDLY
234 g_array_elt_zero (array, array->len, 1);
235 #else /* !ENABLE_GC_FRIENDLY */
236 g_array_zero_terminate (array);
237 #endif /* ENABLE_GC_FRIENDLY */
243 g_array_remove_index_fast (GArray* farray,
246 GRealArray* array = (GRealArray*) farray;
248 g_return_val_if_fail (array, NULL);
250 g_return_val_if_fail (index < array->len, NULL);
252 if (index != array->len - 1)
253 g_memmove (g_array_elt_pos (array, index),
254 g_array_elt_pos (array, array->len - 1),
255 g_array_elt_len (array, 1));
259 #ifdef ENABLE_GC_FRIENDLY
260 g_array_elt_zero (array, array->len, 1);
261 #else /* !ENABLE_GC_FRIENDLY */
262 g_array_zero_terminate (array);
263 #endif /* ENABLE_GC_FRIENDLY */
269 g_array_sort (GArray *farray,
270 GCompareFunc compare_func)
272 GRealArray *array = (GRealArray*) farray;
274 g_return_if_fail (array != NULL);
275 g_return_if_fail (array->data != NULL);
284 g_array_sort_with_data (GArray *farray,
285 GCompareFuncData compare_func,
288 GRealArray *array = (GRealArray*) farray;
290 g_return_if_fail (array != NULL);
291 g_return_if_fail (array->data != NULL);
293 g_qsort_with_data (array->data,
302 g_nearest_pow (gint num)
313 g_array_maybe_expand (GRealArray *array,
316 guint want_alloc = g_array_elt_len (array, array->len + len +
317 array->zero_terminated);
319 if (want_alloc > array->alloc)
321 want_alloc = g_nearest_pow (want_alloc);
322 want_alloc = MAX (want_alloc, MIN_ARRAY_SIZE);
324 array->data = g_realloc (array->data, want_alloc);
326 #ifdef ENABLE_GC_FRIENDLY
327 memset (array->data + array->alloc, 0, want_alloc - array->alloc);
328 #endif /* ENABLE_GC_FRIENDLY */
330 array->alloc = want_alloc;
337 typedef struct _GRealPtrArray GRealPtrArray;
339 struct _GRealPtrArray
346 static void g_ptr_array_maybe_expand (GRealPtrArray *array,
349 static GMemChunk *ptr_array_mem_chunk = NULL;
350 G_LOCK_DEFINE_STATIC (ptr_array_mem_chunk);
354 g_ptr_array_new (void)
356 return g_ptr_array_sized_new (0);
360 g_ptr_array_sized_new (guint reserved_size)
362 GRealPtrArray *array;
364 G_LOCK (ptr_array_mem_chunk);
365 if (!ptr_array_mem_chunk)
366 ptr_array_mem_chunk = g_mem_chunk_new ("array mem chunk",
367 sizeof (GRealPtrArray),
368 1024, G_ALLOC_AND_FREE);
370 array = g_chunk_new (GRealPtrArray, ptr_array_mem_chunk);
371 G_UNLOCK (ptr_array_mem_chunk);
377 if (reserved_size != 0)
378 g_ptr_array_maybe_expand (array, reserved_size);
380 return (GPtrArray*) array;
384 g_ptr_array_free (GPtrArray *array,
385 gboolean free_segment)
389 g_return_val_if_fail (array, NULL);
393 g_free (array->pdata);
397 segment = array->pdata;
399 G_LOCK (ptr_array_mem_chunk);
400 g_mem_chunk_free (ptr_array_mem_chunk, array);
401 G_UNLOCK (ptr_array_mem_chunk);
407 g_ptr_array_maybe_expand (GRealPtrArray *array,
410 if ((array->len + len) > array->alloc)
412 #ifdef ENABLE_GC_FRIENDLY
413 guint old_alloc = array->alloc;
414 #endif /* ENABLE_GC_FRIENDLY */
415 array->alloc = g_nearest_pow (array->len + len);
416 array->alloc = MAX (array->alloc, MIN_ARRAY_SIZE);
417 array->pdata = g_realloc (array->pdata, sizeof(gpointer) * array->alloc);
418 #ifdef ENABLE_GC_FRIENDLY
419 for ( ; old_alloc < array->alloc; old_alloc++)
420 array->pdata [old_alloc] = NULL;
421 #endif /* ENABLE_GC_FRIENDLY */
426 g_ptr_array_set_size (GPtrArray *farray,
429 GRealPtrArray* array = (GRealPtrArray*) farray;
431 g_return_if_fail (array);
433 if (length > array->len)
436 g_ptr_array_maybe_expand (array, (length - array->len));
438 * memset (array->pdata + array->len, 0,
439 * sizeof (gpointer) * (length - array->len));
440 * to make it really portable. Remember (void*)NULL needn't be
441 * bitwise zero. It of course is silly not to use memset (..,0,..).
443 for (i = array->len; i < length; i++)
444 array->pdata[i] = NULL;
446 #ifdef ENABLE_GC_FRIENDLY
447 else if (length < array->len)
450 for (i = length; i < array->len; i++)
451 array->pdata[i] = NULL;
453 #endif /* ENABLE_GC_FRIENDLY */
459 g_ptr_array_remove_index (GPtrArray* farray,
462 GRealPtrArray* array = (GRealPtrArray*) farray;
465 g_return_val_if_fail (array, NULL);
467 g_return_val_if_fail (index < array->len, NULL);
469 result = array->pdata[index];
471 if (index != array->len - 1)
472 g_memmove (array->pdata + index, array->pdata + index + 1,
473 sizeof (gpointer) * (array->len - index - 1));
477 #ifdef ENABLE_GC_FRIENDLY
478 array->pdata[array->len] = NULL;
479 #endif /* ENABLE_GC_FRIENDLY */
485 g_ptr_array_remove_index_fast (GPtrArray* farray,
488 GRealPtrArray* array = (GRealPtrArray*) farray;
491 g_return_val_if_fail (array, NULL);
493 g_return_val_if_fail (index < array->len, NULL);
495 result = array->pdata[index];
497 if (index != array->len - 1)
498 array->pdata[index] = array->pdata[array->len - 1];
502 #ifdef ENABLE_GC_FRIENDLY
503 array->pdata[array->len] = NULL;
504 #endif /* ENABLE_GC_FRIENDLY */
510 g_ptr_array_remove (GPtrArray* farray,
513 GRealPtrArray* array = (GRealPtrArray*) farray;
516 g_return_val_if_fail (array, FALSE);
518 for (i = 0; i < array->len; i += 1)
520 if (array->pdata[i] == data)
522 g_ptr_array_remove_index (farray, i);
531 g_ptr_array_remove_fast (GPtrArray* farray,
534 GRealPtrArray* array = (GRealPtrArray*) farray;
537 g_return_val_if_fail (array, FALSE);
539 for (i = 0; i < array->len; i += 1)
541 if (array->pdata[i] == data)
543 g_ptr_array_remove_index_fast (farray, i);
552 g_ptr_array_add (GPtrArray* farray,
555 GRealPtrArray* array = (GRealPtrArray*) farray;
557 g_return_if_fail (array);
559 g_ptr_array_maybe_expand (array, 1);
561 array->pdata[array->len++] = data;
565 g_ptr_array_sort (GPtrArray *array,
566 GCompareFunc compare_func)
568 g_return_if_fail (array != NULL);
569 g_return_if_fail (array->pdata != NULL);
578 g_ptr_array_sort_with_data (GPtrArray *array,
579 GCompareFuncData compare_func,
582 g_return_if_fail (array != NULL);
583 g_return_if_fail (array->pdata != NULL);
585 g_qsort_with_data (array->pdata,
595 GByteArray* g_byte_array_new (void)
597 return (GByteArray*) g_array_sized_new (FALSE, FALSE, 1, 0);
600 GByteArray* g_byte_array_sized_new (guint reserved_size)
602 return (GByteArray*) g_array_sized_new (FALSE, FALSE, 1, reserved_size);
605 guint8* g_byte_array_free (GByteArray *array,
606 gboolean free_segment)
608 return (guint8*) g_array_free ((GArray*) array, free_segment);
611 GByteArray* g_byte_array_append (GByteArray *array,
615 g_array_append_vals ((GArray*) array, (guint8*)data, len);
620 GByteArray* g_byte_array_prepend (GByteArray *array,
624 g_array_prepend_vals ((GArray*) array, (guint8*)data, len);
629 GByteArray* g_byte_array_set_size (GByteArray *array,
632 g_array_set_size ((GArray*) array, length);
637 GByteArray* g_byte_array_remove_index (GByteArray *array,
640 g_array_remove_index((GArray*) array, index);
645 GByteArray* g_byte_array_remove_index_fast (GByteArray *array,
648 g_array_remove_index_fast((GArray*) array, index);
654 g_byte_array_sort (GByteArray *array,
655 GCompareFunc compare_func)
657 g_array_sort ((GArray *) array, compare_func);
661 g_byte_array_sort_with_data (GByteArray *array,
662 GCompareFuncData compare_func,
665 g_array_sort_with_data ((GArray *) array, compare_func, user_data);