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
48typedef struct _GRealArray  GRealArray;
49
50struct _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
69static gint g_nearest_pow        (gint        num) G_GNUC_CONST;
70static void g_array_maybe_expand (GRealArray *array,
71				  gint        len);
72
73GArray*
74g_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
81GArray* 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
104gchar*
105g_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
125GArray*
126g_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
144GArray*
145g_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
165GArray*
166g_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
188GArray*
189g_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
210GArray*
211g_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
235GArray*
236g_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
260GArray*
261g_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
285void
286g_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
299void
300g_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
316static gint
317g_nearest_pow (gint num)
318{
319  gint n = 1;
320
321  while (n < num)
322    n <<= 1;
323
324  return n;
325}
326
327static void
328g_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
351typedef struct _GRealPtrArray  GRealPtrArray;
352
353struct _GRealPtrArray
354{
355  gpointer *pdata;
356  guint     len;
357  guint     alloc;
358};
359
360static void g_ptr_array_maybe_expand (GRealPtrArray *array,
361				      gint           len);
362
363GPtrArray*
364g_ptr_array_new (void)
365{
366  return g_ptr_array_sized_new (0);
367}
368
369GPtrArray*
370g_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
384gpointer*
385g_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
405static void
406g_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
421void
422g_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
452gpointer
453g_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
477gpointer
478g_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
501void
502g_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
526gboolean
527g_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
547gboolean
548g_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
568void
569g_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
581void
582g_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
593void
594g_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 **/
617void
618g_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
633GByteArray* g_byte_array_new (void)
634{
635  return (GByteArray*) g_array_sized_new (FALSE, FALSE, 1, 0);
636}
637
638GByteArray* g_byte_array_sized_new (guint reserved_size)
639{
640  return (GByteArray*) g_array_sized_new (FALSE, FALSE, 1, reserved_size);
641}
642
643guint8*	    g_byte_array_free     (GByteArray *array,
644			           gboolean    free_segment)
645{
646  return (guint8*) g_array_free ((GArray*) array, free_segment);
647}
648
649GByteArray* 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
658GByteArray* 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
667GByteArray* 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
675GByteArray* 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
683GByteArray* 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
691GByteArray*
692g_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
703void
704g_byte_array_sort (GByteArray   *array,
705		   GCompareFunc  compare_func)
706{
707  g_array_sort ((GArray *) array, compare_func);
708}
709
710void
711g_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