Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * pg_list.h
4 : * interface for PostgreSQL generic linked list package
5 : *
6 : * This package implements singly-linked homogeneous lists.
7 : *
8 : * It is important to have constant-time length, append, and prepend
9 : * operations. To achieve this, we deal with two distinct data
10 : * structures:
11 : *
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.
17 : *
18 : * We support three types of lists:
19 : *
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
25 : *
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.)
28 : *
29 : *
30 : * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
31 : * Portions Copyright (c) 1994, Regents of the University of California
32 : *
33 : * src/include/nodes/pg_list.h
34 : *
35 : *-------------------------------------------------------------------------
36 : */
37 : #ifndef PG_LIST_H
38 : #define PG_LIST_H
39 :
40 : #include "nodes/nodes.h"
41 :
42 :
43 : typedef struct ListCell ListCell;
44 :
45 : typedef struct List
46 : {
47 : NodeTag type; /* T_List, T_IntList, or T_OidList */
48 : int length;
49 : ListCell *head;
50 : ListCell *tail;
51 : } List;
52 :
53 : struct ListCell
54 : {
55 : union
56 : {
57 : void *ptr_value;
58 : int int_value;
59 : Oid oid_value;
60 : } data;
61 : ListCell *next;
62 : };
63 :
64 : /*
65 : * The *only* valid representation of an empty list is NIL; in other
66 : * words, a non-NIL list is guaranteed to have length >= 1 and
67 : * head/tail != NULL
68 : */
69 : #define NIL ((List *) NULL)
70 :
71 : /*
72 : * These routines are used frequently. However, we can't implement
73 : * them as macros, since we want to avoid double-evaluation of macro
74 : * arguments.
75 : */
76 : static inline ListCell *
77 14333749 : list_head(const List *l)
78 : {
79 14333749 : return l ? l->head : NULL;
80 : }
81 :
82 : static inline ListCell *
83 60013 : list_tail(List *l)
84 : {
85 60013 : return l ? l->tail : NULL;
86 : }
87 :
88 : static inline int
89 2660682 : list_length(const List *l)
90 : {
91 2660682 : return l ? l->length : 0;
92 : }
93 :
94 : /*
95 : * NB: There is an unfortunate legacy from a previous incarnation of
96 : * the List API: the macro lfirst() was used to mean "the data in this
97 : * cons cell". To avoid changing every usage of lfirst(), that meaning
98 : * has been kept. As a result, lfirst() takes a ListCell and returns
99 : * the data it contains; to get the data in the first cell of a
100 : * List, use linitial(). Worse, lsecond() is more closely related to
101 : * linitial() than lfirst(): given a List, lsecond() returns the data
102 : * in the second cons cell.
103 : */
104 :
105 : #define lnext(lc) ((lc)->next)
106 : #define lfirst(lc) ((lc)->data.ptr_value)
107 : #define lfirst_int(lc) ((lc)->data.int_value)
108 : #define lfirst_oid(lc) ((lc)->data.oid_value)
109 : #define lfirst_node(type,lc) castNode(type, lfirst(lc))
110 :
111 : #define linitial(l) lfirst(list_head(l))
112 : #define linitial_int(l) lfirst_int(list_head(l))
113 : #define linitial_oid(l) lfirst_oid(list_head(l))
114 : #define linitial_node(type,l) castNode(type, linitial(l))
115 :
116 : #define lsecond(l) lfirst(lnext(list_head(l)))
117 : #define lsecond_int(l) lfirst_int(lnext(list_head(l)))
118 : #define lsecond_oid(l) lfirst_oid(lnext(list_head(l)))
119 : #define lsecond_node(type,l) castNode(type, lsecond(l))
120 :
121 : #define lthird(l) lfirst(lnext(lnext(list_head(l))))
122 : #define lthird_int(l) lfirst_int(lnext(lnext(list_head(l))))
123 : #define lthird_oid(l) lfirst_oid(lnext(lnext(list_head(l))))
124 : #define lthird_node(type,l) castNode(type, lthird(l))
125 :
126 : #define lfourth(l) lfirst(lnext(lnext(lnext(list_head(l)))))
127 : #define lfourth_int(l) lfirst_int(lnext(lnext(lnext(list_head(l)))))
128 : #define lfourth_oid(l) lfirst_oid(lnext(lnext(lnext(list_head(l)))))
129 : #define lfourth_node(type,l) castNode(type, lfourth(l))
130 :
131 : #define llast(l) lfirst(list_tail(l))
132 : #define llast_int(l) lfirst_int(list_tail(l))
133 : #define llast_oid(l) lfirst_oid(list_tail(l))
134 : #define llast_node(type,l) castNode(type, llast(l))
135 :
136 : /*
137 : * Convenience macros for building fixed-length lists
138 : */
139 : #define list_make1(x1) lcons(x1, NIL)
140 : #define list_make2(x1,x2) lcons(x1, list_make1(x2))
141 : #define list_make3(x1,x2,x3) lcons(x1, list_make2(x2, x3))
142 : #define list_make4(x1,x2,x3,x4) lcons(x1, list_make3(x2, x3, x4))
143 : #define list_make5(x1,x2,x3,x4,x5) lcons(x1, list_make4(x2, x3, x4, x5))
144 :
145 : #define list_make1_int(x1) lcons_int(x1, NIL)
146 : #define list_make2_int(x1,x2) lcons_int(x1, list_make1_int(x2))
147 : #define list_make3_int(x1,x2,x3) lcons_int(x1, list_make2_int(x2, x3))
148 : #define list_make4_int(x1,x2,x3,x4) lcons_int(x1, list_make3_int(x2, x3, x4))
149 : #define list_make5_int(x1,x2,x3,x4,x5) lcons_int(x1, list_make4_int(x2, x3, x4, x5))
150 :
151 : #define list_make1_oid(x1) lcons_oid(x1, NIL)
152 : #define list_make2_oid(x1,x2) lcons_oid(x1, list_make1_oid(x2))
153 : #define list_make3_oid(x1,x2,x3) lcons_oid(x1, list_make2_oid(x2, x3))
154 : #define list_make4_oid(x1,x2,x3,x4) lcons_oid(x1, list_make3_oid(x2, x3, x4))
155 : #define list_make5_oid(x1,x2,x3,x4,x5) lcons_oid(x1, list_make4_oid(x2, x3, x4, x5))
156 :
157 : /*
158 : * foreach -
159 : * a convenience macro which loops through the list
160 : */
161 : #define foreach(cell, l) \
162 : for ((cell) = list_head(l); (cell) != NULL; (cell) = lnext(cell))
163 :
164 : /*
165 : * for_each_cell -
166 : * a convenience macro which loops through a list starting from a
167 : * specified cell
168 : */
169 : #define for_each_cell(cell, initcell) \
170 : for ((cell) = (initcell); (cell) != NULL; (cell) = lnext(cell))
171 :
172 : /*
173 : * forboth -
174 : * a convenience macro for advancing through two linked lists
175 : * simultaneously. This macro loops through both lists at the same
176 : * time, stopping when either list runs out of elements. Depending
177 : * on the requirements of the call site, it may also be wise to
178 : * assert that the lengths of the two lists are equal.
179 : */
180 : #define forboth(cell1, list1, cell2, list2) \
181 : for ((cell1) = list_head(list1), (cell2) = list_head(list2); \
182 : (cell1) != NULL && (cell2) != NULL; \
183 : (cell1) = lnext(cell1), (cell2) = lnext(cell2))
184 :
185 : /*
186 : * for_both_cell -
187 : * a convenience macro which loops through two lists starting from the
188 : * specified cells of each. This macro loops through both lists at the same
189 : * time, stopping when either list runs out of elements. Depending on the
190 : * requirements of the call site, it may also be wise to assert that the
191 : * lengths of the two lists are equal, and initcell1 and initcell2 are at
192 : * the same position in the respective lists.
193 : */
194 : #define for_both_cell(cell1, initcell1, cell2, initcell2) \
195 : for ((cell1) = (initcell1), (cell2) = (initcell2); \
196 : (cell1) != NULL && (cell2) != NULL; \
197 : (cell1) = lnext(cell1), (cell2) = lnext(cell2))
198 :
199 : /*
200 : * forthree -
201 : * the same for three lists
202 : */
203 : #define forthree(cell1, list1, cell2, list2, cell3, list3) \
204 : for ((cell1) = list_head(list1), (cell2) = list_head(list2), (cell3) = list_head(list3); \
205 : (cell1) != NULL && (cell2) != NULL && (cell3) != NULL; \
206 : (cell1) = lnext(cell1), (cell2) = lnext(cell2), (cell3) = lnext(cell3))
207 :
208 : extern List *lappend(List *list, void *datum);
209 : extern List *lappend_int(List *list, int datum);
210 : extern List *lappend_oid(List *list, Oid datum);
211 :
212 : extern ListCell *lappend_cell(List *list, ListCell *prev, void *datum);
213 : extern ListCell *lappend_cell_int(List *list, ListCell *prev, int datum);
214 : extern ListCell *lappend_cell_oid(List *list, ListCell *prev, Oid datum);
215 :
216 : extern List *lcons(void *datum, List *list);
217 : extern List *lcons_int(int datum, List *list);
218 : extern List *lcons_oid(Oid datum, List *list);
219 :
220 : extern List *list_concat(List *list1, List *list2);
221 : extern List *list_truncate(List *list, int new_size);
222 :
223 : extern ListCell *list_nth_cell(const List *list, int n);
224 : extern void *list_nth(const List *list, int n);
225 : extern int list_nth_int(const List *list, int n);
226 : extern Oid list_nth_oid(const List *list, int n);
227 : #define list_nth_node(type,list,n) castNode(type, list_nth(list, n))
228 :
229 : extern bool list_member(const List *list, const void *datum);
230 : extern bool list_member_ptr(const List *list, const void *datum);
231 : extern bool list_member_int(const List *list, int datum);
232 : extern bool list_member_oid(const List *list, Oid datum);
233 :
234 : extern List *list_delete(List *list, void *datum);
235 : extern List *list_delete_ptr(List *list, void *datum);
236 : extern List *list_delete_int(List *list, int datum);
237 : extern List *list_delete_oid(List *list, Oid datum);
238 : extern List *list_delete_first(List *list);
239 : extern List *list_delete_cell(List *list, ListCell *cell, ListCell *prev);
240 :
241 : extern List *list_union(const List *list1, const List *list2);
242 : extern List *list_union_ptr(const List *list1, const List *list2);
243 : extern List *list_union_int(const List *list1, const List *list2);
244 : extern List *list_union_oid(const List *list1, const List *list2);
245 :
246 : extern List *list_intersection(const List *list1, const List *list2);
247 : extern List *list_intersection_int(const List *list1, const List *list2);
248 :
249 : /* currently, there's no need for list_intersection_ptr etc */
250 :
251 : extern List *list_difference(const List *list1, const List *list2);
252 : extern List *list_difference_ptr(const List *list1, const List *list2);
253 : extern List *list_difference_int(const List *list1, const List *list2);
254 : extern List *list_difference_oid(const List *list1, const List *list2);
255 :
256 : extern List *list_append_unique(List *list, void *datum);
257 : extern List *list_append_unique_ptr(List *list, void *datum);
258 : extern List *list_append_unique_int(List *list, int datum);
259 : extern List *list_append_unique_oid(List *list, Oid datum);
260 :
261 : extern List *list_concat_unique(List *list1, List *list2);
262 : extern List *list_concat_unique_ptr(List *list1, List *list2);
263 : extern List *list_concat_unique_int(List *list1, List *list2);
264 : extern List *list_concat_unique_oid(List *list1, List *list2);
265 :
266 : extern void list_free(List *list);
267 : extern void list_free_deep(List *list);
268 :
269 : extern List *list_copy(const List *list);
270 : extern List *list_copy_tail(const List *list, int nskip);
271 :
272 : /*
273 : * To ease migration to the new list API, a set of compatibility
274 : * macros are provided that reduce the impact of the list API changes
275 : * as far as possible. Until client code has been rewritten to use the
276 : * new list API, the ENABLE_LIST_COMPAT symbol can be defined before
277 : * including pg_list.h
278 : */
279 : #ifdef ENABLE_LIST_COMPAT
280 :
281 : #define lfirsti(lc) lfirst_int(lc)
282 : #define lfirsto(lc) lfirst_oid(lc)
283 :
284 : #define makeList1(x1) list_make1(x1)
285 : #define makeList2(x1, x2) list_make2(x1, x2)
286 : #define makeList3(x1, x2, x3) list_make3(x1, x2, x3)
287 : #define makeList4(x1, x2, x3, x4) list_make4(x1, x2, x3, x4)
288 :
289 : #define makeListi1(x1) list_make1_int(x1)
290 : #define makeListi2(x1, x2) list_make2_int(x1, x2)
291 :
292 : #define makeListo1(x1) list_make1_oid(x1)
293 : #define makeListo2(x1, x2) list_make2_oid(x1, x2)
294 :
295 : #define lconsi(datum, list) lcons_int(datum, list)
296 : #define lconso(datum, list) lcons_oid(datum, list)
297 :
298 : #define lappendi(list, datum) lappend_int(list, datum)
299 : #define lappendo(list, datum) lappend_oid(list, datum)
300 :
301 : #define nconc(l1, l2) list_concat(l1, l2)
302 :
303 : #define nth(n, list) list_nth(list, n)
304 :
305 : #define member(datum, list) list_member(list, datum)
306 : #define ptrMember(datum, list) list_member_ptr(list, datum)
307 : #define intMember(datum, list) list_member_int(list, datum)
308 : #define oidMember(datum, list) list_member_oid(list, datum)
309 :
310 : /*
311 : * Note that the old lremove() determined equality via pointer
312 : * comparison, whereas the new list_delete() uses equal(); in order to
313 : * keep the same behavior, we therefore need to map lremove() calls to
314 : * list_delete_ptr() rather than list_delete()
315 : */
316 : #define lremove(elem, list) list_delete_ptr(list, elem)
317 : #define LispRemove(elem, list) list_delete(list, elem)
318 : #define lremovei(elem, list) list_delete_int(list, elem)
319 : #define lremoveo(elem, list) list_delete_oid(list, elem)
320 :
321 : #define ltruncate(n, list) list_truncate(list, n)
322 :
323 : #define set_union(l1, l2) list_union(l1, l2)
324 : #define set_uniono(l1, l2) list_union_oid(l1, l2)
325 : #define set_ptrUnion(l1, l2) list_union_ptr(l1, l2)
326 :
327 : #define set_difference(l1, l2) list_difference(l1, l2)
328 : #define set_differenceo(l1, l2) list_difference_oid(l1, l2)
329 : #define set_ptrDifference(l1, l2) list_difference_ptr(l1, l2)
330 :
331 : #define equali(l1, l2) equal(l1, l2)
332 : #define equalo(l1, l2) equal(l1, l2)
333 :
334 : #define freeList(list) list_free(list)
335 :
336 : #define listCopy(list) list_copy(list)
337 :
338 : extern int length(List *list);
339 : #endif /* ENABLE_LIST_COMPAT */
340 :
341 : #endif /* PG_LIST_H */
|
