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_insert_vals (GArray        *farray,
 117                      guint          index,
 118                      gconstpointer  data,
 119                      guint          len)
 120 {
 121   GRealArray *array = (GRealArray*) farray;
 122
 123   g_array_maybe_expand (array, len);
 124
 125   g_memmove (array->data + array->elt_size * (len + index),
 126              array->data + array->elt_size * index,
 127              array->elt_size * (array->len - index));
 128
 129   memcpy (array->data + array->elt_size * index, data, len * array->elt_size);
 130
 131   array->len += len;
 132
 133   return farray;
 134 }
 135
 136 GArray*
 137 g_array_set_size (GArray *farray,
 138                   guint   length)
 139 {
 140   GRealArray *array = (GRealArray*) farray;
 141
 142   if (array->len < length)
 143     g_array_maybe_expand (array, length - array->len);
 144
 145   array->len = length;
 146
 147   return farray;
 148 }
 149
 150 GArray*
 151 g_array_remove_index (GArray* farray,
 152                       guint index)
 153 {
 154   GRealArray* array = (GRealArray*) farray;
 155
 156   g_return_val_if_fail (array, NULL);
 157
 158   g_return_val_if_fail (index >= 0 && index < array->len, NULL);
 159
 160   if (index != array->len - 1)
 161       g_memmove (array->data + array->elt_size * index,
 162                  array->data + array->elt_size * (index + 1),
 163                  array->elt_size * (array->len - index - 1));
 164
 165   if (array->zero_terminated)
 166     memset (array->data + array->elt_size * (array->len - 1), 0,
 167             array->elt_size);
 168
 169   array->len -= 1;
 170
 171   return farray;
 172 }
 173
 174 GArray*
 175 g_array_remove_index_fast (GArray* farray,
 176                            guint index)
 177 {
 178   GRealArray* array = (GRealArray*) farray;
 179
 180   g_return_val_if_fail (array, NULL);
 181
 182   g_return_val_if_fail (index >= 0 && index < array->len, NULL);
 183
 184   if (index != array->len - 1)
 185     g_memmove (array->data + array->elt_size * index,
 186                array->data + array->elt_size * (array->len - 1),
 187                array->elt_size);
 188
 189   if (array->zero_terminated)
 190     memset (array->data + array->elt_size * (array->len - 1), 0,
 191             array->elt_size);
 192
 193   array->len -= 1;
 194
 195   return farray;
 196 }
 197
 198 static gint
 199 g_nearest_pow (gint num)
 200 {
 201   gint n = 1;
 202
 203   while (n < num)
 204     n <<= 1;
 205
 206   return n;
 207 }
 208
 209 static void
 210 g_array_maybe_expand (GRealArray *array,
 211                       gint        len)
 212 {
 213   guint want_alloc = (array->len + len + array->zero_terminated) * array->elt_size;
 214
 215   if (want_alloc > array->alloc)
 216     {
 217       guint old_alloc = array->alloc;
 218
 219       array->alloc = g_nearest_pow (want_alloc);
 220       array->alloc = MAX (array->alloc, MIN_ARRAY_SIZE);
 221
 222       array->data = g_realloc (array->data, array->alloc);
 223
 224       if (array->clear || array->zero_terminated)
 225         memset (array->data + old_alloc, 0, array->alloc - old_alloc);
 226     }
 227 }
 228
 229 /* Pointer Array
 230  */
 231
 232 typedef struct _GRealPtrArray  GRealPtrArray;
 233
 234 struct _GRealPtrArray
 235 {
 236   gpointer *pdata;
 237   guint     len;
 238   guint     alloc;
 239 };
 240
 241 static void g_ptr_array_maybe_expand (GRealPtrArray *array,
 242                                       gint           len);
 243
 244
 245 static GMemChunk *ptr_array_mem_chunk = NULL;
 246
 247
 248
 249 GPtrArray*
 250 g_ptr_array_new (void)
 251 {
 252   GRealPtrArray *array;
 253
 254   if (!ptr_array_mem_chunk)
 255     ptr_array_mem_chunk = g_mem_chunk_new ("array mem chunk",
 256                                            sizeof (GRealPtrArray),
 257                                            1024, G_ALLOC_AND_FREE);
 258
 259   array = g_chunk_new (GRealPtrArray, ptr_array_mem_chunk);
 260
 261   array->pdata = NULL;
 262   array->len = 0;
 263   array->alloc = 0;
 264
 265   return (GPtrArray*) array;
 266 }
 267
 268 void
 269 g_ptr_array_free (GPtrArray   *array,
 270                   gboolean  free_segment)
 271 {
 272   g_return_if_fail (array);
 273
 274   if (free_segment)
 275     g_free (array->pdata);
 276
 277   g_mem_chunk_free (ptr_array_mem_chunk, array);
 278 }
 279
 280 static void
 281 g_ptr_array_maybe_expand (GRealPtrArray *array,
 282                           gint        len)
 283 {
 284   guint old_alloc;
 285
 286   if ((array->len + len) > array->alloc)
 287     {
 288       old_alloc = array->alloc;
 289
 290       array->alloc = g_nearest_pow (array->len + len);
 291       array->alloc = MAX (array->alloc, MIN_ARRAY_SIZE);
 292       if (array->pdata)
 293         array->pdata = g_realloc (array->pdata, sizeof(gpointer) * array->alloc);
 294       else
 295         array->pdata = g_new0 (gpointer, array->alloc);
 296
 297       memset (array->pdata + old_alloc, 0, array->alloc - old_alloc);
 298     }
 299 }
 300
 301 void
 302 g_ptr_array_set_size  (GPtrArray   *farray,
 303                        gint          length)
 304 {
 305   GRealPtrArray* array = (GRealPtrArray*) farray;
 306
 307   g_return_if_fail (array);
 308
 309   if (length > array->len)
 310     g_ptr_array_maybe_expand (array, (length - array->len));
 311
 312   array->len = length;
 313 }
 314
 315 gpointer
 316 g_ptr_array_remove_index (GPtrArray* farray,
 317                           guint index)
 318 {
 319   GRealPtrArray* array = (GRealPtrArray*) farray;
 320   gpointer result;
 321
 322   g_return_val_if_fail (array, NULL);
 323
 324   g_return_val_if_fail (index >= 0 && index < array->len, NULL);
 325
 326   result = array->pdata[index];
 327
 328   if (index != array->len - 1)
 329     g_memmove (array->pdata + index, array->pdata + index + 1,
 330                array->len - index - 1);
 331
 332   array->pdata[array->len - 1] = NULL;
 333
 334   array->len -= 1;
 335
 336   return result;
 337 }
 338
 339 gpointer
 340 g_ptr_array_remove_index_fast (GPtrArray* farray,
 341                                guint index)
 342 {
 343   GRealPtrArray* array = (GRealPtrArray*) farray;
 344   gpointer result;
 345
 346   g_return_val_if_fail (array, NULL);
 347
 348   g_return_val_if_fail (index >= 0 && index < array->len, NULL);
 349
 350   result = array->pdata[index];
 351
 352   if (index != array->len - 1)
 353     array->pdata[index] = array->pdata[array->len - 1];
 354
 355   array->pdata[array->len - 1] = NULL;
 356
 357   array->len -= 1;
 358
 359   return result;
 360 }
 361
 362 gboolean
 363 g_ptr_array_remove (GPtrArray* farray,
 364                     gpointer data)
 365 {
 366   GRealPtrArray* array = (GRealPtrArray*) farray;
 367   int i;
 368
 369   g_return_val_if_fail (array, FALSE);
 370
 371   for (i = 0; i < array->len; i += 1)
 372     {
 373       if (array->pdata[i] == data)
 374         {
 375           g_ptr_array_remove_index (farray, i);
 376           return TRUE;
 377         }
 378     }
 379
 380   return FALSE;
 381 }
 382
 383 gboolean
 384 g_ptr_array_remove_fast (GPtrArray* farray,
 385                          gpointer data)
 386 {
 387   GRealPtrArray* array = (GRealPtrArray*) farray;
 388   int i;
 389
 390   g_return_val_if_fail (array, FALSE);
 391
 392   for (i = 0; i < array->len; i += 1)
 393     {
 394       if (array->pdata[i] == data)
 395         {
 396           g_ptr_array_remove_index_fast (farray, i);
 397           return TRUE;
 398         }
 399     }
 400
 401   return FALSE;
 402 }
 403
 404 void
 405 g_ptr_array_add (GPtrArray* farray,
 406                  gpointer data)
 407 {
 408   GRealPtrArray* array = (GRealPtrArray*) farray;
 409
 410   g_return_if_fail (array);
 411
 412   g_ptr_array_maybe_expand (array, 1);
 413
 414   array->pdata[array->len++] = data;
 415 }
 416
 417 /* Byte arrays
 418  */
 419
 420 GByteArray* g_byte_array_new      (void)
 421 {
 422   return (GByteArray*) g_array_new (FALSE, FALSE, 1);
 423 }
 424
 425 void        g_byte_array_free     (GByteArray *array,
 426                                    gboolean    free_segment)
 427 {
 428   g_array_free ((GArray*) array, free_segment);
 429 }
 430
 431 GByteArray* g_byte_array_append   (GByteArray *array,
 432                                    const guint8 *data,
 433                                    guint       len)
 434 {
 435   g_array_append_vals ((GArray*) array, (guint8*)data, len);
 436
 437   return array;
 438 }
 439
 440 GByteArray* g_byte_array_prepend  (GByteArray *array,
 441                                    const guint8 *data,
 442                                    guint       len)
 443 {
 444   g_array_prepend_vals ((GArray*) array, (guint8*)data, len);
 445
 446   return array;
 447 }
 448
 449 GByteArray* g_byte_array_set_size (GByteArray *array,
 450                                    guint       length)
 451 {
 452   g_array_set_size ((GArray*) array, length);
 453
 454   return array;
 455 }
 456
 457 GByteArray* g_byte_array_remove_index (GByteArray *array,
 458                                        guint index)
 459 {
 460   g_array_remove_index((GArray*) array, index);
 461
 462   return array;
 463 }
 464
 465 GByteArray* g_byte_array_remove_index_fast (GByteArray *array,
 466                                                    guint index)
 467 {
 468   g_array_remove_index_fast((GArray*) array, index);
 469
 470   return array;
 471 }