garray.c 16 KB
Newer Older
Owen Taylor's avatar
Owen Taylor committed
1 2 3 4
/* GLIB - Library of useful routines for C programming
 * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
 *
 * This library is free software; you can redistribute it and/or
5
 * modify it under the terms of the GNU Lesser General Public
Owen Taylor's avatar
Owen Taylor committed
6 7 8 9 10 11
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12
 * Lesser General Public License for more details.
Owen Taylor's avatar
Owen Taylor committed
13
 *
14
 * You should have received a copy of the GNU Lesser General Public
Owen Taylor's avatar
Owen Taylor committed
15 16 17 18
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */
19

20
/*
21
 * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
22 23 24 25 26
 * file for a list of people on the GLib Team.  See the ChangeLog
 * files for a list of changes.  These files are distributed with
 * GLib at ftp://ftp.gtk.org/pub/gtk/. 
 */

27 28 29 30
/* 
 * MT safe
 */

31
#include "config.h"
32

Owen Taylor's avatar
Owen Taylor committed
33
#include <string.h>
34
#include <stdlib.h>
Owen Taylor's avatar
Owen Taylor committed
35 36 37 38 39 40 41 42 43 44 45 46
#include "glib.h"


#define MIN_ARRAY_SIZE  16

typedef struct _GRealArray  GRealArray;

struct _GRealArray
{
  guint8 *data;
  guint   len;
  guint   alloc;
47 48 49
  guint   elt_size;
  guint   zero_terminated : 1;
  guint   clear : 1;
Owen Taylor's avatar
Owen Taylor committed
50 51
};

52 53
#define g_array_elt_len(array,i) ((array)->elt_size * (i))
#define g_array_elt_pos(array,i) ((array)->data + g_array_elt_len((array),(i)))
54
#define g_array_elt_zero(array, pos, len) 				\
55
  (memset (g_array_elt_pos ((array), pos), 0,  g_array_elt_len ((array), len)))
56 57 58
#define g_array_zero_terminate(array) G_STMT_START{			\
  if ((array)->zero_terminated)						\
    g_array_elt_zero ((array), (array)->len, 1);			\
59
}G_STMT_END
Owen Taylor's avatar
Owen Taylor committed
60

Elliot Lee's avatar
Elliot Lee committed
61
static gint g_nearest_pow        (gint        num) G_GNUC_CONST;
Owen Taylor's avatar
Owen Taylor committed
62 63 64 65
static void g_array_maybe_expand (GRealArray *array,
				  gint        len);

static GMemChunk *array_mem_chunk = NULL;
66
G_LOCK_DEFINE_STATIC (array_mem_chunk);
Owen Taylor's avatar
Owen Taylor committed
67 68

GArray*
69 70 71
g_array_new (gboolean zero_terminated,
	     gboolean clear,
	     guint    elt_size)
72 73 74 75 76 77 78 79
{
  return (GArray*) g_array_sized_new (zero_terminated, clear, elt_size, 0);
}

GArray* g_array_sized_new (gboolean zero_terminated,
			   gboolean clear,
			   guint    elt_size,
			   guint    reserved_size)
Owen Taylor's avatar
Owen Taylor committed
80 81 82
{
  GRealArray *array;

83
  G_LOCK (array_mem_chunk);
Owen Taylor's avatar
Owen Taylor committed
84 85 86 87 88 89
  if (!array_mem_chunk)
    array_mem_chunk = g_mem_chunk_new ("array mem chunk",
				       sizeof (GRealArray),
				       1024, G_ALLOC_AND_FREE);

  array = g_chunk_new (GRealArray, array_mem_chunk);
90
  G_UNLOCK (array_mem_chunk);
Owen Taylor's avatar
Owen Taylor committed
91

92 93 94
  array->data            = NULL;
  array->len             = 0;
  array->alloc           = 0;
Owen Taylor's avatar
Owen Taylor committed
95
  array->zero_terminated = (zero_terminated ? 1 : 0);
96 97
  array->clear           = (clear ? 1 : 0);
  array->elt_size        = elt_size;
Owen Taylor's avatar
Owen Taylor committed
98

99
  if (array->zero_terminated || reserved_size != 0)
100
    {
101 102
      g_array_maybe_expand (array, reserved_size);
      g_array_zero_terminate(array);
103 104
    }

Owen Taylor's avatar
Owen Taylor committed
105 106 107
  return (GArray*) array;
}

