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 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 #include <string.h>
  20 #include "glib.h"
  21
  22
  23 #define MIN_ARRAY_SIZE  16
  24
  25
  26 typedef struct _GRealArray  GRealArray;
  27
  28 struct _GRealArray
  29 {
  30   guint8 *data;
  31   guint   len;
  32   guint   alloc;
  33   guint   elt_size;
  34   guint   zero_terminated : 1;
  35   guint   clear : 1;
  36 };
  37
  38
  39 static gint g_nearest_pow        (gint        num);
  40 static void g_array_maybe_expand (GRealArray *array,
  41                                   gint        len);
  42
  43
  44 static GMemChunk *array_mem_chunk = NULL;
  45
  46
  47 GArray*
  48 g_array_new (gboolean zero_terminated,
  49              gboolean clear,
  50              guint    elt_size)
  51 {
  52   GRealArray *array;
  53
  54   if (!array_mem_chunk)
  55     array_mem_chunk = g_mem_chunk_new ("array mem chunk",
  56                                        sizeof (GRealArray),
  57                                        1024, G_ALLOC_AND_FREE);
  58
  59   array = g_chunk_new (GRealArray, array_mem_chunk);
  60
  61   array->data            = NULL;
  62   array->len             = 0;
  63   array->alloc           = 0;
  64   array->zero_terminated = (zero_terminated ? 1 : 0);
  65   array->clear           = (clear ? 1 : 0);
  66   array->elt_size        = elt_size;
  67
  68   return (GArray*) array;
  69 }
  70
  71 void
  72 g_array_free (GArray  *array,
  73               gboolean free_segment)
  74 {
  75   if (free_segment)
  76     g_free (array->data);
  77
  78   g_mem_chunk_free (array_mem_chunk, array);
  79 }
  80
  81 GArray*
  82 g_array_append_vals (GArray       *farray,
  83                      gconstpointer data,
  84                      guint         len)
  85 {
  86   GRealArray *array = (GRealArray*) farray;
  87
  88   g_array_maybe_expand (array, len);
  89
  90   memcpy (array->data + array->elt_size * array->len, data, array->elt_size * len);
  91
  92   array->len += len;
  93
  94   return farray;
  95 }
  96
  97 GArray*
  98 g_array_prepend_vals (GArray        *farray,
  99                       gconstpointer  data,
 100                       guint          len)
 101 {
 102   GRealArray *array = (GRealArray*) farray;
 103
 104   g_array_maybe_expand (array, len);
 105
 106   g_memmove (array->data + array->elt_size * len, array->data, array->elt_size * array->len);
 107
 108   memcpy (array->data, data, len * array->elt_size);
 109
 110   array->len += len;
 111
 112   return farray;
 113 }
 114
 115 GArray*
 116 g_array_set_size (GArray *farray,
 117                   guint   length)
 118 {
 119   GRealArray *array = (GRealArray*) farray;
 120
 121   if (array->len < length)
 122     g_array_maybe_expand (array, length - array->len);
 123
 124   array->len = length;
 125
 126   return farray;
 127 }
 128
 129 static gint
 130 g_nearest_pow (gint num)
 131 {
 132   gint n = 1;
 133
 134   while (n < num)
 135     n <<= 1;
 136
 137   return n;
 138 }
 139
 140 static void
 141 g_array_maybe_expand (GRealArray *array,
 142                       gint        len)
 143 {
 144   guint want_alloc = (array->len + len + array->zero_terminated) * array->elt_size;
 145
 146   if (want_alloc > array->alloc)
 147     {
 148       guint old_alloc = array->alloc;
 149
 150       array->alloc = g_nearest_pow (want_alloc);
 151       array->alloc = MAX (array->alloc, MIN_ARRAY_SIZE);
 152
 153       array->data = g_realloc (array->data, array->alloc);
 154
 155       if (array->clear || array->zero_terminated)
 156         memset (array->data + old_alloc, 0, array->alloc - old_alloc);
 157     }
 158 }
 159
 160 /* Pointer Array
 161  */
 162
 163 typedef struct _GRealPtrArray  GRealPtrArray;
 164
 165 struct _GRealPtrArray
 166 {
 167   gpointer *pdata;
 168   guint     len;
 169   guint     alloc;
 170 };
 171
 172 static void g_ptr_array_maybe_expand (GRealPtrArray *array,
 173                                       gint           len);
 174
 175
 176 static GMemChunk *ptr_array_mem_chunk = NULL;
 177
 178
 179
 180 GPtrArray*
 181 g_ptr_array_new ()
 182 {
 183   GRealPtrArray *array;
 184
 185   if (!ptr_array_mem_chunk)
 186     ptr_array_mem_chunk = g_mem_chunk_new ("array mem chunk",
 187                                            sizeof (GRealPtrArray),
 188                                            1024, G_ALLOC_AND_FREE);
 189
 190   array = g_chunk_new (GRealPtrArray, ptr_array_mem_chunk);
 191
 192   array->pdata = NULL;
 193   array->len = 0;
 194   array->alloc = 0;
 195
 196   return (GPtrArray*) array;
 197 }
 198
 199 void
 200 g_ptr_array_free (GPtrArray   *array,
 201                   gboolean  free_segment)
 202 {
 203   g_return_if_fail (array);
 204
 205   if (free_segment)
 206     g_free (array->pdata);
 207
 208   g_mem_chunk_free (ptr_array_mem_chunk, array);
 209 }
 210
 211 static void
 212 g_ptr_array_maybe_expand (GRealPtrArray *array,
 213                           gint        len)
 214 {
 215   guint old_alloc;
 216
 217   if ((array->len + len) > array->alloc)
 218     {
 219       old_alloc = array->alloc;
 220
 221       array->alloc = g_nearest_pow (array->len + len);
 222       array->alloc = MAX (array->alloc, MIN_ARRAY_SIZE);
 223       if (array->pdata)
 224         array->pdata = g_realloc (array->pdata, sizeof(gpointer) * array->alloc);
 225       else
 226         array->pdata = g_new0 (gpointer, array->alloc);
 227
 228       memset (array->pdata + old_alloc, 0, array->alloc - old_alloc);
 229     }
 230 }
 231
 232 void
 233 g_ptr_array_set_size  (GPtrArray   *farray,
 234                        gint          length)
 235 {
 236   GRealPtrArray* array = (GRealPtrArray*) farray;
 237
 238   g_return_if_fail (array);
 239
 240   if (length > array->len)
 241     g_ptr_array_maybe_expand (array, (length - array->len));
 242
 243   array->len = length;
 244 }
 245
 246 gpointer
 247 g_ptr_array_remove_index (GPtrArray* farray,
 248                           gint index)
 249 {
 250   GRealPtrArray* array = (GRealPtrArray*) farray;
 251   gpointer result;
 252
 253   g_return_val_if_fail (array, NULL);
 254
 255   g_return_val_if_fail (index >= 0 && index < array->len, NULL);
 256
 257   result = array->pdata[index];
 258
 259   array->pdata[index] = array->pdata[array->len - 1];
 260
 261   array->pdata[array->len - 1] = NULL;
 262
 263   array->len -= 1;
 264
 265   return result;
 266 }
 267
 268 gboolean
 269 g_ptr_array_remove (GPtrArray* farray,
 270                     gpointer data)
 271 {
 272   GRealPtrArray* array = (GRealPtrArray*) farray;
 273   int i;
 274
 275   g_return_val_if_fail (array, FALSE);
 276
 277   for (i = 0; i < array->len; i += 1)
 278     {
 279       if (array->pdata[i] == data)
 280         {
 281           g_ptr_array_remove_index (farray, i);
 282           return TRUE;
 283         }
 284     }
 285
 286   return FALSE;
 287 }
 288
 289 void
 290 g_ptr_array_add (GPtrArray* farray,
 291                  gpointer data)
 292 {
 293   GRealPtrArray* array = (GRealPtrArray*) farray;
 294
 295   g_return_if_fail (array);
 296
 297   g_ptr_array_maybe_expand (array, 1);
 298
 299   array->pdata[array->len++] = data;
 300 }
 301
 302 /* Byte arrays
 303  */
 304
 305 GByteArray* g_byte_array_new      (void)
 306 {
 307   return (GByteArray*) g_array_new (FALSE, FALSE, 1);
 308 }
 309
 310 void        g_byte_array_free     (GByteArray *array,
 311                                    gboolean    free_segment)
 312 {
 313   g_array_free ((GArray*) array, free_segment);
 314 }
 315
 316 GByteArray* g_byte_array_append   (GByteArray *array,
 317                                    const guint8 *data,
 318                                    guint       len)
 319 {
 320   g_array_append_vals ((GArray*) array, (guint8*)data, len);
 321
 322   return array;
 323 }
 324
 325 GByteArray* g_byte_array_prepend  (GByteArray *array,
 326                                    const guint8 *data,
 327                                    guint       len)
 328 {
 329   g_array_prepend_vals ((GArray*) array, (guint8*)data, len);
 330
 331   return array;
 332 }
 333
 334 GByteArray* g_byte_array_set_size (GByteArray *array,
 335                                    guint       length)
 336 {
 337   g_array_set_size ((GArray*) array, length);
 338
 339   return array;
 340 }