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