108
gchar*
109 110
g_array_free (GArray  *array,
	      gboolean free_segment)
Owen Taylor's avatar
Owen Taylor committed
111
{
112 113 114 115
  gchar* segment;

  g_return_val_if_fail (array, NULL);

Owen Taylor's avatar
Owen Taylor committed
116
  if (free_segment)
117 118 119 120 121 122
    {
      g_free (array->data);
      segment = NULL;
    }
  else
    segment = array->data;
Owen Taylor's avatar
Owen Taylor committed
123

124
  G_LOCK (array_mem_chunk);
Owen Taylor's avatar
Owen Taylor committed
125
  g_mem_chunk_free (array_mem_chunk, array);
126
  G_UNLOCK (array_mem_chunk);
127 128

  return segment;
Owen Taylor's avatar
Owen Taylor committed
129 130 131
}

GArray*
Owen Taylor's avatar
Owen Taylor committed
132 133 134
g_array_append_vals (GArray       *farray,
		     gconstpointer data,
		     guint         len)
Owen Taylor's avatar
Owen Taylor committed
135
{
136
  GRealArray *array = (GRealArray*) farray;
Owen Taylor's avatar
Owen Taylor committed
137

138
  g_array_maybe_expand (array, len);
Owen Taylor's avatar
Owen Taylor committed
139

140 141
  memcpy (g_array_elt_pos (array, array->len), data, 
	  g_array_elt_len (array, len));
Owen Taylor's avatar
Owen Taylor committed
142

143 144
  array->len += len;

145 146
  g_array_zero_terminate (array);

147
  return farray;
Owen Taylor's avatar
Owen Taylor committed
148 149 150
}

GArray*
Owen Taylor's avatar
Owen Taylor committed
151 152 153
g_array_prepend_vals (GArray        *farray,
		      gconstpointer  data,
		      guint          len)
Owen Taylor's avatar
Owen Taylor committed
154
{
155
  GRealArray *array = (GRealArray*) farray;
Owen Taylor's avatar
Owen Taylor committed
156

157
  g_array_maybe_expand (array, len);
Owen Taylor's avatar
Owen Taylor committed
158

159 160
  g_memmove (g_array_elt_pos (array, len), g_array_elt_pos (array, 0), 
	     g_array_elt_len (array, array->len));
Owen Taylor's avatar
Owen Taylor committed
161

162
  memcpy (g_array_elt_pos (array, 0), data, g_array_elt_len (array, len));
163 164 165

  array->len += len;

166 167
  g_array_zero_terminate (array);

168
  return farray;
Owen Taylor's avatar
Owen Taylor committed
169 170
}

171 172 173 174 175 176 177 178 179 180
GArray*
g_array_insert_vals (GArray        *farray,
		     guint          index,
		     gconstpointer  data,
		     guint          len)
{
  GRealArray *array = (GRealArray*) farray;

  g_array_maybe_expand (array, len);

181 182 183
  g_memmove (g_array_elt_pos (array, len + index), 
	     g_array_elt_pos (array, index), 
	     g_array_elt_len (array, array->len - index));
184

185
  memcpy (g_array_elt_pos (array, index), data, g_array_elt_len (array, len));
186 187 188

  array->len += len;

189 190
  g_array_zero_terminate (array);

191 192 193
  return farray;
}

Owen Taylor's avatar
Owen Taylor committed
194
GArray*
195 196
g_array_set_size (GArray *farray,
		  guint   length)
