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