Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * pg_list.h
4 : : * interface for PostgreSQL generic list package
5 : : *
6 : : * Once upon a time, parts of Postgres were written in Lisp and used real
7 : : * cons-cell lists for major data structures. When that code was rewritten
8 : : * in C, we initially had a faithful emulation of cons-cell lists, which
9 : : * unsurprisingly was a performance bottleneck. A couple of major rewrites
10 : : * later, these data structures are actually simple expansible arrays;
11 : : * but the "List" name and a lot of the notation survives.
12 : : *
13 : : * One important concession to the original implementation is that an empty
14 : : * list is always represented by a null pointer (preferentially written NIL).
15 : : * Non-empty lists have a header, which will not be relocated as long as the
16 : : * list remains non-empty, and an expansible data array.
17 : : *
18 : : * We support four 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 : : * T_XidList: lists of TransactionIds
26 : : * (the XidList infrastructure is less complete than the other cases)
27 : : *
28 : : * (At the moment, ints, Oids, and XIDs are the same size, but they may not
29 : : * always be so; be careful to use the appropriate list type for your data.)
30 : : *
31 : : *
32 : : * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group
33 : : * Portions Copyright (c) 1994, Regents of the University of California
34 : : *
35 : : * src/include/nodes/pg_list.h
36 : : *
37 : : *-------------------------------------------------------------------------
38 : : */
39 : : #ifndef PG_LIST_H
40 : : #define PG_LIST_H
41 : :
42 : : #include "nodes/nodes.h"
43 : :
44 : :
45 : : typedef union ListCell
46 : : {
47 : : void *ptr_value;
48 : : int int_value;
49 : : Oid oid_value;
50 : : TransactionId xid_value;
51 : : } ListCell;
52 : :
53 : : typedef struct List
54 : : {
55 : : NodeTag type; /* T_List, T_IntList, T_OidList, or T_XidList */
56 : : int length; /* number of elements currently present */
57 : : int max_length; /* allocated length of elements[] */
58 : : ListCell *elements; /* re-allocatable array of cells */
59 : : /* We may allocate some cells along with the List header: */
60 : : ListCell initial_elements[FLEXIBLE_ARRAY_MEMBER];
61 : : /* If elements == initial_elements, it's not a separate allocation */
62 : : } List;
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.
67 : : */
68 : : #define NIL ((List *) NULL)
69 : :
70 : : /*
71 : : * State structs for various looping macros below.
72 : : */
73 : : typedef struct ForEachState
74 : : {
75 : : const List *l; /* list we're looping through */
76 : : int i; /* current element index */
77 : : } ForEachState;
78 : :
79 : : typedef struct ForBothState
80 : : {
81 : : const List *l1; /* lists we're looping through */
82 : : const List *l2;
83 : : int i; /* common element index */
84 : : } ForBothState;
85 : :
86 : : typedef struct ForBothCellState
87 : : {
88 : : const List *l1; /* lists we're looping through */
89 : : const List *l2;
90 : : int i1; /* current element indexes */
91 : : int i2;
92 : : } ForBothCellState;
93 : :
94 : : typedef struct ForThreeState
95 : : {
96 : : const List *l1; /* lists we're looping through */
97 : : const List *l2;
98 : : const List *l3;
99 : : int i; /* common element index */
100 : : } ForThreeState;
101 : :
102 : : typedef struct ForFourState
103 : : {
104 : : const List *l1; /* lists we're looping through */
105 : : const List *l2;
106 : : const List *l3;
107 : : const List *l4;
108 : : int i; /* common element index */
109 : : } ForFourState;
110 : :
111 : : typedef struct ForFiveState
112 : : {
113 : : const List *l1; /* lists we're looping through */
114 : : const List *l2;
115 : : const List *l3;
116 : : const List *l4;
117 : : const List *l5;
118 : : int i; /* common element index */
119 : : } ForFiveState;
120 : :
121 : : /*
122 : : * These routines are small enough, and used often enough, to justify being
123 : : * inline.
124 : : */
125 : :
126 : : /* Fetch address of list's first cell; NULL if empty list */
127 : : static inline ListCell *
5263 peter_e@gmx.net 128 :CBC 25848096 : list_head(const List *l)
129 : : {
2486 tgl@sss.pgh.pa.us 130 [ + + ]: 25848096 : return l ? &l->elements[0] : NULL;
131 : : }
132 : :
133 : : /* Fetch address of list's last cell; NULL if empty list */
134 : : static inline ListCell *
135 : : list_tail(const List *l)
136 : : {
137 : : return l ? &l->elements[l->length - 1] : NULL;
138 : : }
139 : :
140 : : /* Fetch address of list's second cell, if it has one, else NULL */
141 : : static inline ListCell *
142 : 95785 : list_second_cell(const List *l)
143 : : {
144 [ + - + + ]: 95785 : if (l && l->length >= 2)
145 : 90379 : return &l->elements[1];
146 : : else
147 : 5406 : return NULL;
148 : : }
149 : :
150 : : /* Fetch list's length */
151 : : static inline int
5263 peter_e@gmx.net 152 : 73691787 : list_length(const List *l)
153 : : {
8014 neilc@samurai.com 154 [ + + ]: 73691787 : return l ? l->length : 0;
155 : : }
156 : :
157 : : /*
158 : : * Macros to access the data values within List cells.
159 : : *
160 : : * Note that with the exception of the "xxx_node" macros, these are
161 : : * lvalues and can be assigned to.
162 : : *
163 : : * NB: There is an unfortunate legacy from a previous incarnation of
164 : : * the List API: the macro lfirst() was used to mean "the data in this
165 : : * cons cell". To avoid changing every usage of lfirst(), that meaning
166 : : * has been kept. As a result, lfirst() takes a ListCell and returns
167 : : * the data it contains; to get the data in the first cell of a
168 : : * List, use linitial(). Worse, lsecond() is more closely related to
169 : : * linitial() than lfirst(): given a List, lsecond() returns the data
170 : : * in the second list cell.
171 : : */
172 : : #define lfirst(lc) ((lc)->ptr_value)
173 : : #define lfirst_int(lc) ((lc)->int_value)
174 : : #define lfirst_oid(lc) ((lc)->oid_value)
175 : : #define lfirst_xid(lc) ((lc)->xid_value)
176 : : #define lfirst_node(type,lc) castNode(type, lfirst(lc))
177 : :
178 : : #define linitial(l) lfirst(list_nth_cell(l, 0))
179 : : #define linitial_int(l) lfirst_int(list_nth_cell(l, 0))
180 : : #define linitial_oid(l) lfirst_oid(list_nth_cell(l, 0))
181 : : #define linitial_node(type,l) castNode(type, linitial(l))
182 : :
183 : : #define lsecond(l) lfirst(list_nth_cell(l, 1))
184 : : #define lsecond_int(l) lfirst_int(list_nth_cell(l, 1))
185 : : #define lsecond_oid(l) lfirst_oid(list_nth_cell(l, 1))
186 : : #define lsecond_node(type,l) castNode(type, lsecond(l))
187 : :
188 : : #define lthird(l) lfirst(list_nth_cell(l, 2))
189 : : #define lthird_int(l) lfirst_int(list_nth_cell(l, 2))
190 : : #define lthird_oid(l) lfirst_oid(list_nth_cell(l, 2))
191 : : #define lthird_node(type,l) castNode(type, lthird(l))
192 : :
193 : : #define lfourth(l) lfirst(list_nth_cell(l, 3))
194 : : #define lfourth_int(l) lfirst_int(list_nth_cell(l, 3))
195 : : #define lfourth_oid(l) lfirst_oid(list_nth_cell(l, 3))
196 : : #define lfourth_node(type,l) castNode(type, lfourth(l))
197 : :
198 : : #define llast(l) lfirst(list_last_cell(l))
199 : : #define llast_int(l) lfirst_int(list_last_cell(l))
200 : : #define llast_oid(l) lfirst_oid(list_last_cell(l))
201 : : #define llast_xid(l) lfirst_xid(list_last_cell(l))
202 : : #define llast_node(type,l) castNode(type, llast(l))
203 : :
204 : : /*
205 : : * Convenience macros for building fixed-length lists
206 : : */
207 : :
208 : : static inline ListCell
40 peter@eisentraut.org 209 :GNC 11574105 : list_make_ptr_cell(void *v)
210 : : {
211 : : ListCell c;
212 : :
213 : 11574105 : c.ptr_value = v;
214 : 11574105 : return c;
215 : : }
216 : :
217 : : static inline ListCell
218 : 137001 : list_make_int_cell(int v)
219 : : {
220 : : ListCell c;
221 : :
222 : 137001 : c.int_value = v;
223 : 137001 : return c;
224 : : }
225 : :
226 : : static inline ListCell
227 : 59169 : list_make_oid_cell(Oid v)
228 : : {
229 : : ListCell c;
230 : :
231 : 59169 : c.oid_value = v;
232 : 59169 : return c;
233 : : }
234 : :
235 : : static inline ListCell
236 : : list_make_xid_cell(TransactionId v)
237 : : {
238 : : ListCell c;
239 : :
240 : : c.xid_value = v;
241 : : return c;
242 : : }
243 : :
244 : : #define list_make1(x1) \
245 : : list_make1_impl(T_List, list_make_ptr_cell(x1))
246 : : #define list_make2(x1,x2) \
247 : : list_make2_impl(T_List, list_make_ptr_cell(x1), list_make_ptr_cell(x2))
248 : : #define list_make3(x1,x2,x3) \
249 : : list_make3_impl(T_List, list_make_ptr_cell(x1), list_make_ptr_cell(x2), \
250 : : list_make_ptr_cell(x3))
251 : : #define list_make4(x1,x2,x3,x4) \
252 : : list_make4_impl(T_List, list_make_ptr_cell(x1), list_make_ptr_cell(x2), \
253 : : list_make_ptr_cell(x3), list_make_ptr_cell(x4))
254 : : #define list_make5(x1,x2,x3,x4,x5) \
255 : : list_make5_impl(T_List, list_make_ptr_cell(x1), list_make_ptr_cell(x2), \
256 : : list_make_ptr_cell(x3), list_make_ptr_cell(x4), \
257 : : list_make_ptr_cell(x5))
258 : :
259 : : #define list_make1_int(x1) \
260 : : list_make1_impl(T_IntList, list_make_int_cell(x1))
261 : : #define list_make2_int(x1,x2) \
262 : : list_make2_impl(T_IntList, list_make_int_cell(x1), list_make_int_cell(x2))
263 : : #define list_make3_int(x1,x2,x3) \
264 : : list_make3_impl(T_IntList, list_make_int_cell(x1), list_make_int_cell(x2), \
265 : : list_make_int_cell(x3))
266 : : #define list_make4_int(x1,x2,x3,x4) \
267 : : list_make4_impl(T_IntList, list_make_int_cell(x1), list_make_int_cell(x2), \
268 : : list_make_int_cell(x3), list_make_int_cell(x4))
269 : : #define list_make5_int(x1,x2,x3,x4,x5) \
270 : : list_make5_impl(T_IntList, list_make_int_cell(x1), list_make_int_cell(x2), \
271 : : list_make_int_cell(x3), list_make_int_cell(x4), \
272 : : list_make_int_cell(x5))
273 : :
274 : : #define list_make1_oid(x1) \
275 : : list_make1_impl(T_OidList, list_make_oid_cell(x1))
276 : : #define list_make2_oid(x1,x2) \
277 : : list_make2_impl(T_OidList, list_make_oid_cell(x1), list_make_oid_cell(x2))
278 : : #define list_make3_oid(x1,x2,x3) \
279 : : list_make3_impl(T_OidList, list_make_oid_cell(x1), list_make_oid_cell(x2), \
280 : : list_make_oid_cell(x3))
281 : : #define list_make4_oid(x1,x2,x3,x4) \
282 : : list_make4_impl(T_OidList, list_make_oid_cell(x1), list_make_oid_cell(x2), \
283 : : list_make_oid_cell(x3), list_make_oid_cell(x4))
284 : : #define list_make5_oid(x1,x2,x3,x4,x5) \
285 : : list_make5_impl(T_OidList, list_make_oid_cell(x1), list_make_oid_cell(x2), \
286 : : list_make_oid_cell(x3), list_make_oid_cell(x4), \
287 : : list_make_oid_cell(x5))
288 : :
289 : : #define list_make1_xid(x1) \
290 : : list_make1_impl(T_XidList, list_make_xid_cell(x1))
291 : : #define list_make2_xid(x1,x2) \
292 : : list_make2_impl(T_XidList, list_make_xid_cell(x1), list_make_xid_cell(x2))
293 : : #define list_make3_xid(x1,x2,x3) \
294 : : list_make3_impl(T_XidList, list_make_xid_cell(x1), list_make_xid_cell(x2), \
295 : : list_make_xid_cell(x3))
296 : : #define list_make4_xid(x1,x2,x3,x4) \
297 : : list_make4_impl(T_XidList, list_make_xid_cell(x1), list_make_xid_cell(x2), \
298 : : list_make_xid_cell(x3), list_make_xid_cell(x4))
299 : : #define list_make5_xid(x1,x2,x3,x4,x5) \
300 : : list_make5_impl(T_XidList, list_make_xid_cell(x1), list_make_xid_cell(x2), \
301 : : list_make_xid_cell(x3), list_make_xid_cell(x4), \
302 : : list_make_xid_cell(x5))
303 : :
304 : : /*
305 : : * Locate the n'th cell (counting from 0) of the list.
306 : : * It is an assertion failure if there is no such cell.
307 : : */
308 : : static inline ListCell *
2486 tgl@sss.pgh.pa.us 309 :CBC 59811870 : list_nth_cell(const List *list, int n)
310 : : {
311 [ - + ]: 59811870 : Assert(list != NIL);
312 [ + - - + ]: 59811870 : Assert(n >= 0 && n < list->length);
313 : 59811870 : return &list->elements[n];
314 : : }
315 : :
316 : : /*
317 : : * Return the last cell in a non-NIL List.
318 : : */
319 : : static inline ListCell *
2045 drowley@postgresql.o 320 : 80602444 : list_last_cell(const List *list)
321 : : {
322 [ - + ]: 80602444 : Assert(list != NIL);
323 : 80602444 : return &list->elements[list->length - 1];
324 : : }
325 : :
326 : : /*
327 : : * Return the pointer value contained in the n'th element of the
328 : : * specified list. (List elements begin at 0.)
329 : : */
330 : : static inline void *
2486 tgl@sss.pgh.pa.us 331 : 23071404 : list_nth(const List *list, int n)
332 : : {
333 [ - + ]: 23071404 : Assert(IsA(list, List));
334 : 23071404 : return lfirst(list_nth_cell(list, n));
335 : : }
336 : :
337 : : /*
338 : : * Return the integer value contained in the n'th element of the
339 : : * specified list.
340 : : */
341 : : static inline int
342 : 14982 : list_nth_int(const List *list, int n)
343 : : {
344 [ - + ]: 14982 : Assert(IsA(list, IntList));
345 : 14982 : return lfirst_int(list_nth_cell(list, n));
346 : : }
347 : :
348 : : /*
349 : : * Return the OID value contained in the n'th element of the specified
350 : : * list.
351 : : */
352 : : static inline Oid
353 : 10744 : list_nth_oid(const List *list, int n)
354 : : {
355 [ - + ]: 10744 : Assert(IsA(list, OidList));
356 : 10744 : return lfirst_oid(list_nth_cell(list, n));
357 : : }
358 : :
359 : : #define list_nth_node(type,list,n) castNode(type, list_nth(list, n))
360 : :
361 : : /*
362 : : * Get the given ListCell's index (from 0) in the given List.
363 : : */
364 : : static inline int
365 : 161740 : list_cell_number(const List *l, const ListCell *c)
366 : : {
367 [ + - - + ]: 161740 : Assert(c >= &l->elements[0] && c < &l->elements[l->length]);
368 : 161740 : return c - l->elements;
369 : : }
370 : :
371 : : /*
372 : : * Get the address of the next cell after "c" within list "l", or NULL if none.
373 : : */
374 : : static inline ListCell *
375 : 14931422 : lnext(const List *l, const ListCell *c)
376 : : {
377 [ + - - + ]: 14931422 : Assert(c >= &l->elements[0] && c < &l->elements[l->length]);
378 : 14931422 : c++;
379 [ + + ]: 14931422 : if (c < &l->elements[l->length])
380 : 7929683 : return (ListCell *) c;
381 : : else
382 : 7001739 : return NULL;
383 : : }
384 : :
385 : : /*
386 : : * foreach -
387 : : * a convenience macro for looping through a list
388 : : *
389 : : * "cell" must be the name of a "ListCell *" variable; it's made to point
390 : : * to each List element in turn. "cell" will be NULL after normal exit from
391 : : * the loop, but an early "break" will leave it pointing at the current
392 : : * List element.
393 : : *
394 : : * Beware of changing the List object while the loop is iterating.
395 : : * The current semantics are that we examine successive list indices in
396 : : * each iteration, so that insertion or deletion of list elements could
397 : : * cause elements to be re-visited or skipped unexpectedly. Previous
398 : : * implementations of foreach() behaved differently. However, it's safe
399 : : * to append elements to the List (or in general, insert them after the
400 : : * current element); such new elements are guaranteed to be visited.
401 : : * Also, the current element of the List can be deleted, if you use
402 : : * foreach_delete_current() to do so. BUT: either of these actions will
403 : : * invalidate the "cell" pointer for the remainder of the current iteration.
404 : : */
405 : : #define foreach(cell, lst) \
406 : : for (ForEachState cell##__state = {(lst), 0}; \
407 : : (cell##__state.l != NIL && \
408 : : cell##__state.i < cell##__state.l->length) ? \
409 : : (cell = &cell##__state.l->elements[cell##__state.i], true) : \
410 : : (cell = NULL, false); \
411 : : cell##__state.i++)
412 : :
413 : : /*
414 : : * foreach_delete_current -
415 : : * delete the current list element from the List associated with a
416 : : * surrounding foreach() or foreach_*() loop, returning the new List
417 : : * pointer; pass the name of the iterator variable.
418 : : *
419 : : * This is similar to list_delete_cell(), but it also adjusts the loop's state
420 : : * so that no list elements will be missed. Do not delete elements from an
421 : : * active foreach or foreach_* loop's list in any other way!
422 : : */
423 : : #define foreach_delete_current(lst, var_or_cell) \
424 : : ((List *) (var_or_cell##__state.l = list_delete_nth_cell(lst, var_or_cell##__state.i--)))
425 : :
426 : : /*
427 : : * foreach_current_index -
428 : : * get the zero-based list index of a surrounding foreach() or foreach_*()
429 : : * loop's current element; pass the name of the iterator variable.
430 : : *
431 : : * Beware of using this after foreach_delete_current(); the value will be
432 : : * out of sync for the rest of the current loop iteration. Anyway, since
433 : : * you just deleted the current element, the value is pretty meaningless.
434 : : */
435 : : #define foreach_current_index(var_or_cell) (var_or_cell##__state.i)
436 : :
437 : : /*
438 : : * for_each_from -
439 : : * Like foreach(), but start from the N'th (zero-based) list element,
440 : : * not necessarily the first one.
441 : : *
442 : : * It's okay for N to exceed the list length, but not for it to be negative.
443 : : *
444 : : * The caveats for foreach() apply equally here.
445 : : */
446 : : #define for_each_from(cell, lst, N) \
447 : : for (ForEachState cell##__state = for_each_from_setup(lst, N); \
448 : : (cell##__state.l != NIL && \
449 : : cell##__state.i < cell##__state.l->length) ? \
450 : : (cell = &cell##__state.l->elements[cell##__state.i], true) : \
451 : : (cell = NULL, false); \
452 : : cell##__state.i++)
453 : :
454 : : static inline ForEachState
2045 455 : 640322 : for_each_from_setup(const List *lst, int N)
456 : : {
457 : 640322 : ForEachState r = {lst, N};
458 : :
459 [ - + ]: 640322 : Assert(N >= 0);
460 : 640322 : return r;
461 : : }
462 : :
463 : : /*
464 : : * for_each_cell -
465 : : * a convenience macro which loops through a list starting from a
466 : : * specified cell
467 : : *
468 : : * The caveats for foreach() apply equally here.
469 : : */
470 : : #define for_each_cell(cell, lst, initcell) \
471 : : for (ForEachState cell##__state = for_each_cell_setup(lst, initcell); \
472 : : (cell##__state.l != NIL && \
473 : : cell##__state.i < cell##__state.l->length) ? \
474 : : (cell = &cell##__state.l->elements[cell##__state.i], true) : \
475 : : (cell = NULL, false); \
476 : : cell##__state.i++)
477 : :
478 : : static inline ForEachState
479 : 160892 : for_each_cell_setup(const List *lst, const ListCell *initcell)
480 : : {
2486 481 : 321784 : ForEachState r = {lst,
482 [ + + ]: 160892 : initcell ? list_cell_number(lst, initcell) : list_length(lst)};
483 : :
484 : 160892 : return r;
485 : : }
486 : :
487 : : /*
488 : : * Convenience macros that loop through a list without needing a separate
489 : : * "ListCell *" variable. Instead, the macros declare a locally-scoped loop
490 : : * variable with the provided name and the appropriate type.
491 : : *
492 : : * Since the variable is scoped to the loop, it's not possible to detect an
493 : : * early break by checking its value after the loop completes, as is common
494 : : * practice. If you need to do this, you can either use foreach() instead or
495 : : * manually track early breaks with a separate variable declared outside of the
496 : : * loop.
497 : : *
498 : : * Note that the caveats described in the comment above the foreach() macro
499 : : * also apply to these convenience macros.
500 : : */
501 : : #define foreach_ptr(type, var, lst) foreach_internal(type, *, var, lst, lfirst)
502 : : #define foreach_int(var, lst) foreach_internal(int, , var, lst, lfirst_int)
503 : : #define foreach_oid(var, lst) foreach_internal(Oid, , var, lst, lfirst_oid)
504 : : #define foreach_xid(var, lst) foreach_internal(TransactionId, , var, lst, lfirst_xid)
505 : :
506 : : /*
507 : : * The internal implementation of the above macros. Do not use directly.
508 : : *
509 : : * This macro actually generates two loops in order to declare two variables of
510 : : * different types. The outer loop only iterates once, so we expect optimizing
511 : : * compilers will unroll it, thereby optimizing it away.
512 : : */
513 : : #define foreach_internal(type, pointer, var, lst, func) \
514 : : for (type pointer var = 0, pointer var##__outerloop = (type pointer) 1; \
515 : : var##__outerloop; \
516 : : var##__outerloop = 0) \
517 : : for (ForEachState var##__state = {(lst), 0}; \
518 : : (var##__state.l != NIL && \
519 : : var##__state.i < var##__state.l->length && \
520 : : (var = (type pointer) func(&var##__state.l->elements[var##__state.i]), true)); \
521 : : var##__state.i++)
522 : :
523 : : /*
524 : : * foreach_node -
525 : : * The same as foreach_ptr, but asserts that the element is of the specified
526 : : * node type.
527 : : */
528 : : #define foreach_node(type, var, lst) \
529 : : for (type * var = 0, *var##__outerloop = (type *) 1; \
530 : : var##__outerloop; \
531 : : var##__outerloop = 0) \
532 : : for (ForEachState var##__state = {(lst), 0}; \
533 : : (var##__state.l != NIL && \
534 : : var##__state.i < var##__state.l->length && \
535 : : (var = lfirst_node(type, &var##__state.l->elements[var##__state.i]), true)); \
536 : : var##__state.i++)
537 : :
538 : : /*
539 : : * forboth -
540 : : * a convenience macro for advancing through two linked lists
541 : : * simultaneously. This macro loops through both lists at the same
542 : : * time, stopping when either list runs out of elements. Depending
543 : : * on the requirements of the call site, it may also be wise to
544 : : * assert that the lengths of the two lists are equal. (But, if they
545 : : * are not, some callers rely on the ending cell values being separately
546 : : * NULL or non-NULL as defined here; don't try to optimize that.)
547 : : *
548 : : * The caveats for foreach() apply equally here.
549 : : */
550 : : #define forboth(cell1, list1, cell2, list2) \
551 : : for (ForBothState cell1##__state = {(list1), (list2), 0}; \
552 : : multi_for_advance_cell(cell1, cell1##__state, l1, i), \
553 : : multi_for_advance_cell(cell2, cell1##__state, l2, i), \
554 : : (cell1 != NULL && cell2 != NULL); \
555 : : cell1##__state.i++)
556 : :
557 : : #define multi_for_advance_cell(cell, state, l, i) \
558 : : (cell = (state.l != NIL && state.i < state.l->length) ? \
559 : : &state.l->elements[state.i] : NULL)
560 : :
561 : : /*
562 : : * for_both_cell -
563 : : * a convenience macro which loops through two lists starting from the
564 : : * specified cells of each. This macro loops through both lists at the same
565 : : * time, stopping when either list runs out of elements. Depending on the
566 : : * requirements of the call site, it may also be wise to assert that the
567 : : * lengths of the two lists are equal, and initcell1 and initcell2 are at
568 : : * the same position in the respective lists.
569 : : *
570 : : * The caveats for foreach() apply equally here.
571 : : */
572 : : #define for_both_cell(cell1, list1, initcell1, cell2, list2, initcell2) \
573 : : for (ForBothCellState cell1##__state = \
574 : : for_both_cell_setup(list1, initcell1, list2, initcell2); \
575 : : multi_for_advance_cell(cell1, cell1##__state, l1, i1), \
576 : : multi_for_advance_cell(cell2, cell1##__state, l2, i2), \
577 : : (cell1 != NULL && cell2 != NULL); \
578 : : cell1##__state.i1++, cell1##__state.i2++)
579 : :
580 : : static inline ForBothCellState
2045 581 : 2956 : for_both_cell_setup(const List *list1, const ListCell *initcell1,
582 : : const List *list2, const ListCell *initcell2)
583 : : {
2486 584 : 8868 : ForBothCellState r = {list1, list2,
585 [ + - ]: 2956 : initcell1 ? list_cell_number(list1, initcell1) : list_length(list1),
586 [ + - ]: 2956 : initcell2 ? list_cell_number(list2, initcell2) : list_length(list2)};
587 : :
588 : 2956 : return r;
589 : : }
590 : :
591 : : /*
592 : : * forthree -
593 : : * the same for three lists
594 : : */
595 : : #define forthree(cell1, list1, cell2, list2, cell3, list3) \
596 : : for (ForThreeState cell1##__state = {(list1), (list2), (list3), 0}; \
597 : : multi_for_advance_cell(cell1, cell1##__state, l1, i), \
598 : : multi_for_advance_cell(cell2, cell1##__state, l2, i), \
599 : : multi_for_advance_cell(cell3, cell1##__state, l3, i), \
600 : : (cell1 != NULL && cell2 != NULL && cell3 != NULL); \
601 : : cell1##__state.i++)
602 : :
603 : : /*
604 : : * forfour -
605 : : * the same for four lists
606 : : */
607 : : #define forfour(cell1, list1, cell2, list2, cell3, list3, cell4, list4) \
608 : : for (ForFourState cell1##__state = {(list1), (list2), (list3), (list4), 0}; \
609 : : multi_for_advance_cell(cell1, cell1##__state, l1, i), \
610 : : multi_for_advance_cell(cell2, cell1##__state, l2, i), \
611 : : multi_for_advance_cell(cell3, cell1##__state, l3, i), \
612 : : multi_for_advance_cell(cell4, cell1##__state, l4, i), \
613 : : (cell1 != NULL && cell2 != NULL && cell3 != NULL && cell4 != NULL); \
614 : : cell1##__state.i++)
615 : :
616 : : /*
617 : : * forfive -
618 : : * the same for five lists
619 : : */
620 : : #define forfive(cell1, list1, cell2, list2, cell3, list3, cell4, list4, cell5, list5) \
621 : : for (ForFiveState cell1##__state = {(list1), (list2), (list3), (list4), (list5), 0}; \
622 : : multi_for_advance_cell(cell1, cell1##__state, l1, i), \
623 : : multi_for_advance_cell(cell2, cell1##__state, l2, i), \
624 : : multi_for_advance_cell(cell3, cell1##__state, l3, i), \
625 : : multi_for_advance_cell(cell4, cell1##__state, l4, i), \
626 : : multi_for_advance_cell(cell5, cell1##__state, l5, i), \
627 : : (cell1 != NULL && cell2 != NULL && cell3 != NULL && \
628 : : cell4 != NULL && cell5 != NULL); \
629 : : cell1##__state.i++)
630 : :
631 : : /* Functions in src/backend/nodes/list.c */
632 : :
633 : : extern List *list_make1_impl(NodeTag t, ListCell datum1);
634 : : extern List *list_make2_impl(NodeTag t, ListCell datum1, ListCell datum2);
635 : : extern List *list_make3_impl(NodeTag t, ListCell datum1, ListCell datum2,
636 : : ListCell datum3);
637 : : extern List *list_make4_impl(NodeTag t, ListCell datum1, ListCell datum2,
638 : : ListCell datum3, ListCell datum4);
639 : : extern List *list_make5_impl(NodeTag t, ListCell datum1, ListCell datum2,
640 : : ListCell datum3, ListCell datum4,
641 : : ListCell datum5);
642 : :
643 : : pg_nodiscard extern List *lappend(List *list, void *datum);
644 : : pg_nodiscard extern List *lappend_int(List *list, int datum);
645 : : pg_nodiscard extern List *lappend_oid(List *list, Oid datum);
646 : : pg_nodiscard extern List *lappend_xid(List *list, TransactionId datum);
647 : :
648 : : pg_nodiscard extern List *list_insert_nth(List *list, int pos, void *datum);
649 : : pg_nodiscard extern List *list_insert_nth_int(List *list, int pos, int datum);
650 : : pg_nodiscard extern List *list_insert_nth_oid(List *list, int pos, Oid datum);
651 : :
652 : : pg_nodiscard extern List *lcons(void *datum, List *list);
653 : : pg_nodiscard extern List *lcons_int(int datum, List *list);
654 : : pg_nodiscard extern List *lcons_oid(Oid datum, List *list);
655 : :
656 : : pg_nodiscard extern List *list_concat(List *list1, const List *list2);
657 : : pg_nodiscard extern List *list_concat_copy(const List *list1, const List *list2);
658 : :
659 : : pg_nodiscard extern List *list_truncate(List *list, int new_size);
660 : :
661 : : extern bool list_member(const List *list, const void *datum);
662 : : extern bool list_member_ptr(const List *list, const void *datum);
663 : : extern bool list_member_int(const List *list, int datum);
664 : : extern bool list_member_oid(const List *list, Oid datum);
665 : : extern bool list_member_xid(const List *list, TransactionId datum);
666 : :
667 : : pg_nodiscard extern List *list_delete(List *list, void *datum);
668 : : pg_nodiscard extern List *list_delete_ptr(List *list, void *datum);
669 : : pg_nodiscard extern List *list_delete_int(List *list, int datum);
670 : : pg_nodiscard extern List *list_delete_oid(List *list, Oid datum);
671 : : pg_nodiscard extern List *list_delete_first(List *list);
672 : : pg_nodiscard extern List *list_delete_last(List *list);
673 : : pg_nodiscard extern List *list_delete_first_n(List *list, int n);
674 : : pg_nodiscard extern List *list_delete_nth_cell(List *list, int n);
675 : : pg_nodiscard extern List *list_delete_cell(List *list, ListCell *cell);
676 : :
677 : : extern List *list_union(const List *list1, const List *list2);
678 : : extern List *list_union_ptr(const List *list1, const List *list2);
679 : : extern List *list_union_int(const List *list1, const List *list2);
680 : : extern List *list_union_oid(const List *list1, const List *list2);
681 : :
682 : : extern List *list_intersection(const List *list1, const List *list2);
683 : : extern List *list_intersection_int(const List *list1, const List *list2);
684 : :
685 : : /* currently, there's no need for list_intersection_ptr etc */
686 : :
687 : : extern List *list_difference(const List *list1, const List *list2);
688 : : extern List *list_difference_ptr(const List *list1, const List *list2);
689 : : extern List *list_difference_int(const List *list1, const List *list2);
690 : : extern List *list_difference_oid(const List *list1, const List *list2);
691 : :
692 : : pg_nodiscard extern List *list_append_unique(List *list, void *datum);
693 : : pg_nodiscard extern List *list_append_unique_ptr(List *list, void *datum);
694 : : pg_nodiscard extern List *list_append_unique_int(List *list, int datum);
695 : : pg_nodiscard extern List *list_append_unique_oid(List *list, Oid datum);
696 : :
697 : : pg_nodiscard extern List *list_concat_unique(List *list1, const List *list2);
698 : : pg_nodiscard extern List *list_concat_unique_ptr(List *list1, const List *list2);
699 : : pg_nodiscard extern List *list_concat_unique_int(List *list1, const List *list2);
700 : : pg_nodiscard extern List *list_concat_unique_oid(List *list1, const List *list2);
701 : :
702 : : extern void list_deduplicate_oid(List *list);
703 : :
704 : : extern void list_free(List *list);
705 : : extern void list_free_deep(List *list);
706 : :
707 : : pg_nodiscard extern List *list_copy(const List *oldlist);
708 : : pg_nodiscard extern List *list_copy_head(const List *oldlist, int len);
709 : : pg_nodiscard extern List *list_copy_tail(const List *oldlist, int nskip);
710 : : pg_nodiscard extern List *list_copy_deep(const List *oldlist);
711 : :
712 : : typedef int (*list_sort_comparator) (const ListCell *a, const ListCell *b);
713 : : extern void list_sort(List *list, list_sort_comparator cmp);
714 : :
715 : : extern int list_int_cmp(const ListCell *p1, const ListCell *p2);
716 : : extern int list_oid_cmp(const ListCell *p1, const ListCell *p2);
717 : :
718 : : #endif /* PG_LIST_H */
|
