1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
3 *
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.
8 *
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.
13 *
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.
18 */
19
20 /*
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/.
25 */
26
27 /*
28 * MT safe
29 */
30
31 #include "config.h"
32
33 #include <string.h>
34 #include <stdlib.h>
35
36 #include "garray.h"
37
38 #include "gmem.h"
39 #include "gthread.h"
40 #include "gmessages.h"
41 #include "gqsort.h"
42
43 #include "galias.h"
44
45
46 #define MIN_ARRAY_SIZE 16
47
48 typedef struct _GRealArray GRealArray;
49
50 struct _GRealArray
51 {
52 guint8 *data;
53 guint len;
54 guint alloc;
55 guint elt_size;
56 guint zero_terminated : 1;
57 guint clear : 1;
58 };
59
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); \
67 }G_STMT_END
68
69 static gint g_nearest_pow (gint num) G_GNUC_CONST;
70 static void g_array_maybe_expand (GRealArray *array,
71 gint len);
72
73 GArray*
g_array_new(gboolean zero_terminated,gboolean clear,guint elt_size)74 g_array_new (gboolean zero_terminated,
75 gboolean clear,
76 guint elt_size)
77 {
78 return (GArray*) g_array_sized_new (zero_terminated, clear, elt_size, 0);
79 }
80
g_array_sized_new(gboolean zero_terminated,gboolean clear,guint elt_size,guint reserved_size)81 GArray* g_array_sized_new (gboolean zero_terminated,
82 gboolean clear,
83 guint elt_size,
84 guint reserved_size)
85 {
86 GRealArray *array = g_slice_new (GRealArray);
87
88 array->data = NULL;
89 array->len = 0;
90 array->alloc = 0;
91 array->zero_terminated = (zero_terminated ? 1 : 0);
92 array->clear = (clear ? 1 : 0);
93 array->elt_size = elt_size;
94
95 if (array->zero_terminated || reserved_size != 0)
96 {
97 g_array_maybe_expand (array, reserved_size);
98 g_array_zero_terminate(array);
99 }
100
101 return (GArray*) array;
102 }
103
104 gchar*
g_array_free(GArray * array,gboolean free_segment)105 g_array_free (GArray *array,
106 gboolean free_segment)
107 {
108 gchar* segment;
109
110 g_return_val_if_fail (array, NULL);
111
112 if (free_segment)
113 {
114 g_free (array->data);
115 segment = NULL;
116 }
117 else
118 segment = array->data;
119
120 g_slice_free1 (sizeof (GRealArray), array);
121
122 return segment;
123 }
124
125 GArray*
g_array_append_vals(GArray * farray,gconstpointer data,guint len)126 g_array_append_vals (GArray *farray,
127 gconstpointer data,
128 guint len)
129 {
130 GRealArray *array = (GRealArray*) farray;
131
132 g_array_maybe_expand (array, len);
133
134 memcpy (g_array_elt_pos (array, array->len), data,
135 g_array_elt_len (array, len));
136
137 array->len += len;
138
139 g_array_zero_terminate (array);
140
141 return farray;
142 }
143
144 GArray*
g_array_prepend_vals(GArray * farray,gconstpointer data,guint len)145 g_array_prepend_vals (GArray *farray,
146 gconstpointer data,
147 guint len)
148 {
149 GRealArray *array = (GRealArray*) farray;
150
151 g_array_maybe_expand (array, len);
152
153 g_memmove (g_array_elt_pos (array, len), g_array_elt_pos (array, 0),
154 g_array_elt_len (array, array->len));
155
156 memcpy (g_array_elt_pos (array, 0), data, g_array_elt_len (array, len));
157
158 array->len += len;
159
160 g_array_zero_terminate (array);
161
162 return farray;
163 }
164
165 GArray*
g_array_insert_vals(GArray * farray,guint index_,gconstpointer data,guint len)166 g_array_insert_vals (GArray *farray,
167 guint index_,
168 gconstpointer data,
169 guint len)
170 {
171 GRealArray *array = (GRealArray*) farray;
172
173 g_array_maybe_expand (array, len);
174
175 g_memmove (g_array_elt_pos (array, len + index_),
176 g_array_elt_pos (array, index_),
177 g_array_elt_len (array, array->len - index_));
178
179 memcpy (g_array_elt_pos (array, index_), data, g_array_elt_len (array, len));
180
181 array->len += len;
182
183 g_array_zero_terminate (array);
184
185 return farray;
186 }
187
188 GArray*
g_array_set_size(GArray * farray,guint length)189 g_array_set_size (GArray *farray,
190 guint length)
191 {
192 GRealArray *array = (GRealArray*) farray;
193 if (length > array->len)
194 {
195 g_array_maybe_expand (array, length - array->len);
196
197 if (array->clear)
198 g_array_elt_zero (array, array->len, length - array->len);
199 }
200 else if (G_UNLIKELY (g_mem_gc_friendly) && length < array->len)
201 g_array_elt_zero (array, length, array->len - length);
202
203 array->len = length;
204
205 g_array_zero_terminate (array);
206
207 return farray;
208 }
209
210 GArray*
g_array_remove_index(GArray * farray,guint index_)211 g_array_remove_index (GArray *farray,
212 guint index_)
213 {
214 GRealArray* array = (GRealArray*) farray;
215
216 g_return_val_if_fail (array, NULL);
217
218 g_return_val_if_fail (index_ < array->len, NULL);
219
220 if (index_ != array->len - 1)
221 g_memmove (g_array_elt_pos (array, index_),
222 g_array_elt_pos (array, index_ + 1),
223 g_array_elt_len (array, array->len - index_ - 1));
224
225 array->len -= 1;
226
227 if (G_UNLIKELY (g_mem_gc_friendly))
228 g_array_elt_zero (array, array->len, 1);
229 else
230 g_array_zero_terminate (array);
231
232 return farray;
233 }
234
235 GArray*
g_array_remove_index_fast(GArray * farray,guint index_)236 g_array_remove_index_fast (GArray *farray,
237 guint index_)
238 {
239 GRealArray* array = (GRealArray*) farray;
240
241 g_return_val_if_fail (array, NULL);
242
243 g_return_val_if_fail (index_ < array->len, NULL);
244
245 if (index_ != array->len - 1)
246 memcpy (g_array_elt_pos (array, index_),
247 g_array_elt_pos (array, array->len - 1),
248 g_array_elt_len (array, 1));
249
250 array->len -= 1;
251
252 if (G_UNLIKELY (g_mem_gc_friendly))
253 g_array_elt_zero (array, array->len, 1);
254 else
255 g_array_zero_terminate (array);
256
257 return farray;
258 }
259
260 GArray*
g_array_remove_range(GArray * farray,guint index_,guint length)261 g_array_remove_range (GArray *farray,
262 guint index_,
263 guint length)
264 {
265 GRealArray *array = (GRealArray*) farray;
266
267 g_return_val_if_fail (array, NULL);
268 g_return_val_if_fail (index_ < array->len, NULL);
269 g_return_val_if_fail (index_ + length <= array->len, NULL);
270
271 if (index_ + length != array->len)
272 g_memmove (g_array_elt_pos (array, index_),
273 g_array_elt_pos (array, index_ + length),
274 (array->len - (index_ + length)) * array->elt_size);
275
276 array->len -= length;
277 if (G_UNLIKELY (g_mem_gc_friendly))
278 g_array_elt_zero (array, array->len, length);
279 else
280 g_array_zero_terminate (array);
281
282 return farray;
283 }
284
285 void
g_array_sort(GArray * farray,GCompareFunc compare_func)286 g_array_sort (GArray *farray,
287 GCompareFunc compare_func)
288 {
289 GRealArray *array = (GRealArray*) farray;
290
291 g_return_if_fail (array != NULL);
292
293 qsort (array->data,
294 array->len,
295 array->elt_size,
296 compare_func);
297 }
298
299 void
g_array_sort_with_data(GArray * farray,GCompareDataFunc compare_func,gpointer user_data)300 g_array_sort_with_data (GArray *farray,
301 GCompareDataFunc compare_func,
302 gpointer user_data)
303 {
304 GRealArray *array = (GRealArray*) farray;
305
306 g_return_if_fail (array != NULL);
307
308 g_qsort_with_data (array->data,
309 array->len,
310 array->elt_size,
311 compare_func,
312 user_data);
313 }
314
315
316 static gint
g_nearest_pow(gint num)317 g_nearest_pow (gint num)
318 {
319 gint n = 1;
320
321 while (n < num)
322 n <<= 1;
323
324 return n;
325 }
326
327 static void
g_array_maybe_expand(GRealArray * array,gint len)328 g_array_maybe_expand (GRealArray *array,
329 gint len)
330 {
331 guint want_alloc = g_array_elt_len (array, array->len + len +
332 array->zero_terminated);
333
334 if (want_alloc > array->alloc)
335 {
336 want_alloc = g_nearest_pow (want_alloc);
337 want_alloc = MAX (want_alloc, MIN_ARRAY_SIZE);
338
339 array->data = g_realloc (array->data, want_alloc);
340
341 if (G_UNLIKELY (g_mem_gc_friendly))
342 memset (array->data + array->alloc, 0, want_alloc - array->alloc);
343
344 array->alloc = want_alloc;
345 }
346 }
347
348 /* Pointer Array
349 */
350
351 typedef struct _GRealPtrArray GRealPtrArray;
352
353 struct _GRealPtrArray
354 {
355 gpointer *pdata;
356 guint len;
357 guint alloc;
358 };
359
360 static void g_ptr_array_maybe_expand (GRealPtrArray *array,
361 gint len);
362
363 GPtrArray*
g_ptr_array_new(void)364 g_ptr_array_new (void)
365 {
366 return g_ptr_array_sized_new (0);
367 }
368
369 GPtrArray*
g_ptr_array_sized_new(guint reserved_size)370 g_ptr_array_sized_new (guint reserved_size)
371 {
372 GRealPtrArray *array = g_slice_new (GRealPtrArray);
373
374 array->pdata = NULL;
375 array->len = 0;
376 array->alloc = 0;
377
378 if (reserved_size != 0)
379 g_ptr_array_maybe_expand (array, reserved_size);
380
381 return (GPtrArray*) array;
382 }
383
384 gpointer*
g_ptr_array_free(GPtrArray * array,gboolean free_segment)385 g_ptr_array_free (GPtrArray *array,
386 gboolean free_segment)
387 {
388 gpointer* segment;
389
390 g_return_val_if_fail (array, NULL);
391
392 if (free_segment)
393 {
394 g_free (array->pdata);
395 segment = NULL;
396 }
397 else
398 segment = array->pdata;
399
400 g_slice_free1 (sizeof (GRealPtrArray), array);
401
402 return segment;
403 }
404
405 static void
g_ptr_array_maybe_expand(GRealPtrArray * array,gint len)406 g_ptr_array_maybe_expand (GRealPtrArray *array,
407 gint len)
408 {
409 if ((array->len + len) > array->alloc)
410 {
411 guint old_alloc = array->alloc;
412 array->alloc = g_nearest_pow (array->len + len);
413 array->alloc = MAX (array->alloc, MIN_ARRAY_SIZE);
414 array->pdata = g_realloc (array->pdata, sizeof (gpointer) * array->alloc);
415 if (G_UNLIKELY (g_mem_gc_friendly))
416 for ( ; old_alloc < array->alloc; old_alloc++)
417 array->pdata [old_alloc] = NULL;
418 }
419 }
420
421 void
g_ptr_array_set_size(GPtrArray * farray,gint length)422 g_ptr_array_set_size (GPtrArray *farray,
423 gint length)
424 {
425 GRealPtrArray* array = (GRealPtrArray*) farray;
426
427 g_return_if_fail (array);
428
429 if (length > array->len)
430 {
431 int i;
432 g_ptr_array_maybe_expand (array, (length - array->len));
433 /* This is not
434 * memset (array->pdata + array->len, 0,
435 * sizeof (gpointer) * (length - array->len));
436 * to make it really portable. Remember (void*)NULL needn't be
437 * bitwise zero. It of course is silly not to use memset (..,0,..).
438 */
439 for (i = array->len; i < length; i++)
440 array->pdata[i] = NULL;
441 }
442 if (G_UNLIKELY (g_mem_gc_friendly) && length < array->len)
443 {
444 int i;
445 for (i = length; i < array->len; i++)
446 array->pdata[i] = NULL;
447 }
448
449 array->len = length;
450 }
451
452 gpointer
g_ptr_array_remove_index(GPtrArray * farray,guint index_)453 g_ptr_array_remove_index (GPtrArray *farray,
454 guint index_)
455 {
456 GRealPtrArray* array = (GRealPtrArray*) farray;
457 gpointer result;
458
459 g_return_val_if_fail (array, NULL);
460
461 g_return_val_if_fail (index_ < array->len, NULL);
462
463 result = array->pdata[index_];
464
465 if (index_ != array->len - 1)
466 g_memmove (array->pdata + index_, array->pdata + index_ + 1,
467 sizeof (gpointer) * (array->len - index_ - 1));
468
469 array->len -= 1;
470
471 if (G_UNLIKELY (g_mem_gc_friendly))
472 array->pdata[array->len] = NULL;
473
474 return result;
475 }
476
477 gpointer
g_ptr_array_remove_index_fast(GPtrArray * farray,guint index_)478 g_ptr_array_remove_index_fast (GPtrArray *farray,
479 guint index_)
480 {
481 GRealPtrArray* array = (GRealPtrArray*) farray;
482 gpointer result;
483
484 g_return_val_if_fail (array, NULL);
485
486 g_return_val_if_fail (index_ < array->len, NULL);
487
488 result = array->pdata[index_];
489
490 if (index_ != array->len - 1)
491 array->pdata[index_] = array->pdata[array->len - 1];
492
493 array->len -= 1;
494
495 if (G_UNLIKELY (g_mem_gc_friendly))
496 array->pdata[array->len] = NULL;
497
498 return result;
499 }
500
501 void
g_ptr_array_remove_range(GPtrArray * farray,guint index_,guint length)502 g_ptr_array_remove_range (GPtrArray *farray,
503 guint index_,
504 guint length)
505 {
506 GRealPtrArray* array = (GRealPtrArray*) farray;
507
508 g_return_if_fail (array);
509 g_return_if_fail (index_ < array->len);
510 g_return_if_fail (index_ + length <= array->len);
511
512 if (index_ + length != array->len)
513 g_memmove (&array->pdata[index_],
514 &array->pdata[index_ + length],
515 (array->len - (index_ + length)) * sizeof (gpointer));
516
517 array->len -= length;
518 if (G_UNLIKELY (g_mem_gc_friendly))
519 {
520 guint i;
521 for (i = 0; i < length; i++)
522 array->pdata[array->len + i] = NULL;
523 }
524 }
525
526 gboolean
g_ptr_array_remove(GPtrArray * farray,gpointer data)527 g_ptr_array_remove (GPtrArray *farray,
528 gpointer data)
529 {
530 GRealPtrArray* array = (GRealPtrArray*) farray;
531 guint i;
532
533 g_return_val_if_fail (array, FALSE);
534
535 for (i = 0; i < array->len; i += 1)
536 {
537 if (array->pdata[i] == data)
538 {
539 g_ptr_array_remove_index (farray, i);
540 return TRUE;
541 }
542 }
543
544 return FALSE;
545 }
546
547 gboolean
g_ptr_array_remove_fast(GPtrArray * farray,gpointer data)548 g_ptr_array_remove_fast (GPtrArray *farray,
549 gpointer data)
550 {
551 GRealPtrArray* array = (GRealPtrArray*) farray;
552 guint i;
553
554 g_return_val_if_fail (array, FALSE);
555
556 for (i = 0; i < array->len; i += 1)
557 {
558 if (array->pdata[i] == data)
559 {
560 g_ptr_array_remove_index_fast (farray, i);
561 return TRUE;
562 }
563 }
564
565 return FALSE;
566 }
567
568 void
g_ptr_array_add(GPtrArray * farray,gpointer data)569 g_ptr_array_add (GPtrArray *farray,
570 gpointer data)
571 {
572 GRealPtrArray* array = (GRealPtrArray*) farray;
573
574 g_return_if_fail (array);
575
576 g_ptr_array_maybe_expand (array, 1);
577
578 array->pdata[array->len++] = data;
579 }
580
581 void
g_ptr_array_sort(GPtrArray * array,GCompareFunc compare_func)582 g_ptr_array_sort (GPtrArray *array,
583 GCompareFunc compare_func)
584 {
585 g_return_if_fail (array != NULL);
586
587 qsort (array->pdata,
588 array->len,
589 sizeof (gpointer),
590 compare_func);
591 }
592
593 void
g_ptr_array_sort_with_data(GPtrArray * array,GCompareDataFunc compare_func,gpointer user_data)594 g_ptr_array_sort_with_data (GPtrArray *array,
595 GCompareDataFunc compare_func,
596 gpointer user_data)
597 {
598 g_return_if_fail (array != NULL);
599
600 g_qsort_with_data (array->pdata,
601 array->len,
602 sizeof (gpointer),
603 compare_func,
604 user_data);
605 }
606
607 /**
608 * g_ptr_array_foreach:
609 * @array: a #GPtrArray
610 * @func: the function to call for each array element
611 * @user_data: user data to pass to the function
612 *
613 * Calls a function for each element of a #GPtrArray.
614 *
615 * Since: 2.4
616 **/
617 void
g_ptr_array_foreach(GPtrArray * array,GFunc func,gpointer user_data)618 g_ptr_array_foreach (GPtrArray *array,
619 GFunc func,
620 gpointer user_data)
621 {
622 guint i;
623
624 g_return_if_fail (array);
625
626 for (i = 0; i < array->len; i++)
627 (*func) (array->pdata[i], user_data);
628 }
629
630 /* Byte arrays
631 */
632
g_byte_array_new(void)633 GByteArray* g_byte_array_new (void)
634 {
635 return (GByteArray*) g_array_sized_new (FALSE, FALSE, 1, 0);
636 }
637
g_byte_array_sized_new(guint reserved_size)638 GByteArray* g_byte_array_sized_new (guint reserved_size)
639 {
640 return (GByteArray*) g_array_sized_new (FALSE, FALSE, 1, reserved_size);
641 }
642
g_byte_array_free(GByteArray * array,gboolean free_segment)643 guint8* g_byte_array_free (GByteArray *array,
644 gboolean free_segment)
645 {
646 return (guint8*) g_array_free ((GArray*) array, free_segment);
647 }
648
g_byte_array_append(GByteArray * array,const guint8 * data,guint len)649 GByteArray* g_byte_array_append (GByteArray *array,
650 const guint8 *data,
651 guint len)
652 {
653 g_array_append_vals ((GArray*) array, (guint8*)data, len);
654
655 return array;
656 }
657
g_byte_array_prepend(GByteArray * array,const guint8 * data,guint len)658 GByteArray* g_byte_array_prepend (GByteArray *array,
659 const guint8 *data,
660 guint len)
661 {
662 g_array_prepend_vals ((GArray*) array, (guint8*)data, len);
663
664 return array;
665 }
666
g_byte_array_set_size(GByteArray * array,guint length)667 GByteArray* g_byte_array_set_size (GByteArray *array,
668 guint length)
669 {
670 g_array_set_size ((GArray*) array, length);
671
672 return array;
673 }
674
g_byte_array_remove_index(GByteArray * array,guint index_)675 GByteArray* g_byte_array_remove_index (GByteArray *array,
676 guint index_)
677 {
678 g_array_remove_index ((GArray*) array, index_);
679
680 return array;
681 }
682
g_byte_array_remove_index_fast(GByteArray * array,guint index_)683 GByteArray* g_byte_array_remove_index_fast (GByteArray *array,
684 guint index_)
685 {
686 g_array_remove_index_fast ((GArray*) array, index_);
687
688 return array;
689 }
690
691 GByteArray*
g_byte_array_remove_range(GByteArray * array,guint index_,guint length)692 g_byte_array_remove_range (GByteArray *array,
693 guint index_,
694 guint length)
695 {
696 g_return_val_if_fail (array, NULL);
697 g_return_val_if_fail (index_ < array->len, NULL);
698 g_return_val_if_fail (index_ + length <= array->len, NULL);
699
700 return (GByteArray *)g_array_remove_range ((GArray*) array, index_, length);
701 }
702
703 void
g_byte_array_sort(GByteArray * array,GCompareFunc compare_func)704 g_byte_array_sort (GByteArray *array,
705 GCompareFunc compare_func)
706 {
707 g_array_sort ((GArray *) array, compare_func);
708 }
709
710 void
g_byte_array_sort_with_data(GByteArray * array,GCompareDataFunc compare_func,gpointer user_data)711 g_byte_array_sort_with_data (GByteArray *array,
712 GCompareDataFunc compare_func,
713 gpointer user_data)
714 {
715 g_array_sort_with_data ((GArray *) array, compare_func, user_data);
716 }
717
718 #define __G_ARRAY_C__
719 #include "galiasdef.c"
720