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