PostgreSQL Source Code: src/backend/nodes/list.c Source File

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

AltStyle によって変換されたページ (->オリジナル) /