| 1 |
/*------------------------------------------------------------------------- |
| 2 |
* |
| 3 |
* list.c |
| 4 |
* implementation for PostgreSQL generic list package |
| 5 |
* |
| 6 |
* See comments in pg_list.h. |
| 7 |
* |
| 8 |
* |
| 9 |
* Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group |
| 10 |
* Portions Copyright (c) 1994, Regents of the University of California |
| 11 |
* |
| 12 |
* |
| 13 |
* IDENTIFICATION |
| 14 |
* src/backend/nodes/list.c |
| 15 |
* |
| 16 |
*------------------------------------------------------------------------- |
| 17 |
*/ |
| 18 |
#include "postgres.h" |
| 19 |
|
| 20 |
#include "common/int.h" |
| 21 |
#include "nodes/pg_list.h" |
| 22 |
#include "port/pg_bitutils.h" |
| 23 |
#include "utils/memdebug.h" |
| 24 |
#include "utils/memutils.h" |
| 25 |
|
| 26 |
|
| 27 |
/* |
| 28 |
* The previous List implementation, since it used a separate palloc chunk |
| 29 |
* for each cons cell, had the property that adding or deleting list cells |
| 30 |
* did not move the storage of other existing cells in the list. Quite a |
| 31 |
* bit of existing code depended on that, by retaining ListCell pointers |
| 32 |
* across such operations on a list. There is no such guarantee in this |
| 33 |
* implementation, so instead we have debugging support that is meant to |
| 34 |
* help flush out now-broken assumptions. Defining DEBUG_LIST_MEMORY_USAGE |
| 35 |
* while building this file causes the List operations to forcibly move |
| 36 |
* all cells in a list whenever a cell is added or deleted. In combination |
| 37 |
* with MEMORY_CONTEXT_CHECKING and/or Valgrind, this can usually expose |
| 38 |
* broken code. It's a bit expensive though, as there's many more palloc |
| 39 |
* cycles and a lot more data-copying than in a default build. |
| 40 |
* |
| 41 |
* By default, we enable this when building for Valgrind. |
| 42 |
*/ |
| 43 |
#ifdef USE_VALGRIND |
| 44 |
#define DEBUG_LIST_MEMORY_USAGE |
| 45 |
#endif |
| 46 |
|
| 47 |
/* Overhead for the fixed part of a List header, measured in ListCells */ |
| 48 |
#define LIST_HEADER_OVERHEAD \ |
| 49 |
((int) ((offsetof(List, initial_elements) - 1) / sizeof(ListCell) + 1)) |
| 50 |
|
| 51 |
/* |
| 52 |
* Macros to simplify writing assertions about the type of a list; a |
| 53 |
* NIL list is considered to be an empty list of any type. |
| 54 |
*/ |
| 55 |
#define IsPointerList(l) ((l) == NIL || IsA((l), List)) |
| 56 |
#define IsIntegerList(l) ((l) == NIL || IsA((l), IntList)) |
| 57 |
#define IsOidList(l) ((l) == NIL || IsA((l), OidList)) |
| 58 |
#define IsXidList(l) ((l) == NIL || IsA((l), XidList)) |
| 59 |
|
| 60 |
#ifdef USE_ASSERT_CHECKING |
| 61 |
/* |
| 62 |
* Check that the specified List is valid (so far as we can tell). |
| 63 |
*/ |
| 64 |
static void |
| 65 |
check_list_invariants(const List *list) |
| 66 |
{ |
| 67 |
if (list == NIL) |
| 68 |
return; |
| 69 |
|
| 70 |
Assert(list->length > 0); |
| 71 |
Assert(list->length <= list->max_length); |
| 72 |
Assert(list->elements != NULL); |
| 73 |
|
| 74 |
Assert(list->type == T_List || |
| 75 |
list->type == T_IntList || |
| 76 |
list->type == T_OidList || |
| 77 |
list->type == T_XidList); |
| 78 |
} |
| 79 |
#else |
| 80 |
#define check_list_invariants(l) ((void) 0) |
| 81 |
#endif /* USE_ASSERT_CHECKING */ |
| 82 |
|
| 83 |
/* |
| 84 |
* Return a freshly allocated List with room for at least min_size cells. |
| 85 |
* |
| 86 |
* Since empty non-NIL lists are invalid, new_list() sets the initial length |
| 87 |
* to min_size, effectively marking that number of cells as valid; the caller |
| 88 |
* is responsible for filling in their data. |
| 89 |
*/ |
| 90 |
static List * |
| 91 |
new_list(NodeTag type, int min_size) |
| 92 |
{ |
| 93 |
List *newlist; |
| 94 |
int max_size; |
| 95 |
|
| 96 |
Assert(min_size > 0); |
| 97 |
|
| 98 |
/* |
| 99 |
* We allocate all the requested cells, and possibly some more, as part of |
| 100 |
* the same palloc request as the List header. This is a big win for the |
| 101 |
* typical case of short fixed-length lists. It can lose if we allocate a |
| 102 |
* moderately long list and then it gets extended; we'll be wasting more |
| 103 |
* initial_elements[] space than if we'd made the header small. However, |
| 104 |
* rounding up the request as we do in the normal code path provides some |
| 105 |
* defense against small extensions. |
| 106 |
*/ |
| 107 |
|
| 108 |
#ifndef DEBUG_LIST_MEMORY_USAGE |
| 109 |
|
| 110 |
/* |
| 111 |
* Normally, we set up a list with some extra cells, to allow it to grow |
| 112 |
* without a repalloc. Prefer cell counts chosen to make the total |
| 113 |
* allocation a power-of-2, since palloc would round it up to that anyway. |
| 114 |
* (That stops being true for very large allocations, but very long lists |
| 115 |
* are infrequent, so it doesn't seem worth special logic for such cases.) |
| 116 |
* |
| 117 |
* The minimum allocation is 8 ListCell units, providing either 4 or 5 |
| 118 |
* available ListCells depending on the machine's word width. Counting |
| 119 |
* palloc's overhead, this uses the same amount of space as a one-cell |
| 120 |
* list did in the old implementation, and less space for any longer list. |
| 121 |
* |
| 122 |
* We needn't worry about integer overflow; no caller passes min_size |
| 123 |
* that's more than twice the size of an existing list, so the size limits |
| 124 |
* within palloc will ensure that we don't overflow here. |
| 125 |
*/ |
| 126 |
max_size = pg_nextpower2_32(Max(8, min_size + LIST_HEADER_OVERHEAD)); |
| 127 |
max_size -= LIST_HEADER_OVERHEAD; |
| 128 |
#else |
| 129 |
|
| 130 |
/* |
| 131 |
* For debugging, don't allow any extra space. This forces any cell |
| 132 |
* addition to go through enlarge_list() and thus move the existing data. |
| 133 |
*/ |
| 134 |
max_size = min_size; |
| 135 |
#endif |
| 136 |
|
| 137 |
newlist = (List *) palloc(offsetof(List, initial_elements) + |
| 138 |
max_size * sizeof(ListCell)); |
| 139 |
newlist->type = type; |
| 140 |
newlist->length = min_size; |
| 141 |
newlist->max_length = max_size; |
| 142 |
newlist->elements = newlist->initial_elements; |
| 143 |
|
| 144 |
return newlist; |
| 145 |
} |
| 146 |
|
| 147 |
/* |
| 148 |
* Enlarge an existing non-NIL List to have room for at least min_size cells. |
| 149 |
* |
| 150 |
* This does *not* update list->length, as some callers would find that |
| 151 |
* inconvenient. (list->length had better be the correct number of existing |
| 152 |
* valid cells, though.) |
| 153 |
*/ |
| 154 |
static void |
| 155 |
enlarge_list(List *list, int min_size) |
| 156 |
{ |
| 157 |
int new_max_len; |
| 158 |
|
| 159 |
Assert(min_size > list->max_length); /* else we shouldn't be here */ |
| 160 |
|
| 161 |
#ifndef DEBUG_LIST_MEMORY_USAGE |
| 162 |
|
| 163 |
/* |
| 164 |
* As above, we prefer power-of-two total allocations; but here we need |
| 165 |
* not account for list header overhead. |
| 166 |
*/ |
| 167 |
|
| 168 |
/* clamp the minimum value to 16, a semi-arbitrary small power of 2 */ |
| 169 |
new_max_len = pg_nextpower2_32(Max(16, min_size)); |
| 170 |
|
| 171 |
#else |
| 172 |
/* As above, don't allocate anything extra */ |
| 173 |
new_max_len = min_size; |
| 174 |
#endif |
| 175 |
|
| 176 |
if (list->elements == list->initial_elements) |
| 177 |
{ |
| 178 |
/* |
| 179 |
* Replace original in-line allocation with a separate palloc block. |
| 180 |
* Ensure it is in the same memory context as the List header. (The |
| 181 |
* previous List implementation did not offer any guarantees about |
| 182 |
* keeping all list cells in the same context, but it seems reasonable |
| 183 |
* to create such a guarantee now.) |
| 184 |
*/ |
| 185 |
list->elements = (ListCell *) |
| 186 |
MemoryContextAlloc(GetMemoryChunkContext(list), |
| 187 |
new_max_len * sizeof(ListCell)); |
| 188 |
memcpy(list->elements, list->initial_elements, |
| 189 |
list->length * sizeof(ListCell)); |
| 190 |
|
| 191 |
/* |
| 192 |
* We must not move the list header, so it's unsafe to try to reclaim |
| 193 |
* the initial_elements[] space via repalloc. In debugging builds, |
| 194 |
* however, we can clear that space and/or mark it inaccessible. |
| 195 |
* (wipe_mem includes VALGRIND_MAKE_MEM_NOACCESS.) |
| 196 |
*/ |
| 197 |
#ifdef CLOBBER_FREED_MEMORY |
| 198 |
wipe_mem(list->initial_elements, |
| 199 |
list->max_length * sizeof(ListCell)); |
| 200 |
#else |
| 201 |
VALGRIND_MAKE_MEM_NOACCESS(list->initial_elements, |
| 202 |
list->max_length * sizeof(ListCell)); |
| 203 |
#endif |
| 204 |
} |
| 205 |
else |
| 206 |
{ |
| 207 |
#ifndef DEBUG_LIST_MEMORY_USAGE |
| 208 |
/* Normally, let repalloc deal with enlargement */ |
| 209 |
list->elements = (ListCell *) repalloc(list->elements, |
| 210 |
new_max_len * sizeof(ListCell)); |
| 211 |
#else |
| 212 |
/* |
| 213 |
* repalloc() might enlarge the space in-place, which we don't want |
| 214 |
* for debugging purposes, so forcibly move the data somewhere else. |
| 215 |
*/ |
| 216 |
ListCell *newelements; |
| 217 |
|
| 218 |
newelements = (ListCell *) |
| 219 |
MemoryContextAlloc(GetMemoryChunkContext(list), |
| 220 |
new_max_len * sizeof(ListCell)); |
| 221 |
memcpy(newelements, list->elements, |
| 222 |
list->length * sizeof(ListCell)); |
| 223 |
pfree(list->elements); |
| 224 |
list->elements = newelements; |
| 225 |
#endif |
| 226 |
} |
| 227 |
|
| 228 |
list->max_length = new_max_len; |
| 229 |
} |
| 230 |
|
| 231 |
/* |
| 232 |
* Convenience functions to construct short Lists from given values. |
| 233 |
* (These are normally invoked via the list_makeN macros.) |
| 234 |
*/ |
| 235 |
List * |
| 236 |
list_make1_impl(NodeTag t, ListCell datum1) |
| 237 |
{ |
| 238 |
List *list = new_list(t, 1); |
| 239 |
|
| 240 |
list->elements[0] = datum1; |
| 241 |
check_list_invariants(list); |
| 242 |
return list; |
| 243 |
} |
| 244 |
|
| 245 |
List * |
| 246 |
list_make2_impl(NodeTag t, ListCell datum1, ListCell datum2) |
| 247 |
{ |
| 248 |
List *list = new_list(t, 2); |
| 249 |
|
| 250 |
list->elements[0] = datum1; |
| 251 |
list->elements[1] = datum2; |
| 252 |
check_list_invariants(list); |
| 253 |
return list; |
| 254 |
} |
| 255 |
|
| 256 |
List * |
| 257 |
list_make3_impl(NodeTag t, ListCell datum1, ListCell datum2, |
| 258 |
ListCell datum3) |
| 259 |
{ |
| 260 |
List *list = new_list(t, 3); |
| 261 |
|
| 262 |
list->elements[0] = datum1; |
| 263 |
list->elements[1] = datum2; |
| 264 |
list->elements[2] = datum3; |
| 265 |
check_list_invariants(list); |
| 266 |
return list; |
| 267 |
} |
| 268 |
|
| 269 |
List * |
| 270 |
list_make4_impl(NodeTag t, ListCell datum1, ListCell datum2, |
| 271 |
ListCell datum3, ListCell datum4) |
| 272 |
{ |
| 273 |
List *list = new_list(t, 4); |
| 274 |
|
| 275 |
list->elements[0] = datum1; |
| 276 |
list->elements[1] = datum2; |
| 277 |
list->elements[2] = datum3; |
| 278 |
list->elements[3] = datum4; |
| 279 |
check_list_invariants(list); |
| 280 |
return list; |
| 281 |
} |
| 282 |
|
| 283 |
List * |
| 284 |
list_make5_impl(NodeTag t, ListCell datum1, ListCell datum2, |
| 285 |
ListCell datum3, ListCell datum4, ListCell datum5) |
| 286 |
{ |
| 287 |
List *list = new_list(t, 5); |
| 288 |
|
| 289 |
list->elements[0] = datum1; |
| 290 |
list->elements[1] = datum2; |
| 291 |
list->elements[2] = datum3; |
| 292 |
list->elements[3] = datum4; |
| 293 |
list->elements[4] = datum5; |
| 294 |
check_list_invariants(list); |
| 295 |
return list; |
| 296 |
} |
| 297 |
|
| 298 |
/* |
| 299 |
* Make room for a new head cell in the given (non-NIL) list. |
| 300 |
* |
| 301 |
* The data in the new head cell is undefined; the caller should be |
| 302 |
* sure to fill it in |
| 303 |
*/ |
| 304 |
static void |
| 305 |
new_head_cell(List *list) |
| 306 |
{ |
| 307 |
/* Enlarge array if necessary */ |
| 308 |
if (list->length >= list->max_length) |
| 309 |
enlarge_list(list, list->length + 1); |
| 310 |
/* Now shove the existing data over */ |
| 311 |
memmove(&list->elements[1], &list->elements[0], |
| 312 |
list->length * sizeof(ListCell)); |
| 313 |
list->length++; |
| 314 |
} |
| 315 |
|
| 316 |
/* |
| 317 |
* Make room for a new tail cell in the given (non-NIL) list. |
| 318 |
* |
| 319 |
* The data in the new tail cell is undefined; the caller should be |
| 320 |
* sure to fill it in |
| 321 |
*/ |
| 322 |
static void |
| 323 |
new_tail_cell(List *list) |
| 324 |
{ |
| 325 |
/* Enlarge array if necessary */ |
| 326 |
if (list->length >= list->max_length) |
| 327 |
enlarge_list(list, list->length + 1); |
| 328 |
list->length++; |
| 329 |
} |
| 330 |
|
| 331 |
/* |
| 332 |
* Append a pointer to the list. A pointer to the modified list is |
| 333 |
* returned. Note that this function may or may not destructively |
| 334 |
* modify the list; callers should always use this function's return |
| 335 |
* value, rather than continuing to use the pointer passed as the |
| 336 |
* first argument. |
| 337 |
*/ |
| 338 |
List * |
| 339 |
lappend(List *list, void *datum) |
| 340 |
{ |
| 341 |
Assert(IsPointerList(list)); |
| 342 |
|
| 343 |
if (list == NIL) |
| 344 |
list = new_list(T_List, 1); |
| 345 |
else |
| 346 |
new_tail_cell(list); |
| 347 |
|
| 348 |
llast(list) = datum; |
| 349 |
check_list_invariants(list); |
| 350 |
return list; |
| 351 |
} |
| 352 |
|
| 353 |
/* |
| 354 |
* Append an integer to the specified list. See lappend() |
| 355 |
*/ |
| 356 |
List * |
| 357 |
lappend_int(List *list, int datum) |
| 358 |
{ |
| 359 |
Assert(IsIntegerList(list)); |
| 360 |
|
| 361 |
if (list == NIL) |
| 362 |
list = new_list(T_IntList, 1); |
| 363 |
else |
| 364 |
new_tail_cell(list); |
| 365 |
|
| 366 |
llast_int(list) = datum; |
| 367 |
check_list_invariants(list); |
| 368 |
return list; |
| 369 |
} |
| 370 |
|
| 371 |
/* |
| 372 |
* Append an OID to the specified list. See lappend() |
| 373 |
*/ |
| 374 |
List * |
| 375 |
lappend_oid(List *list, Oid datum) |
| 376 |
{ |
| 377 |
Assert(IsOidList(list)); |
| 378 |
|
| 379 |
if (list == NIL) |
| 380 |
list = new_list(T_OidList, 1); |
| 381 |
else |
| 382 |
new_tail_cell(list); |
| 383 |
|
| 384 |
llast_oid(list) = datum; |
| 385 |
check_list_invariants(list); |
| 386 |
return list; |
| 387 |
} |
| 388 |
|
| 389 |
/* |
| 390 |
* Append a TransactionId to the specified list. See lappend() |
| 391 |
*/ |
| 392 |
List * |
| 393 |
lappend_xid(List *list, TransactionId datum) |
| 394 |
{ |
| 395 |
Assert(IsXidList(list)); |
| 396 |
|
| 397 |
if (list == NIL) |
| 398 |
list = new_list(T_XidList, 1); |
| 399 |
else |
| 400 |
new_tail_cell(list); |
| 401 |
|
| 402 |
llast_xid(list) = datum; |
| 403 |
check_list_invariants(list); |
| 404 |
return list; |
| 405 |
} |
| 406 |
|
| 407 |
/* |
| 408 |
* Make room for a new cell at position 'pos' (measured from 0). |
| 409 |
* The data in the cell is left undefined, and must be filled in by the |
| 410 |
* caller. 'list' is assumed to be non-NIL, and 'pos' must be a valid |
| 411 |
* list position, ie, 0 <= pos <= list's length. |
| 412 |
* Returns address of the new cell. |
| 413 |
*/ |
| 414 |
static ListCell * |
| 415 |
insert_new_cell(List *list, int pos) |
| 416 |
{ |
| 417 |
Assert(pos >= 0 && pos <= list->length); |
| 418 |
|
| 419 |
/* Enlarge array if necessary */ |
| 420 |
if (list->length >= list->max_length) |
| 421 |
enlarge_list(list, list->length + 1); |
| 422 |
/* Now shove the existing data over */ |
| 423 |
if (pos < list->length) |
| 424 |
memmove(&list->elements[pos + 1], &list->elements[pos], |
| 425 |
(list->length - pos) * sizeof(ListCell)); |
| 426 |
list->length++; |
| 427 |
|
| 428 |
return &list->elements[pos]; |
| 429 |
} |
| 430 |
|
| 431 |
/* |
| 432 |
* Insert the given datum at position 'pos' (measured from 0) in the list. |
| 433 |
* 'pos' must be valid, ie, 0 <= pos <= list's length. |
| 434 |
* |
| 435 |
* Note that this takes time proportional to the distance to the end of the |
| 436 |
* list, since the following entries must be moved. |
| 437 |
*/ |
| 438 |
List * |
| 439 |
list_insert_nth(List *list, int pos, void *datum) |
| 440 |
{ |
| 441 |
if (list == NIL) |
| 442 |
{ |
| 443 |
Assert(pos == 0); |
| 444 |
return list_make1(datum); |
| 445 |
} |
| 446 |
Assert(IsPointerList(list)); |
| 447 |
lfirst(insert_new_cell(list, pos)) = datum; |
| 448 |
check_list_invariants(list); |
| 449 |
return list; |
| 450 |
} |
| 451 |
|
| 452 |
List * |
| 453 |
list_insert_nth_int(List *list, int pos, int datum) |
| 454 |
{ |
| 455 |
if (list == NIL) |
| 456 |
{ |
| 457 |
Assert(pos == 0); |
| 458 |
return list_make1_int(datum); |
| 459 |
} |
| 460 |
Assert(IsIntegerList(list)); |
| 461 |
lfirst_int(insert_new_cell(list, pos)) = datum; |
| 462 |
check_list_invariants(list); |
| 463 |
return list; |
| 464 |
} |
| 465 |
|
| 466 |
List * |
| 467 |
list_insert_nth_oid(List *list, int pos, Oid datum) |
| 468 |
{ |
| 469 |
if (list == NIL) |
| 470 |
{ |
| 471 |
Assert(pos == 0); |
| 472 |
return list_make1_oid(datum); |
| 473 |
} |
| 474 |
Assert(IsOidList(list)); |
| 475 |
lfirst_oid(insert_new_cell(list, pos)) = datum; |
| 476 |
check_list_invariants(list); |
| 477 |
return list; |
| 478 |
} |
| 479 |
|
| 480 |
/* |
| 481 |
* Prepend a new element to the list. A pointer to the modified list |
| 482 |
* is returned. Note that this function may or may not destructively |
| 483 |
* modify the list; callers should always use this function's return |
| 484 |
* value, rather than continuing to use the pointer passed as the |
| 485 |
* second argument. |
| 486 |
* |
| 487 |
* Note that this takes time proportional to the length of the list, |
| 488 |
* since the existing entries must be moved. |
| 489 |
* |
| 490 |
* Caution: before Postgres 8.0, the original List was unmodified and |
| 491 |
* could be considered to retain its separate identity. This is no longer |
| 492 |
* the case. |
| 493 |
*/ |
| 494 |
List * |
| 495 |
lcons(void *datum, List *list) |
| 496 |
{ |
| 497 |
Assert(IsPointerList(list)); |
| 498 |
|
| 499 |
if (list == NIL) |
| 500 |
list = new_list(T_List, 1); |
| 501 |
else |
| 502 |
new_head_cell(list); |
| 503 |
|
| 504 |
linitial(list) = datum; |
| 505 |
check_list_invariants(list); |
| 506 |
return list; |
| 507 |
} |
| 508 |
|
| 509 |
/* |
| 510 |
* Prepend an integer to the list. See lcons() |
| 511 |
*/ |
| 512 |
List * |
| 513 |
lcons_int(int datum, List *list) |
| 514 |
{ |
| 515 |
Assert(IsIntegerList(list)); |
| 516 |
|
| 517 |
if (list == NIL) |
| 518 |
list = new_list(T_IntList, 1); |
| 519 |
else |
| 520 |
new_head_cell(list); |
| 521 |
|
| 522 |
linitial_int(list) = datum; |
| 523 |
check_list_invariants(list); |
| 524 |
return list; |
| 525 |
} |
| 526 |
|
| 527 |
/* |
| 528 |
* Prepend an OID to the list. See lcons() |
| 529 |
*/ |
| 530 |
List * |
| 531 |
lcons_oid(Oid datum, List *list) |
| 532 |
{ |
| 533 |
Assert(IsOidList(list)); |
| 534 |
|
| 535 |
if (list == NIL) |
| 536 |
list = new_list(T_OidList, 1); |
| 537 |
else |
| 538 |
new_head_cell(list); |
| 539 |
|
| 540 |
linitial_oid(list) = datum; |
| 541 |
check_list_invariants(list); |
| 542 |
return list; |
| 543 |
} |
| 544 |
|
| 545 |
/* |
| 546 |
* Concatenate list2 to the end of list1, and return list1. |
| 547 |
* |
| 548 |
* This is equivalent to lappend'ing each element of list2, in order, to list1. |
| 549 |
* list1 is destructively changed, list2 is not. (However, in the case of |
| 550 |
* pointer lists, list1 and list2 will point to the same structures.) |
| 551 |
* |
| 552 |
* Callers should be sure to use the return value as the new pointer to the |
| 553 |
* concatenated list: the 'list1' input pointer may or may not be the same |
| 554 |
* as the returned pointer. |
| 555 |
* |
| 556 |
* Note that this takes at least time proportional to the length of list2. |
| 557 |
* It'd typically be the case that we have to enlarge list1's storage, |
| 558 |
* probably adding time proportional to the length of list1. |
| 559 |
*/ |
| 560 |
List * |
| 561 |
list_concat(List *list1, const List *list2) |
| 562 |
{ |
| 563 |
int new_len; |
| 564 |
|
| 565 |
if (list1 == NIL) |
| 566 |
return list_copy(list2); |
| 567 |
if (list2 == NIL) |
| 568 |
return list1; |
| 569 |
|
| 570 |
Assert(list1->type == list2->type); |
| 571 |
|
| 572 |
new_len = list1->length + list2->length; |
| 573 |
/* Enlarge array if necessary */ |
| 574 |
if (new_len > list1->max_length) |
| 575 |
enlarge_list(list1, new_len); |
| 576 |
|
| 577 |
/* Even if list1 == list2, using memcpy should be safe here */ |
| 578 |
memcpy(&list1->elements[list1->length], &list2->elements[0], |
| 579 |
list2->length * sizeof(ListCell)); |
| 580 |
list1->length = new_len; |
| 581 |
|
| 582 |
check_list_invariants(list1); |
| 583 |
return list1; |
| 584 |
} |
| 585 |
|
| 586 |
/* |
| 587 |
* Form a new list by concatenating the elements of list1 and list2. |
| 588 |
* |
| 589 |
* Neither input list is modified. (However, if they are pointer lists, |
| 590 |
* the output list will point to the same structures.) |
| 591 |
* |
| 592 |
* This is equivalent to, but more efficient than, |
| 593 |
* list_concat(list_copy(list1), list2). |
| 594 |
* Note that some pre-v13 code might list_copy list2 as well, but that's |
| 595 |
* pointless now. |
| 596 |
*/ |
| 597 |
List * |
| 598 |
list_concat_copy(const List *list1, const List *list2) |
| 599 |
{ |
| 600 |
List *result; |
| 601 |
int new_len; |
| 602 |
|
| 603 |
if (list1 == NIL) |
| 604 |
return list_copy(list2); |
| 605 |
if (list2 == NIL) |
| 606 |
return list_copy(list1); |
| 607 |
|
| 608 |
Assert(list1->type == list2->type); |
| 609 |
|
| 610 |
new_len = list1->length + list2->length; |
| 611 |
result = new_list(list1->type, new_len); |
| 612 |
memcpy(result->elements, list1->elements, |
| 613 |
list1->length * sizeof(ListCell)); |
| 614 |
memcpy(result->elements + list1->length, list2->elements, |
| 615 |
list2->length * sizeof(ListCell)); |
| 616 |
|
| 617 |
check_list_invariants(result); |
| 618 |
return result; |
| 619 |
} |
| 620 |
|
| 621 |
/* |
| 622 |
* Truncate 'list' to contain no more than 'new_size' elements. This |
| 623 |
* modifies the list in-place! Despite this, callers should use the |
| 624 |
* pointer returned by this function to refer to the newly truncated |
| 625 |
* list -- it may or may not be the same as the pointer that was |
| 626 |
* passed. |
| 627 |
* |
| 628 |
* Note that any cells removed by list_truncate() are NOT pfree'd. |
| 629 |
*/ |
| 630 |
List * |
| 631 |
list_truncate(List *list, int new_size) |
| 632 |
{ |
| 633 |
if (new_size <= 0) |
| 634 |
return NIL; /* truncate to zero length */ |
| 635 |
|
| 636 |
/* If asked to effectively extend the list, do nothing */ |
| 637 |
if (new_size < list_length(list)) |
| 638 |
list->length = new_size; |
| 639 |
|
| 640 |
/* |
| 641 |
* Note: unlike the individual-list-cell deletion functions, we don't move |
| 642 |
* the list cells to new storage, even in DEBUG_LIST_MEMORY_USAGE mode. |
| 643 |
* This is because none of them can move in this operation, so just like |
| 644 |
* in the old cons-cell-based implementation, this function doesn't |
| 645 |
* invalidate any pointers to cells of the list. This is also the reason |
| 646 |
* for not wiping the memory of the deleted cells: the old code didn't |
| 647 |
* free them either. Perhaps later we'll tighten this up. |
| 648 |
*/ |
| 649 |
|
| 650 |
return list; |
| 651 |
} |
| 652 |
|
| 653 |
/* |
| 654 |
* Return true iff 'datum' is a member of the list. Equality is |
| 655 |
* determined via equal(), so callers should ensure that they pass a |
| 656 |
* Node as 'datum'. |
| 657 |
* |
| 658 |
* This does a simple linear search --- avoid using it on long lists. |
| 659 |
*/ |
| 660 |
bool |
| 661 |
list_member(const List *list, const void *datum) |
| 662 |
{ |
| 663 |
const ListCell *cell; |
| 664 |
|
| 665 |
Assert(IsPointerList(list)); |
| 666 |
check_list_invariants(list); |
| 667 |
|
| 668 |
foreach(cell, list) |
| 669 |
{ |
| 670 |
if (equal(lfirst(cell), datum)) |
| 671 |
return true; |
| 672 |
} |
| 673 |
|
| 674 |
return false; |
| 675 |
} |
| 676 |
|
| 677 |
/* |
| 678 |
* Return true iff 'datum' is a member of the list. Equality is |
| 679 |
* determined by using simple pointer comparison. |
| 680 |
*/ |
| 681 |
bool |
| 682 |
list_member_ptr(const List *list, const void *datum) |
| 683 |
{ |
| 684 |
const ListCell *cell; |
| 685 |
|
| 686 |
Assert(IsPointerList(list)); |
| 687 |
check_list_invariants(list); |
| 688 |
|
| 689 |
foreach(cell, list) |
| 690 |
{ |
| 691 |
if (lfirst(cell) == datum) |
| 692 |
return true; |
| 693 |
} |
| 694 |
|
| 695 |
return false; |
| 696 |
} |
| 697 |
|
| 698 |
/* |
| 699 |
* Return true iff the integer 'datum' is a member of the list. |
| 700 |
*/ |
| 701 |
bool |
| 702 |
list_member_int(const List *list, int datum) |
| 703 |
{ |
| 704 |
const ListCell *cell; |
| 705 |
|
| 706 |
Assert(IsIntegerList(list)); |
| 707 |
check_list_invariants(list); |
| 708 |
|
| 709 |
foreach(cell, list) |
| 710 |
{ |
| 711 |
if (lfirst_int(cell) == datum) |
| 712 |
return true; |
| 713 |
} |
| 714 |
|
| 715 |
return false; |
| 716 |
} |
| 717 |
|
| 718 |
/* |
| 719 |
* Return true iff the OID 'datum' is a member of the list. |
| 720 |
*/ |
| 721 |
bool |
| 722 |
list_member_oid(const List *list, Oid datum) |
| 723 |
{ |
| 724 |
const ListCell *cell; |
| 725 |
|
| 726 |
Assert(IsOidList(list)); |
| 727 |
check_list_invariants(list); |
| 728 |
|
| 729 |
foreach(cell, list) |
| 730 |
{ |
| 731 |
if (lfirst_oid(cell) == datum) |
| 732 |
return true; |
| 733 |
} |
| 734 |
|
| 735 |
return false; |
| 736 |
} |
| 737 |
|
| 738 |
/* |
| 739 |
* Return true iff the TransactionId 'datum' is a member of the list. |
| 740 |
*/ |
| 741 |
bool |
| 742 |
list_member_xid(const List *list, TransactionId datum) |
| 743 |
{ |
| 744 |
const ListCell *cell; |
| 745 |
|
| 746 |
Assert(IsXidList(list)); |
| 747 |
check_list_invariants(list); |
| 748 |
|
| 749 |
foreach(cell, list) |
| 750 |
{ |
| 751 |
if (lfirst_xid(cell) == datum) |
| 752 |
return true; |
| 753 |
} |
| 754 |
|
| 755 |
return false; |
| 756 |
} |
| 757 |
|
| 758 |
/* |
| 759 |
* Delete the n'th cell (counting from 0) in list. |
| 760 |
* |
| 761 |
* The List is pfree'd if this was the last member. |
| 762 |
* |
| 763 |
* Note that this takes time proportional to the distance to the end of the |
| 764 |
* list, since the following entries must be moved. |
| 765 |
*/ |
| 766 |
List * |
| 767 |
list_delete_nth_cell(List *list, int n) |
| 768 |
{ |
| 769 |
check_list_invariants(list); |
| 770 |
|
| 771 |
Assert(n >= 0 && n < list->length); |
| 772 |
|
| 773 |
/* |
| 774 |
* If we're about to delete the last node from the list, free the whole |
| 775 |
* list instead and return NIL, which is the only valid representation of |
| 776 |
* a zero-length list. |
| 777 |
*/ |
| 778 |
if (list->length == 1) |
| 779 |
{ |
| 780 |
list_free(list); |
| 781 |
return NIL; |
| 782 |
} |
| 783 |
|
| 784 |
/* |
| 785 |
* Otherwise, we normally just collapse out the removed element. But for |
| 786 |
* debugging purposes, move the whole list contents someplace else. |
| 787 |
* |
| 788 |
* (Note that we *must* keep the contents in the same memory context.) |
| 789 |
*/ |
| 790 |
#ifndef DEBUG_LIST_MEMORY_USAGE |
| 791 |
memmove(&list->elements[n], &list->elements[n + 1], |
| 792 |
(list->length - 1 - n) * sizeof(ListCell)); |
| 793 |
list->length--; |
| 794 |
#else |
| 795 |
{ |
| 796 |
ListCell *newelems; |
| 797 |
int newmaxlen = list->length - 1; |
| 798 |
|
| 799 |
newelems = (ListCell *) |
| 800 |
MemoryContextAlloc(GetMemoryChunkContext(list), |
| 801 |
newmaxlen * sizeof(ListCell)); |
| 802 |
memcpy(newelems, list->elements, n * sizeof(ListCell)); |
| 803 |
memcpy(&newelems[n], &list->elements[n + 1], |
| 804 |
(list->length - 1 - n) * sizeof(ListCell)); |
| 805 |
if (list->elements != list->initial_elements) |
| 806 |
pfree(list->elements); |
| 807 |
else |
| 808 |
{ |
| 809 |
/* |
| 810 |
* As in enlarge_list(), clear the initial_elements[] space and/or |
| 811 |
* mark it inaccessible. |
| 812 |
*/ |
| 813 |
#ifdef CLOBBER_FREED_MEMORY |
| 814 |
wipe_mem(list->initial_elements, |
| 815 |
list->max_length * sizeof(ListCell)); |
| 816 |
#else |
| 817 |
VALGRIND_MAKE_MEM_NOACCESS(list->initial_elements, |
| 818 |
list->max_length * sizeof(ListCell)); |
| 819 |
#endif |
| 820 |
} |
| 821 |
list->elements = newelems; |
| 822 |
list->max_length = newmaxlen; |
| 823 |
list->length--; |
| 824 |
check_list_invariants(list); |
| 825 |
} |
| 826 |
#endif |
| 827 |
|
| 828 |
return list; |
| 829 |
} |
| 830 |
|
| 831 |
/* |
| 832 |
* Delete 'cell' from 'list'. |
| 833 |
* |
| 834 |
* The List is pfree'd if this was the last member. However, we do not |
| 835 |
* touch any data the cell might've been pointing to. |
| 836 |
* |
| 837 |
* Note that this takes time proportional to the distance to the end of the |
| 838 |
* list, since the following entries must be moved. |
| 839 |
*/ |
| 840 |
List * |
| 841 |
list_delete_cell(List *list, ListCell *cell) |
| 842 |
{ |
| 843 |
return list_delete_nth_cell(list, cell - list->elements); |
| 844 |
} |
| 845 |
|
| 846 |
/* |
| 847 |
* Delete the first cell in list that matches datum, if any. |
| 848 |
* Equality is determined via equal(). |
| 849 |
* |
| 850 |
* This does a simple linear search --- avoid using it on long lists. |
| 851 |
*/ |
| 852 |
List * |
| 853 |
list_delete(List *list, void *datum) |
| 854 |
{ |
| 855 |
ListCell *cell; |
| 856 |
|
| 857 |
Assert(IsPointerList(list)); |
| 858 |
check_list_invariants(list); |
| 859 |
|
| 860 |
foreach(cell, list) |
| 861 |
{ |
| 862 |
if (equal(lfirst(cell), datum)) |
| 863 |
return list_delete_cell(list, cell); |
| 864 |
} |
| 865 |
|
| 866 |
/* Didn't find a match: return the list unmodified */ |
| 867 |
return list; |
| 868 |
} |
| 869 |
|
| 870 |
/* As above, but use simple pointer equality */ |
| 871 |
List * |
| 872 |
list_delete_ptr(List *list, void *datum) |
| 873 |
{ |
| 874 |
ListCell *cell; |
| 875 |
|
| 876 |
Assert(IsPointerList(list)); |
| 877 |
check_list_invariants(list); |
| 878 |
|
| 879 |
foreach(cell, list) |
| 880 |
{ |
| 881 |
if (lfirst(cell) == datum) |
| 882 |
return list_delete_cell(list, cell); |
| 883 |
} |
| 884 |
|
| 885 |
/* Didn't find a match: return the list unmodified */ |
| 886 |
return list; |
| 887 |
} |
| 888 |
|
| 889 |
/* As above, but for integers */ |
| 890 |
List * |
| 891 |
list_delete_int(List *list, int datum) |
| 892 |
{ |
| 893 |
ListCell *cell; |
| 894 |
|
| 895 |
Assert(IsIntegerList(list)); |
| 896 |
check_list_invariants(list); |
| 897 |
|
| 898 |
foreach(cell, list) |
| 899 |
{ |
| 900 |
if (lfirst_int(cell) == datum) |
| 901 |
return list_delete_cell(list, cell); |
| 902 |
} |
| 903 |
|
| 904 |
/* Didn't find a match: return the list unmodified */ |
| 905 |
return list; |
| 906 |
} |
| 907 |
|
| 908 |
/* As above, but for OIDs */ |
| 909 |
List * |
| 910 |
list_delete_oid(List *list, Oid datum) |
| 911 |
{ |
| 912 |
ListCell *cell; |
| 913 |
|
| 914 |
Assert(IsOidList(list)); |
| 915 |
check_list_invariants(list); |
| 916 |
|
| 917 |
foreach(cell, list) |
| 918 |
{ |
| 919 |
if (lfirst_oid(cell) == datum) |
| 920 |
return list_delete_cell(list, cell); |
| 921 |
} |
| 922 |
|
| 923 |
/* Didn't find a match: return the list unmodified */ |
| 924 |
return list; |
| 925 |
} |
| 926 |
|
| 927 |
/* |
| 928 |
* Delete the first element of the list. |
| 929 |
* |
| 930 |
* This is useful to replace the Lisp-y code "list = lnext(list);" in cases |
| 931 |
* where the intent is to alter the list rather than just traverse it. |
| 932 |
* Beware that the list is modified, whereas the Lisp-y coding leaves |
| 933 |
* the original list head intact in case there's another pointer to it. |
| 934 |
* |
| 935 |
* Note that this takes time proportional to the length of the list, |
| 936 |
* since the remaining entries must be moved. Consider reversing the |
| 937 |
* list order so that you can use list_delete_last() instead. However, |
| 938 |
* if that causes you to replace lappend() with lcons(), you haven't |
| 939 |
* improved matters. (In short, you can make an efficient stack from |
| 940 |
* a List, but not an efficient FIFO queue.) |
| 941 |
*/ |
| 942 |
List * |
| 943 |
list_delete_first(List *list) |
| 944 |
{ |
| 945 |
check_list_invariants(list); |
| 946 |
|
| 947 |
if (list == NIL) |
| 948 |
return NIL; /* would an error be better? */ |
| 949 |
|
| 950 |
return list_delete_nth_cell(list, 0); |
| 951 |
} |
| 952 |
|
| 953 |
/* |
| 954 |
* Delete the last element of the list. |
| 955 |
*/ |
| 956 |
List * |
| 957 |
list_delete_last(List *list) |
| 958 |
{ |
| 959 |
check_list_invariants(list); |
| 960 |
|
| 961 |
if (list == NIL) |
| 962 |
return NIL; /* would an error be better? */ |
| 963 |
|
| 964 |
/* list_truncate won't free list if it goes to empty, but this should */ |
| 965 |
if (list_length(list) <= 1) |
| 966 |
{ |
| 967 |
list_free(list); |
| 968 |
return NIL; |
| 969 |
} |
| 970 |
|
| 971 |
return list_truncate(list, list_length(list) - 1); |
| 972 |
} |
| 973 |
|
| 974 |
/* |
| 975 |
* Delete the first N cells of the list. |
| 976 |
* |
| 977 |
* The List is pfree'd if the request causes all cells to be deleted. |
| 978 |
* |
| 979 |
* Note that this takes time proportional to the distance to the end of the |
| 980 |
* list, since the following entries must be moved. |
| 981 |
*/ |
| 982 |
List * |
| 983 |
list_delete_first_n(List *list, int n) |
| 984 |
{ |
| 985 |
check_list_invariants(list); |
| 986 |
|
| 987 |
/* No-op request? */ |
| 988 |
if (n <= 0) |
| 989 |
return list; |
| 990 |
|
| 991 |
/* Delete whole list? */ |
| 992 |
if (n >= list_length(list)) |
| 993 |
{ |
| 994 |
list_free(list); |
| 995 |
return NIL; |
| 996 |
} |
| 997 |
|
| 998 |
/* |
| 999 |
* Otherwise, we normally just collapse out the removed elements. But for |
| 1000 |
* debugging purposes, move the whole list contents someplace else. |
| 1001 |
* |
| 1002 |
* (Note that we *must* keep the contents in the same memory context.) |
| 1003 |
*/ |
| 1004 |
#ifndef DEBUG_LIST_MEMORY_USAGE |
| 1005 |
memmove(&list->elements[0], &list->elements[n], |
| 1006 |
(list->length - n) * sizeof(ListCell)); |
| 1007 |
list->length -= n; |
| 1008 |
#else |
| 1009 |
{ |
| 1010 |
ListCell *newelems; |
| 1011 |
int newmaxlen = list->length - n; |
| 1012 |
|
| 1013 |
newelems = (ListCell *) |
| 1014 |
MemoryContextAlloc(GetMemoryChunkContext(list), |
| 1015 |
newmaxlen * sizeof(ListCell)); |
| 1016 |
memcpy(newelems, &list->elements[n], newmaxlen * sizeof(ListCell)); |
| 1017 |
if (list->elements != list->initial_elements) |
| 1018 |
pfree(list->elements); |
| 1019 |
else |
| 1020 |
{ |
| 1021 |
/* |
| 1022 |
* As in enlarge_list(), clear the initial_elements[] space and/or |
| 1023 |
* mark it inaccessible. |
| 1024 |
*/ |
| 1025 |
#ifdef CLOBBER_FREED_MEMORY |
| 1026 |
wipe_mem(list->initial_elements, |
| 1027 |
list->max_length * sizeof(ListCell)); |
| 1028 |
#else |
| 1029 |
VALGRIND_MAKE_MEM_NOACCESS(list->initial_elements, |
| 1030 |
list->max_length * sizeof(ListCell)); |
| 1031 |
#endif |
| 1032 |
} |
| 1033 |
list->elements = newelems; |
| 1034 |
list->max_length = newmaxlen; |
| 1035 |
list->length = newmaxlen; |
| 1036 |
check_list_invariants(list); |
| 1037 |
} |
| 1038 |
#endif |
| 1039 |
|
| 1040 |
return list; |
| 1041 |
} |
| 1042 |
|
| 1043 |
/* |
| 1044 |
* Generate the union of two lists. This is calculated by copying |
| 1045 |
* list1 via list_copy(), then adding to it all the members of list2 |
| 1046 |
* that aren't already in list1. |
| 1047 |
* |
| 1048 |
* Whether an element is already a member of the list is determined |
| 1049 |
* via equal(). |
| 1050 |
* |
| 1051 |
* The returned list is newly-allocated, although the content of the |
| 1052 |
* cells is the same (i.e. any pointed-to objects are not copied). |
| 1053 |
* |
| 1054 |
* NB: this function will NOT remove any duplicates that are present |
| 1055 |
* in list1 (so it only performs a "union" if list1 is known unique to |
| 1056 |
* start with). Also, if you are about to write "x = list_union(x, y)" |
| 1057 |
* you probably want to use list_concat_unique() instead to avoid wasting |
| 1058 |
* the storage of the old x list. |
| 1059 |
* |
| 1060 |
* Note that this takes time proportional to the product of the list |
| 1061 |
* lengths, so beware of using it on long lists. (We could probably |
| 1062 |
* improve that, but really you should be using some other data structure |
| 1063 |
* if this'd be a performance bottleneck.) |
| 1064 |
*/ |
| 1065 |
List * |
| 1066 |
list_union(const List *list1, const List *list2) |
| 1067 |
{ |
| 1068 |
List *result; |
| 1069 |
const ListCell *cell; |
| 1070 |
|
| 1071 |
Assert(IsPointerList(list1)); |
| 1072 |
Assert(IsPointerList(list2)); |
| 1073 |
|
| 1074 |
result = list_copy(list1); |
| 1075 |
foreach(cell, list2) |
| 1076 |
{ |
| 1077 |
if (!list_member(result, lfirst(cell))) |
| 1078 |
result = lappend(result, lfirst(cell)); |
| 1079 |
} |
| 1080 |
|
| 1081 |
check_list_invariants(result); |
| 1082 |
return result; |
| 1083 |
} |
| 1084 |
|
| 1085 |
/* |
| 1086 |
* This variant of list_union() determines duplicates via simple |
| 1087 |
* pointer comparison. |
| 1088 |
*/ |
| 1089 |
List * |
| 1090 |
list_union_ptr(const List *list1, const List *list2) |
| 1091 |
{ |
| 1092 |
List *result; |
| 1093 |
const ListCell *cell; |
| 1094 |
|
| 1095 |
Assert(IsPointerList(list1)); |
| 1096 |
Assert(IsPointerList(list2)); |
| 1097 |
|
| 1098 |
result = list_copy(list1); |
| 1099 |
foreach(cell, list2) |
| 1100 |
{ |
| 1101 |
if (!list_member_ptr(result, lfirst(cell))) |
| 1102 |
result = lappend(result, lfirst(cell)); |
| 1103 |
} |
| 1104 |
|
| 1105 |
check_list_invariants(result); |
| 1106 |
return result; |
| 1107 |
} |
| 1108 |
|
| 1109 |
/* |
| 1110 |
* This variant of list_union() operates upon lists of integers. |
| 1111 |
*/ |
| 1112 |
List * |
| 1113 |
list_union_int(const List *list1, const List *list2) |
| 1114 |
{ |
| 1115 |
List *result; |
| 1116 |
const ListCell *cell; |
| 1117 |
|
| 1118 |
Assert(IsIntegerList(list1)); |
| 1119 |
Assert(IsIntegerList(list2)); |
| 1120 |
|
| 1121 |
result = list_copy(list1); |
| 1122 |
foreach(cell, list2) |
| 1123 |
{ |
| 1124 |
if (!list_member_int(result, lfirst_int(cell))) |
| 1125 |
result = lappend_int(result, lfirst_int(cell)); |
| 1126 |
} |
| 1127 |
|
| 1128 |
check_list_invariants(result); |
| 1129 |
return result; |
| 1130 |
} |
| 1131 |
|
| 1132 |
/* |
| 1133 |
* This variant of list_union() operates upon lists of OIDs. |
| 1134 |
*/ |
| 1135 |
List * |
| 1136 |
list_union_oid(const List *list1, const List *list2) |
| 1137 |
{ |
| 1138 |
List *result; |
| 1139 |
const ListCell *cell; |
| 1140 |
|
| 1141 |
Assert(IsOidList(list1)); |
| 1142 |
Assert(IsOidList(list2)); |
| 1143 |
|
| 1144 |
result = list_copy(list1); |
| 1145 |
foreach(cell, list2) |
| 1146 |
{ |
| 1147 |
if (!list_member_oid(result, lfirst_oid(cell))) |
| 1148 |
result = lappend_oid(result, lfirst_oid(cell)); |
| 1149 |
} |
| 1150 |
|
| 1151 |
check_list_invariants(result); |
| 1152 |
return result; |
| 1153 |
} |
| 1154 |
|
| 1155 |
/* |
| 1156 |
* Return a list that contains all the cells that are in both list1 and |
| 1157 |
* list2. The returned list is freshly allocated via palloc(), but the |
| 1158 |
* cells themselves point to the same objects as the cells of the |
| 1159 |
* input lists. |
| 1160 |
* |
| 1161 |
* Duplicate entries in list1 will not be suppressed, so it's only a true |
| 1162 |
* "intersection" if list1 is known unique beforehand. |
| 1163 |
* |
| 1164 |
* This variant works on lists of pointers, and determines list |
| 1165 |
* membership via equal(). Note that the list1 member will be pointed |
| 1166 |
* to in the result. |
| 1167 |
* |
| 1168 |
* Note that this takes time proportional to the product of the list |
| 1169 |
* lengths, so beware of using it on long lists. (We could probably |
| 1170 |
* improve that, but really you should be using some other data structure |
| 1171 |
* if this'd be a performance bottleneck.) |
| 1172 |
*/ |
| 1173 |
List * |
| 1174 |
list_intersection(const List *list1, const List *list2) |
| 1175 |
{ |
| 1176 |
List *result; |
| 1177 |
const ListCell *cell; |
| 1178 |
|
| 1179 |
if (list1 == NIL || list2 == NIL) |
| 1180 |
return NIL; |
| 1181 |
|
| 1182 |
Assert(IsPointerList(list1)); |
| 1183 |
Assert(IsPointerList(list2)); |
| 1184 |
|
| 1185 |
result = NIL; |
| 1186 |
foreach(cell, list1) |
| 1187 |
{ |
| 1188 |
if (list_member(list2, lfirst(cell))) |
| 1189 |
result = lappend(result, lfirst(cell)); |
| 1190 |
} |
| 1191 |
|
| 1192 |
check_list_invariants(result); |
| 1193 |
return result; |
| 1194 |
} |
| 1195 |
|
| 1196 |
/* |
| 1197 |
* As list_intersection but operates on lists of integers. |
| 1198 |
*/ |
| 1199 |
List * |
| 1200 |
list_intersection_int(const List *list1, const List *list2) |
| 1201 |
{ |
| 1202 |
List *result; |
| 1203 |
const ListCell *cell; |
| 1204 |
|
| 1205 |
if (list1 == NIL || list2 == NIL) |
| 1206 |
return NIL; |
| 1207 |
|
| 1208 |
Assert(IsIntegerList(list1)); |
| 1209 |
Assert(IsIntegerList(list2)); |
| 1210 |
|
| 1211 |
result = NIL; |
| 1212 |
foreach(cell, list1) |
| 1213 |
{ |
| 1214 |
if (list_member_int(list2, lfirst_int(cell))) |
| 1215 |
result = lappend_int(result, lfirst_int(cell)); |
| 1216 |
} |
| 1217 |
|
| 1218 |
check_list_invariants(result); |
| 1219 |
return result; |
| 1220 |
} |
| 1221 |
|
| 1222 |
/* |
| 1223 |
* Return a list that contains all the cells in list1 that are not in |
| 1224 |
* list2. The returned list is freshly allocated via palloc(), but the |
| 1225 |
* cells themselves point to the same objects as the cells of the |
| 1226 |
* input lists. |
| 1227 |
* |
| 1228 |
* This variant works on lists of pointers, and determines list |
| 1229 |
* membership via equal() |
| 1230 |
* |
| 1231 |
* Note that this takes time proportional to the product of the list |
| 1232 |
* lengths, so beware of using it on long lists. (We could probably |
| 1233 |
* improve that, but really you should be using some other data structure |
| 1234 |
* if this'd be a performance bottleneck.) |
| 1235 |
*/ |
| 1236 |
List * |
| 1237 |
list_difference(const List *list1, const List *list2) |
| 1238 |
{ |
| 1239 |
const ListCell *cell; |
| 1240 |
List *result = NIL; |
| 1241 |
|
| 1242 |
Assert(IsPointerList(list1)); |
| 1243 |
Assert(IsPointerList(list2)); |
| 1244 |
|
| 1245 |
if (list2 == NIL) |
| 1246 |
return list_copy(list1); |
| 1247 |
|
| 1248 |
foreach(cell, list1) |
| 1249 |
{ |
| 1250 |
if (!list_member(list2, lfirst(cell))) |
| 1251 |
result = lappend(result, lfirst(cell)); |
| 1252 |
} |
| 1253 |
|
| 1254 |
check_list_invariants(result); |
| 1255 |
return result; |
| 1256 |
} |
| 1257 |
|
| 1258 |
/* |
| 1259 |
* This variant of list_difference() determines list membership via |
| 1260 |
* simple pointer equality. |
| 1261 |
*/ |
| 1262 |
List * |
| 1263 |
list_difference_ptr(const List *list1, const List *list2) |
| 1264 |
{ |
| 1265 |
const ListCell *cell; |
| 1266 |
List *result = NIL; |
| 1267 |
|
| 1268 |
Assert(IsPointerList(list1)); |
| 1269 |
Assert(IsPointerList(list2)); |
| 1270 |
|
| 1271 |
if (list2 == NIL) |
| 1272 |
return list_copy(list1); |
| 1273 |
|
| 1274 |
foreach(cell, list1) |
| 1275 |
{ |
| 1276 |
if (!list_member_ptr(list2, lfirst(cell))) |
| 1277 |
result = lappend(result, lfirst(cell)); |
| 1278 |
} |
| 1279 |
|
| 1280 |
check_list_invariants(result); |
| 1281 |
return result; |
| 1282 |
} |
| 1283 |
|
| 1284 |
/* |
| 1285 |
* This variant of list_difference() operates upon lists of integers. |
| 1286 |
*/ |
| 1287 |
List * |
| 1288 |
list_difference_int(const List *list1, const List *list2) |
| 1289 |
{ |
| 1290 |
const ListCell *cell; |
| 1291 |
List *result = NIL; |
| 1292 |
|
| 1293 |
Assert(IsIntegerList(list1)); |
| 1294 |
Assert(IsIntegerList(list2)); |
| 1295 |
|
| 1296 |
if (list2 == NIL) |
| 1297 |
return list_copy(list1); |
| 1298 |
|
| 1299 |
foreach(cell, list1) |
| 1300 |
{ |
| 1301 |
if (!list_member_int(list2, lfirst_int(cell))) |
| 1302 |
result = lappend_int(result, lfirst_int(cell)); |
| 1303 |
} |
| 1304 |
|
| 1305 |
check_list_invariants(result); |
| 1306 |
return result; |
| 1307 |
} |
| 1308 |
|
| 1309 |
/* |
| 1310 |
* This variant of list_difference() operates upon lists of OIDs. |
| 1311 |
*/ |
| 1312 |
List * |
| 1313 |
list_difference_oid(const List *list1, const List *list2) |
| 1314 |
{ |
| 1315 |
const ListCell *cell; |
| 1316 |
List *result = NIL; |
| 1317 |
|
| 1318 |
Assert(IsOidList(list1)); |
| 1319 |
Assert(IsOidList(list2)); |
| 1320 |
|
| 1321 |
if (list2 == NIL) |
| 1322 |
return list_copy(list1); |
| 1323 |
|
| 1324 |
foreach(cell, list1) |
| 1325 |
{ |
| 1326 |
if (!list_member_oid(list2, lfirst_oid(cell))) |
| 1327 |
result = lappend_oid(result, lfirst_oid(cell)); |
| 1328 |
} |
| 1329 |
|
| 1330 |
check_list_invariants(result); |
| 1331 |
return result; |
| 1332 |
} |
| 1333 |
|
| 1334 |
/* |
| 1335 |
* Append datum to list, but only if it isn't already in the list. |
| 1336 |
* |
| 1337 |
* Whether an element is already a member of the list is determined |
| 1338 |
* via equal(). |
| 1339 |
* |
| 1340 |
* This does a simple linear search --- avoid using it on long lists. |
| 1341 |
*/ |
| 1342 |
List * |
| 1343 |
list_append_unique(List *list, void *datum) |
| 1344 |
{ |
| 1345 |
if (list_member(list, datum)) |
| 1346 |
return list; |
| 1347 |
else |
| 1348 |
return lappend(list, datum); |
| 1349 |
} |
| 1350 |
|
| 1351 |
/* |
| 1352 |
* This variant of list_append_unique() determines list membership via |
| 1353 |
* simple pointer equality. |
| 1354 |
*/ |
| 1355 |
List * |
| 1356 |
list_append_unique_ptr(List *list, void *datum) |
| 1357 |
{ |
| 1358 |
if (list_member_ptr(list, datum)) |
| 1359 |
return list; |
| 1360 |
else |
| 1361 |
return lappend(list, datum); |
| 1362 |
} |
| 1363 |
|
| 1364 |
/* |
| 1365 |
* This variant of list_append_unique() operates upon lists of integers. |
| 1366 |
*/ |
| 1367 |
List * |
| 1368 |
list_append_unique_int(List *list, int datum) |
| 1369 |
{ |
| 1370 |
if (list_member_int(list, datum)) |
| 1371 |
return list; |
| 1372 |
else |
| 1373 |
return lappend_int(list, datum); |
| 1374 |
} |
| 1375 |
|
| 1376 |
/* |
| 1377 |
* This variant of list_append_unique() operates upon lists of OIDs. |
| 1378 |
*/ |
| 1379 |
List * |
| 1380 |
list_append_unique_oid(List *list, Oid datum) |
| 1381 |
{ |
| 1382 |
if (list_member_oid(list, datum)) |
| 1383 |
return list; |
| 1384 |
else |
| 1385 |
return lappend_oid(list, datum); |
| 1386 |
} |
| 1387 |
|
| 1388 |
/* |
| 1389 |
* Append to list1 each member of list2 that isn't already in list1. |
| 1390 |
* |
| 1391 |
* Whether an element is already a member of the list is determined |
| 1392 |
* via equal(). |
| 1393 |
* |
| 1394 |
* This is almost the same functionality as list_union(), but list1 is |
| 1395 |
* modified in-place rather than being copied. However, callers of this |
| 1396 |
* function may have strict ordering expectations -- i.e. that the relative |
| 1397 |
* order of those list2 elements that are not duplicates is preserved. |
| 1398 |
* |
| 1399 |
* Note that this takes time proportional to the product of the list |
| 1400 |
* lengths, so beware of using it on long lists. (We could probably |
| 1401 |
* improve that, but really you should be using some other data structure |
| 1402 |
* if this'd be a performance bottleneck.) |
| 1403 |
*/ |
| 1404 |
List * |
| 1405 |
list_concat_unique(List *list1, const List *list2) |
| 1406 |
{ |
| 1407 |
ListCell *cell; |
| 1408 |
|
| 1409 |
Assert(IsPointerList(list1)); |
| 1410 |
Assert(IsPointerList(list2)); |
| 1411 |
|
| 1412 |
foreach(cell, list2) |
| 1413 |
{ |
| 1414 |
if (!list_member(list1, lfirst(cell))) |
| 1415 |
list1 = lappend(list1, lfirst(cell)); |
| 1416 |
} |
| 1417 |
|
| 1418 |
check_list_invariants(list1); |
| 1419 |
return list1; |
| 1420 |
} |
| 1421 |
|
| 1422 |
/* |
| 1423 |
* This variant of list_concat_unique() determines list membership via |
| 1424 |
* simple pointer equality. |
| 1425 |
*/ |
| 1426 |
List * |
| 1427 |
list_concat_unique_ptr(List *list1, const List *list2) |
| 1428 |
{ |
| 1429 |
ListCell *cell; |
| 1430 |
|
| 1431 |
Assert(IsPointerList(list1)); |
| 1432 |
Assert(IsPointerList(list2)); |
| 1433 |
|
| 1434 |
foreach(cell, list2) |
| 1435 |
{ |
| 1436 |
if (!list_member_ptr(list1, lfirst(cell))) |
| 1437 |
list1 = lappend(list1, lfirst(cell)); |
| 1438 |
} |
| 1439 |
|
| 1440 |
check_list_invariants(list1); |
| 1441 |
return list1; |
| 1442 |
} |
| 1443 |
|
| 1444 |
/* |
| 1445 |
* This variant of list_concat_unique() operates upon lists of integers. |
| 1446 |
*/ |
| 1447 |
List * |
| 1448 |
list_concat_unique_int(List *list1, const List *list2) |
| 1449 |
{ |
| 1450 |
ListCell *cell; |
| 1451 |
|
| 1452 |
Assert(IsIntegerList(list1)); |
| 1453 |
Assert(IsIntegerList(list2)); |
| 1454 |
|
| 1455 |
foreach(cell, list2) |
| 1456 |
{ |
| 1457 |
if (!list_member_int(list1, lfirst_int(cell))) |
| 1458 |
list1 = lappend_int(list1, lfirst_int(cell)); |
| 1459 |
} |
| 1460 |
|
| 1461 |
check_list_invariants(list1); |
| 1462 |
return list1; |
| 1463 |
} |
| 1464 |
|
| 1465 |
/* |
| 1466 |
* This variant of list_concat_unique() operates upon lists of OIDs. |
| 1467 |
*/ |
| 1468 |
List * |
| 1469 |
list_concat_unique_oid(List *list1, const List *list2) |
| 1470 |
{ |
| 1471 |
ListCell *cell; |
| 1472 |
|
| 1473 |
Assert(IsOidList(list1)); |
| 1474 |
Assert(IsOidList(list2)); |
| 1475 |
|
| 1476 |
foreach(cell, list2) |
| 1477 |
{ |
| 1478 |
if (!list_member_oid(list1, lfirst_oid(cell))) |
| 1479 |
list1 = lappend_oid(list1, lfirst_oid(cell)); |
| 1480 |
} |
| 1481 |
|
| 1482 |
check_list_invariants(list1); |
| 1483 |
return list1; |
| 1484 |
} |
| 1485 |
|
| 1486 |
/* |
| 1487 |
* Remove adjacent duplicates in a list of OIDs. |
| 1488 |
* |
| 1489 |
* It is caller's responsibility to have sorted the list to bring duplicates |
| 1490 |
* together, perhaps via list_sort(list, list_oid_cmp). |
| 1491 |
* |
| 1492 |
* Note that this takes time proportional to the length of the list. |
| 1493 |
*/ |
| 1494 |
void |
| 1495 |
list_deduplicate_oid(List *list) |
| 1496 |
{ |
| 1497 |
int len; |
| 1498 |
|
| 1499 |
Assert(IsOidList(list)); |
| 1500 |
len = list_length(list); |
| 1501 |
if (len > 1) |
| 1502 |
{ |
| 1503 |
ListCell *elements = list->elements; |
| 1504 |
int i = 0; |
| 1505 |
|
| 1506 |
for (int j = 1; j < len; j++) |
| 1507 |
{ |
| 1508 |
if (elements[i].oid_value != elements[j].oid_value) |
| 1509 |
elements[++i].oid_value = elements[j].oid_value; |
| 1510 |
} |
| 1511 |
list->length = i + 1; |
| 1512 |
} |
| 1513 |
check_list_invariants(list); |
| 1514 |
} |
| 1515 |
|
| 1516 |
/* |
| 1517 |
* Free all storage in a list, and optionally the pointed-to elements |
| 1518 |
*/ |
| 1519 |
static void |
| 1520 |
list_free_private(List *list, bool deep) |
| 1521 |
{ |
| 1522 |
if (list == NIL) |
| 1523 |
return; /* nothing to do */ |
| 1524 |
|
| 1525 |
check_list_invariants(list); |
| 1526 |
|
| 1527 |
if (deep) |
| 1528 |
{ |
| 1529 |
for (int i = 0; i < list->length; i++) |
| 1530 |
pfree(lfirst(&list->elements[i])); |
| 1531 |
} |
| 1532 |
if (list->elements != list->initial_elements) |
| 1533 |
pfree(list->elements); |
| 1534 |
pfree(list); |
| 1535 |
} |
| 1536 |
|
| 1537 |
/* |
| 1538 |
* Free all the cells of the list, as well as the list itself. Any |
| 1539 |
* objects that are pointed-to by the cells of the list are NOT |
| 1540 |
* free'd. |
| 1541 |
* |
| 1542 |
* On return, the argument to this function has been freed, so the |
| 1543 |
* caller would be wise to set it to NIL for safety's sake. |
| 1544 |
*/ |
| 1545 |
void |
| 1546 |
list_free(List *list) |
| 1547 |
{ |
| 1548 |
list_free_private(list, false); |
| 1549 |
} |
| 1550 |
|
| 1551 |
/* |
| 1552 |
* Free all the cells of the list, the list itself, and all the |
| 1553 |
* objects pointed-to by the cells of the list (each element in the |
| 1554 |
* list must contain a pointer to a palloc()'d region of memory!) |
| 1555 |
* |
| 1556 |
* On return, the argument to this function has been freed, so the |
| 1557 |
* caller would be wise to set it to NIL for safety's sake. |
| 1558 |
*/ |
| 1559 |
void |
| 1560 |
list_free_deep(List *list) |
| 1561 |
{ |
| 1562 |
/* |
| 1563 |
* A "deep" free operation only makes sense on a list of pointers. |
| 1564 |
*/ |
| 1565 |
Assert(IsPointerList(list)); |
| 1566 |
list_free_private(list, true); |
| 1567 |
} |
| 1568 |
|
| 1569 |
/* |
| 1570 |
* Return a shallow copy of the specified list. |
| 1571 |
*/ |
| 1572 |
List * |
| 1573 |
list_copy(const List *oldlist) |
| 1574 |
{ |
| 1575 |
List *newlist; |
| 1576 |
|
| 1577 |
if (oldlist == NIL) |
| 1578 |
return NIL; |
| 1579 |
|
| 1580 |
newlist = new_list(oldlist->type, oldlist->length); |
| 1581 |
memcpy(newlist->elements, oldlist->elements, |
| 1582 |
newlist->length * sizeof(ListCell)); |
| 1583 |
|
| 1584 |
check_list_invariants(newlist); |
| 1585 |
return newlist; |
| 1586 |
} |
| 1587 |
|
| 1588 |
/* |
| 1589 |
* Return a shallow copy of the specified list containing only the first 'len' |
| 1590 |
* elements. If oldlist is shorter than 'len' then we copy the entire list. |
| 1591 |
*/ |
| 1592 |
List * |
| 1593 |
list_copy_head(const List *oldlist, int len) |
| 1594 |
{ |
| 1595 |
List *newlist; |
| 1596 |
|
| 1597 |
if (oldlist == NIL || len <= 0) |
| 1598 |
return NIL; |
| 1599 |
|
| 1600 |
len = Min(oldlist->length, len); |
| 1601 |
|
| 1602 |
newlist = new_list(oldlist->type, len); |
| 1603 |
memcpy(newlist->elements, oldlist->elements, len * sizeof(ListCell)); |
| 1604 |
|
| 1605 |
check_list_invariants(newlist); |
| 1606 |
return newlist; |
| 1607 |
} |
| 1608 |
|
| 1609 |
/* |
| 1610 |
* Return a shallow copy of the specified list, without the first N elements. |
| 1611 |
*/ |
| 1612 |
List * |
| 1613 |
list_copy_tail(const List *oldlist, int nskip) |
| 1614 |
{ |
| 1615 |
List *newlist; |
| 1616 |
|
| 1617 |
if (nskip < 0) |
| 1618 |
nskip = 0; /* would it be better to elog? */ |
| 1619 |
|
| 1620 |
if (oldlist == NIL || nskip >= oldlist->length) |
| 1621 |
return NIL; |
| 1622 |
|
| 1623 |
newlist = new_list(oldlist->type, oldlist->length - nskip); |
| 1624 |
memcpy(newlist->elements, &oldlist->elements[nskip], |
| 1625 |
newlist->length * sizeof(ListCell)); |
| 1626 |
|
| 1627 |
check_list_invariants(newlist); |
| 1628 |
return newlist; |
| 1629 |
} |
| 1630 |
|
| 1631 |
/* |
| 1632 |
* Return a deep copy of the specified list. |
| 1633 |
* |
| 1634 |
* The list elements are copied via copyObject(), so that this function's |
| 1635 |
* idea of a "deep" copy is considerably deeper than what list_free_deep() |
| 1636 |
* means by the same word. |
| 1637 |
*/ |
| 1638 |
List * |
| 1639 |
list_copy_deep(const List *oldlist) |
| 1640 |
{ |
| 1641 |
List *newlist; |
| 1642 |
|
| 1643 |
if (oldlist == NIL) |
| 1644 |
return NIL; |
| 1645 |
|
| 1646 |
/* This is only sensible for pointer Lists */ |
| 1647 |
Assert(IsA(oldlist, List)); |
| 1648 |
|
| 1649 |
newlist = new_list(oldlist->type, oldlist->length); |
| 1650 |
for (int i = 0; i < newlist->length; i++) |
| 1651 |
lfirst(&newlist->elements[i]) = |
| 1652 |
copyObjectImpl(lfirst(&oldlist->elements[i])); |
| 1653 |
|
| 1654 |
check_list_invariants(newlist); |
| 1655 |
return newlist; |
| 1656 |
} |
| 1657 |
|
| 1658 |
/* |
| 1659 |
* Sort a list according to the specified comparator function. |
| 1660 |
* |
| 1661 |
* The list is sorted in-place. |
| 1662 |
* |
| 1663 |
* The comparator function is declared to receive arguments of type |
| 1664 |
* const ListCell *; this allows it to use lfirst() and variants |
| 1665 |
* without casting its arguments. Otherwise it behaves the same as |
| 1666 |
* the comparator function for standard qsort(). |
| 1667 |
* |
| 1668 |
* Like qsort(), this provides no guarantees about sort stability |
| 1669 |
* for equal keys. |
| 1670 |
* |
| 1671 |
* This is based on qsort(), so it likewise has O(N log N) runtime. |
| 1672 |
*/ |
| 1673 |
void |
| 1674 |
list_sort(List *list, list_sort_comparator cmp) |
| 1675 |
{ |
| 1676 |
typedef int (*qsort_comparator) (const void *a, const void *b); |
| 1677 |
int len; |
| 1678 |
|
| 1679 |
check_list_invariants(list); |
| 1680 |
|
| 1681 |
/* Nothing to do if there's less than two elements */ |
| 1682 |
len = list_length(list); |
| 1683 |
if (len > 1) |
| 1684 |
qsort(list->elements, len, sizeof(ListCell), (qsort_comparator) cmp); |
| 1685 |
} |
| 1686 |
|
| 1687 |
/* |
| 1688 |
* list_sort comparator for sorting a list into ascending int order. |
| 1689 |
*/ |
| 1690 |
int |
| 1691 |
list_int_cmp(const ListCell *p1, const ListCell *p2) |
| 1692 |
{ |
| 1693 |
int v1 = lfirst_int(p1); |
| 1694 |
int v2 = lfirst_int(p2); |
| 1695 |
|
| 1696 |
return pg_cmp_s32(v1, v2); |
| 1697 |
} |
| 1698 |
|
| 1699 |
/* |
| 1700 |
* list_sort comparator for sorting a list into ascending OID order. |
| 1701 |
*/ |
| 1702 |
int |
| 1703 |
list_oid_cmp(const ListCell *p1, const ListCell *p2) |
| 1704 |
{ |
| 1705 |
Oid v1 = lfirst_oid(p1); |
| 1706 |
Oid v2 = lfirst_oid(p2); |
| 1707 |
|
| 1708 |
return pg_cmp_u32(v1, v2); |
| 1709 |
} |