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