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