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