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