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