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