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-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 102388406 : 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 102388406 : max_size = pg_nextpower2_32(Max(8, min_size + LIST_HEADER_OVERHEAD));
127 102388406 : 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 102388406 : newlist = (List *) palloc(offsetof(List, initial_elements) +
138 : max_size * sizeof(ListCell));
139 102388406 : newlist->type = type;
140 102388406 : newlist->length = min_size;
141 102388406 : newlist->max_length = max_size;
142 102388406 : newlist->elements = newlist->initial_elements;
143 :
144 102388406 : 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 5064134 : 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 5064134 : 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 5064134 : 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 3172506 : list->elements = (ListCell *)
186 3172506 : MemoryContextAlloc(GetMemoryChunkContext(list),
187 : new_max_len * sizeof(ListCell));
188 3172506 : memcpy(list->elements, list->initial_elements,
189 3172506 : 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 1891628 : 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 5064134 : list->max_length = new_max_len;
229 5064134 : }
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 12399172 : list_make1_impl(NodeTag t, ListCell datum1)
237 : {
238 12399172 : List *list = new_list(t, 1);
239 :
240 12399172 : list->elements[0] = datum1;
241 : check_list_invariants(list);
242 12399172 : return list;
243 : }
244 :
245 : List *
246 1433736 : list_make2_impl(NodeTag t, ListCell datum1, ListCell datum2)
247 : {
248 1433736 : List *list = new_list(t, 2);
249 :
250 1433736 : list->elements[0] = datum1;
251 1433736 : list->elements[1] = datum2;
252 : check_list_invariants(list);
253 1433736 : return list;
254 : }
255 :
256 : List *
257 6086 : list_make3_impl(NodeTag t, ListCell datum1, ListCell datum2,
258 : ListCell datum3)
259 : {
260 6086 : List *list = new_list(t, 3);
261 :
262 6086 : list->elements[0] = datum1;
263 6086 : list->elements[1] = datum2;
264 6086 : list->elements[2] = datum3;
265 : check_list_invariants(list);
266 6086 : return list;
267 : }
268 :
269 : List *
270 242 : list_make4_impl(NodeTag t, ListCell datum1, ListCell datum2,
271 : ListCell datum3, ListCell datum4)
272 : {
273 242 : List *list = new_list(t, 4);
274 :
275 242 : list->elements[0] = datum1;
276 242 : list->elements[1] = datum2;
277 242 : list->elements[2] = datum3;
278 242 : list->elements[3] = datum4;
279 : check_list_invariants(list);
280 242 : return list;
281 : }
282 :
283 : List *
284 322 : list_make5_impl(NodeTag t, ListCell datum1, ListCell datum2,
285 : ListCell datum3, ListCell datum4, ListCell datum5)
286 : {
287 322 : List *list = new_list(t, 5);
288 :
289 322 : list->elements[0] = datum1;
290 322 : list->elements[1] = datum2;
291 322 : list->elements[2] = datum3;
292 322 : list->elements[3] = datum4;
293 322 : list->elements[4] = datum5;
294 : check_list_invariants(list);
295 322 : 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 2745174 : new_head_cell(List *list)
306 : {
307 : /* Enlarge array if necessary */
308 2745174 : if (list->length >= list->max_length)
309 48240 : enlarge_list(list, list->length + 1);
310 : /* Now shove the existing data over */
311 2745174 : memmove(&list->elements[1], &list->elements[0],
312 2745174 : list->length * sizeof(ListCell));
313 2745174 : list->length++;
314 2745174 : }
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 83030598 : new_tail_cell(List *list)
324 : {
325 : /* Enlarge array if necessary */
326 83030598 : if (list->length >= list->max_length)
327 4994324 : enlarge_list(list, list->length + 1);
328 83030598 : list->length++;
329 83030598 : }
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 125194914 : lappend(List *list, void *datum)
340 : {
341 : Assert(IsPointerList(list));
342 :
343 125194914 : if (list == NIL)
344 51199334 : list = new_list(T_List, 1);
345 : else
346 73995580 : new_tail_cell(list);
347 :
348 125194914 : llast(list) = datum;
349 : check_list_invariants(list);
350 125194914 : return list;
351 : }
352 :
353 : /*
354 : * Append an integer to the specified list. See lappend()
355 : */
356 : List *
357 8794772 : lappend_int(List *list, int datum)
358 : {
359 : Assert(IsIntegerList(list));
360 :
361 8794772 : if (list == NIL)
362 1616068 : list = new_list(T_IntList, 1);
363 : else
364 7178704 : new_tail_cell(list);
365 :
366 8794772 : llast_int(list) = datum;
367 : check_list_invariants(list);
368 8794772 : return list;
369 : }
370 :
371 : /*
372 : * Append an OID to the specified list. See lappend()
373 : */
374 : List *
375 6192964 : lappend_oid(List *list, Oid datum)
376 : {
377 : Assert(IsOidList(list));
378 :
379 6192964 : if (list == NIL)
380 4336716 : list = new_list(T_OidList, 1);
381 : else
382 1856248 : new_tail_cell(list);
383 :
384 6192964 : llast_oid(list) = datum;
385 : check_list_invariants(list);
386 6192964 : return list;
387 : }
388 :
389 : /*
390 : * Append a TransactionId to the specified list. See lappend()
391 : */
392 : List *
393 176 : lappend_xid(List *list, TransactionId datum)
394 : {
395 : Assert(IsXidList(list));
396 :
397 176 : if (list == NIL)
398 110 : list = new_list(T_XidList, 1);
399 : else
400 66 : new_tail_cell(list);
401 :
402 176 : llast_xid(list) = datum;
403 : check_list_invariants(list);
404 176 : 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 658392 : insert_new_cell(List *list, int pos)
416 : {
417 : Assert(pos >= 0 && pos <= list->length);
418 :
419 : /* Enlarge array if necessary */
420 658392 : if (list->length >= list->max_length)
421 1300 : enlarge_list(list, list->length + 1);
422 : /* Now shove the existing data over */
423 658392 : if (pos < list->length)
424 274970 : memmove(&list->elements[pos + 1], &list->elements[pos],
425 274970 : (list->length - pos) * sizeof(ListCell));
426 658392 : list->length++;
427 :
428 658392 : 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 2531564 : list_insert_nth(List *list, int pos, void *datum)
440 : {
441 2531564 : if (list == NIL)
442 : {
443 : Assert(pos == 0);
444 1873172 : return list_make1(datum);
445 : }
446 : Assert(IsPointerList(list));
447 658392 : lfirst(insert_new_cell(list, pos)) = datum;
448 : check_list_invariants(list);
449 658392 : return list;
450 : }
451 :
452 : List *
453 0 : list_insert_nth_int(List *list, int pos, int datum)
454 : {
455 0 : if (list == NIL)
456 : {
457 : Assert(pos == 0);
458 0 : return list_make1_int(datum);
459 : }
460 : Assert(IsIntegerList(list));
461 0 : lfirst_int(insert_new_cell(list, pos)) = datum;
462 : check_list_invariants(list);
463 0 : return list;
464 : }
465 :
466 : List *
467 0 : list_insert_nth_oid(List *list, int pos, Oid datum)
468 : {
469 0 : if (list == NIL)
470 : {
471 : Assert(pos == 0);
472 0 : return list_make1_oid(datum);
473 : }
474 : Assert(IsOidList(list));
475 0 : lfirst_oid(insert_new_cell(list, pos)) = datum;
476 : check_list_invariants(list);
477 0 : 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 6941648 : lcons(void *datum, List *list)
496 : {
497 : Assert(IsPointerList(list));
498 :
499 6941648 : if (list == NIL)
500 4243692 : list = new_list(T_List, 1);
501 : else
502 2697956 : new_head_cell(list);
503 :
504 6941648 : linitial(list) = datum;
505 : check_list_invariants(list);
506 6941648 : return list;
507 : }
508 :
509 : /*
510 : * Prepend an integer to the list. See lcons()
511 : */
512 : List *
513 22462 : lcons_int(int datum, List *list)
514 : {
515 : Assert(IsIntegerList(list));
516 :
517 22462 : if (list == NIL)
518 9392 : list = new_list(T_IntList, 1);
519 : else
520 13070 : new_head_cell(list);
521 :
522 22462 : linitial_int(list) = datum;
523 : check_list_invariants(list);
524 22462 : return list;
525 : }
526 :
527 : /*
528 : * Prepend an OID to the list. See lcons()
529 : */
530 : List *
531 38168 : lcons_oid(Oid datum, List *list)
532 : {
533 : Assert(IsOidList(list));
534 :
535 38168 : if (list == NIL)
536 4020 : list = new_list(T_OidList, 1);
537 : else
538 34148 : new_head_cell(list);
539 :
540 38168 : linitial_oid(list) = datum;
541 : check_list_invariants(list);
542 38168 : 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 5378156 : list_concat(List *list1, const List *list2)
562 : {
563 : int new_len;
564 :
565 5378156 : if (list1 == NIL)
566 3920396 : return list_copy(list2);
567 1457760 : if (list2 == NIL)
568 876242 : return list1;
569 :
570 : Assert(list1->type == list2->type);
571 :
572 581518 : new_len = list1->length + list2->length;
573 : /* Enlarge array if necessary */
574 581518 : if (new_len > list1->max_length)
575 20270 : enlarge_list(list1, new_len);
576 :
577 : /* Even if list1 == list2, using memcpy should be safe here */
578 581518 : memcpy(&list1->elements[list1->length], &list2->elements[0],
579 581518 : list2->length * sizeof(ListCell));
580 581518 : list1->length = new_len;
581 :
582 : check_list_invariants(list1);
583 581518 : 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 931528 : list_concat_copy(const List *list1, const List *list2)
599 : {
600 : List *result;
601 : int new_len;
602 :
603 931528 : if (list1 == NIL)
604 418306 : return list_copy(list2);
605 513222 : if (list2 == NIL)
606 435420 : return list_copy(list1);
607 :
608 : Assert(list1->type == list2->type);
609 :
610 77802 : new_len = list1->length + list2->length;
611 77802 : result = new_list(list1->type, new_len);
612 77802 : memcpy(result->elements, list1->elements,
613 77802 : list1->length * sizeof(ListCell));
614 77802 : memcpy(result->elements + list1->length, list2->elements,
615 77802 : list2->length * sizeof(ListCell));
616 :
617 : check_list_invariants(result);
618 77802 : 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 517560 : list_truncate(List *list, int new_size)
632 : {
633 517560 : if (new_size <= 0)
634 76106 : return NIL; /* truncate to zero length */
635 :
636 : /* If asked to effectively extend the list, do nothing */
637 441454 : if (new_size < list_length(list))
638 104916 : 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 441454 : 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 846686 : 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 993008 : foreach(cell, list)
669 : {
670 226212 : if (equal(lfirst(cell), datum))
671 79890 : return true;
672 : }
673 :
674 766796 : 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 460184 : 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 702662 : foreach(cell, list)
690 : {
691 422438 : if (lfirst(cell) == datum)
692 179960 : return true;
693 : }
694 :
695 280224 : return false;
696 : }
697 :
698 : /*
699 : * Return true iff the integer 'datum' is a member of the list.
700 : */
701 : bool
702 124130 : 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 9993424 : foreach(cell, list)
710 : {
711 9888612 : if (lfirst_int(cell) == datum)
712 19318 : return true;
713 : }
714 :
715 104812 : return false;
716 : }
717 :
718 : /*
719 : * Return true iff the OID 'datum' is a member of the list.
720 : */
721 : bool
722 77437058 : 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 80399810 : foreach(cell, list)
730 : {
731 3966344 : if (lfirst_oid(cell) == datum)
732 1003592 : return true;
733 : }
734 :
735 76433466 : return false;
736 : }
737 :
738 : /*
739 : * Return true iff the TransactionId 'datum' is a member of the list.
740 : */
741 : bool
742 351986 : 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 433726 : foreach(cell, list)
750 : {
751 433550 : if (lfirst_xid(cell) == datum)
752 351810 : return true;
753 : }
754 :
755 176 : 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 3378254 : 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 3378254 : if (list->length == 1)
779 : {
780 1898356 : list_free(list);
781 1898356 : 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 1479898 : memmove(&list->elements[n], &list->elements[n + 1],
792 1479898 : (list->length - 1 - n) * sizeof(ListCell));
793 1479898 : 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 1479898 : 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 2026396 : list_delete_cell(List *list, ListCell *cell)
842 : {
843 2026396 : 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 4472 : list_delete(List *list, void *datum)
854 : {
855 : ListCell *cell;
856 :
857 : Assert(IsPointerList(list));
858 : check_list_invariants(list);
859 :
860 4676 : foreach(cell, list)
861 : {
862 4670 : if (equal(lfirst(cell), datum))
863 4466 : return list_delete_cell(list, cell);
864 : }
865 :
866 : /* Didn't find a match: return the list unmodified */
867 6 : return list;
868 : }
869 :
870 : /* As above, but use simple pointer equality */
871 : List *
872 2010480 : list_delete_ptr(List *list, void *datum)
873 : {
874 : ListCell *cell;
875 :
876 : Assert(IsPointerList(list));
877 : check_list_invariants(list);
878 :
879 2010898 : foreach(cell, list)
880 : {
881 2010898 : if (lfirst(cell) == datum)
882 2010480 : return list_delete_cell(list, cell);
883 : }
884 :
885 : /* Didn't find a match: return the list unmodified */
886 0 : return list;
887 : }
888 :
889 : /* As above, but for integers */
890 : List *
891 164 : list_delete_int(List *list, int datum)
892 : {
893 : ListCell *cell;
894 :
895 : Assert(IsIntegerList(list));
896 : check_list_invariants(list);
897 :
898 170 : foreach(cell, list)
899 : {
900 170 : if (lfirst_int(cell) == datum)
901 164 : return list_delete_cell(list, cell);
902 : }
903 :
904 : /* Didn't find a match: return the list unmodified */
905 0 : return list;
906 : }
907 :
908 : /* As above, but for OIDs */
909 : List *
910 7742 : list_delete_oid(List *list, Oid datum)
911 : {
912 : ListCell *cell;
913 :
914 : Assert(IsOidList(list));
915 : check_list_invariants(list);
916 :
917 7742 : foreach(cell, list)
918 : {
919 1604 : if (lfirst_oid(cell) == datum)
920 1604 : return list_delete_cell(list, cell);
921 : }
922 :
923 : /* Didn't find a match: return the list unmodified */
924 6138 : 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 674204 : list_delete_first(List *list)
944 : {
945 : check_list_invariants(list);
946 :
947 674204 : if (list == NIL)
948 0 : return NIL; /* would an error be better? */
949 :
950 674204 : return list_delete_nth_cell(list, 0);
951 : }
952 :
953 : /*
954 : * Delete the last element of the list.
955 : */
956 : List *
957 67056 : list_delete_last(List *list)
958 : {
959 : check_list_invariants(list);
960 :
961 67056 : if (list == NIL)
962 0 : return NIL; /* would an error be better? */
963 :
964 : /* list_truncate won't free list if it goes to empty, but this should */
965 67056 : if (list_length(list) <= 1)
966 : {
967 35758 : list_free(list);
968 35758 : return NIL;
969 : }
970 :
971 31298 : 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 694 : list_delete_first_n(List *list, int n)
984 : {
985 : check_list_invariants(list);
986 :
987 : /* No-op request? */
988 694 : if (n <= 0)
989 22 : return list;
990 :
991 : /* Delete whole list? */
992 672 : if (n >= list_length(list))
993 : {
994 0 : list_free(list);
995 0 : 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 672 : memmove(&list->elements[0], &list->elements[n],
1006 672 : (list->length - n) * sizeof(ListCell));
1007 672 : 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 672 : 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 8958 : 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 8958 : result = list_copy(list1);
1075 18576 : foreach(cell, list2)
1076 : {
1077 9618 : if (!list_member(result, lfirst(cell)))
1078 9370 : result = lappend(result, lfirst(cell));
1079 : }
1080 :
1081 : check_list_invariants(result);
1082 8958 : return result;
1083 : }
1084 :
1085 : /*
1086 : * This variant of list_union() determines duplicates via simple
1087 : * pointer comparison.
1088 : */
1089 : List *
1090 0 : 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 0 : result = list_copy(list1);
1099 0 : foreach(cell, list2)
1100 : {
1101 0 : if (!list_member_ptr(result, lfirst(cell)))
1102 0 : result = lappend(result, lfirst(cell));
1103 : }
1104 :
1105 : check_list_invariants(result);
1106 0 : return result;
1107 : }
1108 :
1109 : /*
1110 : * This variant of list_union() operates upon lists of integers.
1111 : */
1112 : List *
1113 5802 : 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 5802 : result = list_copy(list1);
1122 11834 : foreach(cell, list2)
1123 : {
1124 6032 : if (!list_member_int(result, lfirst_int(cell)))
1125 5796 : result = lappend_int(result, lfirst_int(cell));
1126 : }
1127 :
1128 : check_list_invariants(result);
1129 5802 : return result;
1130 : }
1131 :
1132 : /*
1133 : * This variant of list_union() operates upon lists of OIDs.
1134 : */
1135 : List *
1136 0 : 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 0 : result = list_copy(list1);
1145 0 : foreach(cell, list2)
1146 : {
1147 0 : if (!list_member_oid(result, lfirst_oid(cell)))
1148 0 : result = lappend_oid(result, lfirst_oid(cell));
1149 : }
1150 :
1151 : check_list_invariants(result);
1152 0 : 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 0 : list_intersection(const List *list1, const List *list2)
1175 : {
1176 : List *result;
1177 : const ListCell *cell;
1178 :
1179 0 : if (list1 == NIL || list2 == NIL)
1180 0 : return NIL;
1181 :
1182 : Assert(IsPointerList(list1));
1183 : Assert(IsPointerList(list2));
1184 :
1185 0 : result = NIL;
1186 0 : foreach(cell, list1)
1187 : {
1188 0 : if (list_member(list2, lfirst(cell)))
1189 0 : result = lappend(result, lfirst(cell));
1190 : }
1191 :
1192 : check_list_invariants(result);
1193 0 : return result;
1194 : }
1195 :
1196 : /*
1197 : * As list_intersection but operates on lists of integers.
1198 : */
1199 : List *
1200 382 : list_intersection_int(const List *list1, const List *list2)
1201 : {
1202 : List *result;
1203 : const ListCell *cell;
1204 :
1205 382 : if (list1 == NIL || list2 == NIL)
1206 0 : return NIL;
1207 :
1208 : Assert(IsIntegerList(list1));
1209 : Assert(IsIntegerList(list2));
1210 :
1211 382 : result = NIL;
1212 812 : foreach(cell, list1)
1213 : {
1214 430 : if (list_member_int(list2, lfirst_int(cell)))
1215 222 : result = lappend_int(result, lfirst_int(cell));
1216 : }
1217 :
1218 : check_list_invariants(result);
1219 382 : 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 37232 : list_difference(const List *list1, const List *list2)
1238 : {
1239 : const ListCell *cell;
1240 37232 : List *result = NIL;
1241 :
1242 : Assert(IsPointerList(list1));
1243 : Assert(IsPointerList(list2));
1244 :
1245 37232 : if (list2 == NIL)
1246 1148 : return list_copy(list1);
1247 :
1248 76932 : foreach(cell, list1)
1249 : {
1250 40848 : if (!list_member(list2, lfirst(cell)))
1251 1544 : result = lappend(result, lfirst(cell));
1252 : }
1253 :
1254 : check_list_invariants(result);
1255 36084 : return result;
1256 : }
1257 :
1258 : /*
1259 : * This variant of list_difference() determines list membership via
1260 : * simple pointer equality.
1261 : */
1262 : List *
1263 21680 : list_difference_ptr(const List *list1, const List *list2)
1264 : {
1265 : const ListCell *cell;
1266 21680 : List *result = NIL;
1267 :
1268 : Assert(IsPointerList(list1));
1269 : Assert(IsPointerList(list2));
1270 :
1271 21680 : if (list2 == NIL)
1272 17192 : return list_copy(list1);
1273 :
1274 11344 : foreach(cell, list1)
1275 : {
1276 6856 : if (!list_member_ptr(list2, lfirst(cell)))
1277 3060 : result = lappend(result, lfirst(cell));
1278 : }
1279 :
1280 : check_list_invariants(result);
1281 4488 : return result;
1282 : }
1283 :
1284 : /*
1285 : * This variant of list_difference() operates upon lists of integers.
1286 : */
1287 : List *
1288 2650 : list_difference_int(const List *list1, const List *list2)
1289 : {
1290 : const ListCell *cell;
1291 2650 : List *result = NIL;
1292 :
1293 : Assert(IsIntegerList(list1));
1294 : Assert(IsIntegerList(list2));
1295 :
1296 2650 : if (list2 == NIL)
1297 1922 : return list_copy(list1);
1298 :
1299 2160 : foreach(cell, list1)
1300 : {
1301 1432 : if (!list_member_int(list2, lfirst_int(cell)))
1302 576 : result = lappend_int(result, lfirst_int(cell));
1303 : }
1304 :
1305 : check_list_invariants(result);
1306 728 : return result;
1307 : }
1308 :
1309 : /*
1310 : * This variant of list_difference() operates upon lists of OIDs.
1311 : */
1312 : List *
1313 404 : list_difference_oid(const List *list1, const List *list2)
1314 : {
1315 : const ListCell *cell;
1316 404 : List *result = NIL;
1317 :
1318 : Assert(IsOidList(list1));
1319 : Assert(IsOidList(list2));
1320 :
1321 404 : if (list2 == NIL)
1322 368 : return list_copy(list1);
1323 :
1324 54 : foreach(cell, list1)
1325 : {
1326 18 : if (!list_member_oid(list2, lfirst_oid(cell)))
1327 6 : result = lappend_oid(result, lfirst_oid(cell));
1328 : }
1329 :
1330 : check_list_invariants(result);
1331 36 : 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 129784 : list_append_unique(List *list, void *datum)
1344 : {
1345 129784 : if (list_member(list, datum))
1346 6260 : return list;
1347 : else
1348 123524 : 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 398648 : list_append_unique_ptr(List *list, void *datum)
1357 : {
1358 398648 : if (list_member_ptr(list, datum))
1359 154682 : return list;
1360 : else
1361 243966 : return lappend(list, datum);
1362 : }
1363 :
1364 : /*
1365 : * This variant of list_append_unique() operates upon lists of integers.
1366 : */
1367 : List *
1368 0 : list_append_unique_int(List *list, int datum)
1369 : {
1370 0 : if (list_member_int(list, datum))
1371 0 : return list;
1372 : else
1373 0 : return lappend_int(list, datum);
1374 : }
1375 :
1376 : /*
1377 : * This variant of list_append_unique() operates upon lists of OIDs.
1378 : */
1379 : List *
1380 6064 : list_append_unique_oid(List *list, Oid datum)
1381 : {
1382 6064 : if (list_member_oid(list, datum))
1383 2266 : return list;
1384 : else
1385 3798 : 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 3094 : list_concat_unique(List *list1, const List *list2)
1406 : {
1407 : ListCell *cell;
1408 :
1409 : Assert(IsPointerList(list1));
1410 : Assert(IsPointerList(list2));
1411 :
1412 5846 : foreach(cell, list2)
1413 : {
1414 2752 : if (!list_member(list1, lfirst(cell)))
1415 2728 : list1 = lappend(list1, lfirst(cell));
1416 : }
1417 :
1418 : check_list_invariants(list1);
1419 3094 : return list1;
1420 : }
1421 :
1422 : /*
1423 : * This variant of list_concat_unique() determines list membership via
1424 : * simple pointer equality.
1425 : */
1426 : List *
1427 1808 : list_concat_unique_ptr(List *list1, const List *list2)
1428 : {
1429 : ListCell *cell;
1430 :
1431 : Assert(IsPointerList(list1));
1432 : Assert(IsPointerList(list2));
1433 :
1434 5902 : foreach(cell, list2)
1435 : {
1436 4094 : if (!list_member_ptr(list1, lfirst(cell)))
1437 1882 : list1 = lappend(list1, lfirst(cell));
1438 : }
1439 :
1440 : check_list_invariants(list1);
1441 1808 : return list1;
1442 : }
1443 :
1444 : /*
1445 : * This variant of list_concat_unique() operates upon lists of integers.
1446 : */
1447 : List *
1448 0 : list_concat_unique_int(List *list1, const List *list2)
1449 : {
1450 : ListCell *cell;
1451 :
1452 : Assert(IsIntegerList(list1));
1453 : Assert(IsIntegerList(list2));
1454 :
1455 0 : foreach(cell, list2)
1456 : {
1457 0 : if (!list_member_int(list1, lfirst_int(cell)))
1458 0 : list1 = lappend_int(list1, lfirst_int(cell));
1459 : }
1460 :
1461 : check_list_invariants(list1);
1462 0 : return list1;
1463 : }
1464 :
1465 : /*
1466 : * This variant of list_concat_unique() operates upon lists of OIDs.
1467 : */
1468 : List *
1469 23326 : list_concat_unique_oid(List *list1, const List *list2)
1470 : {
1471 : ListCell *cell;
1472 :
1473 : Assert(IsOidList(list1));
1474 : Assert(IsOidList(list2));
1475 :
1476 26208 : foreach(cell, list2)
1477 : {
1478 2882 : if (!list_member_oid(list1, lfirst_oid(cell)))
1479 2118 : list1 = lappend_oid(list1, lfirst_oid(cell));
1480 : }
1481 :
1482 : check_list_invariants(list1);
1483 23326 : 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 3038 : list_deduplicate_oid(List *list)
1496 : {
1497 : int len;
1498 :
1499 : Assert(IsOidList(list));
1500 3038 : len = list_length(list);
1501 3038 : if (len > 1)
1502 : {
1503 610 : ListCell *elements = list->elements;
1504 610 : int i = 0;
1505 :
1506 1904 : for (int j = 1; j < len; j++)
1507 : {
1508 1294 : if (elements[i].oid_value != elements[j].oid_value)
1509 1162 : elements[++i].oid_value = elements[j].oid_value;
1510 : }
1511 610 : list->length = i + 1;
1512 : }
1513 : check_list_invariants(list);
1514 3038 : }
1515 :
1516 : /*
1517 : * Free all storage in a list, and optionally the pointed-to elements
1518 : */
1519 : static void
1520 22537948 : list_free_private(List *list, bool deep)
1521 : {
1522 22537948 : if (list == NIL)
1523 16834814 : return; /* nothing to do */
1524 :
1525 : check_list_invariants(list);
1526 :
1527 5703134 : if (deep)
1528 : {
1529 1291122 : for (int i = 0; i < list->length; i++)
1530 982604 : pfree(lfirst(&list->elements[i]));
1531 : }
1532 5703134 : if (list->elements != list->initial_elements)
1533 132088 : pfree(list->elements);
1534 5703134 : 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 21001608 : list_free(List *list)
1547 : {
1548 21001608 : list_free_private(list, false);
1549 21001608 : }
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 1536340 : 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 1536340 : list_free_private(list, true);
1567 1536340 : }
1568 :
1569 : /*
1570 : * Return a shallow copy of the specified list.
1571 : */
1572 : List *
1573 9556412 : list_copy(const List *oldlist)
1574 : {
1575 : List *newlist;
1576 :
1577 9556412 : if (oldlist == NIL)
1578 2050112 : return NIL;
1579 :
1580 7506300 : newlist = new_list(oldlist->type, oldlist->length);
1581 7506300 : memcpy(newlist->elements, oldlist->elements,
1582 7506300 : newlist->length * sizeof(ListCell));
1583 :
1584 : check_list_invariants(newlist);
1585 7506300 : 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 65620 : list_copy_head(const List *oldlist, int len)
1594 : {
1595 : List *newlist;
1596 :
1597 65620 : if (oldlist == NIL || len <= 0)
1598 622 : return NIL;
1599 :
1600 64998 : len = Min(oldlist->length, len);
1601 :
1602 64998 : newlist = new_list(oldlist->type, len);
1603 64998 : memcpy(newlist->elements, oldlist->elements, len * sizeof(ListCell));
1604 :
1605 : check_list_invariants(newlist);
1606 64998 : return newlist;
1607 : }
1608 :
1609 : /*
1610 : * Return a shallow copy of the specified list, without the first N elements.
1611 : */
1612 : List *
1613 94554 : list_copy_tail(const List *oldlist, int nskip)
1614 : {
1615 : List *newlist;
1616 :
1617 94554 : if (nskip < 0)
1618 0 : nskip = 0; /* would it be better to elog? */
1619 :
1620 94554 : if (oldlist == NIL || nskip >= oldlist->length)
1621 1810 : return NIL;
1622 :
1623 92744 : newlist = new_list(oldlist->type, oldlist->length - nskip);
1624 92744 : memcpy(newlist->elements, &oldlist->elements[nskip],
1625 92744 : newlist->length * sizeof(ListCell));
1626 :
1627 : check_list_invariants(newlist);
1628 92744 : 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 19397672 : list_copy_deep(const List *oldlist)
1640 : {
1641 : List *newlist;
1642 :
1643 19397672 : if (oldlist == NIL)
1644 0 : return NIL;
1645 :
1646 : /* This is only sensible for pointer Lists */
1647 : Assert(IsA(oldlist, List));
1648 :
1649 19397672 : newlist = new_list(oldlist->type, oldlist->length);
1650 76407894 : for (int i = 0; i < newlist->length; i++)
1651 57010222 : lfirst(&newlist->elements[i]) =
1652 57010238 : copyObjectImpl(lfirst(&oldlist->elements[i]));
1653 :
1654 : check_list_invariants(newlist);
1655 19397656 : 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 414636 : 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 414636 : len = list_length(list);
1683 414636 : if (len > 1)
1684 132202 : qsort(list->elements, len, sizeof(ListCell), (qsort_comparator) cmp);
1685 414636 : }
1686 :
1687 : /*
1688 : * list_sort comparator for sorting a list into ascending int order.
1689 : */
1690 : int
1691 96 : list_int_cmp(const ListCell *p1, const ListCell *p2)
1692 : {
1693 96 : int v1 = lfirst_int(p1);
1694 96 : int v2 = lfirst_int(p2);
1695 :
1696 96 : 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 170620 : list_oid_cmp(const ListCell *p1, const ListCell *p2)
1704 : {
1705 170620 : Oid v1 = lfirst_oid(p1);
1706 170620 : Oid v2 = lfirst_oid(p2);
1707 :
1708 170620 : return pg_cmp_u32(v1, v2);
1709 : }
|
