release/src/router/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
  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 < 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 < 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,
 316               sizeof (gpointer) * (array->alloc - old_alloc));
 317     }
 318 }
 319
 320 void
 321 g_ptr_array_set_size  (GPtrArray   *farray,
 322                        gint          length)
 323 {
 324   GRealPtrArray* array = (GRealPtrArray*) farray;
 325
 326   g_return_if_fail (array);
 327
 328   if (length > array->len)
 329     g_ptr_array_maybe_expand (array, (length - array->len));
 330
 331   array->len = length;
 332 }
 333
 334 gpointer
 335 g_ptr_array_remove_index (GPtrArray* farray,
 336                           guint index)
 337 {
 338   GRealPtrArray* array = (GRealPtrArray*) farray;
 339   gpointer result;
 340
 341   g_return_val_if_fail (array, NULL);
 342
 343   g_return_val_if_fail (index < array->len, NULL);
 344
 345   result = array->pdata[index];
 346
 347   if (index != array->len - 1)
 348     g_memmove (array->pdata + index, array->pdata + index + 1,
 349                sizeof (gpointer) * (array->len - index - 1));
 350
 351   array->pdata[array->len - 1] = NULL;
 352
 353   array->len -= 1;
 354
 355   return result;
 356 }
 357
 358 gpointer
 359 g_ptr_array_remove_index_fast (GPtrArray* farray,
 360                                guint index)
 361 {
 362   GRealPtrArray* array = (GRealPtrArray*) farray;
 363   gpointer result;
 364
 365   g_return_val_if_fail (array, NULL);
 366
 367   g_return_val_if_fail (index < array->len, NULL);
 368
 369   result = array->pdata[index];
 370
 371   if (index != array->len - 1)
 372     array->pdata[index] = array->pdata[array->len - 1];
 373
 374   array->pdata[array->len - 1] = NULL;
 375
 376   array->len -= 1;
 377
 378   return result;
 379 }
 380
 381 gboolean
 382 g_ptr_array_remove (GPtrArray* farray,
 383                     gpointer data)
 384 {
 385   GRealPtrArray* array = (GRealPtrArray*) farray;
 386   int i;
 387
 388   g_return_val_if_fail (array, FALSE);
 389
 390   for (i = 0; i < array->len; i += 1)
 391     {
 392       if (array->pdata[i] == data)
 393         {
 394           g_ptr_array_remove_index (farray, i);
 395           return TRUE;
 396         }
 397     }
 398
 399   return FALSE;
 400 }
 401
 402 gboolean
 403 g_ptr_array_remove_fast (GPtrArray* farray,
 404                          gpointer data)
 405 {
 406   GRealPtrArray* array = (GRealPtrArray*) farray;
 407   int i;
 408
 409   g_return_val_if_fail (array, FALSE);
 410
 411   for (i = 0; i < array->len; i += 1)
 412     {
 413       if (array->pdata[i] == data)
 414         {
 415           g_ptr_array_remove_index_fast (farray, i);
 416           return TRUE;
 417         }
 418     }
 419
 420   return FALSE;
 421 }
 422
 423 void
 424 g_ptr_array_add (GPtrArray* farray,
 425                  gpointer data)
 426 {
 427   GRealPtrArray* array = (GRealPtrArray*) farray;
 428
 429   g_return_if_fail (array);
 430
 431   g_ptr_array_maybe_expand (array, 1);
 432
 433   array->pdata[array->len++] = data;
 434 }
 435
 436 /* Byte arrays
 437  */
 438
 439 GByteArray* g_byte_array_new      (void)
 440 {
 441   return (GByteArray*) g_array_new (FALSE, FALSE, 1);
 442 }
 443
 444 void        g_byte_array_free     (GByteArray *array,
 445                                    gboolean    free_segment)
 446 {
 447   g_array_free ((GArray*) array, free_segment);
 448 }
 449
 450 GByteArray* g_byte_array_append   (GByteArray *array,
 451                                    const guint8 *data,
 452                                    guint       len)
 453 {
 454   g_array_append_vals ((GArray*) array, (guint8*)data, len);
 455
 456   return array;
 457 }
 458
 459 GByteArray* g_byte_array_prepend  (GByteArray *array,
 460                                    const guint8 *data,
 461                                    guint       len)
 462 {
 463   g_array_prepend_vals ((GArray*) array, (guint8*)data, len);
 464
 465   return array;
 466 }
 467
 468 GByteArray* g_byte_array_set_size (GByteArray *array,
 469                                    guint       length)
 470 {
 471   g_array_set_size ((GArray*) array, length);
 472
 473   return array;
 474 }
 475
 476 GByteArray* g_byte_array_remove_index (GByteArray *array,
 477                                        guint index)
 478 {
 479   g_array_remove_index((GArray*) array, index);
 480
 481   return array;
 482 }
 483
 484 GByteArray* g_byte_array_remove_index_fast (GByteArray *array,
 485                                                    guint index)
 486 {
 487   g_array_remove_index_fast((GArray*) array, index);
 488
 489   return array;
 490 }