Age Owner Branch data 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-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
5377 peter_e@gmx.net 65 :CBC 177488271 : check_list_invariants(const List *list)
66 : : {
8128 neilc@samurai.com 67 [ + + ]: 177488271 : if (list == NIL)
68 : 60509434 : return;
69 : :
70 [ - + ]: 116978837 : Assert(list->length > 0);
2600 tgl@sss.pgh.pa.us 71 [ - + ]: 116978837 : Assert(list->length <= list->max_length);
72 [ - + ]: 116978837 : Assert(list->elements != NULL);
73 : :
8128 neilc@samurai.com 74 [ + + + + : 116978837 : Assert(list->type == T_List ||
+ + - + ]
75 : : list->type == T_IntList ||
76 : : list->type == T_OidList ||
77 : : list->type == T_XidList);
78 : : }
79 : : #else
80 : : #define check_list_invariants(l) ((void) 0)
81 : : #endif /* USE_ASSERT_CHECKING */
82 : :
83 : : /*
84 : : * Return a freshly allocated List with room for at least min_size cells.
85 : : *
86 : : * Since empty non-NIL lists are invalid, new_list() sets the initial length
87 : : * to min_size, effectively marking that number of cells as valid; the caller
88 : : * is responsible for filling in their data.
89 : : */
90 : : static List *
2600 tgl@sss.pgh.pa.us 91 : 58589015 : new_list(NodeTag type, int min_size)
92 : : {
93 : : List *newlist;
94 : : int max_size;
95 : :
96 [ - + ]: 58589015 : 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 : : */
2332 drowley@postgresql.o 126 : 58589015 : max_size = pg_nextpower2_32(Max(8, min_size + LIST_HEADER_OVERHEAD));
2600 tgl@sss.pgh.pa.us 127 : 58589015 : 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 : 58589015 : newlist = (List *) palloc(offsetof(List, initial_elements) +
138 : : max_size * sizeof(ListCell));
139 : 58589015 : newlist->type = type;
140 : 58589015 : newlist->length = min_size;
141 : 58589015 : newlist->max_length = max_size;
142 : 58589015 : newlist->elements = newlist->initial_elements;
143 : :
144 : 58589015 : return newlist;
145 : : }
146 : :
147 : : /*
148 : : * Enlarge an existing non-NIL List to have room for at least min_size cells.
149 : : *
150 : : * This does *not* update list->length, as some callers would find that
151 : : * inconvenient. (list->length had better be the correct number of existing
152 : : * valid cells, though.)
153 : : */
154 : : static void
155 : 2411678 : enlarge_list(List *list, int min_size)
156 : : {
157 : : int new_max_len;
158 : :
159 [ - + ]: 2411678 : 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 */
2332 drowley@postgresql.o 169 : 2411678 : 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 : :
2600 tgl@sss.pgh.pa.us 176 [ + + ]: 2411678 : 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 : 1618279 : list->elements = (ListCell *)
186 : 1618279 : MemoryContextAlloc(GetMemoryChunkContext(list),
187 : : new_max_len * sizeof(ListCell));
188 : 1618279 : memcpy(list->elements, list->initial_elements,
189 : 1618279 : 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
2517 198 : 1618279 : wipe_mem(list->initial_elements,
199 : 1618279 : list->max_length * sizeof(ListCell));
200 : : #else
201 : : VALGRIND_MAKE_MEM_NOACCESS(list->initial_elements,
202 : : list->max_length * sizeof(ListCell));
203 : : #endif
204 : : }
205 : : else
206 : : {
207 : : #ifndef DEBUG_LIST_MEMORY_USAGE
208 : : /* Normally, let repalloc deal with enlargement */
10 michael@paquier.xyz 209 :GNC 793399 : list->elements = repalloc_array(list->elements, ListCell, new_max_len);
210 : : #else
211 : : /*
212 : : * repalloc() might enlarge the space in-place, which we don't want
213 : : * for debugging purposes, so forcibly move the data somewhere else.
214 : : */
215 : : ListCell *newelements;
216 : :
217 : : newelements = (ListCell *)
218 : : MemoryContextAlloc(GetMemoryChunkContext(list),
219 : : new_max_len * sizeof(ListCell));
220 : : memcpy(newelements, list->elements,
221 : : list->length * sizeof(ListCell));
222 : : pfree(list->elements);
223 : : list->elements = newelements;
224 : : #endif
225 : : }
226 : :
2600 tgl@sss.pgh.pa.us 227 :CBC 2411678 : list->max_length = new_max_len;
228 : 2411678 : }
229 : :
230 : : /*
231 : : * Convenience functions to construct short Lists from given values.
232 : : * (These are normally invoked via the list_makeN macros.)
233 : : */
234 : : List *
235 : 9297062 : list_make1_impl(NodeTag t, ListCell datum1)
236 : : {
237 : 9297062 : List *list = new_list(t, 1);
238 : :
239 : 9297062 : list->elements[0] = datum1;
240 : 9297062 : check_list_invariants(list);
241 : 9297062 : return list;
242 : : }
243 : :
244 : : List *
245 : 1149309 : list_make2_impl(NodeTag t, ListCell datum1, ListCell datum2)
246 : : {
247 : 1149309 : List *list = new_list(t, 2);
248 : :
249 : 1149309 : list->elements[0] = datum1;
250 : 1149309 : list->elements[1] = datum2;
251 : 1149309 : check_list_invariants(list);
252 : 1149309 : return list;
253 : : }
254 : :
255 : : List *
256 : 5030 : list_make3_impl(NodeTag t, ListCell datum1, ListCell datum2,
257 : : ListCell datum3)
258 : : {
259 : 5030 : List *list = new_list(t, 3);
260 : :
261 : 5030 : list->elements[0] = datum1;
262 : 5030 : list->elements[1] = datum2;
263 : 5030 : list->elements[2] = datum3;
264 : 5030 : check_list_invariants(list);
265 : 5030 : return list;
266 : : }
267 : :
268 : : List *
269 : 133 : list_make4_impl(NodeTag t, ListCell datum1, ListCell datum2,
270 : : ListCell datum3, ListCell datum4)
271 : : {
272 : 133 : List *list = new_list(t, 4);
273 : :
274 : 133 : list->elements[0] = datum1;
275 : 133 : list->elements[1] = datum2;
276 : 133 : list->elements[2] = datum3;
277 : 133 : list->elements[3] = datum4;
278 : 133 : check_list_invariants(list);
279 : 133 : return list;
280 : : }
281 : :
282 : : List *
2045 tomas.vondra@postgre 283 : 172 : list_make5_impl(NodeTag t, ListCell datum1, ListCell datum2,
284 : : ListCell datum3, ListCell datum4, ListCell datum5)
285 : : {
286 : 172 : List *list = new_list(t, 5);
287 : :
288 : 172 : list->elements[0] = datum1;
289 : 172 : list->elements[1] = datum2;
290 : 172 : list->elements[2] = datum3;
291 : 172 : list->elements[3] = datum4;
292 : 172 : list->elements[4] = datum5;
293 : 172 : check_list_invariants(list);
294 : 172 : return list;
295 : : }
296 : :
297 : : /*
298 : : * Make room for a new head cell in the given (non-NIL) list.
299 : : *
300 : : * The data in the new head cell is undefined; the caller should be
301 : : * sure to fill it in
302 : : */
303 : : static void
8128 neilc@samurai.com 304 : 2251713 : new_head_cell(List *list)
305 : : {
306 : : /* Enlarge array if necessary */
2600 tgl@sss.pgh.pa.us 307 [ + + ]: 2251713 : if (list->length >= list->max_length)
308 : 40107 : enlarge_list(list, list->length + 1);
309 : : /* Now shove the existing data over */
310 : 2251713 : memmove(&list->elements[1], &list->elements[0],
311 : 2251713 : list->length * sizeof(ListCell));
8128 neilc@samurai.com 312 : 2251713 : list->length++;
10760 scrappy@hub.org 313 : 2251713 : }
314 : :
315 : : /*
316 : : * Make room for a new tail cell in the given (non-NIL) list.
317 : : *
318 : : * The data in the new tail cell is undefined; the caller should be
319 : : * sure to fill it in
320 : : */
321 : : static void
8128 neilc@samurai.com 322 : 41609214 : new_tail_cell(List *list)
323 : : {
324 : : /* Enlarge array if necessary */
2600 tgl@sss.pgh.pa.us 325 [ + + ]: 41609214 : if (list->length >= list->max_length)
326 : 2351371 : enlarge_list(list, list->length + 1);
8128 neilc@samurai.com 327 : 41609214 : list->length++;
8600 tgl@sss.pgh.pa.us 328 : 41609214 : }
329 : :
330 : : /*
331 : : * Append a pointer to the list. A pointer to the modified list is
332 : : * returned. Note that this function may or may not destructively
333 : : * modify the list; callers should always use this function's return
334 : : * value, rather than continuing to use the pointer passed as the
335 : : * first argument.
336 : : */
337 : : List *
8492 338 : 68419322 : lappend(List *list, void *datum)
339 : : {
8128 neilc@samurai.com 340 [ + + - + ]: 68419322 : Assert(IsPointerList(list));
341 : :
342 [ + + ]: 68419322 : if (list == NIL)
2600 tgl@sss.pgh.pa.us 343 : 31306758 : list = new_list(T_List, 1);
344 : : else
8128 neilc@samurai.com 345 : 37112564 : new_tail_cell(list);
346 : :
2160 tgl@sss.pgh.pa.us 347 : 68419322 : llast(list) = datum;
8128 neilc@samurai.com 348 : 68419322 : check_list_invariants(list);
349 : 68419322 : return list;
350 : : }
351 : :
352 : : /*
353 : : * Append an integer to the specified list. See lappend()
354 : : */
355 : : List *
356 : 4450801 : lappend_int(List *list, int datum)
357 : : {
358 [ + + - + ]: 4450801 : Assert(IsIntegerList(list));
359 : :
360 [ + + ]: 4450801 : if (list == NIL)
2600 tgl@sss.pgh.pa.us 361 : 989207 : list = new_list(T_IntList, 1);
362 : : else
8128 neilc@samurai.com 363 : 3461594 : new_tail_cell(list);
364 : :
2160 tgl@sss.pgh.pa.us 365 : 4450801 : llast_int(list) = datum;
8128 neilc@samurai.com 366 : 4450801 : check_list_invariants(list);
367 : 4450801 : return list;
368 : : }
369 : :
370 : : /*
371 : : * Append an OID to the specified list. See lappend()
372 : : */
373 : : List *
374 : 4232156 : lappend_oid(List *list, Oid datum)
375 : : {
376 [ + + - + ]: 4232156 : Assert(IsOidList(list));
377 : :
378 [ + + ]: 4232156 : if (list == NIL)
2600 tgl@sss.pgh.pa.us 379 : 3197135 : list = new_list(T_OidList, 1);
380 : : else
8128 neilc@samurai.com 381 : 1035021 : new_tail_cell(list);
382 : :
2160 tgl@sss.pgh.pa.us 383 : 4232156 : llast_oid(list) = datum;
8128 neilc@samurai.com 384 : 4232156 : check_list_invariants(list);
385 : 4232156 : return list;
386 : : }
387 : :
388 : : /*
389 : : * Append a TransactionId to the specified list. See lappend()
390 : : */
391 : : List *
1515 alvherre@alvh.no-ip. 392 : 92 : lappend_xid(List *list, TransactionId datum)
393 : : {
394 [ + + - + ]: 92 : Assert(IsXidList(list));
395 : :
396 [ + + ]: 92 : if (list == NIL)
397 : 57 : list = new_list(T_XidList, 1);
398 : : else
399 : 35 : new_tail_cell(list);
400 : :
401 : 92 : llast_xid(list) = datum;
402 : 92 : check_list_invariants(list);
403 : 92 : return list;
404 : : }
405 : :
406 : : /*
407 : : * Make room for a new cell at position 'pos' (measured from 0).
408 : : * The data in the cell is left undefined, and must be filled in by the
409 : : * caller. 'list' is assumed to be non-NIL, and 'pos' must be a valid
410 : : * list position, ie, 0 <= pos <= list's length.
411 : : * Returns address of the new cell.
412 : : */
413 : : static ListCell *
2600 tgl@sss.pgh.pa.us 414 : 735937 : insert_new_cell(List *list, int pos)
415 : : {
416 [ + - - + ]: 735937 : Assert(pos >= 0 && pos <= list->length);
417 : :
418 : : /* Enlarge array if necessary */
419 [ + + ]: 735937 : if (list->length >= list->max_length)
420 : 1324 : enlarge_list(list, list->length + 1);
421 : : /* Now shove the existing data over */
422 [ + + ]: 735937 : if (pos < list->length)
423 : 317532 : memmove(&list->elements[pos + 1], &list->elements[pos],
424 : 317532 : (list->length - pos) * sizeof(ListCell));
425 : 735937 : list->length++;
426 : :
427 : 735937 : return &list->elements[pos];
428 : : }
429 : :
430 : : /*
431 : : * Insert the given datum at position 'pos' (measured from 0) in the list.
432 : : * 'pos' must be valid, ie, 0 <= pos <= list's length.
433 : : *
434 : : * Note that this takes time proportional to the distance to the end of the
435 : : * list, since the following entries must be moved.
436 : : */
437 : : List *
438 : 2393572 : list_insert_nth(List *list, int pos, void *datum)
439 : : {
440 [ + + ]: 2393572 : if (list == NIL)
441 : : {
442 [ - + ]: 1657635 : Assert(pos == 0);
443 : 1657635 : return list_make1(datum);
444 : : }
445 [ + - - + ]: 735937 : Assert(IsPointerList(list));
446 : 735937 : lfirst(insert_new_cell(list, pos)) = datum;
447 : 735937 : check_list_invariants(list);
448 : 735937 : return list;
449 : : }
450 : :
451 : : List *
2600 tgl@sss.pgh.pa.us 452 :UBC 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 : : }
459 [ # # # # ]: 0 : Assert(IsIntegerList(list));
460 : 0 : lfirst_int(insert_new_cell(list, pos)) = datum;
461 : 0 : check_list_invariants(list);
462 : 0 : return list;
463 : : }
464 : :
465 : : List *
466 : 0 : list_insert_nth_oid(List *list, int pos, Oid datum)
467 : : {
468 [ # # ]: 0 : if (list == NIL)
469 : : {
470 [ # # ]: 0 : Assert(pos == 0);
471 : 0 : return list_make1_oid(datum);
472 : : }
473 [ # # # # ]: 0 : Assert(IsOidList(list));
474 : 0 : lfirst_oid(insert_new_cell(list, pos)) = datum;
475 : 0 : check_list_invariants(list);
476 : 0 : return list;
477 : : }
478 : :
479 : : /*
480 : : * Prepend a new element to the list. A pointer to the modified list
481 : : * is returned. Note that this function may or may not destructively
482 : : * modify the list; callers should always use this function's return
483 : : * value, rather than continuing to use the pointer passed as the
484 : : * second argument.
485 : : *
486 : : * Note that this takes time proportional to the length of the list,
487 : : * since the existing entries must be moved.
488 : : *
489 : : * Caution: before Postgres 8.0, the original List was unmodified and
490 : : * could be considered to retain its separate identity. This is no longer
491 : : * the case.
492 : : */
493 : : List *
8128 neilc@samurai.com 494 :CBC 5354665 : lcons(void *datum, List *list)
495 : : {
496 [ + + - + ]: 5354665 : Assert(IsPointerList(list));
497 : :
498 [ + + ]: 5354665 : if (list == NIL)
2600 tgl@sss.pgh.pa.us 499 : 3139186 : list = new_list(T_List, 1);
500 : : else
8128 neilc@samurai.com 501 : 2215479 : new_head_cell(list);
502 : :
2160 tgl@sss.pgh.pa.us 503 : 5354665 : linitial(list) = datum;
8128 neilc@samurai.com 504 : 5354665 : check_list_invariants(list);
505 : 5354665 : return list;
506 : : }
507 : :
508 : : /*
509 : : * Prepend an integer to the list. See lcons()
510 : : */
511 : : List *
512 : 17266 : lcons_int(int datum, List *list)
513 : : {
514 [ + + - + ]: 17266 : Assert(IsIntegerList(list));
515 : :
516 [ + + ]: 17266 : if (list == NIL)
2600 tgl@sss.pgh.pa.us 517 : 7825 : list = new_list(T_IntList, 1);
518 : : else
8128 neilc@samurai.com 519 : 9441 : new_head_cell(list);
520 : :
2160 tgl@sss.pgh.pa.us 521 : 17266 : linitial_int(list) = datum;
8128 neilc@samurai.com 522 : 17266 : check_list_invariants(list);
523 : 17266 : return list;
524 : : }
525 : :
526 : : /*
527 : : * Prepend an OID to the list. See lcons()
528 : : */
529 : : List *
530 : 28648 : lcons_oid(Oid datum, List *list)
531 : : {
532 [ + + - + ]: 28648 : Assert(IsOidList(list));
533 : :
534 [ + + ]: 28648 : if (list == NIL)
2600 tgl@sss.pgh.pa.us 535 : 1855 : list = new_list(T_OidList, 1);
536 : : else
8128 neilc@samurai.com 537 : 26793 : new_head_cell(list);
538 : :
2160 tgl@sss.pgh.pa.us 539 : 28648 : linitial_oid(list) = datum;
8128 neilc@samurai.com 540 : 28648 : check_list_invariants(list);
541 : 28648 : return list;
542 : : }
543 : :
544 : : /*
545 : : * Concatenate list2 to the end of list1, and return list1.
546 : : *
547 : : * This is equivalent to lappend'ing each element of list2, in order, to list1.
548 : : * list1 is destructively changed, list2 is not. (However, in the case of
549 : : * pointer lists, list1 and list2 will point to the same structures.)
550 : : *
551 : : * Callers should be sure to use the return value as the new pointer to the
552 : : * concatenated list: the 'list1' input pointer may or may not be the same
553 : : * as the returned pointer.
554 : : *
555 : : * Note that this takes at least time proportional to the length of list2.
556 : : * It'd typically be the case that we have to enlarge list1's storage,
557 : : * probably adding time proportional to the length of list1.
558 : : */
559 : : List *
2600 tgl@sss.pgh.pa.us 560 : 5041328 : list_concat(List *list1, const List *list2)
561 : : {
562 : : int new_len;
563 : :
8128 neilc@samurai.com 564 [ + + ]: 5041328 : if (list1 == NIL)
2600 tgl@sss.pgh.pa.us 565 : 3542211 : return list_copy(list2);
8128 neilc@samurai.com 566 [ + + ]: 1499117 : if (list2 == NIL)
567 : 873805 : return list1;
568 : :
569 [ - + ]: 625312 : Assert(list1->type == list2->type);
570 : :
2600 tgl@sss.pgh.pa.us 571 : 625312 : new_len = list1->length + list2->length;
572 : : /* Enlarge array if necessary */
573 [ + + ]: 625312 : if (new_len > list1->max_length)
574 : 18876 : enlarge_list(list1, new_len);
575 : :
576 : : /* Even if list1 == list2, using memcpy should be safe here */
577 : 625312 : memcpy(&list1->elements[list1->length], &list2->elements[0],
578 : 625312 : list2->length * sizeof(ListCell));
579 : 625312 : list1->length = new_len;
580 : :
8128 neilc@samurai.com 581 : 625312 : check_list_invariants(list1);
582 : 625312 : return list1;
583 : : }
584 : :
585 : : /*
586 : : * Form a new list by concatenating the elements of list1 and list2.
587 : : *
588 : : * Neither input list is modified. (However, if they are pointer lists,
589 : : * the output list will point to the same structures.)
590 : : *
591 : : * This is equivalent to, but more efficient than,
592 : : * list_concat(list_copy(list1), list2).
593 : : * Note that some pre-v13 code might list_copy list2 as well, but that's
594 : : * pointless now.
595 : : */
596 : : List *
2572 tgl@sss.pgh.pa.us 597 : 857299 : list_concat_copy(const List *list1, const List *list2)
598 : : {
599 : : List *result;
600 : : int new_len;
601 : :
602 [ + + ]: 857299 : if (list1 == NIL)
603 : 369169 : return list_copy(list2);
604 [ + + ]: 488130 : if (list2 == NIL)
605 : 408163 : return list_copy(list1);
606 : :
607 [ - + ]: 79967 : Assert(list1->type == list2->type);
608 : :
609 : 79967 : new_len = list1->length + list2->length;
610 : 79967 : result = new_list(list1->type, new_len);
611 : 79967 : memcpy(result->elements, list1->elements,
612 : 79967 : list1->length * sizeof(ListCell));
613 : 79967 : memcpy(result->elements + list1->length, list2->elements,
614 : 79967 : list2->length * sizeof(ListCell));
615 : :
616 : 79967 : check_list_invariants(result);
617 : 79967 : return result;
618 : : }
619 : :
620 : : /*
621 : : * Truncate 'list' to contain no more than 'new_size' elements. This
622 : : * modifies the list in-place! Despite this, callers should use the
623 : : * pointer returned by this function to refer to the newly truncated
624 : : * list -- it may or may not be the same as the pointer that was
625 : : * passed.
626 : : *
627 : : * Note that any cells removed by list_truncate() are NOT pfree'd.
628 : : */
629 : : List *
8128 neilc@samurai.com 630 : 530513 : list_truncate(List *list, int new_size)
631 : : {
632 [ + + ]: 530513 : if (new_size <= 0)
8033 bruce@momjian.us 633 : 58084 : return NIL; /* truncate to zero length */
634 : :
635 : : /* If asked to effectively extend the list, do nothing */
2600 tgl@sss.pgh.pa.us 636 [ + + ]: 472429 : if (new_size < list_length(list))
637 : 130593 : 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 : :
8128 neilc@samurai.com 649 : 472429 : return list;
650 : : }
651 : :
652 : : /*
653 : : * Return true iff 'datum' is a member of the list. Equality is
654 : : * determined via equal(), so callers should ensure that they pass a
655 : : * Node as 'datum'.
656 : : *
657 : : * This does a simple linear search --- avoid using it on long lists.
658 : : */
659 : : bool
5377 peter_e@gmx.net 660 : 875872 : list_member(const List *list, const void *datum)
661 : : {
662 : : const ListCell *cell;
663 : :
8128 neilc@samurai.com 664 [ + + - + ]: 875872 : Assert(IsPointerList(list));
665 : 875872 : check_list_invariants(list);
666 : :
8033 bruce@momjian.us 667 [ + + + + : 1569324 : foreach(cell, list)
+ + ]
668 : : {
8128 neilc@samurai.com 669 [ + + ]: 795545 : if (equal(lfirst(cell), datum))
670 : 102093 : return true;
671 : : }
672 : :
673 : 773779 : return false;
674 : : }
675 : :
676 : : /*
677 : : * Return true iff 'datum' is a member of the list. Equality is
678 : : * determined by using simple pointer comparison.
679 : : */
680 : : bool
5377 peter_e@gmx.net 681 : 480951 : list_member_ptr(const List *list, const void *datum)
682 : : {
683 : : const ListCell *cell;
684 : :
8128 neilc@samurai.com 685 [ + + - + ]: 480951 : Assert(IsPointerList(list));
686 : 480951 : check_list_invariants(list);
687 : :
8033 bruce@momjian.us 688 [ + + + + : 768346 : foreach(cell, list)
+ + ]
689 : : {
8128 neilc@samurai.com 690 [ + + ]: 483338 : if (lfirst(cell) == datum)
691 : 195943 : return true;
692 : : }
693 : :
694 : 285008 : return false;
695 : : }
696 : :
697 : : /*
698 : : * Return true iff the integer 'datum' is a member of the list.
699 : : */
700 : : bool
5377 peter_e@gmx.net 701 : 88613 : list_member_int(const List *list, int datum)
702 : : {
703 : : const ListCell *cell;
704 : :
8128 neilc@samurai.com 705 [ + + - + ]: 88613 : Assert(IsIntegerList(list));
706 : 88613 : check_list_invariants(list);
707 : :
8033 bruce@momjian.us 708 [ + + + + : 5035705 : foreach(cell, list)
+ + ]
709 : : {
8128 neilc@samurai.com 710 [ + + ]: 4962363 : if (lfirst_int(cell) == datum)
711 : 15271 : return true;
712 : : }
713 : :
714 : 73342 : return false;
715 : : }
716 : :
717 : : /*
718 : : * Return true iff the OID 'datum' is a member of the list.
719 : : */
720 : : bool
5377 peter_e@gmx.net 721 : 62527176 : list_member_oid(const List *list, Oid datum)
722 : : {
723 : : const ListCell *cell;
724 : :
8128 neilc@samurai.com 725 [ + + - + ]: 62527176 : Assert(IsOidList(list));
726 : 62527176 : check_list_invariants(list);
727 : :
8033 bruce@momjian.us 728 [ + + + + : 66368703 : foreach(cell, list)
+ + ]
729 : : {
8128 neilc@samurai.com 730 [ + + ]: 4743652 : if (lfirst_oid(cell) == datum)
731 : 902125 : return true;
732 : : }
733 : :
734 : 61625051 : return false;
735 : : }
736 : :
737 : : /*
738 : : * Return true iff the TransactionId 'datum' is a member of the list.
739 : : */
740 : : bool
1515 alvherre@alvh.no-ip. 741 : 171001 : list_member_xid(const List *list, TransactionId datum)
742 : : {
743 : : const ListCell *cell;
744 : :
745 [ + + - + ]: 171001 : Assert(IsXidList(list));
746 : 171001 : check_list_invariants(list);
747 : :
748 [ + + + + : 211891 : foreach(cell, list)
+ + ]
749 : : {
1407 750 [ + + ]: 211799 : if (lfirst_xid(cell) == datum)
1515 751 : 170909 : return true;
752 : : }
753 : :
754 : 92 : return false;
755 : : }
756 : :
757 : : /*
758 : : * Delete the n'th cell (counting from 0) in list.
759 : : *
760 : : * The List is pfree'd if this was the last member.
761 : : *
762 : : * Note that this takes time proportional to the distance to the end of the
763 : : * list, since the following entries must be moved.
764 : : */
765 : : List *
2600 tgl@sss.pgh.pa.us 766 : 2796851 : list_delete_nth_cell(List *list, int n)
767 : : {
8128 neilc@samurai.com 768 : 2796851 : check_list_invariants(list);
769 : :
2600 tgl@sss.pgh.pa.us 770 [ + - - + ]: 2796851 : Assert(n >= 0 && n < list->length);
771 : :
772 : : /*
773 : : * If we're about to delete the last node from the list, free the whole
774 : : * list instead and return NIL, which is the only valid representation of
775 : : * a zero-length list.
776 : : */
8128 neilc@samurai.com 777 [ + + ]: 2796851 : if (list->length == 1)
778 : : {
779 : 1387622 : list_free(list);
780 : 1387622 : return NIL;
781 : : }
782 : :
783 : : /*
784 : : * Otherwise, we normally just collapse out the removed element. But for
785 : : * debugging purposes, move the whole list contents someplace else.
786 : : *
787 : : * (Note that we *must* keep the contents in the same memory context.)
788 : : */
789 : : #ifndef DEBUG_LIST_MEMORY_USAGE
2600 tgl@sss.pgh.pa.us 790 : 1409229 : memmove(&list->elements[n], &list->elements[n + 1],
791 : 1409229 : (list->length - 1 - n) * sizeof(ListCell));
8128 neilc@samurai.com 792 : 1409229 : list->length--;
793 : : #else
794 : : {
795 : : ListCell *newelems;
796 : : int newmaxlen = list->length - 1;
797 : :
798 : : newelems = (ListCell *)
799 : : MemoryContextAlloc(GetMemoryChunkContext(list),
800 : : newmaxlen * sizeof(ListCell));
801 : : memcpy(newelems, list->elements, n * sizeof(ListCell));
802 : : memcpy(&newelems[n], &list->elements[n + 1],
803 : : (list->length - 1 - n) * sizeof(ListCell));
804 : : if (list->elements != list->initial_elements)
805 : : pfree(list->elements);
806 : : else
807 : : {
808 : : /*
809 : : * As in enlarge_list(), clear the initial_elements[] space and/or
810 : : * mark it inaccessible.
811 : : */
812 : : #ifdef CLOBBER_FREED_MEMORY
813 : : wipe_mem(list->initial_elements,
814 : : list->max_length * sizeof(ListCell));
815 : : #else
816 : : VALGRIND_MAKE_MEM_NOACCESS(list->initial_elements,
817 : : list->max_length * sizeof(ListCell));
818 : : #endif
819 : : }
820 : : list->elements = newelems;
821 : : list->max_length = newmaxlen;
822 : : list->length--;
823 : : check_list_invariants(list);
824 : : }
825 : : #endif
826 : :
827 : 1409229 : return list;
828 : : }
829 : :
830 : : /*
831 : : * Delete 'cell' from 'list'.
832 : : *
833 : : * The List is pfree'd if this was the last member. However, we do not
834 : : * touch any data the cell might've been pointing to.
835 : : *
836 : : * Note that this takes time proportional to the distance to the end of the
837 : : * list, since the following entries must be moved.
838 : : */
839 : : List *
2600 tgl@sss.pgh.pa.us 840 : 1414477 : list_delete_cell(List *list, ListCell *cell)
841 : : {
842 : 1414477 : 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 *
8128 neilc@samurai.com 852 : 3699 : list_delete(List *list, void *datum)
853 : : {
854 : : ListCell *cell;
855 : :
856 [ + + - + ]: 3699 : Assert(IsPointerList(list));
857 : 3699 : check_list_invariants(list);
858 : :
8033 bruce@momjian.us 859 [ + + + - : 3941 : foreach(cell, list)
+ + ]
860 : : {
8128 neilc@samurai.com 861 [ + + ]: 3938 : if (equal(lfirst(cell), datum))
2600 tgl@sss.pgh.pa.us 862 : 3696 : return list_delete_cell(list, cell);
863 : : }
864 : :
865 : : /* Didn't find a match: return the list unmodified */
8128 neilc@samurai.com 866 : 3 : return list;
867 : : }
868 : :
869 : : /* As above, but use simple pointer equality */
870 : : List *
871 : 1400740 : list_delete_ptr(List *list, void *datum)
872 : : {
873 : : ListCell *cell;
874 : :
875 [ + - - + ]: 1400740 : Assert(IsPointerList(list));
876 : 1400740 : check_list_invariants(list);
877 : :
8033 bruce@momjian.us 878 [ + - + - : 1401110 : foreach(cell, list)
+ - ]
879 : : {
8128 neilc@samurai.com 880 [ + + ]: 1401110 : if (lfirst(cell) == datum)
2600 tgl@sss.pgh.pa.us 881 : 1400740 : return list_delete_cell(list, cell);
882 : : }
883 : :
884 : : /* Didn't find a match: return the list unmodified */
8128 neilc@samurai.com 885 :UBC 0 : return list;
886 : : }
887 : :
888 : : /* As above, but for integers */
889 : : List *
8128 neilc@samurai.com 890 :CBC 144 : list_delete_int(List *list, int datum)
891 : : {
892 : : ListCell *cell;
893 : :
894 [ + - - + ]: 144 : Assert(IsIntegerList(list));
895 : 144 : check_list_invariants(list);
896 : :
8033 bruce@momjian.us 897 [ + - + - : 149 : foreach(cell, list)
+ - ]
898 : : {
8128 neilc@samurai.com 899 [ + + ]: 149 : if (lfirst_int(cell) == datum)
2600 tgl@sss.pgh.pa.us 900 : 144 : return list_delete_cell(list, cell);
901 : : }
902 : :
903 : : /* Didn't find a match: return the list unmodified */
8128 neilc@samurai.com 904 :UBC 0 : return list;
905 : : }
906 : :
907 : : /* As above, but for OIDs */
908 : : List *
8128 neilc@samurai.com 909 :CBC 4937 : list_delete_oid(List *list, Oid datum)
910 : : {
911 : : ListCell *cell;
912 : :
913 [ + + - + ]: 4937 : Assert(IsOidList(list));
914 : 4937 : check_list_invariants(list);
915 : :
8033 bruce@momjian.us 916 [ + + + - : 4937 : foreach(cell, list)
+ + ]
917 : : {
8128 neilc@samurai.com 918 [ + - ]: 1161 : if (lfirst_oid(cell) == datum)
2600 tgl@sss.pgh.pa.us 919 : 1161 : return list_delete_cell(list, cell);
920 : : }
921 : :
922 : : /* Didn't find a match: return the list unmodified */
8128 neilc@samurai.com 923 : 3776 : return list;
924 : : }
925 : :
926 : : /*
927 : : * Delete the first element of the list.
928 : : *
929 : : * This is useful to replace the Lisp-y code "list = lnext(list);" in cases
930 : : * where the intent is to alter the list rather than just traverse it.
931 : : * Beware that the list is modified, whereas the Lisp-y coding leaves
932 : : * the original list head intact in case there's another pointer to it.
933 : : *
934 : : * Note that this takes time proportional to the length of the list,
935 : : * since the remaining entries must be moved. Consider reversing the
936 : : * list order so that you can use list_delete_last() instead. However,
937 : : * if that causes you to replace lappend() with lcons(), you haven't
938 : : * improved matters. (In short, you can make an efficient stack from
939 : : * a List, but not an efficient FIFO queue.)
940 : : */
941 : : List *
942 : 625818 : list_delete_first(List *list)
943 : : {
944 : 625818 : check_list_invariants(list);
945 : :
946 [ - + ]: 625818 : if (list == NIL)
8128 neilc@samurai.com 947 :UBC 0 : return NIL; /* would an error be better? */
948 : :
2600 tgl@sss.pgh.pa.us 949 :CBC 625818 : return list_delete_nth_cell(list, 0);
950 : : }
951 : :
952 : : /*
953 : : * Delete the last element of the list.
954 : : */
955 : : List *
2598 956 : 69774 : list_delete_last(List *list)
957 : : {
958 : 69774 : check_list_invariants(list);
959 : :
960 [ - + ]: 69774 : if (list == NIL)
2598 tgl@sss.pgh.pa.us 961 :UBC 0 : return NIL; /* would an error be better? */
962 : :
963 : : /* list_truncate won't free list if it goes to empty, but this should */
2598 tgl@sss.pgh.pa.us 964 [ + + ]:CBC 69774 : if (list_length(list) <= 1)
965 : : {
966 : 18553 : list_free(list);
967 : 18553 : return NIL;
968 : : }
969 : :
970 : 51221 : 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 *
1759 982 : 472 : list_delete_first_n(List *list, int n)
983 : : {
984 : 472 : check_list_invariants(list);
985 : :
986 : : /* No-op request? */
987 [ + + ]: 472 : if (n <= 0)
988 : 10 : return list;
989 : :
990 : : /* Delete whole list? */
991 [ - + ]: 462 : if (n >= list_length(list))
992 : : {
1759 tgl@sss.pgh.pa.us 993 :UBC 0 : list_free(list);
994 : 0 : return NIL;
995 : : }
996 : :
997 : : /*
998 : : * Otherwise, we normally just collapse out the removed elements. But for
999 : : * debugging purposes, move the whole list contents someplace else.
1000 : : *
1001 : : * (Note that we *must* keep the contents in the same memory context.)
1002 : : */
1003 : : #ifndef DEBUG_LIST_MEMORY_USAGE
1759 tgl@sss.pgh.pa.us 1004 :CBC 462 : memmove(&list->elements[0], &list->elements[n],
1005 : 462 : (list->length - n) * sizeof(ListCell));
1006 : 462 : list->length -= n;
1007 : : #else
1008 : : {
1009 : : ListCell *newelems;
1010 : : int newmaxlen = list->length - n;
1011 : :
1012 : : newelems = (ListCell *)
1013 : : MemoryContextAlloc(GetMemoryChunkContext(list),
1014 : : newmaxlen * sizeof(ListCell));
1015 : : memcpy(newelems, &list->elements[n], newmaxlen * sizeof(ListCell));
1016 : : if (list->elements != list->initial_elements)
1017 : : pfree(list->elements);
1018 : : else
1019 : : {
1020 : : /*
1021 : : * As in enlarge_list(), clear the initial_elements[] space and/or
1022 : : * mark it inaccessible.
1023 : : */
1024 : : #ifdef CLOBBER_FREED_MEMORY
1025 : : wipe_mem(list->initial_elements,
1026 : : list->max_length * sizeof(ListCell));
1027 : : #else
1028 : : VALGRIND_MAKE_MEM_NOACCESS(list->initial_elements,
1029 : : list->max_length * sizeof(ListCell));
1030 : : #endif
1031 : : }
1032 : : list->elements = newelems;
1033 : : list->max_length = newmaxlen;
1034 : : list->length = newmaxlen;
1035 : : check_list_invariants(list);
1036 : : }
1037 : : #endif
1038 : :
1039 : 462 : return list;
1040 : : }
1041 : :
1042 : : /*
1043 : : * Generate the union of two lists. This is calculated by copying
1044 : : * list1 via list_copy(), then adding to it all the members of list2
1045 : : * that aren't already in list1.
1046 : : *
1047 : : * Whether an element is already a member of the list is determined
1048 : : * via equal().
1049 : : *
1050 : : * The returned list is newly-allocated, although the content of the
1051 : : * cells is the same (i.e. any pointed-to objects are not copied).
1052 : : *
1053 : : * NB: this function will NOT remove any duplicates that are present
1054 : : * in list1 (so it only performs a "union" if list1 is known unique to
1055 : : * start with). Also, if you are about to write "x = list_union(x, y)"
1056 : : * you probably want to use list_concat_unique() instead to avoid wasting
1057 : : * the storage of the old x list.
1058 : : *
1059 : : * Note that this takes time proportional to the product of the list
1060 : : * lengths, so beware of using it on long lists. (We could probably
1061 : : * improve that, but really you should be using some other data structure
1062 : : * if this'd be a performance bottleneck.)
1063 : : */
1064 : : List *
5377 peter_e@gmx.net 1065 : 8579 : list_union(const List *list1, const List *list2)
1066 : : {
1067 : : List *result;
1068 : : const ListCell *cell;
1069 : :
8128 neilc@samurai.com 1070 [ - + - - ]: 8579 : Assert(IsPointerList(list1));
1071 [ + + - + ]: 8579 : Assert(IsPointerList(list2));
1072 : :
1073 : 8579 : result = list_copy(list1);
1074 [ + + + + : 17610 : foreach(cell, list2)
+ + ]
1075 : : {
1076 [ + + ]: 9031 : if (!list_member(result, lfirst(cell)))
1077 : 8969 : result = lappend(result, lfirst(cell));
1078 : : }
1079 : :
1080 : 8579 : check_list_invariants(result);
1081 : 8579 : return result;
1082 : : }
1083 : :
1084 : : /*
1085 : : * This variant of list_union() determines duplicates via simple
1086 : : * pointer comparison.
1087 : : */
1088 : : List *
5377 peter_e@gmx.net 1089 :UBC 0 : list_union_ptr(const List *list1, const List *list2)
1090 : : {
1091 : : List *result;
1092 : : const ListCell *cell;
1093 : :
8128 neilc@samurai.com 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 : 0 : return result;
1106 : : }
1107 : :
1108 : : /*
1109 : : * This variant of list_union() operates upon lists of integers.
1110 : : */
1111 : : List *
5377 peter_e@gmx.net 1112 :CBC 5211 : list_union_int(const List *list1, const List *list2)
1113 : : {
1114 : : List *result;
1115 : : const ListCell *cell;
1116 : :
8128 neilc@samurai.com 1117 [ + + - + ]: 5211 : Assert(IsIntegerList(list1));
1118 [ + + - + ]: 5211 : Assert(IsIntegerList(list2));
1119 : :
1120 : 5211 : result = list_copy(list1);
1121 [ + + + + : 10362 : foreach(cell, list2)
+ + ]
1122 : : {
1123 [ + + ]: 5151 : if (!list_member_int(result, lfirst_int(cell)))
1124 : 4983 : result = lappend_int(result, lfirst_int(cell));
1125 : : }
1126 : :
1127 : 5211 : check_list_invariants(result);
1128 : 5211 : return result;
1129 : : }
1130 : :
1131 : : /*
1132 : : * This variant of list_union() operates upon lists of OIDs.
1133 : : */
1134 : : List *
5377 peter_e@gmx.net 1135 :UBC 0 : list_union_oid(const List *list1, const List *list2)
1136 : : {
1137 : : List *result;
1138 : : const ListCell *cell;
1139 : :
8128 neilc@samurai.com 1140 [ # # # # ]: 0 : Assert(IsOidList(list1));
1141 [ # # # # ]: 0 : Assert(IsOidList(list2));
1142 : :
1143 : 0 : result = list_copy(list1);
1144 [ # # # # : 0 : foreach(cell, list2)
# # ]
1145 : : {
1146 [ # # ]: 0 : if (!list_member_oid(result, lfirst_oid(cell)))
1147 : 0 : result = lappend_oid(result, lfirst_oid(cell));
1148 : : }
1149 : :
1150 : 0 : check_list_invariants(result);
1151 : 0 : return result;
1152 : : }
1153 : :
1154 : : /*
1155 : : * Return a list that contains all the cells that are in both list1 and
1156 : : * list2. The returned list is freshly allocated via palloc(), but the
1157 : : * cells themselves point to the same objects as the cells of the
1158 : : * input lists.
1159 : : *
1160 : : * Duplicate entries in list1 will not be suppressed, so it's only a true
1161 : : * "intersection" if list1 is known unique beforehand.
1162 : : *
1163 : : * This variant works on lists of pointers, and determines list
1164 : : * membership via equal(). Note that the list1 member will be pointed
1165 : : * to in the result.
1166 : : *
1167 : : * Note that this takes time proportional to the product of the list
1168 : : * lengths, so beware of using it on long lists. (We could probably
1169 : : * improve that, but really you should be using some other data structure
1170 : : * if this'd be a performance bottleneck.)
1171 : : */
1172 : : List *
5377 peter_e@gmx.net 1173 : 0 : list_intersection(const List *list1, const List *list2)
1174 : : {
1175 : : List *result;
1176 : : const ListCell *cell;
1177 : :
6587 tgl@sss.pgh.pa.us 1178 [ # # # # ]: 0 : if (list1 == NIL || list2 == NIL)
1179 : 0 : return NIL;
1180 : :
1181 [ # # # # ]: 0 : Assert(IsPointerList(list1));
1182 [ # # # # ]: 0 : Assert(IsPointerList(list2));
1183 : :
1184 : 0 : result = NIL;
1185 [ # # # # : 0 : foreach(cell, list1)
# # ]
1186 : : {
1187 [ # # ]: 0 : if (list_member(list2, lfirst(cell)))
1188 : 0 : result = lappend(result, lfirst(cell));
1189 : : }
1190 : :
1191 : 0 : check_list_invariants(result);
1192 : 0 : return result;
1193 : : }
1194 : :
1195 : : /*
1196 : : * As list_intersection but operates on lists of integers.
1197 : : */
1198 : : List *
4121 andres@anarazel.de 1199 :CBC 354 : list_intersection_int(const List *list1, const List *list2)
1200 : : {
1201 : : List *result;
1202 : : const ListCell *cell;
1203 : :
1204 [ + - - + ]: 354 : if (list1 == NIL || list2 == NIL)
4121 andres@anarazel.de 1205 :UBC 0 : return NIL;
1206 : :
4121 andres@anarazel.de 1207 [ + - - + ]:CBC 354 : Assert(IsIntegerList(list1));
1208 [ + - - + ]: 354 : Assert(IsIntegerList(list2));
1209 : :
1210 : 354 : result = NIL;
1211 [ + - + + : 740 : foreach(cell, list1)
+ + ]
1212 : : {
1213 [ + + ]: 386 : if (list_member_int(list2, lfirst_int(cell)))
1214 : 156 : result = lappend_int(result, lfirst_int(cell));
1215 : : }
1216 : :
1217 : 354 : check_list_invariants(result);
1218 : 354 : return result;
1219 : : }
1220 : :
1221 : : /*
1222 : : * Return a list that contains all the cells in list1 that are not in
1223 : : * list2. The returned list is freshly allocated via palloc(), but the
1224 : : * cells themselves point to the same objects as the cells of the
1225 : : * input lists.
1226 : : *
1227 : : * This variant works on lists of pointers, and determines list
1228 : : * membership via equal()
1229 : : *
1230 : : * Note that this takes time proportional to the product of the list
1231 : : * lengths, so beware of using it on long lists. (We could probably
1232 : : * improve that, but really you should be using some other data structure
1233 : : * if this'd be a performance bottleneck.)
1234 : : */
1235 : : List *
5377 peter_e@gmx.net 1236 : 42542 : list_difference(const List *list1, const List *list2)
1237 : : {
1238 : : const ListCell *cell;
8033 bruce@momjian.us 1239 : 42542 : List *result = NIL;
1240 : :
8128 neilc@samurai.com 1241 [ + + - + ]: 42542 : Assert(IsPointerList(list1));
1242 [ + + - + ]: 42542 : Assert(IsPointerList(list2));
1243 : :
1244 [ + + ]: 42542 : if (list2 == NIL)
1245 : 1334 : return list_copy(list1);
1246 : :
8033 bruce@momjian.us 1247 [ + - + + : 88768 : foreach(cell, list1)
+ + ]
1248 : : {
8128 neilc@samurai.com 1249 [ + + ]: 47560 : if (!list_member(list2, lfirst(cell)))
1250 : 1364 : result = lappend(result, lfirst(cell));
1251 : : }
1252 : :
1253 : 41208 : check_list_invariants(result);
10581 bruce@momjian.us 1254 : 41208 : return result;
1255 : : }
1256 : :
1257 : : /*
1258 : : * This variant of list_difference() determines list membership via
1259 : : * simple pointer equality.
1260 : : */
1261 : : List *
5377 peter_e@gmx.net 1262 : 19023 : list_difference_ptr(const List *list1, const List *list2)
1263 : : {
1264 : : const ListCell *cell;
8033 bruce@momjian.us 1265 : 19023 : List *result = NIL;
1266 : :
8128 neilc@samurai.com 1267 [ + + - + ]: 19023 : Assert(IsPointerList(list1));
1268 [ + + - + ]: 19023 : Assert(IsPointerList(list2));
1269 : :
1270 [ + + ]: 19023 : if (list2 == NIL)
1271 : 15749 : return list_copy(list1);
1272 : :
8033 bruce@momjian.us 1273 [ + + + + : 8372 : foreach(cell, list1)
+ + ]
1274 : : {
8128 neilc@samurai.com 1275 [ + + ]: 5098 : if (!list_member_ptr(list2, lfirst(cell)))
1276 : 2118 : result = lappend(result, lfirst(cell));
1277 : : }
1278 : :
1279 : 3274 : check_list_invariants(result);
9875 tgl@sss.pgh.pa.us 1280 : 3274 : return result;
1281 : : }
1282 : :
1283 : : /*
1284 : : * This variant of list_difference() operates upon lists of integers.
1285 : : */
1286 : : List *
5377 peter_e@gmx.net 1287 : 2625 : list_difference_int(const List *list1, const List *list2)
1288 : : {
1289 : : const ListCell *cell;
8033 bruce@momjian.us 1290 : 2625 : List *result = NIL;
1291 : :
8128 neilc@samurai.com 1292 [ + + - + ]: 2625 : Assert(IsIntegerList(list1));
1293 [ + + - + ]: 2625 : Assert(IsIntegerList(list2));
1294 : :
1295 [ + + ]: 2625 : if (list2 == NIL)
1296 : 2005 : return list_copy(list1);
1297 : :
8033 bruce@momjian.us 1298 [ + - + + : 1840 : foreach(cell, list1)
+ + ]
1299 : : {
8128 neilc@samurai.com 1300 [ + + ]: 1220 : if (!list_member_int(list2, lfirst_int(cell)))
1301 : 496 : result = lappend_int(result, lfirst_int(cell));
1302 : : }
1303 : :
1304 : 620 : check_list_invariants(result);
9875 tgl@sss.pgh.pa.us 1305 : 620 : return result;
1306 : : }
1307 : :
1308 : : /*
1309 : : * This variant of list_difference() operates upon lists of OIDs.
1310 : : */
1311 : : List *
5377 peter_e@gmx.net 1312 : 7733 : list_difference_oid(const List *list1, const List *list2)
1313 : : {
1314 : : const ListCell *cell;
8033 bruce@momjian.us 1315 : 7733 : List *result = NIL;
1316 : :
8128 neilc@samurai.com 1317 [ + + - + ]: 7733 : Assert(IsOidList(list1));
1318 [ + + - + ]: 7733 : Assert(IsOidList(list2));
1319 : :
1320 [ + + ]: 7733 : if (list2 == NIL)
1321 : 7327 : return list_copy(list1);
1322 : :
8033 bruce@momjian.us 1323 [ + + + + : 2702 : foreach(cell, list1)
+ + ]
1324 : : {
8128 neilc@samurai.com 1325 [ + + ]: 2296 : if (!list_member_oid(list2, lfirst_oid(cell)))
1326 : 1318 : result = lappend_oid(result, lfirst_oid(cell));
1327 : : }
1328 : :
1329 : 406 : check_list_invariants(result);
1330 : 406 : return result;
1331 : : }
1332 : :
1333 : : /*
1334 : : * Append datum to list, but only if it isn't already in the list.
1335 : : *
1336 : : * Whether an element is already a member of the list is determined
1337 : : * via equal().
1338 : : *
1339 : : * This does a simple linear search --- avoid using it on long lists.
1340 : : */
1341 : : List *
7700 tgl@sss.pgh.pa.us 1342 : 145442 : list_append_unique(List *list, void *datum)
1343 : : {
1344 [ + + ]: 145442 : if (list_member(list, datum))
1345 : 11737 : return list;
1346 : : else
1347 : 133705 : return lappend(list, datum);
1348 : : }
1349 : :
1350 : : /*
1351 : : * This variant of list_append_unique() determines list membership via
1352 : : * simple pointer equality.
1353 : : */
1354 : : List *
1355 : 384290 : list_append_unique_ptr(List *list, void *datum)
1356 : : {
1357 [ + + ]: 384290 : if (list_member_ptr(list, datum))
1358 : 153503 : return list;
1359 : : else
1360 : 230787 : return lappend(list, datum);
1361 : : }
1362 : :
1363 : : /*
1364 : : * This variant of list_append_unique() operates upon lists of integers.
1365 : : */
1366 : : List *
7700 tgl@sss.pgh.pa.us 1367 :UBC 0 : list_append_unique_int(List *list, int datum)
1368 : : {
1369 [ # # ]: 0 : if (list_member_int(list, datum))
1370 : 0 : return list;
1371 : : else
1372 : 0 : return lappend_int(list, datum);
1373 : : }
1374 : :
1375 : : /*
1376 : : * This variant of list_append_unique() operates upon lists of OIDs.
1377 : : */
1378 : : List *
7700 tgl@sss.pgh.pa.us 1379 :CBC 4243 : list_append_unique_oid(List *list, Oid datum)
1380 : : {
1381 [ + + ]: 4243 : if (list_member_oid(list, datum))
1382 : 1375 : return list;
1383 : : else
1384 : 2868 : return lappend_oid(list, datum);
1385 : : }
1386 : :
1387 : : /*
1388 : : * Append to list1 each member of list2 that isn't already in list1.
1389 : : *
1390 : : * Whether an element is already a member of the list is determined
1391 : : * via equal().
1392 : : *
1393 : : * This is almost the same functionality as list_union(), but list1 is
1394 : : * modified in-place rather than being copied. However, callers of this
1395 : : * function may have strict ordering expectations -- i.e. that the relative
1396 : : * order of those list2 elements that are not duplicates is preserved.
1397 : : *
1398 : : * Note that this takes time proportional to the product of the list
1399 : : * lengths, so beware of using it on long lists. (We could probably
1400 : : * improve that, but really you should be using some other data structure
1401 : : * if this'd be a performance bottleneck.)
1402 : : */
1403 : : List *
2600 1404 : 3166 : list_concat_unique(List *list1, const List *list2)
1405 : : {
1406 : : ListCell *cell;
1407 : :
7700 1408 [ + + - + ]: 3166 : Assert(IsPointerList(list1));
1409 [ + + - + ]: 3166 : Assert(IsPointerList(list2));
1410 : :
1411 [ + + + + : 5823 : foreach(cell, list2)
+ + ]
1412 : : {
1413 [ + + ]: 2657 : if (!list_member(list1, lfirst(cell)))
1414 : 2632 : list1 = lappend(list1, lfirst(cell));
1415 : : }
1416 : :
1417 : 3166 : check_list_invariants(list1);
1418 : 3166 : return list1;
1419 : : }
1420 : :
1421 : : /*
1422 : : * This variant of list_concat_unique() determines list membership via
1423 : : * simple pointer equality.
1424 : : */
1425 : : List *
2600 1426 : 1744 : list_concat_unique_ptr(List *list1, const List *list2)
1427 : : {
1428 : : ListCell *cell;
1429 : :
7700 1430 [ + + - + ]: 1744 : Assert(IsPointerList(list1));
1431 [ + - - + ]: 1744 : Assert(IsPointerList(list2));
1432 : :
1433 [ + - + + : 5955 : foreach(cell, list2)
+ + ]
1434 : : {
1435 [ + + ]: 4211 : if (!list_member_ptr(list1, lfirst(cell)))
1436 : 2105 : list1 = lappend(list1, lfirst(cell));
1437 : : }
1438 : :
1439 : 1744 : check_list_invariants(list1);
1440 : 1744 : return list1;
1441 : : }
1442 : :
1443 : : /*
1444 : : * This variant of list_concat_unique() operates upon lists of integers.
1445 : : */
1446 : : List *
2600 tgl@sss.pgh.pa.us 1447 :UBC 0 : list_concat_unique_int(List *list1, const List *list2)
1448 : : {
1449 : : ListCell *cell;
1450 : :
7700 1451 [ # # # # ]: 0 : Assert(IsIntegerList(list1));
1452 [ # # # # ]: 0 : Assert(IsIntegerList(list2));
1453 : :
1454 [ # # # # : 0 : foreach(cell, list2)
# # ]
1455 : : {
1456 [ # # ]: 0 : if (!list_member_int(list1, lfirst_int(cell)))
1457 : 0 : list1 = lappend_int(list1, lfirst_int(cell));
1458 : : }
1459 : :
1460 : 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 : : */
1467 : : List *
2600 tgl@sss.pgh.pa.us 1468 :CBC 16967 : list_concat_unique_oid(List *list1, const List *list2)
1469 : : {
1470 : : ListCell *cell;
1471 : :
7700 1472 [ + + - + ]: 16967 : Assert(IsOidList(list1));
1473 [ + + - + ]: 16967 : Assert(IsOidList(list2));
1474 : :
1475 [ + + + + : 18887 : foreach(cell, list2)
+ + ]
1476 : : {
1477 [ + + ]: 1920 : if (!list_member_oid(list1, lfirst_oid(cell)))
1478 : 1372 : list1 = lappend_oid(list1, lfirst_oid(cell));
1479 : : }
1480 : :
1481 : 16967 : check_list_invariants(list1);
1482 : 16967 : return list1;
1483 : : }
1484 : :
1485 : : /*
1486 : : * Remove adjacent duplicates in a list of OIDs.
1487 : : *
1488 : : * It is caller's responsibility to have sorted the list to bring duplicates
1489 : : * together, perhaps via list_sort(list, list_oid_cmp).
1490 : : *
1491 : : * Note that this takes time proportional to the length of the list.
1492 : : */
1493 : : void
2599 1494 : 1334 : list_deduplicate_oid(List *list)
1495 : : {
1496 : : int len;
1497 : :
1498 [ + + - + ]: 1334 : Assert(IsOidList(list));
1499 : 1334 : len = list_length(list);
1500 [ + + ]: 1334 : if (len > 1)
1501 : : {
1502 : 176 : ListCell *elements = list->elements;
1503 : 176 : int i = 0;
1504 : :
1505 [ + + ]: 492 : for (int j = 1; j < len; j++)
1506 : : {
1507 [ + + ]: 316 : if (elements[i].oid_value != elements[j].oid_value)
1508 : 281 : elements[++i].oid_value = elements[j].oid_value;
1509 : : }
1510 : 176 : list->length = i + 1;
1511 : : }
1512 : 1334 : check_list_invariants(list);
1513 : 1334 : }
1514 : :
1515 : : /*
1516 : : * Free all storage in a list, and optionally the pointed-to elements
1517 : : */
1518 : : static void
8128 neilc@samurai.com 1519 : 18673643 : list_free_private(List *list, bool deep)
1520 : : {
2600 tgl@sss.pgh.pa.us 1521 [ + + ]: 18673643 : if (list == NIL)
1522 : 14372332 : return; /* nothing to do */
1523 : :
8128 neilc@samurai.com 1524 : 4301311 : check_list_invariants(list);
1525 : :
2600 tgl@sss.pgh.pa.us 1526 [ + + ]: 4301311 : if (deep)
1527 : : {
1528 [ + + ]: 1215906 : for (int i = 0; i < list->length; i++)
1529 : 938364 : pfree(lfirst(&list->elements[i]));
1530 : : }
1531 [ + + ]: 4301311 : if (list->elements != list->initial_elements)
1532 : 108429 : pfree(list->elements);
1533 : 4301311 : pfree(list);
1534 : : }
1535 : :
1536 : : /*
1537 : : * Free all the cells of the list, as well as the list itself. Any
1538 : : * objects that are pointed-to by the cells of the list are NOT
1539 : : * free'd.
1540 : : *
1541 : : * On return, the argument to this function has been freed, so the
1542 : : * caller would be wise to set it to NIL for safety's sake.
1543 : : */
1544 : : void
8128 neilc@samurai.com 1545 : 17035897 : list_free(List *list)
1546 : : {
1547 : 17035897 : list_free_private(list, false);
1548 : 17035897 : }
1549 : :
1550 : : /*
1551 : : * Free all the cells of the list, the list itself, and all the
1552 : : * objects pointed-to by the cells of the list (each element in the
1553 : : * list must contain a pointer to a palloc()'d region of memory!)
1554 : : *
1555 : : * On return, the argument to this function has been freed, so the
1556 : : * caller would be wise to set it to NIL for safety's sake.
1557 : : */
1558 : : void
1559 : 1637746 : list_free_deep(List *list)
1560 : : {
1561 : : /*
1562 : : * A "deep" free operation only makes sense on a list of pointers.
1563 : : */
1564 [ + + - + ]: 1637746 : Assert(IsPointerList(list));
1565 : 1637746 : list_free_private(list, true);
1566 : 1637746 : }
1567 : :
1568 : : /*
1569 : : * Return a shallow copy of the specified list.
1570 : : */
1571 : : List *
5377 peter_e@gmx.net 1572 : 7467827 : list_copy(const List *oldlist)
1573 : : {
1574 : : List *newlist;
1575 : :
8128 neilc@samurai.com 1576 [ + + ]: 7467827 : if (oldlist == NIL)
1577 : 1853543 : return NIL;
1578 : :
2600 tgl@sss.pgh.pa.us 1579 : 5614284 : newlist = new_list(oldlist->type, oldlist->length);
1580 : 5614284 : memcpy(newlist->elements, oldlist->elements,
1581 : 5614284 : newlist->length * sizeof(ListCell));
1582 : :
8128 neilc@samurai.com 1583 : 5614284 : check_list_invariants(newlist);
1584 : 5614284 : return newlist;
1585 : : }
1586 : :
1587 : : /*
1588 : : * Return a shallow copy of the specified list containing only the first 'len'
1589 : : * elements. If oldlist is shorter than 'len' then we copy the entire list.
1590 : : */
1591 : : List *
1506 drowley@postgresql.o 1592 : 971338 : list_copy_head(const List *oldlist, int len)
1593 : : {
1594 : : List *newlist;
1595 : :
1225 1596 [ + - + + ]: 971338 : if (oldlist == NIL || len <= 0)
1506 1597 : 822093 : return NIL;
1598 : :
1225 1599 : 149245 : len = Min(oldlist->length, len);
1600 : :
1506 1601 : 149245 : newlist = new_list(oldlist->type, len);
1602 : 149245 : memcpy(newlist->elements, oldlist->elements, len * sizeof(ListCell));
1603 : :
1604 : 149245 : check_list_invariants(newlist);
1605 : 149245 : return newlist;
1606 : : }
1607 : :
1608 : : /*
1609 : : * Return a shallow copy of the specified list, without the first N elements.
1610 : : */
1611 : : List *
5377 peter_e@gmx.net 1612 : 70242 : list_copy_tail(const List *oldlist, int nskip)
1613 : : {
1614 : : List *newlist;
1615 : :
8128 neilc@samurai.com 1616 [ - + ]: 70242 : if (nskip < 0)
8128 neilc@samurai.com 1617 :UBC 0 : nskip = 0; /* would it be better to elog? */
1618 : :
8128 neilc@samurai.com 1619 [ + - + + ]:CBC 70242 : if (oldlist == NIL || nskip >= oldlist->length)
1620 : 1535 : return NIL;
1621 : :
2600 tgl@sss.pgh.pa.us 1622 : 68707 : newlist = new_list(oldlist->type, oldlist->length - nskip);
1623 : 68707 : memcpy(newlist->elements, &oldlist->elements[nskip],
1624 : 68707 : newlist->length * sizeof(ListCell));
1625 : :
1626 : 68707 : check_list_invariants(newlist);
1627 : 68707 : return newlist;
1628 : : }
1629 : :
1630 : : /*
1631 : : * Return a deep copy of the specified list.
1632 : : *
1633 : : * The list elements are copied via copyObject(), so that this function's
1634 : : * idea of a "deep" copy is considerably deeper than what list_free_deep()
1635 : : * means by the same word.
1636 : : */
1637 : : List *
1638 : 3583083 : list_copy_deep(const List *oldlist)
1639 : : {
1640 : : List *newlist;
1641 : :
1642 [ - + ]: 3583083 : if (oldlist == NIL)
2600 tgl@sss.pgh.pa.us 1643 :UBC 0 : return NIL;
1644 : :
1645 : : /* This is only sensible for pointer Lists */
2600 tgl@sss.pgh.pa.us 1646 [ - + ]:CBC 3583083 : Assert(IsA(oldlist, List));
1647 : :
1648 : 3583083 : newlist = new_list(oldlist->type, oldlist->length);
1649 [ + + ]: 17705893 : for (int i = 0; i < newlist->length; i++)
1650 : 14122810 : lfirst(&newlist->elements[i]) =
1651 : 14122810 : copyObjectImpl(lfirst(&oldlist->elements[i]));
1652 : :
8128 neilc@samurai.com 1653 : 3583083 : check_list_invariants(newlist);
1654 : 3583083 : return newlist;
1655 : : }
1656 : :
1657 : : /*
1658 : : * Sort a list according to the specified comparator function.
1659 : : *
1660 : : * The list is sorted in-place.
1661 : : *
1662 : : * The comparator function is declared to receive arguments of type
1663 : : * const ListCell *; this allows it to use lfirst() and variants
1664 : : * without casting its arguments. Otherwise it behaves the same as
1665 : : * the comparator function for standard qsort().
1666 : : *
1667 : : * Like qsort(), this provides no guarantees about sort stability
1668 : : * for equal keys.
1669 : : *
1670 : : * This is based on qsort(), so it likewise has O(N log N) runtime.
1671 : : */
1672 : : void
2599 tgl@sss.pgh.pa.us 1673 : 246858 : 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 : 246858 : check_list_invariants(list);
1679 : :
1680 : : /* Nothing to do if there's less than two elements */
1681 : 246858 : len = list_length(list);
1682 [ + + ]: 246858 : if (len > 1)
1683 : 76086 : qsort(list->elements, len, sizeof(ListCell), (qsort_comparator) cmp);
3187 rhaas@postgresql.org 1684 : 246858 : }
1685 : :
1686 : : /*
1687 : : * list_sort comparator for sorting a list into ascending int order.
1688 : : */
1689 : : int
1988 tomas.vondra@postgre 1690 : 66 : list_int_cmp(const ListCell *p1, const ListCell *p2)
1691 : : {
1692 : 66 : int v1 = lfirst_int(p1);
1693 : 66 : int v2 = lfirst_int(p2);
1694 : :
923 nathan@postgresql.or 1695 : 66 : return pg_cmp_s32(v1, v2);
1696 : : }
1697 : :
1698 : : /*
1699 : : * list_sort comparator for sorting a list into ascending OID order.
1700 : : */
1701 : : int
2599 tgl@sss.pgh.pa.us 1702 : 79823 : list_oid_cmp(const ListCell *p1, const ListCell *p2)
1703 : : {
1704 : 79823 : Oid v1 = lfirst_oid(p1);
1705 : 79823 : Oid v2 = lfirst_oid(p2);
1706 : :
923 nathan@postgresql.or 1707 : 79823 : return pg_cmp_u32(v1, v2);
1708 : : }
|
