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