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 #define MIN_ARRAY_SIZE 16
42 typedef struct _GRealArray GRealArray
;
50 guint zero_terminated
: 1;
54 #define g_array_elt_len(array,i) ((array)->elt_size * (i))
55 #define g_array_elt_pos(array,i) ((array)->data + g_array_elt_len((array),(i)))
56 #define g_array_elt_zero(array, pos, len) \
57 (memset (g_array_elt_pos ((array), pos), 0, g_array_elt_len ((array), len)))
58 #define g_array_zero_terminate(array) G_STMT_START{ \
59 if ((array)->zero_terminated) \
60 g_array_elt_zero ((array), (array)->len, 1); \
63 static gint
g_nearest_pow (gint num
) G_GNUC_CONST
;
64 static void g_array_maybe_expand (GRealArray
*array
,
67 static GMemChunk
*array_mem_chunk
= NULL
;
68 G_LOCK_DEFINE_STATIC (array_mem_chunk
);
71 g_array_new (gboolean zero_terminated
,
75 return (GArray
*) g_array_sized_new (zero_terminated
, clear
, elt_size
, 0);
78 GArray
* g_array_sized_new (gboolean zero_terminated
,
85 G_LOCK (array_mem_chunk
);
87 array_mem_chunk
= g_mem_chunk_new ("array mem chunk",
89 1024, G_ALLOC_AND_FREE
);
91 array
= g_chunk_new (GRealArray
, array_mem_chunk
);
92 G_UNLOCK (array_mem_chunk
);
97 array
->zero_terminated
= (zero_terminated
? 1 : 0);
98 array
->clear
= (clear
? 1 : 0);
99 array
->elt_size
= elt_size
;
101 if (array
->zero_terminated
|| reserved_size
!= 0)
103 g_array_maybe_expand (array
, reserved_size
);
104 g_array_zero_terminate(array
);
107 return (GArray
*) array
;
111 g_array_free (GArray
*array
,
112 gboolean free_segment
)
116 g_return_val_if_fail (array
, NULL
);
120 g_free (array
->data
);
124 segment
= array
->data
;
126 G_LOCK (array_mem_chunk
);
127 g_mem_chunk_free (array_mem_chunk
, array
);
128 G_UNLOCK (array_mem_chunk
);
134 g_array_append_vals (GArray
*farray
,
138 GRealArray
*array
= (GRealArray
*) farray
;
140 g_array_maybe_expand (array
, len
);
142 memcpy (g_array_elt_pos (array
, array
->len
), data
,
143 g_array_elt_len (array
, len
));
147 g_array_zero_terminate (array
);
153 g_array_prepend_vals (GArray
*farray
,
157 GRealArray
*array
= (GRealArray
*) farray
;
159 g_array_maybe_expand (array
, len
);
161 g_memmove (g_array_elt_pos (array
, len
), g_array_elt_pos (array
, 0),
162 g_array_elt_len (array
, array
->len
));
164 memcpy (g_array_elt_pos (array
, 0), data
, g_array_elt_len (array
, len
));
168 g_array_zero_terminate (array
);
174 g_array_insert_vals (GArray
*farray
,
179 GRealArray
*array
= (GRealArray
*) farray
;
181 g_array_maybe_expand (array
, len
);
183 g_memmove (g_array_elt_pos (array
, len
+ index
),
184 g_array_elt_pos (array
, index
),
185 g_array_elt_len (array
, array
->len
- index
));
187 memcpy (g_array_elt_pos (array
, index
), data
, g_array_elt_len (array
, len
));
191 g_array_zero_terminate (array
);
197 g_array_set_size (GArray
*farray
,
200 GRealArray
*array
= (GRealArray
*) farray
;
201 if (length
> array
->len
)
203 g_array_maybe_expand (array
, length
- array
->len
);
206 g_array_elt_zero (array
, array
->len
, length
- array
->len
);
208 #ifdef ENABLE_GC_FRIENDLY
209 else if (length
< array
->len
)
210 g_array_elt_zero (array
, length
, array
->len
- length
);
211 #endif /* ENABLE_GC_FRIENDLY */
215 g_array_zero_terminate (array
);
221 g_array_remove_index (GArray
* farray
,
224 GRealArray
* array
= (GRealArray
*) farray
;
226 g_return_val_if_fail (array
, NULL
);
228 g_return_val_if_fail (index
< array
->len
, NULL
);
230 if (index
!= array
->len
- 1)
231 g_memmove (g_array_elt_pos (array
, index
),
232 g_array_elt_pos (array
, index
+ 1),
233 g_array_elt_len (array
, array
->len
- index
- 1));
237 #ifdef ENABLE_GC_FRIENDLY
238 g_array_elt_zero (array
, array
->len
, 1);
239 #else /* !ENABLE_GC_FRIENDLY */
240 g_array_zero_terminate (array
);
241 #endif /* ENABLE_GC_FRIENDLY */
247 g_array_remove_index_fast (GArray
* farray
,
250 GRealArray
* array
= (GRealArray
*) farray
;
252 g_return_val_if_fail (array
, NULL
);
254 g_return_val_if_fail (index
< array
->len
, NULL
);
256 if (index
!= array
->len
- 1)
257 g_memmove (g_array_elt_pos (array
, index
),
258 g_array_elt_pos (array
, array
->len
- 1),
259 g_array_elt_len (array
, 1));
263 #ifdef ENABLE_GC_FRIENDLY
264 g_array_elt_zero (array
, array
->len
, 1);
265 #else /* !ENABLE_GC_FRIENDLY */
266 g_array_zero_terminate (array
);
267 #endif /* ENABLE_GC_FRIENDLY */
273 g_array_sort (GArray
*farray
,
274 GCompareFunc compare_func
)
276 GRealArray
*array
= (GRealArray
*) farray
;
278 g_return_if_fail (array
!= NULL
);
279 g_return_if_fail (array
->data
!= NULL
);
288 g_array_sort_with_data (GArray
*farray
,
289 GCompareDataFunc compare_func
,
292 GRealArray
*array
= (GRealArray
*) farray
;
294 g_return_if_fail (array
!= NULL
);
295 g_return_if_fail (array
->data
!= NULL
);
297 g_qsort_with_data (array
->data
,
306 g_nearest_pow (gint num
)
317 g_array_maybe_expand (GRealArray
*array
,
320 guint want_alloc
= g_array_elt_len (array
, array
->len
+ len
+
321 array
->zero_terminated
);
323 if (want_alloc
> array
->alloc
)
325 want_alloc
= g_nearest_pow (want_alloc
);
326 want_alloc
= MAX (want_alloc
, MIN_ARRAY_SIZE
);
328 array
->data
= g_realloc (array
->data
, want_alloc
);
330 #ifdef ENABLE_GC_FRIENDLY
331 memset (array
->data
+ array
->alloc
, 0, want_alloc
- array
->alloc
);
332 #endif /* ENABLE_GC_FRIENDLY */
334 array
->alloc
= want_alloc
;
341 typedef struct _GRealPtrArray GRealPtrArray
;
343 struct _GRealPtrArray
350 static void g_ptr_array_maybe_expand (GRealPtrArray
*array
,
353 static GMemChunk
*ptr_array_mem_chunk
= NULL
;
354 G_LOCK_DEFINE_STATIC (ptr_array_mem_chunk
);
358 g_ptr_array_new (void)
360 return g_ptr_array_sized_new (0);
364 g_ptr_array_sized_new (guint reserved_size
)
366 GRealPtrArray
*array
;
368 G_LOCK (ptr_array_mem_chunk
);
369 if (!ptr_array_mem_chunk
)
370 ptr_array_mem_chunk
= g_mem_chunk_new ("array mem chunk",
371 sizeof (GRealPtrArray
),
372 1024, G_ALLOC_AND_FREE
);
374 array
= g_chunk_new (GRealPtrArray
, ptr_array_mem_chunk
);
375 G_UNLOCK (ptr_array_mem_chunk
);
381 if (reserved_size
!= 0)
382 g_ptr_array_maybe_expand (array
, reserved_size
);
384 return (GPtrArray
*) array
;
388 g_ptr_array_free (GPtrArray
*array
,
389 gboolean free_segment
)
393 g_return_val_if_fail (array
, NULL
);
397 g_free (array
->pdata
);
401 segment
= array
->pdata
;
403 G_LOCK (ptr_array_mem_chunk
);
404 g_mem_chunk_free (ptr_array_mem_chunk
, array
);
405 G_UNLOCK (ptr_array_mem_chunk
);
411 g_ptr_array_maybe_expand (GRealPtrArray
*array
,
414 if ((array
->len
+ len
) > array
->alloc
)
416 #ifdef ENABLE_GC_FRIENDLY
417 guint old_alloc
= array
->alloc
;
418 #endif /* ENABLE_GC_FRIENDLY */
419 array
->alloc
= g_nearest_pow (array
->len
+ len
);
420 array
->alloc
= MAX (array
->alloc
, MIN_ARRAY_SIZE
);
421 array
->pdata
= g_realloc (array
->pdata
, sizeof(gpointer
) * array
->alloc
);
422 #ifdef ENABLE_GC_FRIENDLY
423 for ( ; old_alloc
< array
->alloc
; old_alloc
++)
424 array
->pdata
[old_alloc
] = NULL
;
425 #endif /* ENABLE_GC_FRIENDLY */
430 g_ptr_array_set_size (GPtrArray
*farray
,
433 GRealPtrArray
* array
= (GRealPtrArray
*) farray
;
435 g_return_if_fail (array
);
437 if (length
> array
->len
)
440 g_ptr_array_maybe_expand (array
, (length
- array
->len
));
442 * memset (array->pdata + array->len, 0,
443 * sizeof (gpointer) * (length - array->len));
444 * to make it really portable. Remember (void*)NULL needn't be
445 * bitwise zero. It of course is silly not to use memset (..,0,..).
447 for (i
= array
->len
; i
< length
; i
++)
448 array
->pdata
[i
] = NULL
;
450 #ifdef ENABLE_GC_FRIENDLY
451 else if (length
< array
->len
)
454 for (i
= length
; i
< array
->len
; i
++)
455 array
->pdata
[i
] = NULL
;
457 #endif /* ENABLE_GC_FRIENDLY */
463 g_ptr_array_remove_index (GPtrArray
* farray
,
466 GRealPtrArray
* array
= (GRealPtrArray
*) farray
;
469 g_return_val_if_fail (array
, NULL
);
471 g_return_val_if_fail (index
< array
->len
, NULL
);
473 result
= array
->pdata
[index
];
475 if (index
!= array
->len
- 1)
476 g_memmove (array
->pdata
+ index
, array
->pdata
+ index
+ 1,
477 sizeof (gpointer
) * (array
->len
- index
- 1));
481 #ifdef ENABLE_GC_FRIENDLY
482 array
->pdata
[array
->len
] = NULL
;
483 #endif /* ENABLE_GC_FRIENDLY */
489 g_ptr_array_remove_index_fast (GPtrArray
* farray
,
492 GRealPtrArray
* array
= (GRealPtrArray
*) farray
;
495 g_return_val_if_fail (array
, NULL
);
497 g_return_val_if_fail (index
< array
->len
, NULL
);
499 result
= array
->pdata
[index
];
501 if (index
!= array
->len
- 1)
502 array
->pdata
[index
] = array
->pdata
[array
->len
- 1];
506 #ifdef ENABLE_GC_FRIENDLY
507 array
->pdata
[array
->len
] = NULL
;
508 #endif /* ENABLE_GC_FRIENDLY */
514 g_ptr_array_remove (GPtrArray
* farray
,
517 GRealPtrArray
* array
= (GRealPtrArray
*) farray
;
520 g_return_val_if_fail (array
, FALSE
);
522 for (i
= 0; i
< array
->len
; i
+= 1)
524 if (array
->pdata
[i
] == data
)
526 g_ptr_array_remove_index (farray
, i
);
535 g_ptr_array_remove_fast (GPtrArray
* farray
,
538 GRealPtrArray
* array
= (GRealPtrArray
*) farray
;
541 g_return_val_if_fail (array
, FALSE
);
543 for (i
= 0; i
< array
->len
; i
+= 1)
545 if (array
->pdata
[i
] == data
)
547 g_ptr_array_remove_index_fast (farray
, i
);
556 g_ptr_array_add (GPtrArray
* farray
,
559 GRealPtrArray
* array
= (GRealPtrArray
*) farray
;
561 g_return_if_fail (array
);
563 g_ptr_array_maybe_expand (array
, 1);
565 array
->pdata
[array
->len
++] = data
;
569 g_ptr_array_sort (GPtrArray
*array
,
570 GCompareFunc compare_func
)
572 g_return_if_fail (array
!= NULL
);
573 g_return_if_fail (array
->pdata
!= NULL
);
582 g_ptr_array_sort_with_data (GPtrArray
*array
,
583 GCompareDataFunc compare_func
,
586 g_return_if_fail (array
!= NULL
);
587 g_return_if_fail (array
->pdata
!= NULL
);
589 g_qsort_with_data (array
->pdata
,
599 GByteArray
* g_byte_array_new (void)
601 return (GByteArray
*) g_array_sized_new (FALSE
, FALSE
, 1, 0);
604 GByteArray
* g_byte_array_sized_new (guint reserved_size
)
606 return (GByteArray
*) g_array_sized_new (FALSE
, FALSE
, 1, reserved_size
);
609 guint8
* g_byte_array_free (GByteArray
*array
,
610 gboolean free_segment
)
612 return (guint8
*) g_array_free ((GArray
*) array
, free_segment
);
615 GByteArray
* g_byte_array_append (GByteArray
*array
,
619 g_array_append_vals ((GArray
*) array
, (guint8
*)data
, len
);
624 GByteArray
* g_byte_array_prepend (GByteArray
*array
,
628 g_array_prepend_vals ((GArray
*) array
, (guint8
*)data
, len
);
633 GByteArray
* g_byte_array_set_size (GByteArray
*array
,
636 g_array_set_size ((GArray
*) array
, length
);
641 GByteArray
* g_byte_array_remove_index (GByteArray
*array
,
644 g_array_remove_index((GArray
*) array
, index
);
649 GByteArray
* g_byte_array_remove_index_fast (GByteArray
*array
,
652 g_array_remove_index_fast((GArray
*) array
, index
);
658 g_byte_array_sort (GByteArray
*array
,
659 GCompareFunc compare_func
)
661 g_array_sort ((GArray
*) array
, compare_func
);
665 g_byte_array_sort_with_data (GByteArray
*array
,
666 GCompareDataFunc compare_func
,
669 g_array_sort_with_data ((GArray
*) array
, compare_func
, user_data
);