1 /*-------------------------------------------------------------------------
4 * implementation for PostgreSQL generic linked list package
7 * Portions Copyright (c) 1996-2011, PostgreSQL Global Development Group
8 * Portions Copyright (c) 1994, Regents of the University of California
12 * src/backend/nodes/list.c
14 *-------------------------------------------------------------------------
18 #include "nodes/pg_list.h"
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.
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))
29 #ifdef USE_ASSERT_CHECKING
31 * Check that the specified List is valid (so far as we can tell).
34 check_list_invariants(List *list)
39 Assert(list->length > 0);
40 Assert(list->head != NULL);
41 Assert(list->tail != NULL);
43 Assert(list->type == T_List ||
44 list->type == T_IntList ||
45 list->type == T_OidList);
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);
54 #define check_list_invariants(l)
55 #endif /* USE_ASSERT_CHECKING */
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.
63 new_list(NodeTag type)
68 new_head = (ListCell *) palloc(sizeof(*new_head));
69 new_head->next = NULL;
70 /* new_head->data is left undefined! */
72 new_list = (List *) palloc(sizeof(*new_list));
73 new_list->type = type;
75 new_list->head = new_head;
76 new_list->tail = new_head;
82 * Allocate a new cell and make it the head of the specified
83 * list. Assumes the list it is passed is non-NIL.
85 * The data in the new head cell is undefined; the caller should be
89 new_head_cell(List *list)
93 new_head = (ListCell *) palloc(sizeof(*new_head));
94 new_head->next = list->head;
96 list->head = new_head;
101 * Allocate a new cell and make it the tail of the specified
102 * list. Assumes the list it is passed is non-NIL.
104 * The data in the new tail cell is undefined; the caller should be
108 new_tail_cell(List *list)
112 new_tail = (ListCell *) palloc(sizeof(*new_tail));
113 new_tail->next = NULL;
115 list->tail->next = new_tail;
116 list->tail = new_tail;
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
128 lappend(List *list, void *datum)
130 Assert(IsPointerList(list));
133 list = new_list(T_List);
137 lfirst(list->tail) = datum;
138 check_list_invariants(list);
143 * Append an integer to the specified list. See lappend()
146 lappend_int(List *list, int datum)
148 Assert(IsIntegerList(list));
151 list = new_list(T_IntList);
155 lfirst_int(list->tail) = datum;
156 check_list_invariants(list);
161 * Append an OID to the specified list. See lappend()
164 lappend_oid(List *list, Oid datum)
166 Assert(IsOidList(list));
169 list = new_list(T_OidList);
173 lfirst_oid(list->tail) = datum;
174 check_list_invariants(list);
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'.
185 add_new_cell(List *list, ListCell *prev_cell)
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;
194 if (list->tail == prev_cell)
195 list->tail = new_cell;
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.
209 lappend_cell(List *list, ListCell *prev, void *datum)
213 Assert(IsPointerList(list));
215 new_cell = add_new_cell(list, prev);
216 lfirst(new_cell) = datum;
217 check_list_invariants(list);
222 lappend_cell_int(List *list, ListCell *prev, int datum)
226 Assert(IsIntegerList(list));
228 new_cell = add_new_cell(list, prev);
229 lfirst_int(new_cell) = datum;
230 check_list_invariants(list);
235 lappend_cell_oid(List *list, ListCell *prev, Oid datum)
239 Assert(IsOidList(list));
241 new_cell = add_new_cell(list, prev);
242 lfirst_oid(new_cell) = datum;
243 check_list_invariants(list);
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
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
259 lcons(void *datum, List *list)
261 Assert(IsPointerList(list));
264 list = new_list(T_List);
268 lfirst(list->head) = datum;
269 check_list_invariants(list);
274 * Prepend an integer to the list. See lcons()
277 lcons_int(int datum, List *list)
279 Assert(IsIntegerList(list));
282 list = new_list(T_IntList);
286 lfirst_int(list->head) = datum;
287 check_list_invariants(list);
292 * Prepend an OID to the list. See lcons()
295 lcons_oid(Oid datum, List *list)
297 Assert(IsOidList(list));
300 list = new_list(T_OidList);
304 lfirst_oid(list->head) = datum;
305 check_list_invariants(list);
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.
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.
321 list_concat(List *list1, List *list2)
328 elog(ERROR, "cannot list_concat() a list to itself");
330 Assert(list1->type == list2->type);
332 list1->length += list2->length;
333 list1->tail->next = list2->head;
334 list1->tail = list2->tail;
336 check_list_invariants(list1);
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
347 * Note that any cells removed by list_truncate() are NOT pfree'd.
350 list_truncate(List *list, int new_size)
356 return NIL; /* truncate to zero length */
358 /* If asked to effectively extend the list, do nothing */
359 if (new_size >= list_length(list))
369 list->length = new_size;
370 check_list_invariants(list);
376 /* keep the compiler quiet; never reached */
382 * Locate the n'th cell (counting from 0) of the list. It is an assertion
383 * failure if there is no such cell.
386 list_nth_cell(List *list, int n)
392 Assert(n < list->length);
393 check_list_invariants(list);
395 /* Does the caller actually mean to fetch the tail? */
396 if (n == list->length - 1)
399 for (match = list->head; n-- > 0; match = match->next)
406 * Return the data value contained in the n'th element of the
407 * specified list. (List elements begin at 0.)
410 list_nth(List *list, int n)
412 Assert(IsPointerList(list));
413 return lfirst(list_nth_cell(list, n));
417 * Return the integer value contained in the n'th element of the
421 list_nth_int(List *list, int n)
423 Assert(IsIntegerList(list));
424 return lfirst_int(list_nth_cell(list, n));
428 * Return the OID value contained in the n'th element of the specified
432 list_nth_oid(List *list, int n)
434 Assert(IsOidList(list));
435 return lfirst_oid(list_nth_cell(list, n));
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
444 list_member(List *list, void *datum)
448 Assert(IsPointerList(list));
449 check_list_invariants(list);
453 if (equal(lfirst(cell), datum))
461 * Return true iff 'datum' is a member of the list. Equality is
462 * determined by using simple pointer comparison.
465 list_member_ptr(List *list, void *datum)
469 Assert(IsPointerList(list));
470 check_list_invariants(list);
474 if (lfirst(cell) == datum)
482 * Return true iff the integer 'datum' is a member of the list.
485 list_member_int(List *list, int datum)
489 Assert(IsIntegerList(list));
490 check_list_invariants(list);
494 if (lfirst_int(cell) == datum)
502 * Return true iff the OID 'datum' is a member of the list.
505 list_member_oid(List *list, Oid datum)
509 Assert(IsOidList(list));
510 check_list_invariants(list);
514 if (lfirst_oid(cell) == datum)
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)
525 * The cell is pfree'd, as is the List header if this was the last member.
528 list_delete_cell(List *list, ListCell *cell, ListCell *prev)
530 check_list_invariants(list);
531 Assert(prev != NULL ? lnext(prev) == cell : list_head(list) == cell);
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.
538 if (list->length == 1)
545 * Otherwise, adjust the necessary list links, deallocate the particular
546 * node we have just removed, and return the list we were given.
551 prev->next = cell->next;
553 list->head = cell->next;
555 if (list->tail == cell)
563 * Delete the first cell in list that matches datum, if any.
564 * Equality is determined via equal().
567 list_delete(List *list, void *datum)
572 Assert(IsPointerList(list));
573 check_list_invariants(list);
578 if (equal(lfirst(cell), datum))
579 return list_delete_cell(list, cell, prev);
584 /* Didn't find a match: return the list unmodified */
588 /* As above, but use simple pointer equality */
590 list_delete_ptr(List *list, void *datum)
595 Assert(IsPointerList(list));
596 check_list_invariants(list);
601 if (lfirst(cell) == datum)
602 return list_delete_cell(list, cell, prev);
607 /* Didn't find a match: return the list unmodified */
611 /* As above, but for integers */
613 list_delete_int(List *list, int datum)
618 Assert(IsIntegerList(list));
619 check_list_invariants(list);
624 if (lfirst_int(cell) == datum)
625 return list_delete_cell(list, cell, prev);
630 /* Didn't find a match: return the list unmodified */
634 /* As above, but for OIDs */
636 list_delete_oid(List *list, Oid datum)
641 Assert(IsOidList(list));
642 check_list_invariants(list);
647 if (lfirst_oid(cell) == datum)
648 return list_delete_cell(list, cell, prev);
653 /* Didn't find a match: return the list unmodified */
658 * Delete the first element of the list.
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.
666 list_delete_first(List *list)
668 check_list_invariants(list);
671 return NIL; /* would an error be better? */
673 return list_delete_cell(list, list_head(list), NULL);
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.
681 * Whether an element is already a member of the list is determined
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).
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.
693 * This function could probably be implemented a lot faster if it is a
694 * performance bottleneck.
697 list_union(List *list1, List *list2)
702 Assert(IsPointerList(list1));
703 Assert(IsPointerList(list2));
705 result = list_copy(list1);
708 if (!list_member(result, lfirst(cell)))
709 result = lappend(result, lfirst(cell));
712 check_list_invariants(result);
717 * This variant of list_union() determines duplicates via simple
718 * pointer comparison.
721 list_union_ptr(List *list1, List *list2)
726 Assert(IsPointerList(list1));
727 Assert(IsPointerList(list2));
729 result = list_copy(list1);
732 if (!list_member_ptr(result, lfirst(cell)))
733 result = lappend(result, lfirst(cell));
736 check_list_invariants(result);
741 * This variant of list_union() operates upon lists of integers.
744 list_union_int(List *list1, List *list2)
749 Assert(IsIntegerList(list1));
750 Assert(IsIntegerList(list2));
752 result = list_copy(list1);
755 if (!list_member_int(result, lfirst_int(cell)))
756 result = lappend_int(result, lfirst_int(cell));
759 check_list_invariants(result);
764 * This variant of list_union() operates upon lists of OIDs.
767 list_union_oid(List *list1, List *list2)
772 Assert(IsOidList(list1));
773 Assert(IsOidList(list2));
775 result = list_copy(list1);
778 if (!list_member_oid(result, lfirst_oid(cell)))
779 result = lappend_oid(result, lfirst_oid(cell));
782 check_list_invariants(result);
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
792 * Duplicate entries in list1 will not be suppressed, so it's only a true
793 * "intersection" if list1 is known unique beforehand.
795 * This variant works on lists of pointers, and determines list
796 * membership via equal(). Note that the list1 member will be pointed
800 list_intersection(List *list1, List *list2)
805 if (list1 == NIL || list2 == NIL)
808 Assert(IsPointerList(list1));
809 Assert(IsPointerList(list2));
814 if (list_member(list2, lfirst(cell)))
815 result = lappend(result, lfirst(cell));
818 check_list_invariants(result);
823 * Return a list that contains all the cells in list1 that are not in
824 * list2. The returned list is freshly allocated via palloc(), but the
825 * cells themselves point to the same objects as the cells of the
828 * This variant works on lists of pointers, and determines list
829 * membership via equal()
832 list_difference(List *list1, List *list2)
837 Assert(IsPointerList(list1));
838 Assert(IsPointerList(list2));
841 return list_copy(list1);
845 if (!list_member(list2, lfirst(cell)))
846 result = lappend(result, lfirst(cell));
849 check_list_invariants(result);
854 * This variant of list_difference() determines list membership via
855 * simple pointer equality.
858 list_difference_ptr(List *list1, List *list2)
863 Assert(IsPointerList(list1));
864 Assert(IsPointerList(list2));
867 return list_copy(list1);
871 if (!list_member_ptr(list2, lfirst(cell)))
872 result = lappend(result, lfirst(cell));
875 check_list_invariants(result);
880 * This variant of list_difference() operates upon lists of integers.
883 list_difference_int(List *list1, List *list2)
888 Assert(IsIntegerList(list1));
889 Assert(IsIntegerList(list2));
892 return list_copy(list1);
896 if (!list_member_int(list2, lfirst_int(cell)))
897 result = lappend_int(result, lfirst_int(cell));
900 check_list_invariants(result);
905 * This variant of list_difference() operates upon lists of OIDs.
908 list_difference_oid(List *list1, List *list2)
913 Assert(IsOidList(list1));
914 Assert(IsOidList(list2));
917 return list_copy(list1);
921 if (!list_member_oid(list2, lfirst_oid(cell)))
922 result = lappend_oid(result, lfirst_oid(cell));
925 check_list_invariants(result);
930 * Append datum to list, but only if it isn't already in the list.
932 * Whether an element is already a member of the list is determined
936 list_append_unique(List *list, void *datum)
938 if (list_member(list, datum))
941 return lappend(list, datum);
945 * This variant of list_append_unique() determines list membership via
946 * simple pointer equality.
949 list_append_unique_ptr(List *list, void *datum)
951 if (list_member_ptr(list, datum))
954 return lappend(list, datum);
958 * This variant of list_append_unique() operates upon lists of integers.
961 list_append_unique_int(List *list, int datum)
963 if (list_member_int(list, datum))
966 return lappend_int(list, datum);
970 * This variant of list_append_unique() operates upon lists of OIDs.
973 list_append_unique_oid(List *list, Oid datum)
975 if (list_member_oid(list, datum))
978 return lappend_oid(list, datum);
982 * Append to list1 each member of list2 that isn't already in list1.
984 * Whether an element is already a member of the list is determined
987 * This is almost the same functionality as list_union(), but list1 is
988 * modified in-place rather than being copied. Note also that list2's cells
989 * are not inserted in list1, so the analogy to list_concat() isn't perfect.
992 list_concat_unique(List *list1, List *list2)
996 Assert(IsPointerList(list1));
997 Assert(IsPointerList(list2));
1001 if (!list_member(list1, lfirst(cell)))
1002 list1 = lappend(list1, lfirst(cell));
1005 check_list_invariants(list1);
1010 * This variant of list_concat_unique() determines list membership via
1011 * simple pointer equality.
1014 list_concat_unique_ptr(List *list1, List *list2)
1018 Assert(IsPointerList(list1));
1019 Assert(IsPointerList(list2));
1021 foreach(cell, list2)
1023 if (!list_member_ptr(list1, lfirst(cell)))
1024 list1 = lappend(list1, lfirst(cell));
1027 check_list_invariants(list1);
1032 * This variant of list_concat_unique() operates upon lists of integers.
1035 list_concat_unique_int(List *list1, List *list2)
1039 Assert(IsIntegerList(list1));
1040 Assert(IsIntegerList(list2));
1042 foreach(cell, list2)
1044 if (!list_member_int(list1, lfirst_int(cell)))
1045 list1 = lappend_int(list1, lfirst_int(cell));
1048 check_list_invariants(list1);
1053 * This variant of list_concat_unique() operates upon lists of OIDs.
1056 list_concat_unique_oid(List *list1, List *list2)
1060 Assert(IsOidList(list1));
1061 Assert(IsOidList(list2));
1063 foreach(cell, list2)
1065 if (!list_member_oid(list1, lfirst_oid(cell)))
1066 list1 = lappend_oid(list1, lfirst_oid(cell));
1069 check_list_invariants(list1);
1074 * Free all storage in a list, and optionally the pointed-to elements
1077 list_free_private(List *list, bool deep)
1081 check_list_invariants(list);
1083 cell = list_head(list);
1084 while (cell != NULL)
1086 ListCell *tmp = cell;
1099 * Free all the cells of the list, as well as the list itself. Any
1100 * objects that are pointed-to by the cells of the list are NOT
1103 * On return, the argument to this function has been freed, so the
1104 * caller would be wise to set it to NIL for safety's sake.
1107 list_free(List *list)
1109 list_free_private(list, false);
1113 * Free all the cells of the list, the list itself, and all the
1114 * objects pointed-to by the cells of the list (each element in the
1115 * list must contain a pointer to a palloc()'d region of memory!)
1117 * On return, the argument to this function has been freed, so the
1118 * caller would be wise to set it to NIL for safety's sake.
1121 list_free_deep(List *list)
1124 * A "deep" free operation only makes sense on a list of pointers.
1126 Assert(IsPointerList(list));
1127 list_free_private(list, true);
1131 * Return a shallow copy of the specified list.
1134 list_copy(List *oldlist)
1137 ListCell *newlist_prev;
1138 ListCell *oldlist_cur;
1143 newlist = new_list(oldlist->type);
1144 newlist->length = oldlist->length;
1147 * Copy over the data in the first cell; new_list() has already allocated
1148 * the head cell itself
1150 newlist->head->data = oldlist->head->data;
1152 newlist_prev = newlist->head;
1153 oldlist_cur = oldlist->head->next;
1156 ListCell *newlist_cur;
1158 newlist_cur = (ListCell *) palloc(sizeof(*newlist_cur));
1159 newlist_cur->data = oldlist_cur->data;
1160 newlist_prev->next = newlist_cur;
1162 newlist_prev = newlist_cur;
1163 oldlist_cur = oldlist_cur->next;
1166 newlist_prev->next = NULL;
1167 newlist->tail = newlist_prev;
1169 check_list_invariants(newlist);
1174 * Return a shallow copy of the specified list, without the first N elements.
1177 list_copy_tail(List *oldlist, int nskip)
1180 ListCell *newlist_prev;
1181 ListCell *oldlist_cur;
1184 nskip = 0; /* would it be better to elog? */
1186 if (oldlist == NIL || nskip >= oldlist->length)
1189 newlist = new_list(oldlist->type);
1190 newlist->length = oldlist->length - nskip;
1193 * Skip over the unwanted elements.
1195 oldlist_cur = oldlist->head;
1197 oldlist_cur = oldlist_cur->next;
1200 * Copy over the data in the first remaining cell; new_list() has already
1201 * allocated the head cell itself
1203 newlist->head->data = oldlist_cur->data;
1205 newlist_prev = newlist->head;
1206 oldlist_cur = oldlist_cur->next;
1209 ListCell *newlist_cur;
1211 newlist_cur = (ListCell *) palloc(sizeof(*newlist_cur));
1212 newlist_cur->data = oldlist_cur->data;
1213 newlist_prev->next = newlist_cur;
1215 newlist_prev = newlist_cur;
1216 oldlist_cur = oldlist_cur->next;
1219 newlist_prev->next = NULL;
1220 newlist->tail = newlist_prev;
1222 check_list_invariants(newlist);
1227 * pg_list.h defines inline versions of these functions if allowed by the
1228 * compiler; in which case the definitions below are skipped.
1235 return l ? l->head : NULL;
1241 return l ? l->tail : NULL;
1245 list_length(List *l)
1247 return l ? l->length : 0;
1249 #endif /* ! USE_INLINE */
1252 * Temporary compatibility functions
1254 * In order to avoid warnings for these function definitions, we need
1255 * to include a prototype here as well as in pg_list.h. That's because
1256 * we don't enable list API compatibility in list.c, so we
1257 * don't see the prototypes for these functions.
1261 * Given a list, return its length. This is merely defined for the
1262 * sake of backward compatibility: we can't afford to define a macro
1263 * called "length", so it must be a function. New code should use the
1264 * list_length() macro in order to avoid the overhead of a function
1267 int length(List *list);
1272 return list_length(list);