Owen Taylor's avatar
Owen Taylor committed
197
{
198
  GRealArray *array = (GRealArray*) farray;
199
  if (length > array->len)
200 201 202 203 204 205
    {
      g_array_maybe_expand (array, length - array->len);
      
      if (array->clear)
	g_array_elt_zero (array, array->len, length - array->len);
    }
206 207 208 209
#ifdef ENABLE_GC_FRIENDLY  
  else if (length < array->len)
    g_array_elt_zero (array, length, array->len - length);
#endif /* ENABLE_GC_FRIENDLY */  
210
  
211
  array->len = length;
212 213 214
  
  g_array_zero_terminate (array);
  
215 216
  return farray;
}
Owen Taylor's avatar
Owen Taylor committed
217

218 219 220 221 222 223 224 225
GArray*
g_array_remove_index (GArray* farray,
		      guint index)
{
  GRealArray* array = (GRealArray*) farray;

  g_return_val_if_fail (array, NULL);

226
  g_return_val_if_fail (index < array->len, NULL);
227 228

  if (index != array->len - 1)
229 230 231
    g_memmove (g_array_elt_pos (array, index),
	       g_array_elt_pos (array, index + 1),
	       g_array_elt_len (array, array->len - index - 1));
232 233 234
  
  array->len -= 1;

235 236 237
#ifdef ENABLE_GC_FRIENDLY
  g_array_elt_zero (array, array->len, 1);
#else /* !ENABLE_GC_FRIENDLY */
238
  g_array_zero_terminate (array);
239
#endif /* ENABLE_GC_FRIENDLY */  
240

241 242 243 244 245
  return farray;
}

GArray*
g_array_remove_index_fast (GArray* farray,
246
			   guint   index)
247 248 249 250 251
{
  GRealArray* array = (GRealArray*) farray;

  g_return_val_if_fail (array, NULL);

252
  g_return_val_if_fail (index < array->len, NULL);
253 254

  if (index != array->len - 1)
255 256 257
    memcpy (g_array_elt_pos (array, index), 
	    g_array_elt_pos (array, array->len - 1),
	    g_array_elt_len (array, 1));
258 259 260
  
  array->len -= 1;

261 262 263
#ifdef ENABLE_GC_FRIENDLY
  g_array_elt_zero (array, array->len, 1);
#else /* !ENABLE_GC_FRIENDLY */
264
  g_array_zero_terminate (array);
265
#endif /* ENABLE_GC_FRIENDLY */  
266

267 268 269
  return farray;
}

270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295
GArray*
g_array_remove_range (GArray       *farray,
                      guint         index_,
                      guint         length)
{
  GRealArray *array = (GRealArray*) farray;

  g_return_val_if_fail (array, NULL);
  g_return_val_if_fail (index_ < array->len, NULL);
  g_return_val_if_fail (index_ + length <= array->len, NULL);

  if (index_ + length != array->len)
    g_memmove (g_array_elt_pos (array, index_), 
               g_array_elt_pos (array, index_ + length), 
               (array->len - (index_ + length)) * array->elt_size);

  array->len -= length;
#ifdef ENABLE_GC_FRIENDLY
  g_array_elt_zero (array, array->len, length);
#else /* !ENABLE_GC_FRIENDLY */
  g_array_zero_terminate (array);
#endif /* ENABLE_GC_FRIENDLY */

  return farray;
}

296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311
void
g_array_sort (GArray       *farray,
	      GCompareFunc  compare_func)
{
  GRealArray *array = (GRealArray*) farray;

  g_return_if_fail (array != NULL);

  qsort (array->data,
	 array->len,
	 array->elt_size,
	 compare_func);
}

void
g_array_sort_with_data (GArray           *farray,
312
			GCompareDataFunc  compare_func,
313 314 315 316 317 318 319 320 321 322 323 324 325 326
			gpointer          user_data)
{
  GRealArray *array = (GRealArray*) farray;

  g_return_if_fail (array != NULL);

  g_qsort_with_data (array->data,
		     array->len,
		     array->elt_size,
		     compare_func,
		     user_data);
}


Owen Taylor's avatar
Owen Taylor committed
327 328 329 330 331 332 333 334 335 336 337 338 339 340 341
static gint
g_nearest_pow (gint num)
{
  gint n = 1;

  while (n < num)
    n <<= 1;

  return n;
}

