From d0b4399d81f39decccb23fa38f772b71b51bf96a Mon Sep 17 00:00:00 2001 From: Neil Conway Date: Wed, 26 May 2004 04:41:50 +0000 Subject: Reimplement the linked list data structure used throughout the backend. In the past, we used a 'Lispy' linked list implementation: a "list" was merely a pointer to the head node of the list. The problem with that design is that it makes lappend() and length() linear time. This patch fixes that problem (and others) by maintaining a count of the list length and a pointer to the tail node along with each head node pointer. A "list" is now a pointer to a structure containing some meta-data about the list; the head and tail pointers in that structure refer to ListCell structures that maintain the actual linked list of nodes. The function names of the list API have also been changed to, I hope, be more logically consistent. By default, the old function names are still available; they will be disabled-by-default once the rest of the tree has been updated to use the new API names. --- src/backend/nodes/list.c | 1302 +++++++++++++++++++++++++++++++--------------- 1 file changed, 881 insertions(+), 421 deletions(-) (limited to 'src/backend/nodes/list.c') diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.c index aeda02d1702..6fd7b064a6b 100644 --- a/src/backend/nodes/list.c +++ b/src/backend/nodes/list.c @@ -9,700 +9,1160 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/nodes/list.c,v 1.56 2004/01/07 18:43:36 neilc Exp $ + * $PostgreSQL: pgsql/src/backend/nodes/list.c,v 1.57 2004/05/26 04:41:19 neilc Exp $ * *------------------------------------------------------------------------- */ +#define DISABLE_LIST_COMPAT + #include "postgres.h" +#include "nodes/pg_list.h" -#include "nodes/parsenodes.h" +/* + * Routines 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)) +#define IsIntegerList(l) ((l) == NIL || IsA((l), IntList)) +#define IsOidList(l) ((l) == NIL || IsA((l), OidList)) +#ifdef USE_ASSERT_CHECKING /* - * lcons - * - * Add obj to the front of list, or make a new list if 'list' is NIL + * Check that the specified List is valid (so far as we can tell). */ -List * -lcons(void *obj, List *list) +static void +check_list_invariants(List *list) { - List *l = makeNode(List); + if (list == NIL) + return; + + Assert(list->length > 0); + Assert(list->head != NULL); + Assert(list->tail != 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) +#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. + */ +static List * +new_list(NodeTag type) +{ + List *new_list; + ListCell *new_head; + + new_head = (ListCell *) palloc(sizeof(*new_head)); + new_head->next = NULL; + /* new_head->data is left undefined! */ - lfirst(l) = obj; - lnext(l) = list; - return l; + 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; + + return new_list; } /* - * lconsi + * Allocate a new cell and make it the head of the specified + * list. Assumes the list it is passed is non-NIL. * - * Same as lcons, but for integer data + * The data in the new head cell is undefined; the caller should be + * sure to fill it in */ -List * -lconsi(int datum, List *list) +static void +new_head_cell(List *list) { - List *l = makeNode(List); + ListCell *new_head; + + new_head = (ListCell *) palloc(sizeof(*new_head)); + new_head->next = list->head; - lfirsti(l) = datum; - lnext(l) = list; - return l; + list->head = new_head; + list->length++; } /* - * lconso + * Allocate a new cell and make it the tail of the specified + * list. Assumes the list it is passed is non-NIL. * - * Same as lcons, but for Oid data + * The data in the new tail cell is undefined; the caller should be + * sure to fill it in */ -List * -lconso(Oid datum, List *list) +static void +new_tail_cell(List *list) { - List *l = makeNode(List); + ListCell *new_tail; + + new_tail = (ListCell *) palloc(sizeof(*new_tail)); + new_tail->next = NULL; - lfirsto(l) = datum; - lnext(l) = list; - return l; + list->tail->next = new_tail; + list->tail = new_tail; + list->length++; } /* - * lappend - * - * Add obj to the end of list, or make a new list if 'list' is NIL - * - * MORE EXPENSIVE THAN lcons + * Append a pointer to the list. A pointer to the modified list is + * returned. Note that this function may or may not destructively + * modify the list; callers should always use this function's return + * value, rather than continuing to use the pointer passed as the + * first argument. */ List * lappend(List *list, void *datum) { - return nconc(list, makeList1(datum)); + Assert(IsPointerList(list)); + + if (list == NIL) + list = new_list(T_List); + else + new_tail_cell(list); + + lfirst(list->tail) = datum; + check_list_invariants(list); + return list; } /* - * lappendi - * - * Same as lappend, but for integers + * Append an integer to the specified list. See lappend() */ -List * -lappendi(List *list, int datum) +List * +lappend_int(List *list, int datum) { - return nconc(list, makeListi1(datum)); + Assert(IsIntegerList(list)); + + if (list == NIL) + list = new_list(T_IntList); + else + new_tail_cell(list); + + lfirst_int(list->tail) = datum; + check_list_invariants(list); + return list; } /* - * lappendo - * - * Same as lappend, but for Oids + * Append an OID to the specified list. See lappend() */ -List * -lappendo(List *list, Oid datum) +List * +lappend_oid(List *list, Oid datum) { - return nconc(list, makeListo1(datum)); + Assert(IsOidList(list)); + + if (list == NIL) + list = new_list(T_OidList); + else + new_tail_cell(list); + + lfirst_oid(list->tail) = datum; + check_list_invariants(list); + return list; } /* - * nconc - * - * Concat l2 on to the end of l1 - * - * NB: l1 is destructively changed! Use nconc(listCopy(l1), l2) - * if you need to make a merged list without touching the original lists. + * 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'. */ -List * -nconc(List *l1, List *l2) +static ListCell * +add_new_cell(List *list, ListCell *prev_cell) { - List *temp; + ListCell *new_cell; - if (l1 == NIL) - return l2; - if (l2 == NIL) - return l1; - if (l1 == l2) - elog(ERROR, "cannot nconc a list to itself"); + new_cell = (ListCell *) palloc(sizeof(*new_cell)); + /* new_cell->data is left undefined! */ + new_cell->next = prev_cell->next; + prev_cell->next = new_cell; - for (temp = l1; lnext(temp) != NIL; temp = lnext(temp)) - ; + if (list->tail == prev_cell) + list->tail = new_cell; + + list->length++; - lnext(temp) = l2; - return l1; /* list1 is now list1+list2 */ + return new_cell; } /* - * FastAppend - append to a FastList. + * 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. + */ +ListCell * +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; + check_list_invariants(list); + return new_cell; +} + +ListCell * +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; + check_list_invariants(list); + return new_cell; +} + +ListCell * +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; + check_list_invariants(list); + return new_cell; +} + +/* + * Prepend a new element to the list. A pointer to the modified list + * is returned. Note that this function may or may not destructively + * modify the list; callers should always use this function's return + * value, rather than continuing to use the pointer passed as the + * second argument. * - * For long lists this is significantly faster than repeated lappend's, - * since we avoid having to chase down the list again each time. + * Caution: before Postgres 7.5, the original List was unmodified and + * could be considered to retain its separate identity. This is no longer + * the case. */ -void -FastAppend(FastList *fl, void *datum) +List * +lcons(void *datum, List *list) { - List *cell = makeList1(datum); + Assert(IsPointerList(list)); - if (fl->tail) - { - lnext(fl->tail) = cell; - fl->tail = cell; - } + if (list == NIL) + list = new_list(T_List); else - { - /* First cell of list */ - Assert(fl->head == NIL); - fl->head = fl->tail = cell; - } + new_head_cell(list); + + lfirst(list->head) = datum; + check_list_invariants(list); + return list; } /* - * FastAppendi - same for integers + * Prepend an integer to the list. See lcons() */ -void -FastAppendi(FastList *fl, int datum) +List * +lcons_int(int datum, List *list) { - List *cell = makeListi1(datum); + Assert(IsIntegerList(list)); - if (fl->tail) - { - lnext(fl->tail) = cell; - fl->tail = cell; - } + if (list == NIL) + list = new_list(T_IntList); else - { - /* First cell of list */ - Assert(fl->head == NIL); - fl->head = fl->tail = cell; - } + new_head_cell(list); + + lfirst_int(list->head) = datum; + check_list_invariants(list); + return list; } /* - * FastAppendo - same for Oids + * Prepend an OID to the list. See lcons() */ -void -FastAppendo(FastList *fl, Oid datum) +List * +lcons_oid(Oid datum, List *list) { - List *cell = makeListo1(datum); + Assert(IsOidList(list)); - if (fl->tail) - { - lnext(fl->tail) = cell; - fl->tail = cell; - } + if (list == NIL) + list = new_list(T_OidList); else - { - /* First cell of list */ - Assert(fl->head == NIL); - fl->head = fl->tail = cell; - } + new_head_cell(list); + + lfirst_oid(list->head) = datum; + check_list_invariants(list); + return list; } /* - * FastConc - nconc() for FastList building + * 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. * - * Note that the cells of the second argument are absorbed into the FastList. + * 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. */ -void -FastConc(FastList *fl, List *cells) +List * +list_concat(List *list1, List *list2) { - if (cells == NIL) - return; /* nothing to do */ - if (fl->tail) - lnext(fl->tail) = cells; - else - { - /* First cell of list */ - Assert(fl->head == NIL); - fl->head = cells; - } - while (lnext(cells) != NIL) - cells = lnext(cells); - fl->tail = cells; + if (list1 == NIL) + return 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; + + check_list_invariants(list1); + return list1; } /* - * FastConcFast - nconc() for FastList building + * Truncate 'list' to contain no more than 'new_size' elements. This + * modifies the list in-place! Despite this, callers should use the + * pointer returned by this function to refer to the newly truncated + * list -- it may or may not be the same as the pointer that was + * passed. * - * Note that the cells of the second argument are absorbed into the first. + * Note that any cells removed by list_truncate() are NOT pfree'd. */ -void -FastConcFast(FastList *fl, FastList *fl2) +List * +list_truncate(List *list, int new_size) { - if (fl2->head == NIL) - return; /* nothing to do */ - if (fl->tail) - lnext(fl->tail) = fl2->head; - else + 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; + + n = 1; + foreach (cell, list) { - /* First cell of list */ - Assert(fl->head == NIL); - fl->head = fl2->head; + if (n == new_size) + { + cell->next = NULL; + list->tail = cell; + list->length = new_size; + check_list_invariants(list); + return list; + } + n++; } - fl->tail = fl2->tail; + + /* keep the compiler quiet; never reached */ + Assert(false); + return list; } /* - * nth - * - * Get the n'th element of the list. First element is 0th. + * Locate the n'th cell (counting from 0) of the list. It is an assertion + * error if there isn't one. + */ +static ListCell * +list_nth_cell(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 * -nth(int n, List *l) +list_nth(List *list, int n) { - /* XXX assume list is long enough */ - while (n-- > 0) - l = lnext(l); - return lfirst(l); + Assert(IsPointerList(list)); + return lfirst(list_nth_cell(list, n)); } /* - * length - * - * Get the length of l + * Return the integer value contained in the n'th element of the + * specified list. */ int -length(List *l) +list_nth_int(List *list, int n) { - int i = 0; - - while (l != NIL) - { - l = lnext(l); - i++; - } - return i; + Assert(IsIntegerList(list)); + return lfirst_int(list_nth_cell(list, n)); } /* - * llast - * - * Get the last element of l ... error if empty list + * Return the OID value contained in the n'th element of the specified + * list. */ -void * -llast(List *l) +Oid +list_nth_oid(List *list, int n) { - if (l == NIL) - elog(ERROR, "empty list does not have a last item"); - while (lnext(l) != NIL) - l = lnext(l); - return lfirst(l); + Assert(IsOidList(list)); + return lfirst_oid(list_nth_cell(list, n)); } /* - * llastnode - * - * Get the last node of l ... NIL if empty list + * 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'. */ -List * -llastnode(List *l) +bool +list_member(List *list, void *datum) { - if (l == NIL) - return NIL; - while (lnext(l) != NIL) - l = lnext(l); - return l; + ListCell *cell; + + Assert(IsPointerList(list)); + check_list_invariants(list); + + foreach (cell, list) + { + if (equal(lfirst(cell), datum)) + return true; + } + + return false; } /* - * freeList - * - * Free the List nodes of a list - * The pointed-to nodes, if any, are NOT freed. - * This works for integer and Oid lists too. + * Return true iff 'datum' is a member of the list. Equality is + * determined by using simple pointer comparison. */ -void -freeList(List *list) +bool +list_member_ptr(List *list, void *datum) { - while (list != NIL) - { - List *l = list; + ListCell *cell; - list = lnext(list); - pfree(l); + Assert(IsPointerList(list)); + check_list_invariants(list); + + foreach (cell, list) + { + if (lfirst(cell) == datum) + return true; } + + return false; } /* - * equali - * compares two lists of integers + * Return true iff the integer 'datum' is a member of the list. */ bool -equali(List *list1, List *list2) +list_member_int(List *list, int datum) { - List *l; + ListCell *cell; + + Assert(IsIntegerList(list)); + check_list_invariants(list); - foreach(l, list1) + foreach (cell, list) { - if (list2 == NIL) - return false; - if (lfirsti(l) != lfirsti(list2)) - return false; - list2 = lnext(list2); + if (lfirst_int(cell) == datum) + return true; } - if (list2 != NIL) - return false; - return true; + + return false; } /* - * equalo - * compares two lists of Oids + * Return true iff the OID 'datum' is a member of the list. */ bool -equalo(List *list1, List *list2) +list_member_oid(List *list, Oid datum) { - List *l; + ListCell *cell; + + Assert(IsOidList(list)); + check_list_invariants(list); - foreach(l, list1) + foreach (cell, list) { - if (list2 == NIL) - return false; - if (lfirsto(l) != lfirsto(list2)) - return false; - list2 = lnext(list2); + if (lfirst_oid(cell) == datum) + return true; } - if (list2 != NIL) - return false; - return true; + + return false; } /* - * Generate the union of two lists, - * ie, l1 plus all members of l2 that are not already in l1. - * - * NOTE: if there are duplicates in l1 they will still be duplicate in the - * result; but duplicates in l2 are discarded. + * Delete 'cell' from 'list'; 'prev' is the previous element to 'cell' + * in 'list', if any (i.e. prev == NULL iff list->head == cell) * - * The result is a fresh List, but it points to the same member nodes - * as were in the inputs. + * The cell is pfree'd, as is the List header if this was the last member. */ List * -set_union(List *l1, List *l2) +list_delete_cell(List *list, ListCell *cell, ListCell *prev) { - List *retval = listCopy(l1); - List *i; + check_list_invariants(list); + Assert(prev != NULL ? lnext(prev) == cell : list_head(list) == cell); + + /* + * If we're about to delete the last node from the list, free the + * whole list instead and return NIL, which is the only valid + * representation of a zero-length list. + */ + if (list->length == 1) + { + list_free(list); + return NIL; + } - foreach(i, l2) + /* + * Otherwise, adjust the necessary list links, deallocate the + * particular node we have just removed, and return the list we + * were given. + */ + list->length--; + + if (prev) + prev->next = cell->next; + else + list->head = cell->next; + + if (list->tail == cell) + list->tail = prev; + + pfree(cell); + return list; +} + +/* + * Delete the first cell in list that matches datum, if any. + * Equality is determined via equal(). + */ +List * +list_delete(List *list, void *datum) +{ + ListCell *cell; + ListCell *prev; + + Assert(IsPointerList(list)); + check_list_invariants(list); + + prev = NULL; + foreach (cell, list) { - if (!member(lfirst(i), retval)) - retval = lappend(retval, lfirst(i)); + if (equal(lfirst(cell), datum)) + return list_delete_cell(list, cell, prev); + + prev = cell; } - return retval; + + /* Didn't find a match: return the list unmodified */ + return list; } -/* set_union for Oid lists */ +/* As above, but use simple pointer equality */ List * -set_uniono(List *l1, List *l2) +list_delete_ptr(List *list, void *datum) { - List *retval = listCopy(l1); - List *i; + ListCell *cell; + ListCell *prev; - foreach(i, l2) + Assert(IsPointerList(list)); + check_list_invariants(list); + + prev = NULL; + foreach (cell, list) { - if (!oidMember(lfirsto(i), retval)) - retval = lappendo(retval, lfirsto(i)); + if (lfirst(cell) == datum) + return list_delete_cell(list, cell, prev); + + prev = cell; } - return retval; + + /* Didn't find a match: return the list unmodified */ + return list; } -/* set_union when pointer-equality comparison is sufficient */ +/* As above, but for integers */ List * -set_ptrUnion(List *l1, List *l2) +list_delete_int(List *list, int datum) { - List *retval = listCopy(l1); - List *i; + ListCell *cell; + ListCell *prev; + + Assert(IsIntegerList(list)); + check_list_invariants(list); - foreach(i, l2) + prev = NULL; + foreach (cell, list) { - if (!ptrMember(lfirst(i), retval)) - retval = lappend(retval, lfirst(i)); + if (lfirst_int(cell) == datum) + return list_delete_cell(list, cell, prev); + + prev = cell; } - return retval; + + /* Didn't find a match: return the list unmodified */ + return list; +} + +/* As above, but for OIDs */ +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; + } + + /* Didn't find a match: return the list unmodified */ + return list; } /* - * Generate the intersection of two lists, - * ie, all members of both l1 and l2. - * - * NOTE: if there are duplicates in l1 they will still be duplicate in the - * result; but duplicates in l2 are discarded. + * Delete the first element of the list. * - * The result is a fresh List, but it points to the same member nodes - * as were in the inputs. + * 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. */ -#ifdef NOT_USED List * -set_intersect(List *l1, List *l2) +list_delete_first(List *list) { - List *retval = NIL; - List *i; + check_list_invariants(list); - foreach(i, l1) - { - if (member(lfirst(i), l2)) - retval = lappend(retval, lfirst(i)); - } - return retval; + if (list == NIL) + return NIL; /* would an error be better? */ + + return list_delete_cell(list, list_head(list), NULL); } -#endif /* - * member() - * nondestructive, returns t iff l1 is a member of the list l2 + * Generate the union of two lists. This is calculated by copying + * list1 via list_copy(), then adding to it all the members of list2 + * that aren't already in list1. + * + * Whether an element is already a member of the list is determined + * via equal(). + * + * The returned list is newly-allocated, although the content of the + * cells is the same (i.e. any pointed-to objects are not copied). + * + * NB: Bizarrely, this function will NOT remove any duplicates that + * are present in list1 (so it is not really a union at all!). Also, + * this function could probably be implemented a lot faster if it is a + * performance bottleneck. */ -bool -member(void *l1, List *l2) +List * +list_union(List *list1, List *list2) { - List *i; + List *result; + ListCell *cell; + + Assert(IsPointerList(list1)); + Assert(IsPointerList(list2)); - foreach(i, l2) + result = list_copy(list1); + foreach(cell, list2) { - if (equal((Node *) l1, (Node *) lfirst(i))) - return true; + if (!list_member(result, lfirst(cell))) + result = lappend(result, lfirst(cell)); } - return false; + + check_list_invariants(result); + return result; } /* - * like member(), but use when pointer-equality comparison is sufficient + * This variant of list_union() determines duplicates via simple + * pointer comparison. */ -bool -ptrMember(void *l1, List *l2) +List * +list_union_ptr(List *list1, List *list2) { - List *i; + List *result; + ListCell *cell; - foreach(i, l2) + Assert(IsPointerList(list1)); + Assert(IsPointerList(list2)); + + result = list_copy(list1); + foreach(cell, list2) { - if (l1 == lfirst(i)) - return true; + if (!list_member_ptr(result, lfirst(cell))) + result = lappend(result, lfirst(cell)); } - return false; + + check_list_invariants(result); + return result; } /* - * membership test for integer lists + * This variant of list_union() operates upon lists of integers. */ -bool -intMember(int l1, List *l2) +List * +list_union_int(List *list1, List *list2) { - List *i; + List *result; + ListCell *cell; + + Assert(IsIntegerList(list1)); + Assert(IsIntegerList(list2)); - foreach(i, l2) + result = list_copy(list1); + foreach(cell, list2) { - if (l1 == lfirsti(i)) - return true; + if (!list_member_int(result, lfirst_int(cell))) + result = lappend_int(result, lfirst_int(cell)); } - return false; + + check_list_invariants(result); + return result; } /* - * membership test for Oid lists + * This variant of list_union() operates upon lists of OIDs. */ -bool -oidMember(Oid l1, List *l2) +List * +list_union_oid(List *list1, List *list2) { - List *i; + List *result; + ListCell *cell; + + Assert(IsOidList(list1)); + Assert(IsOidList(list2)); - foreach(i, l2) + result = list_copy(list1); + foreach(cell, list2) { - if (l1 == lfirsto(i)) - return true; + if (!list_member_oid(result, lfirst_oid(cell))) + result = lappend_oid(result, lfirst_oid(cell)); } - return false; + + check_list_invariants(result); + return result; } /* - * lremove - * Removes 'elem' from the linked list (destructively changing the list!). - * (If there is more than one equal list member, the first is removed.) + * Return a list that contains all the cells in list1 that are not in + * list2. The returned list is freshly allocated via palloc(), but the + * cells themselves point to the same objects as the cells of the + * input lists. * - * This version matches 'elem' using simple pointer comparison. - * See also LispRemove. + * This variant works on lists of pointers, and determines list + * membership via equal() */ List * -lremove(void *elem, List *list) +list_difference(List *list1, List *list2) { - List *l; - List *prev = NIL; - List *result = list; + ListCell *cell; + List *result = NIL; - foreach(l, list) - { - if (elem == lfirst(l)) - break; - prev = l; - } - if (l != NIL) + Assert(IsPointerList(list1)); + Assert(IsPointerList(list2)); + + if (list2 == NIL) + return list_copy(list1); + + foreach (cell, list1) { - if (prev == NIL) - result = lnext(l); - else - lnext(prev) = lnext(l); - pfree(l); + if (!list_member(list2, lfirst(cell))) + result = lappend(result, lfirst(cell)); } + + check_list_invariants(result); return result; } /* - * LispRemove - * Removes 'elem' from the linked list (destructively changing the list!). - * (If there is more than one equal list member, the first is removed.) - * - * This version matches 'elem' using equal(). - * See also lremove. + * This variant of list_difference() determines list membership via + * simple pointer equality. */ List * -LispRemove(void *elem, List *list) +list_difference_ptr(List *list1, List *list2) { - List *l; - List *prev = NIL; - List *result = list; + ListCell *cell; + List *result = NIL; - foreach(l, list) - { - if (equal(elem, lfirst(l))) - break; - prev = l; - } - if (l != NIL) + Assert(IsPointerList(list1)); + Assert(IsPointerList(list2)); + + if (list2 == NIL) + return list_copy(list1); + + foreach (cell, list1) { - if (prev == NIL) - result = lnext(l); - else - lnext(prev) = lnext(l); - pfree(l); + if (!list_member_ptr(list2, lfirst(cell))) + result = lappend(result, lfirst(cell)); } + + check_list_invariants(result); return result; } /* - * lremovei - * lremove() for integer lists. + * This variant of list_difference() operates upon lists of integers. */ List * -lremovei(int elem, List *list) +list_difference_int(List *list1, List *list2) { - List *l; - List *prev = NIL; - List *result = list; + ListCell *cell; + List *result = NIL; - foreach(l, list) - { - if (elem == lfirsti(l)) - break; - prev = l; - } - if (l != NIL) + Assert(IsIntegerList(list1)); + Assert(IsIntegerList(list2)); + + if (list2 == NIL) + return list_copy(list1); + + foreach (cell, list1) { - if (prev == NIL) - result = lnext(l); - else - lnext(prev) = lnext(l); - pfree(l); + if (!list_member_int(list2, lfirst_int(cell))) + result = lappend_int(result, lfirst_int(cell)); } + + check_list_invariants(result); return result; } /* - * ltruncate - * Truncate a list to n elements. - * Does nothing if n >= length(list). - * NB: the list is modified in-place! + * This variant of list_difference() operates upon lists of OIDs. */ List * -ltruncate(int n, List *list) +list_difference_oid(List *list1, List *list2) { - List *ptr; + ListCell *cell; + List *result = NIL; - if (n <= 0) - return NIL; /* truncate to zero length */ + Assert(IsOidList(list1)); + Assert(IsOidList(list2)); - foreach(ptr, list) + if (list2 == NIL) + return list_copy(list1); + + foreach (cell, list1) { - if (--n == 0) - { - lnext(ptr) = NIL; - break; - } + if (!list_member_oid(list2, lfirst_oid(cell))) + result = lappend_oid(result, lfirst_oid(cell)); } - return list; + + check_list_invariants(result); + return result; +} + +/* Free all storage in a list, and optionally the pointed-to elements */ +static void +list_free_private(List *list, bool deep) +{ + ListCell *cell; + + check_list_invariants(list); + + cell = list_head(list); + while (cell != NULL) + { + ListCell *tmp = cell; + + cell = lnext(cell); + if (deep) + pfree(lfirst(tmp)); + pfree(tmp); + } + + if (list) + pfree(list); } /* - * set_difference + * Free all the cells of the list, as well as the list itself. Any + * objects that are pointed-to by the cells of the list are NOT + * free'd. * - * Return l1 without the elements in l2. + * On return, the argument to this function has been freed, so the + * caller would be wise to set it to NIL for safety's sake. + */ +void +list_free(List *list) +{ + list_free_private(list, false); +} + +/* + * Free all the cells of the list, the list itself, and all the + * objects pointed-to by the cells of the list (each element in the + * list must contain a pointer to a palloc()'d region of memory!) * - * The result is a fresh List, but it points to the same member nodes - * as were in l1. + * On return, the argument to this function has been freed, so the + * caller would be wise to set it to NIL for safety's sake. + */ +void +list_free_deep(List *list) +{ + /* + * A "deep" free operation only makes sense on a list of pointers. + */ + Assert(IsPointerList(list)); + list_free_private(list, true); +} + +/* + * Return a shallow copy of the specified list. */ List * -set_difference(List *l1, List *l2) +list_copy(List *oldlist) { - List *result = NIL; - List *i; + List *newlist; + ListCell *newlist_prev; + ListCell *oldlist_cur; + + if (oldlist == NIL) + return NIL; - if (l2 == NIL) - return listCopy(l1); /* slightly faster path for empty l2 */ + newlist = new_list(oldlist->type); + newlist->length = oldlist->length; - foreach(i, l1) + /* + * 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) { - if (!member(lfirst(i), l2)) - result = lappend(result, lfirst(i)); + 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; } - return result; + + newlist_prev->next = NULL; + newlist->tail = newlist_prev; + + check_list_invariants(newlist); + return newlist; } /* - * set_differenceo - * - * Same as set_difference, but for Oid lists + * Return a shallow copy of the specified list, without the first N elements. */ List * -set_differenceo(List *l1, List *l2) +list_copy_tail(List *oldlist, int nskip) { - List *result = NIL; - List *i; + List *newlist; + ListCell *newlist_prev; + ListCell *oldlist_cur; + + if (nskip < 0) + nskip = 0; /* would it be better to elog? */ - if (l2 == NIL) - return listCopy(l1); /* slightly faster path for empty l2 */ + if (oldlist == NIL || nskip >= oldlist->length) + return NIL; - foreach(i, l1) + 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; + + /* + * Copy over the data in the first remaining cell; new_list() has already + * allocated the head cell itself + */ + newlist->head->data = oldlist_cur->data; + + newlist_prev = newlist->head; + oldlist_cur = oldlist_cur->next; + while (oldlist_cur) { - if (!oidMember(lfirsto(i), l2)) - result = lappendo(result, lfirsto(i)); + 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; } - return result; + + newlist_prev->next = NULL; + newlist->tail = newlist_prev; + + check_list_invariants(newlist); + return newlist; } /* - * set_ptrDifference + * When using non-GCC compilers, we can't define these as inline + * functions in pg_list.h, so they are defined here. * - * Same as set_difference, when pointer-equality comparison is sufficient + * TODO: investigate supporting inlining for some non-GCC compilers. */ -List * -set_ptrDifference(List *l1, List *l2) +#ifndef __GNUC__ + +ListCell * +list_head(List *l) { - List *result = NIL; - List *i; + return l ? l->head : NULL; +} - if (l2 == NIL) - return listCopy(l1); /* slightly faster path for empty l2 */ +ListCell * +list_tail(List *l) +{ + return l ? l->tail : NULL; +} - foreach(i, l1) - { - if (!ptrMember(lfirst(i), l2)) - result = lappend(result, lfirst(i)); - } - return result; +int +list_length(List *l) +{ + return l ? l->length : 0; } +#endif /* ! __GNUC__ */ + /* - * Reverse a list, non-destructively + * 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 explicitly disable list API compatibility in list.c, so we + * don't see the prototypes for these functions. */ -#ifdef NOT_USED + +/* + * 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(List *list); + +int +length(List *list) +{ + return list_length(list); +} + +/* + * This code implements the old "Fast List" API, making use of the new + * List code to do so. There's no need for FastList anymore, so this + * code is a bit sloppy -- it will be removed soon. + */ +void FastListInit(FastList *fl); + +void +FastListInit(FastList *fl) +{ + fl->list = NIL; +} + +void FastListFromList(FastList *fl, List *l); + +void +FastListFromList(FastList *fl, List *list) +{ + fl->list = list; +} + +List *FastListValue(FastList *fl); + List * -lreverse(List *l) +FastListValue(FastList *fl) +{ + return fl->list; +} + +void makeFastList1(FastList *fl, void *elem); + +void +makeFastList1(FastList *fl, void *elem) { - List *result = NIL; - List *i; + fl->list = list_make1(elem); +} - foreach(i, l) - result = lcons(lfirst(i), result); - return result; +void FastAppend(FastList *fl, void *datum); + +void +FastAppend(FastList *fl, void *datum) +{ + fl->list = lappend(fl->list, datum); } -#endif +void FastAppendi(FastList *fl, int datum); + +void +FastAppendi(FastList *fl, int datum) +{ + fl->list = lappend_int(fl->list, datum); +} + +void FastAppendo(FastList *fl, Oid datum); + +void +FastAppendo(FastList *fl, Oid datum) +{ + fl->list = lappend_oid(fl->list, datum); +} + +void FastConc(FastList *fl, List *cells); + +void +FastConc(FastList *fl, List *cells) +{ + fl->list = list_concat(fl->list, cells); +} + +void FastConcFast(FastList *fl1, FastList *fl2); + +void +FastConcFast(FastList *fl1, FastList *fl2) +{ + fl1->list = list_concat(fl1->list, fl2->list); +} -- cgit v1.2.3