LCOV - code coverage report
Current view: top level - src/backend/nodes - list.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13devel Lines: 325 378 86.0 %
Date: 2019-09-22 07:07:17 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-2019, 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 "utils/memutils.h"
      22             : 
      23             : 
      24             : /*
      25             :  * The previous List implementation, since it used a separate palloc chunk
      26             :  * for each cons cell, had the property that adding or deleting list cells
      27             :  * did not move the storage of other existing cells in the list.  Quite a
      28             :  * bit of existing code depended on that, by retaining ListCell pointers
      29             :  * across such operations on a list.  There is no such guarantee in this
      30             :  * implementation, so instead we have debugging support that is meant to
      31             :  * help flush out now-broken assumptions.  Defining DEBUG_LIST_MEMORY_USAGE
      32             :  * while building this file causes the List operations to forcibly move
      33             :  * all cells in a list whenever a cell is added or deleted.  In combination
      34             :  * with MEMORY_CONTEXT_CHECKING and/or Valgrind, this can usually expose
      35             :  * broken code.  It's a bit expensive though, as there's many more palloc
      36             :  * cycles and a lot more data-copying than in a default build.
      37             :  *
      38             :  * By default, we enable this when building for Valgrind.
      39             :  */
      40             : #ifdef USE_VALGRIND
      41             : #define DEBUG_LIST_MEMORY_USAGE
      42             : #endif
      43             : 
      44             : /* Overhead for the fixed part of a List header, measured in ListCells */
      45             : #define LIST_HEADER_OVERHEAD  \
      46             :     ((int) ((offsetof(List, initial_elements) - 1) / sizeof(ListCell) + 1))
      47             : 
      48             : /*
      49             :  * Macros to simplify writing assertions about the type of a list; a
      50             :  * NIL list is considered to be an empty list of any type.
      51             :  */
      52             : #define IsPointerList(l)        ((l) == NIL || IsA((l), List))
      53             : #define IsIntegerList(l)        ((l) == NIL || IsA((l), IntList))
      54             : #define IsOidList(l)            ((l) == NIL || IsA((l), OidList))
      55             : 
      56             : #ifdef USE_ASSERT_CHECKING
      57             : /*
      58             :  * Check that the specified List is valid (so far as we can tell).
      59             :  */
      60             : static void
      61             : check_list_invariants(const List *list)
      62             : {
      63             :     if (list == NIL)
      64             :         return;
      65             : 
      66             :     Assert(list->length > 0);
      67             :     Assert(list->length <= list->max_length);
      68             :     Assert(list->elements != NULL);
      69             : 
      70             :     Assert(list->type == T_List ||
      71             :            list->type == T_IntList ||
      72             :            list->type == T_OidList);
      73             : }
      74             : #else
      75             : #define check_list_invariants(l)  ((void) 0)
      76             : #endif                          /* USE_ASSERT_CHECKING */
      77             : 
      78             : /*
      79             :  * Return a freshly allocated List with room for at least min_size cells.
      80             :  *
      81             :  * Since empty non-NIL lists are invalid, new_list() sets the initial length
      82             :  * to min_size, effectively marking that number of cells as valid; the caller
      83             :  * is responsible for filling in their data.
      84             :  */
      85             : static List *
      86    67032324 : new_list(NodeTag type, int min_size)
      87             : {
      88             :     List       *newlist;
      89             :     int         max_size;
      90             : 
      91             :     Assert(min_size > 0);
      92             : 
      93             :     /*
      94             :      * We allocate all the requested cells, and possibly some more, as part of
      95             :      * the same palloc request as the List header.  This is a big win for the
      96             :      * typical case of short fixed-length lists.  It can lose if we allocate a
      97             :      * moderately long list and then it gets extended; we'll be wasting more
      98             :      * initial_elements[] space than if we'd made the header small.  However,
      99             :      * rounding up the request as we do in the normal code path provides some
     100             :      * defense against small extensions.
     101             :      */
     102             : 
     103             : #ifndef DEBUG_LIST_MEMORY_USAGE
     104             : 
     105             :     /*
     106             :      * Normally, we set up a list with some extra cells, to allow it to grow
     107             :      * without a repalloc.  Prefer cell counts chosen to make the total
     108             :      * allocation a power-of-2, since palloc would round it up to that anyway.
     109             :      * (That stops being true for very large allocations, but very long lists
     110             :      * are infrequent, so it doesn't seem worth special logic for such cases.)
     111             :      *
     112             :      * The minimum allocation is 8 ListCell units, providing either 4 or 5
     113             :      * available ListCells depending on the machine's word width.  Counting
     114             :      * palloc's overhead, this uses the same amount of space as a one-cell
     115             :      * list did in the old implementation, and less space for any longer list.
     116             :      *
     117             :      * We needn't worry about integer overflow; no caller passes min_size
     118             :      * that's more than twice the size of an existing list, so the size limits
     119             :      * within palloc will ensure that we don't overflow here.
     120             :      */
     121    67032324 :     max_size = 8;               /* semi-arbitrary small power of 2 */
     122   137541168 :     while (max_size < min_size + LIST_HEADER_OVERHEAD)
     123     3476520 :         max_size *= 2;
     124    67032324 :     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    67032324 :     newlist = (List *) palloc(offsetof(List, initial_elements) +
     135             :                               max_size * sizeof(ListCell));
     136    67032324 :     newlist->type = type;
     137    67032324 :     newlist->length = min_size;
     138    67032324 :     newlist->max_length = max_size;
     139    67032324 :     newlist->elements = newlist->initial_elements;
     140             : 
     141    67032324 :     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     4968982 : 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.  The existing max length might
     163             :      * not be a power of 2, so don't rely on that.
     164             :      */
     165     4968982 :     new_max_len = 16;           /* semi-arbitrary small power of 2 */
     166    12792736 :     while (new_max_len < min_size)
     167     2854772 :         new_max_len *= 2;
     168             : #else
     169             :     /* As above, don't allocate anything extra */
     170             :     new_max_len = min_size;
     171             : #endif
     172             : 
     173     4968982 :     if (list->elements == list->initial_elements)
     174             :     {
     175             :         List       *newlist PG_USED_FOR_ASSERTS_ONLY;
     176             : 
     177             :         /*
     178             :          * Replace original in-line allocation with a separate palloc block.
     179             :          * Ensure it is in the same memory context as the List header.  (The
     180             :          * previous List implementation did not offer any guarantees about
     181             :          * keeping all list cells in the same context, but it seems reasonable
     182             :          * to create such a guarantee now.)
     183             :          */
     184     3078624 :         list->elements = (ListCell *)
     185     3078624 :             MemoryContextAlloc(GetMemoryChunkContext(list),
     186             :                                new_max_len * sizeof(ListCell));
     187     3078624 :         memcpy(list->elements, list->initial_elements,
     188     3078624 :                list->length * sizeof(ListCell));
     189             : 
     190             :         /*
     191             :          * Currently, asking aset.c to reduce the allocated size of the List
     192             :          * header is pointless in terms of reclaiming space, unless the list
     193             :          * is very long.  However, it seems worth doing anyway to cause the
     194             :          * no-longer-needed initial_elements[] space to be cleared in
     195             :          * debugging builds.
     196             :          */
     197     3078624 :         newlist = (List *) repalloc(list, offsetof(List, initial_elements));
     198             : 
     199             :         /* That better not have failed, nor moved the list header */
     200             :         Assert(newlist == list);
     201             :     }
     202             :     else
     203             :     {
     204             : #ifndef DEBUG_LIST_MEMORY_USAGE
     205             :         /* Normally, let repalloc deal with enlargement */
     206     1890358 :         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     4968982 :     list->max_length = new_max_len;
     226     4968982 : }
     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     9026468 : list_make1_impl(NodeTag t, ListCell datum1)
     234             : {
     235     9026468 :     List       *list = new_list(t, 1);
     236             : 
     237     9026468 :     list->elements[0] = datum1;
     238             :     check_list_invariants(list);
     239     9026468 :     return list;
     240             : }
     241             : 
     242             : List *
     243     1191746 : list_make2_impl(NodeTag t, ListCell datum1, ListCell datum2)
     244             : {
     245     1191746 :     List       *list = new_list(t, 2);
     246             : 
     247     1191746 :     list->elements[0] = datum1;
     248     1191746 :     list->elements[1] = datum2;
     249             :     check_list_invariants(list);
     250     1191746 :     return list;
     251             : }
     252             : 
     253             : List *
     254        4698 : list_make3_impl(NodeTag t, ListCell datum1, ListCell datum2,
     255             :                 ListCell datum3)
     256             : {
     257        4698 :     List       *list = new_list(t, 3);
     258             : 
     259        4698 :     list->elements[0] = datum1;
     260        4698 :     list->elements[1] = datum2;
     261        4698 :     list->elements[2] = datum3;
     262             :     check_list_invariants(list);
     263        4698 :     return list;
     264             : }
     265             : 
     266             : List *
     267         374 : list_make4_impl(NodeTag t, ListCell datum1, ListCell datum2,
     268             :                 ListCell datum3, ListCell datum4)
     269             : {
     270         374 :     List       *list = new_list(t, 4);
     271             : 
     272         374 :     list->elements[0] = datum1;
     273         374 :     list->elements[1] = datum2;
     274         374 :     list->elements[2] = datum3;
     275         374 :     list->elements[3] = datum4;
     276             :     check_list_invariants(list);
     277         374 :     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     2306586 : new_head_cell(List *list)
     288             : {
     289             :     /* Enlarge array if necessary */
     290     2306586 :     if (list->length >= list->max_length)
     291       40454 :         enlarge_list(list, list->length + 1);
     292             :     /* Now shove the existing data over */
     293     2306586 :     memmove(&list->elements[1], &list->elements[0],
     294     2306586 :             list->length * sizeof(ListCell));
     295     2306586 :     list->length++;
     296     2306586 : }
     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    72000588 : new_tail_cell(List *list)
     306             : {
     307             :     /* Enlarge array if necessary */
     308    72000588 :     if (list->length >= list->max_length)
     309     4816302 :         enlarge_list(list, list->length + 1);
     310    72000588 :     list->length++;
     311    72000588 : }
     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    97083676 : lappend(List *list, void *datum)
     322             : {
     323             :     Assert(IsPointerList(list));
     324             : 
     325    97083676 :     if (list == NIL)
     326    26752518 :         list = new_list(T_List, 1);
     327             :     else
     328    70331158 :         new_tail_cell(list);
     329             : 
     330    97083676 :     lfirst(list_tail(list)) = datum;
     331             :     check_list_invariants(list);
     332    97083676 :     return list;
     333             : }
     334             : 
     335             : /*
     336             :  * Append an integer to the specified list. See lappend()
     337             :  */
     338             : List *
     339     1228400 : lappend_int(List *list, int datum)
     340             : {
     341             :     Assert(IsIntegerList(list));
     342             : 
     343     1228400 :     if (list == NIL)
     344      707298 :         list = new_list(T_IntList, 1);
     345             :     else
     346      521102 :         new_tail_cell(list);
     347             : 
     348     1228400 :     lfirst_int(list_tail(list)) = datum;
     349             :     check_list_invariants(list);
     350     1228400 :     return list;
     351             : }
     352             : 
     353             : /*
     354             :  * Append an OID to the specified list. See lappend()
     355             :  */
     356             : List *
     357     3308518 : lappend_oid(List *list, Oid datum)
     358             : {
     359             :     Assert(IsOidList(list));
     360             : 
     361     3308518 :     if (list == NIL)
     362     2160190 :         list = new_list(T_OidList, 1);
     363             :     else
     364     1148328 :         new_tail_cell(list);
     365             : 
     366     3308518 :     lfirst_oid(list_tail(list)) = datum;
     367             :     check_list_invariants(list);
     368     3308518 :     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      303584 : insert_new_cell(List *list, int pos)
     380             : {
     381             :     Assert(pos >= 0 && pos <= list->length);
     382             : 
     383             :     /* Enlarge array if necessary */
     384      303584 :     if (list->length >= list->max_length)
     385         264 :         enlarge_list(list, list->length + 1);
     386             :     /* Now shove the existing data over */
     387      303584 :     if (pos < list->length)
     388      153158 :         memmove(&list->elements[pos + 1], &list->elements[pos],
     389      153158 :                 (list->length - pos) * sizeof(ListCell));
     390      303584 :     list->length++;
     391             : 
     392      303584 :     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     1350536 : list_insert_nth(List *list, int pos, void *datum)
     401             : {
     402     1350536 :     if (list == NIL)
     403             :     {
     404             :         Assert(pos == 0);
     405     1046952 :         return list_make1(datum);
     406             :     }
     407             :     Assert(IsPointerList(list));
     408      303584 :     lfirst(insert_new_cell(list, pos)) = datum;
     409             :     check_list_invariants(list);
     410      303584 :     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     4821142 : lcons(void *datum, List *list)
     454             : {
     455             :     Assert(IsPointerList(list));
     456             : 
     457     4821142 :     if (list == NIL)
     458     2531816 :         list = new_list(T_List, 1);
     459             :     else
     460     2289326 :         new_head_cell(list);
     461             : 
     462     4821142 :     lfirst(list_head(list)) = datum;
     463             :     check_list_invariants(list);
     464     4821142 :     return list;
     465             : }
     466             : 
     467             : /*
     468             :  * Prepend an integer to the list. See lcons()
     469             :  */
     470             : List *
     471        5508 : lcons_int(int datum, List *list)
     472             : {
     473             :     Assert(IsIntegerList(list));
     474             : 
     475        5508 :     if (list == NIL)
     476        3144 :         list = new_list(T_IntList, 1);
     477             :     else
     478        2364 :         new_head_cell(list);
     479             : 
     480        5508 :     lfirst_int(list_head(list)) = datum;
     481             :     check_list_invariants(list);
     482        5508 :     return list;
     483             : }
     484             : 
     485             : /*
     486             :  * Prepend an OID to the list. See lcons()
     487             :  */
     488             : List *
     489       16182 : lcons_oid(Oid datum, List *list)
     490             : {
     491             :     Assert(IsOidList(list));
     492             : 
     493       16182 :     if (list == NIL)
     494        1286 :         list = new_list(T_OidList, 1);
     495             :     else
     496       14896 :         new_head_cell(list);
     497             : 
     498       16182 :     lfirst_oid(list_head(list)) = datum;
     499             :     check_list_invariants(list);
     500       16182 :     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     3750578 : list_concat(List *list1, const List *list2)
     516             : {
     517             :     int         new_len;
     518             : 
     519     3750578 :     if (list1 == NIL)
     520     2490932 :         return list_copy(list2);
     521     1259646 :     if (list2 == NIL)
     522      645492 :         return list1;
     523             : 
     524             :     Assert(list1->type == list2->type);
     525             : 
     526      614154 :     new_len = list1->length + list2->length;
     527             :     /* Enlarge array if necessary */
     528      614154 :     if (new_len > list1->max_length)
     529      111962 :         enlarge_list(list1, new_len);
     530             : 
     531             :     /* Even if list1 == list2, using memcpy should be safe here */
     532      614154 :     memcpy(&list1->elements[list1->length], &list2->elements[0],
     533      614154 :            list2->length * sizeof(ListCell));
     534      614154 :     list1->length = new_len;
     535             : 
     536             :     check_list_invariants(list1);
     537      614154 :     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      553612 : list_concat_copy(const List *list1, const List *list2)
     553             : {
     554             :     List       *result;
     555             :     int         new_len;
     556             : 
     557      553612 :     if (list1 == NIL)
     558      242332 :         return list_copy(list2);
     559      311280 :     if (list2 == NIL)
     560      271830 :         return list_copy(list1);
     561             : 
     562             :     Assert(list1->type == list2->type);
     563             : 
     564       39450 :     new_len = list1->length + list2->length;
     565       39450 :     result = new_list(list1->type, new_len);
     566       39450 :     memcpy(result->elements, list1->elements,
     567       39450 :            list1->length * sizeof(ListCell));
     568       39450 :     memcpy(result->elements + list1->length, list2->elements,
     569       39450 :            list2->length * sizeof(ListCell));
     570             : 
     571             :     check_list_invariants(result);
     572       39450 :     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      287292 : list_truncate(List *list, int new_size)
     586             : {
     587      287292 :     if (new_size <= 0)
     588       75460 :         return NIL;             /* truncate to zero length */
     589             : 
     590             :     /* If asked to effectively extend the list, do nothing */
     591      211832 :     if (new_size < list_length(list))
     592       44388 :         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      211832 :     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      124138 : 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      160526 :     foreach(cell, list)
     621             :     {
     622       91122 :         if (equal(lfirst(cell), datum))
     623       54734 :             return true;
     624             :     }
     625             : 
     626       69404 :     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      291268 : 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      419890 :     foreach(cell, list)
     642             :     {
     643      242458 :         if (lfirst(cell) == datum)
     644      113836 :             return true;
     645             :     }
     646             : 
     647      177432 :     return false;
     648             : }
     649             : 
     650             : /*
     651             :  * Return true iff the integer 'datum' is a member of the list.
     652             :  */
     653             : bool
     654       90276 : 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     4988888 :     foreach(cell, list)
     662             :     {
     663     4915714 :         if (lfirst_int(cell) == datum)
     664       17102 :             return true;
     665             :     }
     666             : 
     667       73174 :     return false;
     668             : }
     669             : 
     670             : /*
     671             :  * Return true iff the OID 'datum' is a member of the list.
     672             :  */
     673             : bool
     674    24922384 : 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    26144450 :     foreach(cell, list)
     682             :     {
     683     1723608 :         if (lfirst_oid(cell) == datum)
     684      501542 :             return true;
     685             :     }
     686             : 
     687    24420842 :     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     1740324 : 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     1740324 :     if (list->length == 1)
     708             :     {
     709      929910 :         list_free(list);
     710      929910 :         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      810414 :     memmove(&list->elements[n], &list->elements[n + 1],
     721      810414 :             (list->length - 1 - n) * sizeof(ListCell));
     722      810414 :     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(), tell palloc code we're not using the
     740             :              * initial_elements space anymore.
     741             :              */
     742             :             List       *newlist PG_USED_FOR_ASSERTS_ONLY;
     743             : 
     744             :             newlist = (List *) repalloc(list, offsetof(List, initial_elements));
     745             :             Assert(newlist == list);
     746             :         }
     747             :         list->elements = newelems;
     748             :         list->max_length = newmaxlen;
     749             :         list->length--;
     750             :         check_list_invariants(list);
     751             :     }
     752             : #endif
     753             : 
     754      810414 :     return list;
     755             : }
     756             : 
     757             : /*
     758             :  * Delete 'cell' from 'list'.
     759             :  *
     760             :  * The List is pfree'd if this was the last member.  However, we do not
     761             :  * touch any data the cell might've been pointing to.
     762             :  */
     763             : List *
     764     1335242 : list_delete_cell(List *list, ListCell *cell)
     765             : {
     766     1335242 :     return list_delete_nth_cell(list, cell - list->elements);
     767             : }
     768             : 
     769             : /*
     770             :  * Delete the first cell in list that matches datum, if any.
     771             :  * Equality is determined via equal().
     772             :  */
     773             : List *
     774           8 : list_delete(List *list, void *datum)
     775             : {
     776             :     ListCell   *cell;
     777             : 
     778             :     Assert(IsPointerList(list));
     779             :     check_list_invariants(list);
     780             : 
     781           8 :     foreach(cell, list)
     782             :     {
     783           4 :         if (equal(lfirst(cell), datum))
     784           4 :             return list_delete_cell(list, cell);
     785             :     }
     786             : 
     787             :     /* Didn't find a match: return the list unmodified */
     788           4 :     return list;
     789             : }
     790             : 
     791             : /* As above, but use simple pointer equality */
     792             : List *
     793     1011004 : list_delete_ptr(List *list, void *datum)
     794             : {
     795             :     ListCell   *cell;
     796             : 
     797             :     Assert(IsPointerList(list));
     798             :     check_list_invariants(list);
     799             : 
     800     1024802 :     foreach(cell, list)
     801             :     {
     802     1024802 :         if (lfirst(cell) == datum)
     803     1011004 :             return list_delete_cell(list, cell);
     804             :     }
     805             : 
     806             :     /* Didn't find a match: return the list unmodified */
     807           0 :     return list;
     808             : }
     809             : 
     810             : /* As above, but for integers */
     811             : List *
     812          56 : list_delete_int(List *list, int datum)
     813             : {
     814             :     ListCell   *cell;
     815             : 
     816             :     Assert(IsIntegerList(list));
     817             :     check_list_invariants(list);
     818             : 
     819          60 :     foreach(cell, list)
     820             :     {
     821          60 :         if (lfirst_int(cell) == datum)
     822          56 :             return list_delete_cell(list, cell);
     823             :     }
     824             : 
     825             :     /* Didn't find a match: return the list unmodified */
     826           0 :     return list;
     827             : }
     828             : 
     829             : /* As above, but for OIDs */
     830             : List *
     831        6804 : list_delete_oid(List *list, Oid datum)
     832             : {
     833             :     ListCell   *cell;
     834             : 
     835             :     Assert(IsOidList(list));
     836             :     check_list_invariants(list);
     837             : 
     838        6804 :     foreach(cell, list)
     839             :     {
     840         846 :         if (lfirst_oid(cell) == datum)
     841         846 :             return list_delete_cell(list, cell);
     842             :     }
     843             : 
     844             :     /* Didn't find a match: return the list unmodified */
     845        5958 :     return list;
     846             : }
     847             : 
     848             : /*
     849             :  * Delete the first element of the list.
     850             :  *
     851             :  * This is useful to replace the Lisp-y code "list = lnext(list);" in cases
     852             :  * where the intent is to alter the list rather than just traverse it.
     853             :  * Beware that the list is modified, whereas the Lisp-y coding leaves
     854             :  * the original list head intact in case there's another pointer to it.
     855             :  */
     856             : List *
     857      405060 : list_delete_first(List *list)
     858             : {
     859             :     check_list_invariants(list);
     860             : 
     861      405060 :     if (list == NIL)
     862           0 :         return NIL;             /* would an error be better? */
     863             : 
     864      405060 :     return list_delete_nth_cell(list, 0);
     865             : }
     866             : 
     867             : /*
     868             :  * Delete the last element of the list.
     869             :  *
     870             :  * This is the opposite of list_delete_first(), but is noticeably cheaper
     871             :  * with a long list, since no data need be moved.
     872             :  */
     873             : List *
     874       23536 : list_delete_last(List *list)
     875             : {
     876             :     check_list_invariants(list);
     877             : 
     878       23536 :     if (list == NIL)
     879           0 :         return NIL;             /* would an error be better? */
     880             : 
     881             :     /* list_truncate won't free list if it goes to empty, but this should */
     882       23536 :     if (list_length(list) <= 1)
     883             :     {
     884       22626 :         list_free(list);
     885       22626 :         return NIL;
     886             :     }
     887             : 
     888         910 :     return list_truncate(list, list_length(list) - 1);
     889             : }
     890             : 
     891             : /*
     892             :  * Generate the union of two lists. This is calculated by copying
     893             :  * list1 via list_copy(), then adding to it all the members of list2
     894             :  * that aren't already in list1.
     895             :  *
     896             :  * Whether an element is already a member of the list is determined
     897             :  * via equal().
     898             :  *
     899             :  * The returned list is newly-allocated, although the content of the
     900             :  * cells is the same (i.e. any pointed-to objects are not copied).
     901             :  *
     902             :  * NB: this function will NOT remove any duplicates that are present
     903             :  * in list1 (so it only performs a "union" if list1 is known unique to
     904             :  * start with).  Also, if you are about to write "x = list_union(x, y)"
     905             :  * you probably want to use list_concat_unique() instead to avoid wasting
     906             :  * the storage of the old x list.
     907             :  *
     908             :  * This function could probably be implemented a lot faster if it is a
     909             :  * performance bottleneck.
     910             :  */
     911             : List *
     912        5488 : list_union(const List *list1, const List *list2)
     913             : {
     914             :     List       *result;
     915             :     const ListCell *cell;
     916             : 
     917             :     Assert(IsPointerList(list1));
     918             :     Assert(IsPointerList(list2));
     919             : 
     920        5488 :     result = list_copy(list1);
     921       11146 :     foreach(cell, list2)
     922             :     {
     923        5658 :         if (!list_member(result, lfirst(cell)))
     924        5606 :             result = lappend(result, lfirst(cell));
     925             :     }
     926             : 
     927             :     check_list_invariants(result);
     928        5488 :     return result;
     929             : }
     930             : 
     931             : /*
     932             :  * This variant of list_union() determines duplicates via simple
     933             :  * pointer comparison.
     934             :  */
     935             : List *
     936           0 : list_union_ptr(const List *list1, const List *list2)
     937             : {
     938             :     List       *result;
     939             :     const ListCell *cell;
     940             : 
     941             :     Assert(IsPointerList(list1));
     942             :     Assert(IsPointerList(list2));
     943             : 
     944           0 :     result = list_copy(list1);
     945           0 :     foreach(cell, list2)
     946             :     {
     947           0 :         if (!list_member_ptr(result, lfirst(cell)))
     948           0 :             result = lappend(result, lfirst(cell));
     949             :     }
     950             : 
     951             :     check_list_invariants(result);
     952           0 :     return result;
     953             : }
     954             : 
     955             : /*
     956             :  * This variant of list_union() operates upon lists of integers.
     957             :  */
     958             : List *
     959        2748 : list_union_int(const List *list1, const List *list2)
     960             : {
     961             :     List       *result;
     962             :     const ListCell *cell;
     963             : 
     964             :     Assert(IsIntegerList(list1));
     965             :     Assert(IsIntegerList(list2));
     966             : 
     967        2748 :     result = list_copy(list1);
     968        5500 :     foreach(cell, list2)
     969             :     {
     970        2752 :         if (!list_member_int(result, lfirst_int(cell)))
     971        2744 :             result = lappend_int(result, lfirst_int(cell));
     972             :     }
     973             : 
     974             :     check_list_invariants(result);
     975        2748 :     return result;
     976             : }
     977             : 
     978             : /*
     979             :  * This variant of list_union() operates upon lists of OIDs.
     980             :  */
     981             : List *
     982           0 : list_union_oid(const List *list1, const List *list2)
     983             : {
     984             :     List       *result;
     985             :     const ListCell *cell;
     986             : 
     987             :     Assert(IsOidList(list1));
     988             :     Assert(IsOidList(list2));
     989             : 
     990           0 :     result = list_copy(list1);
     991           0 :     foreach(cell, list2)
     992             :     {
     993           0 :         if (!list_member_oid(result, lfirst_oid(cell)))
     994           0 :             result = lappend_oid(result, lfirst_oid(cell));
     995             :     }
     996             : 
     997             :     check_list_invariants(result);
     998           0 :     return result;
     999             : }
    1000             : 
    1001             : /*
    1002             :  * Return a list that contains all the cells that are in both list1 and
    1003             :  * list2.  The returned list is freshly allocated via palloc(), but the
    1004             :  * cells themselves point to the same objects as the cells of the
    1005             :  * input lists.
    1006             :  *
    1007             :  * Duplicate entries in list1 will not be suppressed, so it's only a true
    1008             :  * "intersection" if list1 is known unique beforehand.
    1009             :  *
    1010             :  * This variant works on lists of pointers, and determines list
    1011             :  * membership via equal().  Note that the list1 member will be pointed
    1012             :  * to in the result.
    1013             :  */
    1014             : List *
    1015       36136 : list_intersection(const List *list1, const List *list2)
    1016             : {
    1017             :     List       *result;
    1018             :     const ListCell *cell;
    1019             : 
    1020       36136 :     if (list1 == NIL || list2 == NIL)
    1021       33674 :         return NIL;
    1022             : 
    1023             :     Assert(IsPointerList(list1));
    1024             :     Assert(IsPointerList(list2));
    1025             : 
    1026        2462 :     result = NIL;
    1027        5946 :     foreach(cell, list1)
    1028             :     {
    1029        3484 :         if (list_member(list2, lfirst(cell)))
    1030         668 :             result = lappend(result, lfirst(cell));
    1031             :     }
    1032             : 
    1033             :     check_list_invariants(result);
    1034        2462 :     return result;
    1035             : }
    1036             : 
    1037             : /*
    1038             :  * As list_intersection but operates on lists of integers.
    1039             :  */
    1040             : List *
    1041         192 : list_intersection_int(const List *list1, const List *list2)
    1042             : {
    1043             :     List       *result;
    1044             :     const ListCell *cell;
    1045             : 
    1046         192 :     if (list1 == NIL || list2 == NIL)
    1047           0 :         return NIL;
    1048             : 
    1049             :     Assert(IsIntegerList(list1));
    1050             :     Assert(IsIntegerList(list2));
    1051             : 
    1052         192 :     result = NIL;
    1053         416 :     foreach(cell, list1)
    1054             :     {
    1055         224 :         if (list_member_int(list2, lfirst_int(cell)))
    1056         108 :             result = lappend_int(result, lfirst_int(cell));
    1057             :     }
    1058             : 
    1059             :     check_list_invariants(result);
    1060         192 :     return result;
    1061             : }
    1062             : 
    1063             : /*
    1064             :  * Return a list that contains all the cells in list1 that are not in
    1065             :  * list2. The returned list is freshly allocated via palloc(), but the
    1066             :  * cells themselves point to the same objects as the cells of the
    1067             :  * input lists.
    1068             :  *
    1069             :  * This variant works on lists of pointers, and determines list
    1070             :  * membership via equal()
    1071             :  */
    1072             : List *
    1073       29308 : list_difference(const List *list1, const List *list2)
    1074             : {
    1075             :     const ListCell *cell;
    1076       29308 :     List       *result = NIL;
    1077             : 
    1078             :     Assert(IsPointerList(list1));
    1079             :     Assert(IsPointerList(list2));
    1080             : 
    1081       29308 :     if (list2 == NIL)
    1082         722 :         return list_copy(list1);
    1083             : 
    1084       59636 :     foreach(cell, list1)
    1085             :     {
    1086       31050 :         if (!list_member(list2, lfirst(cell)))
    1087         972 :             result = lappend(result, lfirst(cell));
    1088             :     }
    1089             : 
    1090             :     check_list_invariants(result);
    1091       28586 :     return result;
    1092             : }
    1093             : 
    1094             : /*
    1095             :  * This variant of list_difference() determines list membership via
    1096             :  * simple pointer equality.
    1097             :  */
    1098             : List *
    1099       19824 : list_difference_ptr(const List *list1, const List *list2)
    1100             : {
    1101             :     const ListCell *cell;
    1102       19824 :     List       *result = NIL;
    1103             : 
    1104             :     Assert(IsPointerList(list1));
    1105             :     Assert(IsPointerList(list2));
    1106             : 
    1107       19824 :     if (list2 == NIL)
    1108       18284 :         return list_copy(list1);
    1109             : 
    1110        4468 :     foreach(cell, list1)
    1111             :     {
    1112        2928 :         if (!list_member_ptr(list2, lfirst(cell)))
    1113        1052 :             result = lappend(result, lfirst(cell));
    1114             :     }
    1115             : 
    1116             :     check_list_invariants(result);
    1117        1540 :     return result;
    1118             : }
    1119             : 
    1120             : /*
    1121             :  * This variant of list_difference() operates upon lists of integers.
    1122             :  */
    1123             : List *
    1124        1284 : list_difference_int(const List *list1, const List *list2)
    1125             : {
    1126             :     const ListCell *cell;
    1127        1284 :     List       *result = NIL;
    1128             : 
    1129             :     Assert(IsIntegerList(list1));
    1130             :     Assert(IsIntegerList(list2));
    1131             : 
    1132        1284 :     if (list2 == NIL)
    1133        1000 :         return list_copy(list1);
    1134             : 
    1135         828 :     foreach(cell, list1)
    1136             :     {
    1137         544 :         if (!list_member_int(list2, lfirst_int(cell)))
    1138         236 :             result = lappend_int(result, lfirst_int(cell));
    1139             :     }
    1140             : 
    1141             :     check_list_invariants(result);
    1142         284 :     return result;
    1143             : }
    1144             : 
    1145             : /*
    1146             :  * This variant of list_difference() operates upon lists of OIDs.
    1147             :  */
    1148             : List *
    1149           0 : list_difference_oid(const List *list1, const List *list2)
    1150             : {
    1151             :     const ListCell *cell;
    1152           0 :     List       *result = NIL;
    1153             : 
    1154             :     Assert(IsOidList(list1));
    1155             :     Assert(IsOidList(list2));
    1156             : 
    1157           0 :     if (list2 == NIL)
    1158           0 :         return list_copy(list1);
    1159             : 
    1160           0 :     foreach(cell, list1)
    1161             :     {
    1162           0 :         if (!list_member_oid(list2, lfirst_oid(cell)))
    1163           0 :             result = lappend_oid(result, lfirst_oid(cell));
    1164             :     }
    1165             : 
    1166             :     check_list_invariants(result);
    1167           0 :     return result;
    1168             : }
    1169             : 
    1170             : /*
    1171             :  * Append datum to list, but only if it isn't already in the list.
    1172             :  *
    1173             :  * Whether an element is already a member of the list is determined
    1174             :  * via equal().
    1175             :  */
    1176             : List *
    1177        2306 : list_append_unique(List *list, void *datum)
    1178             : {
    1179        2306 :     if (list_member(list, datum))
    1180         340 :         return list;
    1181             :     else
    1182        1966 :         return lappend(list, datum);
    1183             : }
    1184             : 
    1185             : /*
    1186             :  * This variant of list_append_unique() determines list membership via
    1187             :  * simple pointer equality.
    1188             :  */
    1189             : List *
    1190      285286 : list_append_unique_ptr(List *list, void *datum)
    1191             : {
    1192      285286 :     if (list_member_ptr(list, datum))
    1193      109342 :         return list;
    1194             :     else
    1195      175944 :         return lappend(list, datum);
    1196             : }
    1197             : 
    1198             : /*
    1199             :  * This variant of list_append_unique() operates upon lists of integers.
    1200             :  */
    1201             : List *
    1202           0 : list_append_unique_int(List *list, int datum)
    1203             : {
    1204           0 :     if (list_member_int(list, datum))
    1205           0 :         return list;
    1206             :     else
    1207           0 :         return lappend_int(list, datum);
    1208             : }
    1209             : 
    1210             : /*
    1211             :  * This variant of list_append_unique() operates upon lists of OIDs.
    1212             :  */
    1213             : List *
    1214        3136 : list_append_unique_oid(List *list, Oid datum)
    1215             : {
    1216        3136 :     if (list_member_oid(list, datum))
    1217        1632 :         return list;
    1218             :     else
    1219        1504 :         return lappend_oid(list, datum);
    1220             : }
    1221             : 
    1222             : /*
    1223             :  * Append to list1 each member of list2 that isn't already in list1.
    1224             :  *
    1225             :  * Whether an element is already a member of the list is determined
    1226             :  * via equal().
    1227             :  *
    1228             :  * This is almost the same functionality as list_union(), but list1 is
    1229             :  * modified in-place rather than being copied. However, callers of this
    1230             :  * function may have strict ordering expectations -- i.e. that the relative
    1231             :  * order of those list2 elements that are not duplicates is preserved.
    1232             :  */
    1233             : List *
    1234        1324 : list_concat_unique(List *list1, const List *list2)
    1235             : {
    1236             :     ListCell   *cell;
    1237             : 
    1238             :     Assert(IsPointerList(list1));
    1239             :     Assert(IsPointerList(list2));
    1240             : 
    1241        2544 :     foreach(cell, list2)
    1242             :     {
    1243        1220 :         if (!list_member(list1, lfirst(cell)))
    1244        1204 :             list1 = lappend(list1, lfirst(cell));
    1245             :     }
    1246             : 
    1247             :     check_list_invariants(list1);
    1248        1324 :     return list1;
    1249             : }
    1250             : 
    1251             : /*
    1252             :  * This variant of list_concat_unique() determines list membership via
    1253             :  * simple pointer equality.
    1254             :  */
    1255             : List *
    1256           0 : list_concat_unique_ptr(List *list1, const List *list2)
    1257             : {
    1258             :     ListCell   *cell;
    1259             : 
    1260             :     Assert(IsPointerList(list1));
    1261             :     Assert(IsPointerList(list2));
    1262             : 
    1263           0 :     foreach(cell, list2)
    1264             :     {
    1265           0 :         if (!list_member_ptr(list1, lfirst(cell)))
    1266           0 :             list1 = lappend(list1, lfirst(cell));
    1267             :     }
    1268             : 
    1269             :     check_list_invariants(list1);
    1270           0 :     return list1;
    1271             : }
    1272             : 
    1273             : /*
    1274             :  * This variant of list_concat_unique() operates upon lists of integers.
    1275             :  */
    1276             : List *
    1277           0 : list_concat_unique_int(List *list1, const List *list2)
    1278             : {
    1279             :     ListCell   *cell;
    1280             : 
    1281             :     Assert(IsIntegerList(list1));
    1282             :     Assert(IsIntegerList(list2));
    1283             : 
    1284           0 :     foreach(cell, list2)
    1285             :     {
    1286           0 :         if (!list_member_int(list1, lfirst_int(cell)))
    1287           0 :             list1 = lappend_int(list1, lfirst_int(cell));
    1288             :     }
    1289             : 
    1290             :     check_list_invariants(list1);
    1291           0 :     return list1;
    1292             : }
    1293             : 
    1294             : /*
    1295             :  * This variant of list_concat_unique() operates upon lists of OIDs.
    1296             :  */
    1297             : List *
    1298        2330 : list_concat_unique_oid(List *list1, const List *list2)
    1299             : {
    1300             :     ListCell   *cell;
    1301             : 
    1302             :     Assert(IsOidList(list1));
    1303             :     Assert(IsOidList(list2));
    1304             : 
    1305        2330 :     foreach(cell, list2)
    1306             :     {
    1307           0 :         if (!list_member_oid(list1, lfirst_oid(cell)))
    1308           0 :             list1 = lappend_oid(list1, lfirst_oid(cell));
    1309             :     }
    1310             : 
    1311             :     check_list_invariants(list1);
    1312        2330 :     return list1;
    1313             : }
    1314             : 
    1315             : /*
    1316             :  * Remove adjacent duplicates in a list of OIDs.
    1317             :  *
    1318             :  * It is caller's responsibility to have sorted the list to bring duplicates
    1319             :  * together, perhaps via list_sort(list, list_oid_cmp).
    1320             :  */
    1321             : void
    1322         484 : list_deduplicate_oid(List *list)
    1323             : {
    1324             :     int         len;
    1325             : 
    1326             :     Assert(IsOidList(list));
    1327         484 :     len = list_length(list);
    1328         484 :     if (len > 1)
    1329             :     {
    1330          96 :         ListCell   *elements = list->elements;
    1331          96 :         int         i = 0;
    1332             : 
    1333         264 :         for (int j = 1; j < len; j++)
    1334             :         {
    1335         168 :             if (elements[i].oid_value != elements[j].oid_value)
    1336         160 :                 elements[++i].oid_value = elements[j].oid_value;
    1337             :         }
    1338          96 :         list->length = i + 1;
    1339             :     }
    1340             :     check_list_invariants(list);
    1341         484 : }
    1342             : 
    1343             : /*
    1344             :  * Free all storage in a list, and optionally the pointed-to elements
    1345             :  */
    1346             : static void
    1347    17446124 : list_free_private(List *list, bool deep)
    1348             : {
    1349    17446124 :     if (list == NIL)
    1350    13573498 :         return;                 /* nothing to do */
    1351             : 
    1352             :     check_list_invariants(list);
    1353             : 
    1354     3872626 :     if (deep)
    1355             :     {
    1356       10732 :         for (int i = 0; i < list->length; i++)
    1357        6066 :             pfree(lfirst(&list->elements[i]));
    1358             :     }
    1359     3872626 :     if (list->elements != list->initial_elements)
    1360       56862 :         pfree(list->elements);
    1361     3872626 :     pfree(list);
    1362             : }
    1363             : 
    1364             : /*
    1365             :  * Free all the cells of the list, as well as the list itself. Any
    1366             :  * objects that are pointed-to by the cells of the list are NOT
    1367             :  * free'd.
    1368             :  *
    1369             :  * On return, the argument to this function has been freed, so the
    1370             :  * caller would be wise to set it to NIL for safety's sake.
    1371             :  */
    1372             : void
    1373    16682256 : list_free(List *list)
    1374             : {
    1375    16682256 :     list_free_private(list, false);
    1376    16682256 : }
    1377             : 
    1378             : /*
    1379             :  * Free all the cells of the list, the list itself, and all the
    1380             :  * objects pointed-to by the cells of the list (each element in the
    1381             :  * list must contain a pointer to a palloc()'d region of memory!)
    1382             :  *
    1383             :  * On return, the argument to this function has been freed, so the
    1384             :  * caller would be wise to set it to NIL for safety's sake.
    1385             :  */
    1386             : void
    1387      763868 : list_free_deep(List *list)
    1388             : {
    1389             :     /*
    1390             :      * A "deep" free operation only makes sense on a list of pointers.
    1391             :      */
    1392             :     Assert(IsPointerList(list));
    1393      763868 :     list_free_private(list, true);
    1394      763868 : }
    1395             : 
    1396             : /*
    1397             :  * Return a shallow copy of the specified list.
    1398             :  */
    1399             : List *
    1400     6667972 : list_copy(const List *oldlist)
    1401             : {
    1402             :     List       *newlist;
    1403             : 
    1404     6667972 :     if (oldlist == NIL)
    1405     1106546 :         return NIL;
    1406             : 
    1407     5561426 :     newlist = new_list(oldlist->type, oldlist->length);
    1408     5561426 :     memcpy(newlist->elements, oldlist->elements,
    1409     5561426 :            newlist->length * sizeof(ListCell));
    1410             : 
    1411             :     check_list_invariants(newlist);
    1412     5561426 :     return newlist;
    1413             : }
    1414             : 
    1415             : /*
    1416             :  * Return a shallow copy of the specified list, without the first N elements.
    1417             :  */
    1418             : List *
    1419      179086 : list_copy_tail(const List *oldlist, int nskip)
    1420             : {
    1421             :     List       *newlist;
    1422             : 
    1423      179086 :     if (nskip < 0)
    1424           0 :         nskip = 0;              /* would it be better to elog? */
    1425             : 
    1426      179086 :     if (oldlist == NIL || nskip >= oldlist->length)
    1427         858 :         return NIL;
    1428             : 
    1429      178228 :     newlist = new_list(oldlist->type, oldlist->length - nskip);
    1430      178228 :     memcpy(newlist->elements, &oldlist->elements[nskip],
    1431      178228 :            newlist->length * sizeof(ListCell));
    1432             : 
    1433             :     check_list_invariants(newlist);
    1434      178228 :     return newlist;
    1435             : }
    1436             : 
    1437             : /*
    1438             :  * Return a deep copy of the specified list.
    1439             :  *
    1440             :  * The list elements are copied via copyObject(), so that this function's
    1441             :  * idea of a "deep" copy is considerably deeper than what list_free_deep()
    1442             :  * means by the same word.
    1443             :  */
    1444             : List *
    1445    18873682 : list_copy_deep(const List *oldlist)
    1446             : {
    1447             :     List       *newlist;
    1448             : 
    1449    18873682 :     if (oldlist == NIL)
    1450           0 :         return NIL;
    1451             : 
    1452             :     /* This is only sensible for pointer Lists */
    1453             :     Assert(IsA(oldlist, List));
    1454             : 
    1455    18873682 :     newlist = new_list(oldlist->type, oldlist->length);
    1456    76055398 :     for (int i = 0; i < newlist->length; i++)
    1457   114363432 :         lfirst(&newlist->elements[i]) =
    1458    57181716 :             copyObjectImpl(lfirst(&oldlist->elements[i]));
    1459             : 
    1460             :     check_list_invariants(newlist);
    1461    18873682 :     return newlist;
    1462             : }
    1463             : 
    1464             : /*
    1465             :  * Sort a list according to the specified comparator function.
    1466             :  *
    1467             :  * The list is sorted in-place.
    1468             :  *
    1469             :  * The comparator function is declared to receive arguments of type
    1470             :  * const ListCell *; this allows it to use lfirst() and variants
    1471             :  * without casting its arguments.  Otherwise it behaves the same as
    1472             :  * the comparator function for standard qsort().
    1473             :  *
    1474             :  * Like qsort(), this provides no guarantees about sort stability
    1475             :  * for equal keys.
    1476             :  */
    1477             : void
    1478      214012 : list_sort(List *list, list_sort_comparator cmp)
    1479             : {
    1480             :     typedef int (*qsort_comparator) (const void *a, const void *b);
    1481             :     int         len;
    1482             : 
    1483             :     check_list_invariants(list);
    1484             : 
    1485             :     /* Nothing to do if there's less than two elements */
    1486      214012 :     len = list_length(list);
    1487      214012 :     if (len > 1)
    1488       64952 :         qsort(list->elements, len, sizeof(ListCell), (qsort_comparator) cmp);
    1489      214012 : }
    1490             : 
    1491             : /*
    1492             :  * list_sort comparator for sorting a list into ascending OID order.
    1493             :  */
    1494             : int
    1495       76966 : list_oid_cmp(const ListCell *p1, const ListCell *p2)
    1496             : {
    1497       76966 :     Oid         v1 = lfirst_oid(p1);
    1498       76966 :     Oid         v2 = lfirst_oid(p2);
    1499             : 
    1500       76966 :     if (v1 < v2)
    1501       65280 :         return -1;
    1502       11686 :     if (v1 > v2)
    1503       11678 :         return 1;
    1504           8 :     return 0;
    1505             : }

Generated by: LCOV version 1.13