1 /*-------------------------------------------------------------------------
4 * interface for PostgreSQL generic linked list package
6 * This package implements singly-linked homogeneous lists.
8 * It is important to have constant-time length, append, and prepend
9 * operations. To achieve this, we deal with two distinct data
12 * 1. A set of "list cells": each cell contains a data field and
13 * a link to the next cell in the list or NULL.
14 * 2. A single structure containing metadata about the list: the
15 * type of the list, pointers to the head and tail cells, and
16 * the length of the list.
18 * We support three types of lists:
20 * T_List: lists of pointers
21 * (in practice usually pointers to Nodes, but not always;
22 * declared as "void *" to minimize casting annoyances)
23 * T_IntList: lists of integers
24 * T_OidList: lists of Oids
26 * (At the moment, ints and Oids are the same size, but they may not
27 * always be so; try to be careful to maintain the distinction.)
29 * There is also limited support for lists of TransactionIds; since these
30 * are used in only one or two places, we don't provide a full implementation,
31 * but map them onto Oid lists. This effectively assumes that TransactionId
32 * is no wider than Oid and both are unsigned types.
35 * Portions Copyright (c) 2003-2008, PgPool Global Development Group
36 * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
37 * Portions Copyright (c) 1994, Regents of the University of California
39 * $PostgreSQL: pgsql/src/include/nodes/pg_list.h,v 1.56 2007/01/05 22:19:55 momjian Exp $
41 *-------------------------------------------------------------------------
47 #include "pool_parser.h"
51 typedef struct ListCell ListCell;
55 NodeTag type; /* T_List, T_IntList, or T_OidList */
73 * The *only* valid representation of an empty list is NIL; in other
74 * words, a non-NIL list is guaranteed to have length >= 1 and
77 #define NIL ((List *) NULL)
80 * These routines are used frequently. However, we can't implement
81 * them as macros, since we want to avoid double-evaluation of macro
82 * arguments. Therefore, we implement them using GCC inline functions,
83 * and as regular functions with non-GCC compilers.
87 static __inline__ ListCell *
90 return l ? l->head : NULL;
93 static __inline__ ListCell *
96 return l ? l->tail : NULL;
102 return l ? l->length : 0;
106 extern ListCell *list_head(List *l);
107 extern ListCell *list_tail(List *l);
108 extern int list_length(List *l);
109 #endif /* __GNUC__ */
112 * NB: There is an unfortunate legacy from a previous incarnation of
113 * the List API: the macro lfirst() was used to mean "the data in this
114 * cons cell". To avoid changing every usage of lfirst(), that meaning
115 * has been kept. As a result, lfirst() takes a ListCell and returns
116 * the data it contains; to get the data in the first cell of a
117 * List, use linitial(). Worse, lsecond() is more closely related to
118 * linitial() than lfirst(): given a List, lsecond() returns the data
119 * in the second cons cell.
122 #define lnext(lc) ((lc)->next)
123 #define lfirst(lc) ((lc)->data.ptr_value)
124 #define lfirst_int(lc) ((lc)->data.int_value)
125 #define lfirst_oid(lc) ((lc)->data.oid_value)
127 #define linitial(l) lfirst(list_head(l))
128 #define linitial_int(l) lfirst_int(list_head(l))
129 #define linitial_oid(l) lfirst_oid(list_head(l))
131 #define lsecond(l) lfirst(lnext(list_head(l)))
132 #define lsecond_int(l) lfirst_int(lnext(list_head(l)))
133 #define lsecond_oid(l) lfirst_oid(lnext(list_head(l)))
135 #define lthird(l) lfirst(lnext(lnext(list_head(l))))
136 #define lthird_int(l) lfirst_int(lnext(lnext(list_head(l))))
137 #define lthird_oid(l) lfirst_oid(lnext(lnext(list_head(l))))
139 #define lfourth(l) lfirst(lnext(lnext(lnext(list_head(l)))))
140 #define lfourth_int(l) lfirst_int(lnext(lnext(lnext(list_head(l)))))
141 #define lfourth_oid(l) lfirst_oid(lnext(lnext(lnext(list_head(l)))))
143 #define llast(l) lfirst(list_tail(l))
144 #define llast_int(l) lfirst_int(list_tail(l))
145 #define llast_oid(l) lfirst_oid(list_tail(l))
148 * Convenience macros for building fixed-length lists
150 #define list_make1(x1) lcons(x1, NIL)
151 #define list_make2(x1,x2) lcons(x1, list_make1(x2))
152 #define list_make3(x1,x2,x3) lcons(x1, list_make2(x2, x3))
153 #define list_make4(x1,x2,x3,x4) lcons(x1, list_make3(x2, x3, x4))
155 #define list_make1_int(x1) lcons_int(x1, NIL)
156 #define list_make2_int(x1,x2) lcons_int(x1, list_make1_int(x2))
157 #define list_make3_int(x1,x2,x3) lcons_int(x1, list_make2_int(x2, x3))
158 #define list_make4_int(x1,x2,x3,x4) lcons_int(x1, list_make3_int(x2, x3, x4))
160 #define list_make1_oid(x1) lcons_oid(x1, NIL)
161 #define list_make2_oid(x1,x2) lcons_oid(x1, list_make1_oid(x2))
162 #define list_make3_oid(x1,x2,x3) lcons_oid(x1, list_make2_oid(x2, x3))
163 #define list_make4_oid(x1,x2,x3,x4) lcons_oid(x1, list_make3_oid(x2, x3, x4))
166 * Limited support for lists of TransactionIds, mapped onto lists of Oids
168 #define lfirst_xid(lc) ((TransactionId) lfirst_oid(lc))
169 #define lappend_xid(list, datum) lappend_oid(list, (Oid) (datum))
173 * a convenience macro which loops through the list
175 #define foreach(cell, l) \
176 for ((cell) = list_head(l); (cell) != NULL; (cell) = lnext(cell))
180 * a convenience macro which loops through a list starting from a
183 #define for_each_cell(cell, initcell) \
184 for ((cell) = (initcell); (cell) != NULL; (cell) = lnext(cell))
188 * a convenience macro for advancing through two linked lists
189 * simultaneously. This macro loops through both lists at the same
190 * time, stopping when either list runs out of elements. Depending
191 * on the requirements of the call site, it may also be wise to
192 * assert that the lengths of the two lists are equal.
194 #define forboth(cell1, list1, cell2, list2) \
195 for ((cell1) = list_head(list1), (cell2) = list_head(list2); \
196 (cell1) != NULL && (cell2) != NULL; \
197 (cell1) = lnext(cell1), (cell2) = lnext(cell2))
199 extern List *lappend(List *list, void *datum);
200 extern List *lappend_int(List *list, int datum);
201 extern List *lappend_oid(List *list, Oid datum);
203 extern ListCell *lappend_cell(List *list, ListCell *prev, void *datum);
204 extern ListCell *lappend_cell_int(List *list, ListCell *prev, int datum);
205 extern ListCell *lappend_cell_oid(List *list, ListCell *prev, Oid datum);
207 extern List *lcons(void *datum, List *list);
208 extern List *lcons_int(int datum, List *list);
209 extern List *lcons_oid(Oid datum, List *list);
211 extern List *list_concat(List *list1, List *list2);
212 extern List *list_truncate(List *list, int new_size);
214 extern void *list_nth(List *list, int n);
215 extern int list_nth_int(List *list, int n);
216 extern Oid list_nth_oid(List *list, int n);
218 extern bool list_member(List *list, void *datum);
219 extern bool list_member_ptr(List *list, void *datum);
220 extern bool list_member_int(List *list, int datum);
221 extern bool list_member_oid(List *list, Oid datum);
223 extern List *list_delete(List *list, void *datum);
224 extern List *list_delete_ptr(List *list, void *datum);
225 extern List *list_delete_int(List *list, int datum);
226 extern List *list_delete_oid(List *list, Oid datum);
227 extern List *list_delete_first(List *list);
228 extern List *list_delete_cell(List *list, ListCell *cell, ListCell *prev);
230 extern List *list_union(List *list1, List *list2);
231 extern List *list_union_ptr(List *list1, List *list2);
232 extern List *list_union_int(List *list1, List *list2);
233 extern List *list_union_oid(List *list1, List *list2);
235 extern List *list_difference(List *list1, List *list2);
236 extern List *list_difference_ptr(List *list1, List *list2);
237 extern List *list_difference_int(List *list1, List *list2);
238 extern List *list_difference_oid(List *list1, List *list2);
240 extern List *list_append_unique(List *list, void *datum);
241 extern List *list_append_unique_ptr(List *list, void *datum);
242 extern List *list_append_unique_int(List *list, int datum);
243 extern List *list_append_unique_oid(List *list, Oid datum);
245 extern List *list_concat_unique(List *list1, List *list2);
246 extern List *list_concat_unique_ptr(List *list1, List *list2);
247 extern List *list_concat_unique_int(List *list1, List *list2);
248 extern List *list_concat_unique_oid(List *list1, List *list2);
250 extern void list_free(List *list);
251 extern void list_free_deep(List *list);
253 extern List *list_copy(List *list);
254 extern List *list_copy_tail(List *list, int nskip);
257 * To ease migration to the new list API, a set of compatibility
258 * macros are provided that reduce the impact of the list API changes
259 * as far as possible. Until client code has been rewritten to use the
260 * new list API, the ENABLE_LIST_COMPAT symbol can be defined before
261 * including pg_list.h
263 #ifdef ENABLE_LIST_COMPAT
265 #define lfirsti(lc) lfirst_int(lc)
266 #define lfirsto(lc) lfirst_oid(lc)
268 #define makeList1(x1) list_make1(x1)
269 #define makeList2(x1, x2) list_make2(x1, x2)
270 #define makeList3(x1, x2, x3) list_make3(x1, x2, x3)
271 #define makeList4(x1, x2, x3, x4) list_make4(x1, x2, x3, x4)
273 #define makeListi1(x1) list_make1_int(x1)
274 #define makeListi2(x1, x2) list_make2_int(x1, x2)
276 #define makeListo1(x1) list_make1_oid(x1)
277 #define makeListo2(x1, x2) list_make2_oid(x1, x2)
279 #define lconsi(datum, list) lcons_int(datum, list)
280 #define lconso(datum, list) lcons_oid(datum, list)
282 #define lappendi(list, datum) lappend_int(list, datum)
283 #define lappendo(list, datum) lappend_oid(list, datum)
285 #define nconc(l1, l2) list_concat(l1, l2)
287 #define nth(n, list) list_nth(list, n)
289 #define member(datum, list) list_member(list, datum)
290 #define ptrMember(datum, list) list_member_ptr(list, datum)
291 #define intMember(datum, list) list_member_int(list, datum)
292 #define oidMember(datum, list) list_member_oid(list, datum)
295 * Note that the old lremove() determined equality via pointer
296 * comparison, whereas the new list_delete() uses equal(); in order to
297 * keep the same behavior, we therefore need to map lremove() calls to
298 * list_delete_ptr() rather than list_delete()
300 #define lremove(elem, list) list_delete_ptr(list, elem)
301 #define LispRemove(elem, list) list_delete(list, elem)
302 #define lremovei(elem, list) list_delete_int(list, elem)
303 #define lremoveo(elem, list) list_delete_oid(list, elem)
305 #define ltruncate(n, list) list_truncate(list, n)
307 #define set_union(l1, l2) list_union(l1, l2)
308 #define set_uniono(l1, l2) list_union_oid(l1, l2)
309 #define set_ptrUnion(l1, l2) list_union_ptr(l1, l2)
311 #define set_difference(l1, l2) list_difference(l1, l2)
312 #define set_differenceo(l1, l2) list_difference_oid(l1, l2)
313 #define set_ptrDifference(l1, l2) list_difference_ptr(l1, l2)
315 #define equali(l1, l2) equal(l1, l2)
316 #define equalo(l1, l2) equal(l1, l2)
318 #define freeList(list) list_free(list)
320 #define listCopy(list) list_copy(list)
322 extern int length(List *list);
323 #endif /* ENABLE_LIST_COMPAT */
325 #endif /* PG_LIST_H */