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

Generated by: LCOV version 1.13