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