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