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

Generated by: LCOV version 1.14