← Back to branch summary

~vcs-imports/mammoth-replicator/trunk

« back to all changes in this revision

Viewing changes to src/backend/nodes/list.c

  • Committer: alvherre
  • Date: 2005-12-16 21:24:52 UTC
  • Revision ID: svn-v4:db760fc0-0f08-0410-9d63-cc6633f64896:trunk:1
Initial import of the REL8_0_3 sources from the Pgsql CVS repository.

Show diffs side-by-side

added added

removed removed

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