static void
g_array_maybe_expand (GRealArray *array,
		      gint        len)
{
342 343
  guint want_alloc = g_array_elt_len (array, array->len + len + 
				      array->zero_terminated);
Owen Taylor's avatar
Owen Taylor committed
344

345
  if (want_alloc > array->alloc)
Owen Taylor's avatar
Owen Taylor committed
346
    {
347 348
      want_alloc = g_nearest_pow (want_alloc);
      want_alloc = MAX (want_alloc, MIN_ARRAY_SIZE);
349

350 351 352 353 354 355 356
      array->data = g_realloc (array->data, want_alloc);

#ifdef ENABLE_GC_FRIENDLY
      memset (array->data + array->alloc, 0, want_alloc - array->alloc);
#endif /* ENABLE_GC_FRIENDLY */

      array->alloc = want_alloc;
Owen Taylor's avatar
Owen Taylor committed
357 358
    }
}
359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375

/* Pointer Array
 */

typedef struct _GRealPtrArray  GRealPtrArray;

struct _GRealPtrArray
{
  gpointer *pdata;
  guint     len;
  guint     alloc;
};

static void g_ptr_array_maybe_expand (GRealPtrArray *array,
				      gint           len);

static GMemChunk *ptr_array_mem_chunk = NULL;
376
G_LOCK_DEFINE_STATIC (ptr_array_mem_chunk);
377 378 379


GPtrArray*
380
g_ptr_array_new (void)
381 382 383 384 385 386
{
  return g_ptr_array_sized_new (0);
}

GPtrArray*  
g_ptr_array_sized_new (guint reserved_size)
387 388 389
{
  GRealPtrArray *array;

390
  G_LOCK (ptr_array_mem_chunk);
391 392 393 394 395 396
  if (!ptr_array_mem_chunk)
    ptr_array_mem_chunk = g_mem_chunk_new ("array mem chunk",
					   sizeof (GRealPtrArray),
					   1024, G_ALLOC_AND_FREE);

  array = g_chunk_new (GRealPtrArray, ptr_array_mem_chunk);
397
  G_UNLOCK (ptr_array_mem_chunk);
398 399 400 401 402

  array->pdata = NULL;
  array->len = 0;
  array->alloc = 0;

403 404 405 406
  if (reserved_size != 0)
    g_ptr_array_maybe_expand (array, reserved_size);

  return (GPtrArray*) array;  
407 408
}

409
gpointer*
410 411 412
g_ptr_array_free (GPtrArray   *array,
		  gboolean  free_segment)
{
413 414 415
  gpointer* segment;

  g_return_val_if_fail (array, NULL);
416 417

  if (free_segment)
418 419 420 421 422 423
    {
      g_free (array->pdata);
      segment = NULL;
    }
  else
    segment = array->pdata;
424

425
  G_LOCK (ptr_array_mem_chunk);
426
  g_mem_chunk_free (ptr_array_mem_chunk, array);
427
  G_UNLOCK (ptr_array_mem_chunk);
428 429

  return segment;
430 431 432 433 434 435 436 437
}

static void
g_ptr_array_maybe_expand (GRealPtrArray *array,
			  gint        len)
{
  if ((array->len + len) > array->alloc)
    {
438 439 440
#ifdef ENABLE_GC_FRIENDLY
      guint old_alloc = array->alloc;
#endif /* ENABLE_GC_FRIENDLY */
441 442
      array->alloc = g_nearest_pow (array->len + len);
      array->alloc = MAX (array->alloc, MIN_ARRAY_SIZE);
443
      array->pdata = g_realloc (array->pdata, sizeof (gpointer) * array->alloc);
444 445 446 447
#ifdef ENABLE_GC_FRIENDLY
      for ( ; old_alloc < array->alloc; old_alloc++)
	array->pdata [old_alloc] = NULL;
#endif /* ENABLE_GC_FRIENDLY */
448 449 450 451 452 453 454 455 456 457 458 459
    }
}

