1 /*-------------------------------------------------------------------------
4 * implementation for PostgreSQL generic linked list package
7 * Portions Copyright (c) 1996-2015, PostgreSQL Global Development Group
8 * Portions Copyright (c) 1994, Regents of the University of California
12 * src/backend/nodes/list.c
14 *-------------------------------------------------------------------------
19 #define PG_LIST_INCLUDE_DEFINITIONS
21 #include "nodes/pg_list.h"
25 * Routines to simplify writing assertions about the type of a list; a
26 * NIL list is considered to be an empty list of any type.
28 #define IsPointerList(l) ((l) == NIL || IsA((l), List))
29 #define IsIntegerList(l) ((l) == NIL || IsA((l), IntList))
30 #define IsOidList(l) ((l) == NIL || IsA((l), OidList))
32 #ifdef USE_ASSERT_CHECKING
34 * Check that the specified List is valid (so far as we can tell).
37 check_list_invariants(const List *list)
42 Assert(list->length > 0);
43 Assert(list->head != NULL);
44 Assert(list->tail != NULL);
46 Assert(list->type == T_List ||
47 list->type == T_IntList ||
48 list->type == T_OidList);
50 if (list->length == 1)
51 Assert(list->head == list->tail);
52 if (list->length == 2)
53 Assert(list->head->next == list->tail);
54 Assert(list->tail->next == NULL);
57 #define check_list_invariants(l)
58 #endif /* USE_ASSERT_CHECKING */
61 * Return a freshly allocated List. Since empty non-NIL lists are
62 * invalid, new_list() also allocates the head cell of the new list:
63 * the caller should be sure to fill in that cell's data.
66 new_list(NodeTag type)
71 new_head = (ListCell *) palloc(sizeof(*new_head));
72 new_head->next = NULL;
73 /* new_head->data is left undefined! */
75 new_list = (List *) palloc(sizeof(*new_list));
76 new_list->type = type;
78 new_list->head = new_head;
79 new_list->tail = new_head;
85 * Allocate a new cell and make it the head of the specified
86 * list. Assumes the list it is passed is non-NIL.
88 * The data in the new head cell is undefined; the caller should be
92 new_head_cell(List *list)
96 new_head = (ListCell *) palloc(sizeof(*new_head));
97 new_head->next = list->head;
99 list->head = new_head;
104 * Allocate a new cell and make it the tail of the specified
105 * list. Assumes the list it is passed is non-NIL.
107 * The data in the new tail cell is undefined; the caller should be
111 new_tail_cell(List *list)
115 new_tail = (ListCell *) palloc(sizeof(*new_tail));
116 new_tail->next = NULL;
118 list->tail->next = new_tail;
119 list->tail = new_tail;
124 * Append a pointer to the list. A pointer to the modified list is
125 * returned. Note that this function may or may not destructively
126 * modify the list; callers should always use this function's return
127 * value, rather than continuing to use the pointer passed as the
131 lappend(List *list, void *datum)
133 Assert(IsPointerList(list));
136 list = new_list(T_List);
140 lfirst(list->tail) = datum;
141 check_list_invariants(list);
146 * Append an integer to the specified list. See lappend()
149 lappend_int(List *list, int datum)
151 Assert(IsIntegerList(list));
154 list = new_list(T_IntList);
158 lfirst_int(list->tail) = datum;
159 check_list_invariants(list);
164 * Append an OID to the specified list. See lappend()
167 lappend_oid(List *list, Oid datum)
169 Assert(IsOidList(list));
172 list = new_list(T_OidList);
176 lfirst_oid(list->tail) = datum;
177 check_list_invariants(list);
182 * Add a new cell to the list, in the position after 'prev_cell'. The
183 * data in the cell is left undefined, and must be filled in by the
184 * caller. 'list' is assumed to be non-NIL, and 'prev_cell' is assumed
185 * to be non-NULL and a member of 'list'.
188 add_new_cell(List *list, ListCell *prev_cell)
192 new_cell = (ListCell *) palloc(sizeof(*new_cell));
193 /* new_cell->data is left undefined! */
194 new_cell->next = prev_cell->next;
195 prev_cell->next = new_cell;
197 if (list->tail == prev_cell)
198 list->tail = new_cell;
206 * Add a new cell to the specified list (which must be non-NIL);
207 * it will be placed after the list cell 'prev' (which must be
208 * non-NULL and a member of 'list'). The data placed in the new cell
209 * is 'datum'. The newly-constructed cell is returned.
212 lappend_cell(List *list, ListCell *prev, void *datum)
216 Assert(IsPointerList(list));
218 new_cell = add_new_cell(list, prev);
219 lfirst(new_cell) = datum;
220 check_list_invariants(list);
225 lappend_cell_int(List *list, ListCell *prev, int datum)
229 Assert(IsIntegerList(list));
231 new_cell = add_new_cell(list, prev);
232 lfirst_int(new_cell) = datum;
233 check_list_invariants(list);
238 lappend_cell_oid(List *list, ListCell *prev, Oid datum)
242 Assert(IsOidList(list));
244 new_cell = add_new_cell(list, prev);
245 lfirst_oid(new_cell) = datum;
246 check_list_invariants(list);
251 * Prepend a new element to the list. A pointer to the modified list
252 * is returned. Note that this function may or may not destructively
253 * modify the list; callers should always use this function's return
254 * value, rather than continuing to use the pointer passed as the
257 * Caution: before Postgres 8.0, the original List was unmodified and
258 * could be considered to retain its separate identity. This is no longer
262 lcons(void *datum, List *list)
264 Assert(IsPointerList(list));
267 list = new_list(T_List);
271 lfirst(list->head) = datum;
272 check_list_invariants(list);
277 * Prepend an integer to the list. See lcons()
280 lcons_int(int datum, List *list)
282 Assert(IsIntegerList(list));
285 list = new_list(T_IntList);
289 lfirst_int(list->head) = datum;
290 check_list_invariants(list);
295 * Prepend an OID to the list. See lcons()
298 lcons_oid(Oid datum, List *list)
300 Assert(IsOidList(list));
303 list = new_list(T_OidList);
307 lfirst_oid(list->head) = datum;
308 check_list_invariants(list);
313 * Concatenate list2 to the end of list1, and return list1. list1 is
314 * destructively changed. Callers should be sure to use the return
315 * value as the new pointer to the concatenated list: the 'list1'
316 * input pointer may or may not be the same as the returned pointer.
318 * The nodes in list2 are merely appended to the end of list1 in-place
319 * (i.e. they aren't copied; the two lists will share some of the same
320 * storage). Therefore, invoking list_free() on list2 will also
321 * invalidate a portion of list1.
324 list_concat(List *list1, List *list2)
331 elog(ERROR, "cannot list_concat() a list to itself");
333 Assert(list1->type == list2->type);
335 list1->length += list2->length;
336 list1->tail->next = list2->head;
337 list1->tail = list2->tail;
339 check_list_invariants(list1);
344 * Truncate 'list' to contain no more than 'new_size' elements. This
345 * modifies the list in-place! Despite this, callers should use the
346 * pointer returned by this function to refer to the newly truncated
347 * list -- it may or may not be the same as the pointer that was
350 * Note that any cells removed by list_truncate() are NOT pfree'd.
353 list_truncate(List *list, int new_size)
359 return NIL; /* truncate to zero length */
361 /* If asked to effectively extend the list, do nothing */
362 if (new_size >= list_length(list))
372 list->length = new_size;
373 check_list_invariants(list);
379 /* keep the compiler quiet; never reached */
385 * Locate the n'th cell (counting from 0) of the list. It is an assertion
386 * failure if there is no such cell.
389 list_nth_cell(const List *list, int n)
395 Assert(n < list->length);
396 check_list_invariants(list);
398 /* Does the caller actually mean to fetch the tail? */
399 if (n == list->length - 1)
402 for (match = list->head; n-- > 0; match = match->next)
409 * Return the data value contained in the n'th element of the
410 * specified list. (List elements begin at 0.)
413 list_nth(const List *list, int n)
415 Assert(IsPointerList(list));
416 return lfirst(list_nth_cell(list, n));
420 * Return the integer value contained in the n'th element of the
424 list_nth_int(const List *list, int n)
426 Assert(IsIntegerList(list));
427 return lfirst_int(list_nth_cell(list, n));
431 * Return the OID value contained in the n'th element of the specified
435 list_nth_oid(const List *list, int n)
437 Assert(IsOidList(list));
438 return lfirst_oid(list_nth_cell(list, n));
442 * Return true iff 'datum' is a member of the list. Equality is
443 * determined via equal(), so callers should ensure that they pass a
447 list_member(const List *list, const void *datum)
449 const ListCell *cell;
451 Assert(IsPointerList(list));
452 check_list_invariants(list);
456 if (equal(lfirst(cell), datum))
464 * Return true iff 'datum' is a member of the list. Equality is
465 * determined by using simple pointer comparison.
468 list_member_ptr(const List *list, const void *datum)
470 const ListCell *cell;
472 Assert(IsPointerList(list));
473 check_list_invariants(list);
477 if (lfirst(cell) == datum)
485 * Return true iff the integer 'datum' is a member of the list.
488 list_member_int(const List *list, int datum)
490 const ListCell *cell;
492 Assert(IsIntegerList(list));
493 check_list_invariants(list);
497 if (lfirst_int(cell) == datum)
505 * Return true iff the OID 'datum' is a member of the list.
508 list_member_oid(const List *list, Oid datum)
510 const ListCell *cell;
512 Assert(IsOidList(list));
513 check_list_invariants(list);
517 if (lfirst_oid(cell) == datum)
525 * Delete 'cell' from 'list'; 'prev' is the previous element to 'cell'
526 * in 'list', if any (i.e. prev == NULL iff list->head == cell)
528 * The cell is pfree'd, as is the List header if this was the last member.
531 list_delete_cell(List *list, ListCell *cell, ListCell *prev)
533 check_list_invariants(list);
534 Assert(prev != NULL ? lnext(prev) == cell : list_head(list) == cell);
537 * If we're about to delete the last node from the list, free the whole
538 * list instead and return NIL, which is the only valid representation of
539 * a zero-length list.
541 if (list->length == 1)
548 * Otherwise, adjust the necessary list links, deallocate the particular
549 * node we have just removed, and return the list we were given.
554 prev->next = cell->next;
556 list->head = cell->next;
558 if (list->tail == cell)
566 * Delete the first cell in list that matches datum, if any.
567 * Equality is determined via equal().
570 list_delete(List *list, void *datum)
575 Assert(IsPointerList(list));
576 check_list_invariants(list);
581 if (equal(lfirst(cell), datum))
582 return list_delete_cell(list, cell, prev);
587 /* Didn't find a match: return the list unmodified */
591 /* As above, but use simple pointer equality */
593 list_delete_ptr(List *list, void *datum)
598 Assert(IsPointerList(list));
599 check_list_invariants(list);
604 if (lfirst(cell) == datum)
605 return list_delete_cell(list, cell, prev);
610 /* Didn't find a match: return the list unmodified */
614 /* As above, but for integers */
616 list_delete_int(List *list, int datum)
621 Assert(IsIntegerList(list));
622 check_list_invariants(list);
627 if (lfirst_int(cell) == datum)
628 return list_delete_cell(list, cell, prev);
633 /* Didn't find a match: return the list unmodified */
637 /* As above, but for OIDs */
639 list_delete_oid(List *list, Oid datum)
644 Assert(IsOidList(list));
645 check_list_invariants(list);
650 if (lfirst_oid(cell) == datum)
651 return list_delete_cell(list, cell, prev);
656 /* Didn't find a match: return the list unmodified */
661 * Delete the first element of the list.
663 * This is useful to replace the Lisp-y code "list = lnext(list);" in cases
664 * where the intent is to alter the list rather than just traverse it.
665 * Beware that the removed cell is freed, whereas the lnext() coding leaves
666 * the original list head intact if there's another pointer to it.
669 list_delete_first(List *list)
671 check_list_invariants(list);
674 return NIL; /* would an error be better? */
676 return list_delete_cell(list, list_head(list), NULL);
680 * Generate the union of two lists. This is calculated by copying
681 * list1 via list_copy(), then adding to it all the members of list2
682 * that aren't already in list1.
684 * Whether an element is already a member of the list is determined
687 * The returned list is newly-allocated, although the content of the
688 * cells is the same (i.e. any pointed-to objects are not copied).
690 * NB: this function will NOT remove any duplicates that are present
691 * in list1 (so it only performs a "union" if list1 is known unique to
692 * start with). Also, if you are about to write "x = list_union(x, y)"
693 * you probably want to use list_concat_unique() instead to avoid wasting
694 * the list cells of the old x list.
696 * This function could probably be implemented a lot faster if it is a
697 * performance bottleneck.
700 list_union(const List *list1, const List *list2)
703 const ListCell *cell;
705 Assert(IsPointerList(list1));
706 Assert(IsPointerList(list2));
708 result = list_copy(list1);
711 if (!list_member(result, lfirst(cell)))
712 result = lappend(result, lfirst(cell));
715 check_list_invariants(result);
720 * This variant of list_union() determines duplicates via simple
721 * pointer comparison.
724 list_union_ptr(const List *list1, const List *list2)
727 const ListCell *cell;
729 Assert(IsPointerList(list1));
730 Assert(IsPointerList(list2));
732 result = list_copy(list1);
735 if (!list_member_ptr(result, lfirst(cell)))
736 result = lappend(result, lfirst(cell));
739 check_list_invariants(result);
744 * This variant of list_union() operates upon lists of integers.
747 list_union_int(const List *list1, const List *list2)
750 const ListCell *cell;
752 Assert(IsIntegerList(list1));
753 Assert(IsIntegerList(list2));
755 result = list_copy(list1);
758 if (!list_member_int(result, lfirst_int(cell)))
759 result = lappend_int(result, lfirst_int(cell));
762 check_list_invariants(result);
767 * This variant of list_union() operates upon lists of OIDs.
770 list_union_oid(const List *list1, const List *list2)
773 const ListCell *cell;
775 Assert(IsOidList(list1));
776 Assert(IsOidList(list2));
778 result = list_copy(list1);
781 if (!list_member_oid(result, lfirst_oid(cell)))
782 result = lappend_oid(result, lfirst_oid(cell));
785 check_list_invariants(result);
790 * Return a list that contains all the cells that are in both list1 and
791 * list2. The returned list is freshly allocated via palloc(), but the
792 * cells themselves point to the same objects as the cells of the
795 * Duplicate entries in list1 will not be suppressed, so it's only a true
796 * "intersection" if list1 is known unique beforehand.
798 * This variant works on lists of pointers, and determines list
799 * membership via equal(). Note that the list1 member will be pointed
803 list_intersection(const List *list1, const List *list2)
806 const ListCell *cell;
808 if (list1 == NIL || list2 == NIL)
811 Assert(IsPointerList(list1));
812 Assert(IsPointerList(list2));
817 if (list_member(list2, lfirst(cell)))
818 result = lappend(result, lfirst(cell));
821 check_list_invariants(result);
826 * As list_intersection but operates on lists of integers.
829 list_intersection_int(const List *list1, const List *list2)
832 const ListCell *cell;
834 if (list1 == NIL || list2 == NIL)
837 Assert(IsIntegerList(list1));
838 Assert(IsIntegerList(list2));
843 if (list_member_int(list2, lfirst_int(cell)))
844 result = lappend_int(result, lfirst_int(cell));
847 check_list_invariants(result);
852 * Return a list that contains all the cells in list1 that are not in
853 * list2. The returned list is freshly allocated via palloc(), but the
854 * cells themselves point to the same objects as the cells of the
857 * This variant works on lists of pointers, and determines list
858 * membership via equal()
861 list_difference(const List *list1, const List *list2)
863 const ListCell *cell;
866 Assert(IsPointerList(list1));
867 Assert(IsPointerList(list2));
870 return list_copy(list1);
874 if (!list_member(list2, lfirst(cell)))
875 result = lappend(result, lfirst(cell));
878 check_list_invariants(result);
883 * This variant of list_difference() determines list membership via
884 * simple pointer equality.
887 list_difference_ptr(const List *list1, const List *list2)
889 const ListCell *cell;
892 Assert(IsPointerList(list1));
893 Assert(IsPointerList(list2));
896 return list_copy(list1);
900 if (!list_member_ptr(list2, lfirst(cell)))
901 result = lappend(result, lfirst(cell));
904 check_list_invariants(result);
909 * This variant of list_difference() operates upon lists of integers.
912 list_difference_int(const List *list1, const List *list2)
914 const ListCell *cell;
917 Assert(IsIntegerList(list1));
918 Assert(IsIntegerList(list2));
921 return list_copy(list1);
925 if (!list_member_int(list2, lfirst_int(cell)))
926 result = lappend_int(result, lfirst_int(cell));
929 check_list_invariants(result);
934 * This variant of list_difference() operates upon lists of OIDs.
937 list_difference_oid(const List *list1, const List *list2)
939 const ListCell *cell;
942 Assert(IsOidList(list1));
943 Assert(IsOidList(list2));
946 return list_copy(list1);
950 if (!list_member_oid(list2, lfirst_oid(cell)))
951 result = lappend_oid(result, lfirst_oid(cell));
954 check_list_invariants(result);
959 * Append datum to list, but only if it isn't already in the list.
961 * Whether an element is already a member of the list is determined
965 list_append_unique(List *list, void *datum)
967 if (list_member(list, datum))
970 return lappend(list, datum);
974 * This variant of list_append_unique() determines list membership via
975 * simple pointer equality.
978 list_append_unique_ptr(List *list, void *datum)
980 if (list_member_ptr(list, datum))
983 return lappend(list, datum);
987 * This variant of list_append_unique() operates upon lists of integers.
990 list_append_unique_int(List *list, int datum)
992 if (list_member_int(list, datum))
995 return lappend_int(list, datum);
999 * This variant of list_append_unique() operates upon lists of OIDs.
1002 list_append_unique_oid(List *list, Oid datum)
1004 if (list_member_oid(list, datum))
1007 return lappend_oid(list, datum);
1011 * Append to list1 each member of list2 that isn't already in list1.
1013 * Whether an element is already a member of the list is determined
1016 * This is almost the same functionality as list_union(), but list1 is
1017 * modified in-place rather than being copied. Note also that list2's cells
1018 * are not inserted in list1, so the analogy to list_concat() isn't perfect.
1021 list_concat_unique(List *list1, List *list2)
1025 Assert(IsPointerList(list1));
1026 Assert(IsPointerList(list2));
1028 foreach(cell, list2)
1030 if (!list_member(list1, lfirst(cell)))
1031 list1 = lappend(list1, lfirst(cell));
1034 check_list_invariants(list1);
1039 * This variant of list_concat_unique() determines list membership via
1040 * simple pointer equality.
1043 list_concat_unique_ptr(List *list1, List *list2)
1047 Assert(IsPointerList(list1));
1048 Assert(IsPointerList(list2));
1050 foreach(cell, list2)
1052 if (!list_member_ptr(list1, lfirst(cell)))
1053 list1 = lappend(list1, lfirst(cell));
1056 check_list_invariants(list1);
1061 * This variant of list_concat_unique() operates upon lists of integers.
1064 list_concat_unique_int(List *list1, List *list2)
1068 Assert(IsIntegerList(list1));
1069 Assert(IsIntegerList(list2));
1071 foreach(cell, list2)
1073 if (!list_member_int(list1, lfirst_int(cell)))
1074 list1 = lappend_int(list1, lfirst_int(cell));
1077 check_list_invariants(list1);
1082 * This variant of list_concat_unique() operates upon lists of OIDs.
1085 list_concat_unique_oid(List *list1, List *list2)
1089 Assert(IsOidList(list1));
1090 Assert(IsOidList(list2));
1092 foreach(cell, list2)
1094 if (!list_member_oid(list1, lfirst_oid(cell)))
1095 list1 = lappend_oid(list1, lfirst_oid(cell));
1098 check_list_invariants(list1);
1103 * Free all storage in a list, and optionally the pointed-to elements
1106 list_free_private(List *list, bool deep)
1110 check_list_invariants(list);
1112 cell = list_head(list);
1113 while (cell != NULL)
1115 ListCell *tmp = cell;
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
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.
1136 list_free(List *list)
1138 list_free_private(list, false);
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!)
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.
1150 list_free_deep(List *list)
1153 * A "deep" free operation only makes sense on a list of pointers.
1155 Assert(IsPointerList(list));
1156 list_free_private(list, true);
1160 * Return a shallow copy of the specified list.
1163 list_copy(const List *oldlist)
1166 ListCell *newlist_prev;
1167 ListCell *oldlist_cur;
1172 newlist = new_list(oldlist->type);
1173 newlist->length = oldlist->length;
1176 * Copy over the data in the first cell; new_list() has already allocated
1177 * the head cell itself
1179 newlist->head->data = oldlist->head->data;
1181 newlist_prev = newlist->head;
1182 oldlist_cur = oldlist->head->next;
1185 ListCell *newlist_cur;
1187 newlist_cur = (ListCell *) palloc(sizeof(*newlist_cur));
1188 newlist_cur->data = oldlist_cur->data;
1189 newlist_prev->next = newlist_cur;
1191 newlist_prev = newlist_cur;
1192 oldlist_cur = oldlist_cur->next;
1195 newlist_prev->next = NULL;
1196 newlist->tail = newlist_prev;
1198 check_list_invariants(newlist);
1203 * Return a shallow copy of the specified list, without the first N elements.
1206 list_copy_tail(const List *oldlist, int nskip)
1209 ListCell *newlist_prev;
1210 ListCell *oldlist_cur;
1213 nskip = 0; /* would it be better to elog? */
1215 if (oldlist == NIL || nskip >= oldlist->length)
1218 newlist = new_list(oldlist->type);
1219 newlist->length = oldlist->length - nskip;
1222 * Skip over the unwanted elements.
1224 oldlist_cur = oldlist->head;
1226 oldlist_cur = oldlist_cur->next;
1229 * Copy over the data in the first remaining cell; new_list() has already
1230 * allocated the head cell itself
1232 newlist->head->data = oldlist_cur->data;
1234 newlist_prev = newlist->head;
1235 oldlist_cur = oldlist_cur->next;
1238 ListCell *newlist_cur;
1240 newlist_cur = (ListCell *) palloc(sizeof(*newlist_cur));
1241 newlist_cur->data = oldlist_cur->data;
1242 newlist_prev->next = newlist_cur;
1244 newlist_prev = newlist_cur;
1245 oldlist_cur = oldlist_cur->next;
1248 newlist_prev->next = NULL;
1249 newlist->tail = newlist_prev;
1251 check_list_invariants(newlist);
1256 * Temporary compatibility functions
1258 * In order to avoid warnings for these function definitions, we need
1259 * to include a prototype here as well as in pg_list.h. That's because
1260 * we don't enable list API compatibility in list.c, so we
1261 * don't see the prototypes for these functions.
1265 * Given a list, return its length. This is merely defined for the
1266 * sake of backward compatibility: we can't afford to define a macro
1267 * called "length", so it must be a function. New code should use the
1268 * list_length() macro in order to avoid the overhead of a function
1271 int length(const List *list);
1274 length(const List *list)
1276 return list_length(list);