src/backend/nodes/list.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * list.c
   4  *        implementation for PostgreSQL generic linked list package
   5  *
   6  *
   7  * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  *
  11  * IDENTIFICATION
  12  *        $PostgreSQL: pgsql/src/backend/nodes/list.c,v 1.58 2004/05/30 23:40:27 neilc Exp $
  13  *
  14  *-------------------------------------------------------------------------
  15  */
  16 #include "postgres.h"
  17 #include "nodes/pg_list.h"
  18
  19 /*
  20  * Routines to simplify writing assertions about the type of a list; a
  21  * NIL list is considered to be an empty list of any type.
  22  */
  23 #define IsPointerList(l)                ((l) == NIL || IsA((l), List))
  24 #define IsIntegerList(l)                ((l) == NIL || IsA((l), IntList))
  25 #define IsOidList(l)                    ((l) == NIL || IsA((l), OidList))
  26
  27 #ifdef USE_ASSERT_CHECKING
  28 /*
  29  * Check that the specified List is valid (so far as we can tell).
  30  */
  31 static void
  32 check_list_invariants(List *list)
  33 {
  34         if (list == NIL)
  35                 return;
  36
  37         Assert(list->length > 0);
  38         Assert(list->head != NULL);
  39         Assert(list->tail != NULL);
  40
  41         Assert(list->type == T_List ||
  42                    list->type == T_IntList ||
  43                    list->type == T_OidList);
  44
  45         if (list->length == 1)
  46                 Assert(list->head == list->tail);
  47         if (list->length == 2)
  48                 Assert(list->head->next == list->tail);
  49         Assert(list->tail->next == NULL);
  50 }
  51 #else
  52 #define check_list_invariants(l)
  53 #endif /* USE_ASSERT_CHECKING */
  54
  55 /*
  56  * Return a freshly allocated List. Since empty non-NIL lists are
  57  * invalid, new_list() also allocates the head cell of the new list:
  58  * the caller should be sure to fill in that cell's data.
  59  */
  60 static List *
  61 new_list(NodeTag type)
  62 {
  63         List            *new_list;
  64         ListCell        *new_head;
  65
  66         new_head = (ListCell *) palloc(sizeof(*new_head));
  67         new_head->next = NULL;
  68         /* new_head->data is left undefined! */
  69
  70         new_list = (List *) palloc(sizeof(*new_list));
  71         new_list->type = type;
  72         new_list->length = 1;
  73         new_list->head = new_head;
  74         new_list->tail = new_head;
  75
  76         return new_list;
  77 }
  78
  79 /*
  80  * Allocate a new cell and make it the head of the specified
  81  * list. Assumes the list it is passed is non-NIL.
  82  *
  83  * The data in the new head cell is undefined; the caller should be
  84  * sure to fill it in
  85  */
  86 static void
  87 new_head_cell(List *list)
  88 {
  89         ListCell *new_head;
  90
  91         new_head = (ListCell *) palloc(sizeof(*new_head));
  92         new_head->next = list->head;
  93
  94         list->head = new_head;
  95         list->length++;
  96 }
  97
  98 /*
  99  * Allocate a new cell and make it the tail of the specified
 100  * list. Assumes the list it is passed is non-NIL.
 101  *
 102  * The data in the new tail cell is undefined; the caller should be
 103  * sure to fill it in
 104  */
 105 static void
 106 new_tail_cell(List *list)
 107 {
 108         ListCell *new_tail;
 109
 110         new_tail = (ListCell *) palloc(sizeof(*new_tail));
 111         new_tail->next = NULL;
 112
 113         list->tail->next = new_tail;
 114         list->tail = new_tail;
 115         list->length++;
 116 }
 117
 118 /*
 119  * Append a pointer to the list. A pointer to the modified list is
 120  * returned. Note that this function may or may not destructively
 121  * modify the list; callers should always use this function's return
 122  * value, rather than continuing to use the pointer passed as the
 123  * first argument.
 124  */
 125 List *
 126 lappend(List *list, void *datum)
 127 {
 128         Assert(IsPointerList(list));
 129
 130         if (list == NIL)
 131                 list = new_list(T_List);
 132         else
 133                 new_tail_cell(list);
 134
 135         lfirst(list->tail) = datum;
 136         check_list_invariants(list);
 137         return list;
 138 }
 139
 140 /*
 141  * Append an integer to the specified list. See lappend()
 142  */
 143 List *
 144 lappend_int(List *list, int datum)
 145 {
 146         Assert(IsIntegerList(list));
 147
 148         if (list == NIL)
 149                 list = new_list(T_IntList);
 150         else
 151                 new_tail_cell(list);
 152
 153         lfirst_int(list->tail) = datum;
 154         check_list_invariants(list);
 155         return list;
 156 }
 157
 158 /*
 159  * Append an OID to the specified list. See lappend()
 160  */
 161 List *
 162 lappend_oid(List *list, Oid datum)
 163 {
 164         Assert(IsOidList(list));
 165
 166         if (list == NIL)
 167                 list = new_list(T_OidList);
 168         else
 169                 new_tail_cell(list);
 170
 171         lfirst_oid(list->tail) = datum;
 172         check_list_invariants(list);
 173         return list;
 174 }
 175
 176 /*
 177  * Add a new cell to the list, in the position after 'prev_cell'. The
 178  * data in the cell is left undefined, and must be filled in by the
 179  * caller. 'list' is assumed to be non-NIL, and 'prev_cell' is assumed
 180  * to be non-NULL and a member of 'list'.
 181  */
 182 static ListCell *
 183 add_new_cell(List *list, ListCell *prev_cell)
 184 {
 185         ListCell *new_cell;
 186
 187         new_cell = (ListCell *) palloc(sizeof(*new_cell));
 188         /* new_cell->data is left undefined! */
 189         new_cell->next = prev_cell->next;
 190         prev_cell->next = new_cell;
 191
 192         if (list->tail == prev_cell)
 193                 list->tail = new_cell;
 194
 195         list->length++;
 196
 197         return new_cell;
 198 }
 199
 200 /*
 201  * Add a new cell to the specified list (which must be non-NIL);
 202  * it will be placed after the list cell 'prev' (which must be
 203  * non-NULL and a member of 'list'). The data placed in the new cell
 204  * is 'datum'. The newly-constructed cell is returned.
 205  */
 206 ListCell *
 207 lappend_cell(List *list, ListCell *prev, void *datum)
 208 {
 209         ListCell *new_cell;
 210
 211         Assert(IsPointerList(list));
 212
 213         new_cell = add_new_cell(list, prev);
 214         lfirst(new_cell) = datum;
 215         check_list_invariants(list);
 216         return new_cell;
 217 }
 218
 219 ListCell *
 220 lappend_cell_int(List *list, ListCell *prev, int datum)
 221 {
 222         ListCell *new_cell;
 223
 224         Assert(IsIntegerList(list));
 225
 226         new_cell = add_new_cell(list, prev);
 227         lfirst_int(new_cell) = datum;
 228         check_list_invariants(list);
 229         return new_cell;
 230 }
 231
 232 ListCell *
 233 lappend_cell_oid(List *list, ListCell *prev, Oid datum)
 234 {
 235         ListCell *new_cell;
 236
 237         Assert(IsOidList(list));
 238
 239         new_cell = add_new_cell(list, prev);
 240         lfirst_oid(new_cell) = datum;
 241         check_list_invariants(list);
 242         return new_cell;
 243 }
 244
 245 /*
 246  * Prepend a new element to the list. A pointer to the modified list
 247  * is returned. Note that this function may or may not destructively
 248  * modify the list; callers should always use this function's return
 249  * value, rather than continuing to use the pointer passed as the
 250  * second argument.
 251  *
 252  * Caution: before Postgres 7.5, the original List was unmodified and
 253  * could be considered to retain its separate identity.  This is no longer
 254  * the case.
 255  */
 256 List *
 257 lcons(void *datum, List *list)
 258 {
 259         Assert(IsPointerList(list));
 260
 261         if (list == NIL)
 262                 list = new_list(T_List);
 263         else
 264                 new_head_cell(list);
 265
 266         lfirst(list->head) = datum;
 267         check_list_invariants(list);
 268         return list;
 269 }
 270
 271 /*
 272  * Prepend an integer to the list. See lcons()
 273  */
 274 List *
 275 lcons_int(int datum, List *list)
 276 {
 277         Assert(IsIntegerList(list));
 278
 279         if (list == NIL)
 280                 list = new_list(T_IntList);
 281         else
 282                 new_head_cell(list);
 283
 284         lfirst_int(list->head) = datum;
 285         check_list_invariants(list);
 286         return list;
 287 }
 288
 289 /*
 290  * Prepend an OID to the list. See lcons()
 291  */
 292 List *
 293 lcons_oid(Oid datum, List *list)
 294 {
 295         Assert(IsOidList(list));
 296
 297         if (list == NIL)
 298                 list = new_list(T_OidList);
 299         else
 300                 new_head_cell(list);
 301
 302         lfirst_oid(list->head) = datum;
 303         check_list_invariants(list);
 304         return list;
 305 }
 306
 307 /*
 308  * Concatenate list2 to the end of list1, and return list1. list1 is
 309  * destructively changed. Callers should be sure to use the return
 310  * value as the new pointer to the concatenated list: the 'list1'
 311  * input pointer may or may not be the same as the returned pointer.
 312  *
 313  * The nodes in list2 are merely appended to the end of list1 in-place
 314  * (i.e. they aren't copied; the two lists will share some of the same
 315  * storage). Therefore, invoking list_free() on list2 will also
 316  * invalidate a portion of list1.
 317  */
 318 List *
 319 list_concat(List *list1, List *list2)
 320 {
 321         if (list1 == NIL)
 322                 return list2;
 323         if (list2 == NIL)
 324                 return list1;
 325         if (list1 == list2)
 326                 elog(ERROR, "cannot list_concat() a list to itself");
 327
 328         Assert(list1->type == list2->type);
 329
 330         list1->length += list2->length;
 331         list1->tail->next = list2->head;
 332         list1->tail = list2->tail;
 333
 334         check_list_invariants(list1);
 335         return list1;
 336 }
 337
 338 /*
 339  * Truncate 'list' to contain no more than 'new_size' elements. This
 340  * modifies the list in-place! Despite this, callers should use the
 341  * pointer returned by this function to refer to the newly truncated
 342  * list -- it may or may not be the same as the pointer that was
 343  * passed.
 344  *
 345  * Note that any cells removed by list_truncate() are NOT pfree'd.
 346  */
 347 List *
 348 list_truncate(List *list, int new_size)
 349 {
 350         ListCell        *cell;
 351         int                      n;
 352
 353         if (new_size <= 0)
 354                 return NIL;             /* truncate to zero length */
 355
 356         /* If asked to effectively extend the list, do nothing */
 357         if (new_size >= list_length(list))
 358                 return list;
 359
 360         n = 1;
 361         foreach (cell, list)
 362         {
 363                 if (n == new_size)
 364                 {
 365                         cell->next = NULL;
 366                         list->tail = cell;
 367                         list->length = new_size;
 368                         check_list_invariants(list);
 369                         return list;
 370                 }
 371                 n++;
 372         }
 373
 374         /* keep the compiler quiet; never reached */
 375         Assert(false);
 376         return list;
 377 }
 378
 379 /*
 380  * Locate the n'th cell (counting from 0) of the list.  It is an assertion
 381  * error if there isn't one.
 382  */
 383 static ListCell *
 384 list_nth_cell(List *list, int n)
 385 {
 386         ListCell *match;
 387
 388         Assert(list != NIL);
 389         Assert(n >= 0);
 390         Assert(n < list->length);
 391         check_list_invariants(list);
 392
 393         /* Does the caller actually mean to fetch the tail? */
 394         if (n == list->length - 1)
 395                 return list->tail;
 396
 397         for (match = list->head; n-- > 0; match = match->next)
 398                 ;
 399
 400         return match;
 401 }
 402
 403 /*
 404  * Return the data value contained in the n'th element of the
 405  * specified list. (List elements begin at 0.)
 406  */
 407 void *
 408 list_nth(List *list, int n)
 409 {
 410         Assert(IsPointerList(list));
 411         return lfirst(list_nth_cell(list, n));
 412 }
 413
 414 /*
 415  * Return the integer value contained in the n'th element of the
 416  * specified list.
 417  */
 418 int
 419 list_nth_int(List *list, int n)
 420 {
 421         Assert(IsIntegerList(list));
 422         return lfirst_int(list_nth_cell(list, n));
 423 }
 424
 425 /*
 426  * Return the OID value contained in the n'th element of the specified
 427  * list.
 428  */
 429 Oid
 430 list_nth_oid(List *list, int n)
 431 {
 432         Assert(IsOidList(list));
 433         return lfirst_oid(list_nth_cell(list, n));
 434 }
 435
 436 /*
 437  * Return true iff 'datum' is a member of the list. Equality is
 438  * determined via equal(), so callers should ensure that they pass a
 439  * Node as 'datum'.
 440  */
 441 bool
 442 list_member(List *list, void *datum)
 443 {
 444         ListCell *cell;
 445
 446         Assert(IsPointerList(list));
 447         check_list_invariants(list);
 448
 449         foreach (cell, list)
 450         {
 451                 if (equal(lfirst(cell), datum))
 452                         return true;
 453         }
 454
 455         return false;
 456 }
 457
 458 /*
 459  * Return true iff 'datum' is a member of the list. Equality is
 460  * determined by using simple pointer comparison.
 461  */
 462 bool
 463 list_member_ptr(List *list, void *datum)
 464 {
 465         ListCell *cell;
 466
 467         Assert(IsPointerList(list));
 468         check_list_invariants(list);
 469
 470         foreach (cell, list)
 471         {
 472                 if (lfirst(cell) == datum)
 473                         return true;
 474         }
 475
 476         return false;
 477 }
 478
 479 /*
 480  * Return true iff the integer 'datum' is a member of the list.
 481  */
 482 bool
 483 list_member_int(List *list, int datum)
 484 {
 485         ListCell *cell;
 486
 487         Assert(IsIntegerList(list));
 488         check_list_invariants(list);
 489
 490         foreach (cell, list)
 491         {
 492                 if (lfirst_int(cell) == datum)
 493                         return true;
 494         }
 495
 496         return false;
 497 }
 498
 499 /*
 500  * Return true iff the OID 'datum' is a member of the list.
 501  */
 502 bool
 503 list_member_oid(List *list, Oid datum)
 504 {
 505         ListCell *cell;
 506
 507         Assert(IsOidList(list));
 508         check_list_invariants(list);
 509
 510         foreach (cell, list)
 511         {
 512                 if (lfirst_oid(cell) == datum)
 513                         return true;
 514         }
 515
 516         return false;
 517 }
 518
 519 /*
 520  * Delete 'cell' from 'list'; 'prev' is the previous element to 'cell'
 521  * in 'list', if any (i.e. prev == NULL iff list->head == cell)
 522  *
 523  * The cell is pfree'd, as is the List header if this was the last member.
 524  */
 525 List *
 526 list_delete_cell(List *list, ListCell *cell, ListCell *prev)
 527 {
 528         check_list_invariants(list);
 529         Assert(prev != NULL ? lnext(prev) == cell : list_head(list) == cell);
 530
 531         /*
 532          * If we're about to delete the last node from the list, free the
 533          * whole list instead and return NIL, which is the only valid
 534          * representation of a zero-length list.
 535          */
 536         if (list->length == 1)
 537         {
 538                 list_free(list);
 539                 return NIL;
 540         }
 541
 542         /*
 543          * Otherwise, adjust the necessary list links, deallocate the
 544          * particular node we have just removed, and return the list we
 545          * were given.
 546          */
 547         list->length--;
 548
 549         if (prev)
 550                 prev->next = cell->next;
 551         else
 552                 list->head = cell->next;
 553
 554         if (list->tail == cell)
 555                 list->tail = prev;
 556
 557         pfree(cell);
 558         return list;
 559 }
 560
 561 /*
 562  * Delete the first cell in list that matches datum, if any.
 563  * Equality is determined via equal().
 564  */
 565 List *
 566 list_delete(List *list, void *datum)
 567 {
 568         ListCell        *cell;
 569         ListCell        *prev;
 570
 571         Assert(IsPointerList(list));
 572         check_list_invariants(list);
 573
 574         prev = NULL;
 575         foreach (cell, list)
 576         {
 577                 if (equal(lfirst(cell), datum))
 578                         return list_delete_cell(list, cell, prev);
 579
 580                 prev = cell;
 581         }
 582
 583         /* Didn't find a match: return the list unmodified */
 584         return list;
 585 }
 586
 587 /* As above, but use simple pointer equality */
 588 List *
 589 list_delete_ptr(List *list, void *datum)
 590 {
 591         ListCell        *cell;
 592         ListCell        *prev;
 593
 594         Assert(IsPointerList(list));
 595         check_list_invariants(list);
 596
 597         prev = NULL;
 598         foreach (cell, list)
 599         {
 600                 if (lfirst(cell) == datum)
 601                         return list_delete_cell(list, cell, prev);
 602
 603                 prev = cell;
 604         }
 605
 606         /* Didn't find a match: return the list unmodified */
 607         return list;
 608 }
 609
 610 /* As above, but for integers */
 611 List *
 612 list_delete_int(List *list, int datum)
 613 {
 614         ListCell        *cell;
 615         ListCell        *prev;
 616
 617         Assert(IsIntegerList(list));
 618         check_list_invariants(list);
 619
 620         prev = NULL;
 621         foreach (cell, list)
 622         {
 623                 if (lfirst_int(cell) == datum)
 624                         return list_delete_cell(list, cell, prev);
 625
 626                 prev = cell;
 627         }
 628
 629         /* Didn't find a match: return the list unmodified */
 630         return list;
 631 }
 632
 633 /* As above, but for OIDs */
 634 List *
 635 list_delete_oid(List *list, Oid datum)
 636 {
 637         ListCell        *cell;
 638         ListCell        *prev;
 639
 640         Assert(IsOidList(list));
 641         check_list_invariants(list);
 642
 643         prev = NULL;
 644         foreach (cell, list)
 645         {
 646                 if (lfirst_oid(cell) == datum)
 647                         return list_delete_cell(list, cell, prev);
 648
 649                 prev = cell;
 650         }
 651
 652         /* Didn't find a match: return the list unmodified */
 653         return list;
 654 }
 655
 656 /*
 657  * Delete the first element of the list.
 658  *
 659  * This is useful to replace the Lisp-y code "list = lnext(list);" in cases
 660  * where the intent is to alter the list rather than just traverse it.
 661  * Beware that the removed cell is freed, whereas the lnext() coding leaves
 662  * the original list head intact if there's another pointer to it.
 663  */
 664 List *
 665 list_delete_first(List *list)
 666 {
 667         check_list_invariants(list);
 668
 669         if (list == NIL)
 670                 return NIL;                             /* would an error be better? */
 671
 672         return list_delete_cell(list, list_head(list), NULL);
 673 }
 674
 675 /*
 676  * Generate the union of two lists. This is calculated by copying
 677  * list1 via list_copy(), then adding to it all the members of list2
 678  * that aren't already in list1.
 679  *
 680  * Whether an element is already a member of the list is determined
 681  * via equal().
 682  *
 683  * The returned list is newly-allocated, although the content of the
 684  * cells is the same (i.e. any pointed-to objects are not copied).
 685  *
 686  * NB: Bizarrely, this function will NOT remove any duplicates that
 687  * are present in list1 (so it is not really a union at all!). Also,
 688  * this function could probably be implemented a lot faster if it is a
 689  * performance bottleneck.
 690  */
 691 List *
 692 list_union(List *list1, List *list2)
 693 {
 694         List            *result;
 695         ListCell        *cell;
 696
 697         Assert(IsPointerList(list1));
 698         Assert(IsPointerList(list2));
 699
 700         result = list_copy(list1);
 701         foreach(cell, list2)
 702         {
 703                 if (!list_member(result, lfirst(cell)))
 704                         result = lappend(result, lfirst(cell));
 705         }
 706
 707         check_list_invariants(result);
 708         return result;
 709 }
 710
 711 /*
 712  * This variant of list_union() determines duplicates via simple
 713  * pointer comparison.
 714  */
 715 List *
 716 list_union_ptr(List *list1, List *list2)
 717 {
 718         List            *result;
 719         ListCell        *cell;
 720
 721         Assert(IsPointerList(list1));
 722         Assert(IsPointerList(list2));
 723
 724         result = list_copy(list1);
 725         foreach(cell, list2)
 726         {
 727                 if (!list_member_ptr(result, lfirst(cell)))
 728                         result = lappend(result, lfirst(cell));
 729         }
 730
 731         check_list_invariants(result);
 732         return result;
 733 }
 734
 735 /*
 736  * This variant of list_union() operates upon lists of integers.
 737  */
 738 List *
 739 list_union_int(List *list1, List *list2)
 740 {
 741         List            *result;
 742         ListCell        *cell;
 743
 744         Assert(IsIntegerList(list1));
 745         Assert(IsIntegerList(list2));
 746
 747         result = list_copy(list1);
 748         foreach(cell, list2)
 749         {
 750                 if (!list_member_int(result, lfirst_int(cell)))
 751                         result = lappend_int(result, lfirst_int(cell));
 752         }
 753
 754         check_list_invariants(result);
 755         return result;
 756 }
 757
 758 /*
 759  * This variant of list_union() operates upon lists of OIDs.
 760  */
 761 List *
 762 list_union_oid(List *list1, List *list2)
 763 {
 764         List            *result;
 765         ListCell        *cell;
 766
 767         Assert(IsOidList(list1));
 768         Assert(IsOidList(list2));
 769
 770         result = list_copy(list1);
 771         foreach(cell, list2)
 772         {
 773                 if (!list_member_oid(result, lfirst_oid(cell)))
 774                         result = lappend_oid(result, lfirst_oid(cell));
 775         }
 776
 777         check_list_invariants(result);
 778         return result;
 779 }
 780
 781 /*
 782  * Return a list that contains all the cells in list1 that are not in
 783  * list2. The returned list is freshly allocated via palloc(), but the
 784  * cells themselves point to the same objects as the cells of the
 785  * input lists.
 786  *
 787  * This variant works on lists of pointers, and determines list
 788  * membership via equal()
 789  */
 790 List *
 791 list_difference(List *list1, List *list2)
 792 {
 793         ListCell        *cell;
 794         List            *result = NIL;
 795
 796         Assert(IsPointerList(list1));
 797         Assert(IsPointerList(list2));
 798
 799         if (list2 == NIL)
 800                 return list_copy(list1);
 801
 802         foreach (cell, list1)
 803         {
 804                 if (!list_member(list2, lfirst(cell)))
 805                         result = lappend(result, lfirst(cell));
 806         }
 807
 808         check_list_invariants(result);
 809         return result;
 810 }
 811
 812 /*
 813  * This variant of list_difference() determines list membership via
 814  * simple pointer equality.
 815  */
 816 List *
 817 list_difference_ptr(List *list1, List *list2)
 818 {
 819         ListCell        *cell;
 820         List            *result = NIL;
 821
 822         Assert(IsPointerList(list1));
 823         Assert(IsPointerList(list2));
 824
 825         if (list2 == NIL)
 826                 return list_copy(list1);
 827
 828         foreach (cell, list1)
 829         {
 830                 if (!list_member_ptr(list2, lfirst(cell)))
 831                         result = lappend(result, lfirst(cell));
 832         }
 833
 834         check_list_invariants(result);
 835         return result;
 836 }
 837
 838 /*
 839  * This variant of list_difference() operates upon lists of integers.
 840  */
 841 List *
 842 list_difference_int(List *list1, List *list2)
 843 {
 844         ListCell        *cell;
 845         List            *result = NIL;
 846
 847         Assert(IsIntegerList(list1));
 848         Assert(IsIntegerList(list2));
 849
 850         if (list2 == NIL)
 851                 return list_copy(list1);
 852
 853         foreach (cell, list1)
 854         {
 855                 if (!list_member_int(list2, lfirst_int(cell)))
 856                         result = lappend_int(result, lfirst_int(cell));
 857         }
 858
 859         check_list_invariants(result);
 860         return result;
 861 }
 862
 863 /*
 864  * This variant of list_difference() operates upon lists of OIDs.
 865  */
 866 List *
 867 list_difference_oid(List *list1, List *list2)
 868 {
 869         ListCell        *cell;
 870         List            *result = NIL;
 871
 872         Assert(IsOidList(list1));
 873         Assert(IsOidList(list2));
 874
 875         if (list2 == NIL)
 876                 return list_copy(list1);
 877
 878         foreach (cell, list1)
 879         {
 880                 if (!list_member_oid(list2, lfirst_oid(cell)))
 881                         result = lappend_oid(result, lfirst_oid(cell));
 882         }
 883
 884         check_list_invariants(result);
 885         return result;
 886 }
 887
 888 /* Free all storage in a list, and optionally the pointed-to elements */
 889 static void
 890 list_free_private(List *list, bool deep)
 891 {
 892         ListCell        *cell;
 893
 894         check_list_invariants(list);
 895
 896         cell = list_head(list);
 897         while (cell != NULL)
 898         {
 899                 ListCell *tmp = cell;
 900
 901                 cell = lnext(cell);
 902                 if (deep)
 903                         pfree(lfirst(tmp));
 904                 pfree(tmp);
 905         }
 906
 907         if (list)
 908                 pfree(list);
 909 }
 910
 911 /*
 912  * Free all the cells of the list, as well as the list itself. Any
 913  * objects that are pointed-to by the cells of the list are NOT
 914  * free'd.
 915  *
 916  * On return, the argument to this function has been freed, so the
 917  * caller would be wise to set it to NIL for safety's sake.
 918  */
 919 void
 920 list_free(List *list)
 921 {
 922         list_free_private(list, false);
 923 }
 924
 925 /*
 926  * Free all the cells of the list, the list itself, and all the
 927  * objects pointed-to by the cells of the list (each element in the
 928  * list must contain a pointer to a palloc()'d region of memory!)
 929  *
 930  * On return, the argument to this function has been freed, so the
 931  * caller would be wise to set it to NIL for safety's sake.
 932  */
 933 void
 934 list_free_deep(List *list)
 935 {
 936         /*
 937          * A "deep" free operation only makes sense on a list of pointers.
 938          */
 939         Assert(IsPointerList(list));
 940         list_free_private(list, true);
 941 }
 942
 943 /*
 944  * Return a shallow copy of the specified list.
 945  */
 946 List *
 947 list_copy(List *oldlist)
 948 {
 949         List            *newlist;
 950         ListCell        *newlist_prev;
 951         ListCell        *oldlist_cur;
 952
 953         if (oldlist == NIL)
 954                 return NIL;
 955
 956         newlist = new_list(oldlist->type);
 957         newlist->length = oldlist->length;
 958
 959         /*
 960          * Copy over the data in the first cell; new_list() has already
 961          * allocated the head cell itself
 962          */
 963         newlist->head->data = oldlist->head->data;
 964
 965         newlist_prev = newlist->head;
 966         oldlist_cur = oldlist->head->next;
 967         while (oldlist_cur)
 968         {
 969                 ListCell *newlist_cur;
 970
 971                 newlist_cur = (ListCell *) palloc(sizeof(*newlist_cur));
 972                 newlist_cur->data = oldlist_cur->data;
 973                 newlist_prev->next = newlist_cur;
 974
 975                 newlist_prev = newlist_cur;
 976                 oldlist_cur = oldlist_cur->next;
 977         }
 978
 979         newlist_prev->next = NULL;
 980         newlist->tail = newlist_prev;
 981
 982         check_list_invariants(newlist);
 983         return newlist;
 984 }
 985
 986 /*
 987  * Return a shallow copy of the specified list, without the first N elements.
 988  */
 989 List *
 990 list_copy_tail(List *oldlist, int nskip)
 991 {
 992         List            *newlist;
 993         ListCell        *newlist_prev;
 994         ListCell        *oldlist_cur;
 995
 996         if (nskip < 0)
 997                 nskip = 0;                              /* would it be better to elog? */
 998
 999         if (oldlist == NIL || nskip >= oldlist->length)
1000                 return NIL;
1001
1002         newlist = new_list(oldlist->type);
1003         newlist->length = oldlist->length - nskip;
1004
1005         /*
1006          * Skip over the unwanted elements.
1007          */
1008         oldlist_cur = oldlist->head;
1009         while (nskip-- > 0)
1010                 oldlist_cur = oldlist_cur->next;
1011
1012         /*
1013          * Copy over the data in the first remaining cell; new_list() has already
1014          * allocated the head cell itself
1015          */
1016         newlist->head->data = oldlist_cur->data;
1017
1018         newlist_prev = newlist->head;
1019         oldlist_cur = oldlist_cur->next;
1020         while (oldlist_cur)
1021         {
1022                 ListCell *newlist_cur;
1023
1024                 newlist_cur = (ListCell *) palloc(sizeof(*newlist_cur));
1025                 newlist_cur->data = oldlist_cur->data;
1026                 newlist_prev->next = newlist_cur;
1027
1028                 newlist_prev = newlist_cur;
1029                 oldlist_cur = oldlist_cur->next;
1030         }
1031
1032         newlist_prev->next = NULL;
1033         newlist->tail = newlist_prev;
1034
1035         check_list_invariants(newlist);
1036         return newlist;
1037 }
1038
1039 /*
1040  * When using non-GCC compilers, we can't define these as inline
1041  * functions in pg_list.h, so they are defined here.
1042  *
1043  * TODO: investigate supporting inlining for some non-GCC compilers.
1044  */
1045 #ifndef __GNUC__
1046
1047 ListCell *
1048 list_head(List *l)
1049 {
1050         return l ? l->head : NULL;
1051 }
1052
1053 ListCell *
1054 list_tail(List *l)
1055 {
1056         return l ? l->tail : NULL;
1057 }
1058
1059 int
1060 list_length(List *l)
1061 {
1062         return l ? l->length : 0;
1063 }
1064
1065 #endif /* ! __GNUC__ */
1066
1067 /*
1068  * Temporary compatibility functions
1069  *
1070  * In order to avoid warnings for these function definitions, we need
1071  * to include a prototype here as well as in pg_list.h. That's because
1072  * we explicitly disable list API compatibility in list.c, so we
1073  * don't see the prototypes for these functions.
1074  */
1075
1076 /*
1077  * Given a list, return its length. This is merely defined for the
1078  * sake of backward compatibility: we can't afford to define a macro
1079  * called "length", so it must be a function. New code should use the
1080  * list_length() macro in order to avoid the overhead of a function
1081  * call.
1082  */
1083 int length(List *list);
1084
1085 int
1086 length(List *list)
1087 {
1088         return list_length(list);
1089 }
1090
1091 /*
1092  * This code implements the old "Fast List" API, making use of the new
1093  * List code to do so. There's no need for FastList anymore, so this
1094  * code is a bit sloppy -- it will be removed soon.
1095  */
1096 void FastListInit(FastList *fl);
1097
1098 void
1099 FastListInit(FastList *fl)
1100 {
1101         fl->list = NIL;
1102 }
1103
1104 void FastListFromList(FastList *fl, List *l);
1105
1106 void
1107 FastListFromList(FastList *fl, List *list)
1108 {
1109         fl->list = list;
1110 }
1111
1112 List *FastListValue(FastList *fl);
1113
1114 List *
1115 FastListValue(FastList *fl)
1116 {
1117         return fl->list;
1118 }
1119
1120 void makeFastList1(FastList *fl, void *elem);
1121
1122 void
1123 makeFastList1(FastList *fl, void *elem)
1124 {
1125         fl->list = list_make1(elem);
1126 }
1127
1128 void FastAppend(FastList *fl, void *datum);
1129
1130 void
1131 FastAppend(FastList *fl, void *datum)
1132 {
1133         fl->list = lappend(fl->list, datum);
1134 }
1135
1136 void FastAppendi(FastList *fl, int datum);
1137
1138 void
1139 FastAppendi(FastList *fl, int datum)
1140 {
1141         fl->list = lappend_int(fl->list, datum);
1142 }
1143
1144 void FastAppendo(FastList *fl, Oid datum);
1145
1146 void
1147 FastAppendo(FastList *fl, Oid datum)
1148 {
1149         fl->list = lappend_oid(fl->list, datum);
1150 }
1151
1152 void FastConc(FastList *fl, List *cells);
1153
1154 void
1155 FastConc(FastList *fl, List *cells)
1156 {
1157         fl->list = list_concat(fl->list, cells);
1158 }
1159
1160 void FastConcFast(FastList *fl1, FastList *fl2);
1161
1162 void
1163 FastConcFast(FastList *fl1, FastList *fl2)
1164 {
1165         fl1->list = list_concat(fl1->list, fl2->list);
1166 }