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

Generated by: LCOV version 1.14