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/.
38 #define MIN_ARRAY_SIZE 16
40 typedef struct _GRealArray GRealArray;
48 guint zero_terminated : 1;
52 #define g_array_elt_len(array,i) ((array)->elt_size * (i))
53 #define g_array_elt_pos(array,i) ((array)->data + g_array_elt_len((array),(i)))
54 #define g_array_elt_zero(array, pos, len) \
55 (memset (g_array_elt_pos ((array), pos), 0, g_array_elt_len ((array), len)))
56 #define g_array_zero_terminate(array) G_STMT_START{ \
57 if ((array)->zero_terminated) \
58 g_array_elt_zero ((array), (array)->len, 1); \
61 static gint g_nearest_pow (gint num) G_GNUC_CONST;
62 static void g_array_maybe_expand (GRealArray *array,
65 static GMemChunk *array_mem_chunk = NULL;
66 G_LOCK_DEFINE_STATIC (array_mem_chunk);
69 g_array_new (gboolean zero_terminated,
73 return (GArray*) g_array_sized_new (zero_terminated, clear, elt_size, 0);
76 GArray* g_array_sized_new (gboolean zero_terminated,
83 G_LOCK (array_mem_chunk);
85 array_mem_chunk = g_mem_chunk_new ("array mem chunk",
87 1024, G_ALLOC_AND_FREE);
89 array = g_chunk_new (GRealArray, array_mem_chunk);
90 G_UNLOCK (array_mem_chunk);
95 array->zero_terminated = (zero_terminated ? 1 : 0);
96 array->clear = (clear ? 1 : 0);
97 array->elt_size = elt_size;
99 if (array->zero_terminated || reserved_size != 0)
101 g_array_maybe_expand (array, reserved_size);
102 g_array_zero_terminate(array);
105 return (GArray*) array;
109 g_array_free (GArray *array,
110 gboolean free_segment)
114 g_return_val_if_fail (array, NULL);
118 g_free (array->data);
122 segment = array->data;
124 G_LOCK (array_mem_chunk);
125 g_mem_chunk_free (array_mem_chunk, array);
126 G_UNLOCK (array_mem_chunk);
132 g_array_append_vals (GArray *farray,
136 GRealArray *array = (GRealArray*) farray;
138 g_array_maybe_expand (array, len);
140 memcpy (g_array_elt_pos (array, array->len), data,
141 g_array_elt_len (array, len));
145 g_array_zero_terminate (array);
151 g_array_prepend_vals (GArray *farray,
155 GRealArray *array = (GRealArray*) farray;
157 g_array_maybe_expand (array, len);
159 g_memmove (g_array_elt_pos (array, len), g_array_elt_pos (array, 0),
160 g_array_elt_len (array, array->len));
162 memcpy (g_array_elt_pos (array, 0), data, g_array_elt_len (array, len));
166 g_array_zero_terminate (array);
172 g_array_insert_vals (GArray *farray,
177 GRealArray *array = (GRealArray*) farray;
179 g_array_maybe_expand (array, len);
181 g_memmove (g_array_elt_pos (array, len + index),
182 g_array_elt_pos (array, index),
183 g_array_elt_len (array, array->len - index));
185 memcpy (g_array_elt_pos (array, index), data, g_array_elt_len (array, len));
189 g_array_zero_terminate (array);
195 g_array_set_size (GArray *farray,
198 GRealArray *array = (GRealArray*) farray;
199 if (length > array->len)
201 g_array_maybe_expand (array, length - array->len);
204 g_array_elt_zero (array, array->len, length - array->len);
206 #ifdef ENABLE_GC_FRIENDLY
207 else if (length < array->len)
208 g_array_elt_zero (array, length, array->len - length);
209 #endif /* ENABLE_GC_FRIENDLY */
213 g_array_zero_terminate (array);
219 g_array_remove_index (GArray* farray,
222 GRealArray* array = (GRealArray*) farray;
224 g_return_val_if_fail (array, NULL);
226 g_return_val_if_fail (index < array->len, NULL);
228 if (index != array->len - 1)
229 g_memmove (g_array_elt_pos (array, index),
230 g_array_elt_pos (array, index + 1),
231 g_array_elt_len (array, array->len - index - 1));
235 #ifdef ENABLE_GC_FRIENDLY
236 g_array_elt_zero (array, array->len, 1);
237 #else /* !ENABLE_GC_FRIENDLY */
238 g_array_zero_terminate (array);
239 #endif /* ENABLE_GC_FRIENDLY */
245 g_array_remove_index_fast (GArray* farray,
248 GRealArray* array = (GRealArray*) farray;
250 g_return_val_if_fail (array, NULL);
252 g_return_val_if_fail (index < array->len, NULL);
254 if (index != array->len - 1)
255 memcpy (g_array_elt_pos (array, index),
256 g_array_elt_pos (array, array->len - 1),
257 g_array_elt_len (array, 1));
261 #ifdef ENABLE_GC_FRIENDLY
262 g_array_elt_zero (array, array->len, 1);
263 #else /* !ENABLE_GC_FRIENDLY */
264 g_array_zero_terminate (array);
265 #endif /* ENABLE_GC_FRIENDLY */
271 g_array_sort (GArray *farray,
272 GCompareFunc compare_func)
274 GRealArray *array = (GRealArray*) farray;
276 g_return_if_fail (array != NULL);
285 g_array_sort_with_data (GArray *farray,
286 GCompareDataFunc compare_func,
289 GRealArray *array = (GRealArray*) farray;
291 g_return_if_fail (array != 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);
577 g_ptr_array_sort_with_data (GPtrArray *array,
578 GCompareDataFunc compare_func,
581 g_return_if_fail (array != NULL);
583 g_qsort_with_data (array->pdata,
593 GByteArray* g_byte_array_new (void)
595 return (GByteArray*) g_array_sized_new (FALSE, FALSE, 1, 0);
598 GByteArray* g_byte_array_sized_new (guint reserved_size)
600 return (GByteArray*) g_array_sized_new (FALSE, FALSE, 1, reserved_size);
603 guint8* g_byte_array_free (GByteArray *array,
604 gboolean free_segment)
606 return (guint8*) g_array_free ((GArray*) array, free_segment);
609 GByteArray* g_byte_array_append (GByteArray *array,
613 g_array_append_vals ((GArray*) array, (guint8*)data, len);
618 GByteArray* g_byte_array_prepend (GByteArray *array,
622 g_array_prepend_vals ((GArray*) array, (guint8*)data, len);
627 GByteArray* g_byte_array_set_size (GByteArray *array,
630 g_array_set_size ((GArray*) array, length);
635 GByteArray* g_byte_array_remove_index (GByteArray *array,
638 g_array_remove_index((GArray*) array, index);
643 GByteArray* g_byte_array_remove_index_fast (GByteArray *array,
646 g_array_remove_index_fast((GArray*) array, index);
652 g_byte_array_sort (GByteArray *array,
653 GCompareFunc compare_func)
655 g_array_sort ((GArray *) array, compare_func);
659 g_byte_array_sort_with_data (GByteArray *array,
660 GCompareDataFunc compare_func,
663 g_array_sort_with_data ((GArray *) array, compare_func, user_data);