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