source: trunk/third/glib/garray.c @ 14807

Revision 14807, 10.2 KB checked in by ghudson, 25 years ago (diff)
This commit was generated by cvs2svn to compensate for changes in r14806, which included commits to RCS files with non-trunk default branches.
Line 
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}
Note: See TracBrowser for help on using the repository browser.