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