void
g_ptr_array_set_size  (GPtrArray   *farray,
		       gint	     length)
{
  GRealPtrArray* array = (GRealPtrArray*) farray;

  g_return_if_fail (array);

  if (length > array->len)
460 461 462 463 464 465 466 467 468 469 470 471
    {
      int i;
      g_ptr_array_maybe_expand (array, (length - array->len));
      /* This is not 
       *     memset (array->pdata + array->len, 0,
       *            sizeof (gpointer) * (length - array->len));
       * to make it really portable. Remember (void*)NULL needn't be
       * bitwise zero. It of course is silly not to use memset (..,0,..).
       */
      for (i = array->len; i < length; i++)
	array->pdata[i] = NULL;
    }
472 473 474 475 476 477 478 479
#ifdef ENABLE_GC_FRIENDLY  
  else if (length < array->len)
    {
      int i;
      for (i = length; i < array->len; i++)
	array->pdata[i] = NULL;
    }
#endif /* ENABLE_GC_FRIENDLY */  
480 481 482 483

  array->len = length;
}

484
gpointer
485
g_ptr_array_remove_index (GPtrArray* farray,
486
			  guint      index)
487 488
{
  GRealPtrArray* array = (GRealPtrArray*) farray;
489
  gpointer result;
490

491
  g_return_val_if_fail (array, NULL);
492

493
  g_return_val_if_fail (index < array->len, NULL);
494 495

  result = array->pdata[index];
496 497 498
  
  if (index != array->len - 1)
    g_memmove (array->pdata + index, array->pdata + index + 1, 
499
	       sizeof (gpointer) * (array->len - index - 1));
500 501 502
  
  array->len -= 1;

503 504 505 506
#ifdef ENABLE_GC_FRIENDLY  
  array->pdata[array->len] = NULL;
#endif /* ENABLE_GC_FRIENDLY */  

507 508 509 510 511
  return result;
}

gpointer
g_ptr_array_remove_index_fast (GPtrArray* farray,
512
			       guint      index)
513 514 515
{
  GRealPtrArray* array = (GRealPtrArray*) farray;
  gpointer result;
516

517 518
  g_return_val_if_fail (array, NULL);

519
  g_return_val_if_fail (index < array->len, NULL);
520 521 522 523 524

  result = array->pdata[index];
  
  if (index != array->len - 1)
    array->pdata[index] = array->pdata[array->len - 1];
525 526

  array->len -= 1;
527

528 529 530 531
#ifdef ENABLE_GC_FRIENDLY  
  array->pdata[array->len] = NULL;
#endif /* ENABLE_GC_FRIENDLY */  

532
  return result;
533 534
}

535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556
void
g_ptr_array_remove_range (GPtrArray* farray,
                          guint      index_,
                          guint      length)
{
  GRealPtrArray* array = (GRealPtrArray*) farray;

  g_return_if_fail (array);
  g_return_if_fail (index_ < array->len);
  g_return_if_fail (index_ + length <= array->len);

  if (index_ + length != array->len)
    g_memmove (&array->pdata[index_],
               &array->pdata[index_ + length], 
               (array->len - (index_ + length)) * sizeof (gpointer));

  array->len -= length;
#ifdef ENABLE_GC_FRIENDLY
  g_array_elt_zero (array->pdata, array->len, length);
#endif /* ENABLE_GC_FRIENDLY */
}

557 558 559 560 561
gboolean
g_ptr_array_remove (GPtrArray* farray,
		    gpointer data)
{
  GRealPtrArray* array = (GRealPtrArray*) farray;
562
  guint i;
563 564 565 566 567 568 569 570 571 572 573 574 575 576 577

  g_return_val_if_fail (array, FALSE);

  for (i = 0; i < array->len; i += 1)
    {
      if (array->pdata[i] == data)
	{
	  g_ptr_array_remove_index (farray, i);
	  return TRUE;
	}
    }

  return FALSE;
}

