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