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-2024, 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 95571084 : 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 95571084 : max_size = pg_nextpower2_32(Max(8, min_size + LIST_HEADER_OVERHEAD));
127 95571084 : 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 95571084 : newlist = (List *) palloc(offsetof(List, initial_elements) +
138 : max_size * sizeof(ListCell));
139 95571084 : newlist->type = type;
140 95571084 : newlist->length = min_size;
141 95571084 : newlist->max_length = max_size;
142 95571084 : newlist->elements = newlist->initial_elements;
143 :
144 95571084 : 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 4973822 : 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 4973822 : 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 4973822 : 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 3010022 : list->elements = (ListCell *)
186 3010022 : MemoryContextAlloc(GetMemoryChunkContext(list),
187 : new_max_len * sizeof(ListCell));
188 3010022 : memcpy(list->elements, list->initial_elements,
189 3010022 : 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 1963800 : 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 4973822 : list->max_length = new_max_len;
229 4973822 : }
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 11507556 : list_make1_impl(NodeTag t, ListCell datum1)
237 : {
238 11507556 : List *list = new_list(t, 1);
239 :
240 11507556 : list->elements[0] = datum1;
241 : check_list_invariants(list);
242 11507556 : return list;
243 : }
244 :
245 : List *
246 1343978 : list_make2_impl(NodeTag t, ListCell datum1, ListCell datum2)
247 : {
248 1343978 : List *list = new_list(t, 2);
249 :
250 1343978 : list->elements[0] = datum1;
251 1343978 : list->elements[1] = datum2;
252 : check_list_invariants(list);
253 1343978 : return list;
254 : }
255 :
256 : List *
257 5624 : list_make3_impl(NodeTag t, ListCell datum1, ListCell datum2,
258 : ListCell datum3)
259 : {
260 5624 : List *list = new_list(t, 3);
261 :
262 5624 : list->elements[0] = datum1;
263 5624 : list->elements[1] = datum2;
264 5624 : list->elements[2] = datum3;
265 : check_list_invariants(list);
266 5624 : 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 306 : list_make5_impl(NodeTag t, ListCell datum1, ListCell datum2,
285 : ListCell datum3, ListCell datum4, ListCell datum5)
286 : {
287 306 : List *list = new_list(t, 5);
288 :
289 306 : list->elements[0] = datum1;
290 306 : list->elements[1] = datum2;
291 306 : list->elements[2] = datum3;
292 306 : list->elements[3] = datum4;
293 306 : list->elements[4] = datum5;
294 : check_list_invariants(list);
295 306 : 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 2590892 : new_head_cell(List *list)
306 : {
307 : /* Enlarge array if necessary */
308 2590892 : if (list->length >= list->max_length)
309 45882 : enlarge_list(list, list->length + 1);
310 : /* Now shove the existing data over */
311 2590892 : memmove(&list->elements[1], &list->elements[0],
312 2590892 : list->length * sizeof(ListCell));
313 2590892 : list->length++;
314 2590892 : }
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 81603412 : new_tail_cell(List *list)
324 : {
325 : /* Enlarge array if necessary */
326 81603412 : if (list->length >= list->max_length)
327 4906124 : enlarge_list(list, list->length + 1);
328 81603412 : list->length++;
329 81603412 : }
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 120558688 : lappend(List *list, void *datum)
340 : {
341 : Assert(IsPointerList(list));
342 :
343 120558688 : if (list == NIL)
344 48174608 : list = new_list(T_List, 1);
345 : else
346 72384080 : new_tail_cell(list);
347 :
348 120558688 : llast(list) = datum;
349 : check_list_invariants(list);
350 120558688 : return list;
351 : }
352 :
353 : /*
354 : * Append an integer to the specified list. See lappend()
355 : */
356 : List *
357 9109176 : lappend_int(List *list, int datum)
358 : {
359 : Assert(IsIntegerList(list));
360 :
361 9109176 : if (list == NIL)
362 1475470 : list = new_list(T_IntList, 1);
363 : else
364 7633706 : new_tail_cell(list);
365 :
366 9109176 : llast_int(list) = datum;
367 : check_list_invariants(list);
368 9109176 : return list;
369 : }
370 :
371 : /*
372 : * Append an OID to the specified list. See lappend()
373 : */
374 : List *
375 5381724 : lappend_oid(List *list, Oid datum)
376 : {
377 : Assert(IsOidList(list));
378 :
379 5381724 : if (list == NIL)
380 3796164 : list = new_list(T_OidList, 1);
381 : else
382 1585560 : new_tail_cell(list);
383 :
384 5381724 : llast_oid(list) = datum;
385 : check_list_invariants(list);
386 5381724 : return list;
387 : }
388 :
389 : /*
390 : * Append a TransactionId to the specified list. See lappend()
391 : */
392 : List *
393 178 : lappend_xid(List *list, TransactionId datum)
394 : {
395 : Assert(IsXidList(list));
396 :
397 178 : if (list == NIL)
398 112 : list = new_list(T_XidList, 1);
399 : else
400 66 : new_tail_cell(list);
401 :
402 178 : llast_xid(list) = datum;
403 : check_list_invariants(list);
404 178 : 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 638126 : insert_new_cell(List *list, int pos)
416 : {
417 : Assert(pos >= 0 && pos <= list->length);
418 :
419 : /* Enlarge array if necessary */
420 638126 : if (list->length >= list->max_length)
421 1258 : enlarge_list(list, list->length + 1);
422 : /* Now shove the existing data over */
423 638126 : if (pos < list->length)
424 271528 : memmove(&list->elements[pos + 1], &list->elements[pos],
425 271528 : (list->length - pos) * sizeof(ListCell));
426 638126 : list->length++;
427 :
428 638126 : 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 2422724 : list_insert_nth(List *list, int pos, void *datum)
440 : {
441 2422724 : if (list == NIL)
442 : {
443 : Assert(pos == 0);
444 1784598 : return list_make1(datum);
445 : }
446 : Assert(IsPointerList(list));
447 638126 : lfirst(insert_new_cell(list, pos)) = datum;
448 : check_list_invariants(list);
449 638126 : 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 6567454 : lcons(void *datum, List *list)
496 : {
497 : Assert(IsPointerList(list));
498 :
499 6567454 : if (list == NIL)
500 4013772 : list = new_list(T_List, 1);
501 : else
502 2553682 : new_head_cell(list);
503 :
504 6567454 : linitial(list) = datum;
505 : check_list_invariants(list);
506 6567454 : return list;
507 : }
508 :
509 : /*
510 : * Prepend an integer to the list. See lcons()
511 : */
512 : List *
513 12506 : lcons_int(int datum, List *list)
514 : {
515 : Assert(IsIntegerList(list));
516 :
517 12506 : if (list == NIL)
518 5828 : list = new_list(T_IntList, 1);
519 : else
520 6678 : new_head_cell(list);
521 :
522 12506 : linitial_int(list) = datum;
523 : check_list_invariants(list);
524 12506 : return list;
525 : }
526 :
527 : /*
528 : * Prepend an OID to the list. See lcons()
529 : */
530 : List *
531 34652 : lcons_oid(Oid datum, List *list)
532 : {
533 : Assert(IsOidList(list));
534 :
535 34652 : if (list == NIL)
536 4120 : list = new_list(T_OidList, 1);
537 : else
538 30532 : new_head_cell(list);
539 :
540 34652 : linitial_oid(list) = datum;
541 : check_list_invariants(list);
542 34652 : 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 4845716 : list_concat(List *list1, const List *list2)
562 : {
563 : int new_len;
564 :
565 4845716 : if (list1 == NIL)
566 3423654 : return list_copy(list2);
567 1422062 : if (list2 == NIL)
568 859762 : return list1;
569 :
570 : Assert(list1->type == list2->type);
571 :
572 562300 : new_len = list1->length + list2->length;
573 : /* Enlarge array if necessary */
574 562300 : if (new_len > list1->max_length)
575 20558 : enlarge_list(list1, new_len);
576 :
577 : /* Even if list1 == list2, using memcpy should be safe here */
578 562300 : memcpy(&list1->elements[list1->length], &list2->elements[0],
579 562300 : list2->length * sizeof(ListCell));
580 562300 : list1->length = new_len;
581 :
582 : check_list_invariants(list1);
583 562300 : 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 869668 : list_concat_copy(const List *list1, const List *list2)
599 : {
600 : List *result;
601 : int new_len;
602 :
603 869668 : if (list1 == NIL)
604 398554 : return list_copy(list2);
605 471114 : if (list2 == NIL)
606 399156 : return list_copy(list1);
607 :
608 : Assert(list1->type == list2->type);
609 :
610 71958 : new_len = list1->length + list2->length;
611 71958 : result = new_list(list1->type, new_len);
612 71958 : memcpy(result->elements, list1->elements,
613 71958 : list1->length * sizeof(ListCell));
614 71958 : memcpy(result->elements + list1->length, list2->elements,
615 71958 : list2->length * sizeof(ListCell));
616 :
617 : check_list_invariants(result);
618 71958 : 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 494668 : list_truncate(List *list, int new_size)
632 : {
633 494668 : if (new_size <= 0)
634 74314 : return NIL; /* truncate to zero length */
635 :
636 : /* If asked to effectively extend the list, do nothing */
637 420354 : if (new_size < list_length(list))
638 88590 : 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 420354 : 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 799078 : 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 938576 : foreach(cell, list)
669 : {
670 216690 : if (equal(lfirst(cell), datum))
671 77192 : return true;
672 : }
673 :
674 721886 : 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 466502 : 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 648680 : foreach(cell, list)
690 : {
691 369742 : if (lfirst(cell) == datum)
692 187564 : return true;
693 : }
694 :
695 278938 : return false;
696 : }
697 :
698 : /*
699 : * Return true iff the integer 'datum' is a member of the list.
700 : */
701 : bool
702 111958 : 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 9943444 : foreach(cell, list)
710 : {
711 9849444 : if (lfirst_int(cell) == datum)
712 17958 : return true;
713 : }
714 :
715 94000 : return false;
716 : }
717 :
718 : /*
719 : * Return true iff the OID 'datum' is a member of the list.
720 : */
721 : bool
722 70403320 : 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 73236418 : foreach(cell, list)
730 : {
731 3618542 : if (lfirst_oid(cell) == datum)
732 785444 : return true;
733 : }
734 :
735 69617876 : 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 433548 : if (lfirst_xid(cell) == datum)
752 351808 : return true;
753 : }
754 :
755 178 : 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 3224452 : 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 3224452 : if (list->length == 1)
779 : {
780 1824024 : list_free(list);
781 1824024 : 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 1400428 : memmove(&list->elements[n], &list->elements[n + 1],
792 1400428 : (list->length - 1 - n) * sizeof(ListCell));
793 1400428 : 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 1400428 : 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 1934318 : list_delete_cell(List *list, ListCell *cell)
842 : {
843 1934318 : 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 276 : list_delete(List *list, void *datum)
854 : {
855 : ListCell *cell;
856 :
857 : Assert(IsPointerList(list));
858 : check_list_invariants(list);
859 :
860 282 : foreach(cell, list)
861 : {
862 276 : if (equal(lfirst(cell), datum))
863 270 : 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 1923268 : list_delete_ptr(List *list, void *datum)
873 : {
874 : ListCell *cell;
875 :
876 : Assert(IsPointerList(list));
877 : check_list_invariants(list);
878 :
879 1923760 : foreach(cell, list)
880 : {
881 1923760 : if (lfirst(cell) == datum)
882 1923268 : 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 80 : list_delete_int(List *list, int datum)
892 : {
893 : ListCell *cell;
894 :
895 : Assert(IsIntegerList(list));
896 : check_list_invariants(list);
897 :
898 86 : foreach(cell, list)
899 : {
900 86 : if (lfirst_int(cell) == datum)
901 80 : 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 7490 : list_delete_oid(List *list, Oid datum)
911 : {
912 : ListCell *cell;
913 :
914 : Assert(IsOidList(list));
915 : check_list_invariants(list);
916 :
917 7490 : foreach(cell, list)
918 : {
919 1556 : if (lfirst_oid(cell) == datum)
920 1556 : return list_delete_cell(list, cell);
921 : }
922 :
923 : /* Didn't find a match: return the list unmodified */
924 5934 : 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 641050 : list_delete_first(List *list)
944 : {
945 : check_list_invariants(list);
946 :
947 641050 : if (list == NIL)
948 0 : return NIL; /* would an error be better? */
949 :
950 641050 : return list_delete_nth_cell(list, 0);
951 : }
952 :
953 : /*
954 : * Delete the last element of the list.
955 : */
956 : List *
957 65720 : list_delete_last(List *list)
958 : {
959 : check_list_invariants(list);
960 :
961 65720 : 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 65720 : if (list_length(list) <= 1)
966 : {
967 34632 : list_free(list);
968 34632 : return NIL;
969 : }
970 :
971 31088 : 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 466 : list_delete_first_n(List *list, int n)
984 : {
985 : check_list_invariants(list);
986 :
987 : /* No-op request? */
988 466 : if (n <= 0)
989 2 : return list;
990 :
991 : /* Delete whole list? */
992 464 : 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 464 : memmove(&list->elements[0], &list->elements[n],
1006 464 : (list->length - n) * sizeof(ListCell));
1007 464 : 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 464 : 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 8464 : 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 8464 : result = list_copy(list1);
1075 17594 : foreach(cell, list2)
1076 : {
1077 9130 : if (!list_member(result, lfirst(cell)))
1078 8882 : result = lappend(result, lfirst(cell));
1079 : }
1080 :
1081 : check_list_invariants(result);
1082 8464 : 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 5322 : 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 5322 : result = list_copy(list1);
1122 10826 : foreach(cell, list2)
1123 : {
1124 5504 : if (!list_member_int(result, lfirst_int(cell)))
1125 5268 : result = lappend_int(result, lfirst_int(cell));
1126 : }
1127 :
1128 : check_list_invariants(result);
1129 5322 : 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 298 : list_intersection_int(const List *list1, const List *list2)
1201 : {
1202 : List *result;
1203 : const ListCell *cell;
1204 :
1205 298 : if (list1 == NIL || list2 == NIL)
1206 0 : return NIL;
1207 :
1208 : Assert(IsIntegerList(list1));
1209 : Assert(IsIntegerList(list2));
1210 :
1211 298 : result = NIL;
1212 644 : foreach(cell, list1)
1213 : {
1214 346 : if (list_member_int(list2, lfirst_int(cell)))
1215 162 : result = lappend_int(result, lfirst_int(cell));
1216 : }
1217 :
1218 : check_list_invariants(result);
1219 298 : 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 36114 : list_difference(const List *list1, const List *list2)
1238 : {
1239 : const ListCell *cell;
1240 36114 : List *result = NIL;
1241 :
1242 : Assert(IsPointerList(list1));
1243 : Assert(IsPointerList(list2));
1244 :
1245 36114 : if (list2 == NIL)
1246 1130 : return list_copy(list1);
1247 :
1248 74860 : foreach(cell, list1)
1249 : {
1250 39876 : if (!list_member(list2, lfirst(cell)))
1251 1878 : result = lappend(result, lfirst(cell));
1252 : }
1253 :
1254 : check_list_invariants(result);
1255 34984 : return result;
1256 : }
1257 :
1258 : /*
1259 : * This variant of list_difference() determines list membership via
1260 : * simple pointer equality.
1261 : */
1262 : List *
1263 20134 : list_difference_ptr(const List *list1, const List *list2)
1264 : {
1265 : const ListCell *cell;
1266 20134 : List *result = NIL;
1267 :
1268 : Assert(IsPointerList(list1));
1269 : Assert(IsPointerList(list2));
1270 :
1271 20134 : if (list2 == NIL)
1272 15906 : return list_copy(list1);
1273 :
1274 10668 : foreach(cell, list1)
1275 : {
1276 6440 : if (!list_member_ptr(list2, lfirst(cell)))
1277 2888 : result = lappend(result, lfirst(cell));
1278 : }
1279 :
1280 : check_list_invariants(result);
1281 4228 : return result;
1282 : }
1283 :
1284 : /*
1285 : * This variant of list_difference() operates upon lists of integers.
1286 : */
1287 : List *
1288 2410 : list_difference_int(const List *list1, const List *list2)
1289 : {
1290 : const ListCell *cell;
1291 2410 : List *result = NIL;
1292 :
1293 : Assert(IsIntegerList(list1));
1294 : Assert(IsIntegerList(list2));
1295 :
1296 2410 : if (list2 == NIL)
1297 1742 : return list_copy(list1);
1298 :
1299 1980 : foreach(cell, list1)
1300 : {
1301 1312 : if (!list_member_int(list2, lfirst_int(cell)))
1302 516 : result = lappend_int(result, lfirst_int(cell));
1303 : }
1304 :
1305 : check_list_invariants(result);
1306 668 : return result;
1307 : }
1308 :
1309 : /*
1310 : * This variant of list_difference() operates upon lists of OIDs.
1311 : */
1312 : List *
1313 392 : list_difference_oid(const List *list1, const List *list2)
1314 : {
1315 : const ListCell *cell;
1316 392 : List *result = NIL;
1317 :
1318 : Assert(IsOidList(list1));
1319 : Assert(IsOidList(list2));
1320 :
1321 392 : if (list2 == NIL)
1322 356 : 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 120482 : list_append_unique(List *list, void *datum)
1344 : {
1345 120482 : if (list_member(list, datum))
1346 5746 : return list;
1347 : else
1348 114736 : 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 427944 : list_append_unique_ptr(List *list, void *datum)
1357 : {
1358 427944 : if (list_member_ptr(list, datum))
1359 164142 : return list;
1360 : else
1361 263802 : 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 6018 : list_append_unique_oid(List *list, Oid datum)
1381 : {
1382 6018 : if (list_member_oid(list, datum))
1383 2266 : return list;
1384 : else
1385 3752 : 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 2844 : list_concat_unique(List *list1, const List *list2)
1406 : {
1407 : ListCell *cell;
1408 :
1409 : Assert(IsPointerList(list1));
1410 : Assert(IsPointerList(list2));
1411 :
1412 5364 : foreach(cell, list2)
1413 : {
1414 2520 : if (!list_member(list1, lfirst(cell)))
1415 2496 : list1 = lappend(list1, lfirst(cell));
1416 : }
1417 :
1418 : check_list_invariants(list1);
1419 2844 : return list1;
1420 : }
1421 :
1422 : /*
1423 : * This variant of list_concat_unique() determines list membership via
1424 : * simple pointer equality.
1425 : */
1426 : List *
1427 7948 : list_concat_unique_ptr(List *list1, const List *list2)
1428 : {
1429 : ListCell *cell;
1430 :
1431 : Assert(IsPointerList(list1));
1432 : Assert(IsPointerList(list2));
1433 :
1434 20478 : foreach(cell, list2)
1435 : {
1436 12530 : if (!list_member_ptr(list1, lfirst(cell)))
1437 4662 : list1 = lappend(list1, lfirst(cell));
1438 : }
1439 :
1440 : check_list_invariants(list1);
1441 7948 : 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 22258 : list_concat_unique_oid(List *list1, const List *list2)
1470 : {
1471 : ListCell *cell;
1472 :
1473 : Assert(IsOidList(list1));
1474 : Assert(IsOidList(list2));
1475 :
1476 25044 : foreach(cell, list2)
1477 : {
1478 2786 : if (!list_member_oid(list1, lfirst_oid(cell)))
1479 2136 : list1 = lappend_oid(list1, lfirst_oid(cell));
1480 : }
1481 :
1482 : check_list_invariants(list1);
1483 22258 : 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 2962 : list_deduplicate_oid(List *list)
1496 : {
1497 : int len;
1498 :
1499 : Assert(IsOidList(list));
1500 2962 : len = list_length(list);
1501 2962 : if (len > 1)
1502 : {
1503 620 : ListCell *elements = list->elements;
1504 620 : int i = 0;
1505 :
1506 1924 : for (int j = 1; j < len; j++)
1507 : {
1508 1304 : if (elements[i].oid_value != elements[j].oid_value)
1509 1172 : elements[++i].oid_value = elements[j].oid_value;
1510 : }
1511 620 : list->length = i + 1;
1512 : }
1513 : check_list_invariants(list);
1514 2962 : }
1515 :
1516 : /*
1517 : * Free all storage in a list, and optionally the pointed-to elements
1518 : */
1519 : static void
1520 21000128 : list_free_private(List *list, bool deep)
1521 : {
1522 21000128 : if (list == NIL)
1523 15889980 : return; /* nothing to do */
1524 :
1525 : check_list_invariants(list);
1526 :
1527 5110148 : if (deep)
1528 : {
1529 1235802 : for (int i = 0; i < list->length; i++)
1530 944068 : pfree(lfirst(&list->elements[i]));
1531 : }
1532 5110148 : if (list->elements != list->initial_elements)
1533 124672 : pfree(list->elements);
1534 5110148 : 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 19687676 : list_free(List *list)
1547 : {
1548 19687676 : list_free_private(list, false);
1549 19687676 : }
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 1312452 : 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 1312452 : list_free_private(list, true);
1567 1312452 : }
1568 :
1569 : /*
1570 : * Return a shallow copy of the specified list.
1571 : */
1572 : List *
1573 8583016 : list_copy(const List *oldlist)
1574 : {
1575 : List *newlist;
1576 :
1577 8583016 : if (oldlist == NIL)
1578 1731388 : return NIL;
1579 :
1580 6851628 : newlist = new_list(oldlist->type, oldlist->length);
1581 6851628 : memcpy(newlist->elements, oldlist->elements,
1582 6851628 : newlist->length * sizeof(ListCell));
1583 :
1584 : check_list_invariants(newlist);
1585 6851628 : 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 81430 : list_copy_head(const List *oldlist, int len)
1594 : {
1595 : List *newlist;
1596 :
1597 81430 : if (oldlist == NIL || len <= 0)
1598 404 : return NIL;
1599 :
1600 81026 : len = Min(oldlist->length, len);
1601 :
1602 81026 : newlist = new_list(oldlist->type, len);
1603 81026 : memcpy(newlist->elements, oldlist->elements, len * sizeof(ListCell));
1604 :
1605 : check_list_invariants(newlist);
1606 81026 : return newlist;
1607 : }
1608 :
1609 : /*
1610 : * Return a shallow copy of the specified list, without the first N elements.
1611 : */
1612 : List *
1613 91046 : list_copy_tail(const List *oldlist, int nskip)
1614 : {
1615 : List *newlist;
1616 :
1617 91046 : if (nskip < 0)
1618 0 : nskip = 0; /* would it be better to elog? */
1619 :
1620 91046 : if (oldlist == NIL || nskip >= oldlist->length)
1621 1810 : return NIL;
1622 :
1623 89236 : newlist = new_list(oldlist->type, oldlist->length - nskip);
1624 89236 : memcpy(newlist->elements, &oldlist->elements[nskip],
1625 89236 : newlist->length * sizeof(ListCell));
1626 :
1627 : check_list_invariants(newlist);
1628 89236 : 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 18149456 : list_copy_deep(const List *oldlist)
1640 : {
1641 : List *newlist;
1642 :
1643 18149456 : if (oldlist == NIL)
1644 0 : return NIL;
1645 :
1646 : /* This is only sensible for pointer Lists */
1647 : Assert(IsA(oldlist, List));
1648 :
1649 18149456 : newlist = new_list(oldlist->type, oldlist->length);
1650 73544026 : for (int i = 0; i < newlist->length; i++)
1651 55394570 : lfirst(&newlist->elements[i]) =
1652 55394570 : copyObjectImpl(lfirst(&oldlist->elements[i]));
1653 :
1654 : check_list_invariants(newlist);
1655 18149456 : 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 360444 : 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 360444 : len = list_length(list);
1683 360444 : if (len > 1)
1684 87780 : qsort(list->elements, len, sizeof(ListCell), (qsort_comparator) cmp);
1685 360444 : }
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 105974 : list_oid_cmp(const ListCell *p1, const ListCell *p2)
1704 : {
1705 105974 : Oid v1 = lfirst_oid(p1);
1706 105974 : Oid v2 = lfirst_oid(p2);
1707 :
1708 105974 : return pg_cmp_u32(v1, v2);
1709 : }
|