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