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