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 Library 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 * Library General Public License for more details.
13 *
14 * You should have received a copy of the GNU Library 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-1999.  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 <string.h>
32#include "glib.h"
33
34
35#define MIN_ARRAY_SIZE  16
36
37
38typedef struct _GRealArray  GRealArray;
39
40struct _GRealArray
41{
42  guint8 *data;
43  guint   len;
44  guint   alloc;
45  guint   elt_size;
46  guint   zero_terminated : 1;
47  guint   clear : 1;
48};
49
50
51static gint g_nearest_pow        (gint        num);
52static void g_array_maybe_expand (GRealArray *array,
53				  gint        len);
54
55static GMemChunk *array_mem_chunk = NULL;
56G_LOCK_DEFINE_STATIC (array_mem_chunk);
57
58GArray*
59g_array_new (gboolean zero_terminated,
60	     gboolean clear,
61	     guint    elt_size)
62{
63  GRealArray *array;
64
65  G_LOCK (array_mem_chunk);
66  if (!array_mem_chunk)
67    array_mem_chunk = g_mem_chunk_new ("array mem chunk",
68				       sizeof (GRealArray),
69				       1024, G_ALLOC_AND_FREE);
70
71  array = g_chunk_new (GRealArray, array_mem_chunk);
72  G_UNLOCK (array_mem_chunk);
73
74  array->data            = NULL;
75  array->len             = 0;
76  array->alloc           = 0;
77  array->zero_terminated = (zero_terminated ? 1 : 0);
78  array->clear           = (clear ? 1 : 0);
79  array->elt_size        = elt_size;
80
81  return (GArray*) array;
82}
83
84void
85g_array_free (GArray  *array,
86	      gboolean free_segment)
87{
88  if (free_segment)
89    g_free (array->data);
90
91  G_LOCK (array_mem_chunk);
92  g_mem_chunk_free (array_mem_chunk, array);
93  G_UNLOCK (array_mem_chunk);
94}
95
96GArray*
97g_array_append_vals (GArray       *farray,
98		     gconstpointer data,
99		     guint         len)
100{
101  GRealArray *array = (GRealArray*) farray;
102
103  g_array_maybe_expand (array, len);
104
105  memcpy (array->data + array->elt_size * array->len, data, array->elt_size * len);
106
107  array->len += len;
108
109  return farray;
110}
111
112GArray*
113g_array_prepend_vals (GArray        *farray,
114		      gconstpointer  data,
115		      guint          len)
116{
117  GRealArray *array = (GRealArray*) farray;
118
119  g_array_maybe_expand (array, len);
120
121  g_memmove (array->data + array->elt_size * len, array->data, array->elt_size * array->len);
122
123  memcpy (array->data, data, len * array->elt_size);
124
125  array->len += len;
126
127  return farray;
128}
129
130GArray*
131g_array_insert_vals (GArray        *farray,
132		     guint          index,
133		     gconstpointer  data,
134		     guint          len)
135{
136  GRealArray *array = (GRealArray*) farray;
137
138  g_array_maybe_expand (array, len);
139
140  g_memmove (array->data + array->elt_size * (len + index),
141	     array->data + array->elt_size * index,
142	     array->elt_size * (array->len - index));
143
144  memcpy (array->data + array->elt_size * index, data, len * array->elt_size);
145
146  array->len += len;
147
148  return farray;
149}
150
151GArray*
152g_array_set_size (GArray *farray,
153		  guint   length)
154{
155  GRealArray *array = (GRealArray*) farray;
156
157  if (array->len < length)
158    g_array_maybe_expand (array, length - array->len);
159
160  array->len = length;
161
162  return farray;
163}
164
165GArray*
166g_array_remove_index (GArray* farray,
167		      guint index)
168{
169  GRealArray* array = (GRealArray*) farray;
170
171  g_return_val_if_fail (array, NULL);
172
173  g_return_val_if_fail (index < array->len, NULL);
174
175  if (index != array->len - 1)
176      g_memmove (array->data + array->elt_size * index,
177		 array->data + array->elt_size * (index + 1),
178		 array->elt_size * (array->len - index - 1));
179
180  if (array->zero_terminated)
181    memset (array->data + array->elt_size * (array->len - 1), 0,
182	    array->elt_size);
183
184  array->len -= 1;
185
186  return farray;
187}
188
189GArray*
190g_array_remove_index_fast (GArray* farray,
191			   guint index)
192{
193  GRealArray* array = (GRealArray*) farray;
194
195  g_return_val_if_fail (array, NULL);
196
197  g_return_val_if_fail (index < array->len, NULL);
198
199  if (index != array->len - 1)
200    g_memmove (array->data + array->elt_size * index,
201	       array->data + array->elt_size * (array->len - 1),
202	       array->elt_size);
203
204  if (array->zero_terminated)
205    memset (array->data + array->elt_size * (array->len - 1), 0,
206	    array->elt_size);
207
208  array->len -= 1;
209
210  return farray;
211}
212
213static gint
214g_nearest_pow (gint num)
215{
216  gint n = 1;
217
218  while (n < num)
219    n <<= 1;
220
221  return n;
222}
223
224static void
225g_array_maybe_expand (GRealArray *array,
226		      gint        len)
227{
228  guint want_alloc = (array->len + len + array->zero_terminated) * array->elt_size;
229
230  if (want_alloc > array->alloc)
231    {
232      guint old_alloc = array->alloc;
233
234      array->alloc = g_nearest_pow (want_alloc);
235      array->alloc = MAX (array->alloc, MIN_ARRAY_SIZE);
236
237      array->data = g_realloc (array->data, array->alloc);
238
239      if (array->clear || array->zero_terminated)
240	memset (array->data + old_alloc, 0, array->alloc - old_alloc);
241    }
242}
243
244/* Pointer Array
245 */
246
247typedef struct _GRealPtrArray  GRealPtrArray;
248
249struct _GRealPtrArray
250{
251  gpointer *pdata;
252  guint     len;
253  guint     alloc;
254};
255
256static void g_ptr_array_maybe_expand (GRealPtrArray *array,
257				      gint           len);
258
259static GMemChunk *ptr_array_mem_chunk = NULL;
260G_LOCK_DEFINE_STATIC (ptr_array_mem_chunk);
261
262
263GPtrArray*
264g_ptr_array_new (void)
265{
266  GRealPtrArray *array;
267
268  G_LOCK (ptr_array_mem_chunk);
269  if (!ptr_array_mem_chunk)
270    ptr_array_mem_chunk = g_mem_chunk_new ("array mem chunk",
271					   sizeof (GRealPtrArray),
272					   1024, G_ALLOC_AND_FREE);
273
274  array = g_chunk_new (GRealPtrArray, ptr_array_mem_chunk);
275  G_UNLOCK (ptr_array_mem_chunk);
276
277  array->pdata = NULL;
278  array->len = 0;
279  array->alloc = 0;
280
281  return (GPtrArray*) array;
282}
283
284void
285g_ptr_array_free (GPtrArray   *array,
286		  gboolean  free_segment)
287{
288  g_return_if_fail (array);
289
290  if (free_segment)
291    g_free (array->pdata);
292
293  G_LOCK (ptr_array_mem_chunk);
294  g_mem_chunk_free (ptr_array_mem_chunk, array);
295  G_UNLOCK (ptr_array_mem_chunk);
296}
297
298static void
299g_ptr_array_maybe_expand (GRealPtrArray *array,
300			  gint        len)
301{
302  guint old_alloc;
303
304  if ((array->len + len) > array->alloc)
305    {
306      old_alloc = array->alloc;
307
308      array->alloc = g_nearest_pow (array->len + len);
309      array->alloc = MAX (array->alloc, MIN_ARRAY_SIZE);
310      if (array->pdata)
311	array->pdata = g_realloc (array->pdata, sizeof(gpointer) * array->alloc);
312      else
313	array->pdata = g_new0 (gpointer, array->alloc);
314
315      memset (array->pdata + old_alloc, 0,
316	      sizeof (gpointer) * (array->alloc - old_alloc));
317    }
318}
319
320void
321g_ptr_array_set_size  (GPtrArray   *farray,
322		       gint	     length)
323{
324  GRealPtrArray* array = (GRealPtrArray*) farray;
325
326  g_return_if_fail (array);
327
328  if (length > array->len)
329    g_ptr_array_maybe_expand (array, (length - array->len));
330
331  array->len = length;
332}
333
334gpointer
335g_ptr_array_remove_index (GPtrArray* farray,
336			  guint index)
337{
338  GRealPtrArray* array = (GRealPtrArray*) farray;
339  gpointer result;
340
341  g_return_val_if_fail (array, NULL);
342
343  g_return_val_if_fail (index < array->len, NULL);
344
345  result = array->pdata[index];
346
347  if (index != array->len - 1)
348    g_memmove (array->pdata + index, array->pdata + index + 1,
349	       sizeof (gpointer) * (array->len - index - 1));
350
351  array->pdata[array->len - 1] = NULL;
352
353  array->len -= 1;
354
355  return result;
356}
357
358gpointer
359g_ptr_array_remove_index_fast (GPtrArray* farray,
360			       guint index)
361{
362  GRealPtrArray* array = (GRealPtrArray*) farray;
363  gpointer result;
364
365  g_return_val_if_fail (array, NULL);
366
367  g_return_val_if_fail (index < array->len, NULL);
368
369  result = array->pdata[index];
370
371  if (index != array->len - 1)
372    array->pdata[index] = array->pdata[array->len - 1];
373
374  array->pdata[array->len - 1] = NULL;
375
376  array->len -= 1;
377
378  return result;
379}
380
381gboolean
382g_ptr_array_remove (GPtrArray* farray,
383		    gpointer data)
384{
385  GRealPtrArray* array = (GRealPtrArray*) farray;
386  int i;
387
388  g_return_val_if_fail (array, FALSE);
389
390  for (i = 0; i < array->len; i += 1)
391    {
392      if (array->pdata[i] == data)
393	{
394	  g_ptr_array_remove_index (farray, i);
395	  return TRUE;
396	}
397    }
398
399  return FALSE;
400}
401
402gboolean
403g_ptr_array_remove_fast (GPtrArray* farray,
404			 gpointer data)
405{
406  GRealPtrArray* array = (GRealPtrArray*) farray;
407  int i;
408
409  g_return_val_if_fail (array, FALSE);
410
411  for (i = 0; i < array->len; i += 1)
412    {
413      if (array->pdata[i] == data)
414	{
415	  g_ptr_array_remove_index_fast (farray, i);
416	  return TRUE;
417	}
418    }
419
420  return FALSE;
421}
422
423void
424g_ptr_array_add (GPtrArray* farray,
425		 gpointer data)
426{
427  GRealPtrArray* array = (GRealPtrArray*) farray;
428
429  g_return_if_fail (array);
430
431  g_ptr_array_maybe_expand (array, 1);
432
433  array->pdata[array->len++] = data;
434}
435
436/* Byte arrays
437 */
438
439GByteArray* g_byte_array_new      (void)
440{
441  return (GByteArray*) g_array_new (FALSE, FALSE, 1);
442}
443
444void	    g_byte_array_free     (GByteArray *array,
445			           gboolean    free_segment)
446{
447  g_array_free ((GArray*) array, free_segment);
448}
449
450GByteArray* g_byte_array_append   (GByteArray *array,
451				   const guint8 *data,
452				   guint       len)
453{
454  g_array_append_vals ((GArray*) array, (guint8*)data, len);
455
456  return array;
457}
458
459GByteArray* g_byte_array_prepend  (GByteArray *array,
460				   const guint8 *data,
461				   guint       len)
462{
463  g_array_prepend_vals ((GArray*) array, (guint8*)data, len);
464
465  return array;
466}
467
468GByteArray* g_byte_array_set_size (GByteArray *array,
469				   guint       length)
470{
471  g_array_set_size ((GArray*) array, length);
472
473  return array;
474}
475
476GByteArray* g_byte_array_remove_index (GByteArray *array,
477				       guint index)
478{
479  g_array_remove_index((GArray*) array, index);
480
481  return array;
482}
483
484GByteArray* g_byte_array_remove_index_fast (GByteArray *array,
485						   guint index)
486{
487  g_array_remove_index_fast((GArray*) array, index);
488
489  return array;
490}
491