diff options
Diffstat (limited to 'src/backend/nodes/list.c')
| -rw-r--r-- | src/backend/nodes/list.c | 816 |
1 files changed, 470 insertions, 346 deletions
diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.c index 9897ab127d0..ecc2911496f 100644 --- a/src/backend/nodes/list.c +++ b/src/backend/nodes/list.c @@ -1,7 +1,9 @@ /*------------------------------------------------------------------------- * * list.c - * implementation for PostgreSQL generic linked list package + * implementation for PostgreSQL generic list package + * + * See comments in pg_list.h. * * * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group @@ -16,10 +18,35 @@ #include "postgres.h" #include "nodes/pg_list.h" +#include "utils/memutils.h" + + +/* + * The previous List implementation, since it used a separate palloc chunk + * for each cons cell, had the property that adding or deleting list cells + * did not move the storage of other existing cells in the list. Quite a + * bit of existing code depended on that, by retaining ListCell pointers + * across such operations on a list. There is no such guarantee in this + * implementation, so instead we have debugging support that is meant to + * help flush out now-broken assumptions. Defining DEBUG_LIST_MEMORY_USAGE + * while building this file causes the List operations to forcibly move + * all cells in a list whenever a cell is added or deleted. In combination + * with MEMORY_CONTEXT_CHECKING and/or Valgrind, this can usually expose + * broken code. It's a bit expensive though, as there's many more palloc + * cycles and a lot more data-copying than in a default build. + * + * By default, we enable this when building for Valgrind. + */ +#ifdef USE_VALGRIND +#define DEBUG_LIST_MEMORY_USAGE +#endif +/* Overhead for the fixed part of a List header, measured in ListCells */ +#define LIST_HEADER_OVERHEAD \ + ((int) ((offsetof(List, initial_elements) - 1) / sizeof(ListCell) + 1)) /* - * Routines to simplify writing assertions about the type of a list; a + * Macros to simplify writing assertions about the type of a list; a * NIL list is considered to be an empty list of any type. */ #define IsPointerList(l) ((l) == NIL || IsA((l), List)) @@ -37,50 +64,221 @@ check_list_invariants(const List *list) return; Assert(list->length > 0); - Assert(list->head != NULL); - Assert(list->tail != NULL); + Assert(list->length <= list->max_length); + Assert(list->elements != NULL); Assert(list->type == T_List || list->type == T_IntList || list->type == T_OidList); - - if (list->length == 1) - Assert(list->head == list->tail); - if (list->length == 2) - Assert(list->head->next == list->tail); - Assert(list->tail->next == NULL); } #else -#define check_list_invariants(l) +#define check_list_invariants(l) ((void) 0) #endif /* USE_ASSERT_CHECKING */ /* - * Return a freshly allocated List. Since empty non-NIL lists are - * invalid, new_list() also allocates the head cell of the new list: - * the caller should be sure to fill in that cell's data. + * Return a freshly allocated List with room for at least min_size cells. + * + * Since empty non-NIL lists are invalid, new_list() sets the initial length + * to min_size, effectively marking that number of cells as valid; the caller + * is responsible for filling in their data. */ static List * -new_list(NodeTag type) +new_list(NodeTag type, int min_size) { - List *new_list; - ListCell *new_head; + List *newlist; + int max_size; - new_head = (ListCell *) palloc(sizeof(*new_head)); - new_head->next = NULL; - /* new_head->data is left undefined! */ + Assert(min_size > 0); + + /* + * We allocate all the requested cells, and possibly some more, as part of + * the same palloc request as the List header. This is a big win for the + * typical case of short fixed-length lists. It can lose if we allocate a + * moderately long list and then it gets extended; we'll be wasting more + * initial_elements[] space than if we'd made the header small. However, + * rounding up the request as we do in the normal code path provides some + * defense against small extensions. + */ - new_list = (List *) palloc(sizeof(*new_list)); - new_list->type = type; - new_list->length = 1; - new_list->head = new_head; - new_list->tail = new_head; +#ifndef DEBUG_LIST_MEMORY_USAGE - return new_list; + /* + * Normally, we set up a list with some extra cells, to allow it to grow + * without a repalloc. Prefer cell counts chosen to make the total + * allocation a power-of-2, since palloc would round it up to that anyway. + * (That stops being true for very large allocations, but very long lists + * are infrequent, so it doesn't seem worth special logic for such cases.) + * + * The minimum allocation is 8 ListCell units, providing either 4 or 5 + * available ListCells depending on the machine's word width. Counting + * palloc's overhead, this uses the same amount of space as a one-cell + * list did in the old implementation, and less space for any longer list. + * + * We needn't worry about integer overflow; no caller passes min_size + * that's more than twice the size of an existing list, so the size limits + * within palloc will ensure that we don't overflow here. + */ + max_size = 8; /* semi-arbitrary small power of 2 */ + while (max_size < min_size + LIST_HEADER_OVERHEAD) + max_size *= 2; + max_size -= LIST_HEADER_OVERHEAD; +#else + + /* + * For debugging, don't allow any extra space. This forces any cell + * addition to go through enlarge_list() and thus move the existing data. + */ + max_size = min_size; +#endif + + newlist = (List *) palloc(offsetof(List, initial_elements) + + max_size * sizeof(ListCell)); + newlist->type = type; + newlist->length = min_size; + newlist->max_length = max_size; + newlist->elements = newlist->initial_elements; + + return newlist; } /* - * Allocate a new cell and make it the head of the specified - * list. Assumes the list it is passed is non-NIL. + * Enlarge an existing non-NIL List to have room for at least min_size cells. + * + * This does *not* update list->length, as some callers would find that + * inconvenient. (list->length had better be the correct number of existing + * valid cells, though.) + */ +static void +enlarge_list(List *list, int min_size) +{ + int new_max_len; + + Assert(min_size > list->max_length); /* else we shouldn't be here */ + +#ifndef DEBUG_LIST_MEMORY_USAGE + + /* + * As above, we prefer power-of-two total allocations; but here we need + * not account for list header overhead. The existing max length might + * not be a power of 2, so don't rely on that. + */ + new_max_len = 16; /* semi-arbitrary small power of 2 */ + while (new_max_len < min_size) + new_max_len *= 2; +#else + /* As above, don't allocate anything extra */ + new_max_len = min_size; +#endif + + if (list->elements == list->initial_elements) + { + List *newlist PG_USED_FOR_ASSERTS_ONLY; + + /* + * Replace original in-line allocation with a separate palloc block. + * Ensure it is in the same memory context as the List header. (The + * previous List implementation did not offer any guarantees about + * keeping all list cells in the same context, but it seems reasonable + * to create such a guarantee now.) + */ + list->elements = (ListCell *) + MemoryContextAlloc(GetMemoryChunkContext(list), + new_max_len * sizeof(ListCell)); + memcpy(list->elements, list->initial_elements, + list->length * sizeof(ListCell)); + + /* + * Currently, asking aset.c to reduce the allocated size of the List + * header is pointless in terms of reclaiming space, unless the list + * is very long. However, it seems worth doing anyway to cause the + * no-longer-needed initial_elements[] space to be cleared in + * debugging builds. + */ + newlist = (List *) repalloc(list, offsetof(List, initial_elements)); + + /* That better not have failed, nor moved the list header */ + Assert(newlist == list); + } + else + { +#ifndef DEBUG_LIST_MEMORY_USAGE + /* Normally, let repalloc deal with enlargement */ + list->elements = (ListCell *) repalloc(list->elements, + new_max_len * sizeof(ListCell)); +#else + /* + * repalloc() might enlarge the space in-place, which we don't want + * for debugging purposes, so forcibly move the data somewhere else. + */ + ListCell *newelements; + + newelements = (ListCell *) + MemoryContextAlloc(GetMemoryChunkContext(list), + new_max_len * sizeof(ListCell)); + memcpy(newelements, list->elements, + list->length * sizeof(ListCell)); + pfree(list->elements); + list->elements = newelements; +#endif + } + + list->max_length = new_max_len; +} + +/* + * Convenience functions to construct short Lists from given values. + * (These are normally invoked via the list_makeN macros.) + */ +List * +list_make1_impl(NodeTag t, ListCell datum1) +{ + List *list = new_list(t, 1); + + list->elements[0] = datum1; + check_list_invariants(list); + return list; +} + +List * +list_make2_impl(NodeTag t, ListCell datum1, ListCell datum2) +{ + List *list = new_list(t, 2); + + list->elements[0] = datum1; + list->elements[1] = datum2; + check_list_invariants(list); + return list; +} + +List * +list_make3_impl(NodeTag t, ListCell datum1, ListCell datum2, + ListCell datum3) +{ + List *list = new_list(t, 3); + + list->elements[0] = datum1; + list->elements[1] = datum2; + list->elements[2] = datum3; + check_list_invariants(list); + return list; +} + +List * +list_make4_impl(NodeTag t, ListCell datum1, ListCell datum2, + ListCell datum3, ListCell datum4) +{ + List *list = new_list(t, 4); + + list->elements[0] = datum1; + list->elements[1] = datum2; + list->elements[2] = datum3; + list->elements[3] = datum4; + check_list_invariants(list); + return list; +} + +/* + * Make room for a new head cell in the given (non-NIL) list. * * The data in the new head cell is undefined; the caller should be * sure to fill it in @@ -88,18 +286,17 @@ new_list(NodeTag type) static void new_head_cell(List *list) { - ListCell *new_head; - - new_head = (ListCell *) palloc(sizeof(*new_head)); - new_head->next = list->head; - - list->head = new_head; + /* Enlarge array if necessary */ + if (list->length >= list->max_length) + enlarge_list(list, list->length + 1); + /* Now shove the existing data over */ + memmove(&list->elements[1], &list->elements[0], + list->length * sizeof(ListCell)); list->length++; } /* - * Allocate a new cell and make it the tail of the specified - * list. Assumes the list it is passed is non-NIL. + * Make room for a new tail cell in the given (non-NIL) list. * * The data in the new tail cell is undefined; the caller should be * sure to fill it in @@ -107,13 +304,9 @@ new_head_cell(List *list) static void new_tail_cell(List *list) { - ListCell *new_tail; - - new_tail = (ListCell *) palloc(sizeof(*new_tail)); - new_tail->next = NULL; - - list->tail->next = new_tail; - list->tail = new_tail; + /* Enlarge array if necessary */ + if (list->length >= list->max_length) + enlarge_list(list, list->length + 1); list->length++; } @@ -130,11 +323,11 @@ lappend(List *list, void *datum) Assert(IsPointerList(list)); if (list == NIL) - list = new_list(T_List); + list = new_list(T_List, 1); else new_tail_cell(list); - lfirst(list->tail) = datum; + lfirst(list_tail(list)) = datum; check_list_invariants(list); return list; } @@ -148,11 +341,11 @@ lappend_int(List *list, int datum) Assert(IsIntegerList(list)); if (list == NIL) - list = new_list(T_IntList); + list = new_list(T_IntList, 1); else new_tail_cell(list); - lfirst_int(list->tail) = datum; + lfirst_int(list_tail(list)) = datum; check_list_invariants(list); return list; } @@ -166,82 +359,130 @@ lappend_oid(List *list, Oid datum) Assert(IsOidList(list)); if (list == NIL) - list = new_list(T_OidList); + list = new_list(T_OidList, 1); else new_tail_cell(list); - lfirst_oid(list->tail) = datum; + lfirst_oid(list_tail(list)) = datum; check_list_invariants(list); return list; } /* - * Add a new cell to the list, in the position after 'prev_cell'. The - * data in the cell is left undefined, and must be filled in by the - * caller. 'list' is assumed to be non-NIL, and 'prev_cell' is assumed - * to be non-NULL and a member of 'list'. + * Make room for a new cell at position 'pos' (measured from 0). + * The data in the cell is left undefined, and must be filled in by the + * caller. 'list' is assumed to be non-NIL, and 'pos' must be a valid + * list position, ie, 0 <= pos <= list's length. + * Returns address of the new cell. */ static ListCell * -add_new_cell(List *list, ListCell *prev_cell) +insert_new_cell(List *list, int pos) { - ListCell *new_cell; + Assert(pos >= 0 && pos <= list->length); + + /* Enlarge array if necessary */ + if (list->length >= list->max_length) + enlarge_list(list, list->length + 1); + /* Now shove the existing data over */ + if (pos < list->length) + memmove(&list->elements[pos + 1], &list->elements[pos], + (list->length - pos) * sizeof(ListCell)); + list->length++; - new_cell = (ListCell *) palloc(sizeof(*new_cell)); - /* new_cell->data is left undefined! */ - new_cell->next = prev_cell->next; - prev_cell->next = new_cell; + return &list->elements[pos]; +} - if (list->tail == prev_cell) - list->tail = new_cell; +/* + * Insert the given datum at position 'pos' (measured from 0) in the list. + * 'pos' must be valid, ie, 0 <= pos <= list's length. + */ +List * +list_insert_nth(List *list, int pos, void *datum) +{ + if (list == NIL) + { + Assert(pos == 0); + return list_make1(datum); + } + Assert(IsPointerList(list)); + lfirst(insert_new_cell(list, pos)) = datum; + check_list_invariants(list); + return list; +} - list->length++; +List * +list_insert_nth_int(List *list, int pos, int datum) +{ + if (list == NIL) + { + Assert(pos == 0); + return list_make1_int(datum); + } + Assert(IsIntegerList(list)); + lfirst_int(insert_new_cell(list, pos)) = datum; + check_list_invariants(list); + return list; +} - return new_cell; +List * +list_insert_nth_oid(List *list, int pos, Oid datum) +{ + if (list == NIL) + { + Assert(pos == 0); + return list_make1_oid(datum); + } + Assert(IsOidList(list)); + lfirst_oid(insert_new_cell(list, pos)) = datum; + check_list_invariants(list); + return list; +} + +/* + * Add a new cell to the list, in the position after 'prev_cell'. The + * data in the cell is left undefined, and must be filled in by the + * caller. 'list' is assumed to be non-NIL, and 'prev_cell' is assumed + * to be non-NULL and a member of 'list'. Returns address of new cell. + * + * Caution: prev_cell might no longer point into the list after this! + */ +static ListCell * +add_new_cell_after(List *list, ListCell *prev_cell) +{ + /* insert_new_cell will assert that this is in-range: */ + int pos = prev_cell - list->elements; + + return insert_new_cell(list, pos + 1); } /* * Add a new cell to the specified list (which must be non-NIL); * it will be placed after the list cell 'prev' (which must be * non-NULL and a member of 'list'). The data placed in the new cell - * is 'datum'. The newly-constructed cell is returned. + * is 'datum'. */ -ListCell * +void lappend_cell(List *list, ListCell *prev, void *datum) { - ListCell *new_cell; - Assert(IsPointerList(list)); - - new_cell = add_new_cell(list, prev); - lfirst(new_cell) = datum; + lfirst(add_new_cell_after(list, prev)) = datum; check_list_invariants(list); - return new_cell; } -ListCell * +void lappend_cell_int(List *list, ListCell *prev, int datum) { - ListCell *new_cell; - Assert(IsIntegerList(list)); - - new_cell = add_new_cell(list, prev); - lfirst_int(new_cell) = datum; + lfirst_int(add_new_cell_after(list, prev)) = datum; check_list_invariants(list); - return new_cell; } -ListCell * +void lappend_cell_oid(List *list, ListCell *prev, Oid datum) { - ListCell *new_cell; - Assert(IsOidList(list)); - - new_cell = add_new_cell(list, prev); - lfirst_oid(new_cell) = datum; + lfirst_oid(add_new_cell_after(list, prev)) = datum; check_list_invariants(list); - return new_cell; } /* @@ -261,11 +502,11 @@ lcons(void *datum, List *list) Assert(IsPointerList(list)); if (list == NIL) - list = new_list(T_List); + list = new_list(T_List, 1); else new_head_cell(list); - lfirst(list->head) = datum; + lfirst(list_head(list)) = datum; check_list_invariants(list); return list; } @@ -279,11 +520,11 @@ lcons_int(int datum, List *list) Assert(IsIntegerList(list)); if (list == NIL) - list = new_list(T_IntList); + list = new_list(T_IntList, 1); else new_head_cell(list); - lfirst_int(list->head) = datum; + lfirst_int(list_head(list)) = datum; check_list_invariants(list); return list; } @@ -297,41 +538,44 @@ lcons_oid(Oid datum, List *list) Assert(IsOidList(list)); if (list == NIL) - list = new_list(T_OidList); + list = new_list(T_OidList, 1); else new_head_cell(list); - lfirst_oid(list->head) = datum; + lfirst_oid(list_head(list)) = datum; check_list_invariants(list); return list; } /* * Concatenate list2 to the end of list1, and return list1. list1 is - * destructively changed. Callers should be sure to use the return - * value as the new pointer to the concatenated list: the 'list1' - * input pointer may or may not be the same as the returned pointer. - * - * The nodes in list2 are merely appended to the end of list1 in-place - * (i.e. they aren't copied; the two lists will share some of the same - * storage). Therefore, invoking list_free() on list2 will also - * invalidate a portion of list1. + * destructively changed, list2 is not. (However, in the case of pointer + * lists, list1 and list2 will point to the same structures.) Callers + * should be sure to use the return value as the new pointer to the + * concatenated list: the 'list1' input pointer may or may not be the + * same as the returned pointer. */ List * -list_concat(List *list1, List *list2) +list_concat(List *list1, const List *list2) { + int new_len; + if (list1 == NIL) - return list2; + return list_copy(list2); if (list2 == NIL) return list1; - if (list1 == list2) - elog(ERROR, "cannot list_concat() a list to itself"); Assert(list1->type == list2->type); - list1->length += list2->length; - list1->tail->next = list2->head; - list1->tail = list2->tail; + new_len = list1->length + list2->length; + /* Enlarge array if necessary */ + if (new_len > list1->max_length) + enlarge_list(list1, new_len); + + /* Even if list1 == list2, using memcpy should be safe here */ + memcpy(&list1->elements[list1->length], &list2->elements[0], + list2->length * sizeof(ListCell)); + list1->length = new_len; check_list_invariants(list1); return list1; @@ -349,93 +593,27 @@ list_concat(List *list1, List *list2) List * list_truncate(List *list, int new_size) { - ListCell *cell; - int n; - if (new_size <= 0) return NIL; /* truncate to zero length */ /* If asked to effectively extend the list, do nothing */ - if (new_size >= list_length(list)) - return list; + if (new_size < list_length(list)) + list->length = new_size; - n = 1; - foreach(cell, list) - { - if (n == new_size) - { - cell->next = NULL; - list->tail = cell; - list->length = new_size; - check_list_invariants(list); - return list; - } - n++; - } + /* + * Note: unlike the individual-list-cell deletion functions, we don't move + * the list cells to new storage, even in DEBUG_LIST_MEMORY_USAGE mode. + * This is because none of them can move in this operation, so just like + * in the old cons-cell-based implementation, this function doesn't + * invalidate any pointers to cells of the list. This is also the reason + * for not wiping the memory of the deleted cells: the old code didn't + * free them either. Perhaps later we'll tighten this up. + */ - /* keep the compiler quiet; never reached */ - Assert(false); return list; } /* - * Locate the n'th cell (counting from 0) of the list. It is an assertion - * failure if there is no such cell. - */ -ListCell * -list_nth_cell(const List *list, int n) -{ - ListCell *match; - - Assert(list != NIL); - Assert(n >= 0); - Assert(n < list->length); - check_list_invariants(list); - - /* Does the caller actually mean to fetch the tail? */ - if (n == list->length - 1) - return list->tail; - - for (match = list->head; n-- > 0; match = match->next) - ; - - return match; -} - -/* - * Return the data value contained in the n'th element of the - * specified list. (List elements begin at 0.) - */ -void * -list_nth(const List *list, int n) -{ - Assert(IsPointerList(list)); - return lfirst(list_nth_cell(list, n)); -} - -/* - * Return the integer value contained in the n'th element of the - * specified list. - */ -int -list_nth_int(const List *list, int n) -{ - Assert(IsIntegerList(list)); - return lfirst_int(list_nth_cell(list, n)); -} - -/* - * Return the OID value contained in the n'th element of the specified - * list. - */ -Oid -list_nth_oid(const List *list, int n) -{ - Assert(IsOidList(list)); - return lfirst_oid(list_nth_cell(list, n)); -} - -/* * Return true iff 'datum' is a member of the list. Equality is * determined via equal(), so callers should ensure that they pass a * Node as 'datum'. @@ -519,16 +697,16 @@ list_member_oid(const List *list, Oid datum) } /* - * Delete 'cell' from 'list'; 'prev' is the previous element to 'cell' - * in 'list', if any (i.e. prev == NULL iff list->head == cell) + * Delete the n'th cell (counting from 0) in list. * - * The cell is pfree'd, as is the List header if this was the last member. + * The List is pfree'd if this was the last member. */ List * -list_delete_cell(List *list, ListCell *cell, ListCell *prev) +list_delete_nth_cell(List *list, int n) { check_list_invariants(list); - Assert(prev != NULL ? lnext(prev) == cell : list_head(list) == cell); + + Assert(n >= 0 && n < list->length); /* * If we're about to delete the last node from the list, free the whole @@ -542,24 +720,62 @@ list_delete_cell(List *list, ListCell *cell, ListCell *prev) } /* - * Otherwise, adjust the necessary list links, deallocate the particular - * node we have just removed, and return the list we were given. + * Otherwise, we normally just collapse out the removed element. But for + * debugging purposes, move the whole list contents someplace else. + * + * (Note that we *must* keep the contents in the same memory context.) */ +#ifndef DEBUG_LIST_MEMORY_USAGE + memmove(&list->elements[n], &list->elements[n + 1], + (list->length - 1 - n) * sizeof(ListCell)); list->length--; +#else + { + ListCell *newelems; + int newmaxlen = list->length - 1; + + newelems = (ListCell *) + MemoryContextAlloc(GetMemoryChunkContext(list), + newmaxlen * sizeof(ListCell)); + memcpy(newelems, list->elements, n * sizeof(ListCell)); + memcpy(&newelems[n], &list->elements[n + 1], + (list->length - 1 - n) * sizeof(ListCell)); + if (list->elements != list->initial_elements) + pfree(list->elements); + else + { + /* + * As in enlarge_list(), tell palloc code we're not using the + * initial_elements space anymore. + */ + List *newlist PG_USED_FOR_ASSERTS_ONLY; + + newlist = (List *) repalloc(list, offsetof(List, initial_elements)); + Assert(newlist == list); + } + list->elements = newelems; + list->max_length = newmaxlen; + list->length--; + check_list_invariants(list); + } +#endif - if (prev) - prev->next = cell->next; - else - list->head = cell->next; - - if (list->tail == cell) - list->tail = prev; - - pfree(cell); return list; } /* + * Delete 'cell' from 'list'. + * + * The List is pfree'd if this was the last member. However, we do not + * touch any data the cell might've been pointing to. + */ +List * +list_delete_cell(List *list, ListCell *cell) +{ + return list_delete_nth_cell(list, cell - list->elements); +} + +/* * Delete the first cell in list that matches datum, if any. * Equality is determined via equal(). */ @@ -567,18 +783,14 @@ List * list_delete(List *list, void *datum) { ListCell *cell; - ListCell *prev; Assert(IsPointerList(list)); check_list_invariants(list); - prev = NULL; foreach(cell, list) { if (equal(lfirst(cell), datum)) - return list_delete_cell(list, cell, prev); - - prev = cell; + return list_delete_cell(list, cell); } /* Didn't find a match: return the list unmodified */ @@ -590,18 +802,14 @@ List * list_delete_ptr(List *list, void *datum) { ListCell *cell; - ListCell *prev; Assert(IsPointerList(list)); check_list_invariants(list); - prev = NULL; foreach(cell, list) { if (lfirst(cell) == datum) - return list_delete_cell(list, cell, prev); - - prev = cell; + return list_delete_cell(list, cell); } /* Didn't find a match: return the list unmodified */ @@ -613,18 +821,14 @@ List * list_delete_int(List *list, int datum) { ListCell *cell; - ListCell *prev; Assert(IsIntegerList(list)); check_list_invariants(list); - prev = NULL; foreach(cell, list) { if (lfirst_int(cell) == datum) - return list_delete_cell(list, cell, prev); - - prev = cell; + return list_delete_cell(list, cell); } /* Didn't find a match: return the list unmodified */ @@ -636,18 +840,14 @@ List * list_delete_oid(List *list, Oid datum) { ListCell *cell; - ListCell *prev; Assert(IsOidList(list)); check_list_invariants(list); - prev = NULL; foreach(cell, list) { if (lfirst_oid(cell) == datum) - return list_delete_cell(list, cell, prev); - - prev = cell; + return list_delete_cell(list, cell); } /* Didn't find a match: return the list unmodified */ @@ -659,8 +859,8 @@ list_delete_oid(List *list, Oid datum) * * This is useful to replace the Lisp-y code "list = lnext(list);" in cases * where the intent is to alter the list rather than just traverse it. - * Beware that the removed cell is freed, whereas the lnext() coding leaves - * the original list head intact if there's another pointer to it. + * Beware that the list is modified, whereas the Lisp-y coding leaves + * the original list head intact in case there's another pointer to it. */ List * list_delete_first(List *list) @@ -670,7 +870,7 @@ list_delete_first(List *list) if (list == NIL) return NIL; /* would an error be better? */ - return list_delete_cell(list, list_head(list), NULL); + return list_delete_nth_cell(list, 0); } /* @@ -688,7 +888,7 @@ list_delete_first(List *list) * in list1 (so it only performs a "union" if list1 is known unique to * start with). Also, if you are about to write "x = list_union(x, y)" * you probably want to use list_concat_unique() instead to avoid wasting - * the list cells of the old x list. + * the storage of the old x list. * * This function could probably be implemented a lot faster if it is a * performance bottleneck. @@ -1013,12 +1213,10 @@ list_append_unique_oid(List *list, Oid datum) * This is almost the same functionality as list_union(), but list1 is * modified in-place rather than being copied. However, callers of this * function may have strict ordering expectations -- i.e. that the relative - * order of those list2 elements that are not duplicates is preserved. Note - * also that list2's cells are not inserted in list1, so the analogy to - * list_concat() isn't perfect. + * order of those list2 elements that are not duplicates is preserved. */ List * -list_concat_unique(List *list1, List *list2) +list_concat_unique(List *list1, const List *list2) { ListCell *cell; @@ -1040,7 +1238,7 @@ list_concat_unique(List *list1, List *list2) * simple pointer equality. */ List * -list_concat_unique_ptr(List *list1, List *list2) +list_concat_unique_ptr(List *list1, const List *list2) { ListCell *cell; @@ -1061,7 +1259,7 @@ list_concat_unique_ptr(List *list1, List *list2) * This variant of list_concat_unique() operates upon lists of integers. */ List * -list_concat_unique_int(List *list1, List *list2) +list_concat_unique_int(List *list1, const List *list2) { ListCell *cell; @@ -1082,7 +1280,7 @@ list_concat_unique_int(List *list1, List *list2) * This variant of list_concat_unique() operates upon lists of OIDs. */ List * -list_concat_unique_oid(List *list1, List *list2) +list_concat_unique_oid(List *list1, const List *list2) { ListCell *cell; @@ -1105,23 +1303,19 @@ list_concat_unique_oid(List *list1, List *list2) static void list_free_private(List *list, bool deep) { - ListCell *cell; + if (list == NIL) + return; /* nothing to do */ check_list_invariants(list); - cell = list_head(list); - while (cell != NULL) + if (deep) { - ListCell *tmp = cell; - - cell = lnext(cell); - if (deep) - pfree(lfirst(tmp)); - pfree(tmp); + for (int i = 0; i < list->length; i++) + pfree(lfirst(&list->elements[i])); } - - if (list) - pfree(list); + if (list->elements != list->initial_elements) + pfree(list->elements); + pfree(list); } /* @@ -1163,37 +1357,13 @@ List * list_copy(const List *oldlist) { List *newlist; - ListCell *newlist_prev; - ListCell *oldlist_cur; if (oldlist == NIL) return NIL; - newlist = new_list(oldlist->type); - newlist->length = oldlist->length; - - /* - * Copy over the data in the first cell; new_list() has already allocated - * the head cell itself - */ - newlist->head->data = oldlist->head->data; - - newlist_prev = newlist->head; - oldlist_cur = oldlist->head->next; - while (oldlist_cur) - { - ListCell *newlist_cur; - - newlist_cur = (ListCell *) palloc(sizeof(*newlist_cur)); - newlist_cur->data = oldlist_cur->data; - newlist_prev->next = newlist_cur; - - newlist_prev = newlist_cur; - oldlist_cur = oldlist_cur->next; - } - - newlist_prev->next = NULL; - newlist->tail = newlist_prev; + newlist = new_list(oldlist->type, oldlist->length); + memcpy(newlist->elements, oldlist->elements, + newlist->length * sizeof(ListCell)); check_list_invariants(newlist); return newlist; @@ -1206,8 +1376,6 @@ List * list_copy_tail(const List *oldlist, int nskip) { List *newlist; - ListCell *newlist_prev; - ListCell *oldlist_cur; if (nskip < 0) nskip = 0; /* would it be better to elog? */ @@ -1215,38 +1383,36 @@ list_copy_tail(const List *oldlist, int nskip) if (oldlist == NIL || nskip >= oldlist->length) return NIL; - newlist = new_list(oldlist->type); - newlist->length = oldlist->length - nskip; - - /* - * Skip over the unwanted elements. - */ - oldlist_cur = oldlist->head; - while (nskip-- > 0) - oldlist_cur = oldlist_cur->next; + newlist = new_list(oldlist->type, oldlist->length - nskip); + memcpy(newlist->elements, &oldlist->elements[nskip], + newlist->length * sizeof(ListCell)); - /* - * Copy over the data in the first remaining cell; new_list() has already - * allocated the head cell itself - */ - newlist->head->data = oldlist_cur->data; + check_list_invariants(newlist); + return newlist; +} - newlist_prev = newlist->head; - oldlist_cur = oldlist_cur->next; - while (oldlist_cur) - { - ListCell *newlist_cur; +/* + * Return a deep copy of the specified list. + * + * The list elements are copied via copyObject(), so that this function's + * idea of a "deep" copy is considerably deeper than what list_free_deep() + * means by the same word. + */ +List * +list_copy_deep(const List *oldlist) +{ + List *newlist; - newlist_cur = (ListCell *) palloc(sizeof(*newlist_cur)); - newlist_cur->data = oldlist_cur->data; - newlist_prev->next = newlist_cur; + if (oldlist == NIL) + return NIL; - newlist_prev = newlist_cur; - oldlist_cur = oldlist_cur->next; - } + /* This is only sensible for pointer Lists */ + Assert(IsA(oldlist, List)); - newlist_prev->next = NULL; - newlist->tail = newlist_prev; + newlist = new_list(oldlist->type, oldlist->length); + for (int i = 0; i < newlist->length; i++) + lfirst(&newlist->elements[i]) = + copyObjectImpl(lfirst(&oldlist->elements[i])); check_list_invariants(newlist); return newlist; @@ -1259,6 +1425,8 @@ list_copy_tail(const List *oldlist, int nskip) * fresh copies of any pointed-to data. * * The comparator function receives arguments of type ListCell **. + * (XXX that's really inefficient now, but changing it seems like + * material for a standalone patch.) */ List * list_qsort(const List *list, list_qsort_comparator cmp) @@ -1266,7 +1434,6 @@ list_qsort(const List *list, list_qsort_comparator cmp) int len = list_length(list); ListCell **list_arr; List *newlist; - ListCell *newlist_prev; ListCell *cell; int i; @@ -1274,7 +1441,7 @@ list_qsort(const List *list, list_qsort_comparator cmp) if (len == 0) return NIL; - /* Flatten list cells into an array, so we can use qsort */ + /* We have to make an array of pointers to satisfy the API */ list_arr = (ListCell **) palloc(sizeof(ListCell *) * len); i = 0; foreach(cell, list) @@ -1283,29 +1450,10 @@ list_qsort(const List *list, list_qsort_comparator cmp) qsort(list_arr, len, sizeof(ListCell *), cmp); /* Construct new list (this code is much like list_copy) */ - newlist = new_list(list->type); - newlist->length = len; - - /* - * Copy over the data in the first cell; new_list() has already allocated - * the head cell itself - */ - newlist->head->data = list_arr[0]->data; + newlist = new_list(list->type, len); - newlist_prev = newlist->head; - for (i = 1; i < len; i++) - { - ListCell *newlist_cur; - - newlist_cur = (ListCell *) palloc(sizeof(*newlist_cur)); - newlist_cur->data = list_arr[i]->data; - newlist_prev->next = newlist_cur; - - newlist_prev = newlist_cur; - } - - newlist_prev->next = NULL; - newlist->tail = newlist_prev; + for (i = 0; i < len; i++) + newlist->elements[i] = *list_arr[i]; /* Might as well free the workspace array */ pfree(list_arr); @@ -1313,27 +1461,3 @@ list_qsort(const List *list, list_qsort_comparator cmp) check_list_invariants(newlist); return newlist; } - -/* - * Temporary compatibility functions - * - * In order to avoid warnings for these function definitions, we need - * to include a prototype here as well as in pg_list.h. That's because - * we don't enable list API compatibility in list.c, so we - * don't see the prototypes for these functions. - */ - -/* - * Given a list, return its length. This is merely defined for the - * sake of backward compatibility: we can't afford to define a macro - * called "length", so it must be a function. New code should use the - * list_length() macro in order to avoid the overhead of a function - * call. - */ -int length(const List *list); - -int -length(const List *list) -{ - return list_length(list); -} |