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 "config.h" 32 33 #include <string.h> 34 #include <stdlib.h> 35 36 #include "garray.h" 37 38 #include "gmem.h" 39 #include "gthread.h" 40 #include "gmessages.h" 41 #include "gqsort.h" 42 43 #include "galias.h" 44 45 46 #define MIN_ARRAY_SIZE 16 47 48 typedef struct _GRealArray GRealArray; 49 50 struct _GRealArray 51 { 52 guint8 *data; 53 guint len; 54 guint alloc; 55 guint elt_size; 56 guint zero_terminated : 1; 57 guint clear : 1; 58 }; 59 60 #define g_array_elt_len(array,i) ((array)->elt_size * (i)) 61 #define g_array_elt_pos(array,i) ((array)->data + g_array_elt_len((array),(i))) 62 #define g_array_elt_zero(array, pos, len) \ 63 (memset (g_array_elt_pos ((array), pos), 0, g_array_elt_len ((array), len))) 64 #define g_array_zero_terminate(array) G_STMT_START{ \ 65 if ((array)->zero_terminated) \ 66 g_array_elt_zero ((array), (array)->len, 1); \ 67 }G_STMT_END 68 69 static gint g_nearest_pow (gint num) G_GNUC_CONST; 70 static void g_array_maybe_expand (GRealArray *array, 71 gint len); 72 73 GArray* 74 g_array_new (gboolean zero_terminated, 75 gboolean clear, 76 guint elt_size) 77 { 78 return (GArray*) g_array_sized_new (zero_terminated, clear, elt_size, 0); 79 } 80 81 GArray* g_array_sized_new (gboolean zero_terminated, 82 gboolean clear, 83 guint elt_size, 84 guint reserved_size) 85 { 86 GRealArray *array = g_slice_new (GRealArray); 87 88 array->data = NULL; 89 array->len = 0; 90 array->alloc = 0; 91 array->zero_terminated = (zero_terminated ? 1 : 0); 92 array->clear = (clear ? 1 : 0); 93 array->elt_size = elt_size; 94 95 if (array->zero_terminated || reserved_size != 0) 96 { 97 g_array_maybe_expand (array, reserved_size); 98 g_array_zero_terminate(array); 99 } 100 101 return (GArray*) array; 102 } 103 104 gchar* 105 g_array_free (GArray *array, 106 gboolean free_segment) 107 { 108 gchar* segment; 109 110 g_return_val_if_fail (array, NULL); 111 112 if (free_segment) 113 { 114 g_free (array->data); 115 segment = NULL; 116 } 117 else 118 segment = array->data; 119 120 g_slice_free1 (sizeof (GRealArray), array); 121 122 return segment; 123 } 124 125 GArray* 126 g_array_append_vals (GArray *farray, 127 gconstpointer data, 128 guint len) 129 { 130 GRealArray *array = (GRealArray*) farray; 131 132 g_array_maybe_expand (array, len); 133 134 memcpy (g_array_elt_pos (array, array->len), data, 135 g_array_elt_len (array, len)); 136 137 array->len += len; 138 139 g_array_zero_terminate (array); 140 141 return farray; 142 } 143 144 GArray* 145 g_array_prepend_vals (GArray *farray, 146 gconstpointer data, 147 guint len) 148 { 149 GRealArray *array = (GRealArray*) farray; 150 151 g_array_maybe_expand (array, len); 152 153 g_memmove (g_array_elt_pos (array, len), g_array_elt_pos (array, 0), 154 g_array_elt_len (array, array->len)); 155 156 memcpy (g_array_elt_pos (array, 0), data, g_array_elt_len (array, len)); 157 158 array->len += len; 159 160 g_array_zero_terminate (array); 161 162 return farray; 163 } 164 165 GArray* 166 g_array_insert_vals (GArray *farray, 167 guint index_, 168 gconstpointer data, 169 guint len) 170 { 171 GRealArray *array = (GRealArray*) farray; 172 173 g_array_maybe_expand (array, len); 174 175 g_memmove (g_array_elt_pos (array, len + index_), 176 g_array_elt_pos (array, index_), 177 g_array_elt_len (array, array->len - index_)); 178 179 memcpy (g_array_elt_pos (array, index_), data, g_array_elt_len (array, len)); 180 181 array->len += len; 182 183 g_array_zero_terminate (array); 184 185 return farray; 186 } 187 188 GArray* 189 g_array_set_size (GArray *farray, 190 guint length) 191 { 192 GRealArray *array = (GRealArray*) farray; 193 if (length > array->len) 194 { 195 g_array_maybe_expand (array, length - array->len); 196 197 if (array->clear) 198 g_array_elt_zero (array, array->len, length - array->len); 199 } 200 else if (G_UNLIKELY (g_mem_gc_friendly) && length < array->len) 201 g_array_elt_zero (array, length, array->len - length); 202 203 array->len = length; 204 205 g_array_zero_terminate (array); 206 207 return farray; 208 } 209 210 GArray* 211 g_array_remove_index (GArray *farray, 212 guint index_) 213 { 214 GRealArray* array = (GRealArray*) farray; 215 216 g_return_val_if_fail (array, NULL); 217 218 g_return_val_if_fail (index_ < array->len, NULL); 219 220 if (index_ != array->len - 1) 221 g_memmove (g_array_elt_pos (array, index_), 222 g_array_elt_pos (array, index_ + 1), 223 g_array_elt_len (array, array->len - index_ - 1)); 224 225 array->len -= 1; 226 227 if (G_UNLIKELY (g_mem_gc_friendly)) 228 g_array_elt_zero (array, array->len, 1); 229 else 230 g_array_zero_terminate (array); 231 232 return farray; 233 } 234 235 GArray* 236 g_array_remove_index_fast (GArray *farray, 237 guint index_) 238 { 239 GRealArray* array = (GRealArray*) farray; 240 241 g_return_val_if_fail (array, NULL); 242 243 g_return_val_if_fail (index_ < array->len, NULL); 244 245 if (index_ != array->len - 1) 246 memcpy (g_array_elt_pos (array, index_), 247 g_array_elt_pos (array, array->len - 1), 248 g_array_elt_len (array, 1)); 249 250 array->len -= 1; 251 252 if (G_UNLIKELY (g_mem_gc_friendly)) 253 g_array_elt_zero (array, array->len, 1); 254 else 255 g_array_zero_terminate (array); 256 257 return farray; 258 } 259 260 GArray* 261 g_array_remove_range (GArray *farray, 262 guint index_, 263 guint length) 264 { 265 GRealArray *array = (GRealArray*) farray; 266 267 g_return_val_if_fail (array, NULL); 268 g_return_val_if_fail (index_ < array->len, NULL); 269 g_return_val_if_fail (index_ + length <= array->len, NULL); 270 271 if (index_ + length != array->len) 272 g_memmove (g_array_elt_pos (array, index_), 273 g_array_elt_pos (array, index_ + length), 274 (array->len - (index_ + length)) * array->elt_size); 275 276 array->len -= length; 277 if (G_UNLIKELY (g_mem_gc_friendly)) 278 g_array_elt_zero (array, array->len, length); 279 else 280 g_array_zero_terminate (array); 281 282 return farray; 283 } 284 285 void 286 g_array_sort (GArray *farray, 287 GCompareFunc compare_func) 288 { 289 GRealArray *array = (GRealArray*) farray; 290 291 g_return_if_fail (array != NULL); 292 293 qsort (array->data, 294 array->len, 295 array->elt_size, 296 compare_func); 297 } 298 299 void 300 g_array_sort_with_data (GArray *farray, 301 GCompareDataFunc compare_func, 302 gpointer user_data) 303 { 304 GRealArray *array = (GRealArray*) farray; 305 306 g_return_if_fail (array != NULL); 307 308 g_qsort_with_data (array->data, 309 array->len, 310 array->elt_size, 311 compare_func, 312 user_data); 313 } 314 315 316 static gint 317 g_nearest_pow (gint num) 318 { 319 gint n = 1; 320 321 while (n < num) 322 n <<= 1; 323 324 return n; 325 } 326 327 static void 328 g_array_maybe_expand (GRealArray *array, 329 gint len) 330 { 331 guint want_alloc = g_array_elt_len (array, array->len + len + 332 array->zero_terminated); 333 334 if (want_alloc > array->alloc) 335 { 336 want_alloc = g_nearest_pow (want_alloc); 337 want_alloc = MAX (want_alloc, MIN_ARRAY_SIZE); 338 339 array->data = g_realloc (array->data, want_alloc); 340 341 if (G_UNLIKELY (g_mem_gc_friendly)) 342 memset (array->data + array->alloc, 0, want_alloc - array->alloc); 343 344 array->alloc = want_alloc; 345 } 346 } 347 348 /* Pointer Array 349 */ 350 351 typedef struct _GRealPtrArray GRealPtrArray; 352 353 struct _GRealPtrArray 354 { 355 gpointer *pdata; 356 guint len; 357 guint alloc; 358 }; 359 360 static void g_ptr_array_maybe_expand (GRealPtrArray *array, 361 gint len); 362 363 GPtrArray* 364 g_ptr_array_new (void) 365 { 366 return g_ptr_array_sized_new (0); 367 } 368 369 GPtrArray* 370 g_ptr_array_sized_new (guint reserved_size) 371 { 372 GRealPtrArray *array = g_slice_new (GRealPtrArray); 373 374 array->pdata = NULL; 375 array->len = 0; 376 array->alloc = 0; 377 378 if (reserved_size != 0) 379 g_ptr_array_maybe_expand (array, reserved_size); 380 381 return (GPtrArray*) array; 382 } 383 384 gpointer* 385 g_ptr_array_free (GPtrArray *array, 386 gboolean free_segment) 387 { 388 gpointer* segment; 389 390 g_return_val_if_fail (array, NULL); 391 392 if (free_segment) 393 { 394 g_free (array->pdata); 395 segment = NULL; 396 } 397 else 398 segment = array->pdata; 399 400 g_slice_free1 (sizeof (GRealPtrArray), array); 401 402 return segment; 403 } 404 405 static void 406 g_ptr_array_maybe_expand (GRealPtrArray *array, 407 gint len) 408 { 409 if ((array->len + len) > array->alloc) 410 { 411 guint old_alloc = array->alloc; 412 array->alloc = g_nearest_pow (array->len + len); 413 array->alloc = MAX (array->alloc, MIN_ARRAY_SIZE); 414 array->pdata = g_realloc (array->pdata, sizeof (gpointer) * array->alloc); 415 if (G_UNLIKELY (g_mem_gc_friendly)) 416 for ( ; old_alloc < array->alloc; old_alloc++) 417 array->pdata [old_alloc] = NULL; 418 } 419 } 420 421 void 422 g_ptr_array_set_size (GPtrArray *farray, 423 gint length) 424 { 425 GRealPtrArray* array = (GRealPtrArray*) farray; 426 427 g_return_if_fail (array); 428 429 if (length > array->len) 430 { 431 int i; 432 g_ptr_array_maybe_expand (array, (length - array->len)); 433 /* This is not 434 * memset (array->pdata + array->len, 0, 435 * sizeof (gpointer) * (length - array->len)); 436 * to make it really portable. Remember (void*)NULL needn't be 437 * bitwise zero. It of course is silly not to use memset (..,0,..). 438 */ 439 for (i = array->len; i < length; i++) 440 array->pdata[i] = NULL; 441 } 442 if (G_UNLIKELY (g_mem_gc_friendly) && length < array->len) 443 { 444 int i; 445 for (i = length; i < array->len; i++) 446 array->pdata[i] = NULL; 447 } 448 449 array->len = length; 450 } 451 452 gpointer 453 g_ptr_array_remove_index (GPtrArray *farray, 454 guint index_) 455 { 456 GRealPtrArray* array = (GRealPtrArray*) farray; 457 gpointer result; 458 459 g_return_val_if_fail (array, NULL); 460 461 g_return_val_if_fail (index_ < array->len, NULL); 462 463 result = array->pdata[index_]; 464 465 if (index_ != array->len - 1) 466 g_memmove (array->pdata + index_, array->pdata + index_ + 1, 467 sizeof (gpointer) * (array->len - index_ - 1)); 468 469 array->len -= 1; 470 471 if (G_UNLIKELY (g_mem_gc_friendly)) 472 array->pdata[array->len] = NULL; 473 474 return result; 475 } 476 477 gpointer 478 g_ptr_array_remove_index_fast (GPtrArray *farray, 479 guint index_) 480 { 481 GRealPtrArray* array = (GRealPtrArray*) farray; 482 gpointer result; 483 484 g_return_val_if_fail (array, NULL); 485 486 g_return_val_if_fail (index_ < array->len, NULL); 487 488 result = array->pdata[index_]; 489 490 if (index_ != array->len - 1) 491 array->pdata[index_] = array->pdata[array->len - 1]; 492 493 array->len -= 1; 494 495 if (G_UNLIKELY (g_mem_gc_friendly)) 496 array->pdata[array->len] = NULL; 497 498 return result; 499 } 500 501 void 502 g_ptr_array_remove_range (GPtrArray *farray, 503 guint index_, 504 guint length) 505 { 506 GRealPtrArray* array = (GRealPtrArray*) farray; 507 508 g_return_if_fail (array); 509 g_return_if_fail (index_ < array->len); 510 g_return_if_fail (index_ + length <= array->len); 511 512 if (index_ + length != array->len) 513 g_memmove (&array->pdata[index_], 514 &array->pdata[index_ + length], 515 (array->len - (index_ + length)) * sizeof (gpointer)); 516 517 array->len -= length; 518 if (G_UNLIKELY (g_mem_gc_friendly)) 519 { 520 guint i; 521 for (i = 0; i < length; i++) 522 array->pdata[array->len + i] = NULL; 523 } 524 } 525 526 gboolean 527 g_ptr_array_remove (GPtrArray *farray, 528 gpointer data) 529 { 530 GRealPtrArray* array = (GRealPtrArray*) farray; 531 guint i; 532 533 g_return_val_if_fail (array, FALSE); 534 535 for (i = 0; i < array->len; i += 1) 536 { 537 if (array->pdata[i] == data) 538 { 539 g_ptr_array_remove_index (farray, i); 540 return TRUE; 541 } 542 } 543 544 return FALSE; 545 } 546 547 gboolean 548 g_ptr_array_remove_fast (GPtrArray *farray, 549 gpointer data) 550 { 551 GRealPtrArray* array = (GRealPtrArray*) farray; 552 guint i; 553 554 g_return_val_if_fail (array, FALSE); 555 556 for (i = 0; i < array->len; i += 1) 557 { 558 if (array->pdata[i] == data) 559 { 560 g_ptr_array_remove_index_fast (farray, i); 561 return TRUE; 562 } 563 } 564 565 return FALSE; 566 } 567 568 void 569 g_ptr_array_add (GPtrArray *farray, 570 gpointer data) 571 { 572 GRealPtrArray* array = (GRealPtrArray*) farray; 573 574 g_return_if_fail (array); 575 576 g_ptr_array_maybe_expand (array, 1); 577 578 array->pdata[array->len++] = data; 579 } 580 581 void 582 g_ptr_array_sort (GPtrArray *array, 583 GCompareFunc compare_func) 584 { 585 g_return_if_fail (array != NULL); 586 587 qsort (array->pdata, 588 array->len, 589 sizeof (gpointer), 590 compare_func); 591 } 592 593 void 594 g_ptr_array_sort_with_data (GPtrArray *array, 595 GCompareDataFunc compare_func, 596 gpointer user_data) 597 { 598 g_return_if_fail (array != NULL); 599 600 g_qsort_with_data (array->pdata, 601 array->len, 602 sizeof (gpointer), 603 compare_func, 604 user_data); 605 } 606 607 /** 608 * g_ptr_array_foreach: 609 * @array: a #GPtrArray 610 * @func: the function to call for each array element 611 * @user_data: user data to pass to the function 612 * 613 * Calls a function for each element of a #GPtrArray. 614 * 615 * Since: 2.4 616 **/ 617 void 618 g_ptr_array_foreach (GPtrArray *array, 619 GFunc func, 620 gpointer user_data) 621 { 622 guint i; 623 624 g_return_if_fail (array); 625 626 for (i = 0; i < array->len; i++) 627 (*func) (array->pdata[i], user_data); 628 } 629 630 /* Byte arrays 631 */ 632 633 GByteArray* g_byte_array_new (void) 634 { 635 return (GByteArray*) g_array_sized_new (FALSE, FALSE, 1, 0); 636 } 637 638 GByteArray* g_byte_array_sized_new (guint reserved_size) 639 { 640 return (GByteArray*) g_array_sized_new (FALSE, FALSE, 1, reserved_size); 641 } 642 643 guint8* g_byte_array_free (GByteArray *array, 644 gboolean free_segment) 645 { 646 return (guint8*) g_array_free ((GArray*) array, free_segment); 647 } 648 649 GByteArray* g_byte_array_append (GByteArray *array, 650 const guint8 *data, 651 guint len) 652 { 653 g_array_append_vals ((GArray*) array, (guint8*)data, len); 654 655 return array; 656 } 657 658 GByteArray* g_byte_array_prepend (GByteArray *array, 659 const guint8 *data, 660 guint len) 661 { 662 g_array_prepend_vals ((GArray*) array, (guint8*)data, len); 663 664 return array; 665 } 666 667 GByteArray* g_byte_array_set_size (GByteArray *array, 668 guint length) 669 { 670 g_array_set_size ((GArray*) array, length); 671 672 return array; 673 } 674 675 GByteArray* g_byte_array_remove_index (GByteArray *array, 676 guint index_) 677 { 678 g_array_remove_index ((GArray*) array, index_); 679 680 return array; 681 } 682 683 GByteArray* g_byte_array_remove_index_fast (GByteArray *array, 684 guint index_) 685 { 686 g_array_remove_index_fast ((GArray*) array, index_); 687 688 return array; 689 } 690 691 GByteArray* 692 g_byte_array_remove_range (GByteArray *array, 693 guint index_, 694 guint length) 695 { 696 g_return_val_if_fail (array, NULL); 697 g_return_val_if_fail (index_ < array->len, NULL); 698 g_return_val_if_fail (index_ + length <= array->len, NULL); 699 700 return (GByteArray *)g_array_remove_range ((GArray*) array, index_, length); 701 } 702 703 void 704 g_byte_array_sort (GByteArray *array, 705 GCompareFunc compare_func) 706 { 707 g_array_sort ((GArray *) array, compare_func); 708 } 709 710 void 711 g_byte_array_sort_with_data (GByteArray *array, 712 GCompareDataFunc compare_func, 713 gpointer user_data) 714 { 715 g_array_sort_with_data ((GArray *) array, compare_func, user_data); 716 } 717 718 #define __G_ARRAY_C__ 719 #include "galiasdef.c" 720
