1/*-------------------------------------------------------------------------
2 *
3 * list.c
4 * implementation for PostgreSQL generic linked list package
5 *
6 *
7 * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
8 * Portions Copyright (c) 1994, Regents of the University of California
9 *
10 *
11 * IDENTIFICATION
12 * src/backend/nodes/list.c
13 *
14 *-------------------------------------------------------------------------
15 */
16#include "postgres.h"
17
18#include "nodes/pg_list.h"
19
20
21/*
22 * Routines to simplify writing assertions about the type of a list; a
23 * NIL list is considered to be an empty list of any type.
24 */
25#define IsPointerList(l) ((l) == NIL || IsA((l), List))
26#define IsIntegerList(l) ((l) == NIL || IsA((l), IntList))
27#define IsOidList(l) ((l) == NIL || IsA((l), OidList))
28
29#ifdef USE_ASSERT_CHECKING
30/*
31 * Check that the specified List is valid (so far as we can tell).
32 */
33static void
34check_list_invariants(const List *list)
35{
36 if (list == NIL)
37 return;
38
39 Assert(list->length > 0);
40 Assert(list->head != NULL);
41 Assert(list->tail != NULL);
42
43 Assert(list->type == T_List ||
44 list->type == T_IntList ||
45 list->type == T_OidList);
46
47 if (list->length == 1)
48 Assert(list->head == list->tail);
49 if (list->length == 2)
50 Assert(list->head->next == list->tail);
51 Assert(list->tail->next == NULL);
52}
53#else
54#define check_list_invariants(l)
55#endif /* USE_ASSERT_CHECKING */
56
57/*
58 * Return a freshly allocated List. Since empty non-NIL lists are
59 * invalid, new_list() also allocates the head cell of the new list:
60 * the caller should be sure to fill in that cell's data.
61 */
62static List *
63new_list(NodeTag type)
64{
65 List *new_list;
66 ListCell *new_head;
67
68 new_head = (ListCell *) palloc(sizeof(*new_head));
69 new_head->next = NULL;
70 /* new_head->data is left undefined! */
71
72 new_list = (List *) palloc(sizeof(*new_list));
73 new_list->type = type;
74 new_list->length = 1;
75 new_list->head = new_head;
76 new_list->tail = new_head;
77
78 return new_list;
79}
80
81/*
82 * Allocate a new cell and make it the head of the specified
83 * list. Assumes the list it is passed is non-NIL.
84 *
85 * The data in the new head cell is undefined; the caller should be
86 * sure to fill it in
87 */
88static void
89new_head_cell(List *list)
90{
91 ListCell *new_head;
92
93 new_head = (ListCell *) palloc(sizeof(*new_head));
94 new_head->next = list->head;
95
96 list->head = new_head;
97 list->length++;
98}
99
100/*
101 * Allocate a new cell and make it the tail of the specified
102 * list. Assumes the list it is passed is non-NIL.
103 *
104 * The data in the new tail cell is undefined; the caller should be
105 * sure to fill it in
106 */
107static void
108new_tail_cell(List *list)
109{
110 ListCell *new_tail;
111
112 new_tail = (ListCell *) palloc(sizeof(*new_tail));
113 new_tail->next = NULL;
114
115 list->tail->next = new_tail;
116 list->tail = new_tail;
117 list->length++;
118}
119
120/*
121 * Append a pointer to the list. A pointer to the modified list is
122 * returned. Note that this function may or may not destructively
123 * modify the list; callers should always use this function's return
124 * value, rather than continuing to use the pointer passed as the
125 * first argument.
126 */
127List *
128lappend(List *list, void *datum)
129{
130 Assert(IsPointerList(list));
131
132 if (list == NIL)
133 list = new_list(T_List);
134 else
135 new_tail_cell(list);
136
137 lfirst(list->tail) = datum;
138 check_list_invariants(list);
139 return list;
140}
141
142/*
143 * Append an integer to the specified list. See lappend()
144 */
145List *
146lappend_int(List *list, int datum)
147{
148 Assert(IsIntegerList(list));
149
150 if (list == NIL)
151 list = new_list(T_IntList);
152 else
153 new_tail_cell(list);
154
155 lfirst_int(list->tail) = datum;
156 check_list_invariants(list);
157 return list;
158}
159
160/*
161 * Append an OID to the specified list. See lappend()
162 */
163List *
164lappend_oid(List *list, Oid datum)
165{
166 Assert(IsOidList(list));
167
168 if (list == NIL)
169 list = new_list(T_OidList);
170 else
171 new_tail_cell(list);
172
173 lfirst_oid(list->tail) = datum;
174 check_list_invariants(list);
175 return list;
176}
177
178/*
179 * Add a new cell to the list, in the position after 'prev_cell'. The
180 * data in the cell is left undefined, and must be filled in by the
181 * caller. 'list' is assumed to be non-NIL, and 'prev_cell' is assumed
182 * to be non-NULL and a member of 'list'.
183 */
184static ListCell *
185add_new_cell(List *list, ListCell *prev_cell)
186{
187 ListCell *new_cell;
188
189 new_cell = (ListCell *) palloc(sizeof(*new_cell));
190 /* new_cell->data is left undefined! */
191 new_cell->next = prev_cell->next;
192 prev_cell->next = new_cell;
193
194 if (list->tail == prev_cell)
195 list->tail = new_cell;
196
197 list->length++;
198
199 return new_cell;
200}
201
202/*
203 * Add a new cell to the specified list (which must be non-NIL);
204 * it will be placed after the list cell 'prev' (which must be
205 * non-NULL and a member of 'list'). The data placed in the new cell
206 * is 'datum'. The newly-constructed cell is returned.
207 */
208ListCell *
209lappend_cell(List *list, ListCell *prev, void *datum)
210{
211 ListCell *new_cell;
212
213 Assert(IsPointerList(list));
214
215 new_cell = add_new_cell(list, prev);
216 lfirst(new_cell) = datum;
217 check_list_invariants(list);
218 return new_cell;
219}
220
221ListCell *
222lappend_cell_int(List *list, ListCell *prev, int datum)
223{
224 ListCell *new_cell;
225
226 Assert(IsIntegerList(list));
227
228 new_cell = add_new_cell(list, prev);
229 lfirst_int(new_cell) = datum;
230 check_list_invariants(list);
231 return new_cell;
232}
233
234ListCell *
235lappend_cell_oid(List *list, ListCell *prev, Oid datum)
236{
237 ListCell *new_cell;
238
239 Assert(IsOidList(list));
240
241 new_cell = add_new_cell(list, prev);
242 lfirst_oid(new_cell) = datum;
243 check_list_invariants(list);
244 return new_cell;
245}
246
247/*
248 * Prepend a new element to the list. A pointer to the modified list
249 * is returned. Note that this function may or may not destructively
250 * modify the list; callers should always use this function's return
251 * value, rather than continuing to use the pointer passed as the
252 * second argument.
253 *
254 * Caution: before Postgres 8.0, the original List was unmodified and
255 * could be considered to retain its separate identity. This is no longer
256 * the case.
257 */
258List *
259lcons(void *datum, List *list)
260{
261 Assert(IsPointerList(list));
262
263 if (list == NIL)
264 list = new_list(T_List);
265 else
266 new_head_cell(list);
267
268 lfirst(list->head) = datum;
269 check_list_invariants(list);
270 return list;
271}
272
273/*
274 * Prepend an integer to the list. See lcons()
275 */
276List *
277lcons_int(int datum, List *list)
278{
279 Assert(IsIntegerList(list));
280
281 if (list == NIL)
282 list = new_list(T_IntList);
283 else
284 new_head_cell(list);
285
286 lfirst_int(list->head) = datum;
287 check_list_invariants(list);
288 return list;
289}
290
291/*
292 * Prepend an OID to the list. See lcons()
293 */
294List *
295lcons_oid(Oid datum, List *list)
296{
297 Assert(IsOidList(list));
298
299 if (list == NIL)
300 list = new_list(T_OidList);
301 else
302 new_head_cell(list);
303
304 lfirst_oid(list->head) = datum;
305 check_list_invariants(list);
306 return list;
307}
308
309/*
310 * Concatenate list2 to the end of list1, and return list1. list1 is
311 * destructively changed. Callers should be sure to use the return
312 * value as the new pointer to the concatenated list: the 'list1'
313 * input pointer may or may not be the same as the returned pointer.
314 *
315 * The nodes in list2 are merely appended to the end of list1 in-place
316 * (i.e. they aren't copied; the two lists will share some of the same
317 * storage). Therefore, invoking list_free() on list2 will also
318 * invalidate a portion of list1.
319 */
320List *
321list_concat(List *list1, List *list2)
322{
323 if (list1 == NIL)
324 return list2;
325 if (list2 == NIL)
326 return list1;
327 if (list1 == list2)
328 elog(ERROR, "cannot list_concat() a list to itself");
329
330 Assert(list1->type == list2->type);
331
332 list1->length += list2->length;
333 list1->tail->next = list2->head;
334 list1->tail = list2->tail;
335
336 check_list_invariants(list1);
337 return list1;
338}
339
340/*
341 * Truncate 'list' to contain no more than 'new_size' elements. This
342 * modifies the list in-place! Despite this, callers should use the
343 * pointer returned by this function to refer to the newly truncated
344 * list -- it may or may not be the same as the pointer that was
345 * passed.
346 *
347 * Note that any cells removed by list_truncate() are NOT pfree'd.
348 */
349List *
350list_truncate(List *list, int new_size)
351{
352 ListCell *cell;
353 int n;
354
355 if (new_size <= 0)
356 return NIL; /* truncate to zero length */
357
358 /* If asked to effectively extend the list, do nothing */
359 if (new_size >= list_length(list))
360 return list;
361
362 n = 1;
363 foreach(cell, list)
364 {
365 if (n == new_size)
366 {
367 cell->next = NULL;
368 list->tail = cell;
369 list->length = new_size;
370 check_list_invariants(list);
371 return list;
372 }
373 n++;
374 }
375
376 /* keep the compiler quiet; never reached */
377 Assert(false);
378 return list;
379}
380
381/*
382 * Locate the n'th cell (counting from 0) of the list. It is an assertion
383 * failure if there is no such cell.
384 */
385ListCell *
386list_nth_cell(const List *list, int n)
387{
388 ListCell *match;
389
390 Assert(list != NIL);
391 Assert(n >= 0);
392 Assert(n < list->length);
393 check_list_invariants(list);
394
395 /* Does the caller actually mean to fetch the tail? */
396 if (n == list->length - 1)
397 return list->tail;
398
399 for (match = list->head; n-- > 0; match = match->next)
400 ;
401
402 return match;
403}
404
405/*
406 * Return the data value contained in the n'th element of the
407 * specified list. (List elements begin at 0.)
408 */
409void *
410list_nth(const List *list, int n)
411{
412 Assert(IsPointerList(list));
413 return lfirst(list_nth_cell(list, n));
414}
415
416/*
417 * Return the integer value contained in the n'th element of the
418 * specified list.
419 */
420int
421list_nth_int(const List *list, int n)
422{
423 Assert(IsIntegerList(list));
424 return lfirst_int(list_nth_cell(list, n));
425}
426
427/*
428 * Return the OID value contained in the n'th element of the specified
429 * list.
430 */
431Oid
432list_nth_oid(const List *list, int n)
433{
434 Assert(IsOidList(list));
435 return lfirst_oid(list_nth_cell(list, n));
436}
437
438/*
439 * Return true iff 'datum' is a member of the list. Equality is
440 * determined via equal(), so callers should ensure that they pass a
441 * Node as 'datum'.
442 */
443bool
444list_member(const List *list, const void *datum)
445{
446 const ListCell *cell;
447
448 Assert(IsPointerList(list));
449 check_list_invariants(list);
450
451 foreach(cell, list)
452 {
453 if (equal(lfirst(cell), datum))
454 return true;
455 }
456
457 return false;
458}
459
460/*
461 * Return true iff 'datum' is a member of the list. Equality is
462 * determined by using simple pointer comparison.
463 */
464bool
465list_member_ptr(const List *list, const void *datum)
466{
467 const ListCell *cell;
468
469 Assert(IsPointerList(list));
470 check_list_invariants(list);
471
472 foreach(cell, list)
473 {
474 if (lfirst(cell) == datum)
475 return true;
476 }
477
478 return false;
479}
480
481/*
482 * Return true iff the integer 'datum' is a member of the list.
483 */
484bool
485list_member_int(const List *list, int datum)
486{
487 const ListCell *cell;
488
489 Assert(IsIntegerList(list));
490 check_list_invariants(list);
491
492 foreach(cell, list)
493 {
494 if (lfirst_int(cell) == datum)
495 return true;
496 }
497
498 return false;
499}
500
501/*
502 * Return true iff the OID 'datum' is a member of the list.
503 */
504bool
505list_member_oid(const List *list, Oid datum)
506{
507 const ListCell *cell;
508
509 Assert(IsOidList(list));
510 check_list_invariants(list);
511
512 foreach(cell, list)
513 {
514 if (lfirst_oid(cell) == datum)
515 return true;
516 }
517
518 return false;
519}
520
521/*
522 * Delete 'cell' from 'list'; 'prev' is the previous element to 'cell'
523 * in 'list', if any (i.e. prev == NULL iff list->head == cell)
524 *
525 * The cell is pfree'd, as is the List header if this was the last member.
526 */
527List *
528list_delete_cell(List *list, ListCell *cell, ListCell *prev)
529{
530 check_list_invariants(list);
531 Assert(prev != NULL ? lnext(prev) == cell : list_head(list) == cell);
532
533 /*
534 * If we're about to delete the last node from the list, free the whole
535 * list instead and return NIL, which is the only valid representation of
536 * a zero-length list.
537 */
538 if (list->length == 1)
539 {
540 list_free(list);
541 return NIL;
542 }
543
544 /*
545 * Otherwise, adjust the necessary list links, deallocate the particular
546 * node we have just removed, and return the list we were given.
547 */
548 list->length--;
549
550 if (prev)
551 prev->next = cell->next;
552 else
553 list->head = cell->next;
554
555 if (list->tail == cell)
556 list->tail = prev;
557
558 pfree(cell);
559 return list;
560}
561
562/*
563 * Delete the first cell in list that matches datum, if any.
564 * Equality is determined via equal().
565 */
566List *
567list_delete(List *list, void *datum)
568{
569 ListCell *cell;
570 ListCell *prev;
571
572 Assert(IsPointerList(list));
573 check_list_invariants(list);
574
575 prev = NULL;
576 foreach(cell, list)
577 {
578 if (equal(lfirst(cell), datum))
579 return list_delete_cell(list, cell, prev);
580
581 prev = cell;
582 }
583
584 /* Didn't find a match: return the list unmodified */
585 return list;
586}
587
588/* As above, but use simple pointer equality */
589List *
590list_delete_ptr(List *list, void *datum)
591{
592 ListCell *cell;
593 ListCell *prev;
594
595 Assert(IsPointerList(list));
596 check_list_invariants(list);
597
598 prev = NULL;
599 foreach(cell, list)
600 {
601 if (lfirst(cell) == datum)
602 return list_delete_cell(list, cell, prev);
603
604 prev = cell;
605 }
606
607 /* Didn't find a match: return the list unmodified */
608 return list;
609}
610
611/* As above, but for integers */
612List *
613list_delete_int(List *list, int datum)
614{
615 ListCell *cell;
616 ListCell *prev;
617
618 Assert(IsIntegerList(list));
619 check_list_invariants(list);
620
621 prev = NULL;
622 foreach(cell, list)
623 {
624 if (lfirst_int(cell) == datum)
625 return list_delete_cell(list, cell, prev);
626
627 prev = cell;
628 }
629
630 /* Didn't find a match: return the list unmodified */
631 return list;
632}
633
634/* As above, but for OIDs */
635List *
636list_delete_oid(List *list, Oid datum)
637{
638 ListCell *cell;
639 ListCell *prev;
640
641 Assert(IsOidList(list));
642 check_list_invariants(list);
643
644 prev = NULL;
645 foreach(cell, list)
646 {
647 if (lfirst_oid(cell) == datum)
648 return list_delete_cell(list, cell, prev);
649
650 prev = cell;
651 }
652
653 /* Didn't find a match: return the list unmodified */
654 return list;
655}
656
657/*
658 * Delete the first element of the list.
659 *
660 * This is useful to replace the Lisp-y code "list = lnext(list);" in cases
661 * where the intent is to alter the list rather than just traverse it.
662 * Beware that the removed cell is freed, whereas the lnext() coding leaves
663 * the original list head intact if there's another pointer to it.
664 */
665List *
666list_delete_first(List *list)
667{
668 check_list_invariants(list);
669
670 if (list == NIL)
671 return NIL; /* would an error be better? */
672
673 return list_delete_cell(list, list_head(list), NULL);
674}
675
676/*
677 * Generate the union of two lists. This is calculated by copying
678 * list1 via list_copy(), then adding to it all the members of list2
679 * that aren't already in list1.
680 *
681 * Whether an element is already a member of the list is determined
682 * via equal().
683 *
684 * The returned list is newly-allocated, although the content of the
685 * cells is the same (i.e. any pointed-to objects are not copied).
686 *
687 * NB: this function will NOT remove any duplicates that are present
688 * in list1 (so it only performs a "union" if list1 is known unique to
689 * start with). Also, if you are about to write "x = list_union(x, y)"
690 * you probably want to use list_concat_unique() instead to avoid wasting
691 * the list cells of the old x list.
692 *
693 * This function could probably be implemented a lot faster if it is a
694 * performance bottleneck.
695 */
696List *
697list_union(const List *list1, const List *list2)
698{
699 List *result;
700 const ListCell *cell;
701
702 Assert(IsPointerList(list1));
703 Assert(IsPointerList(list2));
704
705 result = list_copy(list1);
706 foreach(cell, list2)
707 {
708 if (!list_member(result, lfirst(cell)))
709 result = lappend(result, lfirst(cell));
710 }
711
712 check_list_invariants(result);
713 return result;
714}
715
716/*
717 * This variant of list_union() determines duplicates via simple
718 * pointer comparison.
719 */
720List *
721list_union_ptr(const List *list1, const List *list2)
722{
723 List *result;
724 const ListCell *cell;
725
726 Assert(IsPointerList(list1));
727 Assert(IsPointerList(list2));
728
729 result = list_copy(list1);
730 foreach(cell, list2)
731 {
732 if (!list_member_ptr(result, lfirst(cell)))
733 result = lappend(result, lfirst(cell));
734 }
735
736 check_list_invariants(result);
737 return result;
738}
739
740/*
741 * This variant of list_union() operates upon lists of integers.
742 */
743List *
744list_union_int(const List *list1, const List *list2)
745{
746 List *result;
747 const ListCell *cell;
748
749 Assert(IsIntegerList(list1));
750 Assert(IsIntegerList(list2));
751
752 result = list_copy(list1);
753 foreach(cell, list2)
754 {
755 if (!list_member_int(result, lfirst_int(cell)))
756 result = lappend_int(result, lfirst_int(cell));
757 }
758
759 check_list_invariants(result);
760 return result;
761}
762
763/*
764 * This variant of list_union() operates upon lists of OIDs.
765 */
766List *
767list_union_oid(const List *list1, const List *list2)
768{
769 List *result;
770 const ListCell *cell;
771
772 Assert(IsOidList(list1));
773 Assert(IsOidList(list2));
774
775 result = list_copy(list1);
776 foreach(cell, list2)
777 {
778 if (!list_member_oid(result, lfirst_oid(cell)))
779 result = lappend_oid(result, lfirst_oid(cell));
780 }
781
782 check_list_invariants(result);
783 return result;
784}
785
786/*
787 * Return a list that contains all the cells that are in both list1 and
788 * list2. The returned list is freshly allocated via palloc(), but the
789 * cells themselves point to the same objects as the cells of the
790 * input lists.
791 *
792 * Duplicate entries in list1 will not be suppressed, so it's only a true
793 * "intersection" if list1 is known unique beforehand.
794 *
795 * This variant works on lists of pointers, and determines list
796 * membership via equal(). Note that the list1 member will be pointed
797 * to in the result.
798 */
799List *
800list_intersection(const List *list1, const List *list2)
801{
802 List *result;
803 const ListCell *cell;
804
805 if (list1 == NIL || list2 == NIL)
806 return NIL;
807
808 Assert(IsPointerList(list1));
809 Assert(IsPointerList(list2));
810
811 result = NIL;
812 foreach(cell, list1)
813 {
814 if (list_member(list2, lfirst(cell)))
815 result = lappend(result, lfirst(cell));
816 }
817
818 check_list_invariants(result);
819 return result;
820}
821
822/*
823 * As list_intersection but operates on lists of integers.
824 */
825List *
826list_intersection_int(const List *list1, const List *list2)
827{
828 List *result;
829 const ListCell *cell;
830
831 if (list1 == NIL || list2 == NIL)
832 return NIL;
833
834 Assert(IsIntegerList(list1));
835 Assert(IsIntegerList(list2));
836
837 result = NIL;
838 foreach(cell, list1)
839 {
840 if (list_member_int(list2, lfirst_int(cell)))
841 result = lappend_int(result, lfirst_int(cell));
842 }
843
844 check_list_invariants(result);
845 return result;
846}
847
848/*
849 * Return a list that contains all the cells in list1 that are not in
850 * list2. The returned list is freshly allocated via palloc(), but the
851 * cells themselves point to the same objects as the cells of the
852 * input lists.
853 *
854 * This variant works on lists of pointers, and determines list
855 * membership via equal()
856 */
857List *
858list_difference(const List *list1, const List *list2)
859{
860 const ListCell *cell;
861 List *result = NIL;
862
863 Assert(IsPointerList(list1));
864 Assert(IsPointerList(list2));
865
866 if (list2 == NIL)
867 return list_copy(list1);
868
869 foreach(cell, list1)
870 {
871 if (!list_member(list2, lfirst(cell)))
872 result = lappend(result, lfirst(cell));
873 }
874
875 check_list_invariants(result);
876 return result;
877}
878
879/*
880 * This variant of list_difference() determines list membership via
881 * simple pointer equality.
882 */
883List *
884list_difference_ptr(const List *list1, const List *list2)
885{
886 const ListCell *cell;
887 List *result = NIL;
888
889 Assert(IsPointerList(list1));
890 Assert(IsPointerList(list2));
891
892 if (list2 == NIL)
893 return list_copy(list1);
894
895 foreach(cell, list1)
896 {
897 if (!list_member_ptr(list2, lfirst(cell)))
898 result = lappend(result, lfirst(cell));
899 }
900
901 check_list_invariants(result);
902 return result;
903}
904
905/*
906 * This variant of list_difference() operates upon lists of integers.
907 */
908List *
909list_difference_int(const List *list1, const List *list2)
910{
911 const ListCell *cell;
912 List *result = NIL;
913
914 Assert(IsIntegerList(list1));
915 Assert(IsIntegerList(list2));
916
917 if (list2 == NIL)
918 return list_copy(list1);
919
920 foreach(cell, list1)
921 {
922 if (!list_member_int(list2, lfirst_int(cell)))
923 result = lappend_int(result, lfirst_int(cell));
924 }
925
926 check_list_invariants(result);
927 return result;
928}
929
930/*
931 * This variant of list_difference() operates upon lists of OIDs.
932 */
933List *
934list_difference_oid(const List *list1, const List *list2)
935{
936 const ListCell *cell;
937 List *result = NIL;
938
939 Assert(IsOidList(list1));
940 Assert(IsOidList(list2));
941
942 if (list2 == NIL)
943 return list_copy(list1);
944
945 foreach(cell, list1)
946 {
947 if (!list_member_oid(list2, lfirst_oid(cell)))
948 result = lappend_oid(result, lfirst_oid(cell));
949 }
950
951 check_list_invariants(result);
952 return result;
953}
954
955/*
956 * Append datum to list, but only if it isn't already in the list.
957 *
958 * Whether an element is already a member of the list is determined
959 * via equal().
960 */
961List *
962list_append_unique(List *list, void *datum)
963{
964 if (list_member(list, datum))
965 return list;
966 else
967 return lappend(list, datum);
968}
969
970/*
971 * This variant of list_append_unique() determines list membership via
972 * simple pointer equality.
973 */
974List *
975list_append_unique_ptr(List *list, void *datum)
976{
977 if (list_member_ptr(list, datum))
978 return list;
979 else
980 return lappend(list, datum);
981}
982
983/*
984 * This variant of list_append_unique() operates upon lists of integers.
985 */
986List *
987list_append_unique_int(List *list, int datum)
988{
989 if (list_member_int(list, datum))
990 return list;
991 else
992 return lappend_int(list, datum);
993}
994
995/*
996 * This variant of list_append_unique() operates upon lists of OIDs.
997 */
998List *
999list_append_unique_oid(List *list, Oid datum)
1000{
1001 if (list_member_oid(list, datum))
1002 return list;
1003 else
1004 return lappend_oid(list, datum);
1005}
1006
1007/*
1008 * Append to list1 each member of list2 that isn't already in list1.
1009 *
1010 * Whether an element is already a member of the list is determined
1011 * via equal().
1012 *
1013 * This is almost the same functionality as list_union(), but list1 is
1014 * modified in-place rather than being copied. However, callers of this
1015 * function may have strict ordering expectations -- i.e. that the relative
1016 * order of those list2 elements that are not duplicates is preserved. Note
1017 * also that list2's cells are not inserted in list1, so the analogy to
1018 * list_concat() isn't perfect.
1019 */
1020List *
1021list_concat_unique(List *list1, List *list2)
1022{
1023 ListCell *cell;
1024
1025 Assert(IsPointerList(list1));
1026 Assert(IsPointerList(list2));
1027
1028 foreach(cell, list2)
1029 {
1030 if (!list_member(list1, lfirst(cell)))
1031 list1 = lappend(list1, lfirst(cell));
1032 }
1033
1034 check_list_invariants(list1);
1035 return list1;
1036}
1037
1038/*
1039 * This variant of list_concat_unique() determines list membership via
1040 * simple pointer equality.
1041 */
1042List *
1043list_concat_unique_ptr(List *list1, List *list2)
1044{
1045 ListCell *cell;
1046
1047 Assert(IsPointerList(list1));
1048 Assert(IsPointerList(list2));
1049
1050 foreach(cell, list2)
1051 {
1052 if (!list_member_ptr(list1, lfirst(cell)))
1053 list1 = lappend(list1, lfirst(cell));
1054 }
1055
1056 check_list_invariants(list1);
1057 return list1;
1058}
1059
1060/*
1061 * This variant of list_concat_unique() operates upon lists of integers.
1062 */
1063List *
1064list_concat_unique_int(List *list1, List *list2)
1065{
1066 ListCell *cell;
1067
1068 Assert(IsIntegerList(list1));
1069 Assert(IsIntegerList(list2));
1070
1071 foreach(cell, list2)
1072 {
1073 if (!list_member_int(list1, lfirst_int(cell)))
1074 list1 = lappend_int(list1, lfirst_int(cell));
1075 }
1076
1077 check_list_invariants(list1);
1078 return list1;
1079}
1080
1081/*
1082 * This variant of list_concat_unique() operates upon lists of OIDs.
1083 */
1084List *
1085list_concat_unique_oid(List *list1, List *list2)
1086{
1087 ListCell *cell;
1088
1089 Assert(IsOidList(list1));
1090 Assert(IsOidList(list2));
1091
1092 foreach(cell, list2)
1093 {
1094 if (!list_member_oid(list1, lfirst_oid(cell)))
1095 list1 = lappend_oid(list1, lfirst_oid(cell));
1096 }
1097
1098 check_list_invariants(list1);
1099 return list1;
1100}
1101
1102/*
1103 * Free all storage in a list, and optionally the pointed-to elements
1104 */
1105static void
1106list_free_private(List *list, bool deep)
1107{
1108 ListCell *cell;
1109
1110 check_list_invariants(list);
1111
1112 cell = list_head(list);
1113 while (cell != NULL)
1114 {
1115 ListCell *tmp = cell;
1116
1117 cell = lnext(cell);
1118 if (deep)
1119 pfree(lfirst(tmp));
1120 pfree(tmp);
1121 }
1122
1123 if (list)
1124 pfree(list);
1125}
1126
1127/*
1128 * Free all the cells of the list, as well as the list itself. Any
1129 * objects that are pointed-to by the cells of the list are NOT
1130 * free'd.
1131 *
1132 * On return, the argument to this function has been freed, so the
1133 * caller would be wise to set it to NIL for safety's sake.
1134 */
1135void
1136list_free(List *list)
1137{
1138 list_free_private(list, false);
1139}
1140
1141/*
1142 * Free all the cells of the list, the list itself, and all the
1143 * objects pointed-to by the cells of the list (each element in the
1144 * list must contain a pointer to a palloc()'d region of memory!)
1145 *
1146 * On return, the argument to this function has been freed, so the
1147 * caller would be wise to set it to NIL for safety's sake.
1148 */
1149void
1150list_free_deep(List *list)
1151{
1152 /*
1153 * A "deep" free operation only makes sense on a list of pointers.
1154 */
1155 Assert(IsPointerList(list));
1156 list_free_private(list, true);
1157}
1158
1159/*
1160 * Return a shallow copy of the specified list.
1161 */
1162List *
1163list_copy(const List *oldlist)
1164{
1165 List *newlist;
1166 ListCell *newlist_prev;
1167 ListCell *oldlist_cur;
1168
1169 if (oldlist == NIL)
1170 return NIL;
1171
1172 newlist = new_list(oldlist->type);
1173 newlist->length = oldlist->length;
1174
1175 /*
1176 * Copy over the data in the first cell; new_list() has already allocated
1177 * the head cell itself
1178 */
1179 newlist->head->data = oldlist->head->data;
1180
1181 newlist_prev = newlist->head;
1182 oldlist_cur = oldlist->head->next;
1183 while (oldlist_cur)
1184 {
1185 ListCell *newlist_cur;
1186
1187 newlist_cur = (ListCell *) palloc(sizeof(*newlist_cur));
1188 newlist_cur->data = oldlist_cur->data;
1189 newlist_prev->next = newlist_cur;
1190
1191 newlist_prev = newlist_cur;
1192 oldlist_cur = oldlist_cur->next;
1193 }
1194
1195 newlist_prev->next = NULL;
1196 newlist->tail = newlist_prev;
1197
1198 check_list_invariants(newlist);
1199 return newlist;
1200}
1201
1202/*
1203 * Return a shallow copy of the specified list, without the first N elements.
1204 */
1205List *
1206list_copy_tail(const List *oldlist, int nskip)
1207{
1208 List *newlist;
1209 ListCell *newlist_prev;
1210 ListCell *oldlist_cur;
1211
1212 if (nskip < 0)
1213 nskip = 0; /* would it be better to elog? */
1214
1215 if (oldlist == NIL || nskip >= oldlist->length)
1216 return NIL;
1217
1218 newlist = new_list(oldlist->type);
1219 newlist->length = oldlist->length - nskip;
1220
1221 /*
1222 * Skip over the unwanted elements.
1223 */
1224 oldlist_cur = oldlist->head;
1225 while (nskip-- > 0)
1226 oldlist_cur = oldlist_cur->next;
1227
1228 /*
1229 * Copy over the data in the first remaining cell; new_list() has already
1230 * allocated the head cell itself
1231 */
1232 newlist->head->data = oldlist_cur->data;
1233
1234 newlist_prev = newlist->head;
1235 oldlist_cur = oldlist_cur->next;
1236 while (oldlist_cur)
1237 {
1238 ListCell *newlist_cur;
1239
1240 newlist_cur = (ListCell *) palloc(sizeof(*newlist_cur));
1241 newlist_cur->data = oldlist_cur->data;
1242 newlist_prev->next = newlist_cur;
1243
1244 newlist_prev = newlist_cur;
1245 oldlist_cur = oldlist_cur->next;
1246 }
1247
1248 newlist_prev->next = NULL;
1249 newlist->tail = newlist_prev;
1250
1251 check_list_invariants(newlist);
1252 return newlist;
1253}
1254
1255/*
1256 * Sort a list as though by qsort.
1257 *
1258 * A new list is built and returned. Like list_copy, this doesn't make
1259 * fresh copies of any pointed-to data.
1260 *
1261 * The comparator function receives arguments of type ListCell **.
1262 */
1263List *
1264list_qsort(const List *list, list_qsort_comparator cmp)
1265{
1266 int len = list_length(list);
1267 ListCell **list_arr;
1268 List *newlist;
1269 ListCell *newlist_prev;
1270 ListCell *cell;
1271 int i;
1272
1273 /* Empty list is easy */
1274 if (len == 0)
1275 return NIL;
1276
1277 /* Flatten list cells into an array, so we can use qsort */
1278 list_arr = (ListCell **) palloc(sizeof(ListCell *) * len);
1279 i = 0;
1280 foreach(cell, list)
1281 list_arr[i++] = cell;
1282
1283 qsort(list_arr, len, sizeof(ListCell *), cmp);
1284
1285 /* Construct new list (this code is much like list_copy) */
1286 newlist = new_list(list->type);
1287 newlist->length = len;
1288
1289 /*
1290 * Copy over the data in the first cell; new_list() has already allocated
1291 * the head cell itself
1292 */
1293 newlist->head->data = list_arr[0]->data;
1294
1295 newlist_prev = newlist->head;
1296 for (i = 1; i < len; i++)
1297 {
1298 ListCell *newlist_cur;
1299
1300 newlist_cur = (ListCell *) palloc(sizeof(*newlist_cur));
1301 newlist_cur->data = list_arr[i]->data;
1302 newlist_prev->next = newlist_cur;
1303
1304 newlist_prev = newlist_cur;
1305 }
1306
1307 newlist_prev->next = NULL;
1308 newlist->tail = newlist_prev;
1309
1310 /* Might as well free the workspace array */
1311 pfree(list_arr);
1312
1313 check_list_invariants(newlist);
1314 return newlist;
1315}
1316
1317/*
1318 * Temporary compatibility functions
1319 *
1320 * In order to avoid warnings for these function definitions, we need
1321 * to include a prototype here as well as in pg_list.h. That's because
1322 * we don't enable list API compatibility in list.c, so we
1323 * don't see the prototypes for these functions.
1324 */
1325
1326/*
1327 * Given a list, return its length. This is merely defined for the
1328 * sake of backward compatibility: we can't afford to define a macro
1329 * called "length", so it must be a function. New code should use the
1330 * list_length() macro in order to avoid the overhead of a function
1331 * call.
1332 */
1333int length(const List *list);
1334
1335int
1336length(const List *list)
1337{
1338 return list_length(list);
1339}
1340