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