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