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-2019, 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
43typedef struct ListCell ListCell;
44
45typedef 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
53struct 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 */
76static inline ListCell *
77list_head(const List *l)
78{
79 return l ? l->head : NULL;
80}
81
82static inline ListCell *
83list_tail(List *l)
84{
85 return l ? l->tail : NULL;
86}
87
88static inline int
89list_length(const List *l)
90{
91 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/*
209 * forfour -
210 * the same for four lists
211 */
212#define forfour(cell1, list1, cell2, list2, cell3, list3, cell4, list4) \
213 for ((cell1) = list_head(list1), (cell2) = list_head(list2), \
214 (cell3) = list_head(list3), (cell4) = list_head(list4); \
215 (cell1) != NULL && (cell2) != NULL && \
216 (cell3) != NULL && (cell4) != NULL; \
217 (cell1) = lnext(cell1), (cell2) = lnext(cell2), \
218 (cell3) = lnext(cell3), (cell4) = lnext(cell4))
219
220/*
221 * forfive -
222 * the same for five lists
223 */
224#define forfive(cell1, list1, cell2, list2, cell3, list3, cell4, list4, cell5, list5) \
225 for ((cell1) = list_head(list1), (cell2) = list_head(list2), \
226 (cell3) = list_head(list3), (cell4) = list_head(list4), \
227 (cell5) = list_head(list5); \
228 (cell1) != NULL && (cell2) != NULL && (cell3) != NULL && \
229 (cell4) != NULL && (cell5) != NULL; \
230 (cell1) = lnext(cell1), (cell2) = lnext(cell2), \
231 (cell3) = lnext(cell3), (cell4) = lnext(cell4), \
232 (cell5) = lnext(cell5))
233
234extern List *lappend(List *list, void *datum);
235extern List *lappend_int(List *list, int datum);
236extern List *lappend_oid(List *list, Oid datum);
237
238extern ListCell *lappend_cell(List *list, ListCell *prev, void *datum);
239extern ListCell *lappend_cell_int(List *list, ListCell *prev, int datum);
240extern ListCell *lappend_cell_oid(List *list, ListCell *prev, Oid datum);
241
242extern List *lcons(void *datum, List *list);
243extern List *lcons_int(int datum, List *list);
244extern List *lcons_oid(Oid datum, List *list);
245
246extern List *list_concat(List *list1, List *list2);
247extern List *list_truncate(List *list, int new_size);
248
249extern ListCell *list_nth_cell(const List *list, int n);
250extern void *list_nth(const List *list, int n);
251extern int list_nth_int(const List *list, int n);
252extern Oid list_nth_oid(const List *list, int n);
253#define list_nth_node(type,list,n) castNode(type, list_nth(list, n))
254
255extern bool list_member(const List *list, const void *datum);
256extern bool list_member_ptr(const List *list, const void *datum);
257extern bool list_member_int(const List *list, int datum);
258extern bool list_member_oid(const List *list, Oid datum);
259
260extern List *list_delete(List *list, void *datum);
261extern List *list_delete_ptr(List *list, void *datum);
262extern List *list_delete_int(List *list, int datum);
263extern List *list_delete_oid(List *list, Oid datum);
264extern List *list_delete_first(List *list);
265extern List *list_delete_cell(List *list, ListCell *cell, ListCell *prev);
266
267extern List *list_union(const List *list1, const List *list2);
268extern List *list_union_ptr(const List *list1, const List *list2);
269extern List *list_union_int(const List *list1, const List *list2);
270extern List *list_union_oid(const List *list1, const List *list2);
271
272extern List *list_intersection(const List *list1, const List *list2);
273extern List *list_intersection_int(const List *list1, const List *list2);
274
275/* currently, there's no need for list_intersection_ptr etc */
276
277extern List *list_difference(const List *list1, const List *list2);
278extern List *list_difference_ptr(const List *list1, const List *list2);
279extern List *list_difference_int(const List *list1, const List *list2);
280extern List *list_difference_oid(const List *list1, const List *list2);
281
282extern List *list_append_unique(List *list, void *datum);
283extern List *list_append_unique_ptr(List *list, void *datum);
284extern List *list_append_unique_int(List *list, int datum);
285extern List *list_append_unique_oid(List *list, Oid datum);
286
287extern List *list_concat_unique(List *list1, List *list2);
288extern List *list_concat_unique_ptr(List *list1, List *list2);
289extern List *list_concat_unique_int(List *list1, List *list2);
290extern List *list_concat_unique_oid(List *list1, List *list2);
291
292extern void list_free(List *list);
293extern void list_free_deep(List *list);
294
295extern List *list_copy(const List *list);
296extern List *list_copy_tail(const List *list, int nskip);
297
298typedef int (*list_qsort_comparator) (const void *a, const void *b);
299extern List *list_qsort(const List *list, list_qsort_comparator cmp);
300
301/*
302 * To ease migration to the new list API, a set of compatibility
303 * macros are provided that reduce the impact of the list API changes
304 * as far as possible. Until client code has been rewritten to use the
305 * new list API, the ENABLE_LIST_COMPAT symbol can be defined before
306 * including pg_list.h
307 */
308#ifdef ENABLE_LIST_COMPAT
309
310#define lfirsti(lc) lfirst_int(lc)
311#define lfirsto(lc) lfirst_oid(lc)
312
313#define makeList1(x1) list_make1(x1)
314#define makeList2(x1, x2) list_make2(x1, x2)
315#define makeList3(x1, x2, x3) list_make3(x1, x2, x3)
316#define makeList4(x1, x2, x3, x4) list_make4(x1, x2, x3, x4)
317
318#define makeListi1(x1) list_make1_int(x1)
319#define makeListi2(x1, x2) list_make2_int(x1, x2)
320
321#define makeListo1(x1) list_make1_oid(x1)
322#define makeListo2(x1, x2) list_make2_oid(x1, x2)
323
324#define lconsi(datum, list) lcons_int(datum, list)
325#define lconso(datum, list) lcons_oid(datum, list)
326
327#define lappendi(list, datum) lappend_int(list, datum)
328#define lappendo(list, datum) lappend_oid(list, datum)
329
330#define nconc(l1, l2) list_concat(l1, l2)
331
332#define nth(n, list) list_nth(list, n)
333
334#define member(datum, list) list_member(list, datum)
335#define ptrMember(datum, list) list_member_ptr(list, datum)
336#define intMember(datum, list) list_member_int(list, datum)
337#define oidMember(datum, list) list_member_oid(list, datum)
338
339/*
340 * Note that the old lremove() determined equality via pointer
341 * comparison, whereas the new list_delete() uses equal(); in order to
342 * keep the same behavior, we therefore need to map lremove() calls to
343 * list_delete_ptr() rather than list_delete()
344 */
345#define lremove(elem, list) list_delete_ptr(list, elem)
346#define LispRemove(elem, list) list_delete(list, elem)
347#define lremovei(elem, list) list_delete_int(list, elem)
348#define lremoveo(elem, list) list_delete_oid(list, elem)
349
350#define ltruncate(n, list) list_truncate(list, n)
351
352#define set_union(l1, l2) list_union(l1, l2)
353#define set_uniono(l1, l2) list_union_oid(l1, l2)
354#define set_ptrUnion(l1, l2) list_union_ptr(l1, l2)
355
356#define set_difference(l1, l2) list_difference(l1, l2)
357#define set_differenceo(l1, l2) list_difference_oid(l1, l2)
358#define set_ptrDifference(l1, l2) list_difference_ptr(l1, l2)
359
360#define equali(l1, l2) equal(l1, l2)
361#define equalo(l1, l2) equal(l1, l2)
362
363#define freeList(list) list_free(list)
364
365#define listCopy(list) list_copy(list)
366
367extern int length(List *list);
368#endif /* ENABLE_LIST_COMPAT */
369
370#endif /* PG_LIST_H */
371