Branch data Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * list.c
4 : : * implementation for PostgreSQL generic list package
5 : : *
6 : : * See comments in pg_list.h.
7 : : *
8 : : *
9 : : * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group
10 : : * Portions Copyright (c) 1994, Regents of the University of California
11 : : *
12 : : *
13 : : * IDENTIFICATION
14 : : * src/backend/nodes/list.c
15 : : *
16 : : *-------------------------------------------------------------------------
17 : : */
18 : : #include "postgres.h"
19 : :
20 : : #include "common/int.h"
21 : : #include "nodes/pg_list.h"
22 : : #include "port/pg_bitutils.h"
23 : : #include "utils/memdebug.h"
24 : : #include "utils/memutils.h"
25 : :
26 : :
27 : : /*
28 : : * The previous List implementation, since it used a separate palloc chunk
29 : : * for each cons cell, had the property that adding or deleting list cells
30 : : * did not move the storage of other existing cells in the list. Quite a
31 : : * bit of existing code depended on that, by retaining ListCell pointers
32 : : * across such operations on a list. There is no such guarantee in this
33 : : * implementation, so instead we have debugging support that is meant to
34 : : * help flush out now-broken assumptions. Defining DEBUG_LIST_MEMORY_USAGE
35 : : * while building this file causes the List operations to forcibly move
36 : : * all cells in a list whenever a cell is added or deleted. In combination
37 : : * with MEMORY_CONTEXT_CHECKING and/or Valgrind, this can usually expose
38 : : * broken code. It's a bit expensive though, as there's many more palloc
39 : : * cycles and a lot more data-copying than in a default build.
40 : : *
41 : : * By default, we enable this when building for Valgrind.
42 : : */
43 : : #ifdef USE_VALGRIND
44 : : #define DEBUG_LIST_MEMORY_USAGE
45 : : #endif
46 : :
47 : : /* Overhead for the fixed part of a List header, measured in ListCells */
48 : : #define LIST_HEADER_OVERHEAD \
49 : : ((int) ((offsetof(List, initial_elements) - 1) / sizeof(ListCell) + 1))
50 : :
51 : : /*
52 : : * Macros to simplify writing assertions about the type of a list; a
53 : : * NIL list is considered to be an empty list of any type.
54 : : */
55 : : #define IsPointerList(l) ((l) == NIL || IsA((l), List))
56 : : #define IsIntegerList(l) ((l) == NIL || IsA((l), IntList))
57 : : #define IsOidList(l) ((l) == NIL || IsA((l), OidList))
58 : : #define IsXidList(l) ((l) == NIL || IsA((l), XidList))
59 : :
60 : : #ifdef USE_ASSERT_CHECKING
61 : : /*
62 : : * Check that the specified List is valid (so far as we can tell).
63 : : */
64 : : static void
65 : : check_list_invariants(const List *list)
66 : : {
67 : : if (list == NIL)
68 : : return;
69 : :
70 : : Assert(list->length > 0);
71 : : Assert(list->length <= list->max_length);
72 : : Assert(list->elements != NULL);
73 : :
74 : : Assert(list->type == T_List ||
75 : : list->type == T_IntList ||
76 : : list->type == T_OidList ||
77 : : list->type == T_XidList);
78 : : }
79 : : #else
80 : : #define check_list_invariants(l) ((void) 0)
81 : : #endif /* USE_ASSERT_CHECKING */
82 : :
83 : : /*
84 : : * Return a freshly allocated List with room for at least min_size cells.
85 : : *
86 : : * Since empty non-NIL lists are invalid, new_list() sets the initial length
87 : : * to min_size, effectively marking that number of cells as valid; the caller
88 : : * is responsible for filling in their data.
89 : : */
90 : : static List *
91 : 84628365 : 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 : 84628365 : max_size = pg_nextpower2_32(Max(8, min_size + LIST_HEADER_OVERHEAD));
127 : 84628365 : 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 : 84628365 : newlist = (List *) palloc(offsetof(List, initial_elements) +
138 : : max_size * sizeof(ListCell));
139 : 84628365 : newlist->type = type;
140 : 84628365 : newlist->length = min_size;
141 : 84628365 : newlist->max_length = max_size;
142 : 84628365 : newlist->elements = newlist->initial_elements;
143 : :
144 : 84628365 : 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 : 4060892 : 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 : 4060892 : 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 [ + + ]: 4060892 : 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 : 2554131 : list->elements = (ListCell *)
186 : 2554131 : MemoryContextAlloc(GetMemoryChunkContext(list),
187 : : new_max_len * sizeof(ListCell));
188 : 2554131 : memcpy(list->elements, list->initial_elements,
189 : 2554131 : 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 : 1506761 : 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 : 4060892 : list->max_length = new_max_len;
229 : 4060892 : }
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 : 9510112 : list_make1_impl(NodeTag t, ListCell datum1)
237 : : {
238 : 9510112 : List *list = new_list(t, 1);
239 : :
240 : 9510112 : list->elements[0] = datum1;
241 : : check_list_invariants(list);
242 : 9510112 : return list;
243 : : }
244 : :
245 : : List *
246 : 1161742 : list_make2_impl(NodeTag t, ListCell datum1, ListCell datum2)
247 : : {
248 : 1161742 : List *list = new_list(t, 2);
249 : :
250 : 1161742 : list->elements[0] = datum1;
251 : 1161742 : list->elements[1] = datum2;
252 : : check_list_invariants(list);
253 : 1161742 : return list;
254 : : }
255 : :
256 : : List *
257 : 4997 : list_make3_impl(NodeTag t, ListCell datum1, ListCell datum2,
258 : : ListCell datum3)
259 : : {
260 : 4997 : List *list = new_list(t, 3);
261 : :
262 : 4997 : list->elements[0] = datum1;
263 : 4997 : list->elements[1] = datum2;
264 : 4997 : list->elements[2] = datum3;
265 : : check_list_invariants(list);
266 : 4997 : return list;
267 : : }
268 : :
269 : : List *
270 : 131 : list_make4_impl(NodeTag t, ListCell datum1, ListCell datum2,
271 : : ListCell datum3, ListCell datum4)
272 : : {
273 : 131 : List *list = new_list(t, 4);
274 : :
275 : 131 : list->elements[0] = datum1;
276 : 131 : list->elements[1] = datum2;
277 : 131 : list->elements[2] = datum3;
278 : 131 : list->elements[3] = datum4;
279 : : check_list_invariants(list);
280 : 131 : return list;
281 : : }
282 : :
283 : : List *
284 : 171 : list_make5_impl(NodeTag t, ListCell datum1, ListCell datum2,
285 : : ListCell datum3, ListCell datum4, ListCell datum5)
286 : : {
287 : 171 : List *list = new_list(t, 5);
288 : :
289 : 171 : list->elements[0] = datum1;
290 : 171 : list->elements[1] = datum2;
291 : 171 : list->elements[2] = datum3;
292 : 171 : list->elements[3] = datum4;
293 : 171 : list->elements[4] = datum5;
294 : : check_list_invariants(list);
295 : 171 : 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 : 2230169 : new_head_cell(List *list)
306 : : {
307 : : /* Enlarge array if necessary */
308 [ + + ]: 2230169 : if (list->length >= list->max_length)
309 : 39372 : enlarge_list(list, list->length + 1);
310 : : /* Now shove the existing data over */
311 : 2230169 : memmove(&list->elements[1], &list->elements[0],
312 : 2230169 : list->length * sizeof(ListCell));
313 : 2230169 : list->length++;
314 : 2230169 : }
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 : 67680921 : new_tail_cell(List *list)
324 : : {
325 : : /* Enlarge array if necessary */
326 [ + + ]: 67680921 : if (list->length >= list->max_length)
327 : 4001243 : enlarge_list(list, list->length + 1);
328 : 67680921 : list->length++;
329 : 67680921 : }
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 : 103946857 : lappend(List *list, void *datum)
340 : : {
341 : : Assert(IsPointerList(list));
342 : :
343 [ + + ]: 103946857 : if (list == NIL)
344 : 43493784 : list = new_list(T_List, 1);
345 : : else
346 : 60453073 : new_tail_cell(list);
347 : :
348 : 103946857 : llast(list) = datum;
349 : : check_list_invariants(list);
350 : 103946857 : return list;
351 : : }
352 : :
353 : : /*
354 : : * Append an integer to the specified list. See lappend()
355 : : */
356 : : List *
357 : 6875026 : lappend_int(List *list, int datum)
358 : : {
359 : : Assert(IsIntegerList(list));
360 : :
361 [ + + ]: 6875026 : if (list == NIL)
362 : 1244049 : list = new_list(T_IntList, 1);
363 : : else
364 : 5630977 : new_tail_cell(list);
365 : :
366 : 6875026 : llast_int(list) = datum;
367 : : check_list_invariants(list);
368 : 6875026 : return list;
369 : : }
370 : :
371 : : /*
372 : : * Append an OID to the specified list. See lappend()
373 : : */
374 : : List *
375 : 5420149 : lappend_oid(List *list, Oid datum)
376 : : {
377 : : Assert(IsOidList(list));
378 : :
379 [ + + ]: 5420149 : if (list == NIL)
380 : 3823311 : list = new_list(T_OidList, 1);
381 : : else
382 : 1596838 : new_tail_cell(list);
383 : :
384 : 5420149 : llast_oid(list) = datum;
385 : : check_list_invariants(list);
386 : 5420149 : return list;
387 : : }
388 : :
389 : : /*
390 : : * Append a TransactionId to the specified list. See lappend()
391 : : */
392 : : List *
393 : 90 : lappend_xid(List *list, TransactionId datum)
394 : : {
395 : : Assert(IsXidList(list));
396 : :
397 [ + + ]: 90 : if (list == NIL)
398 : 57 : list = new_list(T_XidList, 1);
399 : : else
400 : 33 : new_tail_cell(list);
401 : :
402 : 90 : llast_xid(list) = datum;
403 : : check_list_invariants(list);
404 : 90 : return list;
405 : : }
406 : :
407 : : /*
408 : : * Make room for a new cell at position 'pos' (measured from 0).
409 : : * The data in the cell is left undefined, and must be filled in by the
410 : : * caller. 'list' is assumed to be non-NIL, and 'pos' must be a valid
411 : : * list position, ie, 0 <= pos <= list's length.
412 : : * Returns address of the new cell.
413 : : */
414 : : static ListCell *
415 : 742056 : insert_new_cell(List *list, int pos)
416 : : {
417 : : Assert(pos >= 0 && pos <= list->length);
418 : :
419 : : /* Enlarge array if necessary */
420 [ + + ]: 742056 : if (list->length >= list->max_length)
421 : 1330 : enlarge_list(list, list->length + 1);
422 : : /* Now shove the existing data over */
423 [ + + ]: 742056 : if (pos < list->length)
424 : 320668 : memmove(&list->elements[pos + 1], &list->elements[pos],
425 : 320668 : (list->length - pos) * sizeof(ListCell));
426 : 742056 : list->length++;
427 : :
428 : 742056 : 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 : 2420034 : list_insert_nth(List *list, int pos, void *datum)
440 : : {
441 [ + + ]: 2420034 : if (list == NIL)
442 : : {
443 : : Assert(pos == 0);
444 : 1677978 : return list_make1(datum);
445 : : }
446 : : Assert(IsPointerList(list));
447 : 742056 : lfirst(insert_new_cell(list, pos)) = datum;
448 : : check_list_invariants(list);
449 : 742056 : 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 : 5355149 : lcons(void *datum, List *list)
496 : : {
497 : : Assert(IsPointerList(list));
498 : :
499 [ + + ]: 5355149 : if (list == NIL)
500 : 3166273 : list = new_list(T_List, 1);
501 : : else
502 : 2188876 : new_head_cell(list);
503 : :
504 : 5355149 : linitial(list) = datum;
505 : : check_list_invariants(list);
506 : 5355149 : return list;
507 : : }
508 : :
509 : : /*
510 : : * Prepend an integer to the list. See lcons()
511 : : */
512 : : List *
513 : 17238 : lcons_int(int datum, List *list)
514 : : {
515 : : Assert(IsIntegerList(list));
516 : :
517 [ + + ]: 17238 : if (list == NIL)
518 : 7803 : list = new_list(T_IntList, 1);
519 : : else
520 : 9435 : new_head_cell(list);
521 : :
522 : 17238 : linitial_int(list) = datum;
523 : : check_list_invariants(list);
524 : 17238 : return list;
525 : : }
526 : :
527 : : /*
528 : : * Prepend an OID to the list. See lcons()
529 : : */
530 : : List *
531 : 35883 : lcons_oid(Oid datum, List *list)
532 : : {
533 : : Assert(IsOidList(list));
534 : :
535 [ + + ]: 35883 : if (list == NIL)
536 : 4025 : list = new_list(T_OidList, 1);
537 : : else
538 : 31858 : new_head_cell(list);
539 : :
540 : 35883 : linitial_oid(list) = datum;
541 : : check_list_invariants(list);
542 : 35883 : 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 : 5193209 : list_concat(List *list1, const List *list2)
562 : : {
563 : : int new_len;
564 : :
565 [ + + ]: 5193209 : if (list1 == NIL)
566 : 3678754 : return list_copy(list2);
567 [ + + ]: 1514455 : if (list2 == NIL)
568 : 886232 : return list1;
569 : :
570 : : Assert(list1->type == list2->type);
571 : :
572 : 628223 : new_len = list1->length + list2->length;
573 : : /* Enlarge array if necessary */
574 [ + + ]: 628223 : if (new_len > list1->max_length)
575 : 18947 : enlarge_list(list1, new_len);
576 : :
577 : : /* Even if list1 == list2, using memcpy should be safe here */
578 : 628223 : memcpy(&list1->elements[list1->length], &list2->elements[0],
579 : 628223 : list2->length * sizeof(ListCell));
580 : 628223 : list1->length = new_len;
581 : :
582 : : check_list_invariants(list1);
583 : 628223 : 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 : 869459 : list_concat_copy(const List *list1, const List *list2)
599 : : {
600 : : List *result;
601 : : int new_len;
602 : :
603 [ + + ]: 869459 : if (list1 == NIL)
604 : 374925 : return list_copy(list2);
605 [ + + ]: 494534 : if (list2 == NIL)
606 : 414066 : return list_copy(list1);
607 : :
608 : : Assert(list1->type == list2->type);
609 : :
610 : 80468 : new_len = list1->length + list2->length;
611 : 80468 : result = new_list(list1->type, new_len);
612 : 80468 : memcpy(result->elements, list1->elements,
613 : 80468 : list1->length * sizeof(ListCell));
614 : 80468 : memcpy(result->elements + list1->length, list2->elements,
615 : 80468 : list2->length * sizeof(ListCell));
616 : :
617 : : check_list_invariants(result);
618 : 80468 : 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 : 533559 : list_truncate(List *list, int new_size)
632 : : {
633 [ + + ]: 533559 : if (new_size <= 0)
634 : 58556 : return NIL; /* truncate to zero length */
635 : :
636 : : /* If asked to effectively extend the list, do nothing */
637 [ + + ]: 475003 : if (new_size < list_length(list))
638 : 131558 : 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 : 475003 : 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 : 877801 : 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 [ + + + + : 1555832 : foreach(cell, list)
+ + ]
669 : : {
670 [ + + ]: 780425 : if (equal(lfirst(cell), datum))
671 : 102394 : return true;
672 : : }
673 : :
674 : 775407 : 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 : 463220 : 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 [ + + + + : 750255 : foreach(cell, list)
+ + ]
690 : : {
691 [ + + ]: 464819 : if (lfirst(cell) == datum)
692 : 177784 : return true;
693 : : }
694 : :
695 : 285436 : return false;
696 : : }
697 : :
698 : : /*
699 : : * Return true iff the integer 'datum' is a member of the list.
700 : : */
701 : : bool
702 : 88961 : 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 [ + + + + : 5036142 : foreach(cell, list)
+ + ]
710 : : {
711 [ + + ]: 4962492 : if (lfirst_int(cell) == datum)
712 : 15311 : return true;
713 : : }
714 : :
715 : 73650 : return false;
716 : : }
717 : :
718 : : /*
719 : : * Return true iff the OID 'datum' is a member of the list.
720 : : */
721 : : bool
722 : 61211564 : 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 [ + + + + : 64888809 : foreach(cell, list)
+ + ]
730 : : {
731 [ + + ]: 4597352 : if (lfirst_oid(cell) == datum)
732 : 920107 : return true;
733 : : }
734 : :
735 : 60291457 : return false;
736 : : }
737 : :
738 : : /*
739 : : * Return true iff the TransactionId 'datum' is a member of the list.
740 : : */
741 : : bool
742 : 170966 : 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 [ + + + + : 211836 : foreach(cell, list)
+ + ]
750 : : {
751 [ + + ]: 211746 : if (lfirst_xid(cell) == datum)
752 : 170876 : return true;
753 : : }
754 : :
755 : 90 : return false;
756 : : }
757 : :
758 : : /*
759 : : * Delete the n'th cell (counting from 0) in list.
760 : : *
761 : : * The List is pfree'd if this was the last member.
762 : : *
763 : : * Note that this takes time proportional to the distance to the end of the
764 : : * list, since the following entries must be moved.
765 : : */
766 : : List *
767 : 2759159 : 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 [ + + ]: 2759159 : if (list->length == 1)
779 : : {
780 : 1391709 : list_free(list);
781 : 1391709 : 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 : 1367450 : memmove(&list->elements[n], &list->elements[n + 1],
792 : 1367450 : (list->length - 1 - n) * sizeof(ListCell));
793 : 1367450 : 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 : 1367450 : 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 : 1395504 : list_delete_cell(List *list, ListCell *cell)
842 : : {
843 : 1395504 : 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 : 3755 : list_delete(List *list, void *datum)
854 : : {
855 : : ListCell *cell;
856 : :
857 : : Assert(IsPointerList(list));
858 : : check_list_invariants(list);
859 : :
860 [ + + + - : 3993 : foreach(cell, list)
+ + ]
861 : : {
862 [ + + ]: 3990 : if (equal(lfirst(cell), datum))
863 : 3752 : return list_delete_cell(list, cell);
864 : : }
865 : :
866 : : /* Didn't find a match: return the list unmodified */
867 : 3 : return list;
868 : : }
869 : :
870 : : /* As above, but use simple pointer equality */
871 : : List *
872 : 1381415 : list_delete_ptr(List *list, void *datum)
873 : : {
874 : : ListCell *cell;
875 : :
876 : : Assert(IsPointerList(list));
877 : : check_list_invariants(list);
878 : :
879 [ + - + - : 1381785 : foreach(cell, list)
+ - ]
880 : : {
881 [ + + ]: 1381785 : if (lfirst(cell) == datum)
882 : 1381415 : 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 : 144 : list_delete_int(List *list, int datum)
892 : : {
893 : : ListCell *cell;
894 : :
895 : : Assert(IsIntegerList(list));
896 : : check_list_invariants(list);
897 : :
898 [ + - + - : 149 : foreach(cell, list)
+ - ]
899 : : {
900 [ + + ]: 149 : if (lfirst_int(cell) == datum)
901 : 144 : 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 : 4938 : list_delete_oid(List *list, Oid datum)
911 : : {
912 : : ListCell *cell;
913 : :
914 : : Assert(IsOidList(list));
915 : : check_list_invariants(list);
916 : :
917 [ + + + - : 4938 : foreach(cell, list)
+ + ]
918 : : {
919 [ + - ]: 1162 : if (lfirst_oid(cell) == datum)
920 : 1162 : return list_delete_cell(list, cell);
921 : : }
922 : :
923 : : /* Didn't find a match: return the list unmodified */
924 : 3776 : 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 : 601043 : list_delete_first(List *list)
944 : : {
945 : : check_list_invariants(list);
946 : :
947 [ - + ]: 601043 : if (list == NIL)
948 : 0 : return NIL; /* would an error be better? */
949 : :
950 : 601043 : return list_delete_nth_cell(list, 0);
951 : : }
952 : :
953 : : /*
954 : : * Delete the last element of the list.
955 : : */
956 : : List *
957 : 70003 : list_delete_last(List *list)
958 : : {
959 : : check_list_invariants(list);
960 : :
961 [ - + ]: 70003 : 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 [ + + ]: 70003 : if (list_length(list) <= 1)
966 : : {
967 : 18365 : list_free(list);
968 : 18365 : return NIL;
969 : : }
970 : :
971 : 51638 : 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 : 472 : list_delete_first_n(List *list, int n)
984 : : {
985 : : check_list_invariants(list);
986 : :
987 : : /* No-op request? */
988 [ + + ]: 472 : if (n <= 0)
989 : 11 : return list;
990 : :
991 : : /* Delete whole list? */
992 [ - + ]: 461 : 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 : 461 : memmove(&list->elements[0], &list->elements[n],
1006 : 461 : (list->length - n) * sizeof(ListCell));
1007 : 461 : 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 : 461 : 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 : 8683 : 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 : 8683 : result = list_copy(list1);
1075 [ + + + + : 17814 : foreach(cell, list2)
+ + ]
1076 : : {
1077 [ + + ]: 9131 : if (!list_member(result, lfirst(cell)))
1078 : 9069 : result = lappend(result, lfirst(cell));
1079 : : }
1080 : :
1081 : : check_list_invariants(result);
1082 : 8683 : 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 : 5211 : 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 : 5211 : result = list_copy(list1);
1122 [ + + + + : 10362 : foreach(cell, list2)
+ + ]
1123 : : {
1124 [ + + ]: 5151 : if (!list_member_int(result, lfirst_int(cell)))
1125 : 4983 : result = lappend_int(result, lfirst_int(cell));
1126 : : }
1127 : :
1128 : : check_list_invariants(result);
1129 : 5211 : 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 : 354 : list_intersection_int(const List *list1, const List *list2)
1201 : : {
1202 : : List *result;
1203 : : const ListCell *cell;
1204 : :
1205 [ + - - + ]: 354 : if (list1 == NIL || list2 == NIL)
1206 : 0 : return NIL;
1207 : :
1208 : : Assert(IsIntegerList(list1));
1209 : : Assert(IsIntegerList(list2));
1210 : :
1211 : 354 : result = NIL;
1212 [ + - + + : 740 : foreach(cell, list1)
+ + ]
1213 : : {
1214 [ + + ]: 386 : if (list_member_int(list2, lfirst_int(cell)))
1215 : 156 : result = lappend_int(result, lfirst_int(cell));
1216 : : }
1217 : :
1218 : : check_list_invariants(result);
1219 : 354 : 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 : 41052 : list_difference(const List *list1, const List *list2)
1238 : : {
1239 : : const ListCell *cell;
1240 : 41052 : List *result = NIL;
1241 : :
1242 : : Assert(IsPointerList(list1));
1243 : : Assert(IsPointerList(list2));
1244 : :
1245 [ + + ]: 41052 : if (list2 == NIL)
1246 : 1335 : return list_copy(list1);
1247 : :
1248 [ + - + + : 85555 : foreach(cell, list1)
+ + ]
1249 : : {
1250 [ + + ]: 45838 : if (!list_member(list2, lfirst(cell)))
1251 : 1325 : result = lappend(result, lfirst(cell));
1252 : : }
1253 : :
1254 : : check_list_invariants(result);
1255 : 39717 : return result;
1256 : : }
1257 : :
1258 : : /*
1259 : : * This variant of list_difference() determines list membership via
1260 : : * simple pointer equality.
1261 : : */
1262 : : List *
1263 : 20798 : list_difference_ptr(const List *list1, const List *list2)
1264 : : {
1265 : : const ListCell *cell;
1266 : 20798 : List *result = NIL;
1267 : :
1268 : : Assert(IsPointerList(list1));
1269 : : Assert(IsPointerList(list2));
1270 : :
1271 [ + + ]: 20798 : if (list2 == NIL)
1272 : 17321 : return list_copy(list1);
1273 : :
1274 [ + + + + : 8585 : foreach(cell, list1)
+ + ]
1275 : : {
1276 [ + + ]: 5108 : if (!list_member_ptr(list2, lfirst(cell)))
1277 : 2423 : result = lappend(result, lfirst(cell));
1278 : : }
1279 : :
1280 : : check_list_invariants(result);
1281 : 3477 : return result;
1282 : : }
1283 : :
1284 : : /*
1285 : : * This variant of list_difference() operates upon lists of integers.
1286 : : */
1287 : : List *
1288 : 2625 : list_difference_int(const List *list1, const List *list2)
1289 : : {
1290 : : const ListCell *cell;
1291 : 2625 : List *result = NIL;
1292 : :
1293 : : Assert(IsIntegerList(list1));
1294 : : Assert(IsIntegerList(list2));
1295 : :
1296 [ + + ]: 2625 : if (list2 == NIL)
1297 : 2005 : return list_copy(list1);
1298 : :
1299 [ + - + + : 1840 : foreach(cell, list1)
+ + ]
1300 : : {
1301 [ + + ]: 1220 : if (!list_member_int(list2, lfirst_int(cell)))
1302 : 496 : result = lappend_int(result, lfirst_int(cell));
1303 : : }
1304 : :
1305 : : check_list_invariants(result);
1306 : 620 : return result;
1307 : : }
1308 : :
1309 : : /*
1310 : : * This variant of list_difference() operates upon lists of OIDs.
1311 : : */
1312 : : List *
1313 : 7750 : list_difference_oid(const List *list1, const List *list2)
1314 : : {
1315 : : const ListCell *cell;
1316 : 7750 : List *result = NIL;
1317 : :
1318 : : Assert(IsOidList(list1));
1319 : : Assert(IsOidList(list2));
1320 : :
1321 [ + + ]: 7750 : if (list2 == NIL)
1322 : 7344 : return list_copy(list1);
1323 : :
1324 [ + + + + : 2702 : foreach(cell, list1)
+ + ]
1325 : : {
1326 [ + + ]: 2296 : if (!list_member_oid(list2, lfirst_oid(cell)))
1327 : 1318 : result = lappend_oid(result, lfirst_oid(cell));
1328 : : }
1329 : :
1330 : : check_list_invariants(result);
1331 : 406 : 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 : 146757 : list_append_unique(List *list, void *datum)
1344 : : {
1345 [ + + ]: 146757 : if (list_member(list, datum))
1346 : 11840 : return list;
1347 : : else
1348 : 134917 : 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 : 385334 : list_append_unique_ptr(List *list, void *datum)
1357 : : {
1358 [ + + ]: 385334 : if (list_member_ptr(list, datum))
1359 : 154000 : return list;
1360 : : else
1361 : 231334 : 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 : 4194 : list_append_unique_oid(List *list, Oid datum)
1381 : : {
1382 [ + + ]: 4194 : if (list_member_oid(list, datum))
1383 : 1367 : return list;
1384 : : else
1385 : 2827 : 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 : 3151 : list_concat_unique(List *list1, const List *list2)
1406 : : {
1407 : : ListCell *cell;
1408 : :
1409 : : Assert(IsPointerList(list1));
1410 : : Assert(IsPointerList(list2));
1411 : :
1412 [ + + + + : 5800 : foreach(cell, list2)
+ + ]
1413 : : {
1414 [ + + ]: 2649 : if (!list_member(list1, lfirst(cell)))
1415 : 2624 : list1 = lappend(list1, lfirst(cell));
1416 : : }
1417 : :
1418 : : check_list_invariants(list1);
1419 : 3151 : return list1;
1420 : : }
1421 : :
1422 : : /*
1423 : : * This variant of list_concat_unique() determines list membership via
1424 : : * simple pointer equality.
1425 : : */
1426 : : List *
1427 : 1720 : list_concat_unique_ptr(List *list1, const List *list2)
1428 : : {
1429 : : ListCell *cell;
1430 : :
1431 : : Assert(IsPointerList(list1));
1432 : : Assert(IsPointerList(list2));
1433 : :
1434 [ + - + + : 5883 : foreach(cell, list2)
+ + ]
1435 : : {
1436 [ + + ]: 4163 : if (!list_member_ptr(list1, lfirst(cell)))
1437 : 2081 : list1 = lappend(list1, lfirst(cell));
1438 : : }
1439 : :
1440 : : check_list_invariants(list1);
1441 : 1720 : 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 : 16995 : list_concat_unique_oid(List *list1, const List *list2)
1470 : : {
1471 : : ListCell *cell;
1472 : :
1473 : : Assert(IsOidList(list1));
1474 : : Assert(IsOidList(list2));
1475 : :
1476 [ + + + + : 18915 : foreach(cell, list2)
+ + ]
1477 : : {
1478 [ + + ]: 1920 : if (!list_member_oid(list1, lfirst_oid(cell)))
1479 : 1396 : list1 = lappend_oid(list1, lfirst_oid(cell));
1480 : : }
1481 : :
1482 : : check_list_invariants(list1);
1483 : 16995 : 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 : 1307 : list_deduplicate_oid(List *list)
1496 : : {
1497 : : int len;
1498 : :
1499 : : Assert(IsOidList(list));
1500 : 1307 : len = list_length(list);
1501 [ + + ]: 1307 : if (len > 1)
1502 : : {
1503 : 177 : ListCell *elements = list->elements;
1504 : 177 : int i = 0;
1505 : :
1506 [ + + ]: 494 : for (int j = 1; j < len; j++)
1507 : : {
1508 [ + + ]: 317 : if (elements[i].oid_value != elements[j].oid_value)
1509 : 282 : elements[++i].oid_value = elements[j].oid_value;
1510 : : }
1511 : 177 : list->length = i + 1;
1512 : : }
1513 : : check_list_invariants(list);
1514 : 1307 : }
1515 : :
1516 : : /*
1517 : : * Free all storage in a list, and optionally the pointed-to elements
1518 : : */
1519 : : static void
1520 : 19521890 : list_free_private(List *list, bool deep)
1521 : : {
1522 [ + + ]: 19521890 : if (list == NIL)
1523 : 14941107 : return; /* nothing to do */
1524 : :
1525 : : check_list_invariants(list);
1526 : :
1527 [ + + ]: 4580783 : if (deep)
1528 : : {
1529 [ + + ]: 1346050 : for (int i = 0; i < list->length; i++)
1530 : 1065843 : pfree(lfirst(&list->elements[i]));
1531 : : }
1532 [ + + ]: 4580783 : if (list->elements != list->initial_elements)
1533 : 108980 : pfree(list->elements);
1534 : 4580783 : 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 : 17594528 : list_free(List *list)
1547 : : {
1548 : 17594528 : list_free_private(list, false);
1549 : 17594528 : }
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 : 1927362 : 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 : 1927362 : list_free_private(list, true);
1567 : 1927362 : }
1568 : :
1569 : : /*
1570 : : * Return a shallow copy of the specified list.
1571 : : */
1572 : : List *
1573 : 8483324 : list_copy(const List *oldlist)
1574 : : {
1575 : : List *newlist;
1576 : :
1577 [ + + ]: 8483324 : if (oldlist == NIL)
1578 : 1850788 : return NIL;
1579 : :
1580 : 6632536 : newlist = new_list(oldlist->type, oldlist->length);
1581 : 6632536 : memcpy(newlist->elements, oldlist->elements,
1582 : 6632536 : newlist->length * sizeof(ListCell));
1583 : :
1584 : : check_list_invariants(newlist);
1585 : 6632536 : 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 : 978385 : list_copy_head(const List *oldlist, int len)
1594 : : {
1595 : : List *newlist;
1596 : :
1597 [ + - + + ]: 978385 : if (oldlist == NIL || len <= 0)
1598 : 828252 : return NIL;
1599 : :
1600 : 150133 : len = Min(oldlist->length, len);
1601 : :
1602 : 150133 : newlist = new_list(oldlist->type, len);
1603 : 150133 : memcpy(newlist->elements, oldlist->elements, len * sizeof(ListCell));
1604 : :
1605 : : check_list_invariants(newlist);
1606 : 150133 : return newlist;
1607 : : }
1608 : :
1609 : : /*
1610 : : * Return a shallow copy of the specified list, without the first N elements.
1611 : : */
1612 : : List *
1613 : 70788 : list_copy_tail(const List *oldlist, int nskip)
1614 : : {
1615 : : List *newlist;
1616 : :
1617 [ - + ]: 70788 : if (nskip < 0)
1618 : 0 : nskip = 0; /* would it be better to elog? */
1619 : :
1620 [ + - + + ]: 70788 : if (oldlist == NIL || nskip >= oldlist->length)
1621 : 1534 : return NIL;
1622 : :
1623 : 69254 : newlist = new_list(oldlist->type, oldlist->length - nskip);
1624 : 69254 : memcpy(newlist->elements, &oldlist->elements[nskip],
1625 : 69254 : newlist->length * sizeof(ListCell));
1626 : :
1627 : : check_list_invariants(newlist);
1628 : 69254 : 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 : 15279519 : list_copy_deep(const List *oldlist)
1640 : : {
1641 : : List *newlist;
1642 : :
1643 [ - + ]: 15279519 : if (oldlist == NIL)
1644 : 0 : return NIL;
1645 : :
1646 : : /* This is only sensible for pointer Lists */
1647 : : Assert(IsA(oldlist, List));
1648 : :
1649 : 15279519 : newlist = new_list(oldlist->type, oldlist->length);
1650 [ + + ]: 63806309 : for (int i = 0; i < newlist->length; i++)
1651 : 48526790 : lfirst(&newlist->elements[i]) =
1652 : 48526790 : copyObjectImpl(lfirst(&oldlist->elements[i]));
1653 : :
1654 : : check_list_invariants(newlist);
1655 : 15279519 : 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 : 367221 : 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 : 367221 : len = list_length(list);
1683 [ + + ]: 367221 : if (len > 1)
1684 : 129366 : qsort(list->elements, len, sizeof(ListCell), (qsort_comparator) cmp);
1685 : 367221 : }
1686 : :
1687 : : /*
1688 : : * list_sort comparator for sorting a list into ascending int order.
1689 : : */
1690 : : int
1691 : 66 : list_int_cmp(const ListCell *p1, const ListCell *p2)
1692 : : {
1693 : 66 : int v1 = lfirst_int(p1);
1694 : 66 : int v2 = lfirst_int(p2);
1695 : :
1696 : 66 : 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 : 151967 : list_oid_cmp(const ListCell *p1, const ListCell *p2)
1704 : : {
1705 : 151967 : Oid v1 = lfirst_oid(p1);
1706 : 151967 : Oid v2 = lfirst_oid(p2);
1707 : :
1708 : 151967 : return pg_cmp_u32(v1, v2);
1709 : : }
|
