Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * list.c
4 : * implementation for PostgreSQL generic linked list package
5 : *
6 : *
7 : * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
8 : * Portions Copyright (c) 1994, Regents of the University of California
9 : *
10 : *
11 : * IDENTIFICATION
12 : * src/backend/nodes/list.c
13 : *
14 : *-------------------------------------------------------------------------
15 : */
16 : #include "postgres.h"
17 :
18 : #include "nodes/pg_list.h"
19 :
20 :
21 : /*
22 : * Routines to simplify writing assertions about the type of a list; a
23 : * NIL list is considered to be an empty list of any type.
24 : */
25 : #define IsPointerList(l) ((l) == NIL || IsA((l), List))
26 : #define IsIntegerList(l) ((l) == NIL || IsA((l), IntList))
27 : #define IsOidList(l) ((l) == NIL || IsA((l), OidList))
28 :
29 : #ifdef USE_ASSERT_CHECKING
30 : /*
31 : * Check that the specified List is valid (so far as we can tell).
32 : */
33 : static void
34 6903904 : check_list_invariants(const List *list)
35 : {
36 6903904 : if (list == NIL)
37 9190846 : return;
38 :
39 4616962 : Assert(list->length > 0);
40 4616962 : Assert(list->head != NULL);
41 4616962 : Assert(list->tail != NULL);
42 :
43 4616962 : Assert(list->type == T_List ||
44 : list->type == T_IntList ||
45 : list->type == T_OidList);
46 :
47 4616962 : if (list->length == 1)
48 2545980 : Assert(list->head == list->tail);
49 4616962 : if (list->length == 2)
50 859452 : Assert(list->head->next == list->tail);
51 4616962 : Assert(list->tail->next == NULL);
52 : }
53 : #else
54 : #define check_list_invariants(l)
55 : #endif /* USE_ASSERT_CHECKING */
56 :
57 : /*
58 : * Return a freshly allocated List. Since empty non-NIL lists are
59 : * invalid, new_list() also allocates the head cell of the new list:
60 : * the caller should be sure to fill in that cell's data.
61 : */
62 : static List *
63 2094593 : new_list(NodeTag type)
64 : {
65 : List *new_list;
66 : ListCell *new_head;
67 :
68 2094593 : new_head = (ListCell *) palloc(sizeof(*new_head));
69 2094593 : new_head->next = NULL;
70 : /* new_head->data is left undefined! */
71 :
72 2094593 : new_list = (List *) palloc(sizeof(*new_list));
73 2094593 : new_list->type = type;
74 2094593 : new_list->length = 1;
75 2094593 : new_list->head = new_head;
76 2094593 : new_list->tail = new_head;
77 :
78 2094593 : return new_list;
79 : }
80 :
81 : /*
82 : * Allocate a new cell and make it the head of the specified
83 : * list. Assumes the list it is passed is non-NIL.
84 : *
85 : * The data in the new head cell is undefined; the caller should be
86 : * sure to fill it in
87 : */
88 : static void
89 157866 : new_head_cell(List *list)
90 : {
91 : ListCell *new_head;
92 :
93 157866 : new_head = (ListCell *) palloc(sizeof(*new_head));
94 157866 : new_head->next = list->head;
95 :
96 157866 : list->head = new_head;
97 157866 : list->length++;
98 157866 : }
99 :
100 : /*
101 : * Allocate a new cell and make it the tail of the specified
102 : * list. Assumes the list it is passed is non-NIL.
103 : *
104 : * The data in the new tail cell is undefined; the caller should be
105 : * sure to fill it in
106 : */
107 : static void
108 1371231 : new_tail_cell(List *list)
109 : {
110 : ListCell *new_tail;
111 :
112 1371231 : new_tail = (ListCell *) palloc(sizeof(*new_tail));
113 1371231 : new_tail->next = NULL;
114 :
115 1371231 : list->tail->next = new_tail;
116 1371231 : list->tail = new_tail;
117 1371231 : list->length++;
118 1371231 : }
119 :
120 : /*
121 : * Append a pointer to the list. A pointer to the modified list is
122 : * returned. Note that this function may or may not destructively
123 : * modify the list; callers should always use this function's return
124 : * value, rather than continuing to use the pointer passed as the
125 : * first argument.
126 : */
127 : List *
128 2503709 : lappend(List *list, void *datum)
129 : {
130 2503709 : Assert(IsPointerList(list));
131 :
132 2503709 : if (list == NIL)
133 1182912 : list = new_list(T_List);
134 : else
135 1320797 : new_tail_cell(list);
136 :
137 2503709 : lfirst(list->tail) = datum;
138 2503709 : check_list_invariants(list);
139 2503709 : return list;
140 : }
141 :
142 : /*
143 : * Append an integer to the specified list. See lappend()
144 : */
145 : List *
146 83544 : lappend_int(List *list, int datum)
147 : {
148 83544 : Assert(IsIntegerList(list));
149 :
150 83544 : if (list == NIL)
151 58413 : list = new_list(T_IntList);
152 : else
153 25131 : new_tail_cell(list);
154 :
155 83544 : lfirst_int(list->tail) = datum;
156 83544 : check_list_invariants(list);
157 83544 : return list;
158 : }
159 :
160 : /*
161 : * Append an OID to the specified list. See lappend()
162 : */
163 : List *
164 114746 : lappend_oid(List *list, Oid datum)
165 : {
166 114746 : Assert(IsOidList(list));
167 :
168 114746 : if (list == NIL)
169 89443 : list = new_list(T_OidList);
170 : else
171 25303 : new_tail_cell(list);
172 :
173 114746 : lfirst_oid(list->tail) = datum;
174 114746 : check_list_invariants(list);
175 114746 : return list;
176 : }
177 :
178 : /*
179 : * Add a new cell to the list, in the position after 'prev_cell'. The
180 : * data in the cell is left undefined, and must be filled in by the
181 : * caller. 'list' is assumed to be non-NIL, and 'prev_cell' is assumed
182 : * to be non-NULL and a member of 'list'.
183 : */
184 : static ListCell *
185 11203 : add_new_cell(List *list, ListCell *prev_cell)
186 : {
187 : ListCell *new_cell;
188 :
189 11203 : new_cell = (ListCell *) palloc(sizeof(*new_cell));
190 : /* new_cell->data is left undefined! */
191 11203 : new_cell->next = prev_cell->next;
192 11203 : prev_cell->next = new_cell;
193 :
194 11203 : if (list->tail == prev_cell)
195 9753 : list->tail = new_cell;
196 :
197 11203 : list->length++;
198 :
199 11203 : return new_cell;
200 : }
201 :
202 : /*
203 : * Add a new cell to the specified list (which must be non-NIL);
204 : * it will be placed after the list cell 'prev' (which must be
205 : * non-NULL and a member of 'list'). The data placed in the new cell
206 : * is 'datum'. The newly-constructed cell is returned.
207 : */
208 : ListCell *
209 9131 : lappend_cell(List *list, ListCell *prev, void *datum)
210 : {
211 : ListCell *new_cell;
212 :
213 9131 : Assert(IsPointerList(list));
214 :
215 9131 : new_cell = add_new_cell(list, prev);
216 9131 : lfirst(new_cell) = datum;
217 9131 : check_list_invariants(list);
218 9131 : return new_cell;
219 : }
220 :
221 : ListCell *
222 0 : lappend_cell_int(List *list, ListCell *prev, int datum)
223 : {
224 : ListCell *new_cell;
225 :
226 0 : Assert(IsIntegerList(list));
227 :
228 0 : new_cell = add_new_cell(list, prev);
229 0 : lfirst_int(new_cell) = datum;
230 0 : check_list_invariants(list);
231 0 : return new_cell;
232 : }
233 :
234 : ListCell *
235 2072 : lappend_cell_oid(List *list, ListCell *prev, Oid datum)
236 : {
237 : ListCell *new_cell;
238 :
239 2072 : Assert(IsOidList(list));
240 :
241 2072 : new_cell = add_new_cell(list, prev);
242 2072 : lfirst_oid(new_cell) = datum;
243 2072 : check_list_invariants(list);
244 2072 : return new_cell;
245 : }
246 :
247 : /*
248 : * Prepend a new element to the list. A pointer to the modified list
249 : * is returned. Note that this function may or may not destructively
250 : * modify the list; callers should always use this function's return
251 : * value, rather than continuing to use the pointer passed as the
252 : * second argument.
253 : *
254 : * Caution: before Postgres 8.0, the original List was unmodified and
255 : * could be considered to retain its separate identity. This is no longer
256 : * the case.
257 : */
258 : List *
259 783687 : lcons(void *datum, List *list)
260 : {
261 783687 : Assert(IsPointerList(list));
262 :
263 783687 : if (list == NIL)
264 627741 : list = new_list(T_List);
265 : else
266 155946 : new_head_cell(list);
267 :
268 783687 : lfirst(list->head) = datum;
269 783687 : check_list_invariants(list);
270 783687 : return list;
271 : }
272 :
273 : /*
274 : * Prepend an integer to the list. See lcons()
275 : */
276 : List *
277 7047 : lcons_int(int datum, List *list)
278 : {
279 7047 : Assert(IsIntegerList(list));
280 :
281 7047 : if (list == NIL)
282 6861 : list = new_list(T_IntList);
283 : else
284 186 : new_head_cell(list);
285 :
286 7047 : lfirst_int(list->head) = datum;
287 7047 : check_list_invariants(list);
288 7047 : return list;
289 : }
290 :
291 : /*
292 : * Prepend an OID to the list. See lcons()
293 : */
294 : List *
295 9659 : lcons_oid(Oid datum, List *list)
296 : {
297 9659 : Assert(IsOidList(list));
298 :
299 9659 : if (list == NIL)
300 7925 : list = new_list(T_OidList);
301 : else
302 1734 : new_head_cell(list);
303 :
304 9659 : lfirst_oid(list->head) = datum;
305 9659 : check_list_invariants(list);
306 9659 : return list;
307 : }
308 :
309 : /*
310 : * Concatenate list2 to the end of list1, and return list1. list1 is
311 : * destructively changed. Callers should be sure to use the return
312 : * value as the new pointer to the concatenated list: the 'list1'
313 : * input pointer may or may not be the same as the returned pointer.
314 : *
315 : * The nodes in list2 are merely appended to the end of list1 in-place
316 : * (i.e. they aren't copied; the two lists will share some of the same
317 : * storage). Therefore, invoking list_free() on list2 will also
318 : * invalidate a portion of list1.
319 : */
320 : List *
321 242155 : list_concat(List *list1, List *list2)
322 : {
323 242155 : if (list1 == NIL)
324 166211 : return list2;
325 75944 : if (list2 == NIL)
326 49203 : return list1;
327 26741 : if (list1 == list2)
328 0 : elog(ERROR, "cannot list_concat() a list to itself");
329 :
330 26741 : Assert(list1->type == list2->type);
331 :
332 26741 : list1->length += list2->length;
333 26741 : list1->tail->next = list2->head;
334 26741 : list1->tail = list2->tail;
335 :
336 26741 : check_list_invariants(list1);
337 26741 : return list1;
338 : }
339 :
340 : /*
341 : * Truncate 'list' to contain no more than 'new_size' elements. This
342 : * modifies the list in-place! Despite this, callers should use the
343 : * pointer returned by this function to refer to the newly truncated
344 : * list -- it may or may not be the same as the pointer that was
345 : * passed.
346 : *
347 : * Note that any cells removed by list_truncate() are NOT pfree'd.
348 : */
349 : List *
350 9541 : list_truncate(List *list, int new_size)
351 : {
352 : ListCell *cell;
353 : int n;
354 :
355 9541 : if (new_size <= 0)
356 1982 : return NIL; /* truncate to zero length */
357 :
358 : /* If asked to effectively extend the list, do nothing */
359 7559 : if (new_size >= list_length(list))
360 6182 : return list;
361 :
362 1377 : n = 1;
363 2203 : foreach(cell, list)
364 : {
365 2203 : if (n == new_size)
366 : {
367 1377 : cell->next = NULL;
368 1377 : list->tail = cell;
369 1377 : list->length = new_size;
370 1377 : check_list_invariants(list);
371 1377 : return list;
372 : }
373 826 : n++;
374 : }
375 :
376 : /* keep the compiler quiet; never reached */
377 0 : Assert(false);
378 : return list;
379 : }
380 :
381 : /*
382 : * Locate the n'th cell (counting from 0) of the list. It is an assertion
383 : * failure if there is no such cell.
384 : */
385 : ListCell *
386 384596 : list_nth_cell(const List *list, int n)
387 : {
388 : ListCell *match;
389 :
390 384596 : Assert(list != NIL);
391 384596 : Assert(n >= 0);
392 384596 : Assert(n < list->length);
393 384596 : check_list_invariants(list);
394 :
395 : /* Does the caller actually mean to fetch the tail? */
396 384596 : if (n == list->length - 1)
397 261276 : return list->tail;
398 :
399 123320 : for (match = list->head; n-- > 0; match = match->next)
400 : ;
401 :
402 123320 : return match;
403 : }
404 :
405 : /*
406 : * Return the data value contained in the n'th element of the
407 : * specified list. (List elements begin at 0.)
408 : */
409 : void *
410 382190 : list_nth(const List *list, int n)
411 : {
412 382190 : Assert(IsPointerList(list));
413 382190 : return lfirst(list_nth_cell(list, n));
414 : }
415 :
416 : /*
417 : * Return the integer value contained in the n'th element of the
418 : * specified list.
419 : */
420 : int
421 598 : list_nth_int(const List *list, int n)
422 : {
423 598 : Assert(IsIntegerList(list));
424 598 : return lfirst_int(list_nth_cell(list, n));
425 : }
426 :
427 : /*
428 : * Return the OID value contained in the n'th element of the specified
429 : * list.
430 : */
431 : Oid
432 548 : list_nth_oid(const List *list, int n)
433 : {
434 548 : Assert(IsOidList(list));
435 548 : return lfirst_oid(list_nth_cell(list, n));
436 : }
437 :
438 : /*
439 : * Return true iff 'datum' is a member of the list. Equality is
440 : * determined via equal(), so callers should ensure that they pass a
441 : * Node as 'datum'.
442 : */
443 : bool
444 9892 : list_member(const List *list, const void *datum)
445 : {
446 : const ListCell *cell;
447 :
448 9892 : Assert(IsPointerList(list));
449 9892 : check_list_invariants(list);
450 :
451 13174 : foreach(cell, list)
452 : {
453 7369 : if (equal(lfirst(cell), datum))
454 4087 : return true;
455 : }
456 :
457 5805 : return false;
458 : }
459 :
460 : /*
461 : * Return true iff 'datum' is a member of the list. Equality is
462 : * determined by using simple pointer comparison.
463 : */
464 : bool
465 58476 : list_member_ptr(const List *list, const void *datum)
466 : {
467 : const ListCell *cell;
468 :
469 58476 : Assert(IsPointerList(list));
470 58476 : check_list_invariants(list);
471 :
472 83218 : foreach(cell, list)
473 : {
474 47816 : if (lfirst(cell) == datum)
475 23074 : return true;
476 : }
477 :
478 35402 : return false;
479 : }
480 :
481 : /*
482 : * Return true iff the integer 'datum' is a member of the list.
483 : */
484 : bool
485 6653 : list_member_int(const List *list, int datum)
486 : {
487 : const ListCell *cell;
488 :
489 6653 : Assert(IsIntegerList(list));
490 6653 : check_list_invariants(list);
491 :
492 8381 : foreach(cell, list)
493 : {
494 2780 : if (lfirst_int(cell) == datum)
495 1052 : return true;
496 : }
497 :
498 5601 : return false;
499 : }
500 :
501 : /*
502 : * Return true iff the OID 'datum' is a member of the list.
503 : */
504 : bool
505 1789148 : list_member_oid(const List *list, Oid datum)
506 : {
507 : const ListCell *cell;
508 :
509 1789148 : Assert(IsOidList(list));
510 1789148 : check_list_invariants(list);
511 :
512 1890111 : foreach(cell, list)
513 : {
514 124897 : if (lfirst_oid(cell) == datum)
515 23934 : return true;
516 : }
517 :
518 1765214 : return false;
519 : }
520 :
521 : /*
522 : * Delete 'cell' from 'list'; 'prev' is the previous element to 'cell'
523 : * in 'list', if any (i.e. prev == NULL iff list->head == cell)
524 : *
525 : * The cell is pfree'd, as is the List header if this was the last member.
526 : */
527 : List *
528 133125 : list_delete_cell(List *list, ListCell *cell, ListCell *prev)
529 : {
530 133125 : check_list_invariants(list);
531 133125 : Assert(prev != NULL ? lnext(prev) == cell : list_head(list) == cell);
532 :
533 : /*
534 : * If we're about to delete the last node from the list, free the whole
535 : * list instead and return NIL, which is the only valid representation of
536 : * a zero-length list.
537 : */
538 133125 : if (list->length == 1)
539 : {
540 68422 : list_free(list);
541 68422 : return NIL;
542 : }
543 :
544 : /*
545 : * Otherwise, adjust the necessary list links, deallocate the particular
546 : * node we have just removed, and return the list we were given.
547 : */
548 64703 : list->length--;
549 :
550 64703 : if (prev)
551 4456 : prev->next = cell->next;
552 : else
553 60247 : list->head = cell->next;
554 :
555 64703 : if (list->tail == cell)
556 3788 : list->tail = prev;
557 :
558 64703 : pfree(cell);
559 64703 : return list;
560 : }
561 :
562 : /*
563 : * Delete the first cell in list that matches datum, if any.
564 : * Equality is determined via equal().
565 : */
566 : List *
567 0 : list_delete(List *list, void *datum)
568 : {
569 : ListCell *cell;
570 : ListCell *prev;
571 :
572 0 : Assert(IsPointerList(list));
573 0 : check_list_invariants(list);
574 :
575 0 : prev = NULL;
576 0 : foreach(cell, list)
577 : {
578 0 : if (equal(lfirst(cell), datum))
579 0 : return list_delete_cell(list, cell, prev);
580 :
581 0 : prev = cell;
582 : }
583 :
584 : /* Didn't find a match: return the list unmodified */
585 0 : return list;
586 : }
587 :
588 : /* As above, but use simple pointer equality */
589 : List *
590 76277 : list_delete_ptr(List *list, void *datum)
591 : {
592 : ListCell *cell;
593 : ListCell *prev;
594 :
595 76277 : Assert(IsPointerList(list));
596 76277 : check_list_invariants(list);
597 :
598 76277 : prev = NULL;
599 77125 : foreach(cell, list)
600 : {
601 77125 : if (lfirst(cell) == datum)
602 76277 : return list_delete_cell(list, cell, prev);
603 :
604 848 : prev = cell;
605 : }
606 :
607 : /* Didn't find a match: return the list unmodified */
608 0 : return list;
609 : }
610 :
611 : /* As above, but for integers */
612 : List *
613 6 : list_delete_int(List *list, int datum)
614 : {
615 : ListCell *cell;
616 : ListCell *prev;
617 :
618 6 : Assert(IsIntegerList(list));
619 6 : check_list_invariants(list);
620 :
621 6 : prev = NULL;
622 6 : foreach(cell, list)
623 : {
624 6 : if (lfirst_int(cell) == datum)
625 6 : return list_delete_cell(list, cell, prev);
626 :
627 0 : prev = cell;
628 : }
629 :
630 : /* Didn't find a match: return the list unmodified */
631 0 : return list;
632 : }
633 :
634 : /* As above, but for OIDs */
635 : List *
636 147 : list_delete_oid(List *list, Oid datum)
637 : {
638 : ListCell *cell;
639 : ListCell *prev;
640 :
641 147 : Assert(IsOidList(list));
642 147 : check_list_invariants(list);
643 :
644 147 : prev = NULL;
645 147 : foreach(cell, list)
646 : {
647 72 : if (lfirst_oid(cell) == datum)
648 72 : return list_delete_cell(list, cell, prev);
649 :
650 0 : prev = cell;
651 : }
652 :
653 : /* Didn't find a match: return the list unmodified */
654 75 : return list;
655 : }
656 :
657 : /*
658 : * Delete the first element of the list.
659 : *
660 : * This is useful to replace the Lisp-y code "list = lnext(list);" in cases
661 : * where the intent is to alter the list rather than just traverse it.
662 : * Beware that the removed cell is freed, whereas the lnext() coding leaves
663 : * the original list head intact if there's another pointer to it.
664 : */
665 : List *
666 38654 : list_delete_first(List *list)
667 : {
668 38654 : check_list_invariants(list);
669 :
670 38654 : if (list == NIL)
671 0 : return NIL; /* would an error be better? */
672 :
673 38654 : return list_delete_cell(list, list_head(list), NULL);
674 : }
675 :
676 : /*
677 : * Generate the union of two lists. This is calculated by copying
678 : * list1 via list_copy(), then adding to it all the members of list2
679 : * that aren't already in list1.
680 : *
681 : * Whether an element is already a member of the list is determined
682 : * via equal().
683 : *
684 : * The returned list is newly-allocated, although the content of the
685 : * cells is the same (i.e. any pointed-to objects are not copied).
686 : *
687 : * NB: this function will NOT remove any duplicates that are present
688 : * in list1 (so it only performs a "union" if list1 is known unique to
689 : * start with). Also, if you are about to write "x = list_union(x, y)"
690 : * you probably want to use list_concat_unique() instead to avoid wasting
691 : * the list cells of the old x list.
692 : *
693 : * This function could probably be implemented a lot faster if it is a
694 : * performance bottleneck.
695 : */
696 : List *
697 370 : list_union(const List *list1, const List *list2)
698 : {
699 : List *result;
700 : const ListCell *cell;
701 :
702 370 : Assert(IsPointerList(list1));
703 370 : Assert(IsPointerList(list2));
704 :
705 370 : result = list_copy(list1);
706 766 : foreach(cell, list2)
707 : {
708 396 : if (!list_member(result, lfirst(cell)))
709 386 : result = lappend(result, lfirst(cell));
710 : }
711 :
712 370 : check_list_invariants(result);
713 370 : return result;
714 : }
715 :
716 : /*
717 : * This variant of list_union() determines duplicates via simple
718 : * pointer comparison.
719 : */
720 : List *
721 0 : list_union_ptr(const List *list1, const List *list2)
722 : {
723 : List *result;
724 : const ListCell *cell;
725 :
726 0 : Assert(IsPointerList(list1));
727 0 : Assert(IsPointerList(list2));
728 :
729 0 : result = list_copy(list1);
730 0 : foreach(cell, list2)
731 : {
732 0 : if (!list_member_ptr(result, lfirst(cell)))
733 0 : result = lappend(result, lfirst(cell));
734 : }
735 :
736 0 : check_list_invariants(result);
737 0 : return result;
738 : }
739 :
740 : /*
741 : * This variant of list_union() operates upon lists of integers.
742 : */
743 : List *
744 599 : list_union_int(const List *list1, const List *list2)
745 : {
746 : List *result;
747 : const ListCell *cell;
748 :
749 599 : Assert(IsIntegerList(list1));
750 599 : Assert(IsIntegerList(list2));
751 :
752 599 : result = list_copy(list1);
753 1213 : foreach(cell, list2)
754 : {
755 614 : if (!list_member_int(result, lfirst_int(cell)))
756 612 : result = lappend_int(result, lfirst_int(cell));
757 : }
758 :
759 599 : check_list_invariants(result);
760 599 : return result;
761 : }
762 :
763 : /*
764 : * This variant of list_union() operates upon lists of OIDs.
765 : */
766 : List *
767 0 : list_union_oid(const List *list1, const List *list2)
768 : {
769 : List *result;
770 : const ListCell *cell;
771 :
772 0 : Assert(IsOidList(list1));
773 0 : Assert(IsOidList(list2));
774 :
775 0 : result = list_copy(list1);
776 0 : foreach(cell, list2)
777 : {
778 0 : if (!list_member_oid(result, lfirst_oid(cell)))
779 0 : result = lappend_oid(result, lfirst_oid(cell));
780 : }
781 :
782 0 : check_list_invariants(result);
783 0 : return result;
784 : }
785 :
786 : /*
787 : * Return a list that contains all the cells that are in both list1 and
788 : * list2. The returned list is freshly allocated via palloc(), but the
789 : * cells themselves point to the same objects as the cells of the
790 : * input lists.
791 : *
792 : * Duplicate entries in list1 will not be suppressed, so it's only a true
793 : * "intersection" if list1 is known unique beforehand.
794 : *
795 : * This variant works on lists of pointers, and determines list
796 : * membership via equal(). Note that the list1 member will be pointed
797 : * to in the result.
798 : */
799 : List *
800 1285 : list_intersection(const List *list1, const List *list2)
801 : {
802 : List *result;
803 : const ListCell *cell;
804 :
805 1285 : if (list1 == NIL || list2 == NIL)
806 1185 : return NIL;
807 :
808 100 : Assert(IsPointerList(list1));
809 100 : Assert(IsPointerList(list2));
810 :
811 100 : result = NIL;
812 267 : foreach(cell, list1)
813 : {
814 167 : if (list_member(list2, lfirst(cell)))
815 37 : result = lappend(result, lfirst(cell));
816 : }
817 :
818 100 : check_list_invariants(result);
819 100 : return result;
820 : }
821 :
822 : /*
823 : * As list_intersection but operates on lists of integers.
824 : */
825 : List *
826 39 : list_intersection_int(const List *list1, const List *list2)
827 : {
828 : List *result;
829 : const ListCell *cell;
830 :
831 39 : if (list1 == NIL || list2 == NIL)
832 0 : return NIL;
833 :
834 39 : Assert(IsIntegerList(list1));
835 39 : Assert(IsIntegerList(list2));
836 :
837 39 : result = NIL;
838 86 : foreach(cell, list1)
839 : {
840 47 : if (list_member_int(list2, lfirst_int(cell)))
841 23 : result = lappend_int(result, lfirst_int(cell));
842 : }
843 :
844 39 : check_list_invariants(result);
845 39 : return result;
846 : }
847 :
848 : /*
849 : * Return a list that contains all the cells in list1 that are not in
850 : * list2. The returned list is freshly allocated via palloc(), but the
851 : * cells themselves point to the same objects as the cells of the
852 : * input lists.
853 : *
854 : * This variant works on lists of pointers, and determines list
855 : * membership via equal()
856 : */
857 : List *
858 1749 : list_difference(const List *list1, const List *list2)
859 : {
860 : const ListCell *cell;
861 1749 : List *result = NIL;
862 :
863 1749 : Assert(IsPointerList(list1));
864 1749 : Assert(IsPointerList(list2));
865 :
866 1749 : if (list2 == NIL)
867 140 : return list_copy(list1);
868 :
869 3441 : foreach(cell, list1)
870 : {
871 1832 : if (!list_member(list2, lfirst(cell)))
872 142 : result = lappend(result, lfirst(cell));
873 : }
874 :
875 1609 : check_list_invariants(result);
876 1609 : return result;
877 : }
878 :
879 : /*
880 : * This variant of list_difference() determines list membership via
881 : * simple pointer equality.
882 : */
883 : List *
884 1587 : list_difference_ptr(const List *list1, const List *list2)
885 : {
886 : const ListCell *cell;
887 1587 : List *result = NIL;
888 :
889 1587 : Assert(IsPointerList(list1));
890 1587 : Assert(IsPointerList(list2));
891 :
892 1587 : if (list2 == NIL)
893 1573 : return list_copy(list1);
894 :
895 29 : foreach(cell, list1)
896 : {
897 15 : if (!list_member_ptr(list2, lfirst(cell)))
898 10 : result = lappend(result, lfirst(cell));
899 : }
900 :
901 14 : check_list_invariants(result);
902 14 : return result;
903 : }
904 :
905 : /*
906 : * This variant of list_difference() operates upon lists of integers.
907 : */
908 : List *
909 281 : list_difference_int(const List *list1, const List *list2)
910 : {
911 : const ListCell *cell;
912 281 : List *result = NIL;
913 :
914 281 : Assert(IsIntegerList(list1));
915 281 : Assert(IsIntegerList(list2));
916 :
917 281 : if (list2 == NIL)
918 215 : return list_copy(list1);
919 :
920 191 : foreach(cell, list1)
921 : {
922 125 : if (!list_member_int(list2, lfirst_int(cell)))
923 53 : result = lappend_int(result, lfirst_int(cell));
924 : }
925 :
926 66 : check_list_invariants(result);
927 66 : return result;
928 : }
929 :
930 : /*
931 : * This variant of list_difference() operates upon lists of OIDs.
932 : */
933 : List *
934 0 : list_difference_oid(const List *list1, const List *list2)
935 : {
936 : const ListCell *cell;
937 0 : List *result = NIL;
938 :
939 0 : Assert(IsOidList(list1));
940 0 : Assert(IsOidList(list2));
941 :
942 0 : if (list2 == NIL)
943 0 : return list_copy(list1);
944 :
945 0 : foreach(cell, list1)
946 : {
947 0 : if (!list_member_oid(list2, lfirst_oid(cell)))
948 0 : result = lappend_oid(result, lfirst_oid(cell));
949 : }
950 :
951 0 : check_list_invariants(result);
952 0 : return result;
953 : }
954 :
955 : /*
956 : * Append datum to list, but only if it isn't already in the list.
957 : *
958 : * Whether an element is already a member of the list is determined
959 : * via equal().
960 : */
961 : List *
962 471 : list_append_unique(List *list, void *datum)
963 : {
964 471 : if (list_member(list, datum))
965 69 : return list;
966 : else
967 402 : return lappend(list, datum);
968 : }
969 :
970 : /*
971 : * This variant of list_append_unique() determines list membership via
972 : * simple pointer equality.
973 : */
974 : List *
975 20576 : list_append_unique_ptr(List *list, void *datum)
976 : {
977 20576 : if (list_member_ptr(list, datum))
978 3123 : return list;
979 : else
980 17453 : return lappend(list, datum);
981 : }
982 :
983 : /*
984 : * This variant of list_append_unique() operates upon lists of integers.
985 : */
986 : List *
987 0 : list_append_unique_int(List *list, int datum)
988 : {
989 0 : if (list_member_int(list, datum))
990 0 : return list;
991 : else
992 0 : return lappend_int(list, datum);
993 : }
994 :
995 : /*
996 : * This variant of list_append_unique() operates upon lists of OIDs.
997 : */
998 : List *
999 468 : list_append_unique_oid(List *list, Oid datum)
1000 : {
1001 468 : if (list_member_oid(list, datum))
1002 197 : return list;
1003 : else
1004 271 : return lappend_oid(list, datum);
1005 : }
1006 :
1007 : /*
1008 : * Append to list1 each member of list2 that isn't already in list1.
1009 : *
1010 : * Whether an element is already a member of the list is determined
1011 : * via equal().
1012 : *
1013 : * This is almost the same functionality as list_union(), but list1 is
1014 : * modified in-place rather than being copied. Note also that list2's cells
1015 : * are not inserted in list1, so the analogy to list_concat() isn't perfect.
1016 : */
1017 : List *
1018 12 : list_concat_unique(List *list1, List *list2)
1019 : {
1020 : ListCell *cell;
1021 :
1022 12 : Assert(IsPointerList(list1));
1023 12 : Assert(IsPointerList(list2));
1024 :
1025 24 : foreach(cell, list2)
1026 : {
1027 12 : if (!list_member(list1, lfirst(cell)))
1028 12 : list1 = lappend(list1, lfirst(cell));
1029 : }
1030 :
1031 12 : check_list_invariants(list1);
1032 12 : return list1;
1033 : }
1034 :
1035 : /*
1036 : * This variant of list_concat_unique() determines list membership via
1037 : * simple pointer equality.
1038 : */
1039 : List *
1040 0 : list_concat_unique_ptr(List *list1, List *list2)
1041 : {
1042 : ListCell *cell;
1043 :
1044 0 : Assert(IsPointerList(list1));
1045 0 : Assert(IsPointerList(list2));
1046 :
1047 0 : foreach(cell, list2)
1048 : {
1049 0 : if (!list_member_ptr(list1, lfirst(cell)))
1050 0 : list1 = lappend(list1, lfirst(cell));
1051 : }
1052 :
1053 0 : check_list_invariants(list1);
1054 0 : return list1;
1055 : }
1056 :
1057 : /*
1058 : * This variant of list_concat_unique() operates upon lists of integers.
1059 : */
1060 : List *
1061 0 : list_concat_unique_int(List *list1, List *list2)
1062 : {
1063 : ListCell *cell;
1064 :
1065 0 : Assert(IsIntegerList(list1));
1066 0 : Assert(IsIntegerList(list2));
1067 :
1068 0 : foreach(cell, list2)
1069 : {
1070 0 : if (!list_member_int(list1, lfirst_int(cell)))
1071 0 : list1 = lappend_int(list1, lfirst_int(cell));
1072 : }
1073 :
1074 0 : check_list_invariants(list1);
1075 0 : return list1;
1076 : }
1077 :
1078 : /*
1079 : * This variant of list_concat_unique() operates upon lists of OIDs.
1080 : */
1081 : List *
1082 259 : list_concat_unique_oid(List *list1, List *list2)
1083 : {
1084 : ListCell *cell;
1085 :
1086 259 : Assert(IsOidList(list1));
1087 259 : Assert(IsOidList(list2));
1088 :
1089 259 : foreach(cell, list2)
1090 : {
1091 0 : if (!list_member_oid(list1, lfirst_oid(cell)))
1092 0 : list1 = lappend_oid(list1, lfirst_oid(cell));
1093 : }
1094 :
1095 259 : check_list_invariants(list1);
1096 259 : return list1;
1097 : }
1098 :
1099 : /*
1100 : * Free all storage in a list, and optionally the pointed-to elements
1101 : */
1102 : static void
1103 740851 : list_free_private(List *list, bool deep)
1104 : {
1105 : ListCell *cell;
1106 :
1107 740851 : check_list_invariants(list);
1108 :
1109 740851 : cell = list_head(list);
1110 1761436 : while (cell != NULL)
1111 : {
1112 279734 : ListCell *tmp = cell;
1113 :
1114 279734 : cell = lnext(cell);
1115 279734 : if (deep)
1116 707 : pfree(lfirst(tmp));
1117 279734 : pfree(tmp);
1118 : }
1119 :
1120 740851 : if (list)
1121 170018 : pfree(list);
1122 740851 : }
1123 :
1124 : /*
1125 : * Free all the cells of the list, as well as the list itself. Any
1126 : * objects that are pointed-to by the cells of the list are NOT
1127 : * free'd.
1128 : *
1129 : * On return, the argument to this function has been freed, so the
1130 : * caller would be wise to set it to NIL for safety's sake.
1131 : */
1132 : void
1133 706144 : list_free(List *list)
1134 : {
1135 706144 : list_free_private(list, false);
1136 706144 : }
1137 :
1138 : /*
1139 : * Free all the cells of the list, the list itself, and all the
1140 : * objects pointed-to by the cells of the list (each element in the
1141 : * list must contain a pointer to a palloc()'d region of memory!)
1142 : *
1143 : * On return, the argument to this function has been freed, so the
1144 : * caller would be wise to set it to NIL for safety's sake.
1145 : */
1146 : void
1147 34707 : list_free_deep(List *list)
1148 : {
1149 : /*
1150 : * A "deep" free operation only makes sense on a list of pointers.
1151 : */
1152 34707 : Assert(IsPointerList(list));
1153 34707 : list_free_private(list, true);
1154 34707 : }
1155 :
1156 : /*
1157 : * Return a shallow copy of the specified list.
1158 : */
1159 : List *
1160 165436 : list_copy(const List *oldlist)
1161 : {
1162 : List *newlist;
1163 : ListCell *newlist_prev;
1164 : ListCell *oldlist_cur;
1165 :
1166 165436 : if (oldlist == NIL)
1167 47253 : return NIL;
1168 :
1169 118183 : newlist = new_list(oldlist->type);
1170 118183 : newlist->length = oldlist->length;
1171 :
1172 : /*
1173 : * Copy over the data in the first cell; new_list() has already allocated
1174 : * the head cell itself
1175 : */
1176 118183 : newlist->head->data = oldlist->head->data;
1177 :
1178 118183 : newlist_prev = newlist->head;
1179 118183 : oldlist_cur = oldlist->head->next;
1180 329574 : while (oldlist_cur)
1181 : {
1182 : ListCell *newlist_cur;
1183 :
1184 93208 : newlist_cur = (ListCell *) palloc(sizeof(*newlist_cur));
1185 93208 : newlist_cur->data = oldlist_cur->data;
1186 93208 : newlist_prev->next = newlist_cur;
1187 :
1188 93208 : newlist_prev = newlist_cur;
1189 93208 : oldlist_cur = oldlist_cur->next;
1190 : }
1191 :
1192 118183 : newlist_prev->next = NULL;
1193 118183 : newlist->tail = newlist_prev;
1194 :
1195 118183 : check_list_invariants(newlist);
1196 118183 : return newlist;
1197 : }
1198 :
1199 : /*
1200 : * Return a shallow copy of the specified list, without the first N elements.
1201 : */
1202 : List *
1203 3216 : list_copy_tail(const List *oldlist, int nskip)
1204 : {
1205 : List *newlist;
1206 : ListCell *newlist_prev;
1207 : ListCell *oldlist_cur;
1208 :
1209 3216 : if (nskip < 0)
1210 0 : nskip = 0; /* would it be better to elog? */
1211 :
1212 3216 : if (oldlist == NIL || nskip >= oldlist->length)
1213 101 : return NIL;
1214 :
1215 3115 : newlist = new_list(oldlist->type);
1216 3115 : newlist->length = oldlist->length - nskip;
1217 :
1218 : /*
1219 : * Skip over the unwanted elements.
1220 : */
1221 3115 : oldlist_cur = oldlist->head;
1222 6701 : while (nskip-- > 0)
1223 471 : oldlist_cur = oldlist_cur->next;
1224 :
1225 : /*
1226 : * Copy over the data in the first remaining cell; new_list() has already
1227 : * allocated the head cell itself
1228 : */
1229 3115 : newlist->head->data = oldlist_cur->data;
1230 :
1231 3115 : newlist_prev = newlist->head;
1232 3115 : oldlist_cur = oldlist_cur->next;
1233 60964 : while (oldlist_cur)
1234 : {
1235 : ListCell *newlist_cur;
1236 :
1237 54734 : newlist_cur = (ListCell *) palloc(sizeof(*newlist_cur));
1238 54734 : newlist_cur->data = oldlist_cur->data;
1239 54734 : newlist_prev->next = newlist_cur;
1240 :
1241 54734 : newlist_prev = newlist_cur;
1242 54734 : oldlist_cur = oldlist_cur->next;
1243 : }
1244 :
1245 3115 : newlist_prev->next = NULL;
1246 3115 : newlist->tail = newlist_prev;
1247 :
1248 3115 : check_list_invariants(newlist);
1249 3115 : return newlist;
1250 : }
1251 :
1252 : /*
1253 : * Temporary compatibility functions
1254 : *
1255 : * In order to avoid warnings for these function definitions, we need
1256 : * to include a prototype here as well as in pg_list.h. That's because
1257 : * we don't enable list API compatibility in list.c, so we
1258 : * don't see the prototypes for these functions.
1259 : */
1260 :
1261 : /*
1262 : * Given a list, return its length. This is merely defined for the
1263 : * sake of backward compatibility: we can't afford to define a macro
1264 : * called "length", so it must be a function. New code should use the
1265 : * list_length() macro in order to avoid the overhead of a function
1266 : * call.
1267 : */
1268 : int length(const List *list);
1269 :
1270 : int
1271 0 : length(const List *list)
1272 : {
1273 0 : return list_length(list);
1274 : }
|
