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-2023, 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 *
128 27620168 : list_head(const List *l)
129 : {
130 27620168 : 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 122450 : list_second_cell(const List *l)
143 : {
144 122450 : if (l && l->length >= 2)
145 118538 : return &l->elements[1];
146 : else
147 3912 : return NULL;
148 : }
149 :
150 : /* Fetch list's length */
151 : static inline int
152 69824114 : list_length(const List *l)
153 : {
154 69824114 : 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 : #define list_make_ptr_cell(v) ((ListCell) {.ptr_value = (v)})
208 : #define list_make_int_cell(v) ((ListCell) {.int_value = (v)})
209 : #define list_make_oid_cell(v) ((ListCell) {.oid_value = (v)})
210 : #define list_make_xid_cell(v) ((ListCell) {.xid_value = (v)})
211 :
212 : #define list_make1(x1) \
213 : list_make1_impl(T_List, list_make_ptr_cell(x1))
214 : #define list_make2(x1,x2) \
215 : list_make2_impl(T_List, list_make_ptr_cell(x1), list_make_ptr_cell(x2))
216 : #define list_make3(x1,x2,x3) \
217 : list_make3_impl(T_List, list_make_ptr_cell(x1), list_make_ptr_cell(x2), \
218 : list_make_ptr_cell(x3))
219 : #define list_make4(x1,x2,x3,x4) \
220 : list_make4_impl(T_List, list_make_ptr_cell(x1), list_make_ptr_cell(x2), \
221 : list_make_ptr_cell(x3), list_make_ptr_cell(x4))
222 : #define list_make5(x1,x2,x3,x4,x5) \
223 : list_make5_impl(T_List, list_make_ptr_cell(x1), list_make_ptr_cell(x2), \
224 : list_make_ptr_cell(x3), list_make_ptr_cell(x4), \
225 : list_make_ptr_cell(x5))
226 :
227 : #define list_make1_int(x1) \
228 : list_make1_impl(T_IntList, list_make_int_cell(x1))
229 : #define list_make2_int(x1,x2) \
230 : list_make2_impl(T_IntList, list_make_int_cell(x1), list_make_int_cell(x2))
231 : #define list_make3_int(x1,x2,x3) \
232 : list_make3_impl(T_IntList, list_make_int_cell(x1), list_make_int_cell(x2), \
233 : list_make_int_cell(x3))
234 : #define list_make4_int(x1,x2,x3,x4) \
235 : list_make4_impl(T_IntList, list_make_int_cell(x1), list_make_int_cell(x2), \
236 : list_make_int_cell(x3), list_make_int_cell(x4))
237 : #define list_make5_int(x1,x2,x3,x4,x5) \
238 : list_make5_impl(T_IntList, list_make_int_cell(x1), list_make_int_cell(x2), \
239 : list_make_int_cell(x3), list_make_int_cell(x4), \
240 : list_make_int_cell(x5))
241 :
242 : #define list_make1_oid(x1) \
243 : list_make1_impl(T_OidList, list_make_oid_cell(x1))
244 : #define list_make2_oid(x1,x2) \
245 : list_make2_impl(T_OidList, list_make_oid_cell(x1), list_make_oid_cell(x2))
246 : #define list_make3_oid(x1,x2,x3) \
247 : list_make3_impl(T_OidList, list_make_oid_cell(x1), list_make_oid_cell(x2), \
248 : list_make_oid_cell(x3))
249 : #define list_make4_oid(x1,x2,x3,x4) \
250 : list_make4_impl(T_OidList, list_make_oid_cell(x1), list_make_oid_cell(x2), \
251 : list_make_oid_cell(x3), list_make_oid_cell(x4))
252 : #define list_make5_oid(x1,x2,x3,x4,x5) \
253 : list_make5_impl(T_OidList, list_make_oid_cell(x1), list_make_oid_cell(x2), \
254 : list_make_oid_cell(x3), list_make_oid_cell(x4), \
255 : list_make_oid_cell(x5))
256 :
257 : #define list_make1_xid(x1) \
258 : list_make1_impl(T_XidList, list_make_xid_cell(x1))
259 : #define list_make2_xid(x1,x2) \
260 : list_make2_impl(T_XidList, list_make_xid_cell(x1), list_make_xid_cell(x2))
261 : #define list_make3_xid(x1,x2,x3) \
262 : list_make3_impl(T_XidList, list_make_xid_cell(x1), list_make_xid_cell(x2), \
263 : list_make_xid_cell(x3))
264 : #define list_make4_xid(x1,x2,x3,x4) \
265 : list_make4_impl(T_XidList, list_make_xid_cell(x1), list_make_xid_cell(x2), \
266 : list_make_xid_cell(x3), list_make_xid_cell(x4))
267 : #define list_make5_xid(x1,x2,x3,x4,x5) \
268 : list_make5_impl(T_XidList, list_make_xid_cell(x1), list_make_xid_cell(x2), \
269 : list_make_xid_cell(x3), list_make_xid_cell(x4), \
270 : list_make_xid_cell(x5))
271 :
272 : /*
273 : * Locate the n'th cell (counting from 0) of the list.
274 : * It is an assertion failure if there is no such cell.
275 : */
276 : static inline ListCell *
277 59055862 : list_nth_cell(const List *list, int n)
278 : {
279 : Assert(list != NIL);
280 : Assert(n >= 0 && n < list->length);
281 59055862 : return &list->elements[n];
282 : }
283 :
284 : /*
285 : * Return the last cell in a non-NIL List.
286 : */
287 : static inline ListCell *
288 126982982 : list_last_cell(const List *list)
289 : {
290 : Assert(list != NIL);
291 126982982 : return &list->elements[list->length - 1];
292 : }
293 :
294 : /*
295 : * Return the pointer value contained in the n'th element of the
296 : * specified list. (List elements begin at 0.)
297 : */
298 : static inline void *
299 21753076 : list_nth(const List *list, int n)
300 : {
301 : Assert(IsA(list, List));
302 21753076 : return lfirst(list_nth_cell(list, n));
303 : }
304 :
305 : /*
306 : * Return the integer value contained in the n'th element of the
307 : * specified list.
308 : */
309 : static inline int
310 11476 : list_nth_int(const List *list, int n)
311 : {
312 : Assert(IsA(list, IntList));
313 11476 : return lfirst_int(list_nth_cell(list, n));
314 : }
315 :
316 : /*
317 : * Return the OID value contained in the n'th element of the specified
318 : * list.
319 : */
320 : static inline Oid
321 13908 : list_nth_oid(const List *list, int n)
322 : {
323 : Assert(IsA(list, OidList));
324 13908 : return lfirst_oid(list_nth_cell(list, n));
325 : }
326 :
327 : #define list_nth_node(type,list,n) castNode(type, list_nth(list, n))
328 :
329 : /*
330 : * Get the given ListCell's index (from 0) in the given List.
331 : */
332 : static inline int
333 181082 : list_cell_number(const List *l, const ListCell *c)
334 : {
335 : Assert(c >= &l->elements[0] && c < &l->elements[l->length]);
336 181082 : return c - l->elements;
337 : }
338 :
339 : /*
340 : * Get the address of the next cell after "c" within list "l", or NULL if none.
341 : */
342 : static inline ListCell *
343 50665058 : lnext(const List *l, const ListCell *c)
344 : {
345 : Assert(c >= &l->elements[0] && c < &l->elements[l->length]);
346 50665058 : c++;
347 50665058 : if (c < &l->elements[l->length])
348 33331218 : return (ListCell *) c;
349 : else
350 17333840 : return NULL;
351 : }
352 :
353 : /*
354 : * foreach -
355 : * a convenience macro for looping through a list
356 : *
357 : * "cell" must be the name of a "ListCell *" variable; it's made to point
358 : * to each List element in turn. "cell" will be NULL after normal exit from
359 : * the loop, but an early "break" will leave it pointing at the current
360 : * List element.
361 : *
362 : * Beware of changing the List object while the loop is iterating.
363 : * The current semantics are that we examine successive list indices in
364 : * each iteration, so that insertion or deletion of list elements could
365 : * cause elements to be re-visited or skipped unexpectedly. Previous
366 : * implementations of foreach() behaved differently. However, it's safe
367 : * to append elements to the List (or in general, insert them after the
368 : * current element); such new elements are guaranteed to be visited.
369 : * Also, the current element of the List can be deleted, if you use
370 : * foreach_delete_current() to do so. BUT: either of these actions will
371 : * invalidate the "cell" pointer for the remainder of the current iteration.
372 : */
373 : #define foreach(cell, lst) \
374 : for (ForEachState cell##__state = {(lst), 0}; \
375 : (cell##__state.l != NIL && \
376 : cell##__state.i < cell##__state.l->length) ? \
377 : (cell = &cell##__state.l->elements[cell##__state.i], true) : \
378 : (cell = NULL, false); \
379 : cell##__state.i++)
380 :
381 : /*
382 : * foreach_delete_current -
383 : * delete the current list element from the List associated with a
384 : * surrounding foreach() loop, returning the new List pointer.
385 : *
386 : * This is equivalent to list_delete_cell(), but it also adjusts the foreach
387 : * loop's state so that no list elements will be missed. Do not delete
388 : * elements from an active foreach loop's list in any other way!
389 : */
390 : #define foreach_delete_current(lst, cell) \
391 : (cell##__state.i--, \
392 : (List *) (cell##__state.l = list_delete_cell(lst, cell)))
393 :
394 : /*
395 : * foreach_current_index -
396 : * get the zero-based list index of a surrounding foreach() loop's
397 : * current element; pass the name of the "ListCell *" iterator variable.
398 : *
399 : * Beware of using this after foreach_delete_current(); the value will be
400 : * out of sync for the rest of the current loop iteration. Anyway, since
401 : * you just deleted the current element, the value is pretty meaningless.
402 : */
403 : #define foreach_current_index(cell) (cell##__state.i)
404 :
405 : /*
406 : * for_each_from -
407 : * Like foreach(), but start from the N'th (zero-based) list element,
408 : * not necessarily the first one.
409 : *
410 : * It's okay for N to exceed the list length, but not for it to be negative.
411 : *
412 : * The caveats for foreach() apply equally here.
413 : */
414 : #define for_each_from(cell, lst, N) \
415 : for (ForEachState cell##__state = for_each_from_setup(lst, N); \
416 : (cell##__state.l != NIL && \
417 : cell##__state.i < cell##__state.l->length) ? \
418 : (cell = &cell##__state.l->elements[cell##__state.i], true) : \
419 : (cell = NULL, false); \
420 : cell##__state.i++)
421 :
422 : static inline ForEachState
423 566974 : for_each_from_setup(const List *lst, int N)
424 : {
425 566974 : ForEachState r = {lst, N};
426 :
427 : Assert(N >= 0);
428 566974 : return r;
429 : }
430 :
431 : /*
432 : * for_each_cell -
433 : * a convenience macro which loops through a list starting from a
434 : * specified cell
435 : *
436 : * The caveats for foreach() apply equally here.
437 : */
438 : #define for_each_cell(cell, lst, initcell) \
439 : for (ForEachState cell##__state = for_each_cell_setup(lst, initcell); \
440 : (cell##__state.l != NIL && \
441 : cell##__state.i < cell##__state.l->length) ? \
442 : (cell = &cell##__state.l->elements[cell##__state.i], true) : \
443 : (cell = NULL, false); \
444 : cell##__state.i++)
445 :
446 : static inline ForEachState
447 180216 : for_each_cell_setup(const List *lst, const ListCell *initcell)
448 : {
449 360432 : ForEachState r = {lst,
450 180216 : initcell ? list_cell_number(lst, initcell) : list_length(lst)};
451 :
452 180216 : return r;
453 : }
454 :
455 : /*
456 : * forboth -
457 : * a convenience macro for advancing through two linked lists
458 : * simultaneously. This macro loops through both lists at the same
459 : * time, stopping when either list runs out of elements. Depending
460 : * on the requirements of the call site, it may also be wise to
461 : * assert that the lengths of the two lists are equal. (But, if they
462 : * are not, some callers rely on the ending cell values being separately
463 : * NULL or non-NULL as defined here; don't try to optimize that.)
464 : *
465 : * The caveats for foreach() apply equally here.
466 : */
467 : #define forboth(cell1, list1, cell2, list2) \
468 : for (ForBothState cell1##__state = {(list1), (list2), 0}; \
469 : multi_for_advance_cell(cell1, cell1##__state, l1, i), \
470 : multi_for_advance_cell(cell2, cell1##__state, l2, i), \
471 : (cell1 != NULL && cell2 != NULL); \
472 : cell1##__state.i++)
473 :
474 : #define multi_for_advance_cell(cell, state, l, i) \
475 : (cell = (state.l != NIL && state.i < state.l->length) ? \
476 : &state.l->elements[state.i] : NULL)
477 :
478 : /*
479 : * for_both_cell -
480 : * a convenience macro which loops through two lists starting from the
481 : * specified cells of each. This macro loops through both lists at the same
482 : * time, stopping when either list runs out of elements. Depending on the
483 : * requirements of the call site, it may also be wise to assert that the
484 : * lengths of the two lists are equal, and initcell1 and initcell2 are at
485 : * the same position in the respective lists.
486 : *
487 : * The caveats for foreach() apply equally here.
488 : */
489 : #define for_both_cell(cell1, list1, initcell1, cell2, list2, initcell2) \
490 : for (ForBothCellState cell1##__state = \
491 : for_both_cell_setup(list1, initcell1, list2, initcell2); \
492 : multi_for_advance_cell(cell1, cell1##__state, l1, i1), \
493 : multi_for_advance_cell(cell2, cell1##__state, l2, i2), \
494 : (cell1 != NULL && cell2 != NULL); \
495 : cell1##__state.i1++, cell1##__state.i2++)
496 :
497 : static inline ForBothCellState
498 3282 : for_both_cell_setup(const List *list1, const ListCell *initcell1,
499 : const List *list2, const ListCell *initcell2)
500 : {
501 9846 : ForBothCellState r = {list1, list2,
502 3282 : initcell1 ? list_cell_number(list1, initcell1) : list_length(list1),
503 3282 : initcell2 ? list_cell_number(list2, initcell2) : list_length(list2)};
504 :
505 3282 : return r;
506 : }
507 :
508 : /*
509 : * forthree -
510 : * the same for three lists
511 : */
512 : #define forthree(cell1, list1, cell2, list2, cell3, list3) \
513 : for (ForThreeState cell1##__state = {(list1), (list2), (list3), 0}; \
514 : multi_for_advance_cell(cell1, cell1##__state, l1, i), \
515 : multi_for_advance_cell(cell2, cell1##__state, l2, i), \
516 : multi_for_advance_cell(cell3, cell1##__state, l3, i), \
517 : (cell1 != NULL && cell2 != NULL && cell3 != NULL); \
518 : cell1##__state.i++)
519 :
520 : /*
521 : * forfour -
522 : * the same for four lists
523 : */
524 : #define forfour(cell1, list1, cell2, list2, cell3, list3, cell4, list4) \
525 : for (ForFourState cell1##__state = {(list1), (list2), (list3), (list4), 0}; \
526 : multi_for_advance_cell(cell1, cell1##__state, l1, i), \
527 : multi_for_advance_cell(cell2, cell1##__state, l2, i), \
528 : multi_for_advance_cell(cell3, cell1##__state, l3, i), \
529 : multi_for_advance_cell(cell4, cell1##__state, l4, i), \
530 : (cell1 != NULL && cell2 != NULL && cell3 != NULL && cell4 != NULL); \
531 : cell1##__state.i++)
532 :
533 : /*
534 : * forfive -
535 : * the same for five lists
536 : */
537 : #define forfive(cell1, list1, cell2, list2, cell3, list3, cell4, list4, cell5, list5) \
538 : for (ForFiveState cell1##__state = {(list1), (list2), (list3), (list4), (list5), 0}; \
539 : multi_for_advance_cell(cell1, cell1##__state, l1, i), \
540 : multi_for_advance_cell(cell2, cell1##__state, l2, i), \
541 : multi_for_advance_cell(cell3, cell1##__state, l3, i), \
542 : multi_for_advance_cell(cell4, cell1##__state, l4, i), \
543 : multi_for_advance_cell(cell5, cell1##__state, l5, i), \
544 : (cell1 != NULL && cell2 != NULL && cell3 != NULL && \
545 : cell4 != NULL && cell5 != NULL); \
546 : cell1##__state.i++)
547 :
548 : /* Functions in src/backend/nodes/list.c */
549 :
550 : extern List *list_make1_impl(NodeTag t, ListCell datum1);
551 : extern List *list_make2_impl(NodeTag t, ListCell datum1, ListCell datum2);
552 : extern List *list_make3_impl(NodeTag t, ListCell datum1, ListCell datum2,
553 : ListCell datum3);
554 : extern List *list_make4_impl(NodeTag t, ListCell datum1, ListCell datum2,
555 : ListCell datum3, ListCell datum4);
556 : extern List *list_make5_impl(NodeTag t, ListCell datum1, ListCell datum2,
557 : ListCell datum3, ListCell datum4,
558 : ListCell datum5);
559 :
560 : extern pg_nodiscard List *lappend(List *list, void *datum);
561 : extern pg_nodiscard List *lappend_int(List *list, int datum);
562 : extern pg_nodiscard List *lappend_oid(List *list, Oid datum);
563 : extern pg_nodiscard List *lappend_xid(List *list, TransactionId datum);
564 :
565 : extern pg_nodiscard List *list_insert_nth(List *list, int pos, void *datum);
566 : extern pg_nodiscard List *list_insert_nth_int(List *list, int pos, int datum);
567 : extern pg_nodiscard List *list_insert_nth_oid(List *list, int pos, Oid datum);
568 :
569 : extern pg_nodiscard List *lcons(void *datum, List *list);
570 : extern pg_nodiscard List *lcons_int(int datum, List *list);
571 : extern pg_nodiscard List *lcons_oid(Oid datum, List *list);
572 :
573 : extern pg_nodiscard List *list_concat(List *list1, const List *list2);
574 : extern pg_nodiscard List *list_concat_copy(const List *list1, const List *list2);
575 :
576 : extern pg_nodiscard List *list_truncate(List *list, int new_size);
577 :
578 : extern bool list_member(const List *list, const void *datum);
579 : extern bool list_member_ptr(const List *list, const void *datum);
580 : extern bool list_member_int(const List *list, int datum);
581 : extern bool list_member_oid(const List *list, Oid datum);
582 : extern bool list_member_xid(const List *list, TransactionId datum);
583 :
584 : extern pg_nodiscard List *list_delete(List *list, void *datum);
585 : extern pg_nodiscard List *list_delete_ptr(List *list, void *datum);
586 : extern pg_nodiscard List *list_delete_int(List *list, int datum);
587 : extern pg_nodiscard List *list_delete_oid(List *list, Oid datum);
588 : extern pg_nodiscard List *list_delete_first(List *list);
589 : extern pg_nodiscard List *list_delete_last(List *list);
590 : extern pg_nodiscard List *list_delete_first_n(List *list, int n);
591 : extern pg_nodiscard List *list_delete_nth_cell(List *list, int n);
592 : extern pg_nodiscard List *list_delete_cell(List *list, ListCell *cell);
593 :
594 : extern List *list_union(const List *list1, const List *list2);
595 : extern List *list_union_ptr(const List *list1, const List *list2);
596 : extern List *list_union_int(const List *list1, const List *list2);
597 : extern List *list_union_oid(const List *list1, const List *list2);
598 :
599 : extern List *list_intersection(const List *list1, const List *list2);
600 : extern List *list_intersection_int(const List *list1, const List *list2);
601 :
602 : /* currently, there's no need for list_intersection_ptr etc */
603 :
604 : extern List *list_difference(const List *list1, const List *list2);
605 : extern List *list_difference_ptr(const List *list1, const List *list2);
606 : extern List *list_difference_int(const List *list1, const List *list2);
607 : extern List *list_difference_oid(const List *list1, const List *list2);
608 :
609 : extern pg_nodiscard List *list_append_unique(List *list, void *datum);
610 : extern pg_nodiscard List *list_append_unique_ptr(List *list, void *datum);
611 : extern pg_nodiscard List *list_append_unique_int(List *list, int datum);
612 : extern pg_nodiscard List *list_append_unique_oid(List *list, Oid datum);
613 :
614 : extern pg_nodiscard List *list_concat_unique(List *list1, const List *list2);
615 : extern pg_nodiscard List *list_concat_unique_ptr(List *list1, const List *list2);
616 : extern pg_nodiscard List *list_concat_unique_int(List *list1, const List *list2);
617 : extern pg_nodiscard List *list_concat_unique_oid(List *list1, const List *list2);
618 :
619 : extern void list_deduplicate_oid(List *list);
620 :
621 : extern void list_free(List *list);
622 : extern void list_free_deep(List *list);
623 :
624 : extern pg_nodiscard List *list_copy(const List *oldlist);
625 : extern pg_nodiscard List *list_copy_head(const List *oldlist, int len);
626 : extern pg_nodiscard List *list_copy_tail(const List *oldlist, int nskip);
627 : extern pg_nodiscard List *list_copy_deep(const List *oldlist);
628 :
629 : typedef int (*list_sort_comparator) (const ListCell *a, const ListCell *b);
630 : extern void list_sort(List *list, list_sort_comparator cmp);
631 :
632 : extern int list_int_cmp(const ListCell *p1, const ListCell *p2);
633 : extern int list_oid_cmp(const ListCell *p1, const ListCell *p2);
634 :
635 : #endif /* PG_LIST_H */
|
