git.8kb.co.uk Git - pgpool-ii/pgpool-ii_2.2.5/blob - parser/list.c

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