578 579 580 581 582
gboolean
g_ptr_array_remove_fast (GPtrArray* farray,
			 gpointer data)
{
  GRealPtrArray* array = (GRealPtrArray*) farray;
583
  guint i;
584 585 586 587 588 589 590 591 592 593 594 595 596 597 598

  g_return_val_if_fail (array, FALSE);

  for (i = 0; i < array->len; i += 1)
    {
      if (array->pdata[i] == data)
	{
	  g_ptr_array_remove_index_fast (farray, i);
	  return TRUE;
	}
    }

  return FALSE;
}

599 600 601 602 603 604 605 606 607 608 609 610 611
void
g_ptr_array_add (GPtrArray* farray,
		 gpointer data)
{
  GRealPtrArray* array = (GRealPtrArray*) farray;

  g_return_if_fail (array);

  g_ptr_array_maybe_expand (array, 1);

  array->pdata[array->len++] = data;
}

612 613 614 615 616 617 618 619 620 621 622 623 624 625
void
g_ptr_array_sort (GPtrArray    *array,
		  GCompareFunc  compare_func)
{
  g_return_if_fail (array != NULL);

  qsort (array->pdata,
	 array->len,
	 sizeof (gpointer),
	 compare_func);
}

void
g_ptr_array_sort_with_data (GPtrArray        *array,
626
			    GCompareDataFunc  compare_func,
627 628 629 630 631 632 633 634 635 636 637
			    gpointer          user_data)
{
  g_return_if_fail (array != NULL);

  g_qsort_with_data (array->pdata,
		     array->len,
		     sizeof (gpointer),
		     compare_func,
		     user_data);
}

638
/* Byte arrays 
639 640 641 642
 */

GByteArray* g_byte_array_new      (void)
{
643 644 645 646 647 648
  return (GByteArray*) g_array_sized_new (FALSE, FALSE, 1, 0);
}

GByteArray* g_byte_array_sized_new (guint reserved_size)
{
  return (GByteArray*) g_array_sized_new (FALSE, FALSE, 1, reserved_size);
649 650
}

651
guint8*	    g_byte_array_free     (GByteArray *array,
652
			           gboolean    free_segment)
653
{
654
  return (guint8*) g_array_free ((GArray*) array, free_segment);
655 656 657 658 659 660
}

GByteArray* g_byte_array_append   (GByteArray *array,
				   const guint8 *data,
				   guint       len)
{
661
  g_array_append_vals ((GArray*) array, (guint8*)data, len);
662 663 664 665 666 667 668 669

  return array;
}

GByteArray* g_byte_array_prepend  (GByteArray *array,
				   const guint8 *data,
				   guint       len)
{
670
  g_array_prepend_vals ((GArray*) array, (guint8*)data, len);
671 672 673 674

  return array;
}

675 676
GByteArray* g_byte_array_set_size (GByteArray *array,
				   guint       length)
677
{
678
  g_array_set_size ((GArray*) array, length);
679 680 681

  return array;
}
682 683 684 685 686 687 688 689 690 691

GByteArray* g_byte_array_remove_index (GByteArray *array,
				       guint index)
{
  g_array_remove_index((GArray*) array, index);

  return array;
}

GByteArray* g_byte_array_remove_index_fast (GByteArray *array,
692
					    guint index)
693 694 695 696 697
{
  g_array_remove_index_fast((GArray*) array, index);

  return array;
}
698

699 700 701 702 703 704 705 706 707 708 709 710
GByteArray*
g_byte_array_remove_range (GByteArray *array,
                           guint index_,
                           guint length)
{
  g_return_val_if_fail (array, FALSE);
  g_return_val_if_fail (index_ < array->len, FALSE);
  g_return_val_if_fail (index_ + length <= array->len, FALSE);

  return g_array_remove_range ((GArray*) array, index_, length);
}

711 712 713 714 715 716 717 718 719
void
g_byte_array_sort (GByteArray   *array,
		   GCompareFunc  compare_func)
{
  g_array_sort ((GArray *) array, compare_func);
}

void
g_byte_array_sort_with_data (GByteArray       *array,
720
			     GCompareDataFunc  compare_func,
721 722 723 724
			     gpointer          user_data)
{
  g_array_sort_with_data ((GArray *) array, compare_func, user_data);
}