LCOV - code coverage report
Current view: top level - src/backend/nodes - list.c (source / functions) Hit Total Coverage
Test: PostgreSQL 12beta2 Lines: 314 366 85.8 %
Date: 2019-06-18 07:06:57 Functions: 46 54 85.2 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * list.c
       4             :  *    implementation for PostgreSQL generic linked list package
       5             :  *
       6             :  *
       7             :  * Portions Copyright (c) 1996-2019, 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    45616038 : new_list(NodeTag type)
      64             : {
      65             :     List       *new_list;
      66             :     ListCell   *new_head;
      67             : 
      68    45616038 :     new_head = (ListCell *) palloc(sizeof(*new_head));
      69    45616038 :     new_head->next = NULL;
      70             :     /* new_head->data is left undefined! */
      71             : 
      72    45616038 :     new_list = (List *) palloc(sizeof(*new_list));
      73    45616038 :     new_list->type = type;
      74    45616038 :     new_list->length = 1;
      75    45616038 :     new_list->head = new_head;
      76    45616038 :     new_list->tail = new_head;
      77             : 
      78    45616038 :     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     3639390 : new_head_cell(List *list)
      90             : {
      91             :     ListCell   *new_head;
      92             : 
      93     3639390 :     new_head = (ListCell *) palloc(sizeof(*new_head));
      94     3639390 :     new_head->next = list->head;
      95             : 
      96     3639390 :     list->head = new_head;
      97     3639390 :     list->length++;
      98     3639390 : }
      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    71954200 : new_tail_cell(List *list)
     109             : {
     110             :     ListCell   *new_tail;
     111             : 
     112    71954200 :     new_tail = (ListCell *) palloc(sizeof(*new_tail));
     113    71954200 :     new_tail->next = NULL;
     114             : 
     115    71954200 :     list->tail->next = new_tail;
     116    71954200 :     list->tail = new_tail;
     117    71954200 :     list->length++;
     118    71954200 : }
     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    96794170 : lappend(List *list, void *datum)
     129             : {
     130             :     Assert(IsPointerList(list));
     131             : 
     132    96794170 :     if (list == NIL)
     133    26422088 :         list = new_list(T_List);
     134             :     else
     135    70372082 :         new_tail_cell(list);
     136             : 
     137    96794170 :     lfirst(list->tail) = datum;
     138             :     check_list_invariants(list);
     139    96794170 :     return list;
     140             : }
     141             : 
     142             : /*
     143             :  * Append an integer to the specified list. See lappend()
     144             :  */
     145             : List *
     146     1222306 : lappend_int(List *list, int datum)
     147             : {
     148             :     Assert(IsIntegerList(list));
     149             : 
     150     1222306 :     if (list == NIL)
     151      706784 :         list = new_list(T_IntList);
     152             :     else
     153      515522 :         new_tail_cell(list);
     154             : 
     155     1222306 :     lfirst_int(list->tail) = datum;
     156             :     check_list_invariants(list);
     157     1222306 :     return list;
     158             : }
     159             : 
     160             : /*
     161             :  * Append an OID to the specified list. See lappend()
     162             :  */
     163             : List *
     164     3037506 : lappend_oid(List *list, Oid datum)
     165             : {
     166             :     Assert(IsOidList(list));
     167             : 
     168     3037506 :     if (list == NIL)
     169     1970910 :         list = new_list(T_OidList);
     170             :     else
     171     1066596 :         new_tail_cell(list);
     172             : 
     173     3037506 :     lfirst_oid(list->tail) = datum;
     174             :     check_list_invariants(list);
     175     3037506 :     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      242270 : add_new_cell(List *list, ListCell *prev_cell)
     186             : {
     187             :     ListCell   *new_cell;
     188             : 
     189      242270 :     new_cell = (ListCell *) palloc(sizeof(*new_cell));
     190             :     /* new_cell->data is left undefined! */
     191      242270 :     new_cell->next = prev_cell->next;
     192      242270 :     prev_cell->next = new_cell;
     193             : 
     194      242270 :     if (list->tail == prev_cell)
     195      213738 :         list->tail = new_cell;
     196             : 
     197      242270 :     list->length++;
     198             : 
     199      242270 :     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      178426 : lappend_cell(List *list, ListCell *prev, void *datum)
     210             : {
     211             :     ListCell   *new_cell;
     212             : 
     213             :     Assert(IsPointerList(list));
     214             : 
     215      178426 :     new_cell = add_new_cell(list, prev);
     216      178426 :     lfirst(new_cell) = datum;
     217             :     check_list_invariants(list);
     218      178426 :     return new_cell;
     219             : }
     220             : 
     221             : ListCell *
     222           0 : lappend_cell_int(List *list, ListCell *prev, int datum)
     223             : {
     224             :     ListCell   *new_cell;
     225             : 
     226             :     Assert(IsIntegerList(list));
     227             : 
     228           0 :     new_cell = add_new_cell(list, prev);
     229           0 :     lfirst_int(new_cell) = datum;
     230             :     check_list_invariants(list);
     231           0 :     return new_cell;
     232             : }
     233             : 
     234             : ListCell *
     235       63844 : lappend_cell_oid(List *list, ListCell *prev, Oid datum)
     236             : {
     237             :     ListCell   *new_cell;
     238             : 
     239             :     Assert(IsOidList(list));
     240             : 
     241       63844 :     new_cell = add_new_cell(list, prev);
     242       63844 :     lfirst_oid(new_cell) = datum;
     243             :     check_list_invariants(list);
     244       63844 :     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    16243568 : lcons(void *datum, List *list)
     260             : {
     261             :     Assert(IsPointerList(list));
     262             : 
     263    16243568 :     if (list == NIL)
     264    12628410 :         list = new_list(T_List);
     265             :     else
     266     3615158 :         new_head_cell(list);
     267             : 
     268    16243568 :     lfirst(list->head) = datum;
     269             :     check_list_invariants(list);
     270    16243568 :     return list;
     271             : }
     272             : 
     273             : /*
     274             :  * Prepend an integer to the list. See lcons()
     275             :  */
     276             : List *
     277      137130 : lcons_int(int datum, List *list)
     278             : {
     279             :     Assert(IsIntegerList(list));
     280             : 
     281      137130 :     if (list == NIL)
     282      133000 :         list = new_list(T_IntList);
     283             :     else
     284        4130 :         new_head_cell(list);
     285             : 
     286      137130 :     lfirst_int(list->head) = datum;
     287             :     check_list_invariants(list);
     288      137130 :     return list;
     289             : }
     290             : 
     291             : /*
     292             :  * Prepend an OID to the list. See lcons()
     293             :  */
     294             : List *
     295      166720 : lcons_oid(Oid datum, List *list)
     296             : {
     297             :     Assert(IsOidList(list));
     298             : 
     299      166720 :     if (list == NIL)
     300      146618 :         list = new_list(T_OidList);
     301             :     else
     302       20102 :         new_head_cell(list);
     303             : 
     304      166720 :     lfirst_oid(list->head) = datum;
     305             :     check_list_invariants(list);
     306      166720 :     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     4376026 : list_concat(List *list1, List *list2)
     322             : {
     323     4376026 :     if (list1 == NIL)
     324     2792096 :         return list2;
     325     1583930 :     if (list2 == NIL)
     326      935376 :         return list1;
     327      648554 :     if (list1 == list2)
     328           0 :         elog(ERROR, "cannot list_concat() a list to itself");
     329             : 
     330             :     Assert(list1->type == list2->type);
     331             : 
     332      648554 :     list1->length += list2->length;
     333      648554 :     list1->tail->next = list2->head;
     334      648554 :     list1->tail = list2->tail;
     335             : 
     336             :     check_list_invariants(list1);
     337      648554 :     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      273176 : list_truncate(List *list, int new_size)
     351             : {
     352             :     ListCell   *cell;
     353             :     int         n;
     354             : 
     355      273176 :     if (new_size <= 0)
     356       76138 :         return NIL;             /* truncate to zero length */
     357             : 
     358             :     /* If asked to effectively extend the list, do nothing */
     359      197038 :     if (new_size >= list_length(list))
     360      165254 :         return list;
     361             : 
     362       31784 :     n = 1;
     363       80650 :     foreach(cell, list)
     364             :     {
     365       80650 :         if (n == new_size)
     366             :         {
     367       31784 :             cell->next = NULL;
     368       31784 :             list->tail = cell;
     369       31784 :             list->length = new_size;
     370             :             check_list_invariants(list);
     371       31784 :             return list;
     372             :         }
     373       48866 :         n++;
     374             :     }
     375             : 
     376             :     /* keep the compiler quiet; never reached */
     377             :     Assert(false);
     378           0 :     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             : ListCell *
     386     7018038 : 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     7018038 :     if (n == list->length - 1)
     397     3093646 :         return list->tail;
     398             : 
     399     3924392 :     for (match = list->head; n-- > 0; match = match->next)
     400             :         ;
     401             : 
     402     3924392 :     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     6988374 : list_nth(const List *list, int n)
     411             : {
     412             :     Assert(IsPointerList(list));
     413     6988374 :     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        5608 : list_nth_int(const List *list, int n)
     422             : {
     423             :     Assert(IsIntegerList(list));
     424        5608 :     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        7704 : list_nth_oid(const List *list, int n)
     433             : {
     434             :     Assert(IsOidList(list));
     435        7704 :     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      124178 : 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      160582 :     foreach(cell, list)
     452             :     {
     453       91756 :         if (equal(lfirst(cell), datum))
     454       55352 :             return true;
     455             :     }
     456             : 
     457       68826 :     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      289924 : 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      419600 :     foreach(cell, list)
     473             :     {
     474      242874 :         if (lfirst(cell) == datum)
     475      113198 :             return true;
     476             :     }
     477             : 
     478      176726 :     return false;
     479             : }
     480             : 
     481             : /*
     482             :  * Return true iff the integer 'datum' is a member of the list.
     483             :  */
     484             : bool
     485       89986 : 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     4988452 :     foreach(cell, list)
     493             :     {
     494     4915438 :         if (lfirst_int(cell) == datum)
     495       16972 :             return true;
     496             :     }
     497             : 
     498       73014 :     return false;
     499             : }
     500             : 
     501             : /*
     502             :  * Return true iff the OID 'datum' is a member of the list.
     503             :  */
     504             : bool
     505    18889494 : 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    20309844 :     foreach(cell, list)
     513             :     {
     514     1908950 :         if (lfirst_oid(cell) == datum)
     515      488600 :             return true;
     516             :     }
     517             : 
     518    18400894 :     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     1753176 : 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     1753176 :     if (list->length == 1)
     539             :     {
     540      927504 :         list_free(list);
     541      927504 :         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      825672 :     list->length--;
     549             : 
     550      825672 :     if (prev)
     551       85326 :         prev->next = cell->next;
     552             :     else
     553      740346 :         list->head = cell->next;
     554             : 
     555      825672 :     if (list->tail == cell)
     556       71772 :         list->tail = prev;
     557             : 
     558      825672 :     pfree(cell);
     559      825672 :     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           8 : 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           8 :     prev = NULL;
     576           8 :     foreach(cell, list)
     577             :     {
     578           4 :         if (equal(lfirst(cell), datum))
     579           4 :             return list_delete_cell(list, cell, prev);
     580             : 
     581           0 :         prev = cell;
     582             :     }
     583             : 
     584             :     /* Didn't find a match: return the list unmodified */
     585           4 :     return list;
     586             : }
     587             : 
     588             : /* As above, but use simple pointer equality */
     589             : List *
     590     1002236 : 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     1002236 :     prev = NULL;
     599     1016098 :     foreach(cell, list)
     600             :     {
     601     1016098 :         if (lfirst(cell) == datum)
     602     1002236 :             return list_delete_cell(list, cell, prev);
     603             : 
     604       13862 :         prev = cell;
     605             :     }
     606             : 
     607             :     /* Didn't find a match: return the list unmodified */
     608           0 :     return list;
     609             : }
     610             : 
     611             : /* As above, but for integers */
     612             : List *
     613          36 : 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          36 :     prev = NULL;
     622          36 :     foreach(cell, list)
     623             :     {
     624          36 :         if (lfirst_int(cell) == datum)
     625          36 :             return list_delete_cell(list, cell, prev);
     626             : 
     627           0 :         prev = cell;
     628             :     }
     629             : 
     630             :     /* Didn't find a match: return the list unmodified */
     631           0 :     return list;
     632             : }
     633             : 
     634             : /* As above, but for OIDs */
     635             : List *
     636        6400 : 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        6400 :     prev = NULL;
     645        6400 :     foreach(cell, list)
     646             :     {
     647         766 :         if (lfirst_oid(cell) == datum)
     648         766 :             return list_delete_cell(list, cell, prev);
     649             : 
     650           0 :         prev = cell;
     651             :     }
     652             : 
     653             :     /* Didn't find a match: return the list unmodified */
     654        5634 :     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      424202 : list_delete_first(List *list)
     667             : {
     668             :     check_list_invariants(list);
     669             : 
     670      424202 :     if (list == NIL)
     671           0 :         return NIL;             /* would an error be better? */
     672             : 
     673      424202 :     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        5104 : 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        5104 :     result = list_copy(list1);
     706       10364 :     foreach(cell, list2)
     707             :     {
     708        5260 :         if (!list_member(result, lfirst(cell)))
     709        5214 :             result = lappend(result, lfirst(cell));
     710             :     }
     711             : 
     712             :     check_list_invariants(result);
     713        5104 :     return result;
     714             : }
     715             : 
     716             : /*
     717             :  * This variant of list_union() determines duplicates via simple
     718             :  * pointer comparison.
     719             :  */
     720             : List *
     721           0 : 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           0 :     result = list_copy(list1);
     730           0 :     foreach(cell, list2)
     731             :     {
     732           0 :         if (!list_member_ptr(result, lfirst(cell)))
     733           0 :             result = lappend(result, lfirst(cell));
     734             :     }
     735             : 
     736             :     check_list_invariants(result);
     737           0 :     return result;
     738             : }
     739             : 
     740             : /*
     741             :  * This variant of list_union() operates upon lists of integers.
     742             :  */
     743             : List *
     744        2636 : 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        2636 :     result = list_copy(list1);
     753        5292 :     foreach(cell, list2)
     754             :     {
     755        2656 :         if (!list_member_int(result, lfirst_int(cell)))
     756        2648 :             result = lappend_int(result, lfirst_int(cell));
     757             :     }
     758             : 
     759             :     check_list_invariants(result);
     760        2636 :     return result;
     761             : }
     762             : 
     763             : /*
     764             :  * This variant of list_union() operates upon lists of OIDs.
     765             :  */
     766             : List *
     767           0 : 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           0 :     result = list_copy(list1);
     776           0 :     foreach(cell, list2)
     777             :     {
     778           0 :         if (!list_member_oid(result, lfirst_oid(cell)))
     779           0 :             result = lappend_oid(result, lfirst_oid(cell));
     780             :     }
     781             : 
     782             :     check_list_invariants(result);
     783           0 :     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       36034 : list_intersection(const List *list1, const List *list2)
     801             : {
     802             :     List       *result;
     803             :     const ListCell *cell;
     804             : 
     805       36034 :     if (list1 == NIL || list2 == NIL)
     806       33572 :         return NIL;
     807             : 
     808             :     Assert(IsPointerList(list1));
     809             :     Assert(IsPointerList(list2));
     810             : 
     811        2462 :     result = NIL;
     812        5946 :     foreach(cell, list1)
     813             :     {
     814        3484 :         if (list_member(list2, lfirst(cell)))
     815         668 :             result = lappend(result, lfirst(cell));
     816             :     }
     817             : 
     818             :     check_list_invariants(result);
     819        2462 :     return result;
     820             : }
     821             : 
     822             : /*
     823             :  * As list_intersection but operates on lists of integers.
     824             :  */
     825             : List *
     826         188 : list_intersection_int(const List *list1, const List *list2)
     827             : {
     828             :     List       *result;
     829             :     const ListCell *cell;
     830             : 
     831         188 :     if (list1 == NIL || list2 == NIL)
     832           0 :         return NIL;
     833             : 
     834             :     Assert(IsIntegerList(list1));
     835             :     Assert(IsIntegerList(list2));
     836             : 
     837         188 :     result = NIL;
     838         408 :     foreach(cell, list1)
     839             :     {
     840         220 :         if (list_member_int(list2, lfirst_int(cell)))
     841         104 :             result = lappend_int(result, lfirst_int(cell));
     842             :     }
     843             : 
     844             :     check_list_invariants(result);
     845         188 :     return result;
     846             : }
     847             : 
     848             : /*
     849             :  * Return a list that contains all the cells in list1 that are not in
     850             :  * list2. The returned list is freshly allocated via palloc(), but the
     851             :  * cells themselves point to the same objects as the cells of the
     852             :  * input lists.
     853             :  *
     854             :  * This variant works on lists of pointers, and determines list
     855             :  * membership via equal()
     856             :  */
     857             : List *
     858       29778 : list_difference(const List *list1, const List *list2)
     859             : {
     860             :     const ListCell *cell;
     861       29778 :     List       *result = NIL;
     862             : 
     863             :     Assert(IsPointerList(list1));
     864             :     Assert(IsPointerList(list2));
     865             : 
     866       29778 :     if (list2 == NIL)
     867         714 :         return list_copy(list1);
     868             : 
     869       60564 :     foreach(cell, list1)
     870             :     {
     871       31500 :         if (!list_member(list2, lfirst(cell)))
     872         956 :             result = lappend(result, lfirst(cell));
     873             :     }
     874             : 
     875             :     check_list_invariants(result);
     876       29064 :     return result;
     877             : }
     878             : 
     879             : /*
     880             :  * This variant of list_difference() determines list membership via
     881             :  * simple pointer equality.
     882             :  */
     883             : List *
     884       19992 : list_difference_ptr(const List *list1, const List *list2)
     885             : {
     886             :     const ListCell *cell;
     887       19992 :     List       *result = NIL;
     888             : 
     889             :     Assert(IsPointerList(list1));
     890             :     Assert(IsPointerList(list2));
     891             : 
     892       19992 :     if (list2 == NIL)
     893       18440 :         return list_copy(list1);
     894             : 
     895        4498 :     foreach(cell, list1)
     896             :     {
     897        2946 :         if (!list_member_ptr(list2, lfirst(cell)))
     898        1078 :             result = lappend(result, lfirst(cell));
     899             :     }
     900             : 
     901             :     check_list_invariants(result);
     902        1552 :     return result;
     903             : }
     904             : 
     905             : /*
     906             :  * This variant of list_difference() operates upon lists of integers.
     907             :  */
     908             : List *
     909        1228 : list_difference_int(const List *list1, const List *list2)
     910             : {
     911             :     const ListCell *cell;
     912        1228 :     List       *result = NIL;
     913             : 
     914             :     Assert(IsIntegerList(list1));
     915             :     Assert(IsIntegerList(list2));
     916             : 
     917        1228 :     if (list2 == NIL)
     918         948 :         return list_copy(list1);
     919             : 
     920         812 :     foreach(cell, list1)
     921             :     {
     922         532 :         if (!list_member_int(list2, lfirst_int(cell)))
     923         228 :             result = lappend_int(result, lfirst_int(cell));
     924             :     }
     925             : 
     926             :     check_list_invariants(result);
     927         280 :     return result;
     928             : }
     929             : 
     930             : /*
     931             :  * This variant of list_difference() operates upon lists of OIDs.
     932             :  */
     933             : List *
     934           0 : list_difference_oid(const List *list1, const List *list2)
     935             : {
     936             :     const ListCell *cell;
     937           0 :     List       *result = NIL;
     938             : 
     939             :     Assert(IsOidList(list1));
     940             :     Assert(IsOidList(list2));
     941             : 
     942           0 :     if (list2 == NIL)
     943           0 :         return list_copy(list1);
     944             : 
     945           0 :     foreach(cell, list1)
     946             :     {
     947           0 :         if (!list_member_oid(list2, lfirst_oid(cell)))
     948           0 :             result = lappend_oid(result, lfirst_oid(cell));
     949             :     }
     950             : 
     951             :     check_list_invariants(result);
     952           0 :     return result;
     953             : }
     954             : 
     955             : /*
     956             :  * Append datum to list, but only if it isn't already in the list.
     957             :  *
     958             :  * Whether an element is already a member of the list is determined
     959             :  * via equal().
     960             :  */
     961             : List *
     962        2282 : list_append_unique(List *list, void *datum)
     963             : {
     964        2282 :     if (list_member(list, datum))
     965         340 :         return list;
     966             :     else
     967        1942 :         return lappend(list, datum);
     968             : }
     969             : 
     970             : /*
     971             :  * This variant of list_append_unique() determines list membership via
     972             :  * simple pointer equality.
     973             :  */
     974             : List *
     975      283932 : list_append_unique_ptr(List *list, void *datum)
     976             : {
     977      283932 :     if (list_member_ptr(list, datum))
     978      108716 :         return list;
     979             :     else
     980      175216 :         return lappend(list, datum);
     981             : }
     982             : 
     983             : /*
     984             :  * This variant of list_append_unique() operates upon lists of integers.
     985             :  */
     986             : List *
     987           0 : list_append_unique_int(List *list, int datum)
     988             : {
     989           0 :     if (list_member_int(list, datum))
     990           0 :         return list;
     991             :     else
     992           0 :         return lappend_int(list, datum);
     993             : }
     994             : 
     995             : /*
     996             :  * This variant of list_append_unique() operates upon lists of OIDs.
     997             :  */
     998             : List *
     999        3246 : list_append_unique_oid(List *list, Oid datum)
    1000             : {
    1001        3246 :     if (list_member_oid(list, datum))
    1002        1632 :         return list;
    1003             :     else
    1004        1614 :         return lappend_oid(list, datum);
    1005             : }
    1006             : 
    1007             : /*
    1008             :  * Append to list1 each member of list2 that isn't already in list1.
    1009             :  *
    1010             :  * Whether an element is already a member of the list is determined
    1011             :  * via equal().
    1012             :  *
    1013             :  * This is almost the same functionality as list_union(), but list1 is
    1014             :  * modified in-place rather than being copied. However, callers of this
    1015             :  * function may have strict ordering expectations -- i.e. that the relative
    1016             :  * order of those list2 elements that are not duplicates is preserved. Note
    1017             :  * also that list2's cells are not inserted in list1, so the analogy to
    1018             :  * list_concat() isn't perfect.
    1019             :  */
    1020             : List *
    1021        1300 : list_concat_unique(List *list1, List *list2)
    1022             : {
    1023             :     ListCell   *cell;
    1024             : 
    1025             :     Assert(IsPointerList(list1));
    1026             :     Assert(IsPointerList(list2));
    1027             : 
    1028        2496 :     foreach(cell, list2)
    1029             :     {
    1030        1196 :         if (!list_member(list1, lfirst(cell)))
    1031        1180 :             list1 = lappend(list1, lfirst(cell));
    1032             :     }
    1033             : 
    1034             :     check_list_invariants(list1);
    1035        1300 :     return list1;
    1036             : }
    1037             : 
    1038             : /*
    1039             :  * This variant of list_concat_unique() determines list membership via
    1040             :  * simple pointer equality.
    1041             :  */
    1042             : List *
    1043           0 : list_concat_unique_ptr(List *list1, List *list2)
    1044             : {
    1045             :     ListCell   *cell;
    1046             : 
    1047             :     Assert(IsPointerList(list1));
    1048             :     Assert(IsPointerList(list2));
    1049             : 
    1050           0 :     foreach(cell, list2)
    1051             :     {
    1052           0 :         if (!list_member_ptr(list1, lfirst(cell)))
    1053           0 :             list1 = lappend(list1, lfirst(cell));
    1054             :     }
    1055             : 
    1056             :     check_list_invariants(list1);
    1057           0 :     return list1;
    1058             : }
    1059             : 
    1060             : /*
    1061             :  * This variant of list_concat_unique() operates upon lists of integers.
    1062             :  */
    1063             : List *
    1064           0 : list_concat_unique_int(List *list1, List *list2)
    1065             : {
    1066             :     ListCell   *cell;
    1067             : 
    1068             :     Assert(IsIntegerList(list1));
    1069             :     Assert(IsIntegerList(list2));
    1070             : 
    1071           0 :     foreach(cell, list2)
    1072             :     {
    1073           0 :         if (!list_member_int(list1, lfirst_int(cell)))
    1074           0 :             list1 = lappend_int(list1, lfirst_int(cell));
    1075             :     }
    1076             : 
    1077             :     check_list_invariants(list1);
    1078           0 :     return list1;
    1079             : }
    1080             : 
    1081             : /*
    1082             :  * This variant of list_concat_unique() operates upon lists of OIDs.
    1083             :  */
    1084             : List *
    1085        2302 : list_concat_unique_oid(List *list1, List *list2)
    1086             : {
    1087             :     ListCell   *cell;
    1088             : 
    1089             :     Assert(IsOidList(list1));
    1090             :     Assert(IsOidList(list2));
    1091             : 
    1092        2302 :     foreach(cell, list2)
    1093             :     {
    1094           0 :         if (!list_member_oid(list1, lfirst_oid(cell)))
    1095           0 :             list1 = lappend_oid(list1, lfirst_oid(cell));
    1096             :     }
    1097             : 
    1098             :     check_list_invariants(list1);
    1099        2302 :     return list1;
    1100             : }
    1101             : 
    1102             : /*
    1103             :  * Free all storage in a list, and optionally the pointed-to elements
    1104             :  */
    1105             : static void
    1106    17304154 : list_free_private(List *list, bool deep)
    1107             : {
    1108             :     ListCell   *cell;
    1109             : 
    1110             :     check_list_invariants(list);
    1111             : 
    1112    17304154 :     cell = list_head(list);
    1113    40824454 :     while (cell != NULL)
    1114             :     {
    1115     6216146 :         ListCell   *tmp = cell;
    1116             : 
    1117     6216146 :         cell = lnext(cell);
    1118     6216146 :         if (deep)
    1119        5920 :             pfree(lfirst(tmp));
    1120     6216146 :         pfree(tmp);
    1121             :     }
    1122             : 
    1123    17304154 :     if (list)
    1124     3555020 :         pfree(list);
    1125    17304154 : }
    1126             : 
    1127             : /*
    1128             :  * Free all the cells of the list, as well as the list itself. Any
    1129             :  * objects that are pointed-to by the cells of the list are NOT
    1130             :  * free'd.
    1131             :  *
    1132             :  * On return, the argument to this function has been freed, so the
    1133             :  * caller would be wise to set it to NIL for safety's sake.
    1134             :  */
    1135             : void
    1136    16551070 : list_free(List *list)
    1137             : {
    1138    16551070 :     list_free_private(list, false);
    1139    16551070 : }
    1140             : 
    1141             : /*
    1142             :  * Free all the cells of the list, the list itself, and all the
    1143             :  * objects pointed-to by the cells of the list (each element in the
    1144             :  * list must contain a pointer to a palloc()'d region of memory!)
    1145             :  *
    1146             :  * On return, the argument to this function has been freed, so the
    1147             :  * caller would be wise to set it to NIL for safety's sake.
    1148             :  */
    1149             : void
    1150      753084 : list_free_deep(List *list)
    1151             : {
    1152             :     /*
    1153             :      * A "deep" free operation only makes sense on a list of pointers.
    1154             :      */
    1155             :     Assert(IsPointerList(list));
    1156      753084 :     list_free_private(list, true);
    1157      753084 : }
    1158             : 
    1159             : /*
    1160             :  * Return a shallow copy of the specified list.
    1161             :  */
    1162             : List *
    1163     4182580 : list_copy(const List *oldlist)
    1164             : {
    1165             :     List       *newlist;
    1166             :     ListCell   *newlist_prev;
    1167             :     ListCell   *oldlist_cur;
    1168             : 
    1169     4182580 :     if (oldlist == NIL)
    1170      761372 :         return NIL;
    1171             : 
    1172     3421208 :     newlist = new_list(oldlist->type);
    1173     3421208 :     newlist->length = oldlist->length;
    1174             : 
    1175             :     /*
    1176             :      * Copy over the data in the first cell; new_list() has already allocated
    1177             :      * the head cell itself
    1178             :      */
    1179     3421208 :     newlist->head->data = oldlist->head->data;
    1180             : 
    1181     3421208 :     newlist_prev = newlist->head;
    1182     3421208 :     oldlist_cur = oldlist->head->next;
    1183     9469932 :     while (oldlist_cur)
    1184             :     {
    1185             :         ListCell   *newlist_cur;
    1186             : 
    1187     2627516 :         newlist_cur = (ListCell *) palloc(sizeof(*newlist_cur));
    1188     2627516 :         newlist_cur->data = oldlist_cur->data;
    1189     2627516 :         newlist_prev->next = newlist_cur;
    1190             : 
    1191     2627516 :         newlist_prev = newlist_cur;
    1192     2627516 :         oldlist_cur = oldlist_cur->next;
    1193             :     }
    1194             : 
    1195     3421208 :     newlist_prev->next = NULL;
    1196     3421208 :     newlist->tail = newlist_prev;
    1197             : 
    1198             :     check_list_invariants(newlist);
    1199     3421208 :     return newlist;
    1200             : }
    1201             : 
    1202             : /*
    1203             :  * Return a shallow copy of the specified list, without the first N elements.
    1204             :  */
    1205             : List *
    1206      177256 : list_copy_tail(const List *oldlist, int nskip)
    1207             : {
    1208             :     List       *newlist;
    1209             :     ListCell   *newlist_prev;
    1210             :     ListCell   *oldlist_cur;
    1211             : 
    1212      177256 :     if (nskip < 0)
    1213           0 :         nskip = 0;              /* would it be better to elog? */
    1214             : 
    1215      177256 :     if (oldlist == NIL || nskip >= oldlist->length)
    1216          56 :         return NIL;
    1217             : 
    1218      177200 :     newlist = new_list(oldlist->type);
    1219      177200 :     newlist->length = oldlist->length - nskip;
    1220             : 
    1221             :     /*
    1222             :      * Skip over the unwanted elements.
    1223             :      */
    1224      177200 :     oldlist_cur = oldlist->head;
    1225      357198 :     while (nskip-- > 0)
    1226        2798 :         oldlist_cur = oldlist_cur->next;
    1227             : 
    1228             :     /*
    1229             :      * Copy over the data in the first remaining cell; new_list() has already
    1230             :      * allocated the head cell itself
    1231             :      */
    1232      177200 :     newlist->head->data = oldlist_cur->data;
    1233             : 
    1234      177200 :     newlist_prev = newlist->head;
    1235      177200 :     oldlist_cur = oldlist_cur->next;
    1236     4299662 :     while (oldlist_cur)
    1237             :     {
    1238             :         ListCell   *newlist_cur;
    1239             : 
    1240     3945262 :         newlist_cur = (ListCell *) palloc(sizeof(*newlist_cur));
    1241     3945262 :         newlist_cur->data = oldlist_cur->data;
    1242     3945262 :         newlist_prev->next = newlist_cur;
    1243             : 
    1244     3945262 :         newlist_prev = newlist_cur;
    1245     3945262 :         oldlist_cur = oldlist_cur->next;
    1246             :     }
    1247             : 
    1248      177200 :     newlist_prev->next = NULL;
    1249      177200 :     newlist->tail = newlist_prev;
    1250             : 
    1251             :     check_list_invariants(newlist);
    1252      177200 :     return newlist;
    1253             : }
    1254             : 
    1255             : /*
    1256             :  * Sort a list as though by qsort.
    1257             :  *
    1258             :  * A new list is built and returned.  Like list_copy, this doesn't make
    1259             :  * fresh copies of any pointed-to data.
    1260             :  *
    1261             :  * The comparator function receives arguments of type ListCell **.
    1262             :  */
    1263             : List *
    1264       19104 : list_qsort(const List *list, list_qsort_comparator cmp)
    1265             : {
    1266       19104 :     int         len = list_length(list);
    1267             :     ListCell  **list_arr;
    1268             :     List       *newlist;
    1269             :     ListCell   *newlist_prev;
    1270             :     ListCell   *cell;
    1271             :     int         i;
    1272             : 
    1273             :     /* Empty list is easy */
    1274       19104 :     if (len == 0)
    1275        9284 :         return NIL;
    1276             : 
    1277             :     /* Flatten list cells into an array, so we can use qsort */
    1278        9820 :     list_arr = (ListCell **) palloc(sizeof(ListCell *) * len);
    1279        9820 :     i = 0;
    1280       37842 :     foreach(cell, list)
    1281       28022 :         list_arr[i++] = cell;
    1282             : 
    1283        9820 :     qsort(list_arr, len, sizeof(ListCell *), cmp);
    1284             : 
    1285             :     /* Construct new list (this code is much like list_copy) */
    1286        9820 :     newlist = new_list(list->type);
    1287        9820 :     newlist->length = len;
    1288             : 
    1289             :     /*
    1290             :      * Copy over the data in the first cell; new_list() has already allocated
    1291             :      * the head cell itself
    1292             :      */
    1293        9820 :     newlist->head->data = list_arr[0]->data;
    1294             : 
    1295        9820 :     newlist_prev = newlist->head;
    1296       28022 :     for (i = 1; i < len; i++)
    1297             :     {
    1298             :         ListCell   *newlist_cur;
    1299             : 
    1300       18202 :         newlist_cur = (ListCell *) palloc(sizeof(*newlist_cur));
    1301       18202 :         newlist_cur->data = list_arr[i]->data;
    1302       18202 :         newlist_prev->next = newlist_cur;
    1303             : 
    1304       18202 :         newlist_prev = newlist_cur;
    1305             :     }
    1306             : 
    1307        9820 :     newlist_prev->next = NULL;
    1308        9820 :     newlist->tail = newlist_prev;
    1309             : 
    1310             :     /* Might as well free the workspace array */
    1311        9820 :     pfree(list_arr);
    1312             : 
    1313             :     check_list_invariants(newlist);
    1314        9820 :     return newlist;
    1315             : }
    1316             : 
    1317             : /*
    1318             :  * Temporary compatibility functions
    1319             :  *
    1320             :  * In order to avoid warnings for these function definitions, we need
    1321             :  * to include a prototype here as well as in pg_list.h. That's because
    1322             :  * we don't enable list API compatibility in list.c, so we
    1323             :  * don't see the prototypes for these functions.
    1324             :  */
    1325             : 
    1326             : /*
    1327             :  * Given a list, return its length. This is merely defined for the
    1328             :  * sake of backward compatibility: we can't afford to define a macro
    1329             :  * called "length", so it must be a function. New code should use the
    1330             :  * list_length() macro in order to avoid the overhead of a function
    1331             :  * call.
    1332             :  */
    1333             : int         length(const List *list);
    1334             : 
    1335             : int
    1336           0 : length(const List *list)
    1337             : {
    1338           0 :     return list_length(list);
    1339             : }

Generated by: LCOV version 1.13