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
);