I've attached the latest header and implementation files (pg_list.h
and list.c, respectively) for the new linked list implementation. I'm
pretty satisfied with the new API: now would be the ideal time to
suggest any changes you think I should make to it. I decided to use a
new naming convention: all public functions and macros are prefixed
with list_ or cell_, as appropriate, and type-specific functions are
suffixed with _int or _oid, as appropriate.
ISTM that the "allocate the list itself and the head node in one
palloc()" idea that Tom suggested actually won't work: since the head
node can change over the life of the list, we need to be able to
deallocate a list cell via pfree() -- which would not be the case if a
particular node was allocated via the same palloc() as the list
itself.
BTW, one nice thing about the new List API is that it lets us get rid
of the WRITE_INTLIST_FIELD() and related cruft in nodes/, because each
type of list (T_List, T_IntList, or T_OidList) is now a legitimate
Node in its own right. So we can now use WRITE_NODE_FIELD() to output
a list of integers, for example.
(The implementation is a little "off the cuff", and I haven't reviewed
it; also, since the tree is totally broken with this patch applied, I
haven't tested it either. That said, I'd appreciate anyone mentioning
any implementation bugs they might happen to spot.)
Incidentally, does anyone have any thoughts on the best way to commit
this? It requires changing pretty much _every single_ place in the
code that uses the List API. Although most of those modifications
should be trivial, it will still require touching a lot of
files. Should I just make the changes locally and commit them all in
one fell swoop? Create a private branch in CVS? Any other suggestions?
FWIW, I'm hoping to have this done (and committed to CVS HEAD) by the
end of next weekend.
-Neil
/*-------------------------------------------------------------------------
*
* list.c
* implementation for PostgreSQL generic linked list package
*
*
* Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
*
* IDENTIFICATION
* $PostgreSQL: pgsql-server/src/backend/nodes/list.c,v 1.55 2003/11/29 19:51:49 pgsql Exp $
*
*-------------------------------------------------------------------------
*/
#include "postgres.h"
#include "nodes/pg_list.h"
/*
* 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 = palloc(sizeof(*new_head));
new_head->next = NULL;
new_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;
}
/*
* Allocate a new cell and make it the head of the specified list. The
* data in the new head cell is undefined; the caller should be sure
* to fill it in
*/
static void
new_head_cell(List *list)
{
ListCell *new_head;
new_head = palloc(sizeof(*new_head));
new_head->next = list->head;
list->head = new_head;
list->length++;
}
/*
* Allocate a new cell and make it the tail of the specified list. The
* data in the new tail cell is undefined; the caller should be sure
* to fill it in
*/
static void
new_tail_cell(List *list)
{
ListCell *new_tail;
new_tail = palloc(sizeof(*new_tail));
new_tail->next = NULL;
list->tail->next = new_tail;
list->tail = new_tail;
list->length++;
}
/*
* 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 *
list_append(List *list, void *datum)
{
if (list == NIL)
list = new_list(T_List);
else
new_tail_cell(list);
cell_value(list_tail(list)) = datum;
return list;
}
/*
* Append an integer to the specified list. See list_append()
*/
List *
list_append_int(List *list, int datum)
{
if (list == NIL)
list = new_list(T_IntList);
else
new_tail_cell(list);
cell_value_int(list_tail(list)) = datum;
return list;
}
/*
* Append an OID to the specified list. See list_append()
*/
List *
list_append_oid(List *list, Oid datum)
{
if (list == NIL)
list = new_list(T_OidList);
else
new_tail_cell(list);
cell_value_oid(list_tail(list)) = datum;
return list;
}
/*
* Private convenience routine: allocate a new tail cell and place the
* data from the specified cell into it. The data is copied via a
* shallow copy, not a deep copy.
*/
static List *
list_append_auto(List *list, ListCell *cell)
{
/* XXX: broken if list == NIL */
switch (list->type)
{
case T_List:
return list_append(list, cell_value(cell));
case T_IntList:
return list_append_int(list, cell_value_int(cell));
case T_OidList:
return list_append_oid(list, cell_value_oid(cell));
default:
{
/* Keep the compiler quiet; never reached */
Assert(false);
return NIL;
}
}
}
/*
* Prepend 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 *
list_prepend(List *list, void *datum)
{
if (list == NIL)
list = new_list(T_List);
else
new_head_cell(list);
cell_value(list_head(list)) = datum;
return list;
}
/*
* Prepend an integer to the list. See list_prepend()
*/
List *
list_prepend_int(List *list, int datum)
{
if (list == NIL)
list = new_list(T_IntList);
else
new_head_cell(list);
cell_value_int(list_head(list)) = datum;
return list;
}
/*
* Prepend an OID to the list. See list_prepend()
*/
List *
list_prepend_oid(List *list, Oid datum)
{
if (list == NIL)
list = new_list(T_OidList);
else
new_head_cell(list);
cell_value_oid(list_head(list)) = datum;
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). So freeing list2 will also invalidate a
* portion of list1.
*/
List *
list_conc(List *list1, List *list2)
{
if (list1 == NIL)
return list2;
if (list2 == NIL)
return list1;
if (list1 == list2)
elog(ERROR, "cannot list_conc() a list to itself");
list1->length += list2->length;
list1->tail->next = list2->head;
list1->tail = list2->tail;
return list1;
}
void *
list_nth(List *list, int n)
{
ListCell *match;
Assert(list != NIL);
Assert(n >= 0);
Assert(n <= (list->length - 1));
Assert(list->type == T_List);
/* Does the caller actually mean to fetch the tail? */
if (n == list->length - 1)
return cell_value(list_tail(list));
for (match = list->head; n-- > 0; match = match->next)
;
return cell_value(match);
}
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)
return list;
n = 0;
foreach (cell, list)
{
n++;
if (n == new_size)
{
cell->next = NULL;
list->tail = cell;
list->length = new_size;
return list;
}
}
/* keep the compiler quiet; never reached */
Assert(false);
return list;
}
/*
* Return true iff 'datum' is a member of the list. Equality is
* determined by using equal(), so callers should ensure that they
* pass a Node as 'datum'
*/
bool
list_member(List *list, void *datum)
{
ListCell *cell;
foreach (cell, list)
{
if (equal(cell_value(cell), datum))
return true;
}
return false;
}
/*
* Return true iff 'datum' is a member of the list. Equality is
* determined by using simple pointer comparison.
*/
bool
list_member_simple(List *list, void *datum)
{
ListCell *cell;
Assert(list == NIL || IsA(list, List));
foreach (cell, list)
{
if (cell_value(cell) == datum)
return true;
}
return false;
}
/*
* Return true iff the integer 'datum' is a member of the list.
*/
bool
list_member_int(List *list, int datum)
{
ListCell *cell;
Assert(list == NIL || IsA(list, OidList));
foreach (cell, list)
{
if (cell_value_int(cell) == datum)
return true;
}
return false;
}
/*
* Return true iff the OID 'datum' is a member of the list.
*/
bool
list_member_oid(List *list, Oid datum)
{
ListCell *cell;
Assert(list == NIL || IsA(list, IntList));
foreach (cell, list)
{
if (cell_value_oid(cell) == datum)
return true;
}
return false;
}
/*
* Private convenience routine: return true iff 'cell' is a member of
* 'list', using the comparison rules specified by 'simple'.
*/
static bool
list_member_auto(List *list, ListCell *cell, bool simple)
{
/* A zero-cell list can't have any members */
if (list == NIL)
return false;
switch (list->type)
{
case T_List:
{
if (simple)
return list_member_simple(list, cell_value(cell));
else
return list_member(list, cell_value(cell));
}
case T_IntList:
return list_member_int(list, cell_value_int(cell));
case T_OidList:
return list_member_oid(list, cell_value_oid(cell));
default:
{
/* Keep the compiler quiet; never reached */
Assert(false);
return false;
}
}
}
/*
* Remove 'cell' from 'list'; 'prev' is the previous element to 'cell'
* in 'list', if any (i.e. prev == NULL iff list->head == cell)
*/
static List *
remove_list_cell(List *list, ListCell *cell, ListCell *prev)
{
list->length--;
/*
* If we just removed the last node from the last, free it and
* return 'NIL', which is the only valid representation of a
* zero-length list.
*/
if (list->length == 0)
{
list_free(list);
return NIL;
}
/*
* Otherwise, adjust the necessary list links, deallocate the
* particular node we've removed, and return the list we were
* given.
*/
if (prev)
prev->next = cell->next;
if (list->head == cell)
list->head = cell->next;
if (list->tail == cell)
list->tail = prev;
pfree(cell);
return list;
}
List *
list_remove(List *list, void *datum)
{
ListCell *cell;
ListCell *prev;
prev = NULL;
foreach (cell, list)
{
if (equal(cell_value(cell), datum))
return remove_list_cell(list, cell, prev);
prev = cell;
}
/* Didn't find a match: return the list unmodified */
return list;
}
List *
list_remove_simple(List *list, void *datum)
{
ListCell *cell;
ListCell *prev;
prev = NULL;
foreach (cell, list)
{
if (cell_value(cell) == datum)
return remove_list_cell(list, cell, prev);
prev = cell;
}
/* Didn't find a match: return the list unmodified */
return list;
}
List *
list_remove_int(List *list, int datum)
{
ListCell *cell;
ListCell *prev;
prev = NULL;
foreach (cell, list)
{
if (cell_value_int(cell) == datum)
return remove_list_cell(list, cell, prev);
prev = cell;
}
/* Didn't find a match: return the list unmodified */
return list;
}
List *
list_remove_oid(List *list, Oid datum)
{
ListCell *cell;
ListCell *prev;
prev = NULL;
foreach (cell, list)
{
if (cell_value_oid(cell) == datum)
return remove_list_cell(list, cell, prev);
prev = cell;
}
/* Didn't find a match: return the list unmodified */
return list;
}
/*
* Returns true iff c1 and c2 are equal ListCells, according to the
* rules specified by 'simple'
*/
#define CELL_NOT_EQUAL(c1, c2, simple) \
(simple) \
? (cell_value(c1) != cell_value(c2)) \
: (!equal(cell_value(c1), cell_value(c2)))
/*
* Returns true iff list1 is equal to list2. Lists are equal if they
* have the same length, the same type, and all their nodes are cell.
*
* If 'simple' is true, cell equality is determined by
* pointer-equality comparison. Otherwise, equal() is used.
*/
bool
list_equal_private(List *list1, List *list2, bool simple)
{
ListCell *c1;
ListCell *c2;
/*
* Return quickly for obviously nonequivalent lists
*/
if (list_length(list1) != list_length(list2))
return false;
if (list1->type != list2->type)
return false;
c1 = list_head(list1);
c2 = list_head(list2);
while (c1 != NULL || c2 != NULL)
{
if (CELL_NOT_EQUAL(c1, c2, simple))
return false;
c1 = cell_next(c1);
c2 = cell_next(c2);
}
/*
* The lists are the same length, so we can't run out of one
* before the other
*/
Assert(c1 == NULL && c2 == NULL);
return true;
}
/*
* 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.
*
* If 'simple' is true, duplicates are determined via simple pointer
* equality. Otherwise, duplicates are determined via equal().
*
* Returns a new List, whose cells are the same as the appropriate
* cells from list1 and list2 (i.e. the cells aren't copied)
*
* NB: Strangely, this function will NOT remove any duplicates that
* are present in list1. Also, this function could probably be
* implemented a lot faster if it were a performance bottleneck.
*/
List *
list_set_union_private(List *list1, List *list2, bool simple)
{
List *new_list;
ListCell *cell;
new_list = list_copy(list1);
foreach (cell, list2)
{
if (!list_member_auto(new_list, cell, simple))
list_append_auto(new_list, cell);
}
return new_list;
}
/*
* Return a freshly-allocated List that contains all the cells in
* list1 that are not in list2. The list is freshly allocated via
* palloc(), but the cells themselves point to the same objects as the
* nodes from the input lists.
*
* If 'simple' is true, we determine duplicates in list2 via simple
* pointer-equality comparisons. Otherwise, equal() is used.
*/
List *
list_set_difference_private(List *list1, List *list2, bool simple)
{
ListCell *cell;
List *new_list = NIL;
if (list2 == NIL)
return list_copy(list1);
foreach (cell, list1)
{
if (!list_member_auto(list2, cell, simple))
new_list = list_append_auto(new_list, cell);
}
return new_list;
}
/*
* 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 freed.
*/
void
list_free(List *list)
{
ListCell *cell;
cell = list_head(list);
while (cell != NULL)
{
ListCell *tmp = cell;
cell = cell_next(cell);
pfree(tmp);
}
if (list)
pfree(list);
}
/*
* Return a copy the specified list. If 'deep' is true, objects
* pointed-to by list cells are also copied via
* copyObject(). Otherwise, pointed-to objects are not copied. The
* storage for the new List is allocated via palloc().
*/
List *
list_copy_private(List *list, bool deep)
{
List *newlist;
ListCell *cell;
ListCell *prev;
if (list == NIL)
return NIL;
/*
* For lists of integers and OIDs, shallow copy and deep copy are
* equivalent, so force the former because copyObject() can't
* handle integers or Oids
*/
if (IsA(list, IntList) || IsA(list, OidList))
deep = false;
newlist = new_list(list->type);
newlist->length = list->length;
/*
* Copy the head cell: new_node() has already allocated it
*/
if (deep)
cell_value(list_head(newlist)) = copyObject(cell_value(list_head(list)));
else
newlist->head->data = list->head->data;
prev = list_head(newlist);
foreach (cell, list)
{
ListCell *newcell;
newcell = palloc(sizeof(*newcell));
if (deep)
cell_value(newcell) = copyObject(cell_value(cell));
else
newcell->data = cell->data;
prev->next = newcell;
prev = newcell;
}
prev->next = NULL;
newlist->tail = prev;
return newlist;
}
/*-------------------------------------------------------------------------
*
* pg_list.h
* interface for PostgreSQL generic linked list package
*
*
* Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
* $PostgreSQL: pgsql-server/src/include/nodes/pg_list.h,v 1.42 2003/11/29 22:41:06 pgsql Exp $
*
*-------------------------------------------------------------------------
*/
#ifndef PG_LIST_H
#define PG_LIST_H
#include "nodes/nodes.h"
/*----------------------
* List node
*
* We support three types of lists:
* lists of pointers (in practice always pointers to Nodes, but declare as
* "void *" to minimize casting annoyances)
* lists of integers
* lists of Oids
*
* (At this writing, ints and Oids are the same size, but they may not always
* be so; try to be careful to maintain the distinction.)
*
* Lists must be homogeneous.
*----------------------
*/
typedef struct ListCell
{
union
{
void *ptr_value;
int int_value;
Oid oid_value;
} data;
struct ListCell *next;
} ListCell;
typedef struct List
{
NodeTag type; /* T_List, T_IntList, or T_OidList */
int length;
ListCell *head;
ListCell *tail;
} List;
/*
* The *only* valid representation of an empty list is NIL; in other
* words, a non-NIL list is guaranteed to have length >= 1 and
* head/tail != NULL
*/
#define NIL ((List *) NULL)
#define list_length(l) ((l) ? (l)->length : 0)
#define list_head(l) ((l) ? (l)->head : NULL)
#define list_tail(l) ((l) ? (l)->tail : NULL)
#define cell_next(lc) ((lc)->next)
#define cell_value(lc) ((lc)->data.ptr_value)
#define cell_value_int(lc) ((lc)->data.int_value)
#define cell_value_oid(lc) ((lc)->data.oid_value)
/*
* foreach -
* a convenience macro which loops through the list
*/
#define foreach(lc, l) \
for ((lc) = list_head(l); (lc) != NULL; (lc) = cell_next(lc))
extern List *list_append(List *list, void *datum);
extern List *list_append_int(List *list, int datum);
extern List *list_append_oid(List *list, Oid datum);
extern List *list_prepend(List *list, void *datum);
extern List *list_prepend_int(List *list, int datum);
extern List *list_prepend_oid(List *list, Oid datum);
extern List *list_conc(List *list1, List *list2);
extern void *list_nth(List *list, int n);
extern List *list_truncate(List *list, int new_size);
extern bool list_member(List *list, void *datum);
extern bool list_member_simple(List *list, void *datum);
extern bool list_member_int(List *list, int datum);
extern bool list_member_oid(List *list, Oid datum);
extern List *list_remove(List *list, void *datum);
extern List *list_remove_simple(List *list, void *datum);
extern List *list_remove_int(List *list, int datum);
extern List *list_remove_oid(List *list, Oid datum);
#define list_equal(l1, l2) \
list_equal_private(l1, l2, false)
#define list_equal_simple(l1, l2) \
list_equal_private(l1, l2, true)
#define list_set_union(l1, l2) \
list_set_union_private(l1, l2, false)
#define list_set_union_simple(l1, l2) \
list_set_union_private(l1, l2, true)
#define list_set_difference(l1, l2) \
list_set_difference_private(l1, l2, false)
#define list_set_difference_simple(l1, l2) \
list_set_difference_private(l1, l2, true)
#define list_copy(list) \
list_copy_private(list, false)
#define list_deep_copy(list) \
list_copy_private(list, true)
extern void list_free(List *list);
/*
* Private API functions; callers should not invoke these
* directly. Rather, one of the convenience macros above should be
* used.
*/
extern bool list_equal_private(List *list1, List *list2,
bool simple);
extern List *list_set_union_private(List *list1, List *list2,
bool simple);
extern List *list_set_difference_private(List *list1, List *list2,
bool simple);
extern List *list_copy_private(List *list, bool shallow);
#endif /* PG_LIST_H */
---------------------------(end of broadcast)---------------------------
TIP 2: you can get off all lists at once with the unregister command
(send "unregister YourEmailAddressHere" to [EMAIL PROTECTED])
