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-2026, 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 64836717 : 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 64836717 : max_size = pg_nextpower2_32(Max(8, min_size + LIST_HEADER_OVERHEAD));
127 64836717 : 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 64836717 : newlist = (List *) palloc(offsetof(List, initial_elements) +
138 : max_size * sizeof(ListCell));
139 64836717 : newlist->type = type;
140 64836717 : newlist->length = min_size;
141 64836717 : newlist->max_length = max_size;
142 64836717 : newlist->elements = newlist->initial_elements;
143 :
144 64836717 : 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 3379837 : 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 3379837 : 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 3379837 : 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 2113082 : list->elements = (ListCell *)
186 2113082 : MemoryContextAlloc(GetMemoryChunkContext(list),
187 : new_max_len * sizeof(ListCell));
188 2113082 : memcpy(list->elements, list->initial_elements,
189 2113082 : 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 1266755 : 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 3379837 : list->max_length = new_max_len;
229 3379837 : }
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 7354408 : list_make1_impl(NodeTag t, ListCell datum1)
237 : {
238 7354408 : List *list = new_list(t, 1);
239 :
240 7354408 : list->elements[0] = datum1;
241 : check_list_invariants(list);
242 7354408 : return list;
243 : }
244 :
245 : List *
246 903802 : list_make2_impl(NodeTag t, ListCell datum1, ListCell datum2)
247 : {
248 903802 : List *list = new_list(t, 2);
249 :
250 903802 : list->elements[0] = datum1;
251 903802 : list->elements[1] = datum2;
252 : check_list_invariants(list);
253 903802 : return list;
254 : }
255 :
256 : List *
257 3434 : list_make3_impl(NodeTag t, ListCell datum1, ListCell datum2,
258 : ListCell datum3)
259 : {
260 3434 : List *list = new_list(t, 3);
261 :
262 3434 : list->elements[0] = datum1;
263 3434 : list->elements[1] = datum2;
264 3434 : list->elements[2] = datum3;
265 : check_list_invariants(list);
266 3434 : return list;
267 : }
268 :
269 : List *
270 121 : list_make4_impl(NodeTag t, ListCell datum1, ListCell datum2,
271 : ListCell datum3, ListCell datum4)
272 : {
273 121 : List *list = new_list(t, 4);
274 :
275 121 : list->elements[0] = datum1;
276 121 : list->elements[1] = datum2;
277 121 : list->elements[2] = datum3;
278 121 : list->elements[3] = datum4;
279 : check_list_invariants(list);
280 121 : return list;
281 : }
282 :
283 : List *
284 170 : list_make5_impl(NodeTag t, ListCell datum1, ListCell datum2,
285 : ListCell datum3, ListCell datum4, ListCell datum5)
286 : {
287 170 : List *list = new_list(t, 5);
288 :
289 170 : list->elements[0] = datum1;
290 170 : list->elements[1] = datum2;
291 170 : list->elements[2] = datum3;
292 170 : list->elements[3] = datum4;
293 170 : list->elements[4] = datum5;
294 : check_list_invariants(list);
295 170 : 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 1753414 : new_head_cell(List *list)
306 : {
307 : /* Enlarge array if necessary */
308 1753414 : if (list->length >= list->max_length)
309 30538 : enlarge_list(list, list->length + 1);
310 : /* Now shove the existing data over */
311 1753414 : memmove(&list->elements[1], &list->elements[0],
312 1753414 : list->length * sizeof(ListCell));
313 1753414 : list->length++;
314 1753414 : }
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 54733485 : new_tail_cell(List *list)
324 : {
325 : /* Enlarge array if necessary */
326 54733485 : if (list->length >= list->max_length)
327 3334936 : enlarge_list(list, list->length + 1);
328 54733485 : list->length++;
329 54733485 : }
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 81285605 : lappend(List *list, void *datum)
340 : {
341 : Assert(IsPointerList(list));
342 :
343 81285605 : if (list == NIL)
344 32796883 : list = new_list(T_List, 1);
345 : else
346 48488722 : new_tail_cell(list);
347 :
348 81285605 : llast(list) = datum;
349 : check_list_invariants(list);
350 81285605 : return list;
351 : }
352 :
353 : /*
354 : * Append an integer to the specified list. See lappend()
355 : */
356 : List *
357 5988744 : lappend_int(List *list, int datum)
358 : {
359 : Assert(IsIntegerList(list));
360 :
361 5988744 : if (list == NIL)
362 1078719 : list = new_list(T_IntList, 1);
363 : else
364 4910025 : new_tail_cell(list);
365 :
366 5988744 : llast_int(list) = datum;
367 : check_list_invariants(list);
368 5988744 : return list;
369 : }
370 :
371 : /*
372 : * Append an OID to the specified list. See lappend()
373 : */
374 : List *
375 4223325 : lappend_oid(List *list, Oid datum)
376 : {
377 : Assert(IsOidList(list));
378 :
379 4223325 : if (list == NIL)
380 2888620 : list = new_list(T_OidList, 1);
381 : else
382 1334705 : new_tail_cell(list);
383 :
384 4223325 : llast_oid(list) = datum;
385 : check_list_invariants(list);
386 4223325 : return list;
387 : }
388 :
389 : /*
390 : * Append a TransactionId to the specified list. See lappend()
391 : */
392 : List *
393 90 : lappend_xid(List *list, TransactionId datum)
394 : {
395 : Assert(IsXidList(list));
396 :
397 90 : if (list == NIL)
398 57 : list = new_list(T_XidList, 1);
399 : else
400 33 : new_tail_cell(list);
401 :
402 90 : llast_xid(list) = datum;
403 : check_list_invariants(list);
404 90 : 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 542806 : insert_new_cell(List *list, int pos)
416 : {
417 : Assert(pos >= 0 && pos <= list->length);
418 :
419 : /* Enlarge array if necessary */
420 542806 : if (list->length >= list->max_length)
421 1245 : enlarge_list(list, list->length + 1);
422 : /* Now shove the existing data over */
423 542806 : if (pos < list->length)
424 235760 : memmove(&list->elements[pos + 1], &list->elements[pos],
425 235760 : (list->length - pos) * sizeof(ListCell));
426 542806 : list->length++;
427 :
428 542806 : 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 1726835 : list_insert_nth(List *list, int pos, void *datum)
440 : {
441 1726835 : if (list == NIL)
442 : {
443 : Assert(pos == 0);
444 1184029 : return list_make1(datum);
445 : }
446 : Assert(IsPointerList(list));
447 542806 : lfirst(insert_new_cell(list, pos)) = datum;
448 : check_list_invariants(list);
449 542806 : 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 4167071 : lcons(void *datum, List *list)
496 : {
497 : Assert(IsPointerList(list));
498 :
499 4167071 : if (list == NIL)
500 2444185 : list = new_list(T_List, 1);
501 : else
502 1722886 : new_head_cell(list);
503 :
504 4167071 : linitial(list) = datum;
505 : check_list_invariants(list);
506 4167071 : return list;
507 : }
508 :
509 : /*
510 : * Prepend an integer to the list. See lcons()
511 : */
512 : List *
513 12595 : lcons_int(int datum, List *list)
514 : {
515 : Assert(IsIntegerList(list));
516 :
517 12595 : if (list == NIL)
518 5569 : list = new_list(T_IntList, 1);
519 : else
520 7026 : new_head_cell(list);
521 :
522 12595 : linitial_int(list) = datum;
523 : check_list_invariants(list);
524 12595 : return list;
525 : }
526 :
527 : /*
528 : * Prepend an OID to the list. See lcons()
529 : */
530 : List *
531 26121 : lcons_oid(Oid datum, List *list)
532 : {
533 : Assert(IsOidList(list));
534 :
535 26121 : if (list == NIL)
536 2619 : list = new_list(T_OidList, 1);
537 : else
538 23502 : new_head_cell(list);
539 :
540 26121 : linitial_oid(list) = datum;
541 : check_list_invariants(list);
542 26121 : 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 3941236 : list_concat(List *list1, const List *list2)
562 : {
563 : int new_len;
564 :
565 3941236 : if (list1 == NIL)
566 2866379 : return list_copy(list2);
567 1074857 : if (list2 == NIL)
568 629130 : return list1;
569 :
570 : Assert(list1->type == list2->type);
571 :
572 445727 : new_len = list1->length + list2->length;
573 : /* Enlarge array if necessary */
574 445727 : if (new_len > list1->max_length)
575 13118 : enlarge_list(list1, new_len);
576 :
577 : /* Even if list1 == list2, using memcpy should be safe here */
578 445727 : memcpy(&list1->elements[list1->length], &list2->elements[0],
579 445727 : list2->length * sizeof(ListCell));
580 445727 : list1->length = new_len;
581 :
582 : check_list_invariants(list1);
583 445727 : 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 629379 : list_concat_copy(const List *list1, const List *list2)
599 : {
600 : List *result;
601 : int new_len;
602 :
603 629379 : if (list1 == NIL)
604 277058 : return list_copy(list2);
605 352321 : if (list2 == NIL)
606 293676 : return list_copy(list1);
607 :
608 : Assert(list1->type == list2->type);
609 :
610 58645 : new_len = list1->length + list2->length;
611 58645 : result = new_list(list1->type, new_len);
612 58645 : memcpy(result->elements, list1->elements,
613 58645 : list1->length * sizeof(ListCell));
614 58645 : memcpy(result->elements + list1->length, list2->elements,
615 58645 : list2->length * sizeof(ListCell));
616 :
617 : check_list_invariants(result);
618 58645 : 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 413129 : list_truncate(List *list, int new_size)
632 : {
633 413129 : if (new_size <= 0)
634 48830 : return NIL; /* truncate to zero length */
635 :
636 : /* If asked to effectively extend the list, do nothing */
637 364299 : if (new_size < list_length(list))
638 73228 : 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 364299 : 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 654902 : 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 1202929 : foreach(cell, list)
669 : {
670 612884 : if (equal(lfirst(cell), datum))
671 64857 : return true;
672 : }
673 :
674 590045 : 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 351047 : 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 559231 : foreach(cell, list)
690 : {
691 340889 : if (lfirst(cell) == datum)
692 132705 : return true;
693 : }
694 :
695 218342 : return false;
696 : }
697 :
698 : /*
699 : * Return true iff the integer 'datum' is a member of the list.
700 : */
701 : bool
702 71520 : 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 5012441 : foreach(cell, list)
710 : {
711 4952421 : if (lfirst_int(cell) == datum)
712 11500 : return true;
713 : }
714 :
715 60020 : return false;
716 : }
717 :
718 : /*
719 : * Return true iff the OID 'datum' is a member of the list.
720 : */
721 : bool
722 49125411 : 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 51839314 : foreach(cell, list)
730 : {
731 3410026 : if (lfirst_oid(cell) == datum)
732 696123 : return true;
733 : }
734 :
735 48429288 : return false;
736 : }
737 :
738 : /*
739 : * Return true iff the TransactionId 'datum' is a member of the list.
740 : */
741 : bool
742 175995 : 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 216865 : foreach(cell, list)
750 : {
751 216775 : if (lfirst_xid(cell) == datum)
752 175905 : return true;
753 : }
754 :
755 90 : 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 2130936 : 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 2130936 : if (list->length == 1)
779 : {
780 1077713 : list_free(list);
781 1077713 : 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 1053223 : memmove(&list->elements[n], &list->elements[n + 1],
792 1053223 : (list->length - 1 - n) * sizeof(ListCell));
793 1053223 : 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 1053223 : 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 1135504 : list_delete_cell(List *list, ListCell *cell)
842 : {
843 1135504 : 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 3251 : list_delete(List *list, void *datum)
854 : {
855 : ListCell *cell;
856 :
857 : Assert(IsPointerList(list));
858 : check_list_invariants(list);
859 :
860 3418 : foreach(cell, list)
861 : {
862 3415 : if (equal(lfirst(cell), datum))
863 3248 : return list_delete_cell(list, cell);
864 : }
865 :
866 : /* Didn't find a match: return the list unmodified */
867 3 : return list;
868 : }
869 :
870 : /* As above, but use simple pointer equality */
871 : List *
872 1124629 : list_delete_ptr(List *list, void *datum)
873 : {
874 : ListCell *cell;
875 :
876 : Assert(IsPointerList(list));
877 : check_list_invariants(list);
878 :
879 1124858 : foreach(cell, list)
880 : {
881 1124858 : if (lfirst(cell) == datum)
882 1124629 : 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 88 : list_delete_int(List *list, int datum)
892 : {
893 : ListCell *cell;
894 :
895 : Assert(IsIntegerList(list));
896 : check_list_invariants(list);
897 :
898 91 : foreach(cell, list)
899 : {
900 91 : if (lfirst_int(cell) == datum)
901 88 : 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 3918 : list_delete_oid(List *list, Oid datum)
911 : {
912 : ListCell *cell;
913 :
914 : Assert(IsOidList(list));
915 : check_list_invariants(list);
916 :
917 3918 : foreach(cell, list)
918 : {
919 826 : if (lfirst_oid(cell) == datum)
920 826 : return list_delete_cell(list, cell);
921 : }
922 :
923 : /* Didn't find a match: return the list unmodified */
924 3092 : 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 445354 : list_delete_first(List *list)
944 : {
945 : check_list_invariants(list);
946 :
947 445354 : if (list == NIL)
948 0 : return NIL; /* would an error be better? */
949 :
950 445354 : return list_delete_nth_cell(list, 0);
951 : }
952 :
953 : /*
954 : * Delete the last element of the list.
955 : */
956 : List *
957 29019 : list_delete_last(List *list)
958 : {
959 : check_list_invariants(list);
960 :
961 29019 : 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 29019 : if (list_length(list) <= 1)
966 : {
967 13617 : list_free(list);
968 13617 : return NIL;
969 : }
970 :
971 15402 : 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 382 : list_delete_first_n(List *list, int n)
984 : {
985 : check_list_invariants(list);
986 :
987 : /* No-op request? */
988 382 : if (n <= 0)
989 12 : return list;
990 :
991 : /* Delete whole list? */
992 370 : 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 370 : memmove(&list->elements[0], &list->elements[n],
1006 370 : (list->length - n) * sizeof(ListCell));
1007 370 : 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 370 : 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 6886 : 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 6886 : result = list_copy(list1);
1075 14086 : foreach(cell, list2)
1076 : {
1077 7200 : if (!list_member(result, lfirst(cell)))
1078 7153 : result = lappend(result, lfirst(cell));
1079 : }
1080 :
1081 : check_list_invariants(result);
1082 6886 : 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 3371 : 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 3371 : result = list_copy(list1);
1122 6709 : foreach(cell, list2)
1123 : {
1124 3338 : if (!list_member_int(result, lfirst_int(cell)))
1125 3220 : result = lappend_int(result, lfirst_int(cell));
1126 : }
1127 :
1128 : check_list_invariants(result);
1129 3371 : 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 233 : list_intersection_int(const List *list1, const List *list2)
1201 : {
1202 : List *result;
1203 : const ListCell *cell;
1204 :
1205 233 : if (list1 == NIL || list2 == NIL)
1206 0 : return NIL;
1207 :
1208 : Assert(IsIntegerList(list1));
1209 : Assert(IsIntegerList(list2));
1210 :
1211 233 : result = NIL;
1212 490 : foreach(cell, list1)
1213 : {
1214 257 : if (list_member_int(list2, lfirst_int(cell)))
1215 117 : result = lappend_int(result, lfirst_int(cell));
1216 : }
1217 :
1218 : check_list_invariants(result);
1219 233 : 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 26342 : list_difference(const List *list1, const List *list2)
1238 : {
1239 : const ListCell *cell;
1240 26342 : List *result = NIL;
1241 :
1242 : Assert(IsPointerList(list1));
1243 : Assert(IsPointerList(list2));
1244 :
1245 26342 : if (list2 == NIL)
1246 824 : return list_copy(list1);
1247 :
1248 54417 : foreach(cell, list1)
1249 : {
1250 28899 : if (!list_member(list2, lfirst(cell)))
1251 1046 : result = lappend(result, lfirst(cell));
1252 : }
1253 :
1254 : check_list_invariants(result);
1255 25518 : return result;
1256 : }
1257 :
1258 : /*
1259 : * This variant of list_difference() determines list membership via
1260 : * simple pointer equality.
1261 : */
1262 : List *
1263 14561 : list_difference_ptr(const List *list1, const List *list2)
1264 : {
1265 : const ListCell *cell;
1266 14561 : List *result = NIL;
1267 :
1268 : Assert(IsPointerList(list1));
1269 : Assert(IsPointerList(list2));
1270 :
1271 14561 : if (list2 == NIL)
1272 11744 : return list_copy(list1);
1273 :
1274 6858 : foreach(cell, list1)
1275 : {
1276 4041 : if (!list_member_ptr(list2, lfirst(cell)))
1277 2029 : result = lappend(result, lfirst(cell));
1278 : }
1279 :
1280 : check_list_invariants(result);
1281 2817 : return result;
1282 : }
1283 :
1284 : /*
1285 : * This variant of list_difference() operates upon lists of integers.
1286 : */
1287 : List *
1288 1521 : list_difference_int(const List *list1, const List *list2)
1289 : {
1290 : const ListCell *cell;
1291 1521 : List *result = NIL;
1292 :
1293 : Assert(IsIntegerList(list1));
1294 : Assert(IsIntegerList(list2));
1295 :
1296 1521 : if (list2 == NIL)
1297 1145 : return list_copy(list1);
1298 :
1299 1116 : foreach(cell, list1)
1300 : {
1301 740 : if (!list_member_int(list2, lfirst_int(cell)))
1302 300 : result = lappend_int(result, lfirst_int(cell));
1303 : }
1304 :
1305 : check_list_invariants(result);
1306 376 : return result;
1307 : }
1308 :
1309 : /*
1310 : * This variant of list_difference() operates upon lists of OIDs.
1311 : */
1312 : List *
1313 4833 : list_difference_oid(const List *list1, const List *list2)
1314 : {
1315 : const ListCell *cell;
1316 4833 : List *result = NIL;
1317 :
1318 : Assert(IsOidList(list1));
1319 : Assert(IsOidList(list2));
1320 :
1321 4833 : if (list2 == NIL)
1322 4815 : return list_copy(list1);
1323 :
1324 27 : foreach(cell, list1)
1325 : {
1326 9 : if (!list_member_oid(list2, lfirst_oid(cell)))
1327 3 : result = lappend_oid(result, lfirst_oid(cell));
1328 : }
1329 :
1330 : check_list_invariants(result);
1331 18 : 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 100526 : list_append_unique(List *list, void *datum)
1344 : {
1345 100526 : if (list_member(list, datum))
1346 7765 : return list;
1347 : else
1348 92761 : 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 295806 : list_append_unique_ptr(List *list, void *datum)
1357 : {
1358 295806 : if (list_member_ptr(list, datum))
1359 115226 : return list;
1360 : else
1361 180580 : 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 3131 : list_append_unique_oid(List *list, Oid datum)
1381 : {
1382 3131 : if (list_member_oid(list, datum))
1383 1124 : return list;
1384 : else
1385 2007 : 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 1939 : list_concat_unique(List *list1, const List *list2)
1406 : {
1407 : ListCell *cell;
1408 :
1409 : Assert(IsPointerList(list1));
1410 : Assert(IsPointerList(list2));
1411 :
1412 3583 : foreach(cell, list2)
1413 : {
1414 1644 : if (!list_member(list1, lfirst(cell)))
1415 1626 : list1 = lappend(list1, lfirst(cell));
1416 : }
1417 :
1418 : check_list_invariants(list1);
1419 1939 : return list1;
1420 : }
1421 :
1422 : /*
1423 : * This variant of list_concat_unique() determines list membership via
1424 : * simple pointer equality.
1425 : */
1426 : List *
1427 1383 : list_concat_unique_ptr(List *list1, const List *list2)
1428 : {
1429 : ListCell *cell;
1430 :
1431 : Assert(IsPointerList(list1));
1432 : Assert(IsPointerList(list2));
1433 :
1434 4662 : foreach(cell, list2)
1435 : {
1436 3279 : if (!list_member_ptr(list1, lfirst(cell)))
1437 1694 : list1 = lappend(list1, lfirst(cell));
1438 : }
1439 :
1440 : check_list_invariants(list1);
1441 1383 : 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 13600 : list_concat_unique_oid(List *list1, const List *list2)
1470 : {
1471 : ListCell *cell;
1472 :
1473 : Assert(IsOidList(list1));
1474 : Assert(IsOidList(list2));
1475 :
1476 15149 : foreach(cell, list2)
1477 : {
1478 1549 : if (!list_member_oid(list1, lfirst_oid(cell)))
1479 1167 : list1 = lappend_oid(list1, lfirst_oid(cell));
1480 : }
1481 :
1482 : check_list_invariants(list1);
1483 13600 : 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 1879 : list_deduplicate_oid(List *list)
1496 : {
1497 : int len;
1498 :
1499 : Assert(IsOidList(list));
1500 1879 : len = list_length(list);
1501 1879 : if (len > 1)
1502 : {
1503 331 : ListCell *elements = list->elements;
1504 331 : int i = 0;
1505 :
1506 1014 : for (int j = 1; j < len; j++)
1507 : {
1508 683 : if (elements[i].oid_value != elements[j].oid_value)
1509 615 : elements[++i].oid_value = elements[j].oid_value;
1510 : }
1511 331 : list->length = i + 1;
1512 : }
1513 : check_list_invariants(list);
1514 1879 : }
1515 :
1516 : /*
1517 : * Free all storage in a list, and optionally the pointed-to elements
1518 : */
1519 : static void
1520 12954434 : list_free_private(List *list, bool deep)
1521 : {
1522 12954434 : if (list == NIL)
1523 9451627 : return; /* nothing to do */
1524 :
1525 : check_list_invariants(list);
1526 :
1527 3502807 : if (deep)
1528 : {
1529 818699 : for (int i = 0; i < list->length; i++)
1530 625905 : pfree(lfirst(&list->elements[i]));
1531 : }
1532 3502807 : if (list->elements != list->initial_elements)
1533 83101 : pfree(list->elements);
1534 3502807 : 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 11987127 : list_free(List *list)
1547 : {
1548 11987127 : list_free_private(list, false);
1549 11987127 : }
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 967307 : 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 967307 : list_free_private(list, true);
1567 967307 : }
1568 :
1569 : /*
1570 : * Return a shallow copy of the specified list.
1571 : */
1572 : List *
1573 6566698 : list_copy(const List *oldlist)
1574 : {
1575 : List *newlist;
1576 :
1577 6566698 : if (oldlist == NIL)
1578 1402429 : return NIL;
1579 :
1580 5164269 : newlist = new_list(oldlist->type, oldlist->length);
1581 5164269 : memcpy(newlist->elements, oldlist->elements,
1582 5164269 : newlist->length * sizeof(ListCell));
1583 :
1584 : check_list_invariants(newlist);
1585 5164269 : 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 671840 : list_copy_head(const List *oldlist, int len)
1594 : {
1595 : List *newlist;
1596 :
1597 671840 : if (oldlist == NIL || len <= 0)
1598 617048 : return NIL;
1599 :
1600 54792 : len = Min(oldlist->length, len);
1601 :
1602 54792 : newlist = new_list(oldlist->type, len);
1603 54792 : memcpy(newlist->elements, oldlist->elements, len * sizeof(ListCell));
1604 :
1605 : check_list_invariants(newlist);
1606 54792 : return newlist;
1607 : }
1608 :
1609 : /*
1610 : * Return a shallow copy of the specified list, without the first N elements.
1611 : */
1612 : List *
1613 59210 : list_copy_tail(const List *oldlist, int nskip)
1614 : {
1615 : List *newlist;
1616 :
1617 59210 : if (nskip < 0)
1618 0 : nskip = 0; /* would it be better to elog? */
1619 :
1620 59210 : if (oldlist == NIL || nskip >= oldlist->length)
1621 1123 : return NIL;
1622 :
1623 58087 : newlist = new_list(oldlist->type, oldlist->length - nskip);
1624 58087 : memcpy(newlist->elements, &oldlist->elements[nskip],
1625 58087 : newlist->length * sizeof(ListCell));
1626 :
1627 : check_list_invariants(newlist);
1628 58087 : 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 12022337 : list_copy_deep(const List *oldlist)
1640 : {
1641 : List *newlist;
1642 :
1643 12022337 : if (oldlist == NIL)
1644 0 : return NIL;
1645 :
1646 : /* This is only sensible for pointer Lists */
1647 : Assert(IsA(oldlist, List));
1648 :
1649 12022337 : newlist = new_list(oldlist->type, oldlist->length);
1650 51173711 : for (int i = 0; i < newlist->length; i++)
1651 39151374 : lfirst(&newlist->elements[i]) =
1652 39151374 : copyObjectImpl(lfirst(&oldlist->elements[i]));
1653 :
1654 : check_list_invariants(newlist);
1655 12022337 : 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 305848 : 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 305848 : len = list_length(list);
1683 305848 : if (len > 1)
1684 106645 : qsort(list->elements, len, sizeof(ListCell), (qsort_comparator) cmp);
1685 305848 : }
1686 :
1687 : /*
1688 : * list_sort comparator for sorting a list into ascending int order.
1689 : */
1690 : int
1691 48 : list_int_cmp(const ListCell *p1, const ListCell *p2)
1692 : {
1693 48 : int v1 = lfirst_int(p1);
1694 48 : int v2 = lfirst_int(p2);
1695 :
1696 48 : 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 134064 : list_oid_cmp(const ListCell *p1, const ListCell *p2)
1704 : {
1705 134064 : Oid v1 = lfirst_oid(p1);
1706 134064 : Oid v2 = lfirst_oid(p2);
1707 :
1708 134064 : return pg_cmp_u32(v1, v2);
1709 : }
|
