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 Lesser 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  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser 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-2000.  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 typedef struct _GRealArray  GRealArray;
  38
  39 struct _GRealArray
  40 {
  41   guint8 *data;
  42   guint   len;
  43   guint   alloc;
  44   guint   elt_size;
  45   guint   zero_terminated : 1;
  46   guint   clear : 1;
  47 };
  48
  49 #define g_array_elt_len(array,i) ((array)->elt_size * (i))
  50 #define g_array_elt_pos(array,i) ((array)->data + g_array_elt_len((array),(i)))
  51 #define g_array_elt_zero(array, pos, len)                               \
  52   (memset (g_array_elt_pos ((array), pos), 0,  g_array_elt_len ((array), len)))
  53 #define g_array_zero_terminate(array) G_STMT_START{                     \
  54   if ((array)->zero_terminated)                                         \
  55     g_array_elt_zero ((array), (array)->len, 1);                        \
  56 }G_STMT_END
  57
  58 static gint g_nearest_pow        (gint        num) G_GNUC_CONST;
  59 static void g_array_maybe_expand (GRealArray *array,
  60                                   gint        len);
  61
  62 static GMemChunk *array_mem_chunk = NULL;
  63 G_LOCK_DEFINE_STATIC (array_mem_chunk);
  64
  65 GArray*
  66 g_array_new (gboolean zero_terminated,
  67              gboolean clear,
  68              guint    elt_size)
  69 {
  70   return (GArray*) g_array_sized_new (zero_terminated, clear, elt_size, 0);
  71 }
  72
  73 GArray* g_array_sized_new (gboolean zero_terminated,
  74                            gboolean clear,
  75                            guint    elt_size,
  76                            guint    reserved_size)
  77 {
  78   GRealArray *array;
  79
  80   G_LOCK (array_mem_chunk);
  81   if (!array_mem_chunk)
  82     array_mem_chunk = g_mem_chunk_new ("array mem chunk",
  83                                        sizeof (GRealArray),
  84                                        1024, G_ALLOC_AND_FREE);
  85
  86   array = g_chunk_new (GRealArray, array_mem_chunk);
  87   G_UNLOCK (array_mem_chunk);
  88
  89   array->data            = NULL;
  90   array->len             = 0;
  91   array->alloc           = 0;
  92   array->zero_terminated = (zero_terminated ? 1 : 0);
  93   array->clear           = (clear ? 1 : 0);
  94   array->elt_size        = elt_size;
  95
  96   if (array->zero_terminated || reserved_size != 0)
  97     {
  98       g_array_maybe_expand (array, reserved_size);
  99       g_array_zero_terminate(array);
 100     }
 101
 102   return (GArray*) array;
 103 }
 104
 105 gchar*
 106 g_array_free (GArray  *array,
 107               gboolean free_segment)
 108 {
 109   gchar* segment;
 110
 111   g_return_val_if_fail (array, NULL);
 112
 113   if (free_segment)
 114     {
 115       g_free (array->data);
 116       segment = NULL;
 117     }
 118   else
 119     segment = array->data;
 120
 121   G_LOCK (array_mem_chunk);
 122   g_mem_chunk_free (array_mem_chunk, array);
 123   G_UNLOCK (array_mem_chunk);
 124
 125   return segment;
 126 }
 127
 128 GArray*
 129 g_array_append_vals (GArray       *farray,
 130                      gconstpointer data,
 131                      guint         len)
 132 {
 133   GRealArray *array = (GRealArray*) farray;
 134
 135   g_array_maybe_expand (array, len);
 136
 137   memcpy (g_array_elt_pos (array, array->len), data,
 138           g_array_elt_len (array, len));
 139
 140   array->len += len;
 141
 142   g_array_zero_terminate (array);
 143
 144   return farray;
 145 }
 146
 147 GArray*
 148 g_array_prepend_vals (GArray        *farray,
 149                       gconstpointer  data,
 150                       guint          len)
 151 {
 152   GRealArray *array = (GRealArray*) farray;
 153
 154   g_array_maybe_expand (array, len);
 155
 156   g_memmove (g_array_elt_pos (array, len), g_array_elt_pos (array, 0),
 157              g_array_elt_len (array, array->len));
 158
 159   memcpy (g_array_elt_pos (array, 0), data, g_array_elt_len (array, len));
 160
 161   array->len += len;
 162
 163   g_array_zero_terminate (array);
 164
 165   return farray;
 166 }
 167
 168 GArray*
 169 g_array_insert_vals (GArray        *farray,
 170                      guint          index,
 171                      gconstpointer  data,
 172                      guint          len)
 173 {
 174   GRealArray *array = (GRealArray*) farray;
 175
 176   g_array_maybe_expand (array, len);
 177
 178   g_memmove (g_array_elt_pos (array, len + index),
 179              g_array_elt_pos (array, index),
 180              g_array_elt_len (array, array->len - index));
 181
 182   memcpy (g_array_elt_pos (array, index), data, g_array_elt_len (array, len));
 183
 184   array->len += len;
 185
 186   g_array_zero_terminate (array);
 187
 188   return farray;
 189 }
 190
 191 GArray*
 192 g_array_set_size (GArray *farray,
 193                   guint   length)
 194 {
 195   GRealArray *array = (GRealArray*) farray;
 196   if (length > array->len)
 197     {
 198       g_array_maybe_expand (array, length - array->len);
 199
 200       if (array->clear)
 201         g_array_elt_zero (array, array->len, length - array->len);
 202     }
 203 #ifdef ENABLE_GC_FRIENDLY
 204   else if (length < array->len)
 205     g_array_elt_zero (array, length, array->len - length);
 206 #endif /* ENABLE_GC_FRIENDLY */
 207
 208   array->len = length;
 209
 210   g_array_zero_terminate (array);
 211
 212   return farray;
 213 }
 214
 215 GArray*
 216 g_array_remove_index (GArray* farray,
 217                       guint index)
 218 {
 219   GRealArray* array = (GRealArray*) farray;
 220
 221   g_return_val_if_fail (array, NULL);
 222
 223   g_return_val_if_fail (index < array->len, NULL);
 224
 225   if (index != array->len - 1)
 226     g_memmove (g_array_elt_pos (array, index),
 227                g_array_elt_pos (array, index + 1),
 228                g_array_elt_len (array, array->len - index - 1));
 229
 230   array->len -= 1;
 231
 232 #ifdef ENABLE_GC_FRIENDLY
 233   g_array_elt_zero (array, array->len, 1);
 234 #else /* !ENABLE_GC_FRIENDLY */
 235   g_array_zero_terminate (array);
 236 #endif /* ENABLE_GC_FRIENDLY */
 237
 238   return farray;
 239 }
 240
 241 GArray*
 242 g_array_remove_index_fast (GArray* farray,
 243                            guint   index)
 244 {
 245   GRealArray* array = (GRealArray*) farray;
 246
 247   g_return_val_if_fail (array, NULL);
 248
 249   g_return_val_if_fail (index < array->len, NULL);
 250
 251   if (index != array->len - 1)
 252     g_memmove (g_array_elt_pos (array, index),
 253                g_array_elt_pos (array, array->len - 1),
 254                g_array_elt_len (array, 1));
 255
 256   array->len -= 1;
 257
 258 #ifdef ENABLE_GC_FRIENDLY
 259   g_array_elt_zero (array, array->len, 1);
 260 #else /* !ENABLE_GC_FRIENDLY */
 261   g_array_zero_terminate (array);
 262 #endif /* ENABLE_GC_FRIENDLY */
 263
 264   return farray;
 265 }
 266
 267 static gint
 268 g_nearest_pow (gint num)
 269 {
 270   gint n = 1;
 271
 272   while (n < num)
 273     n <<= 1;
 274
 275   return n;
 276 }
 277
 278 static void
 279 g_array_maybe_expand (GRealArray *array,
 280                       gint        len)
 281 {
 282   guint want_alloc = g_array_elt_len (array, array->len + len +
 283                                       array->zero_terminated);
 284
 285   if (want_alloc > array->alloc)
 286     {
 287       want_alloc = g_nearest_pow (want_alloc);
 288       want_alloc = MAX (want_alloc, MIN_ARRAY_SIZE);
 289
 290       array->data = g_realloc (array->data, want_alloc);
 291
 292 #ifdef ENABLE_GC_FRIENDLY
 293       memset (array->data + array->alloc, 0, want_alloc - array->alloc);
 294 #endif /* ENABLE_GC_FRIENDLY */
 295
 296       array->alloc = want_alloc;
 297     }
 298 }
 299
 300 /* Pointer Array
 301  */
 302
 303 typedef struct _GRealPtrArray  GRealPtrArray;
 304
 305 struct _GRealPtrArray
 306 {
 307   gpointer *pdata;
 308   guint     len;
 309   guint     alloc;
 310 };
 311
 312 static void g_ptr_array_maybe_expand (GRealPtrArray *array,
 313                                       gint           len);
 314
 315 static GMemChunk *ptr_array_mem_chunk = NULL;
 316 G_LOCK_DEFINE_STATIC (ptr_array_mem_chunk);
 317
 318
 319 GPtrArray*
 320 g_ptr_array_new (void)
 321 {
 322   return g_ptr_array_sized_new (0);
 323 }
 324
 325 GPtrArray*
 326 g_ptr_array_sized_new (guint reserved_size)
 327 {
 328   GRealPtrArray *array;
 329
 330   G_LOCK (ptr_array_mem_chunk);
 331   if (!ptr_array_mem_chunk)
 332     ptr_array_mem_chunk = g_mem_chunk_new ("array mem chunk",
 333                                            sizeof (GRealPtrArray),
 334                                            1024, G_ALLOC_AND_FREE);
 335
 336   array = g_chunk_new (GRealPtrArray, ptr_array_mem_chunk);
 337   G_UNLOCK (ptr_array_mem_chunk);
 338
 339   array->pdata = NULL;
 340   array->len = 0;
 341   array->alloc = 0;
 342
 343   if (reserved_size != 0)
 344     g_ptr_array_maybe_expand (array, reserved_size);
 345
 346   return (GPtrArray*) array;
 347 }
 348
 349 gpointer*
 350 g_ptr_array_free (GPtrArray   *array,
 351                   gboolean  free_segment)
 352 {
 353   gpointer* segment;
 354
 355   g_return_val_if_fail (array, NULL);
 356
 357   if (free_segment)
 358     {
 359       g_free (array->pdata);
 360       segment = NULL;
 361     }
 362   else
 363     segment = array->pdata;
 364
 365   G_LOCK (ptr_array_mem_chunk);
 366   g_mem_chunk_free (ptr_array_mem_chunk, array);
 367   G_UNLOCK (ptr_array_mem_chunk);
 368
 369   return segment;
 370 }
 371
 372 static void
 373 g_ptr_array_maybe_expand (GRealPtrArray *array,
 374                           gint        len)
 375 {
 376   if ((array->len + len) > array->alloc)
 377     {
 378 #ifdef ENABLE_GC_FRIENDLY
 379       guint old_alloc = array->alloc;
 380 #endif /* ENABLE_GC_FRIENDLY */
 381       array->alloc = g_nearest_pow (array->len + len);
 382       array->alloc = MAX (array->alloc, MIN_ARRAY_SIZE);
 383       array->pdata = g_realloc (array->pdata, sizeof(gpointer) * array->alloc);
 384 #ifdef ENABLE_GC_FRIENDLY
 385       for ( ; old_alloc < array->alloc; old_alloc++)
 386         array->pdata [old_alloc] = NULL;
 387 #endif /* ENABLE_GC_FRIENDLY */
 388     }
 389 }
 390
 391 void
 392 g_ptr_array_set_size  (GPtrArray   *farray,
 393                        gint          length)
 394 {
 395   GRealPtrArray* array = (GRealPtrArray*) farray;
 396
 397   g_return_if_fail (array);
 398
 399   if (length > array->len)
 400     {
 401       int i;
 402       g_ptr_array_maybe_expand (array, (length - array->len));
 403       /* This is not
 404        *     memset (array->pdata + array->len, 0,
 405        *            sizeof (gpointer) * (length - array->len));
 406        * to make it really portable. Remember (void*)NULL needn't be
 407        * bitwise zero. It of course is silly not to use memset (..,0,..).
 408        */
 409       for (i = array->len; i < length; i++)
 410         array->pdata[i] = NULL;
 411     }
 412 #ifdef ENABLE_GC_FRIENDLY
 413   else if (length < array->len)
 414     {
 415       int i;
 416       for (i = length; i < array->len; i++)
 417         array->pdata[i] = NULL;
 418     }
 419 #endif /* ENABLE_GC_FRIENDLY */
 420
 421   array->len = length;
 422 }
 423
 424 gpointer
 425 g_ptr_array_remove_index (GPtrArray* farray,
 426                           guint      index)
 427 {
 428   GRealPtrArray* array = (GRealPtrArray*) farray;
 429   gpointer result;
 430
 431   g_return_val_if_fail (array, NULL);
 432
 433   g_return_val_if_fail (index < array->len, NULL);
 434
 435   result = array->pdata[index];
 436
 437   if (index != array->len - 1)
 438     g_memmove (array->pdata + index, array->pdata + index + 1,
 439                sizeof (gpointer) * (array->len - index - 1));
 440
 441   array->len -= 1;
 442
 443 #ifdef ENABLE_GC_FRIENDLY
 444   array->pdata[array->len] = NULL;
 445 #endif /* ENABLE_GC_FRIENDLY */
 446
 447   return result;
 448 }
 449
 450 gpointer
 451 g_ptr_array_remove_index_fast (GPtrArray* farray,
 452                                guint      index)
 453 {
 454   GRealPtrArray* array = (GRealPtrArray*) farray;
 455   gpointer result;
 456
 457   g_return_val_if_fail (array, NULL);
 458
 459   g_return_val_if_fail (index < array->len, NULL);
 460
 461   result = array->pdata[index];
 462
 463   if (index != array->len - 1)
 464     array->pdata[index] = array->pdata[array->len - 1];
 465
 466   array->len -= 1;
 467
 468 #ifdef ENABLE_GC_FRIENDLY
 469   array->pdata[array->len] = NULL;
 470 #endif /* ENABLE_GC_FRIENDLY */
 471
 472   return result;
 473 }
 474
 475 gboolean
 476 g_ptr_array_remove (GPtrArray* farray,
 477                     gpointer data)
 478 {
 479   GRealPtrArray* array = (GRealPtrArray*) farray;
 480   int i;
 481
 482   g_return_val_if_fail (array, FALSE);
 483
 484   for (i = 0; i < array->len; i += 1)
 485     {
 486       if (array->pdata[i] == data)
 487         {
 488           g_ptr_array_remove_index (farray, i);
 489           return TRUE;
 490         }
 491     }
 492
 493   return FALSE;
 494 }
 495
 496 gboolean
 497 g_ptr_array_remove_fast (GPtrArray* farray,
 498                          gpointer data)
 499 {
 500   GRealPtrArray* array = (GRealPtrArray*) farray;
 501   int i;
 502
 503   g_return_val_if_fail (array, FALSE);
 504
 505   for (i = 0; i < array->len; i += 1)
 506     {
 507       if (array->pdata[i] == data)
 508         {
 509           g_ptr_array_remove_index_fast (farray, i);
 510           return TRUE;
 511         }
 512     }
 513
 514   return FALSE;
 515 }
 516
 517 void
 518 g_ptr_array_add (GPtrArray* farray,
 519                  gpointer data)
 520 {
 521   GRealPtrArray* array = (GRealPtrArray*) farray;
 522
 523   g_return_if_fail (array);
 524
 525   g_ptr_array_maybe_expand (array, 1);
 526
 527   array->pdata[array->len++] = data;
 528 }
 529
 530 /* Byte arrays
 531  */
 532
 533 GByteArray* g_byte_array_new      (void)
 534 {
 535   return (GByteArray*) g_array_sized_new (FALSE, FALSE, 1, 0);
 536 }
 537
 538 GByteArray* g_byte_array_sized_new (guint reserved_size)
 539 {
 540   return (GByteArray*) g_array_sized_new (FALSE, FALSE, 1, reserved_size);
 541 }
 542
 543 guint8*     g_byte_array_free     (GByteArray *array,
 544                                    gboolean    free_segment)
 545 {
 546   return (guint8*) g_array_free ((GArray*) array, free_segment);
 547 }
 548
 549 GByteArray* g_byte_array_append   (GByteArray *array,
 550                                    const guint8 *data,
 551                                    guint       len)
 552 {
 553   g_array_append_vals ((GArray*) array, (guint8*)data, len);
 554
 555   return array;
 556 }
 557
 558 GByteArray* g_byte_array_prepend  (GByteArray *array,
 559                                    const guint8 *data,
 560                                    guint       len)
 561 {
 562   g_array_prepend_vals ((GArray*) array, (guint8*)data, len);
 563
 564   return array;
 565 }
 566
 567 GByteArray* g_byte_array_set_size (GByteArray *array,
 568                                    guint       length)
 569 {
 570   g_array_set_size ((GArray*) array, length);
 571
 572   return array;
 573 }
 574
 575 GByteArray* g_byte_array_remove_index (GByteArray *array,
 576                                        guint index)
 577 {
 578   g_array_remove_index((GArray*) array, index);
 579
 580   return array;
 581 }
 582
 583 GByteArray* g_byte_array_remove_index_fast (GByteArray *array,
 584                                                    guint index)
 585 {
 586   g_array_remove_index_fast((GArray*) array, index);
 587
 588   return array;
 589 }