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