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-2019, 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 "utils/memutils.h"
22 
23 
24 /*
25  * The previous List implementation, since it used a separate palloc chunk
26  * for each cons cell, had the property that adding or deleting list cells
27  * did not move the storage of other existing cells in the list. Quite a
28  * bit of existing code depended on that, by retaining ListCell pointers
29  * across such operations on a list. There is no such guarantee in this
30  * implementation, so instead we have debugging support that is meant to
31  * help flush out now-broken assumptions. Defining DEBUG_LIST_MEMORY_USAGE
32  * while building this file causes the List operations to forcibly move
33  * all cells in a list whenever a cell is added or deleted. In combination
34  * with MEMORY_CONTEXT_CHECKING and/or Valgrind, this can usually expose
35  * broken code. It's a bit expensive though, as there's many more palloc
36  * cycles and a lot more data-copying than in a default build.
37  *
38  * By default, we enable this when building for Valgrind.
39  */
40 #ifdef USE_VALGRIND
41 #define DEBUG_LIST_MEMORY_USAGE
42 #endif
43 
44 /* Overhead for the fixed part of a List header, measured in ListCells */
45 #define LIST_HEADER_OVERHEAD \
46  ((int) ((offsetof(List, initial_elements) - 1) / sizeof(ListCell) + 1))
47 
48 /*
49  * Macros to simplify writing assertions about the type of a list; a
50  * NIL list is considered to be an empty list of any type.
51  */
52 #define IsPointerList(l) ((l) == NIL || IsA((l), List))
53 #define IsIntegerList(l) ((l) == NIL || IsA((l), IntList))
54 #define IsOidList(l) ((l) == NIL || IsA((l), OidList))
55 
56 #ifdef USE_ASSERT_CHECKING
57 /*
58  * Check that the specified List is valid (so far as we can tell).
59  */
60 static void
62 {
63  if (list == NIL)
64  return;
65 
66  Assert(list->length > 0);
67  Assert(list->length <= list->max_length);
68  Assert(list->elements != NULL);
69 
70  Assert(list->type == T_List ||
71  list->type == T_IntList ||
72  list->type == T_OidList);
73 }
74 #else
75 #define check_list_invariants(l) ((void) 0)
76 #endif /* USE_ASSERT_CHECKING */
77 
78 /*
79  * Return a freshly allocated List with room for at least min_size cells.
80  *
81  * Since empty non-NIL lists are invalid, new_list() sets the initial length
82  * to min_size, effectively marking that number of cells as valid; the caller
83  * is responsible for filling in their data.
84  */
85 static List *
86 new_list(NodeTag type, int min_size)
87 {
88  List *newlist;
89  int max_size;
90 
91  Assert(min_size > 0);
92 
93  /*
94  * We allocate all the requested cells, and possibly some more, as part of
95  * the same palloc request as the List header. This is a big win for the
96  * typical case of short fixed-length lists. It can lose if we allocate a
97  * moderately long list and then it gets extended; we'll be wasting more
98  * initial_elements[] space than if we'd made the header small. However,
99  * rounding up the request as we do in the normal code path provides some
100  * defense against small extensions.
101  */
102 
103 #ifndef DEBUG_LIST_MEMORY_USAGE
104 
105  /*
106  * Normally, we set up a list with some extra cells, to allow it to grow
107  * without a repalloc. Prefer cell counts chosen to make the total
108  * allocation a power-of-2, since palloc would round it up to that anyway.
109  * (That stops being true for very large allocations, but very long lists
110  * are infrequent, so it doesn't seem worth special logic for such cases.)
111  *
112  * The minimum allocation is 8 ListCell units, providing either 4 or 5
113  * available ListCells depending on the machine's word width. Counting
114  * palloc's overhead, this uses the same amount of space as a one-cell
115  * list did in the old implementation, and less space for any longer list.
116  *
117  * We needn't worry about integer overflow; no caller passes min_size
118  * that's more than twice the size of an existing list, so the size limits
119  * within palloc will ensure that we don't overflow here.
120  */
121  max_size = 8; /* semi-arbitrary small power of 2 */
122  while (max_size < min_size + LIST_HEADER_OVERHEAD)
123  max_size *= 2;
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. The existing max length might
163  * not be a power of 2, so don't rely on that.
164  */
165  new_max_len = 16; /* semi-arbitrary small power of 2 */
166  while (new_max_len < min_size)
167  new_max_len *= 2;
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  {
176 
177  /*
178  * Replace original in-line allocation with a separate palloc block.
179  * Ensure it is in the same memory context as the List header. (The
180  * previous List implementation did not offer any guarantees about
181  * keeping all list cells in the same context, but it seems reasonable
182  * to create such a guarantee now.)
183  */
184  list->elements = (ListCell *)
186  new_max_len * sizeof(ListCell));
187  memcpy(list->elements, list->initial_elements,
188  list->length * sizeof(ListCell));
189 
190  /*
191  * Currently, asking aset.c to reduce the allocated size of the List
192  * header is pointless in terms of reclaiming space, unless the list
193  * is very long. However, it seems worth doing anyway to cause the
194  * no-longer-needed initial_elements[] space to be cleared in
195  * debugging builds.
196  */
197  newlist = (List *) repalloc(list, offsetof(List, initial_elements));
198 
199  /* That better not have failed, nor moved the list header */
200  Assert(newlist == list);
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  lfirst(list_tail(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  lfirst_int(list_tail(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  lfirst_oid(list_tail(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  lfirst(list_head(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  lfirst_int(list_head(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  lfirst_oid(list_head(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(), tell palloc code we're not using the
740  * initial_elements space anymore.
741  */
743 
744  newlist = (List *) repalloc(list, offsetof(List, initial_elements));
745  Assert(newlist == list);
746  }
747  list->elements = newelems;
748  list->max_length = newmaxlen;
749  list->length--;
750  check_list_invariants(list);
751  }
752 #endif
753 
754  return list;
755 }
756 
757 /*
758  * Delete 'cell' from 'list'.
759  *
760  * The List is pfree'd if this was the last member. However, we do not
761  * touch any data the cell might've been pointing to.
762  */
763 List *
765 {
766  return list_delete_nth_cell(list, cell - list->elements);
767 }
768 
769 /*
770  * Delete the first cell in list that matches datum, if any.
771  * Equality is determined via equal().
772  */
773 List *
774 list_delete(List *list, void *datum)
775 {
776  ListCell *cell;
777 
778  Assert(IsPointerList(list));
779  check_list_invariants(list);
780 
781  foreach(cell, list)
782  {
783  if (equal(lfirst(cell), datum))
784  return list_delete_cell(list, cell);
785  }
786 
787  /* Didn't find a match: return the list unmodified */
788  return list;
789 }
790 
791 /* As above, but use simple pointer equality */
792 List *
793 list_delete_ptr(List *list, void *datum)
794 {
795  ListCell *cell;
796 
797  Assert(IsPointerList(list));
798  check_list_invariants(list);
799 
800  foreach(cell, list)
801  {
802  if (lfirst(cell) == datum)
803  return list_delete_cell(list, cell);
804  }
805 
806  /* Didn't find a match: return the list unmodified */
807  return list;
808 }
809 
810 /* As above, but for integers */
811 List *
813 {
814  ListCell *cell;
815 
816  Assert(IsIntegerList(list));
817  check_list_invariants(list);
818 
819  foreach(cell, list)
820  {
821  if (lfirst_int(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 for OIDs */
830 List *
832 {
833  ListCell *cell;
834 
835  Assert(IsOidList(list));
836  check_list_invariants(list);
837 
838  foreach(cell, list)
839  {
840  if (lfirst_oid(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 /*
849  * Delete the first element of the list.
850  *
851  * This is useful to replace the Lisp-y code "list = lnext(list);" in cases
852  * where the intent is to alter the list rather than just traverse it.
853  * Beware that the list is modified, whereas the Lisp-y coding leaves
854  * the original list head intact in case there's another pointer to it.
855  */
856 List *
858 {
859  check_list_invariants(list);
860 
861  if (list == NIL)
862  return NIL; /* would an error be better? */
863 
864  return list_delete_nth_cell(list, 0);
865 }
866 
867 /*
868  * Delete the last element of the list.
869  *
870  * This is the opposite of list_delete_first(), but is noticeably cheaper
871  * with a long list, since no data need be moved.
872  */
873 List *
875 {
876  check_list_invariants(list);
877 
878  if (list == NIL)
879  return NIL; /* would an error be better? */
880 
881  /* list_truncate won't free list if it goes to empty, but this should */
882  if (list_length(list) <= 1)
883  {
884  list_free(list);
885  return NIL;
886  }
887 
888  return list_truncate(list, list_length(list) - 1);
889 }
890 
891 /*
892  * Generate the union of two lists. This is calculated by copying
893  * list1 via list_copy(), then adding to it all the members of list2
894  * that aren't already in list1.
895  *
896  * Whether an element is already a member of the list is determined
897  * via equal().
898  *
899  * The returned list is newly-allocated, although the content of the
900  * cells is the same (i.e. any pointed-to objects are not copied).
901  *
902  * NB: this function will NOT remove any duplicates that are present
903  * in list1 (so it only performs a "union" if list1 is known unique to
904  * start with). Also, if you are about to write "x = list_union(x, y)"
905  * you probably want to use list_concat_unique() instead to avoid wasting
906  * the storage of the old x list.
907  *
908  * This function could probably be implemented a lot faster if it is a
909  * performance bottleneck.
910  */
911 List *
912 list_union(const List *list1, const List *list2)
913 {
914  List *result;
915  const ListCell *cell;
916 
917  Assert(IsPointerList(list1));
918  Assert(IsPointerList(list2));
919 
920  result = list_copy(list1);
921  foreach(cell, list2)
922  {
923  if (!list_member(result, lfirst(cell)))
924  result = lappend(result, lfirst(cell));
925  }
926 
927  check_list_invariants(result);
928  return result;
929 }
930 
931 /*
932  * This variant of list_union() determines duplicates via simple
933  * pointer comparison.
934  */
935 List *
936 list_union_ptr(const List *list1, const List *list2)
937 {
938  List *result;
939  const ListCell *cell;
940 
941  Assert(IsPointerList(list1));
942  Assert(IsPointerList(list2));
943 
944  result = list_copy(list1);
945  foreach(cell, list2)
946  {
947  if (!list_member_ptr(result, lfirst(cell)))
948  result = lappend(result, lfirst(cell));
949  }
950 
951  check_list_invariants(result);
952  return result;
953 }
954 
955 /*
956  * This variant of list_union() operates upon lists of integers.
957  */
958 List *
959 list_union_int(const List *list1, const List *list2)
960 {
961  List *result;
962  const ListCell *cell;
963 
964  Assert(IsIntegerList(list1));
965  Assert(IsIntegerList(list2));
966 
967  result = list_copy(list1);
968  foreach(cell, list2)
969  {
970  if (!list_member_int(result, lfirst_int(cell)))
971  result = lappend_int(result, lfirst_int(cell));
972  }
973 
974  check_list_invariants(result);
975  return result;
976 }
977 
978 /*
979  * This variant of list_union() operates upon lists of OIDs.
980  */
981 List *
982 list_union_oid(const List *list1, const List *list2)
983 {
984  List *result;
985  const ListCell *cell;
986 
987  Assert(IsOidList(list1));
988  Assert(IsOidList(list2));
989 
990  result = list_copy(list1);
991  foreach(cell, list2)
992  {
993  if (!list_member_oid(result, lfirst_oid(cell)))
994  result = lappend_oid(result, lfirst_oid(cell));
995  }
996 
997  check_list_invariants(result);
998  return result;
999 }
1000 
1001 /*
1002  * Return a list that contains all the cells that are in both list1 and
1003  * list2. The returned list is freshly allocated via palloc(), but the
1004  * cells themselves point to the same objects as the cells of the
1005  * input lists.
1006  *
1007  * Duplicate entries in list1 will not be suppressed, so it's only a true
1008  * "intersection" if list1 is known unique beforehand.
1009  *
1010  * This variant works on lists of pointers, and determines list
1011  * membership via equal(). Note that the list1 member will be pointed
1012  * to in the result.
1013  */
1014 List *
1015 list_intersection(const List *list1, const List *list2)
1016 {
1017  List *result;
1018  const ListCell *cell;
1019 
1020  if (list1 == NIL || list2 == NIL)
1021  return NIL;
1022 
1023  Assert(IsPointerList(list1));
1024  Assert(IsPointerList(list2));
1025 
1026  result = NIL;
1027  foreach(cell, list1)
1028  {
1029  if (list_member(list2, lfirst(cell)))
1030  result = lappend(result, lfirst(cell));
1031  }
1032 
1033  check_list_invariants(result);
1034  return result;
1035 }
1036 
1037 /*
1038  * As list_intersection but operates on lists of integers.
1039  */
1040 List *
1041 list_intersection_int(const List *list1, const List *list2)
1042 {
1043  List *result;
1044  const ListCell *cell;
1045 
1046  if (list1 == NIL || list2 == NIL)
1047  return NIL;
1048 
1049  Assert(IsIntegerList(list1));
1050  Assert(IsIntegerList(list2));
1051 
1052  result = NIL;
1053  foreach(cell, list1)
1054  {
1055  if (list_member_int(list2, lfirst_int(cell)))
1056  result = lappend_int(result, lfirst_int(cell));
1057  }
1058 
1059  check_list_invariants(result);
1060  return result;
1061 }
1062 
1063 /*
1064  * Return a list that contains all the cells in list1 that are not in
1065  * list2. The returned list is freshly allocated via palloc(), but the
1066  * cells themselves point to the same objects as the cells of the
1067  * input lists.
1068  *
1069  * This variant works on lists of pointers, and determines list
1070  * membership via equal()
1071  */
1072 List *
1073 list_difference(const List *list1, const List *list2)
1074 {
1075  const ListCell *cell;
1076  List *result = NIL;
1077 
1078  Assert(IsPointerList(list1));
1079  Assert(IsPointerList(list2));
1080 
1081  if (list2 == NIL)
1082  return list_copy(list1);
1083 
1084  foreach(cell, list1)
1085  {
1086  if (!list_member(list2, lfirst(cell)))
1087  result = lappend(result, lfirst(cell));
1088  }
1089 
1090  check_list_invariants(result);
1091  return result;
1092 }
1093 
1094 /*
1095  * This variant of list_difference() determines list membership via
1096  * simple pointer equality.
1097  */
1098 List *
1099 list_difference_ptr(const List *list1, const List *list2)
1100 {
1101  const ListCell *cell;
1102  List *result = NIL;
1103 
1104  Assert(IsPointerList(list1));
1105  Assert(IsPointerList(list2));
1106 
1107  if (list2 == NIL)
1108  return list_copy(list1);
1109 
1110  foreach(cell, list1)
1111  {
1112  if (!list_member_ptr(list2, lfirst(cell)))
1113  result = lappend(result, lfirst(cell));
1114  }
1115 
1116  check_list_invariants(result);
1117  return result;
1118 }
1119 
1120 /*
1121  * This variant of list_difference() operates upon lists of integers.
1122  */
1123 List *
1124 list_difference_int(const List *list1, const List *list2)
1125 {
1126  const ListCell *cell;
1127  List *result = NIL;
1128 
1129  Assert(IsIntegerList(list1));
1130  Assert(IsIntegerList(list2));
1131 
1132  if (list2 == NIL)
1133  return list_copy(list1);
1134 
1135  foreach(cell, list1)
1136  {
1137  if (!list_member_int(list2, lfirst_int(cell)))
1138  result = lappend_int(result, lfirst_int(cell));
1139  }
1140 
1141  check_list_invariants(result);
1142  return result;
1143 }
1144 
1145 /*
1146  * This variant of list_difference() operates upon lists of OIDs.
1147  */
1148 List *
1149 list_difference_oid(const List *list1, const List *list2)
1150 {
1151  const ListCell *cell;
1152  List *result = NIL;
1153 
1154  Assert(IsOidList(list1));
1155  Assert(IsOidList(list2));
1156 
1157  if (list2 == NIL)
1158  return list_copy(list1);
1159 
1160  foreach(cell, list1)
1161  {
1162  if (!list_member_oid(list2, lfirst_oid(cell)))
1163  result = lappend_oid(result, lfirst_oid(cell));
1164  }
1165 
1166  check_list_invariants(result);
1167  return result;
1168 }
1169 
1170 /*
1171  * Append datum to list, but only if it isn't already in the list.
1172  *
1173  * Whether an element is already a member of the list is determined
1174  * via equal().
1175  */
1176 List *
1178 {
1179  if (list_member(list, datum))
1180  return list;
1181  else
1182  return lappend(list, datum);
1183 }
1184 
1185 /*
1186  * This variant of list_append_unique() determines list membership via
1187  * simple pointer equality.
1188  */
1189 List *
1191 {
1192  if (list_member_ptr(list, datum))
1193  return list;
1194  else
1195  return lappend(list, datum);
1196 }
1197 
1198 /*
1199  * This variant of list_append_unique() operates upon lists of integers.
1200  */
1201 List *
1203 {
1204  if (list_member_int(list, datum))
1205  return list;
1206  else
1207  return lappend_int(list, datum);
1208 }
1209 
1210 /*
1211  * This variant of list_append_unique() operates upon lists of OIDs.
1212  */
1213 List *
1215 {
1216  if (list_member_oid(list, datum))
1217  return list;
1218  else
1219  return lappend_oid(list, datum);
1220 }
1221 
1222 /*
1223  * Append to list1 each member of list2 that isn't already in list1.
1224  *
1225  * Whether an element is already a member of the list is determined
1226  * via equal().
1227  *
1228  * This is almost the same functionality as list_union(), but list1 is
1229  * modified in-place rather than being copied. However, callers of this
1230  * function may have strict ordering expectations -- i.e. that the relative
1231  * order of those list2 elements that are not duplicates is preserved.
1232  */
1233 List *
1234 list_concat_unique(List *list1, const List *list2)
1235 {
1236  ListCell *cell;
1237 
1238  Assert(IsPointerList(list1));
1239  Assert(IsPointerList(list2));
1240 
1241  foreach(cell, list2)
1242  {
1243  if (!list_member(list1, lfirst(cell)))
1244  list1 = lappend(list1, lfirst(cell));
1245  }
1246 
1247  check_list_invariants(list1);
1248  return list1;
1249 }
1250 
1251 /*
1252  * This variant of list_concat_unique() determines list membership via
1253  * simple pointer equality.
1254  */
1255 List *
1256 list_concat_unique_ptr(List *list1, const List *list2)
1257 {
1258  ListCell *cell;
1259 
1260  Assert(IsPointerList(list1));
1261  Assert(IsPointerList(list2));
1262 
1263  foreach(cell, list2)
1264  {
1265  if (!list_member_ptr(list1, lfirst(cell)))
1266  list1 = lappend(list1, lfirst(cell));
1267  }
1268 
1269  check_list_invariants(list1);
1270  return list1;
1271 }
1272 
1273 /*
1274  * This variant of list_concat_unique() operates upon lists of integers.
1275  */
1276 List *
1277 list_concat_unique_int(List *list1, const List *list2)
1278 {
1279  ListCell *cell;
1280 
1281  Assert(IsIntegerList(list1));
1282  Assert(IsIntegerList(list2));
1283 
1284  foreach(cell, list2)
1285  {
1286  if (!list_member_int(list1, lfirst_int(cell)))
1287  list1 = lappend_int(list1, lfirst_int(cell));
1288  }
1289 
1290  check_list_invariants(list1);
1291  return list1;
1292 }
1293 
1294 /*
1295  * This variant of list_concat_unique() operates upon lists of OIDs.
1296  */
1297 List *
1298 list_concat_unique_oid(List *list1, const List *list2)
1299 {
1300  ListCell *cell;
1301 
1302  Assert(IsOidList(list1));
1303  Assert(IsOidList(list2));
1304 
1305  foreach(cell, list2)
1306  {
1307  if (!list_member_oid(list1, lfirst_oid(cell)))
1308  list1 = lappend_oid(list1, lfirst_oid(cell));
1309  }
1310 
1311  check_list_invariants(list1);
1312  return list1;
1313 }
1314 
1315 /*
1316  * Remove adjacent duplicates in a list of OIDs.
1317  *
1318  * It is caller's responsibility to have sorted the list to bring duplicates
1319  * together, perhaps via list_sort(list, list_oid_cmp).
1320  */
1321 void
1323 {
1324  int len;
1325 
1326  Assert(IsOidList(list));
1327  len = list_length(list);
1328  if (len > 1)
1329  {
1330  ListCell *elements = list->elements;
1331  int i = 0;
1332 
1333  for (int j = 1; j < len; j++)
1334  {
1335  if (elements[i].oid_value != elements[j].oid_value)
1336  elements[++i].oid_value = elements[j].oid_value;
1337  }
1338  list->length = i + 1;
1339  }
1340  check_list_invariants(list);
1341 }
1342 
1343 /*
1344  * Free all storage in a list, and optionally the pointed-to elements
1345  */
1346 static void
1348 {
1349  if (list == NIL)
1350  return; /* nothing to do */
1351 
1352  check_list_invariants(list);
1353 
1354  if (deep)
1355  {
1356  for (int i = 0; i < list->length; i++)
1357  pfree(lfirst(&list->elements[i]));
1358  }
1359  if (list->elements != list->initial_elements)
1360  pfree(list->elements);
1361  pfree(list);
1362 }
1363 
1364 /*
1365  * Free all the cells of the list, as well as the list itself. Any
1366  * objects that are pointed-to by the cells of the list are NOT
1367  * free'd.
1368  *
1369  * On return, the argument to this function has been freed, so the
1370  * caller would be wise to set it to NIL for safety's sake.
1371  */
1372 void
1374 {
1375  list_free_private(list, false);
1376 }
1377 
1378 /*
1379  * Free all the cells of the list, the list itself, and all the
1380  * objects pointed-to by the cells of the list (each element in the
1381  * list must contain a pointer to a palloc()'d region of memory!)
1382  *
1383  * On return, the argument to this function has been freed, so the
1384  * caller would be wise to set it to NIL for safety's sake.
1385  */
1386 void
1388 {
1389  /*
1390  * A "deep" free operation only makes sense on a list of pointers.
1391  */
1392  Assert(IsPointerList(list));
1393  list_free_private(list, true);
1394 }
1395 
1396 /*
1397  * Return a shallow copy of the specified list.
1398  */
1399 List *
1400 list_copy(const List *oldlist)
1401 {
1402  List *newlist;
1403 
1404  if (oldlist == NIL)
1405  return NIL;
1406 
1407  newlist = new_list(oldlist->type, oldlist->length);
1408  memcpy(newlist->elements, oldlist->elements,
1409  newlist->length * sizeof(ListCell));
1410 
1411  check_list_invariants(newlist);
1412  return newlist;
1413 }
1414 
1415 /*
1416  * Return a shallow copy of the specified list, without the first N elements.
1417  */
1418 List *
1419 list_copy_tail(const List *oldlist, int nskip)
1420 {
1421  List *newlist;
1422 
1423  if (nskip < 0)
1424  nskip = 0; /* would it be better to elog? */
1425 
1426  if (oldlist == NIL || nskip >= oldlist->length)
1427  return NIL;
1428 
1429  newlist = new_list(oldlist->type, oldlist->length - nskip);
1430  memcpy(newlist->elements, &oldlist->elements[nskip],
1431  newlist->length * sizeof(ListCell));
1432 
1433  check_list_invariants(newlist);
1434  return newlist;
1435 }
1436 
1437 /*
1438  * Return a deep copy of the specified list.
1439  *
1440  * The list elements are copied via copyObject(), so that this function's
1441  * idea of a "deep" copy is considerably deeper than what list_free_deep()
1442  * means by the same word.
1443  */
1444 List *
1445 list_copy_deep(const List *oldlist)
1446 {
1447  List *newlist;
1448 
1449  if (oldlist == NIL)
1450  return NIL;
1451 
1452  /* This is only sensible for pointer Lists */
1453  Assert(IsA(oldlist, List));
1454 
1455  newlist = new_list(oldlist->type, oldlist->length);
1456  for (int i = 0; i < newlist->length; i++)
1457  lfirst(&newlist->elements[i]) =
1458  copyObjectImpl(lfirst(&oldlist->elements[i]));
1459 
1460  check_list_invariants(newlist);
1461  return newlist;
1462 }
1463 
1464 /*
1465  * Sort a list according to the specified comparator function.
1466  *
1467  * The list is sorted in-place.
1468  *
1469  * The comparator function is declared to receive arguments of type
1470  * const ListCell *; this allows it to use lfirst() and variants
1471  * without casting its arguments. Otherwise it behaves the same as
1472  * the comparator function for standard qsort().
1473  *
1474  * Like qsort(), this provides no guarantees about sort stability
1475  * for equal keys.
1476  */
1477 void
1479 {
1480  typedef int (*qsort_comparator) (const void *a, const void *b);
1481  int len;
1482 
1483  check_list_invariants(list);
1484 
1485  /* Nothing to do if there's less than two elements */
1486  len = list_length(list);
1487  if (len > 1)
1488  qsort(list->elements, len, sizeof(ListCell), (qsort_comparator) cmp);
1489 }
1490 
1491 /*
1492  * list_sort comparator for sorting a list into ascending OID order.
1493  */
1494 int
1495 list_oid_cmp(const ListCell *p1, const ListCell *p2)
1496 {
1497  Oid v1 = lfirst_oid(p1);
1498  Oid v2 = lfirst_oid(p2);
1499 
1500  if (v1 < v2)
1501  return -1;
1502  if (v1 > v2)
1503  return 1;
1504  return 0;
1505 }
#define NIL
Definition: pg_list.h:65
List * list_delete_int(List *list, int datum)
Definition: list.c:812
#define IsA(nodeptr, _type_)
Definition: nodes.h:576
List * list_append_unique_oid(List *list, Oid datum)
Definition: list.c:1214
List * list_difference_int(const List *list1, const List *list2)
Definition: list.c:1124
List * list_union_oid(const List *list1, const List *list2)
Definition: list.c:982
List * list_concat_unique_int(List *list1, const List *list2)
Definition: list.c:1277
List * lcons_int(int datum, List *list)
Definition: list.c:471
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:3008
List * list_intersection_int(const List *list1, const List *list2)
Definition: list.c:1041
static void new_head_cell(List *list)
Definition: list.c:287
List * list_difference_ptr(const List *list1, const List *list2)
Definition: list.c:1099
#define check_list_invariants(l)
Definition: list.c:75
List * list_truncate(List *list, int new_size)
Definition: list.c:585
List * list_copy(const List *oldlist)
Definition: list.c:1400
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
List * lcons_oid(Oid datum, List *list)
Definition: list.c:489
List * list_union(const List *list1, const List *list2)
Definition: list.c:912
List * list_delete_ptr(List *list, void *datum)
Definition: list.c:793
List * list_copy_tail(const List *oldlist, int nskip)
Definition: list.c:1419
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:1387
static ListCell * insert_new_cell(List *list, int pos)
Definition: list.c:379
#define IsIntegerList(l)
Definition: list.c:53
List * list_copy_deep(const List *oldlist)
Definition: list.c:1445
#define list_make1(x1)
Definition: pg_list.h:227
int list_oid_cmp(const ListCell *p1, const ListCell *p2)
Definition: list.c:1495
List * list_insert_nth(List *list, int pos, void *datum)
Definition: list.c:400
void pfree(void *pointer)
Definition: mcxt.c:1031
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:1190
List * list_concat_unique_oid(List *list1, const List *list2)
Definition: list.c:1298
#define lfirst_int(lc)
Definition: pg_list.h:191
List * list_union_ptr(const List *list1, const List *list2)
Definition: list.c:936
bool list_member_int(const List *list, int datum)
Definition: list.c:654
#define LIST_HEADER_OVERHEAD
Definition: list.c:45
List * list_append_unique(List *list, void *datum)
Definition: list.c:1177
#define memmove(d, s, c)
Definition: c.h:1238
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:1015
List * list_delete_last(List *list)
Definition: list.c:874
List * list_union_int(const List *list1, const List *list2)
Definition: list.c:959
static ListCell * list_head(const List *l)
Definition: pg_list.h:125
List * list_delete_oid(List *list, Oid datum)
Definition: list.c:831
static void new_tail_cell(List *list)
Definition: list.c:305
void list_deduplicate_oid(List *list)
Definition: list.c:1322
#define list_make1_int(x1)
Definition: pg_list.h:238
#define IsPointerList(l)
Definition: list.c:52
Definition: nodes.h:297
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:1149
union ListCell ListCell
int(* list_sort_comparator)(const ListCell *a, const ListCell *b)
Definition: pg_list.h:574
#define list_make1_oid(x1)
Definition: pg_list.h:249
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:764
List * list_make2_impl(NodeTag t, ListCell datum1, ListCell datum2)
Definition: list.c:243
#define IsOidList(l)
Definition: list.c:54
bool list_member_ptr(const List *list, const void *datum)
Definition: list.c:634
List * lcons(void *datum, List *list)
Definition: list.c:453
bool list_member_oid(const List *list, Oid datum)
Definition: list.c:674
#define Assert(condition)
Definition: c.h:732
#define lfirst(lc)
Definition: pg_list.h:190
List * list_make4_impl(NodeTag t, ListCell datum1, ListCell datum2, ListCell datum3, ListCell datum4)
Definition: list.c:267
static int list_length(const List *l)
Definition: pg_list.h:169
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:1073
List * list_make1_impl(NodeTag t, ListCell datum1)
Definition: list.c:233
static void list_free_private(List *list, bool deep)
Definition: list.c:1347
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:1044
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:924
void list_sort(List *list, list_sort_comparator cmp)
Definition: list.c:1478
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:771
List * list_insert_nth_int(List *list, int pos, int datum)
Definition: list.c:414
void list_free(List *list)
Definition: list.c:1373
int i
List * list_append_unique_int(List *list, int datum)
Definition: list.c:1202
ListCell initial_elements[FLEXIBLE_ARRAY_MEMBER]
Definition: pg_list.h:57
static ListCell * list_tail(const List *l)
Definition: pg_list.h:132
#define qsort(a, b, c, d)
Definition: port.h:492
List * list_delete(List *list, void *datum)
Definition: list.c:774
List * list_delete_nth_cell(List *list, int n)
Definition: list.c:696
#define PG_USED_FOR_ASSERTS_ONLY
Definition: c.h:123
Definition: pg_list.h:50
List * list_concat_unique_ptr(List *list1, const List *list2)
Definition: list.c:1256
static List * new_list(NodeTag type, int min_size)
Definition: list.c:86
#define offsetof(type, field)
Definition: c.h:655
#define lfirst_oid(lc)
Definition: pg_list.h:192
List * list_delete_first(List *list)
Definition: list.c:857
static MemoryContext GetMemoryChunkContext(void *pointer)
Definition: memutils.h:112
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:4757
List * list_concat_unique(List *list1, const List *list2)
Definition: list.c:1234