PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
pg_list.h
Go to the documentation of this file.
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-2015, 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;
51 } List;
52 
53 struct ListCell
54 {
55  union
56  {
57  void *ptr_value;
58  int int_value;
60  } data;
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 list_head(const List *l)
78 {
79  return l ? l->head : NULL;
80 }
81 
82 static inline ListCell *
84 {
85  return l ? l->tail : NULL;
86 }
87 
88 static inline int
89 list_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 
110 #define linitial(l) lfirst(list_head(l))
111 #define linitial_int(l) lfirst_int(list_head(l))
112 #define linitial_oid(l) lfirst_oid(list_head(l))
113 
114 #define lsecond(l) lfirst(lnext(list_head(l)))
115 #define lsecond_int(l) lfirst_int(lnext(list_head(l)))
116 #define lsecond_oid(l) lfirst_oid(lnext(list_head(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 
122 #define lfourth(l) lfirst(lnext(lnext(lnext(list_head(l)))))
123 #define lfourth_int(l) lfirst_int(lnext(lnext(lnext(list_head(l)))))
124 #define lfourth_oid(l) lfirst_oid(lnext(lnext(lnext(list_head(l)))))
125 
126 #define llast(l) lfirst(list_tail(l))
127 #define llast_int(l) lfirst_int(list_tail(l))
128 #define llast_oid(l) lfirst_oid(list_tail(l))
129 
130 /*
131  * Convenience macros for building fixed-length lists
132  */
133 #define list_make1(x1) lcons(x1, NIL)
134 #define list_make2(x1,x2) lcons(x1, list_make1(x2))
135 #define list_make3(x1,x2,x3) lcons(x1, list_make2(x2, x3))
136 #define list_make4(x1,x2,x3,x4) lcons(x1, list_make3(x2, x3, x4))
137 
138 #define list_make1_int(x1) lcons_int(x1, NIL)
139 #define list_make2_int(x1,x2) lcons_int(x1, list_make1_int(x2))
140 #define list_make3_int(x1,x2,x3) lcons_int(x1, list_make2_int(x2, x3))
141 #define list_make4_int(x1,x2,x3,x4) lcons_int(x1, list_make3_int(x2, x3, x4))
142 
143 #define list_make1_oid(x1) lcons_oid(x1, NIL)
144 #define list_make2_oid(x1,x2) lcons_oid(x1, list_make1_oid(x2))
145 #define list_make3_oid(x1,x2,x3) lcons_oid(x1, list_make2_oid(x2, x3))
146 #define list_make4_oid(x1,x2,x3,x4) lcons_oid(x1, list_make3_oid(x2, x3, x4))
147 
148 /*
149  * foreach -
150  * a convenience macro which loops through the list
151  */
152 #define foreach(cell, l) \
153  for ((cell) = list_head(l); (cell) != NULL; (cell) = lnext(cell))
154 
155 /*
156  * for_each_cell -
157  * a convenience macro which loops through a list starting from a
158  * specified cell
159  */
160 #define for_each_cell(cell, initcell) \
161  for ((cell) = (initcell); (cell) != NULL; (cell) = lnext(cell))
162 
163 /*
164  * forboth -
165  * a convenience macro for advancing through two linked lists
166  * simultaneously. This macro loops through both lists at the same
167  * time, stopping when either list runs out of elements. Depending
168  * on the requirements of the call site, it may also be wise to
169  * assert that the lengths of the two lists are equal.
170  */
171 #define forboth(cell1, list1, cell2, list2) \
172  for ((cell1) = list_head(list1), (cell2) = list_head(list2); \
173  (cell1) != NULL && (cell2) != NULL; \
174  (cell1) = lnext(cell1), (cell2) = lnext(cell2))
175 
176 /*
177  * forthree -
178  * the same for three lists
179  */
180 #define forthree(cell1, list1, cell2, list2, cell3, list3) \
181  for ((cell1) = list_head(list1), (cell2) = list_head(list2), (cell3) = list_head(list3); \
182  (cell1) != NULL && (cell2) != NULL && (cell3) != NULL; \
183  (cell1) = lnext(cell1), (cell2) = lnext(cell2), (cell3) = lnext(cell3))
184 
185 extern List *lappend(List *list, void *datum);
186 extern List *lappend_int(List *list, int datum);
187 extern List *lappend_oid(List *list, Oid datum);
188 
189 extern ListCell *lappend_cell(List *list, ListCell *prev, void *datum);
190 extern ListCell *lappend_cell_int(List *list, ListCell *prev, int datum);
191 extern ListCell *lappend_cell_oid(List *list, ListCell *prev, Oid datum);
192 
193 extern List *lcons(void *datum, List *list);
194 extern List *lcons_int(int datum, List *list);
195 extern List *lcons_oid(Oid datum, List *list);
196 
197 extern List *list_concat(List *list1, List *list2);
198 extern List *list_truncate(List *list, int new_size);
199 
200 extern ListCell *list_nth_cell(const List *list, int n);
201 extern void *list_nth(const List *list, int n);
202 extern int list_nth_int(const List *list, int n);
203 extern Oid list_nth_oid(const List *list, int n);
204 
205 extern bool list_member(const List *list, const void *datum);
206 extern bool list_member_ptr(const List *list, const void *datum);
207 extern bool list_member_int(const List *list, int datum);
208 extern bool list_member_oid(const List *list, Oid datum);
209 
210 extern List *list_delete(List *list, void *datum);
211 extern List *list_delete_ptr(List *list, void *datum);
212 extern List *list_delete_int(List *list, int datum);
213 extern List *list_delete_oid(List *list, Oid datum);
214 extern List *list_delete_first(List *list);
215 extern List *list_delete_cell(List *list, ListCell *cell, ListCell *prev);
216 
217 extern List *list_union(const List *list1, const List *list2);
218 extern List *list_union_ptr(const List *list1, const List *list2);
219 extern List *list_union_int(const List *list1, const List *list2);
220 extern List *list_union_oid(const List *list1, const List *list2);
221 
222 extern List *list_intersection(const List *list1, const List *list2);
223 extern List *list_intersection_int(const List *list1, const List *list2);
224 
225 /* currently, there's no need for list_intersection_ptr etc */
226 
227 extern List *list_difference(const List *list1, const List *list2);
228 extern List *list_difference_ptr(const List *list1, const List *list2);
229 extern List *list_difference_int(const List *list1, const List *list2);
230 extern List *list_difference_oid(const List *list1, const List *list2);
231 
232 extern List *list_append_unique(List *list, void *datum);
233 extern List *list_append_unique_ptr(List *list, void *datum);
234 extern List *list_append_unique_int(List *list, int datum);
235 extern List *list_append_unique_oid(List *list, Oid datum);
236 
237 extern List *list_concat_unique(List *list1, List *list2);
238 extern List *list_concat_unique_ptr(List *list1, List *list2);
239 extern List *list_concat_unique_int(List *list1, List *list2);
240 extern List *list_concat_unique_oid(List *list1, List *list2);
241 
242 extern void list_free(List *list);
243 extern void list_free_deep(List *list);
244 
245 extern List *list_copy(const List *list);
246 extern List *list_copy_tail(const List *list, int nskip);
247 
248 /*
249  * To ease migration to the new list API, a set of compatibility
250  * macros are provided that reduce the impact of the list API changes
251  * as far as possible. Until client code has been rewritten to use the
252  * new list API, the ENABLE_LIST_COMPAT symbol can be defined before
253  * including pg_list.h
254  */
255 #ifdef ENABLE_LIST_COMPAT
256 
257 #define lfirsti(lc) lfirst_int(lc)
258 #define lfirsto(lc) lfirst_oid(lc)
259 
260 #define makeList1(x1) list_make1(x1)
261 #define makeList2(x1, x2) list_make2(x1, x2)
262 #define makeList3(x1, x2, x3) list_make3(x1, x2, x3)
263 #define makeList4(x1, x2, x3, x4) list_make4(x1, x2, x3, x4)
264 
265 #define makeListi1(x1) list_make1_int(x1)
266 #define makeListi2(x1, x2) list_make2_int(x1, x2)
267 
268 #define makeListo1(x1) list_make1_oid(x1)
269 #define makeListo2(x1, x2) list_make2_oid(x1, x2)
270 
271 #define lconsi(datum, list) lcons_int(datum, list)
272 #define lconso(datum, list) lcons_oid(datum, list)
273 
274 #define lappendi(list, datum) lappend_int(list, datum)
275 #define lappendo(list, datum) lappend_oid(list, datum)
276 
277 #define nconc(l1, l2) list_concat(l1, l2)
278 
279 #define nth(n, list) list_nth(list, n)
280 
281 #define member(datum, list) list_member(list, datum)
282 #define ptrMember(datum, list) list_member_ptr(list, datum)
283 #define intMember(datum, list) list_member_int(list, datum)
284 #define oidMember(datum, list) list_member_oid(list, datum)
285 
286 /*
287  * Note that the old lremove() determined equality via pointer
288  * comparison, whereas the new list_delete() uses equal(); in order to
289  * keep the same behavior, we therefore need to map lremove() calls to
290  * list_delete_ptr() rather than list_delete()
291  */
292 #define lremove(elem, list) list_delete_ptr(list, elem)
293 #define LispRemove(elem, list) list_delete(list, elem)
294 #define lremovei(elem, list) list_delete_int(list, elem)
295 #define lremoveo(elem, list) list_delete_oid(list, elem)
296 
297 #define ltruncate(n, list) list_truncate(list, n)
298 
299 #define set_union(l1, l2) list_union(l1, l2)
300 #define set_uniono(l1, l2) list_union_oid(l1, l2)
301 #define set_ptrUnion(l1, l2) list_union_ptr(l1, l2)
302 
303 #define set_difference(l1, l2) list_difference(l1, l2)
304 #define set_differenceo(l1, l2) list_difference_oid(l1, l2)
305 #define set_ptrDifference(l1, l2) list_difference_ptr(l1, l2)
306 
307 #define equali(l1, l2) equal(l1, l2)
308 #define equalo(l1, l2) equal(l1, l2)
309 
310 #define freeList(list) list_free(list)
311 
312 #define listCopy(list) list_copy(list)
313 
314 extern int length(List *list);
315 #endif /* ENABLE_LIST_COMPAT */
316 
317 #endif /* PG_LIST_H */
ListCell * lappend_cell_int(List *list, ListCell *prev, int datum)
Definition: list.c:222
bool list_member_int(const List *list, int datum)
Definition: list.c:485
int length(const List *list)
Definition: list.c:1271
List * list_concat_unique_int(List *list1, List *list2)
Definition: list.c:1061
int int_value
Definition: pg_list.h:58
List * list_concat(List *list1, List *list2)
Definition: list.c:321
ListCell * lappend_cell(List *list, ListCell *prev, void *datum)
Definition: list.c:209
List * list_difference_ptr(const List *list1, const List *list2)
Definition: list.c:884
List * list_union(const List *list1, const List *list2)
Definition: list.c:697
List * list_concat_unique_ptr(List *list1, List *list2)
Definition: list.c:1040
List * lcons_oid(Oid datum, List *list)
Definition: list.c:295
union ListCell::@45 data
void * list_nth(const List *list, int n)
Definition: list.c:410
List * list_truncate(List *list, int new_size)
Definition: list.c:350
unsigned int Oid
Definition: postgres_ext.h:31
List * list_delete_first(List *list)
Definition: list.c:666
NodeTag
Definition: nodes.h:26
List * lappend(List *list, void *datum)
Definition: list.c:128
List * list_copy(const List *list)
Definition: list.c:1160
List * list_union_ptr(const List *list1, const List *list2)
Definition: list.c:721
List * list_union_oid(const List *list1, const List *list2)
Definition: list.c:767
bool list_member_oid(const List *list, Oid datum)
Definition: list.c:505
List * list_delete_int(List *list, int datum)
Definition: list.c:613
static ListCell * list_tail(List *l)
Definition: pg_list.h:83
List * lcons(void *datum, List *list)
Definition: list.c:259
void * ptr_value
Definition: pg_list.h:57
void list_free(List *list)
Definition: list.c:1133
List * list_union_int(const List *list1, const List *list2)
Definition: list.c:744
ListCell * lappend_cell_oid(List *list, ListCell *prev, Oid datum)
Definition: list.c:235
Oid oid_value
Definition: pg_list.h:59
void list_free_deep(List *list)
Definition: list.c:1147
List * list_intersection_int(const List *list1, const List *list2)
Definition: list.c:826
static ListCell * list_head(const List *l)
Definition: pg_list.h:77
List * list_concat_unique(List *list1, List *list2)
Definition: list.c:1018
List * list_difference(const List *list1, const List *list2)
Definition: list.c:858
int list_nth_int(const List *list, int n)
Definition: list.c:421
List * list_append_unique_int(List *list, int datum)
Definition: list.c:987
List * list_concat_unique_oid(List *list1, List *list2)
Definition: list.c:1082
List * lappend_oid(List *list, Oid datum)
Definition: list.c:164
List * list_delete(List *list, void *datum)
Definition: list.c:567
List * list_delete_oid(List *list, Oid datum)
Definition: list.c:636
bool list_member(const List *list, const void *datum)
Definition: list.c:444
List * list_delete_ptr(List *list, void *datum)
Definition: list.c:590
ListCell * list_nth_cell(const List *list, int n)
Definition: list.c:386
List * list_copy_tail(const List *list, int nskip)
Definition: list.c:1203
List * list_delete_cell(List *list, ListCell *cell, ListCell *prev)
Definition: list.c:528
ListCell * next
Definition: pg_list.h:61
#define NULL
Definition: c.h:215
bool list_member_ptr(const List *list, const void *datum)
Definition: list.c:465
List * lappend_int(List *list, int datum)
Definition: list.c:146
Oid list_nth_oid(const List *list, int n)
Definition: list.c:432
static int list_length(const List *l)
Definition: pg_list.h:89
List * list_append_unique_oid(List *list, Oid datum)
Definition: list.c:999
int length
Definition: pg_list.h:48
List * list_difference_int(const List *list1, const List *list2)
Definition: list.c:909
NodeTag type
Definition: pg_list.h:47
tuple list
Definition: sort-test.py:11
List * list_append_unique_ptr(List *list, void *datum)
Definition: list.c:975
ListCell * head
Definition: pg_list.h:49
struct List List
List * list_intersection(const List *list1, const List *list2)
Definition: list.c:800
Definition: pg_list.h:45
List * lcons_int(int datum, List *list)
Definition: list.c:277
ListCell * tail
Definition: pg_list.h:50
List * list_difference_oid(const List *list1, const List *list2)
Definition: list.c:934
List * list_append_unique(List *list, void *datum)
Definition: list.c:962