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 : 25285939 : check_list_invariants(const List *list)
66 : : {
67 [ + + ]: 25285939 : if (list == NIL)
68 : 6315255 : return;
69 : :
70 [ + - ]: 18970684 : Assert(list->length > 0);
71 [ + - ]: 18970684 : Assert(list->length <= list->max_length);
72 [ + - ]: 18970684 : Assert(list->elements != NULL);
73 : :
74 [ + + + + : 18970684 : Assert(list->type == T_List ||
- + # # ]
75 : : list->type == T_IntList ||
76 : : list->type == T_OidList ||
77 : : list->type == T_XidList);
78 : 25285939 : }
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 : 9443408 : new_list(NodeTag type, int min_size)
92 : : {
93 : 9443408 : List *newlist;
94 : 9443408 : int max_size;
95 : :
96 [ + - ]: 9443408 : 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 [ + + ]: 9443408 : max_size = pg_nextpower2_32(Max(8, min_size + LIST_HEADER_OVERHEAD));
127 : 9443408 : 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 : 9443408 : newlist = (List *) palloc(offsetof(List, initial_elements) +
138 : 9443408 : max_size * sizeof(ListCell));
139 : 9443408 : newlist->type = type;
140 : 9443408 : newlist->length = min_size;
141 : 9443408 : newlist->max_length = max_size;
142 : 9443408 : newlist->elements = newlist->initial_elements;
143 : :
144 : 18886816 : return newlist;
145 : 9443408 : }
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 : 247606 : enlarge_list(List *list, int min_size)
156 : : {
157 : 247606 : int new_max_len;
158 : :
159 [ + - ]: 247606 : 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 [ + + ]: 247606 : 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 [ + + ]: 247606 : 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 : 169439 : list->elements = (ListCell *)
186 : 338878 : MemoryContextAlloc(GetMemoryChunkContext(list),
187 : 169439 : new_max_len * sizeof(ListCell));
188 : 169439 : memcpy(list->elements, list->initial_elements,
189 : : 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 : 338878 : wipe_mem(list->initial_elements,
199 : 169439 : list->max_length * sizeof(ListCell));
200 : : #else
201 : : VALGRIND_MAKE_MEM_NOACCESS(list->initial_elements,
202 : : list->max_length * sizeof(ListCell));
203 : : #endif
204 : 169439 : }
205 : : else
206 : : {
207 : : #ifndef DEBUG_LIST_MEMORY_USAGE
208 : : /* Normally, let repalloc deal with enlargement */
209 : 156334 : list->elements = (ListCell *) repalloc(list->elements,
210 : 78167 : 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 : 247606 : list->max_length = new_max_len;
229 : 247606 : }
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 : 1199906 : list_make1_impl(NodeTag t, ListCell datum1)
237 : : {
238 : 1199906 : List *list = new_list(t, 1);
239 : :
240 : 1199906 : list->elements[0] = datum1;
241 : 1199906 : check_list_invariants(list);
242 : 2399812 : return list;
243 : 1199906 : }
244 : :
245 : : List *
246 : 144343 : list_make2_impl(NodeTag t, ListCell datum1, ListCell datum2)
247 : : {
248 : 144343 : List *list = new_list(t, 2);
249 : :
250 : 144343 : list->elements[0] = datum1;
251 : 144343 : list->elements[1] = datum2;
252 : 144343 : check_list_invariants(list);
253 : 288686 : return list;
254 : 144343 : }
255 : :
256 : : List *
257 : 583 : list_make3_impl(NodeTag t, ListCell datum1, ListCell datum2,
258 : : ListCell datum3)
259 : : {
260 : 583 : List *list = new_list(t, 3);
261 : :
262 : 583 : list->elements[0] = datum1;
263 : 583 : list->elements[1] = datum2;
264 : 583 : list->elements[2] = datum3;
265 : 583 : check_list_invariants(list);
266 : 1166 : return list;
267 : 583 : }
268 : :
269 : : List *
270 : 5 : list_make4_impl(NodeTag t, ListCell datum1, ListCell datum2,
271 : : ListCell datum3, ListCell datum4)
272 : : {
273 : 5 : List *list = new_list(t, 4);
274 : :
275 : 5 : list->elements[0] = datum1;
276 : 5 : list->elements[1] = datum2;
277 : 5 : list->elements[2] = datum3;
278 : 5 : list->elements[3] = datum4;
279 : 5 : check_list_invariants(list);
280 : 10 : return list;
281 : 5 : }
282 : :
283 : : List *
284 : 0 : list_make5_impl(NodeTag t, ListCell datum1, ListCell datum2,
285 : : ListCell datum3, ListCell datum4, ListCell datum5)
286 : : {
287 : 0 : List *list = new_list(t, 5);
288 : :
289 : 0 : list->elements[0] = datum1;
290 : 0 : list->elements[1] = datum2;
291 : 0 : list->elements[2] = datum3;
292 : 0 : list->elements[3] = datum4;
293 : 0 : list->elements[4] = datum5;
294 : 0 : check_list_invariants(list);
295 : 0 : return list;
296 : 0 : }
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 : 397597 : new_head_cell(List *list)
306 : : {
307 : : /* Enlarge array if necessary */
308 [ + + ]: 397597 : if (list->length >= list->max_length)
309 : 6219 : enlarge_list(list, list->length + 1);
310 : : /* Now shove the existing data over */
311 : 397597 : memmove(&list->elements[1], &list->elements[0],
312 : : list->length * sizeof(ListCell));
313 : 397597 : list->length++;
314 : 397597 : }
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 : 5597684 : new_tail_cell(List *list)
324 : : {
325 : : /* Enlarge array if necessary */
326 [ + + ]: 5597684 : if (list->length >= list->max_length)
327 : 239704 : enlarge_list(list, list->length + 1);
328 : 5597684 : list->length++;
329 : 5597684 : }
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 : 10426732 : lappend(List *list, void *datum)
340 : : {
341 [ + + + - ]: 10426732 : Assert(IsPointerList(list));
342 : :
343 [ + + ]: 10426732 : if (list == NIL)
344 : 5280434 : list = new_list(T_List, 1);
345 : : else
346 : 5146298 : new_tail_cell(list);
347 : :
348 : 10426732 : llast(list) = datum;
349 : 10426732 : check_list_invariants(list);
350 : 10426732 : return list;
351 : : }
352 : :
353 : : /*
354 : : * Append an integer to the specified list. See lappend()
355 : : */
356 : : List *
357 : 867321 : lappend_int(List *list, int datum)
358 : : {
359 [ + + + - ]: 867321 : Assert(IsIntegerList(list));
360 : :
361 [ + + ]: 867321 : if (list == NIL)
362 : 528227 : list = new_list(T_IntList, 1);
363 : : else
364 : 339094 : new_tail_cell(list);
365 : :
366 : 867321 : llast_int(list) = datum;
367 : 867321 : check_list_invariants(list);
368 : 867321 : return list;
369 : : }
370 : :
371 : : /*
372 : : * Append an OID to the specified list. See lappend()
373 : : */
374 : : List *
375 : 493598 : lappend_oid(List *list, Oid datum)
376 : : {
377 [ + + + - ]: 493598 : Assert(IsOidList(list));
378 : :
379 [ + + ]: 493598 : if (list == NIL)
380 : 381306 : list = new_list(T_OidList, 1);
381 : : else
382 : 112292 : new_tail_cell(list);
383 : :
384 : 493598 : llast_oid(list) = datum;
385 : 493598 : check_list_invariants(list);
386 : 493598 : return list;
387 : : }
388 : :
389 : : /*
390 : : * Append a TransactionId to the specified list. See lappend()
391 : : */
392 : : List *
393 : 0 : lappend_xid(List *list, TransactionId datum)
394 : : {
395 [ # # # # ]: 0 : Assert(IsXidList(list));
396 : :
397 [ # # ]: 0 : if (list == NIL)
398 : 0 : list = new_list(T_XidList, 1);
399 : : else
400 : 0 : new_tail_cell(list);
401 : :
402 : 0 : llast_xid(list) = datum;
403 : 0 : check_list_invariants(list);
404 : 0 : 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 : 89636 : insert_new_cell(List *list, int pos)
416 : : {
417 [ + - ]: 89636 : Assert(pos >= 0 && pos <= list->length);
418 : :
419 : : /* Enlarge array if necessary */
420 [ + + ]: 89636 : if (list->length >= list->max_length)
421 : 69 : enlarge_list(list, list->length + 1);
422 : : /* Now shove the existing data over */
423 [ + + ]: 89636 : if (pos < list->length)
424 : 43124 : memmove(&list->elements[pos + 1], &list->elements[pos],
425 : : (list->length - pos) * sizeof(ListCell));
426 : 89636 : list->length++;
427 : :
428 : 89636 : 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 : 307620 : list_insert_nth(List *list, int pos, void *datum)
440 : : {
441 [ + + ]: 307620 : if (list == NIL)
442 : : {
443 [ + - ]: 217984 : Assert(pos == 0);
444 : 217984 : return list_make1(datum);
445 : : }
446 [ + - + - ]: 89636 : Assert(IsPointerList(list));
447 : 89636 : lfirst(insert_new_cell(list, pos)) = datum;
448 : 89636 : check_list_invariants(list);
449 : 89636 : return list;
450 : 307620 : }
451 : :
452 : : List *
453 : 0 : list_insert_nth_int(List *list, int pos, int datum)
454 : : {
455 [ # # ]: 0 : if (list == NIL)
456 : : {
457 [ # # ]: 0 : Assert(pos == 0);
458 : 0 : return list_make1_int(datum);
459 : : }
460 [ # # # # ]: 0 : Assert(IsIntegerList(list));
461 : 0 : lfirst_int(insert_new_cell(list, pos)) = datum;
462 : 0 : check_list_invariants(list);
463 : 0 : return list;
464 : 0 : }
465 : :
466 : : List *
467 : 0 : list_insert_nth_oid(List *list, int pos, Oid datum)
468 : : {
469 [ # # ]: 0 : if (list == NIL)
470 : : {
471 [ # # ]: 0 : Assert(pos == 0);
472 : 0 : return list_make1_oid(datum);
473 : : }
474 [ # # # # ]: 0 : Assert(IsOidList(list));
475 : 0 : lfirst_oid(insert_new_cell(list, pos)) = datum;
476 : 0 : check_list_invariants(list);
477 : 0 : return list;
478 : 0 : }
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 : 1186173 : lcons(void *datum, List *list)
496 : : {
497 [ + + + - ]: 1186173 : Assert(IsPointerList(list));
498 : :
499 [ + + ]: 1186173 : if (list == NIL)
500 : 796434 : list = new_list(T_List, 1);
501 : : else
502 : 389739 : new_head_cell(list);
503 : :
504 : 1186173 : linitial(list) = datum;
505 : 1186173 : check_list_invariants(list);
506 : 1186173 : return list;
507 : : }
508 : :
509 : : /*
510 : : * Prepend an integer to the list. See lcons()
511 : : */
512 : : List *
513 : 3652 : lcons_int(int datum, List *list)
514 : : {
515 [ + + + - ]: 3652 : Assert(IsIntegerList(list));
516 : :
517 [ + + ]: 3652 : if (list == NIL)
518 : 1602 : list = new_list(T_IntList, 1);
519 : : else
520 : 2050 : new_head_cell(list);
521 : :
522 : 3652 : linitial_int(list) = datum;
523 : 3652 : check_list_invariants(list);
524 : 3652 : return list;
525 : : }
526 : :
527 : : /*
528 : : * Prepend an OID to the list. See lcons()
529 : : */
530 : : List *
531 : 6294 : lcons_oid(Oid datum, List *list)
532 : : {
533 [ + + + - ]: 6294 : Assert(IsOidList(list));
534 : :
535 [ + + ]: 6294 : if (list == NIL)
536 : 486 : list = new_list(T_OidList, 1);
537 : : else
538 : 5808 : new_head_cell(list);
539 : :
540 : 6294 : linitial_oid(list) = datum;
541 : 6294 : check_list_invariants(list);
542 : 6294 : 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 : 592509 : list_concat(List *list1, const List *list2)
562 : : {
563 : 592509 : int new_len;
564 : :
565 [ + + ]: 592509 : if (list1 == NIL)
566 : 426292 : return list_copy(list2);
567 [ + + ]: 166217 : if (list2 == NIL)
568 : 103821 : return list1;
569 : :
570 [ + - ]: 62396 : Assert(list1->type == list2->type);
571 : :
572 : 62396 : new_len = list1->length + list2->length;
573 : : /* Enlarge array if necessary */
574 [ + + ]: 62396 : if (new_len > list1->max_length)
575 : 1614 : enlarge_list(list1, new_len);
576 : :
577 : : /* Even if list1 == list2, using memcpy should be safe here */
578 : 62396 : memcpy(&list1->elements[list1->length], &list2->elements[0],
579 : : list2->length * sizeof(ListCell));
580 : 62396 : list1->length = new_len;
581 : :
582 : 62396 : check_list_invariants(list1);
583 : 62396 : return list1;
584 : 592509 : }
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 : 104563 : list_concat_copy(const List *list1, const List *list2)
599 : : {
600 : 104563 : List *result;
601 : 104563 : int new_len;
602 : :
603 [ + + ]: 104563 : if (list1 == NIL)
604 : 47957 : return list_copy(list2);
605 [ + + ]: 56606 : if (list2 == NIL)
606 : 46846 : return list_copy(list1);
607 : :
608 [ + - ]: 9760 : Assert(list1->type == list2->type);
609 : :
610 : 9760 : new_len = list1->length + list2->length;
611 : 9760 : result = new_list(list1->type, new_len);
612 : 9760 : memcpy(result->elements, list1->elements,
613 : : list1->length * sizeof(ListCell));
614 : 9760 : memcpy(result->elements + list1->length, list2->elements,
615 : : list2->length * sizeof(ListCell));
616 : :
617 : 9760 : check_list_invariants(result);
618 : 9760 : return result;
619 : 104563 : }
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 : 59423 : list_truncate(List *list, int new_size)
632 : : {
633 [ + + ]: 59423 : if (new_size <= 0)
634 : 7885 : return NIL; /* truncate to zero length */
635 : :
636 : : /* If asked to effectively extend the list, do nothing */
637 [ + + ]: 51538 : if (new_size < list_length(list))
638 : 14174 : 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 : 51538 : return list;
651 : 59423 : }
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 : 97742 : list_member(const List *list, const void *datum)
662 : : {
663 : 97742 : const ListCell *cell;
664 : :
665 [ + + + - ]: 97742 : Assert(IsPointerList(list));
666 : 97742 : check_list_invariants(list);
667 : :
668 [ + + + + : 143199 : foreach(cell, list)
+ + + + ]
669 : : {
670 [ + + ]: 45457 : if (equal(lfirst(cell), datum))
671 : 11756 : return true;
672 : 33701 : }
673 : :
674 : 85986 : return false;
675 : 97742 : }
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 : 43169 : list_member_ptr(const List *list, const void *datum)
683 : : {
684 : 43169 : const ListCell *cell;
685 : :
686 [ + + + - ]: 43169 : Assert(IsPointerList(list));
687 : 43169 : check_list_invariants(list);
688 : :
689 [ + + + + : 90619 : foreach(cell, list)
+ + + + ]
690 : : {
691 [ + + ]: 47450 : if (lfirst(cell) == datum)
692 : 18093 : return true;
693 : 29357 : }
694 : :
695 : 25076 : return false;
696 : 43169 : }
697 : :
698 : : /*
699 : : * Return true iff the integer 'datum' is a member of the list.
700 : : */
701 : : bool
702 : 9069 : list_member_int(const List *list, int datum)
703 : : {
704 : 9069 : const ListCell *cell;
705 : :
706 [ + + + - ]: 9069 : Assert(IsIntegerList(list));
707 : 9069 : check_list_invariants(list);
708 : :
709 [ + + + + : 13623 : foreach(cell, list)
+ + + + ]
710 : : {
711 [ + + ]: 4554 : if (lfirst_int(cell) == datum)
712 : 2245 : return true;
713 : 2309 : }
714 : :
715 : 6824 : return false;
716 : 9069 : }
717 : :
718 : : /*
719 : : * Return true iff the OID 'datum' is a member of the list.
720 : : */
721 : : bool
722 : 6626166 : list_member_oid(const List *list, Oid datum)
723 : : {
724 : 6626166 : const ListCell *cell;
725 : :
726 [ + + + - ]: 6626166 : Assert(IsOidList(list));
727 : 6626166 : check_list_invariants(list);
728 : :
729 [ + + + + : 7378981 : foreach(cell, list)
+ + + + ]
730 : : {
731 [ + + ]: 752815 : if (lfirst_oid(cell) == datum)
732 : 106370 : return true;
733 : 646445 : }
734 : :
735 : 6519796 : return false;
736 : 6626166 : }
737 : :
738 : : /*
739 : : * Return true iff the TransactionId 'datum' is a member of the list.
740 : : */
741 : : bool
742 : 0 : list_member_xid(const List *list, TransactionId datum)
743 : : {
744 : 0 : const ListCell *cell;
745 : :
746 [ # # # # ]: 0 : Assert(IsXidList(list));
747 : 0 : check_list_invariants(list);
748 : :
749 [ # # # # : 0 : foreach(cell, list)
# # # # ]
750 : : {
751 [ # # ]: 0 : if (lfirst_xid(cell) == datum)
752 : 0 : return true;
753 : 0 : }
754 : :
755 : 0 : return false;
756 : 0 : }
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 : 830282 : list_delete_nth_cell(List *list, int n)
768 : : {
769 : 830282 : check_list_invariants(list);
770 : :
771 [ + - ]: 830282 : 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 [ + + ]: 830282 : if (list->length == 1)
779 : : {
780 : 555967 : list_free(list);
781 : 555967 : 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 : 274315 : memmove(&list->elements[n], &list->elements[n + 1],
792 : : (list->length - 1 - n) * sizeof(ListCell));
793 : 274315 : 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 : 274315 : return list;
829 : 830282 : }
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 : 671362 : list_delete_cell(List *list, ListCell *cell)
842 : : {
843 : 671362 : 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 : 215 : list_delete(List *list, void *datum)
854 : : {
855 : 215 : ListCell *cell;
856 : :
857 [ + - + - ]: 215 : Assert(IsPointerList(list));
858 : 215 : check_list_invariants(list);
859 : :
860 [ + - - + : 448 : foreach(cell, list)
+ - + - ]
861 : : {
862 [ + + ]: 233 : if (equal(lfirst(cell), datum))
863 : 215 : return list_delete_cell(list, cell);
864 : 18 : }
865 : :
866 : : /* Didn't find a match: return the list unmodified */
867 : 0 : return list;
868 : 215 : }
869 : :
870 : : /* As above, but use simple pointer equality */
871 : : List *
872 : 670408 : list_delete_ptr(List *list, void *datum)
873 : : {
874 : 670408 : ListCell *cell;
875 : :
876 [ + - + - ]: 670408 : Assert(IsPointerList(list));
877 : 670408 : check_list_invariants(list);
878 : :
879 [ + - + + : 1340996 : foreach(cell, list)
+ + + + ]
880 : : {
881 [ + + ]: 670588 : if (lfirst(cell) == datum)
882 : 669683 : return list_delete_cell(list, cell);
883 : 905 : }
884 : :
885 : : /* Didn't find a match: return the list unmodified */
886 : 725 : return list;
887 : 670408 : }
888 : :
889 : : /* As above, but for integers */
890 : : List *
891 : 28 : list_delete_int(List *list, int datum)
892 : : {
893 : 28 : ListCell *cell;
894 : :
895 [ + - + - ]: 28 : Assert(IsIntegerList(list));
896 : 28 : check_list_invariants(list);
897 : :
898 [ + - - + : 57 : foreach(cell, list)
+ - + - ]
899 : : {
900 [ + + ]: 29 : if (lfirst_int(cell) == datum)
901 : 28 : return list_delete_cell(list, cell);
902 : 1 : }
903 : :
904 : : /* Didn't find a match: return the list unmodified */
905 : 0 : return list;
906 : 28 : }
907 : :
908 : : /* As above, but for OIDs */
909 : : List *
910 : 679 : list_delete_oid(List *list, Oid datum)
911 : : {
912 : 679 : ListCell *cell;
913 : :
914 [ + + + - ]: 679 : Assert(IsOidList(list));
915 : 679 : check_list_invariants(list);
916 : :
917 [ + + - + : 880 : foreach(cell, list)
+ + + + ]
918 : : {
919 [ + - ]: 201 : if (lfirst_oid(cell) == datum)
920 : 201 : return list_delete_cell(list, cell);
921 : 0 : }
922 : :
923 : : /* Didn't find a match: return the list unmodified */
924 : 478 : return list;
925 : 679 : }
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 : 80171 : list_delete_first(List *list)
944 : : {
945 : 80171 : check_list_invariants(list);
946 : :
947 [ + - ]: 80171 : if (list == NIL)
948 : 0 : return NIL; /* would an error be better? */
949 : :
950 : 80171 : return list_delete_nth_cell(list, 0);
951 : 80171 : }
952 : :
953 : : /*
954 : : * Delete the last element of the list.
955 : : */
956 : : List *
957 : 8111 : list_delete_last(List *list)
958 : : {
959 : 8111 : check_list_invariants(list);
960 : :
961 [ + - ]: 8111 : 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 [ + + ]: 8111 : if (list_length(list) <= 1)
966 : : {
967 : 3085 : list_free(list);
968 : 3085 : return NIL;
969 : : }
970 : :
971 : 5026 : return list_truncate(list, list_length(list) - 1);
972 : 8111 : }
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 : 51 : list_delete_first_n(List *list, int n)
984 : : {
985 : 51 : check_list_invariants(list);
986 : :
987 : : /* No-op request? */
988 [ - + ]: 51 : if (n <= 0)
989 : 0 : return list;
990 : :
991 : : /* Delete whole list? */
992 [ - + ]: 51 : 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 : 51 : memmove(&list->elements[0], &list->elements[n],
1006 : : (list->length - n) * sizeof(ListCell));
1007 : 51 : 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 : 51 : return list;
1041 : 51 : }
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 : 883 : list_union(const List *list1, const List *list2)
1067 : : {
1068 : 883 : List *result;
1069 : 883 : const ListCell *cell;
1070 : :
1071 [ - + # # ]: 883 : Assert(IsPointerList(list1));
1072 [ + + + - ]: 883 : Assert(IsPointerList(list2));
1073 : :
1074 : 883 : result = list_copy(list1);
1075 [ + + + + : 1827 : foreach(cell, list2)
+ + ]
1076 : : {
1077 [ + + ]: 944 : if (!list_member(result, lfirst(cell)))
1078 : 929 : result = lappend(result, lfirst(cell));
1079 : 944 : }
1080 : :
1081 : 883 : check_list_invariants(result);
1082 : 1766 : return result;
1083 : 883 : }
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 : 0 : List *result;
1093 : 0 : const ListCell *cell;
1094 : :
1095 [ # # # # ]: 0 : Assert(IsPointerList(list1));
1096 [ # # # # ]: 0 : 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 : 0 : }
1104 : :
1105 : 0 : check_list_invariants(result);
1106 : 0 : return result;
1107 : 0 : }
1108 : :
1109 : : /*
1110 : : * This variant of list_union() operates upon lists of integers.
1111 : : */
1112 : : List *
1113 : 1085 : list_union_int(const List *list1, const List *list2)
1114 : : {
1115 : 1085 : List *result;
1116 : 1085 : const ListCell *cell;
1117 : :
1118 [ + + + - ]: 1085 : Assert(IsIntegerList(list1));
1119 [ + + + - ]: 1085 : Assert(IsIntegerList(list2));
1120 : :
1121 : 1085 : result = list_copy(list1);
1122 [ + + + + : 2163 : foreach(cell, list2)
+ + ]
1123 : : {
1124 [ + + ]: 1078 : if (!list_member_int(result, lfirst_int(cell)))
1125 : 1044 : result = lappend_int(result, lfirst_int(cell));
1126 : 1078 : }
1127 : :
1128 : 1085 : check_list_invariants(result);
1129 : 2170 : return result;
1130 : 1085 : }
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 : 0 : List *result;
1139 : 0 : const ListCell *cell;
1140 : :
1141 [ # # # # ]: 0 : Assert(IsOidList(list1));
1142 [ # # # # ]: 0 : 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 : 0 : }
1150 : :
1151 : 0 : check_list_invariants(result);
1152 : 0 : return result;
1153 : 0 : }
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 : 0 : List *result;
1177 : 0 : const ListCell *cell;
1178 : :
1179 [ # # # # ]: 0 : if (list1 == NIL || list2 == NIL)
1180 : 0 : return NIL;
1181 : :
1182 [ # # # # ]: 0 : Assert(IsPointerList(list1));
1183 [ # # # # ]: 0 : 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 : 0 : }
1191 : :
1192 : 0 : check_list_invariants(result);
1193 : 0 : return result;
1194 : 0 : }
1195 : :
1196 : : /*
1197 : : * As list_intersection but operates on lists of integers.
1198 : : */
1199 : : List *
1200 : 77 : list_intersection_int(const List *list1, const List *list2)
1201 : : {
1202 : 77 : List *result;
1203 : 77 : const ListCell *cell;
1204 : :
1205 [ + - - + ]: 77 : if (list1 == NIL || list2 == NIL)
1206 : 0 : return NIL;
1207 : :
1208 [ + - + - ]: 77 : Assert(IsIntegerList(list1));
1209 [ + - + - ]: 77 : Assert(IsIntegerList(list2));
1210 : :
1211 : 77 : result = NIL;
1212 [ + - + + : 162 : foreach(cell, list1)
+ + ]
1213 : : {
1214 [ + + ]: 85 : if (list_member_int(list2, lfirst_int(cell)))
1215 : 39 : result = lappend_int(result, lfirst_int(cell));
1216 : 85 : }
1217 : :
1218 : 77 : check_list_invariants(result);
1219 : 77 : return result;
1220 : 77 : }
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 : 4073 : list_difference(const List *list1, const List *list2)
1238 : : {
1239 : 4073 : const ListCell *cell;
1240 : 4073 : List *result = NIL;
1241 : :
1242 [ + + + - ]: 4073 : Assert(IsPointerList(list1));
1243 [ + + + - ]: 4073 : Assert(IsPointerList(list2));
1244 : :
1245 [ + + ]: 4073 : if (list2 == NIL)
1246 : 191 : return list_copy(list1);
1247 : :
1248 [ + - + + : 8406 : foreach(cell, list1)
+ + ]
1249 : : {
1250 [ + + ]: 4524 : if (!list_member(list2, lfirst(cell)))
1251 : 138 : result = lappend(result, lfirst(cell));
1252 : 4524 : }
1253 : :
1254 : 3882 : check_list_invariants(result);
1255 : 3882 : return result;
1256 : 4073 : }
1257 : :
1258 : : /*
1259 : : * This variant of list_difference() determines list membership via
1260 : : * simple pointer equality.
1261 : : */
1262 : : List *
1263 : 2874 : list_difference_ptr(const List *list1, const List *list2)
1264 : : {
1265 : 2874 : const ListCell *cell;
1266 : 2874 : List *result = NIL;
1267 : :
1268 [ + + + - ]: 2874 : Assert(IsPointerList(list1));
1269 [ + + + - ]: 2874 : Assert(IsPointerList(list2));
1270 : :
1271 [ + + ]: 2874 : if (list2 == NIL)
1272 : 2364 : return list_copy(list1);
1273 : :
1274 [ + + + + : 1402 : foreach(cell, list1)
+ + ]
1275 : : {
1276 [ + + ]: 892 : if (!list_member_ptr(list2, lfirst(cell)))
1277 : 307 : result = lappend(result, lfirst(cell));
1278 : 892 : }
1279 : :
1280 : 510 : check_list_invariants(result);
1281 : 510 : return result;
1282 : 2874 : }
1283 : :
1284 : : /*
1285 : : * This variant of list_difference() operates upon lists of integers.
1286 : : */
1287 : : List *
1288 : 491 : list_difference_int(const List *list1, const List *list2)
1289 : : {
1290 : 491 : const ListCell *cell;
1291 : 491 : List *result = NIL;
1292 : :
1293 [ + + + - ]: 491 : Assert(IsIntegerList(list1));
1294 [ + + + - ]: 491 : Assert(IsIntegerList(list2));
1295 : :
1296 [ + + ]: 491 : if (list2 == NIL)
1297 : 369 : return list_copy(list1);
1298 : :
1299 [ + - + + : 362 : foreach(cell, list1)
+ + ]
1300 : : {
1301 [ + + ]: 240 : if (!list_member_int(list2, lfirst_int(cell)))
1302 : 98 : result = lappend_int(result, lfirst_int(cell));
1303 : 240 : }
1304 : :
1305 : 122 : check_list_invariants(result);
1306 : 122 : return result;
1307 : 491 : }
1308 : :
1309 : : /*
1310 : : * This variant of list_difference() operates upon lists of OIDs.
1311 : : */
1312 : : List *
1313 : 66 : list_difference_oid(const List *list1, const List *list2)
1314 : : {
1315 : 66 : const ListCell *cell;
1316 : 66 : List *result = NIL;
1317 : :
1318 [ + + + - ]: 66 : Assert(IsOidList(list1));
1319 [ + + + - ]: 66 : Assert(IsOidList(list2));
1320 : :
1321 [ + + ]: 66 : if (list2 == NIL)
1322 : 60 : return list_copy(list1);
1323 : :
1324 [ + + + + : 9 : foreach(cell, list1)
+ + ]
1325 : : {
1326 [ + + ]: 3 : if (!list_member_oid(list2, lfirst_oid(cell)))
1327 : 1 : result = lappend_oid(result, lfirst_oid(cell));
1328 : 3 : }
1329 : :
1330 : 6 : check_list_invariants(result);
1331 : 6 : return result;
1332 : 66 : }
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 : 16205 : list_append_unique(List *list, void *datum)
1344 : : {
1345 [ + + ]: 16205 : if (list_member(list, datum))
1346 : 1007 : return list;
1347 : : else
1348 : 15198 : return lappend(list, datum);
1349 : 16205 : }
1350 : :
1351 : : /*
1352 : : * This variant of list_append_unique() determines list membership via
1353 : : * simple pointer equality.
1354 : : */
1355 : : List *
1356 : 30059 : list_append_unique_ptr(List *list, void *datum)
1357 : : {
1358 [ + + ]: 30059 : if (list_member_ptr(list, datum))
1359 : 12587 : return list;
1360 : : else
1361 : 17472 : return lappend(list, datum);
1362 : 30059 : }
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 : 0 : }
1375 : :
1376 : : /*
1377 : : * This variant of list_append_unique() operates upon lists of OIDs.
1378 : : */
1379 : : List *
1380 : 792 : list_append_unique_oid(List *list, Oid datum)
1381 : : {
1382 [ + + ]: 792 : if (list_member_oid(list, datum))
1383 : 245 : return list;
1384 : : else
1385 : 547 : return lappend_oid(list, datum);
1386 : 792 : }
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 : 525 : list_concat_unique(List *list1, const List *list2)
1406 : : {
1407 : 525 : ListCell *cell;
1408 : :
1409 [ + + + - ]: 525 : Assert(IsPointerList(list1));
1410 [ + + + - ]: 525 : Assert(IsPointerList(list2));
1411 : :
1412 [ + + + + : 970 : foreach(cell, list2)
+ + ]
1413 : : {
1414 [ + + ]: 445 : if (!list_member(list1, lfirst(cell)))
1415 : 439 : list1 = lappend(list1, lfirst(cell));
1416 : 445 : }
1417 : :
1418 : 525 : check_list_invariants(list1);
1419 : 1050 : return list1;
1420 : 525 : }
1421 : :
1422 : : /*
1423 : : * This variant of list_concat_unique() determines list membership via
1424 : : * simple pointer equality.
1425 : : */
1426 : : List *
1427 : 144 : list_concat_unique_ptr(List *list1, const List *list2)
1428 : : {
1429 : 144 : ListCell *cell;
1430 : :
1431 [ + + + - ]: 144 : Assert(IsPointerList(list1));
1432 [ + - + - ]: 144 : Assert(IsPointerList(list2));
1433 : :
1434 [ + - + + : 484 : foreach(cell, list2)
+ + ]
1435 : : {
1436 [ + + ]: 340 : if (!list_member_ptr(list1, lfirst(cell)))
1437 : 128 : list1 = lappend(list1, lfirst(cell));
1438 : 340 : }
1439 : :
1440 : 144 : check_list_invariants(list1);
1441 : 288 : return list1;
1442 : 144 : }
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 : 0 : ListCell *cell;
1451 : :
1452 [ # # # # ]: 0 : Assert(IsIntegerList(list1));
1453 [ # # # # ]: 0 : 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 : 0 : }
1460 : :
1461 : 0 : check_list_invariants(list1);
1462 : 0 : return list1;
1463 : 0 : }
1464 : :
1465 : : /*
1466 : : * This variant of list_concat_unique() operates upon lists of OIDs.
1467 : : */
1468 : : List *
1469 : 2688 : list_concat_unique_oid(List *list1, const List *list2)
1470 : : {
1471 : 2688 : ListCell *cell;
1472 : :
1473 [ + + + - ]: 2688 : Assert(IsOidList(list1));
1474 [ + + + - ]: 2688 : Assert(IsOidList(list2));
1475 : :
1476 [ + + + + : 3120 : foreach(cell, list2)
+ + ]
1477 : : {
1478 [ + + ]: 432 : if (!list_member_oid(list1, lfirst_oid(cell)))
1479 : 304 : list1 = lappend_oid(list1, lfirst_oid(cell));
1480 : 432 : }
1481 : :
1482 : 2688 : check_list_invariants(list1);
1483 : 5376 : return list1;
1484 : 2688 : }
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 : 247 : list_deduplicate_oid(List *list)
1496 : : {
1497 : 247 : int len;
1498 : :
1499 [ + + + - ]: 247 : Assert(IsOidList(list));
1500 : 247 : len = list_length(list);
1501 [ + + ]: 247 : if (len > 1)
1502 : : {
1503 : 31 : ListCell *elements = list->elements;
1504 : 31 : int i = 0;
1505 : :
1506 [ + + ]: 86 : for (int j = 1; j < len; j++)
1507 : : {
1508 [ + + ]: 55 : if (elements[i].oid_value != elements[j].oid_value)
1509 : 48 : elements[++i].oid_value = elements[j].oid_value;
1510 : 55 : }
1511 : 31 : list->length = i + 1;
1512 : 31 : }
1513 : 247 : check_list_invariants(list);
1514 : 247 : }
1515 : :
1516 : : /*
1517 : : * Free all storage in a list, and optionally the pointed-to elements
1518 : : */
1519 : : static void
1520 : 3113438 : list_free_private(List *list, bool deep)
1521 : : {
1522 [ + + ]: 3113438 : if (list == NIL)
1523 : 1825028 : return; /* nothing to do */
1524 : :
1525 : 1288410 : check_list_invariants(list);
1526 : :
1527 [ + + ]: 1288410 : if (deep)
1528 : : {
1529 [ + + ]: 130269 : for (int i = 0; i < list->length; i++)
1530 : 95069 : pfree(lfirst(&list->elements[i]));
1531 : 35200 : }
1532 [ + + ]: 1288410 : if (list->elements != list->initial_elements)
1533 : 15355 : pfree(list->elements);
1534 : 1288410 : pfree(list);
1535 : 3113438 : }
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 : 2928510 : list_free(List *list)
1547 : : {
1548 : 2928510 : list_free_private(list, false);
1549 : 2928510 : }
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 : 184928 : list_free_deep(List *list)
1561 : : {
1562 : : /*
1563 : : * A "deep" free operation only makes sense on a list of pointers.
1564 : : */
1565 [ + + + - ]: 184928 : Assert(IsPointerList(list));
1566 : 184928 : list_free_private(list, true);
1567 : 184928 : }
1568 : :
1569 : : /*
1570 : : * Return a shallow copy of the specified list.
1571 : : */
1572 : : List *
1573 : 890086 : list_copy(const List *oldlist)
1574 : : {
1575 : 890086 : List *newlist;
1576 : :
1577 [ + + ]: 890086 : if (oldlist == NIL)
1578 : 230106 : return NIL;
1579 : :
1580 : 659980 : newlist = new_list(oldlist->type, oldlist->length);
1581 : 659980 : memcpy(newlist->elements, oldlist->elements,
1582 : : newlist->length * sizeof(ListCell));
1583 : :
1584 : 659980 : check_list_invariants(newlist);
1585 : 659980 : return newlist;
1586 : 890086 : }
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 : 96635 : list_copy_head(const List *oldlist, int len)
1594 : : {
1595 : 96635 : List *newlist;
1596 : :
1597 [ + - + + ]: 96635 : if (oldlist == NIL || len <= 0)
1598 : 92495 : return NIL;
1599 : :
1600 [ - + ]: 4140 : len = Min(oldlist->length, len);
1601 : :
1602 : 4140 : newlist = new_list(oldlist->type, len);
1603 : 4140 : memcpy(newlist->elements, oldlist->elements, len * sizeof(ListCell));
1604 : :
1605 : 4140 : check_list_invariants(newlist);
1606 : 4140 : return newlist;
1607 : 96635 : }
1608 : :
1609 : : /*
1610 : : * Return a shallow copy of the specified list, without the first N elements.
1611 : : */
1612 : : List *
1613 : 10117 : list_copy_tail(const List *oldlist, int nskip)
1614 : : {
1615 : 10117 : List *newlist;
1616 : :
1617 [ + - ]: 10117 : if (nskip < 0)
1618 : 0 : nskip = 0; /* would it be better to elog? */
1619 : :
1620 [ + - + + ]: 10117 : if (oldlist == NIL || nskip >= oldlist->length)
1621 : 373 : return NIL;
1622 : :
1623 : 9744 : newlist = new_list(oldlist->type, oldlist->length - nskip);
1624 : 9744 : memcpy(newlist->elements, &oldlist->elements[nskip],
1625 : : newlist->length * sizeof(ListCell));
1626 : :
1627 : 9744 : check_list_invariants(newlist);
1628 : 9744 : return newlist;
1629 : 10117 : }
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 : 426458 : list_copy_deep(const List *oldlist)
1640 : : {
1641 : 426458 : List *newlist;
1642 : :
1643 [ + - ]: 426458 : if (oldlist == NIL)
1644 : 0 : return NIL;
1645 : :
1646 : : /* This is only sensible for pointer Lists */
1647 [ + - ]: 426458 : Assert(IsA(oldlist, List));
1648 : :
1649 : 426458 : newlist = new_list(oldlist->type, oldlist->length);
1650 [ + + ]: 1671530 : for (int i = 0; i < newlist->length; i++)
1651 : 1245072 : lfirst(&newlist->elements[i]) =
1652 : 1245072 : copyObjectImpl(lfirst(&oldlist->elements[i]));
1653 : :
1654 : 426458 : check_list_invariants(newlist);
1655 : 426458 : return newlist;
1656 : 426458 : }
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 : 30548 : list_sort(List *list, list_sort_comparator cmp)
1675 : : {
1676 : : typedef int (*qsort_comparator) (const void *a, const void *b);
1677 : 30548 : int len;
1678 : :
1679 : 30548 : check_list_invariants(list);
1680 : :
1681 : : /* Nothing to do if there's less than two elements */
1682 : 30548 : len = list_length(list);
1683 [ + + ]: 30548 : if (len > 1)
1684 : 7763 : qsort(list->elements, len, sizeof(ListCell), (qsort_comparator) cmp);
1685 : 30548 : }
1686 : :
1687 : : /*
1688 : : * list_sort comparator for sorting a list into ascending int order.
1689 : : */
1690 : : int
1691 : 12 : list_int_cmp(const ListCell *p1, const ListCell *p2)
1692 : : {
1693 : 12 : int v1 = lfirst_int(p1);
1694 : 12 : int v2 = lfirst_int(p2);
1695 : :
1696 : 24 : return pg_cmp_s32(v1, v2);
1697 : 12 : }
1698 : :
1699 : : /*
1700 : : * list_sort comparator for sorting a list into ascending OID order.
1701 : : */
1702 : : int
1703 : 5546 : list_oid_cmp(const ListCell *p1, const ListCell *p2)
1704 : : {
1705 : 5546 : Oid v1 = lfirst_oid(p1);
1706 : 5546 : Oid v2 = lfirst_oid(p2);
1707 : :
1708 : 11092 : return pg_cmp_u32(v1, v2);
1709 : 5546 : }
|
