LCOV - code coverage report
Current view: top level - src/backend/nodes - list.c (source / functions) Hit Total Coverage
Test: PostgreSQL 15devel Lines: 350 399 87.7 %
Date: 2021-12-09 04:09:06 Functions: 56 63 88.9 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * list.c
       4             :  *    implementation for PostgreSQL generic list package
       5             :  *
       6             :  * See comments in pg_list.h.
       7             :  *
       8             :  *
       9             :  * Portions Copyright (c) 1996-2021, PostgreSQL Global Development Group
      10             :  * Portions Copyright (c) 1994, Regents of the University of California
      11             :  *
      12             :  *
      13             :  * IDENTIFICATION
      14             :  *    src/backend/nodes/list.c
      15             :  *
      16             :  *-------------------------------------------------------------------------
      17             :  */
      18             : #include "postgres.h"
      19             : 
      20             : #include "nodes/pg_list.h"
      21             : #include "port/pg_bitutils.h"
      22             : #include "utils/memdebug.h"
      23             : #include "utils/memutils.h"
      24             : 
      25             : 
      26             : /*
      27             :  * The previous List implementation, since it used a separate palloc chunk
      28             :  * for each cons cell, had the property that adding or deleting list cells
      29             :  * did not move the storage of other existing cells in the list.  Quite a
      30             :  * bit of existing code depended on that, by retaining ListCell pointers
      31             :  * across such operations on a list.  There is no such guarantee in this
      32             :  * implementation, so instead we have debugging support that is meant to
      33             :  * help flush out now-broken assumptions.  Defining DEBUG_LIST_MEMORY_USAGE
      34             :  * while building this file causes the List operations to forcibly move
      35             :  * all cells in a list whenever a cell is added or deleted.  In combination
      36             :  * with MEMORY_CONTEXT_CHECKING and/or Valgrind, this can usually expose
      37             :  * broken code.  It's a bit expensive though, as there's many more palloc
      38             :  * cycles and a lot more data-copying than in a default build.
      39             :  *
      40             :  * By default, we enable this when building for Valgrind.
      41             :  */
      42             : #ifdef USE_VALGRIND
      43             : #define DEBUG_LIST_MEMORY_USAGE
      44             : #endif
      45             : 
      46             : /* Overhead for the fixed part of a List header, measured in ListCells */
      47             : #define LIST_HEADER_OVERHEAD  \
      48             :     ((int) ((offsetof(List, initial_elements) - 1) / sizeof(ListCell) + 1))
      49             : 
      50             : /*
      51             :  * Macros to simplify writing assertions about the type of a list; a
      52             :  * NIL list is considered to be an empty list of any type.
      53             :  */
      54             : #define IsPointerList(l)        ((l) == NIL || IsA((l), List))
      55             : #define IsIntegerList(l)        ((l) == NIL || IsA((l), IntList))
      56             : #define IsOidList(l)            ((l) == NIL || IsA((l), OidList))
      57             : 
      58             : #ifdef USE_ASSERT_CHECKING
      59             : /*
      60             :  * Check that the specified List is valid (so far as we can tell).
      61             :  */
      62             : static void
      63             : check_list_invariants(const List *list)
      64             : {
      65             :     if (list == NIL)
      66             :         return;
      67             : 
      68             :     Assert(list->length > 0);
      69             :     Assert(list->length <= list->max_length);
      70             :     Assert(list->elements != NULL);
      71             : 
      72             :     Assert(list->type == T_List ||
      73             :            list->type == T_IntList ||
      74             :            list->type == T_OidList);
      75             : }
      76             : #else
      77             : #define check_list_invariants(l)  ((void) 0)
      78             : #endif                          /* USE_ASSERT_CHECKING */
      79             : 
      80             : /*
      81             :  * Return a freshly allocated List with room for at least min_size cells.
      82             :  *
      83             :  * Since empty non-NIL lists are invalid, new_list() sets the initial length
      84             :  * to min_size, effectively marking that number of cells as valid; the caller
      85             :  * is responsible for filling in their data.
      86             :  */
      87             : static List *
      88    79999098 : new_list(NodeTag type, int min_size)
      89             : {
      90             :     List       *newlist;
      91             :     int         max_size;
      92             : 
      93             :     Assert(min_size > 0);
      94             : 
      95             :     /*
      96             :      * We allocate all the requested cells, and possibly some more, as part of
      97             :      * the same palloc request as the List header.  This is a big win for the
      98             :      * typical case of short fixed-length lists.  It can lose if we allocate a
      99             :      * moderately long list and then it gets extended; we'll be wasting more
     100             :      * initial_elements[] space than if we'd made the header small.  However,
     101             :      * rounding up the request as we do in the normal code path provides some
     102             :      * defense against small extensions.
     103             :      */
     104             : 
     105             : #ifndef DEBUG_LIST_MEMORY_USAGE
     106             : 
     107             :     /*
     108             :      * Normally, we set up a list with some extra cells, to allow it to grow
     109             :      * without a repalloc.  Prefer cell counts chosen to make the total
     110             :      * allocation a power-of-2, since palloc would round it up to that anyway.
     111             :      * (That stops being true for very large allocations, but very long lists
     112             :      * are infrequent, so it doesn't seem worth special logic for such cases.)
     113             :      *
     114             :      * The minimum allocation is 8 ListCell units, providing either 4 or 5
     115             :      * available ListCells depending on the machine's word width.  Counting
     116             :      * palloc's overhead, this uses the same amount of space as a one-cell
     117             :      * list did in the old implementation, and less space for any longer list.
     118             :      *
     119             :      * We needn't worry about integer overflow; no caller passes min_size
     120             :      * that's more than twice the size of an existing list, so the size limits
     121             :      * within palloc will ensure that we don't overflow here.
     122             :      */
     123    79999098 :     max_size = pg_nextpower2_32(Max(8, min_size + LIST_HEADER_OVERHEAD));
     124    79999098 :     max_size -= LIST_HEADER_OVERHEAD;
     125             : #else
     126             : 
     127             :     /*
     128             :      * For debugging, don't allow any extra space.  This forces any cell
     129             :      * addition to go through enlarge_list() and thus move the existing data.
     130             :      */
     131             :     max_size = min_size;
     132             : #endif
     133             : 
     134    79999098 :     newlist = (List *) palloc(offsetof(List, initial_elements) +
     135             :                               max_size * sizeof(ListCell));
     136    79999098 :     newlist->type = type;
     137    79999098 :     newlist->length = min_size;
     138    79999098 :     newlist->max_length = max_size;
     139    79999098 :     newlist->elements = newlist->initial_elements;
     140             : 
     141    79999098 :     return newlist;
     142             : }
     143             : 
     144             : /*
     145             :  * Enlarge an existing non-NIL List to have room for at least min_size cells.
     146             :  *
     147             :  * This does *not* update list->length, as some callers would find that
     148             :  * inconvenient.  (list->length had better be the correct number of existing
     149             :  * valid cells, though.)
     150             :  */
     151             : static void
     152     5671208 : enlarge_list(List *list, int min_size)
     153             : {
     154             :     int         new_max_len;
     155             : 
     156             :     Assert(min_size > list->max_length);  /* else we shouldn't be here */
     157             : 
     158             : #ifndef DEBUG_LIST_MEMORY_USAGE
     159             : 
     160             :     /*
     161             :      * As above, we prefer power-of-two total allocations; but here we need
     162             :      * not account for list header overhead.
     163             :      */
     164             : 
     165             :     /* clamp the minimum value to 16, a semi-arbitrary small power of 2 */
     166     5671208 :     new_max_len = pg_nextpower2_32(Max(16, min_size));
     167             : 
     168             : #else
     169             :     /* As above, don't allocate anything extra */
     170             :     new_max_len = min_size;
     171             : #endif
     172             : 
     173     5671208 :     if (list->elements == list->initial_elements)
     174             :     {
     175             :         /*
     176             :          * Replace original in-line allocation with a separate palloc block.
     177             :          * Ensure it is in the same memory context as the List header.  (The
     178             :          * previous List implementation did not offer any guarantees about
     179             :          * keeping all list cells in the same context, but it seems reasonable
     180             :          * to create such a guarantee now.)
     181             :          */
     182     3451580 :         list->elements = (ListCell *)
     183     3451580 :             MemoryContextAlloc(GetMemoryChunkContext(list),
     184             :                                new_max_len * sizeof(ListCell));
     185     3451580 :         memcpy(list->elements, list->initial_elements,
     186     3451580 :                list->length * sizeof(ListCell));
     187             : 
     188             :         /*
     189             :          * We must not move the list header, so it's unsafe to try to reclaim
     190             :          * the initial_elements[] space via repalloc.  In debugging builds,
     191             :          * however, we can clear that space and/or mark it inaccessible.
     192             :          * (wipe_mem includes VALGRIND_MAKE_MEM_NOACCESS.)
     193             :          */
     194             : #ifdef CLOBBER_FREED_MEMORY
     195             :         wipe_mem(list->initial_elements,
     196             :                  list->max_length * sizeof(ListCell));
     197             : #else
     198             :         VALGRIND_MAKE_MEM_NOACCESS(list->initial_elements,
     199             :                                    list->max_length * sizeof(ListCell));
     200             : #endif
     201             :     }
     202             :     else
     203             :     {
     204             : #ifndef DEBUG_LIST_MEMORY_USAGE
     205             :         /* Normally, let repalloc deal with enlargement */
     206     2219628 :         list->elements = (ListCell *) repalloc(list->elements,
     207             :                                                new_max_len * sizeof(ListCell));
     208             : #else
     209             :         /*
     210             :          * repalloc() might enlarge the space in-place, which we don't want
     211             :          * for debugging purposes, so forcibly move the data somewhere else.
     212             :          */
     213             :         ListCell   *newelements;
     214             : 
     215             :         newelements = (ListCell *)
     216             :             MemoryContextAlloc(GetMemoryChunkContext(list),
     217             :                                new_max_len * sizeof(ListCell));
     218             :         memcpy(newelements, list->elements,
     219             :                list->length * sizeof(ListCell));
     220             :         pfree(list->elements);
     221             :         list->elements = newelements;
     222             : #endif
     223             :     }
     224             : 
     225     5671208 :     list->max_length = new_max_len;
     226     5671208 : }
     227             : 
     228             : /*
     229             :  * Convenience functions to construct short Lists from given values.
     230             :  * (These are normally invoked via the list_makeN macros.)
     231             :  */
     232             : List *
     233    11648396 : list_make1_impl(NodeTag t, ListCell datum1)
     234             : {
     235    11648396 :     List       *list = new_list(t, 1);
     236             : 
     237    11648396 :     list->elements[0] = datum1;
     238             :     check_list_invariants(list);
     239    11648396 :     return list;
     240             : }
     241             : 
     242             : List *
     243     1707922 : list_make2_impl(NodeTag t, ListCell datum1, ListCell datum2)
     244             : {
     245     1707922 :     List       *list = new_list(t, 2);
     246             : 
     247     1707922 :     list->elements[0] = datum1;
     248     1707922 :     list->elements[1] = datum2;
     249             :     check_list_invariants(list);
     250     1707922 :     return list;
     251             : }
     252             : 
     253             : List *
     254        4192 : list_make3_impl(NodeTag t, ListCell datum1, ListCell datum2,
     255             :                 ListCell datum3)
     256             : {
     257        4192 :     List       *list = new_list(t, 3);
     258             : 
     259        4192 :     list->elements[0] = datum1;
     260        4192 :     list->elements[1] = datum2;
     261        4192 :     list->elements[2] = datum3;
     262             :     check_list_invariants(list);
     263        4192 :     return list;
     264             : }
     265             : 
     266             : List *
     267         208 : list_make4_impl(NodeTag t, ListCell datum1, ListCell datum2,
     268             :                 ListCell datum3, ListCell datum4)
     269             : {
     270         208 :     List       *list = new_list(t, 4);
     271             : 
     272         208 :     list->elements[0] = datum1;
     273         208 :     list->elements[1] = datum2;
     274         208 :     list->elements[2] = datum3;
     275         208 :     list->elements[3] = datum4;
     276             :     check_list_invariants(list);
     277         208 :     return list;
     278             : }
     279             : 
     280             : List *
     281         264 : list_make5_impl(NodeTag t, ListCell datum1, ListCell datum2,
     282             :                 ListCell datum3, ListCell datum4, ListCell datum5)
     283             : {
     284         264 :     List       *list = new_list(t, 5);
     285             : 
     286         264 :     list->elements[0] = datum1;
     287         264 :     list->elements[1] = datum2;
     288         264 :     list->elements[2] = datum3;
     289         264 :     list->elements[3] = datum4;
     290         264 :     list->elements[4] = datum5;
     291             :     check_list_invariants(list);
     292         264 :     return list;
     293             : }
     294             : 
     295             : /*
     296             :  * Make room for a new head cell in the given (non-NIL) list.
     297             :  *
     298             :  * The data in the new head cell is undefined; the caller should be
     299             :  * sure to fill it in
     300             :  */
     301             : static void
     302     2734022 : new_head_cell(List *list)
     303             : {
     304             :     /* Enlarge array if necessary */
     305     2734022 :     if (list->length >= list->max_length)
     306       50724 :         enlarge_list(list, list->length + 1);
     307             :     /* Now shove the existing data over */
     308     2734022 :     memmove(&list->elements[1], &list->elements[0],
     309     2734022 :             list->length * sizeof(ListCell));
     310     2734022 :     list->length++;
     311     2734022 : }
     312             : 
     313             : /*
     314             :  * Make room for a new tail cell in the given (non-NIL) list.
     315             :  *
     316             :  * The data in the new tail cell is undefined; the caller should be
     317             :  * sure to fill it in
     318             :  */
     319             : static void
     320    86290782 : new_tail_cell(List *list)
     321             : {
     322             :     /* Enlarge array if necessary */
     323    86290782 :     if (list->length >= list->max_length)
     324     5585034 :         enlarge_list(list, list->length + 1);
     325    86290782 :     list->length++;
     326    86290782 : }
     327             : 
     328             : /*
     329             :  * Append a pointer to the list. A pointer to the modified list is
     330             :  * returned. Note that this function may or may not destructively
     331             :  * modify the list; callers should always use this function's return
     332             :  * value, rather than continuing to use the pointer passed as the
     333             :  * first argument.
     334             :  */
     335             : List *
     336   103702198 : lappend(List *list, void *datum)
     337             : {
     338             :     Assert(IsPointerList(list));
     339             : 
     340   103702198 :     if (list == NIL)
     341    30485788 :         list = new_list(T_List, 1);
     342             :     else
     343    73216410 :         new_tail_cell(list);
     344             : 
     345   103702198 :     llast(list) = datum;
     346             :     check_list_invariants(list);
     347   103702198 :     return list;
     348             : }
     349             : 
     350             : /*
     351             :  * Append an integer to the specified list. See lappend()
     352             :  */
     353             : List *
     354    12577006 : lappend_int(List *list, int datum)
     355             : {
     356             :     Assert(IsIntegerList(list));
     357             : 
     358    12577006 :     if (list == NIL)
     359     1260916 :         list = new_list(T_IntList, 1);
     360             :     else
     361    11316090 :         new_tail_cell(list);
     362             : 
     363    12577006 :     llast_int(list) = datum;
     364             :     check_list_invariants(list);
     365    12577006 :     return list;
     366             : }
     367             : 
     368             : /*
     369             :  * Append an OID to the specified list. See lappend()
     370             :  */
     371             : List *
     372     4376880 : lappend_oid(List *list, Oid datum)
     373             : {
     374             :     Assert(IsOidList(list));
     375             : 
     376     4376880 :     if (list == NIL)
     377     2618598 :         list = new_list(T_OidList, 1);
     378             :     else
     379     1758282 :         new_tail_cell(list);
     380             : 
     381     4376880 :     llast_oid(list) = datum;
     382             :     check_list_invariants(list);
     383     4376880 :     return list;
     384             : }
     385             : 
     386             : /*
     387             :  * Make room for a new cell at position 'pos' (measured from 0).
     388             :  * The data in the cell is left undefined, and must be filled in by the
     389             :  * caller. 'list' is assumed to be non-NIL, and 'pos' must be a valid
     390             :  * list position, ie, 0 <= pos <= list's length.
     391             :  * Returns address of the new cell.
     392             :  */
     393             : static ListCell *
     394      285396 : insert_new_cell(List *list, int pos)
     395             : {
     396             :     Assert(pos >= 0 && pos <= list->length);
     397             : 
     398             :     /* Enlarge array if necessary */
     399      285396 :     if (list->length >= list->max_length)
     400         482 :         enlarge_list(list, list->length + 1);
     401             :     /* Now shove the existing data over */
     402      285396 :     if (pos < list->length)
     403      121960 :         memmove(&list->elements[pos + 1], &list->elements[pos],
     404      121960 :                 (list->length - pos) * sizeof(ListCell));
     405      285396 :     list->length++;
     406             : 
     407      285396 :     return &list->elements[pos];
     408             : }
     409             : 
     410             : /*
     411             :  * Insert the given datum at position 'pos' (measured from 0) in the list.
     412             :  * 'pos' must be valid, ie, 0 <= pos <= list's length.
     413             :  *
     414             :  * Note that this takes time proportional to the distance to the end of the
     415             :  * list, since the following entries must be moved.
     416             :  */
     417             : List *
     418     1382528 : list_insert_nth(List *list, int pos, void *datum)
     419             : {
     420     1382528 :     if (list == NIL)
     421             :     {
     422             :         Assert(pos == 0);
     423     1097132 :         return list_make1(datum);
     424             :     }
     425             :     Assert(IsPointerList(list));
     426      285396 :     lfirst(insert_new_cell(list, pos)) = datum;
     427             :     check_list_invariants(list);
     428      285396 :     return list;
     429             : }
     430             : 
     431             : List *
     432           0 : list_insert_nth_int(List *list, int pos, int datum)
     433             : {
     434           0 :     if (list == NIL)
     435             :     {
     436             :         Assert(pos == 0);
     437           0 :         return list_make1_int(datum);
     438             :     }
     439             :     Assert(IsIntegerList(list));
     440           0 :     lfirst_int(insert_new_cell(list, pos)) = datum;
     441             :     check_list_invariants(list);
     442           0 :     return list;
     443             : }
     444             : 
     445             : List *
     446           0 : list_insert_nth_oid(List *list, int pos, Oid datum)
     447             : {
     448           0 :     if (list == NIL)
     449             :     {
     450             :         Assert(pos == 0);
     451           0 :         return list_make1_oid(datum);
     452             :     }
     453             :     Assert(IsOidList(list));
     454           0 :     lfirst_oid(insert_new_cell(list, pos)) = datum;
     455             :     check_list_invariants(list);
     456           0 :     return list;
     457             : }
     458             : 
     459             : /*
     460             :  * Prepend a new element to the list. A pointer to the modified list
     461             :  * is returned. Note that this function may or may not destructively
     462             :  * modify the list; callers should always use this function's return
     463             :  * value, rather than continuing to use the pointer passed as the
     464             :  * second argument.
     465             :  *
     466             :  * Note that this takes time proportional to the length of the list,
     467             :  * since the existing entries must be moved.
     468             :  *
     469             :  * Caution: before Postgres 8.0, the original List was unmodified and
     470             :  * could be considered to retain its separate identity.  This is no longer
     471             :  * the case.
     472             :  */
     473             : List *
     474     5673126 : lcons(void *datum, List *list)
     475             : {
     476             :     Assert(IsPointerList(list));
     477             : 
     478     5673126 :     if (list == NIL)
     479     2961340 :         list = new_list(T_List, 1);
     480             :     else
     481     2711786 :         new_head_cell(list);
     482             : 
     483     5673126 :     linitial(list) = datum;
     484             :     check_list_invariants(list);
     485     5673126 :     return list;
     486             : }
     487             : 
     488             : /*
     489             :  * Prepend an integer to the list. See lcons()
     490             :  */
     491             : List *
     492       10026 : lcons_int(int datum, List *list)
     493             : {
     494             :     Assert(IsIntegerList(list));
     495             : 
     496       10026 :     if (list == NIL)
     497        5554 :         list = new_list(T_IntList, 1);
     498             :     else
     499        4472 :         new_head_cell(list);
     500             : 
     501       10026 :     linitial_int(list) = datum;
     502             :     check_list_invariants(list);
     503       10026 :     return list;
     504             : }
     505             : 
     506             : /*
     507             :  * Prepend an OID to the list. See lcons()
     508             :  */
     509             : List *
     510       18824 : lcons_oid(Oid datum, List *list)
     511             : {
     512             :     Assert(IsOidList(list));
     513             : 
     514       18824 :     if (list == NIL)
     515        1060 :         list = new_list(T_OidList, 1);
     516             :     else
     517       17764 :         new_head_cell(list);
     518             : 
     519       18824 :     linitial_oid(list) = datum;
     520             :     check_list_invariants(list);
     521       18824 :     return list;
     522             : }
     523             : 
     524             : /*
     525             :  * Concatenate list2 to the end of list1, and return list1.
     526             :  *
     527             :  * This is equivalent to lappend'ing each element of list2, in order, to list1.
     528             :  * list1 is destructively changed, list2 is not.  (However, in the case of
     529             :  * pointer lists, list1 and list2 will point to the same structures.)
     530             :  *
     531             :  * Callers should be sure to use the return value as the new pointer to the
     532             :  * concatenated list: the 'list1' input pointer may or may not be the same
     533             :  * as the returned pointer.
     534             :  *
     535             :  * Note that this takes at least time proportional to the length of list2.
     536             :  * It'd typically be the case that we have to enlarge list1's storage,
     537             :  * probably adding time proportional to the length of list1.
     538             :  */
     539             : List *
     540     3704896 : list_concat(List *list1, const List *list2)
     541             : {
     542             :     int         new_len;
     543             : 
     544     3704896 :     if (list1 == NIL)
     545     2603332 :         return list_copy(list2);
     546     1101564 :     if (list2 == NIL)
     547      552652 :         return list1;
     548             : 
     549             :     Assert(list1->type == list2->type);
     550             : 
     551      548912 :     new_len = list1->length + list2->length;
     552             :     /* Enlarge array if necessary */
     553      548912 :     if (new_len > list1->max_length)
     554       34968 :         enlarge_list(list1, new_len);
     555             : 
     556             :     /* Even if list1 == list2, using memcpy should be safe here */
     557      548912 :     memcpy(&list1->elements[list1->length], &list2->elements[0],
     558      548912 :            list2->length * sizeof(ListCell));
     559      548912 :     list1->length = new_len;
     560             : 
     561             :     check_list_invariants(list1);
     562      548912 :     return list1;
     563             : }
     564             : 
     565             : /*
     566             :  * Form a new list by concatenating the elements of list1 and list2.
     567             :  *
     568             :  * Neither input list is modified.  (However, if they are pointer lists,
     569             :  * the output list will point to the same structures.)
     570             :  *
     571             :  * This is equivalent to, but more efficient than,
     572             :  * list_concat(list_copy(list1), list2).
     573             :  * Note that some pre-v13 code might list_copy list2 as well, but that's
     574             :  * pointless now.
     575             :  */
     576             : List *
     577      558000 : list_concat_copy(const List *list1, const List *list2)
     578             : {
     579             :     List       *result;
     580             :     int         new_len;
     581             : 
     582      558000 :     if (list1 == NIL)
     583      238374 :         return list_copy(list2);
     584      319626 :     if (list2 == NIL)
     585      283188 :         return list_copy(list1);
     586             : 
     587             :     Assert(list1->type == list2->type);
     588             : 
     589       36438 :     new_len = list1->length + list2->length;
     590       36438 :     result = new_list(list1->type, new_len);
     591       36438 :     memcpy(result->elements, list1->elements,
     592       36438 :            list1->length * sizeof(ListCell));
     593       36438 :     memcpy(result->elements + list1->length, list2->elements,
     594       36438 :            list2->length * sizeof(ListCell));
     595             : 
     596             :     check_list_invariants(result);
     597       36438 :     return result;
     598             : }
     599             : 
     600             : /*
     601             :  * Truncate 'list' to contain no more than 'new_size' elements. This
     602             :  * modifies the list in-place! Despite this, callers should use the
     603             :  * pointer returned by this function to refer to the newly truncated
     604             :  * list -- it may or may not be the same as the pointer that was
     605             :  * passed.
     606             :  *
     607             :  * Note that any cells removed by list_truncate() are NOT pfree'd.
     608             :  */
     609             : List *
     610      337496 : list_truncate(List *list, int new_size)
     611             : {
     612      337496 :     if (new_size <= 0)
     613       93918 :         return NIL;             /* truncate to zero length */
     614             : 
     615             :     /* If asked to effectively extend the list, do nothing */
     616      243578 :     if (new_size < list_length(list))
     617       86682 :         list->length = new_size;
     618             : 
     619             :     /*
     620             :      * Note: unlike the individual-list-cell deletion functions, we don't move
     621             :      * the list cells to new storage, even in DEBUG_LIST_MEMORY_USAGE mode.
     622             :      * This is because none of them can move in this operation, so just like
     623             :      * in the old cons-cell-based implementation, this function doesn't
     624             :      * invalidate any pointers to cells of the list.  This is also the reason
     625             :      * for not wiping the memory of the deleted cells: the old code didn't
     626             :      * free them either.  Perhaps later we'll tighten this up.
     627             :      */
     628             : 
     629      243578 :     return list;
     630             : }
     631             : 
     632             : /*
     633             :  * Return true iff 'datum' is a member of the list. Equality is
     634             :  * determined via equal(), so callers should ensure that they pass a
     635             :  * Node as 'datum'.
     636             :  *
     637             :  * This does a simple linear search --- avoid using it on long lists.
     638             :  */
     639             : bool
     640      108566 : list_member(const List *list, const void *datum)
     641             : {
     642             :     const ListCell *cell;
     643             : 
     644             :     Assert(IsPointerList(list));
     645             :     check_list_invariants(list);
     646             : 
     647      145218 :     foreach(cell, list)
     648             :     {
     649       80188 :         if (equal(lfirst(cell), datum))
     650       43536 :             return true;
     651             :     }
     652             : 
     653       65030 :     return false;
     654             : }
     655             : 
     656             : /*
     657             :  * Return true iff 'datum' is a member of the list. Equality is
     658             :  * determined by using simple pointer comparison.
     659             :  */
     660             : bool
     661      197758 : list_member_ptr(const List *list, const void *datum)
     662             : {
     663             :     const ListCell *cell;
     664             : 
     665             :     Assert(IsPointerList(list));
     666             :     check_list_invariants(list);
     667             : 
     668      271548 :     foreach(cell, list)
     669             :     {
     670      154444 :         if (lfirst(cell) == datum)
     671       80654 :             return true;
     672             :     }
     673             : 
     674      117104 :     return false;
     675             : }
     676             : 
     677             : /*
     678             :  * Return true iff the integer 'datum' is a member of the list.
     679             :  */
     680             : bool
     681       72602 : list_member_int(const List *list, int datum)
     682             : {
     683             :     const ListCell *cell;
     684             : 
     685             :     Assert(IsIntegerList(list));
     686             :     check_list_invariants(list);
     687             : 
     688     5010822 :     foreach(cell, list)
     689             :     {
     690     4956848 :         if (lfirst_int(cell) == datum)
     691       18628 :             return true;
     692             :     }
     693             : 
     694       53974 :     return false;
     695             : }
     696             : 
     697             : /*
     698             :  * Return true iff the OID 'datum' is a member of the list.
     699             :  */
     700             : bool
     701    40203954 : list_member_oid(const List *list, Oid datum)
     702             : {
     703             :     const ListCell *cell;
     704             : 
     705             :     Assert(IsOidList(list));
     706             :     check_list_invariants(list);
     707             : 
     708    42264342 :     foreach(cell, list)
     709             :     {
     710     2491170 :         if (lfirst_oid(cell) == datum)
     711      430782 :             return true;
     712             :     }
     713             : 
     714    39773172 :     return false;
     715             : }
     716             : 
     717             : /*
     718             :  * Delete the n'th cell (counting from 0) in list.
     719             :  *
     720             :  * The List is pfree'd if this was the last member.
     721             :  *
     722             :  * Note that this takes time proportional to the distance to the end of the
     723             :  * list, since the following entries must be moved.
     724             :  */
     725             : List *
     726     2279406 : list_delete_nth_cell(List *list, int n)
     727             : {
     728             :     check_list_invariants(list);
     729             : 
     730             :     Assert(n >= 0 && n < list->length);
     731             : 
     732             :     /*
     733             :      * If we're about to delete the last node from the list, free the whole
     734             :      * list instead and return NIL, which is the only valid representation of
     735             :      * a zero-length list.
     736             :      */
     737     2279406 :     if (list->length == 1)
     738             :     {
     739     1298042 :         list_free(list);
     740     1298042 :         return NIL;
     741             :     }
     742             : 
     743             :     /*
     744             :      * Otherwise, we normally just collapse out the removed element.  But for
     745             :      * debugging purposes, move the whole list contents someplace else.
     746             :      *
     747             :      * (Note that we *must* keep the contents in the same memory context.)
     748             :      */
     749             : #ifndef DEBUG_LIST_MEMORY_USAGE
     750      981364 :     memmove(&list->elements[n], &list->elements[n + 1],
     751      981364 :             (list->length - 1 - n) * sizeof(ListCell));
     752      981364 :     list->length--;
     753             : #else
     754             :     {
     755             :         ListCell   *newelems;
     756             :         int         newmaxlen = list->length - 1;
     757             : 
     758             :         newelems = (ListCell *)
     759             :             MemoryContextAlloc(GetMemoryChunkContext(list),
     760             :                                newmaxlen * sizeof(ListCell));
     761             :         memcpy(newelems, list->elements, n * sizeof(ListCell));
     762             :         memcpy(&newelems[n], &list->elements[n + 1],
     763             :                (list->length - 1 - n) * sizeof(ListCell));
     764             :         if (list->elements != list->initial_elements)
     765             :             pfree(list->elements);
     766             :         else
     767             :         {
     768             :             /*
     769             :              * As in enlarge_list(), clear the initial_elements[] space and/or
     770             :              * mark it inaccessible.
     771             :              */
     772             : #ifdef CLOBBER_FREED_MEMORY
     773             :             wipe_mem(list->initial_elements,
     774             :                      list->max_length * sizeof(ListCell));
     775             : #else
     776             :             VALGRIND_MAKE_MEM_NOACCESS(list->initial_elements,
     777             :                                        list->max_length * sizeof(ListCell));
     778             : #endif
     779             :         }
     780             :         list->elements = newelems;
     781             :         list->max_length = newmaxlen;
     782             :         list->length--;
     783             :         check_list_invariants(list);
     784             :     }
     785             : #endif
     786             : 
     787      981364 :     return list;
     788             : }
     789             : 
     790             : /*
     791             :  * Delete 'cell' from 'list'.
     792             :  *
     793             :  * The List is pfree'd if this was the last member.  However, we do not
     794             :  * touch any data the cell might've been pointing to.
     795             :  *
     796             :  * Note that this takes time proportional to the distance to the end of the
     797             :  * list, since the following entries must be moved.
     798             :  */
     799             : List *
     800     1665264 : list_delete_cell(List *list, ListCell *cell)
     801             : {
     802     1665264 :     return list_delete_nth_cell(list, cell - list->elements);
     803             : }
     804             : 
     805             : /*
     806             :  * Delete the first cell in list that matches datum, if any.
     807             :  * Equality is determined via equal().
     808             :  *
     809             :  * This does a simple linear search --- avoid using it on long lists.
     810             :  */
     811             : List *
     812           8 : list_delete(List *list, void *datum)
     813             : {
     814             :     ListCell   *cell;
     815             : 
     816             :     Assert(IsPointerList(list));
     817             :     check_list_invariants(list);
     818             : 
     819           8 :     foreach(cell, list)
     820             :     {
     821           4 :         if (equal(lfirst(cell), datum))
     822           4 :             return list_delete_cell(list, cell);
     823             :     }
     824             : 
     825             :     /* Didn't find a match: return the list unmodified */
     826           4 :     return list;
     827             : }
     828             : 
     829             : /* As above, but use simple pointer equality */
     830             : List *
     831     1354072 : list_delete_ptr(List *list, void *datum)
     832             : {
     833             :     ListCell   *cell;
     834             : 
     835             :     Assert(IsPointerList(list));
     836             :     check_list_invariants(list);
     837             : 
     838     1354264 :     foreach(cell, list)
     839             :     {
     840     1354264 :         if (lfirst(cell) == datum)
     841     1354072 :             return list_delete_cell(list, cell);
     842             :     }
     843             : 
     844             :     /* Didn't find a match: return the list unmodified */
     845           0 :     return list;
     846             : }
     847             : 
     848             : /* As above, but for integers */
     849             : List *
     850          56 : list_delete_int(List *list, int datum)
     851             : {
     852             :     ListCell   *cell;
     853             : 
     854             :     Assert(IsIntegerList(list));
     855             :     check_list_invariants(list);
     856             : 
     857          60 :     foreach(cell, list)
     858             :     {
     859          60 :         if (lfirst_int(cell) == datum)
     860          56 :             return list_delete_cell(list, cell);
     861             :     }
     862             : 
     863             :     /* Didn't find a match: return the list unmodified */
     864           0 :     return list;
     865             : }
     866             : 
     867             : /* As above, but for OIDs */
     868             : List *
     869        7286 : list_delete_oid(List *list, Oid datum)
     870             : {
     871             :     ListCell   *cell;
     872             : 
     873             :     Assert(IsOidList(list));
     874             :     check_list_invariants(list);
     875             : 
     876        7286 :     foreach(cell, list)
     877             :     {
     878        1024 :         if (lfirst_oid(cell) == datum)
     879        1024 :             return list_delete_cell(list, cell);
     880             :     }
     881             : 
     882             :     /* Didn't find a match: return the list unmodified */
     883        6262 :     return list;
     884             : }
     885             : 
     886             : /*
     887             :  * Delete the first element of the list.
     888             :  *
     889             :  * This is useful to replace the Lisp-y code "list = lnext(list);" in cases
     890             :  * where the intent is to alter the list rather than just traverse it.
     891             :  * Beware that the list is modified, whereas the Lisp-y coding leaves
     892             :  * the original list head intact in case there's another pointer to it.
     893             :  *
     894             :  * Note that this takes time proportional to the length of the list,
     895             :  * since the remaining entries must be moved.  Consider reversing the
     896             :  * list order so that you can use list_delete_last() instead.  However,
     897             :  * if that causes you to replace lappend() with lcons(), you haven't
     898             :  * improved matters.  (In short, you can make an efficient stack from
     899             :  * a List, but not an efficient FIFO queue.)
     900             :  */
     901             : List *
     902      589996 : list_delete_first(List *list)
     903             : {
     904             :     check_list_invariants(list);
     905             : 
     906      589996 :     if (list == NIL)
     907           0 :         return NIL;             /* would an error be better? */
     908             : 
     909      589996 :     return list_delete_nth_cell(list, 0);
     910             : }
     911             : 
     912             : /*
     913             :  * Delete the last element of the list.
     914             :  */
     915             : List *
     916       41918 : list_delete_last(List *list)
     917             : {
     918             :     check_list_invariants(list);
     919             : 
     920       41918 :     if (list == NIL)
     921           0 :         return NIL;             /* would an error be better? */
     922             : 
     923             :     /* list_truncate won't free list if it goes to empty, but this should */
     924       41918 :     if (list_length(list) <= 1)
     925             :     {
     926       21248 :         list_free(list);
     927       21248 :         return NIL;
     928             :     }
     929             : 
     930       20670 :     return list_truncate(list, list_length(list) - 1);
     931             : }
     932             : 
     933             : /*
     934             :  * Delete the first N cells of the list.
     935             :  *
     936             :  * The List is pfree'd if the request causes all cells to be deleted.
     937             :  *
     938             :  * Note that this takes time proportional to the distance to the end of the
     939             :  * list, since the following entries must be moved.
     940             :  */
     941             : List *
     942         302 : list_delete_first_n(List *list, int n)
     943             : {
     944             :     check_list_invariants(list);
     945             : 
     946             :     /* No-op request? */
     947         302 :     if (n <= 0)
     948           0 :         return list;
     949             : 
     950             :     /* Delete whole list? */
     951         302 :     if (n >= list_length(list))
     952             :     {
     953           0 :         list_free(list);
     954           0 :         return NIL;
     955             :     }
     956             : 
     957             :     /*
     958             :      * Otherwise, we normally just collapse out the removed elements.  But for
     959             :      * debugging purposes, move the whole list contents someplace else.
     960             :      *
     961             :      * (Note that we *must* keep the contents in the same memory context.)
     962             :      */
     963             : #ifndef DEBUG_LIST_MEMORY_USAGE
     964         302 :     memmove(&list->elements[0], &list->elements[n],
     965         302 :             (list->length - n) * sizeof(ListCell));
     966         302 :     list->length -= n;
     967             : #else
     968             :     {
     969             :         ListCell   *newelems;
     970             :         int         newmaxlen = list->length - n;
     971             : 
     972             :         newelems = (ListCell *)
     973             :             MemoryContextAlloc(GetMemoryChunkContext(list),
     974             :                                newmaxlen * sizeof(ListCell));
     975             :         memcpy(newelems, &list->elements[n], newmaxlen * sizeof(ListCell));
     976             :         if (list->elements != list->initial_elements)
     977             :             pfree(list->elements);
     978             :         else
     979             :         {
     980             :             /*
     981             :              * As in enlarge_list(), clear the initial_elements[] space and/or
     982             :              * mark it inaccessible.
     983             :              */
     984             : #ifdef CLOBBER_FREED_MEMORY
     985             :             wipe_mem(list->initial_elements,
     986             :                      list->max_length * sizeof(ListCell));
     987             : #else
     988             :             VALGRIND_MAKE_MEM_NOACCESS(list->initial_elements,
     989             :                                        list->max_length * sizeof(ListCell));
     990             : #endif
     991             :         }
     992             :         list->elements = newelems;
     993             :         list->max_length = newmaxlen;
     994             :         list->length = newmaxlen;
     995             :         check_list_invariants(list);
     996             :     }
     997             : #endif
     998             : 
     999         302 :     return list;
    1000             : }
    1001             : 
    1002             : /*
    1003             :  * Generate the union of two lists. This is calculated by copying
    1004             :  * list1 via list_copy(), then adding to it all the members of list2
    1005             :  * that aren't already in list1.
    1006             :  *
    1007             :  * Whether an element is already a member of the list is determined
    1008             :  * via equal().
    1009             :  *
    1010             :  * The returned list is newly-allocated, although the content of the
    1011             :  * cells is the same (i.e. any pointed-to objects are not copied).
    1012             :  *
    1013             :  * NB: this function will NOT remove any duplicates that are present
    1014             :  * in list1 (so it only performs a "union" if list1 is known unique to
    1015             :  * start with).  Also, if you are about to write "x = list_union(x, y)"
    1016             :  * you probably want to use list_concat_unique() instead to avoid wasting
    1017             :  * the storage of the old x list.
    1018             :  *
    1019             :  * Note that this takes time proportional to the product of the list
    1020             :  * lengths, so beware of using it on long lists.  (We could probably
    1021             :  * improve that, but really you should be using some other data structure
    1022             :  * if this'd be a performance bottleneck.)
    1023             :  */
    1024             : List *
    1025        5226 : list_union(const List *list1, const List *list2)
    1026             : {
    1027             :     List       *result;
    1028             :     const ListCell *cell;
    1029             : 
    1030             :     Assert(IsPointerList(list1));
    1031             :     Assert(IsPointerList(list2));
    1032             : 
    1033        5226 :     result = list_copy(list1);
    1034       10878 :     foreach(cell, list2)
    1035             :     {
    1036        5652 :         if (!list_member(result, lfirst(cell)))
    1037        5458 :             result = lappend(result, lfirst(cell));
    1038             :     }
    1039             : 
    1040             :     check_list_invariants(result);
    1041        5226 :     return result;
    1042             : }
    1043             : 
    1044             : /*
    1045             :  * This variant of list_union() determines duplicates via simple
    1046             :  * pointer comparison.
    1047             :  */
    1048             : List *
    1049           0 : list_union_ptr(const List *list1, const List *list2)
    1050             : {
    1051             :     List       *result;
    1052             :     const ListCell *cell;
    1053             : 
    1054             :     Assert(IsPointerList(list1));
    1055             :     Assert(IsPointerList(list2));
    1056             : 
    1057           0 :     result = list_copy(list1);
    1058           0 :     foreach(cell, list2)
    1059             :     {
    1060           0 :         if (!list_member_ptr(result, lfirst(cell)))
    1061           0 :             result = lappend(result, lfirst(cell));
    1062             :     }
    1063             : 
    1064             :     check_list_invariants(result);
    1065           0 :     return result;
    1066             : }
    1067             : 
    1068             : /*
    1069             :  * This variant of list_union() operates upon lists of integers.
    1070             :  */
    1071             : List *
    1072        3572 : list_union_int(const List *list1, const List *list2)
    1073             : {
    1074             :     List       *result;
    1075             :     const ListCell *cell;
    1076             : 
    1077             :     Assert(IsIntegerList(list1));
    1078             :     Assert(IsIntegerList(list2));
    1079             : 
    1080        3572 :     result = list_copy(list1);
    1081        7276 :     foreach(cell, list2)
    1082             :     {
    1083        3704 :         if (!list_member_int(result, lfirst_int(cell)))
    1084        3536 :             result = lappend_int(result, lfirst_int(cell));
    1085             :     }
    1086             : 
    1087             :     check_list_invariants(result);
    1088        3572 :     return result;
    1089             : }
    1090             : 
    1091             : /*
    1092             :  * This variant of list_union() operates upon lists of OIDs.
    1093             :  */
    1094             : List *
    1095           0 : list_union_oid(const List *list1, const List *list2)
    1096             : {
    1097             :     List       *result;
    1098             :     const ListCell *cell;
    1099             : 
    1100             :     Assert(IsOidList(list1));
    1101             :     Assert(IsOidList(list2));
    1102             : 
    1103           0 :     result = list_copy(list1);
    1104           0 :     foreach(cell, list2)
    1105             :     {
    1106           0 :         if (!list_member_oid(result, lfirst_oid(cell)))
    1107           0 :             result = lappend_oid(result, lfirst_oid(cell));
    1108             :     }
    1109             : 
    1110             :     check_list_invariants(result);
    1111           0 :     return result;
    1112             : }
    1113             : 
    1114             : /*
    1115             :  * Return a list that contains all the cells that are in both list1 and
    1116             :  * list2.  The returned list is freshly allocated via palloc(), but the
    1117             :  * cells themselves point to the same objects as the cells of the
    1118             :  * input lists.
    1119             :  *
    1120             :  * Duplicate entries in list1 will not be suppressed, so it's only a true
    1121             :  * "intersection" if list1 is known unique beforehand.
    1122             :  *
    1123             :  * This variant works on lists of pointers, and determines list
    1124             :  * membership via equal().  Note that the list1 member will be pointed
    1125             :  * to in the result.
    1126             :  *
    1127             :  * Note that this takes time proportional to the product of the list
    1128             :  * lengths, so beware of using it on long lists.  (We could probably
    1129             :  * improve that, but really you should be using some other data structure
    1130             :  * if this'd be a performance bottleneck.)
    1131             :  */
    1132             : List *
    1133       24690 : list_intersection(const List *list1, const List *list2)
    1134             : {
    1135             :     List       *result;
    1136             :     const ListCell *cell;
    1137             : 
    1138       24690 :     if (list1 == NIL || list2 == NIL)
    1139       22784 :         return NIL;
    1140             : 
    1141             :     Assert(IsPointerList(list1));
    1142             :     Assert(IsPointerList(list2));
    1143             : 
    1144        1906 :     result = NIL;
    1145        5086 :     foreach(cell, list1)
    1146             :     {
    1147        3180 :         if (list_member(list2, lfirst(cell)))
    1148         766 :             result = lappend(result, lfirst(cell));
    1149             :     }
    1150             : 
    1151             :     check_list_invariants(result);
    1152        1906 :     return result;
    1153             : }
    1154             : 
    1155             : /*
    1156             :  * As list_intersection but operates on lists of integers.
    1157             :  */
    1158             : List *
    1159         200 : list_intersection_int(const List *list1, const List *list2)
    1160             : {
    1161             :     List       *result;
    1162             :     const ListCell *cell;
    1163             : 
    1164         200 :     if (list1 == NIL || list2 == NIL)
    1165           0 :         return NIL;
    1166             : 
    1167             :     Assert(IsIntegerList(list1));
    1168             :     Assert(IsIntegerList(list2));
    1169             : 
    1170         200 :     result = NIL;
    1171         432 :     foreach(cell, list1)
    1172             :     {
    1173         232 :         if (list_member_int(list2, lfirst_int(cell)))
    1174         108 :             result = lappend_int(result, lfirst_int(cell));
    1175             :     }
    1176             : 
    1177             :     check_list_invariants(result);
    1178         200 :     return result;
    1179             : }
    1180             : 
    1181             : /*
    1182             :  * Return a list that contains all the cells in list1 that are not in
    1183             :  * list2. The returned list is freshly allocated via palloc(), but the
    1184             :  * cells themselves point to the same objects as the cells of the
    1185             :  * input lists.
    1186             :  *
    1187             :  * This variant works on lists of pointers, and determines list
    1188             :  * membership via equal()
    1189             :  *
    1190             :  * Note that this takes time proportional to the product of the list
    1191             :  * lengths, so beware of using it on long lists.  (We could probably
    1192             :  * improve that, but really you should be using some other data structure
    1193             :  * if this'd be a performance bottleneck.)
    1194             :  */
    1195             : List *
    1196       20290 : list_difference(const List *list1, const List *list2)
    1197             : {
    1198             :     const ListCell *cell;
    1199       20290 :     List       *result = NIL;
    1200             : 
    1201             :     Assert(IsPointerList(list1));
    1202             :     Assert(IsPointerList(list2));
    1203             : 
    1204       20290 :     if (list2 == NIL)
    1205         750 :         return list_copy(list1);
    1206             : 
    1207       42192 :     foreach(cell, list1)
    1208             :     {
    1209       22652 :         if (!list_member(list2, lfirst(cell)))
    1210        1342 :             result = lappend(result, lfirst(cell));
    1211             :     }
    1212             : 
    1213             :     check_list_invariants(result);
    1214       19540 :     return result;
    1215             : }
    1216             : 
    1217             : /*
    1218             :  * This variant of list_difference() determines list membership via
    1219             :  * simple pointer equality.
    1220             :  */
    1221             : List *
    1222       16252 : list_difference_ptr(const List *list1, const List *list2)
    1223             : {
    1224             :     const ListCell *cell;
    1225       16252 :     List       *result = NIL;
    1226             : 
    1227             :     Assert(IsPointerList(list1));
    1228             :     Assert(IsPointerList(list2));
    1229             : 
    1230       16252 :     if (list2 == NIL)
    1231       13840 :         return list_copy(list1);
    1232             : 
    1233        6210 :     foreach(cell, list1)
    1234             :     {
    1235        3798 :         if (!list_member_ptr(list2, lfirst(cell)))
    1236        1582 :             result = lappend(result, lfirst(cell));
    1237             :     }
    1238             : 
    1239             :     check_list_invariants(result);
    1240        2412 :     return result;
    1241             : }
    1242             : 
    1243             : /*
    1244             :  * This variant of list_difference() operates upon lists of integers.
    1245             :  */
    1246             : List *
    1247        1612 : list_difference_int(const List *list1, const List *list2)
    1248             : {
    1249             :     const ListCell *cell;
    1250        1612 :     List       *result = NIL;
    1251             : 
    1252             :     Assert(IsIntegerList(list1));
    1253             :     Assert(IsIntegerList(list2));
    1254             : 
    1255        1612 :     if (list2 == NIL)
    1256        1160 :         return list_copy(list1);
    1257             : 
    1258        1340 :     foreach(cell, list1)
    1259             :     {
    1260         888 :         if (!list_member_int(list2, lfirst_int(cell)))
    1261         348 :             result = lappend_int(result, lfirst_int(cell));
    1262             :     }
    1263             : 
    1264             :     check_list_invariants(result);
    1265         452 :     return result;
    1266             : }
    1267             : 
    1268             : /*
    1269             :  * This variant of list_difference() operates upon lists of OIDs.
    1270             :  */
    1271             : List *
    1272          28 : list_difference_oid(const List *list1, const List *list2)
    1273             : {
    1274             :     const ListCell *cell;
    1275          28 :     List       *result = NIL;
    1276             : 
    1277             :     Assert(IsOidList(list1));
    1278             :     Assert(IsOidList(list2));
    1279             : 
    1280          28 :     if (list2 == NIL)
    1281           8 :         return list_copy(list1);
    1282             : 
    1283          28 :     foreach(cell, list1)
    1284             :     {
    1285           8 :         if (!list_member_oid(list2, lfirst_oid(cell)))
    1286           4 :             result = lappend_oid(result, lfirst_oid(cell));
    1287             :     }
    1288             : 
    1289             :     check_list_invariants(result);
    1290          20 :     return result;
    1291             : }
    1292             : 
    1293             : /*
    1294             :  * Append datum to list, but only if it isn't already in the list.
    1295             :  *
    1296             :  * Whether an element is already a member of the list is determined
    1297             :  * via equal().
    1298             :  *
    1299             :  * This does a simple linear search --- avoid using it on long lists.
    1300             :  */
    1301             : List *
    1302        2306 : list_append_unique(List *list, void *datum)
    1303             : {
    1304        2306 :     if (list_member(list, datum))
    1305         340 :         return list;
    1306             :     else
    1307        1966 :         return lappend(list, datum);
    1308             : }
    1309             : 
    1310             : /*
    1311             :  * This variant of list_append_unique() determines list membership via
    1312             :  * simple pointer equality.
    1313             :  */
    1314             : List *
    1315      190062 : list_append_unique_ptr(List *list, void *datum)
    1316             : {
    1317      190062 :     if (list_member_ptr(list, datum))
    1318       75132 :         return list;
    1319             :     else
    1320      114930 :         return lappend(list, datum);
    1321             : }
    1322             : 
    1323             : /*
    1324             :  * This variant of list_append_unique() operates upon lists of integers.
    1325             :  */
    1326             : List *
    1327           0 : list_append_unique_int(List *list, int datum)
    1328             : {
    1329           0 :     if (list_member_int(list, datum))
    1330           0 :         return list;
    1331             :     else
    1332           0 :         return lappend_int(list, datum);
    1333             : }
    1334             : 
    1335             : /*
    1336             :  * This variant of list_append_unique() operates upon lists of OIDs.
    1337             :  */
    1338             : List *
    1339        3666 : list_append_unique_oid(List *list, Oid datum)
    1340             : {
    1341        3666 :     if (list_member_oid(list, datum))
    1342        1708 :         return list;
    1343             :     else
    1344        1958 :         return lappend_oid(list, datum);
    1345             : }
    1346             : 
    1347             : /*
    1348             :  * Append to list1 each member of list2 that isn't already in list1.
    1349             :  *
    1350             :  * Whether an element is already a member of the list is determined
    1351             :  * via equal().
    1352             :  *
    1353             :  * This is almost the same functionality as list_union(), but list1 is
    1354             :  * modified in-place rather than being copied. However, callers of this
    1355             :  * function may have strict ordering expectations -- i.e. that the relative
    1356             :  * order of those list2 elements that are not duplicates is preserved.
    1357             :  *
    1358             :  * Note that this takes time proportional to the product of the list
    1359             :  * lengths, so beware of using it on long lists.  (We could probably
    1360             :  * improve that, but really you should be using some other data structure
    1361             :  * if this'd be a performance bottleneck.)
    1362             :  */
    1363             : List *
    1364        1476 : list_concat_unique(List *list1, const List *list2)
    1365             : {
    1366             :     ListCell   *cell;
    1367             : 
    1368             :     Assert(IsPointerList(list1));
    1369             :     Assert(IsPointerList(list2));
    1370             : 
    1371        2824 :     foreach(cell, list2)
    1372             :     {
    1373        1348 :         if (!list_member(list1, lfirst(cell)))
    1374        1332 :             list1 = lappend(list1, lfirst(cell));
    1375             :     }
    1376             : 
    1377             :     check_list_invariants(list1);
    1378        1476 :     return list1;
    1379             : }
    1380             : 
    1381             : /*
    1382             :  * This variant of list_concat_unique() determines list membership via
    1383             :  * simple pointer equality.
    1384             :  */
    1385             : List *
    1386           0 : list_concat_unique_ptr(List *list1, const List *list2)
    1387             : {
    1388             :     ListCell   *cell;
    1389             : 
    1390             :     Assert(IsPointerList(list1));
    1391             :     Assert(IsPointerList(list2));
    1392             : 
    1393           0 :     foreach(cell, list2)
    1394             :     {
    1395           0 :         if (!list_member_ptr(list1, lfirst(cell)))
    1396           0 :             list1 = lappend(list1, lfirst(cell));
    1397             :     }
    1398             : 
    1399             :     check_list_invariants(list1);
    1400           0 :     return list1;
    1401             : }
    1402             : 
    1403             : /*
    1404             :  * This variant of list_concat_unique() operates upon lists of integers.
    1405             :  */
    1406             : List *
    1407           0 : list_concat_unique_int(List *list1, const List *list2)
    1408             : {
    1409             :     ListCell   *cell;
    1410             : 
    1411             :     Assert(IsIntegerList(list1));
    1412             :     Assert(IsIntegerList(list2));
    1413             : 
    1414           0 :     foreach(cell, list2)
    1415             :     {
    1416           0 :         if (!list_member_int(list1, lfirst_int(cell)))
    1417           0 :             list1 = lappend_int(list1, lfirst_int(cell));
    1418             :     }
    1419             : 
    1420             :     check_list_invariants(list1);
    1421           0 :     return list1;
    1422             : }
    1423             : 
    1424             : /*
    1425             :  * This variant of list_concat_unique() operates upon lists of OIDs.
    1426             :  */
    1427             : List *
    1428        7940 : list_concat_unique_oid(List *list1, const List *list2)
    1429             : {
    1430             :     ListCell   *cell;
    1431             : 
    1432             :     Assert(IsOidList(list1));
    1433             :     Assert(IsOidList(list2));
    1434             : 
    1435        8916 :     foreach(cell, list2)
    1436             :     {
    1437         976 :         if (!list_member_oid(list1, lfirst_oid(cell)))
    1438         704 :             list1 = lappend_oid(list1, lfirst_oid(cell));
    1439             :     }
    1440             : 
    1441             :     check_list_invariants(list1);
    1442        7940 :     return list1;
    1443             : }
    1444             : 
    1445             : /*
    1446             :  * Remove adjacent duplicates in a list of OIDs.
    1447             :  *
    1448             :  * It is caller's responsibility to have sorted the list to bring duplicates
    1449             :  * together, perhaps via list_sort(list, list_oid_cmp).
    1450             :  *
    1451             :  * Note that this takes time proportional to the length of the list.
    1452             :  */
    1453             : void
    1454         732 : list_deduplicate_oid(List *list)
    1455             : {
    1456             :     int         len;
    1457             : 
    1458             :     Assert(IsOidList(list));
    1459         732 :     len = list_length(list);
    1460         732 :     if (len > 1)
    1461             :     {
    1462         136 :         ListCell   *elements = list->elements;
    1463         136 :         int         i = 0;
    1464             : 
    1465         390 :         for (int j = 1; j < len; j++)
    1466             :         {
    1467         254 :             if (elements[i].oid_value != elements[j].oid_value)
    1468         224 :                 elements[++i].oid_value = elements[j].oid_value;
    1469             :         }
    1470         136 :         list->length = i + 1;
    1471             :     }
    1472             :     check_list_invariants(list);
    1473         732 : }
    1474             : 
    1475             : /*
    1476             :  * Free all storage in a list, and optionally the pointed-to elements
    1477             :  */
    1478             : static void
    1479    19668970 : list_free_private(List *list, bool deep)
    1480             : {
    1481    19668970 :     if (list == NIL)
    1482    14285016 :         return;                 /* nothing to do */
    1483             : 
    1484             :     check_list_invariants(list);
    1485             : 
    1486     5383954 :     if (deep)
    1487             :     {
    1488      163164 :         for (int i = 0; i < list->length; i++)
    1489      153062 :             pfree(lfirst(&list->elements[i]));
    1490             :     }
    1491     5383954 :     if (list->elements != list->initial_elements)
    1492       45880 :         pfree(list->elements);
    1493     5383954 :     pfree(list);
    1494             : }
    1495             : 
    1496             : /*
    1497             :  * Free all the cells of the list, as well as the list itself. Any
    1498             :  * objects that are pointed-to by the cells of the list are NOT
    1499             :  * free'd.
    1500             :  *
    1501             :  * On return, the argument to this function has been freed, so the
    1502             :  * caller would be wise to set it to NIL for safety's sake.
    1503             :  */
    1504             : void
    1505    18549136 : list_free(List *list)
    1506             : {
    1507    18549136 :     list_free_private(list, false);
    1508    18549136 : }
    1509             : 
    1510             : /*
    1511             :  * Free all the cells of the list, the list itself, and all the
    1512             :  * objects pointed-to by the cells of the list (each element in the
    1513             :  * list must contain a pointer to a palloc()'d region of memory!)
    1514             :  *
    1515             :  * On return, the argument to this function has been freed, so the
    1516             :  * caller would be wise to set it to NIL for safety's sake.
    1517             :  */
    1518             : void
    1519     1119834 : list_free_deep(List *list)
    1520             : {
    1521             :     /*
    1522             :      * A "deep" free operation only makes sense on a list of pointers.
    1523             :      */
    1524             :     Assert(IsPointerList(list));
    1525     1119834 :     list_free_private(list, true);
    1526     1119834 : }
    1527             : 
    1528             : /*
    1529             :  * Return a shallow copy of the specified list.
    1530             :  */
    1531             : List *
    1532     8278750 : list_copy(const List *oldlist)
    1533             : {
    1534             :     List       *newlist;
    1535             : 
    1536     8278750 :     if (oldlist == NIL)
    1537     1258788 :         return NIL;
    1538             : 
    1539     7019962 :     newlist = new_list(oldlist->type, oldlist->length);
    1540     7019962 :     memcpy(newlist->elements, oldlist->elements,
    1541     7019962 :            newlist->length * sizeof(ListCell));
    1542             : 
    1543             :     check_list_invariants(newlist);
    1544     7019962 :     return newlist;
    1545             : }
    1546             : 
    1547             : /*
    1548             :  * Return a shallow copy of the specified list, without the first N elements.
    1549             :  */
    1550             : List *
    1551      117106 : list_copy_tail(const List *oldlist, int nskip)
    1552             : {
    1553             :     List       *newlist;
    1554             : 
    1555      117106 :     if (nskip < 0)
    1556           0 :         nskip = 0;              /* would it be better to elog? */
    1557             : 
    1558      117106 :     if (oldlist == NIL || nskip >= oldlist->length)
    1559         978 :         return NIL;
    1560             : 
    1561      116128 :     newlist = new_list(oldlist->type, oldlist->length - nskip);
    1562      116128 :     memcpy(newlist->elements, &oldlist->elements[nskip],
    1563      116128 :            newlist->length * sizeof(ListCell));
    1564             : 
    1565             :     check_list_invariants(newlist);
    1566      116128 :     return newlist;
    1567             : }
    1568             : 
    1569             : /*
    1570             :  * Return a deep copy of the specified list.
    1571             :  *
    1572             :  * The list elements are copied via copyObject(), so that this function's
    1573             :  * idea of a "deep" copy is considerably deeper than what list_free_deep()
    1574             :  * means by the same word.
    1575             :  */
    1576             : List *
    1577    22132332 : list_copy_deep(const List *oldlist)
    1578             : {
    1579             :     List       *newlist;
    1580             : 
    1581    22132332 :     if (oldlist == NIL)
    1582           0 :         return NIL;
    1583             : 
    1584             :     /* This is only sensible for pointer Lists */
    1585             :     Assert(IsA(oldlist, List));
    1586             : 
    1587    22132332 :     newlist = new_list(oldlist->type, oldlist->length);
    1588    87328410 :     for (int i = 0; i < newlist->length; i++)
    1589    65196078 :         lfirst(&newlist->elements[i]) =
    1590    65196078 :             copyObjectImpl(lfirst(&oldlist->elements[i]));
    1591             : 
    1592             :     check_list_invariants(newlist);
    1593    22132332 :     return newlist;
    1594             : }
    1595             : 
    1596             : /*
    1597             :  * Sort a list according to the specified comparator function.
    1598             :  *
    1599             :  * The list is sorted in-place.
    1600             :  *
    1601             :  * The comparator function is declared to receive arguments of type
    1602             :  * const ListCell *; this allows it to use lfirst() and variants
    1603             :  * without casting its arguments.  Otherwise it behaves the same as
    1604             :  * the comparator function for standard qsort().
    1605             :  *
    1606             :  * Like qsort(), this provides no guarantees about sort stability
    1607             :  * for equal keys.
    1608             :  *
    1609             :  * This is based on qsort(), so it likewise has O(N log N) runtime.
    1610             :  */
    1611             : void
    1612      294706 : list_sort(List *list, list_sort_comparator cmp)
    1613             : {
    1614             :     typedef int (*qsort_comparator) (const void *a, const void *b);
    1615             :     int         len;
    1616             : 
    1617             :     check_list_invariants(list);
    1618             : 
    1619             :     /* Nothing to do if there's less than two elements */
    1620      294706 :     len = list_length(list);
    1621      294706 :     if (len > 1)
    1622      103182 :         qsort(list->elements, len, sizeof(ListCell), (qsort_comparator) cmp);
    1623      294706 : }
    1624             : 
    1625             : /*
    1626             :  * list_sort comparator for sorting a list into ascending int order.
    1627             :  */
    1628             : int
    1629          72 : list_int_cmp(const ListCell *p1, const ListCell *p2)
    1630             : {
    1631          72 :     int         v1 = lfirst_int(p1);
    1632          72 :     int         v2 = lfirst_int(p2);
    1633             : 
    1634          72 :     if (v1 < v2)
    1635          72 :         return -1;
    1636           0 :     if (v1 > v2)
    1637           0 :         return 1;
    1638           0 :     return 0;
    1639             : }
    1640             : 
    1641             : /*
    1642             :  * list_sort comparator for sorting a list into ascending OID order.
    1643             :  */
    1644             : int
    1645      126648 : list_oid_cmp(const ListCell *p1, const ListCell *p2)
    1646             : {
    1647      126648 :     Oid         v1 = lfirst_oid(p1);
    1648      126648 :     Oid         v2 = lfirst_oid(p2);
    1649             : 
    1650      126648 :     if (v1 < v2)
    1651      100314 :         return -1;
    1652       26334 :     if (v1 > v2)
    1653       26304 :         return 1;
    1654          30 :     return 0;
    1655             : }

Generated by: LCOV version 1.14