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
  20 /*
  21  * Modified by the GLib Team and others 1997-1999.  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
 186   if (array->len < length)
 187     {
 188       g_array_maybe_expand (array, length - array->len);
 189
 190       if (array->clear)
 191         g_array_elt_zero (array, array->len, length - array->len);
 192     }
 193
 194   array->len = length;
 195
 196   g_array_zero_terminate (array);
 197
 198   return farray;
 199 }
 200
 201 GArray*
 202 g_array_remove_index (GArray* farray,
 203                       guint index)
 204 {
 205   GRealArray* array = (GRealArray*) farray;
 206
 207   g_return_val_if_fail (array, NULL);
 208
 209   g_return_val_if_fail (index >= 0 && index < array->len, NULL);
 210
 211   if (index != array->len - 1)
 212     g_memmove (g_array_elt_pos (array, index),
 213                g_array_elt_pos (array, index + 1),
 214                g_array_elt_len (array, array->len - index - 1));
 215
 216   array->len -= 1;
 217
 218   g_array_zero_terminate (array);
 219
 220   return farray;
 221 }
 222
 223 GArray*
 224 g_array_remove_index_fast (GArray* farray,
 225                            guint index)
 226 {
 227   GRealArray* array = (GRealArray*) farray;
 228
 229   g_return_val_if_fail (array, NULL);
 230
 231   g_return_val_if_fail (index >= 0 && index < array->len, NULL);
 232
 233   if (index != array->len - 1)
 234     g_memmove (g_array_elt_pos (array, index),
 235                g_array_elt_pos (array, array->len - 1),
 236                g_array_elt_len (array, 1));
 237
 238   array->len -= 1;
 239
 240   g_array_zero_terminate (array);
 241
 242   return farray;
 243 }
 244
 245 static gint
 246 g_nearest_pow (gint num)
 247 {
 248   gint n = 1;
 249
 250   while (n < num)
 251     n <<= 1;
 252
 253   return n;
 254 }
 255
 256 static void
 257 g_array_maybe_expand (GRealArray *array,
 258                       gint        len)
 259 {
 260   guint want_alloc = g_array_elt_len (array, array->len + len +
 261                                       array->zero_terminated);
 262
 263   if (want_alloc > array->alloc)
 264     {
 265       array->alloc = g_nearest_pow (want_alloc);
 266       array->alloc = MAX (array->alloc, MIN_ARRAY_SIZE);
 267
 268       array->data = g_realloc (array->data, array->alloc);
 269     }
 270 }
 271
 272 /* Pointer Array
 273  */
 274
 275 typedef struct _GRealPtrArray  GRealPtrArray;
 276
 277 struct _GRealPtrArray
 278 {
 279   gpointer *pdata;
 280   guint     len;
 281   guint     alloc;
 282 };
 283
 284 static void g_ptr_array_maybe_expand (GRealPtrArray *array,
 285                                       gint           len);
 286
 287 static GMemChunk *ptr_array_mem_chunk = NULL;
 288 G_LOCK_DEFINE_STATIC (ptr_array_mem_chunk);
 289
 290
 291 GPtrArray*
 292 g_ptr_array_new (void)
 293 {
 294   return g_ptr_array_sized_new (0);
 295 }
 296
 297 GPtrArray*
 298 g_ptr_array_sized_new (guint reserved_size)
 299 {
 300   GRealPtrArray *array;
 301
 302   G_LOCK (ptr_array_mem_chunk);
 303   if (!ptr_array_mem_chunk)
 304     ptr_array_mem_chunk = g_mem_chunk_new ("array mem chunk",
 305                                            sizeof (GRealPtrArray),
 306                                            1024, G_ALLOC_AND_FREE);
 307
 308   array = g_chunk_new (GRealPtrArray, ptr_array_mem_chunk);
 309   G_UNLOCK (ptr_array_mem_chunk);
 310
 311   array->pdata = NULL;
 312   array->len = 0;
 313   array->alloc = 0;
 314
 315   if (reserved_size != 0)
 316     g_ptr_array_maybe_expand (array, reserved_size);
 317
 318   return (GPtrArray*) array;
 319 }
 320
 321 void
 322 g_ptr_array_free (GPtrArray   *array,
 323                   gboolean  free_segment)
 324 {
 325   g_return_if_fail (array);
 326
 327   if (free_segment)
 328     g_free (array->pdata);
 329
 330   G_LOCK (ptr_array_mem_chunk);
 331   g_mem_chunk_free (ptr_array_mem_chunk, array);
 332   G_UNLOCK (ptr_array_mem_chunk);
 333 }
 334
 335 static void
 336 g_ptr_array_maybe_expand (GRealPtrArray *array,
 337                           gint        len)
 338 {
 339   if ((array->len + len) > array->alloc)
 340     {
 341       array->alloc = g_nearest_pow (array->len + len);
 342       array->alloc = MAX (array->alloc, MIN_ARRAY_SIZE);
 343       array->pdata = g_realloc (array->pdata, sizeof(gpointer) * array->alloc);
 344     }
 345 }
 346
 347 void
 348 g_ptr_array_set_size  (GPtrArray   *farray,
 349                        gint          length)
 350 {
 351   GRealPtrArray* array = (GRealPtrArray*) farray;
 352
 353   g_return_if_fail (array);
 354
 355   if (length > array->len)
 356     {
 357       int i;
 358       g_ptr_array_maybe_expand (array, (length - array->len));
 359       /* This is not
 360        *     memset (array->pdata + array->len, 0,
 361        *            sizeof (gpointer) * (length - array->len));
 362        * to make it really portable. Remember (void*)NULL needn't be
 363        * bitwise zero. It of course is silly not to use memset (..,0,..).
 364        */
 365       for (i = array->len; i < length; i++)
 366         array->pdata[i] = NULL;
 367     }
 368
 369   array->len = length;
 370 }
 371
 372 gpointer
 373 g_ptr_array_remove_index (GPtrArray* farray,
 374                           guint index)
 375 {
 376   GRealPtrArray* array = (GRealPtrArray*) farray;
 377   gpointer result;
 378
 379   g_return_val_if_fail (array, NULL);
 380
 381   g_return_val_if_fail (index >= 0 && index < array->len, NULL);
 382
 383   result = array->pdata[index];
 384
 385   if (index != array->len - 1)
 386     g_memmove (array->pdata + index, array->pdata + index + 1,
 387                sizeof (gpointer) * (array->len - index - 1));
 388
 389   array->len -= 1;
 390
 391   return result;
 392 }
 393
 394 gpointer
 395 g_ptr_array_remove_index_fast (GPtrArray* farray,
 396                                guint index)
 397 {
 398   GRealPtrArray* array = (GRealPtrArray*) farray;
 399   gpointer result;
 400
 401   g_return_val_if_fail (array, NULL);
 402
 403   g_return_val_if_fail (index >= 0 && index < array->len, NULL);
 404
 405   result = array->pdata[index];
 406
 407   if (index != array->len - 1)
 408     array->pdata[index] = array->pdata[array->len - 1];
 409
 410   array->len -= 1;
 411
 412   return result;
 413 }
 414
 415 gboolean
 416 g_ptr_array_remove (GPtrArray* farray,
 417                     gpointer data)
 418 {
 419   GRealPtrArray* array = (GRealPtrArray*) farray;
 420   int i;
 421
 422   g_return_val_if_fail (array, FALSE);
 423
 424   for (i = 0; i < array->len; i += 1)
 425     {
 426       if (array->pdata[i] == data)
 427         {
 428           g_ptr_array_remove_index (farray, i);
 429           return TRUE;
 430         }
 431     }
 432
 433   return FALSE;
 434 }
 435
 436 gboolean
 437 g_ptr_array_remove_fast (GPtrArray* farray,
 438                          gpointer data)
 439 {
 440   GRealPtrArray* array = (GRealPtrArray*) farray;
 441   int i;
 442
 443   g_return_val_if_fail (array, FALSE);
 444
 445   for (i = 0; i < array->len; i += 1)
 446     {
 447       if (array->pdata[i] == data)
 448         {
 449           g_ptr_array_remove_index_fast (farray, i);
 450           return TRUE;
 451         }
 452     }
 453
 454   return FALSE;
 455 }
 456
 457 void
 458 g_ptr_array_add (GPtrArray* farray,
 459                  gpointer data)
 460 {
 461   GRealPtrArray* array = (GRealPtrArray*) farray;
 462
 463   g_return_if_fail (array);
 464
 465   g_ptr_array_maybe_expand (array, 1);
 466
 467   array->pdata[array->len++] = data;
 468 }
 469
 470 /* Byte arrays
 471  */
 472
 473 GByteArray* g_byte_array_new      (void)
 474 {
 475   return (GByteArray*) g_array_sized_new (FALSE, FALSE, 1, 0);
 476 }
 477
 478 GByteArray* g_byte_array_sized_new (guint reserved_size)
 479 {
 480   return (GByteArray*) g_array_sized_new (FALSE, FALSE, 1, reserved_size);
 481 }
 482
 483 void        g_byte_array_free     (GByteArray *array,
 484                                    gboolean    free_segment)
 485 {
 486   g_array_free ((GArray*) array, free_segment);
 487 }
 488
 489 GByteArray* g_byte_array_append   (GByteArray *array,
 490                                    const guint8 *data,
 491                                    guint       len)
 492 {
 493   g_array_append_vals ((GArray*) array, (guint8*)data, len);
 494
 495   return array;
 496 }
 497
 498 GByteArray* g_byte_array_prepend  (GByteArray *array,
 499                                    const guint8 *data,
 500                                    guint       len)
 501 {
 502   g_array_prepend_vals ((GArray*) array, (guint8*)data, len);
 503
 504   return array;
 505 }
 506
 507 GByteArray* g_byte_array_set_size (GByteArray *array,
 508                                    guint       length)
 509 {
 510   g_array_set_size ((GArray*) array, length);
 511
 512   return array;
 513 }
 514
 515 GByteArray* g_byte_array_remove_index (GByteArray *array,
 516                                        guint index)
 517 {
 518   g_array_remove_index((GArray*) array, index);
 519
 520   return array;
 521 }
 522
 523 GByteArray* g_byte_array_remove_index_fast (GByteArray *array,
 524                                                    guint index)
 525 {
 526   g_array_remove_index_fast((GArray*) array, index);
 527
 528   return array;
 529 }