| 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-2025, 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 |
list_head(const List *l) |
| 129 |
{ |
| 130 |
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 |
list_second_cell(const List *l) |
| 143 |
{ |
| 144 |
if (l && l->length >= 2) |
| 145 |
return &l->elements[1]; |
| 146 |
else |
| 147 |
return NULL; |
| 148 |
} |
| 149 |
|
| 150 |
/* Fetch list's length */ |
| 151 |
static inline int |
| 152 |
list_length(const List *l) |
| 153 |
{ |
| 154 |
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 |
list_nth_cell(const List *list, int n) |
| 278 |
{ |
| 279 |
Assert(list != NIL); |
| 280 |
Assert(n >= 0 && n < list->length); |
| 281 |
return &list->elements[n]; |
| 282 |
} |
| 283 |
|
| 284 |
/* |
| 285 |
* Return the last cell in a non-NIL List. |
| 286 |
*/ |
| 287 |
static inline ListCell * |
| 288 |
list_last_cell(const List *list) |
| 289 |
{ |
| 290 |
Assert(list != NIL); |
| 291 |
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 |
list_nth(const List *list, int n) |
| 300 |
{ |
| 301 |
Assert(IsA(list, List)); |
| 302 |
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 |
list_nth_int(const List *list, int n) |
| 311 |
{ |
| 312 |
Assert(IsA(list, IntList)); |
| 313 |
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 |
list_nth_oid(const List *list, int n) |
| 322 |
{ |
| 323 |
Assert(IsA(list, OidList)); |
| 324 |
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 |
list_cell_number(const List *l, const ListCell *c) |
| 334 |
{ |
| 335 |
Assert(c >= &l->elements[0] && c < &l->elements[l->length]); |
| 336 |
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 |
lnext(const List *l, const ListCell *c) |
| 344 |
{ |
| 345 |
Assert(c >= &l->elements[0] && c < &l->elements[l->length]); |
| 346 |
c++; |
| 347 |
if (c < &l->elements[l->length]) |
| 348 |
return (ListCell *) c; |
| 349 |
else |
| 350 |
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() or foreach_*() loop, returning the new List |
| 385 |
* pointer; pass the name of the iterator variable. |
| 386 |
* |
| 387 |
* This is similar to list_delete_cell(), but it also adjusts the loop's state |
| 388 |
* so that no list elements will be missed. Do not delete elements from an |
| 389 |
* active foreach or foreach_* loop's list in any other way! |
| 390 |
*/ |
| 391 |
#define foreach_delete_current(lst, var_or_cell) \ |
| 392 |
((List *) (var_or_cell##__state.l = list_delete_nth_cell(lst, var_or_cell##__state.i--))) |
| 393 |
|
| 394 |
/* |
| 395 |
* foreach_current_index - |
| 396 |
* get the zero-based list index of a surrounding foreach() or foreach_*() |
| 397 |
* loop's current element; pass the name of the 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(var_or_cell) (var_or_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 |
for_each_from_setup(const List *lst, int N) |
| 424 |
{ |
| 425 |
ForEachState r = {lst, N}; |
| 426 |
|
| 427 |
Assert(N >= 0); |
| 428 |
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 |
for_each_cell_setup(const List *lst, const ListCell *initcell) |
| 448 |
{ |
| 449 |
ForEachState r = {lst, |
| 450 |
initcell ? list_cell_number(lst, initcell) : list_length(lst)}; |
| 451 |
|
| 452 |
return r; |
| 453 |
} |
| 454 |
|
| 455 |
/* |
| 456 |
* Convenience macros that loop through a list without needing a separate |
| 457 |
* "ListCell *" variable. Instead, the macros declare a locally-scoped loop |
| 458 |
* variable with the provided name and the appropriate type. |
| 459 |
* |
| 460 |
* Since the variable is scoped to the loop, it's not possible to detect an |
| 461 |
* early break by checking its value after the loop completes, as is common |
| 462 |
* practice. If you need to do this, you can either use foreach() instead or |
| 463 |
* manually track early breaks with a separate variable declared outside of the |
| 464 |
* loop. |
| 465 |
* |
| 466 |
* Note that the caveats described in the comment above the foreach() macro |
| 467 |
* also apply to these convenience macros. |
| 468 |
*/ |
| 469 |
#define foreach_ptr(type, var, lst) foreach_internal(type, *, var, lst, lfirst) |
| 470 |
#define foreach_int(var, lst) foreach_internal(int, , var, lst, lfirst_int) |
| 471 |
#define foreach_oid(var, lst) foreach_internal(Oid, , var, lst, lfirst_oid) |
| 472 |
#define foreach_xid(var, lst) foreach_internal(TransactionId, , var, lst, lfirst_xid) |
| 473 |
|
| 474 |
/* |
| 475 |
* The internal implementation of the above macros. Do not use directly. |
| 476 |
* |
| 477 |
* This macro actually generates two loops in order to declare two variables of |
| 478 |
* different types. The outer loop only iterates once, so we expect optimizing |
| 479 |
* compilers will unroll it, thereby optimizing it away. |
| 480 |
*/ |
| 481 |
#define foreach_internal(type, pointer, var, lst, func) \ |
| 482 |
for (type pointer var = 0, pointer var##__outerloop = (type pointer) 1; \ |
| 483 |
var##__outerloop; \ |
| 484 |
var##__outerloop = 0) \ |
| 485 |
for (ForEachState var##__state = {(lst), 0}; \ |
| 486 |
(var##__state.l != NIL && \ |
| 487 |
var##__state.i < var##__state.l->length && \ |
| 488 |
(var = (type pointer) func(&var##__state.l->elements[var##__state.i]), true)); \ |
| 489 |
var##__state.i++) |
| 490 |
|
| 491 |
/* |
| 492 |
* foreach_node - |
| 493 |
* The same as foreach_ptr, but asserts that the element is of the specified |
| 494 |
* node type. |
| 495 |
*/ |
| 496 |
#define foreach_node(type, var, lst) \ |
| 497 |
for (type * var = 0, *var##__outerloop = (type *) 1; \ |
| 498 |
var##__outerloop; \ |
| 499 |
var##__outerloop = 0) \ |
| 500 |
for (ForEachState var##__state = {(lst), 0}; \ |
| 501 |
(var##__state.l != NIL && \ |
| 502 |
var##__state.i < var##__state.l->length && \ |
| 503 |
(var = lfirst_node(type, &var##__state.l->elements[var##__state.i]), true)); \ |
| 504 |
var##__state.i++) |
| 505 |
|
| 506 |
/* |
| 507 |
* forboth - |
| 508 |
* a convenience macro for advancing through two linked lists |
| 509 |
* simultaneously. This macro loops through both lists at the same |
| 510 |
* time, stopping when either list runs out of elements. Depending |
| 511 |
* on the requirements of the call site, it may also be wise to |
| 512 |
* assert that the lengths of the two lists are equal. (But, if they |
| 513 |
* are not, some callers rely on the ending cell values being separately |
| 514 |
* NULL or non-NULL as defined here; don't try to optimize that.) |
| 515 |
* |
| 516 |
* The caveats for foreach() apply equally here. |
| 517 |
*/ |
| 518 |
#define forboth(cell1, list1, cell2, list2) \ |
| 519 |
for (ForBothState cell1##__state = {(list1), (list2), 0}; \ |
| 520 |
multi_for_advance_cell(cell1, cell1##__state, l1, i), \ |
| 521 |
multi_for_advance_cell(cell2, cell1##__state, l2, i), \ |
| 522 |
(cell1 != NULL && cell2 != NULL); \ |
| 523 |
cell1##__state.i++) |
| 524 |
|
| 525 |
#define multi_for_advance_cell(cell, state, l, i) \ |
| 526 |
(cell = (state.l != NIL && state.i < state.l->length) ? \ |
| 527 |
&state.l->elements[state.i] : NULL) |
| 528 |
|
| 529 |
/* |
| 530 |
* for_both_cell - |
| 531 |
* a convenience macro which loops through two lists starting from the |
| 532 |
* specified cells of each. This macro loops through both lists at the same |
| 533 |
* time, stopping when either list runs out of elements. Depending on the |
| 534 |
* requirements of the call site, it may also be wise to assert that the |
| 535 |
* lengths of the two lists are equal, and initcell1 and initcell2 are at |
| 536 |
* the same position in the respective lists. |
| 537 |
* |
| 538 |
* The caveats for foreach() apply equally here. |
| 539 |
*/ |
| 540 |
#define for_both_cell(cell1, list1, initcell1, cell2, list2, initcell2) \ |
| 541 |
for (ForBothCellState cell1##__state = \ |
| 542 |
for_both_cell_setup(list1, initcell1, list2, initcell2); \ |
| 543 |
multi_for_advance_cell(cell1, cell1##__state, l1, i1), \ |
| 544 |
multi_for_advance_cell(cell2, cell1##__state, l2, i2), \ |
| 545 |
(cell1 != NULL && cell2 != NULL); \ |
| 546 |
cell1##__state.i1++, cell1##__state.i2++) |
| 547 |
|
| 548 |
static inline ForBothCellState |
| 549 |
for_both_cell_setup(const List *list1, const ListCell *initcell1, |
| 550 |
const List *list2, const ListCell *initcell2) |
| 551 |
{ |
| 552 |
ForBothCellState r = {list1, list2, |
| 553 |
initcell1 ? list_cell_number(list1, initcell1) : list_length(list1), |
| 554 |
initcell2 ? list_cell_number(list2, initcell2) : list_length(list2)}; |
| 555 |
|
| 556 |
return r; |
| 557 |
} |
| 558 |
|
| 559 |
/* |
| 560 |
* forthree - |
| 561 |
* the same for three lists |
| 562 |
*/ |
| 563 |
#define forthree(cell1, list1, cell2, list2, cell3, list3) \ |
| 564 |
for (ForThreeState cell1##__state = {(list1), (list2), (list3), 0}; \ |
| 565 |
multi_for_advance_cell(cell1, cell1##__state, l1, i), \ |
| 566 |
multi_for_advance_cell(cell2, cell1##__state, l2, i), \ |
| 567 |
multi_for_advance_cell(cell3, cell1##__state, l3, i), \ |
| 568 |
(cell1 != NULL && cell2 != NULL && cell3 != NULL); \ |
| 569 |
cell1##__state.i++) |
| 570 |
|
| 571 |
/* |
| 572 |
* forfour - |
| 573 |
* the same for four lists |
| 574 |
*/ |
| 575 |
#define forfour(cell1, list1, cell2, list2, cell3, list3, cell4, list4) \ |
| 576 |
for (ForFourState cell1##__state = {(list1), (list2), (list3), (list4), 0}; \ |
| 577 |
multi_for_advance_cell(cell1, cell1##__state, l1, i), \ |
| 578 |
multi_for_advance_cell(cell2, cell1##__state, l2, i), \ |
| 579 |
multi_for_advance_cell(cell3, cell1##__state, l3, i), \ |
| 580 |
multi_for_advance_cell(cell4, cell1##__state, l4, i), \ |
| 581 |
(cell1 != NULL && cell2 != NULL && cell3 != NULL && cell4 != NULL); \ |
| 582 |
cell1##__state.i++) |
| 583 |
|
| 584 |
/* |
| 585 |
* forfive - |
| 586 |
* the same for five lists |
| 587 |
*/ |
| 588 |
#define forfive(cell1, list1, cell2, list2, cell3, list3, cell4, list4, cell5, list5) \ |
| 589 |
for (ForFiveState cell1##__state = {(list1), (list2), (list3), (list4), (list5), 0}; \ |
| 590 |
multi_for_advance_cell(cell1, cell1##__state, l1, i), \ |
| 591 |
multi_for_advance_cell(cell2, cell1##__state, l2, i), \ |
| 592 |
multi_for_advance_cell(cell3, cell1##__state, l3, i), \ |
| 593 |
multi_for_advance_cell(cell4, cell1##__state, l4, i), \ |
| 594 |
multi_for_advance_cell(cell5, cell1##__state, l5, i), \ |
| 595 |
(cell1 != NULL && cell2 != NULL && cell3 != NULL && \ |
| 596 |
cell4 != NULL && cell5 != NULL); \ |
| 597 |
cell1##__state.i++) |
| 598 |
|
| 599 |
/* Functions in src/backend/nodes/list.c */ |
| 600 |
|
| 601 |
extern List *list_make1_impl(NodeTag t, ListCell datum1); |
| 602 |
extern List *list_make2_impl(NodeTag t, ListCell datum1, ListCell datum2); |
| 603 |
extern List *list_make3_impl(NodeTag t, ListCell datum1, ListCell datum2, |
| 604 |
ListCell datum3); |
| 605 |
extern List *list_make4_impl(NodeTag t, ListCell datum1, ListCell datum2, |
| 606 |
ListCell datum3, ListCell datum4); |
| 607 |
extern List *list_make5_impl(NodeTag t, ListCell datum1, ListCell datum2, |
| 608 |
ListCell datum3, ListCell datum4, |
| 609 |
ListCell datum5); |
| 610 |
|
| 611 |
pg_nodiscard extern List *lappend(List *list, void *datum); |
| 612 |
pg_nodiscard extern List *lappend_int(List *list, int datum); |
| 613 |
pg_nodiscard extern List *lappend_oid(List *list, Oid datum); |
| 614 |
pg_nodiscard extern List *lappend_xid(List *list, TransactionId datum); |
| 615 |
|
| 616 |
pg_nodiscard extern List *list_insert_nth(List *list, int pos, void *datum); |
| 617 |
pg_nodiscard extern List *list_insert_nth_int(List *list, int pos, int datum); |
| 618 |
pg_nodiscard extern List *list_insert_nth_oid(List *list, int pos, Oid datum); |
| 619 |
|
| 620 |
pg_nodiscard extern List *lcons(void *datum, List *list); |
| 621 |
pg_nodiscard extern List *lcons_int(int datum, List *list); |
| 622 |
pg_nodiscard extern List *lcons_oid(Oid datum, List *list); |
| 623 |
|
| 624 |
pg_nodiscard extern List *list_concat(List *list1, const List *list2); |
| 625 |
pg_nodiscard extern List *list_concat_copy(const List *list1, const List *list2); |
| 626 |
|
| 627 |
pg_nodiscard extern List *list_truncate(List *list, int new_size); |
| 628 |
|
| 629 |
extern bool list_member(const List *list, const void *datum); |
| 630 |
extern bool list_member_ptr(const List *list, const void *datum); |
| 631 |
extern bool list_member_int(const List *list, int datum); |
| 632 |
extern bool list_member_oid(const List *list, Oid datum); |
| 633 |
extern bool list_member_xid(const List *list, TransactionId datum); |
| 634 |
|
| 635 |
pg_nodiscard extern List *list_delete(List *list, void *datum); |
| 636 |
pg_nodiscard extern List *list_delete_ptr(List *list, void *datum); |
| 637 |
pg_nodiscard extern List *list_delete_int(List *list, int datum); |
| 638 |
pg_nodiscard extern List *list_delete_oid(List *list, Oid datum); |
| 639 |
pg_nodiscard extern List *list_delete_first(List *list); |
| 640 |
pg_nodiscard extern List *list_delete_last(List *list); |
| 641 |
pg_nodiscard extern List *list_delete_first_n(List *list, int n); |
| 642 |
pg_nodiscard extern List *list_delete_nth_cell(List *list, int n); |
| 643 |
pg_nodiscard extern List *list_delete_cell(List *list, ListCell *cell); |
| 644 |
|
| 645 |
extern List *list_union(const List *list1, const List *list2); |
| 646 |
extern List *list_union_ptr(const List *list1, const List *list2); |
| 647 |
extern List *list_union_int(const List *list1, const List *list2); |
| 648 |
extern List *list_union_oid(const List *list1, const List *list2); |
| 649 |
|
| 650 |
extern List *list_intersection(const List *list1, const List *list2); |
| 651 |
extern List *list_intersection_int(const List *list1, const List *list2); |
| 652 |
|
| 653 |
/* currently, there's no need for list_intersection_ptr etc */ |
| 654 |
|
| 655 |
extern List *list_difference(const List *list1, const List *list2); |
| 656 |
extern List *list_difference_ptr(const List *list1, const List *list2); |
| 657 |
extern List *list_difference_int(const List *list1, const List *list2); |
| 658 |
extern List *list_difference_oid(const List *list1, const List *list2); |
| 659 |
|
| 660 |
pg_nodiscard extern List *list_append_unique(List *list, void *datum); |
| 661 |
pg_nodiscard extern List *list_append_unique_ptr(List *list, void *datum); |
| 662 |
pg_nodiscard extern List *list_append_unique_int(List *list, int datum); |
| 663 |
pg_nodiscard extern List *list_append_unique_oid(List *list, Oid datum); |
| 664 |
|
| 665 |
pg_nodiscard extern List *list_concat_unique(List *list1, const List *list2); |
| 666 |
pg_nodiscard extern List *list_concat_unique_ptr(List *list1, const List *list2); |
| 667 |
pg_nodiscard extern List *list_concat_unique_int(List *list1, const List *list2); |
| 668 |
pg_nodiscard extern List *list_concat_unique_oid(List *list1, const List *list2); |
| 669 |
|
| 670 |
extern void list_deduplicate_oid(List *list); |
| 671 |
|
| 672 |
extern void list_free(List *list); |
| 673 |
extern void list_free_deep(List *list); |
| 674 |
|
| 675 |
pg_nodiscard extern List *list_copy(const List *oldlist); |
| 676 |
pg_nodiscard extern List *list_copy_head(const List *oldlist, int len); |
| 677 |
pg_nodiscard extern List *list_copy_tail(const List *oldlist, int nskip); |
| 678 |
pg_nodiscard extern List *list_copy_deep(const List *oldlist); |
| 679 |
|
| 680 |
typedef int (*list_sort_comparator) (const ListCell *a, const ListCell *b); |
| 681 |
extern void list_sort(List *list, list_sort_comparator cmp); |
| 682 |
|
| 683 |
extern int list_int_cmp(const ListCell *p1, const ListCell *p2); |
| 684 |
extern int list_oid_cmp(const ListCell *p1, const ListCell *p2); |
| 685 |
|
| 686 |
#endif /* PG_LIST_H */ |