1/*--------------------------------------------------------------------
2 * Symbols referenced in this file:
3 * - lappend
4 * - new_list
5 * - new_tail_cell
6 * - lcons
7 * - new_head_cell
8 * - list_concat
9 * - list_nth
10 * - list_nth_cell
11 * - list_delete_cell
12 * - list_free
13 * - list_free_private
14 * - list_copy
15 * - list_copy_tail
16 * - list_truncate
17 *--------------------------------------------------------------------
18 */
19
20/*-------------------------------------------------------------------------
21 *
22 * list.c
23 * implementation for PostgreSQL generic linked list package
24 *
25 *
26 * Portions Copyright (c) 1996-2017, PostgreSQL Global Development PGGroup
27 * Portions Copyright (c) 1994, Regents of the University of California
28 *
29 *
30 * IDENTIFICATION
31 * src/backend/nodes/list.c
32 *
33 *-------------------------------------------------------------------------
34 */
35#include "pg_functions.hpp"
36#include "nodes/pg_list.hpp"
37
38
39/*
40 * Routines to simplify writing assertions about the type of a list; a
41 * NIL list is considered to be an empty list of any type.
42 */
43#define IsPointerList(l) ((l) == NIL || IsA((l), PGList))
44#define IsIntegerList(l) ((l) == NIL || IsA((l), IntList))
45#define IsOidList(l) ((l) == NIL || IsA((l), OidList))
46
47#ifdef USE_ASSERT_CHECKING
48/*
49 * Check that the specified PGList is valid (so far as we can tell).
50 */
51static void
52check_list_invariants(const PGList *list)
53{
54 if (list == NIL)
55 return;
56
57 Assert(list->length > 0);
58 Assert(list->head != NULL);
59 Assert(list->tail != NULL);
60
61 Assert(list->type == T_PGList ||
62 list->type == T_PGIntList ||
63 list->type == T_PGOidList);
64
65 if (list->length == 1)
66 Assert(list->head == list->tail);
67 if (list->length == 2)
68 Assert(list->head->next == list->tail);
69 Assert(list->tail->next == NULL);
70}
71#else
72#define check_list_invariants(l)
73#endif /* USE_ASSERT_CHECKING */
74
75/*
76 * Return a freshly allocated List. Since empty non-NIL lists are
77 * invalid, new_list() also allocates the head cell of the new list:
78 * the caller should be sure to fill in that cell's data.
79 */
80static PGList *
81new_list(PGNodeTag type)
82{
83 PGList *new_list;
84 PGListCell *new_head;
85
86 new_head = (PGListCell *) palloc(sizeof(*new_head));
87 new_head->next = NULL;
88 /* new_head->data is left undefined! */
89
90 new_list = (PGList *) palloc(sizeof(*new_list));
91 new_list->type = type;
92 new_list->length = 1;
93 new_list->head = new_head;
94 new_list->tail = new_head;
95
96 return new_list;
97}
98
99/*
100 * Allocate a new cell and make it the head of the specified
101 * list. Assumes the list it is passed is non-NIL.
102 *
103 * The data in the new head cell is undefined; the caller should be
104 * sure to fill it in
105 */
106static void
107new_head_cell(PGList *list)
108{
109 PGListCell *new_head;
110
111 new_head = (PGListCell *) palloc(sizeof(*new_head));
112 new_head->next = list->head;
113
114 list->head = new_head;
115 list->length++;
116}
117
118/*
119 * Allocate a new cell and make it the tail of the specified
120 * list. Assumes the list it is passed is non-NIL.
121 *
122 * The data in the new tail cell is undefined; the caller should be
123 * sure to fill it in
124 */
125static void
126new_tail_cell(PGList *list)
127{
128 PGListCell *new_tail;
129
130 new_tail = (PGListCell *) palloc(sizeof(*new_tail));
131 new_tail->next = NULL;
132
133 list->tail->next = new_tail;
134 list->tail = new_tail;
135 list->length++;
136}
137
138/*
139 * PGAppend a pointer to the list. A pointer to the modified list is
140 * returned. Note that this function may or may not destructively
141 * modify the list; callers should always use this function's return
142 * value, rather than continuing to use the pointer passed as the
143 * first argument.
144 */
145PGList *
146lappend(PGList *list, void *datum)
147{
148 Assert(IsPointerList(list));
149
150 if (list == NIL)
151 list = new_list(T_PGList);
152 else
153 new_tail_cell(list);
154
155 lfirst(list->tail) = datum;
156 check_list_invariants(list);
157 return list;
158}
159
160/*
161 * PGAppend an integer to the specified list. See lappend()
162 */
163
164
165/*
166 * PGAppend an OID to the specified list. See lappend()
167 */
168
169
170/*
171 * Add a new cell to the list, in the position after 'prev_cell'. The
172 * data in the cell is left undefined, and must be filled in by the
173 * caller. 'list' is assumed to be non-NIL, and 'prev_cell' is assumed
174 * to be non-NULL and a member of 'list'.
175 */
176
177
178/*
179 * Add a new cell to the specified list (which must be non-NIL);
180 * it will be placed after the list cell 'prev' (which must be
181 * non-NULL and a member of 'list'). The data placed in the new cell
182 * is 'datum'. The newly-constructed cell is returned.
183 */
184
185
186
187
188
189
190/*
191 * Prepend a new element to the list. A pointer to the modified list
192 * is returned. Note that this function may or may not destructively
193 * modify the list; callers should always use this function's return
194 * value, rather than continuing to use the pointer passed as the
195 * second argument.
196 *
197 * Caution: before Postgres 8.0, the original PGList was unmodified and
198 * could be considered to retain its separate identity. This is no longer
199 * the case.
200 */
201PGList *
202lcons(void *datum, PGList *list)
203{
204 Assert(IsPointerList(list));
205
206 if (list == NIL)
207 list = new_list(T_PGList);
208 else
209 new_head_cell(list);
210
211 lfirst(list->head) = datum;
212 check_list_invariants(list);
213 return list;
214}
215
216/*
217 * Prepend an integer to the list. See lcons()
218 */
219
220
221/*
222 * Prepend an OID to the list. See lcons()
223 */
224
225
226/*
227 * Concatenate list2 to the end of list1, and return list1. list1 is
228 * destructively changed. Callers should be sure to use the return
229 * value as the new pointer to the concatenated list: the 'list1'
230 * input pointer may or may not be the same as the returned pointer.
231 *
232 * The nodes in list2 are merely appended to the end of list1 in-place
233 * (i.e. they aren't copied; the two lists will share some of the same
234 * storage). Therefore, invoking list_free() on list2 will also
235 * invalidate a portion of list1.
236 */
237PGList *
238list_concat(PGList *list1, PGList *list2)
239{
240 if (list1 == NIL)
241 return list2;
242 if (list2 == NIL)
243 return list1;
244 if (list1 == list2)
245 elog(ERROR, "cannot list_concat() a list to itself");
246
247 Assert(list1->type == list2->type);
248
249 list1->length += list2->length;
250 list1->tail->next = list2->head;
251 list1->tail = list2->tail;
252
253 check_list_invariants(list1);
254 return list1;
255}
256
257/*
258 * Truncate 'list' to contain no more than 'new_size' elements. This
259 * modifies the list in-place! Despite this, callers should use the
260 * pointer returned by this function to refer to the newly truncated
261 * list -- it may or may not be the same as the pointer that was
262 * passed.
263 *
264 * Note that any cells removed by list_truncate() are NOT pfree'd.
265 */
266PGList *
267list_truncate(PGList *list, int new_size)
268{
269 PGListCell *cell;
270 int n;
271
272 if (new_size <= 0)
273 return NIL; /* truncate to zero length */
274
275 /* If asked to effectively extend the list, do nothing */
276 if (new_size >= list_length(list))
277 return list;
278
279 n = 1;
280 foreach(cell, list)
281 {
282 if (n == new_size)
283 {
284 cell->next = NULL;
285 list->tail = cell;
286 list->length = new_size;
287 check_list_invariants(list);
288 return list;
289 }
290 n++;
291 }
292
293 /* keep the compiler quiet; never reached */
294 Assert(false);
295 return list;
296}
297
298/*
299 * Locate the n'th cell (counting from 0) of the list. It is an assertion
300 * failure if there is no such cell.
301 */
302PGListCell *
303list_nth_cell(const PGList *list, int n)
304{
305 PGListCell *match;
306
307 Assert(list != NIL);
308 Assert(n >= 0);
309 Assert(n < list->length);
310 check_list_invariants(list);
311
312 /* Does the caller actually mean to fetch the tail? */
313 if (n == list->length - 1)
314 return list->tail;
315
316 for (match = list->head; n-- > 0; match = match->next)
317 ;
318
319 return match;
320}
321
322/*
323 * Return the data value contained in the n'th element of the
324 * specified list. (PGList elements begin at 0.)
325 */
326void *
327list_nth(const PGList *list, int n)
328{
329 Assert(IsPointerList(list));
330 return lfirst(list_nth_cell(list, n));
331}
332
333/*
334 * Delete 'cell' from 'list'; 'prev' is the previous element to 'cell'
335 * in 'list', if any (i.e. prev == NULL iff list->head == cell)
336 *
337 * The cell is pfree'd, as is the PGList header if this was the last member.
338 */
339PGList *
340list_delete_cell(PGList *list, PGListCell *cell, PGListCell *prev)
341{
342 check_list_invariants(list);
343 Assert(prev != NULL ? lnext(prev) == cell : list_head(list) == cell);
344
345 /*
346 * If we're about to delete the last node from the list, free the whole
347 * list instead and return NIL, which is the only valid representation of
348 * a zero-length list.
349 */
350 if (list->length == 1)
351 {
352 list_free(list);
353 return NIL;
354 }
355
356 /*
357 * Otherwise, adjust the necessary list links, deallocate the particular
358 * node we have just removed, and return the list we were given.
359 */
360 list->length--;
361
362 if (prev)
363 prev->next = cell->next;
364 else
365 list->head = cell->next;
366
367 if (list->tail == cell)
368 list->tail = prev;
369
370 pfree(cell);
371 return list;
372}
373
374/*
375 * Free all storage in a list, and optionally the pointed-to elements
376 */
377static void
378list_free_private(PGList *list, bool deep)
379{
380 PGListCell *cell;
381
382 check_list_invariants(list);
383
384 cell = list_head(list);
385 while (cell != NULL)
386 {
387 PGListCell *tmp = cell;
388
389 cell = lnext(cell);
390 if (deep)
391 pfree(lfirst(tmp));
392 pfree(tmp);
393 }
394
395 if (list)
396 pfree(list);
397}
398
399/*
400 * Free all the cells of the list, as well as the list itself. Any
401 * objects that are pointed-to by the cells of the list are NOT
402 * free'd.
403 *
404 * On return, the argument to this function has been freed, so the
405 * caller would be wise to set it to NIL for safety's sake.
406 */
407void
408list_free(PGList *list)
409{
410 list_free_private(list, false);
411}
412
413/*
414 * Free all the cells of the list, the list itself, and all the
415 * objects pointed-to by the cells of the list (each element in the
416 * list must contain a pointer to a palloc()'d region of memory!)
417 *
418 * On return, the argument to this function has been freed, so the
419 * caller would be wise to set it to NIL for safety's sake.
420 */
421
422
423/*
424 * Return a shallow copy of the specified list.
425 */
426PGList *
427list_copy(const PGList *oldlist)
428{
429 PGList *newlist;
430 PGListCell *newlist_prev;
431 PGListCell *oldlist_cur;
432
433 if (oldlist == NIL)
434 return NIL;
435
436 newlist = new_list(oldlist->type);
437 newlist->length = oldlist->length;
438
439 /*
440 * Copy over the data in the first cell; new_list() has already allocated
441 * the head cell itself
442 */
443 newlist->head->data = oldlist->head->data;
444
445 newlist_prev = newlist->head;
446 oldlist_cur = oldlist->head->next;
447 while (oldlist_cur)
448 {
449 PGListCell *newlist_cur;
450
451 newlist_cur = (PGListCell *) palloc(sizeof(*newlist_cur));
452 newlist_cur->data = oldlist_cur->data;
453 newlist_prev->next = newlist_cur;
454
455 newlist_prev = newlist_cur;
456 oldlist_cur = oldlist_cur->next;
457 }
458
459 newlist_prev->next = NULL;
460 newlist->tail = newlist_prev;
461
462 check_list_invariants(newlist);
463 return newlist;
464}
465
466/*
467 * Return a shallow copy of the specified list, without the first N elements.
468 */
469PGList *
470list_copy_tail(const PGList *oldlist, int nskip)
471{
472 PGList *newlist;
473 PGListCell *newlist_prev;
474 PGListCell *oldlist_cur;
475
476 if (nskip < 0)
477 nskip = 0; /* would it be better to elog? */
478
479 if (oldlist == NIL || nskip >= oldlist->length)
480 return NIL;
481
482 newlist = new_list(oldlist->type);
483 newlist->length = oldlist->length - nskip;
484
485 /*
486 * Skip over the unwanted elements.
487 */
488 oldlist_cur = oldlist->head;
489 while (nskip-- > 0)
490 oldlist_cur = oldlist_cur->next;
491
492 /*
493 * Copy over the data in the first remaining cell; new_list() has already
494 * allocated the head cell itself
495 */
496 newlist->head->data = oldlist_cur->data;
497
498 newlist_prev = newlist->head;
499 oldlist_cur = oldlist_cur->next;
500 while (oldlist_cur)
501 {
502 PGListCell *newlist_cur;
503
504 newlist_cur = (PGListCell *) palloc(sizeof(*newlist_cur));
505 newlist_cur->data = oldlist_cur->data;
506 newlist_prev->next = newlist_cur;
507
508 newlist_prev = newlist_cur;
509 oldlist_cur = oldlist_cur->next;
510 }
511
512 newlist_prev->next = NULL;
513 newlist->tail = newlist_prev;
514
515 check_list_invariants(newlist);
516 return newlist;
517}
518
519/*
520 * Temporary compatibility functions
521 *
522 * In order to avoid warnings for these function definitions, we need
523 * to include a prototype here as well as in pg_list.h. That's because
524 * we don't enable list API compatibility in list.c, so we
525 * don't see the prototypes for these functions.
526 */
527
528/*
529 * Given a list, return its length. This is merely defined for the
530 * sake of backward compatibility: we can't afford to define a macro
531 * called "length", so it must be a function. New code should use the
532 * list_length() macro in order to avoid the overhead of a function
533 * call.
534 */
535int length(const PGList *list);
536
537
538