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