Ok, I've attached new versions of list.c and pg_list.h -- this is just a
*rough sketch* of the new List code -- it definitely won't compile, the
intent is just to concretely specify the new List design. Also, I've
only updated the important list functions: I stopped at nth().
(I've attached the whole files, rather than diffs, because I thought
that would be easier to read...)
Any comments would be welcome -- I'm sure I've mucked a few things up.
Also, since it doesn't compile and I haven't done any testing, there are
probably some thinkos & typos in the code.
On Tue, 2003-11-04 at 11:40, Tom Lane wrote:
> Hmm ... taking that one step further, you could probably avoid the need
> for two palloc's in the first lcons/lappend if the List header were
> combined with the first ListCell. This would make for some grottiness
> in ldelete when removing the first list entry, but that's probably
> a good tradeoff.
I haven't implemented this (yet), or the aset.c changes you suggested.
-Neil
/*-------------------------------------------------------------------------
*
* pg_list.h
* POSTGRES generic list package
*
*
* Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
* $Id: pg_list.h,v 1.41 2003/08/22 20:34:33 tgl Exp $
*
*-------------------------------------------------------------------------
*/
#ifndef PG_LIST_H
#define PG_LIST_H
#include "nodes/nodes.h"
/* ----------------------------------------------------------------
* node definitions
* ----------------------------------------------------------------
*/
/*----------------------
* Value node
*
* The same Value struct is used for five node types: T_Integer,
* T_Float, T_String, T_BitString, T_Null.
*
* Integral values are actually represented by a machine integer,
* but both floats and strings are represented as strings.
* Using T_Float as the node type simply indicates that
* the contents of the string look like a valid numeric literal.
*
* (Before Postgres 7.0, we used a double to represent T_Float,
* but that creates loss-of-precision problems when the value is
* ultimately destined to be converted to NUMERIC. Since Value nodes
* are only used in the parsing process, not for runtime data, it's
* better to use the more general representation.)
*
* Note that an integer-looking string will get lexed as T_Float if
* the value is too large to fit in a 'long'.
*
* Nulls, of course, don't need the value part at all.
*----------------------
*/
typedef struct Value
{
NodeTag type; /* tag appropriately (eg. T_String) */
union ValUnion
{
long ival; /* machine integer */
char *str; /* string */
} val;
} Value;
#define intVal(v) (((Value *)(v))->val.ival)
#define floatVal(v) atof(((Value *)(v))->val.str)
#define strVal(v) (((Value *)(v))->val.str)
typedef struct ListCell
{
union
{
void *ptr_value;
int int_value;
Oid oid_value;
} elem;
struct ListCell *next;
} ListCell;
typedef struct List
{
NodeTag type;
ListCell *head;
ListCell *tail;
int length;
} List;
#define NIL ((List *) NULL)
/* ----------------
* accessor macros
*
* The general naming convention is that the base name xyz() is for the
* pointer version, xyzi() is for integers, xyzo() is for Oids. We don't
* bother with multiple names if the same routine can handle all cases.
* ----------------
*/
#define length(l) ((l)->length)
#define value(cell) ((cell)->elem.ptr_value)
#define ivalue(cell) ((cell)->elem.int_value)
#define ovalue(cell) ((cell)->elem.oid_value)
#define lfirst(l) value((l)->head)
#define lfirsti(l) ivalue((l)->head)
#define lfirsto(l) ovalue((l)->head)
#define llast(l) value((l)->tail)
#define lsecond(l) value((l)->head->next)
#define lthird(l) value((l)->head->next->next)
#define lfourth(l) value((l)->head->next->next->next)
/*
* foreach -
* a convenience macro which loops through the list
*/
#define foreach(_cell_,_list_) \
for (_cell_ = (_list_)->head; _elt_->next != NULL; _elt_ = _elt->next)
/*
* Convenience macros for building fixed-length lists
*/
#define makeList1(x1) lcons(x1, NIL)
#define makeList2(x1,x2) lcons(x1, makeList1(x2))
#define makeList3(x1,x2,x3) lcons(x1, makeList2(x2,x3))
#define makeList4(x1,x2,x3,x4) lcons(x1, makeList3(x2,x3,x4))
#define makeListi1(x1) lconsi(x1, NIL)
#define makeListi2(x1,x2) lconsi(x1, makeListi1(x2))
#define makeListo1(x1) lconso(x1, NIL)
#define makeListo2(x1,x2) lconso(x1, makeListo1(x2))
/*
* function prototypes in nodes/list.c
*/
extern Value *makeInteger(long i);
extern Value *makeFloat(char *numericStr);
extern Value *makeString(char *str);
extern Value *makeBitString(char *str);
extern List *lcons(void *datum, List *list);
extern List *lconsi(int datum, List *list);
extern List *lconso(Oid datum, List *list);
extern List *lappend(List *list, void *datum);
extern List *lappendi(List *list, int datum);
extern List *lappendo(List *list, Oid datum);
extern List *nconc(List *list1, List *list2);
extern void *nth(int n, List *l);
extern bool member(void *datum, List *list);
extern bool ptrMember(void *datum, List *list);
extern bool intMember(int datum, List *list);
extern bool oidMember(Oid datum, List *list);
extern List *lremove(void *elem, List *list);
extern List *LispRemove(void *elem, List *list);
extern List *lremovei(int elem, List *list);
extern List *ltruncate(int n, List *list);
extern List *set_union(List *list1, List *list2);
extern List *set_uniono(List *list1, List *list2);
extern List *set_ptrUnion(List *list1, List *list2);
extern List *set_difference(List *list1, List *list2);
extern List *set_differenceo(List *list1, List *list2);
extern List *set_ptrDifference(List *list1, List *list2);
extern bool equali(List *list1, List *list2);
extern bool equalo(List *list1, List *list2);
extern void freeList(List *list);
/* in copyfuncs.c */
extern List *listCopy(List *list);
#endif /* PG_LIST_H */
/*-------------------------------------------------------------------------
*
* list.c
* POSTGRES generic list package
*
*
* Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
*
* IDENTIFICATION
* $Header: /var/lib/cvs/pgsql-server/src/backend/nodes/list.c,v 1.54 2003/08/08 21:41:44 momjian Exp $
*
* NOTES
* XXX a few of the following functions are duplicated to handle
* List of pointers and List of integers separately. Some day,
* someone should unify them. - ay 11/2/94
* This file needs cleanup.
*
* HISTORY
* AUTHOR DATE MAJOR EVENT
* Andrew Yu Oct, 1994 file creation
*
*-------------------------------------------------------------------------
*/
#include "postgres.h"
#include "nodes/parsenodes.h"
/*
* makeInteger
*/
Value *
makeInteger(long i)
{
Value *v = makeNode(Value);
v->type = T_Integer;
v->val.ival = i;
return v;
}
/*
* makeFloat
*
* Caller is responsible for passing a palloc'd string.
*/
Value *
makeFloat(char *numericStr)
{
Value *v = makeNode(Value);
v->type = T_Float;
v->val.str = numericStr;
return v;
}
/*
* makeString
*
* Caller is responsible for passing a palloc'd string.
*/
Value *
makeString(char *str)
{
Value *v = makeNode(Value);
v->type = T_String;
v->val.str = str;
return v;
}
/*
* makeBitString
*
* Caller is responsible for passing a palloc'd string.
*/
Value *
makeBitString(char *str)
{
Value *v = makeNode(Value);
v->type = T_BitString;
v->val.str = str;
return v;
}
static List *
new_list(NodeTag type)
{
List *retval;
retval = palloc(sizeof(*retval));
retval->type = type;
retval->head = NULL;
retval->tail = NULL;
retval->length = 0;
return retval;
}
/*
* Add a new, and as yet undefined, head element to the list, which
* must be non-NIL. The list is mutated in place. The caller should
* fill in the value of the new head element.
*/
static List *
new_head_elem(List *list)
{
ListCell *new_head;
new_head = palloc(sizeof(*new_head));
new_head->next = list->head;
list->head = new_head;
/*
* If this is the only element in the list, it is both the head
* and the tail, so we need to update the tail pointer as well
*/
if (list->tail == NULL)
list->tail = list->head;
list->length++;
}
/*
* Add a new, and as yet undefined, tail element to the list, which
* must be non-NIL. The list is mutated in place. The caller should
* fill in the value of the new tail element.
*/
static List *
new_tail_elem(List *list)
{
ListCell *new_tail;
new_tail = palloc(sizeof(*new_tail));
new_tail->next = NULL;
list->tail->next = new_tail;
list->tail = new_tail;
/*
* If this is the only element in the list, it is both the tail
* and the head, so we need to update the head pointer as well
*/
if (list->head == NULL)
list->head = list->tail;
list->length++;
}
#ifdef USE_ASSERT_CHECKING
/*
* This should probably be made into a macro...
*/
static void
check_invariant(List *list)
{
if (list == NIL)
return;
/*
* An empty list MUST be represented as NIL
*/
Assert(list->length > 0);
/*
* Since the list is non-empty, its head and tail must be defined
*/
Assert(list->head != NULL);
Assert(list->tail != NULL);
if (list->length == 1)
Assert(list->tail == list->head);
/*
* The list must have a valid tag
*/
Assert(list->type == T_List ||
list->type == T_IntList ||
list->type == T_OidList);
/*
* XXX: We could iterate through the list here and check if the
* list's length field is actually correct
*/
}
#else
#define check_invariant(l)
#endif /* USE_ASSERT_CHECKING */
List *
lcons(void *datum, List *list)
{
check_invariant(list);
if (list == NIL)
list = new_list(T_List);
new_head_elem(list);
value(list->head) = datum;
return list;
}
List *
lconsi(int datum, List *list)
{
check_invariant(list);
if (list == NIL)
list = new_list(T_IntList);
new_head_elem(list);
ivalue(list->head) = datum;
return list;
}
List *
lconso(Oid datum, List *list)
{
check_invariant(list);
if (list == NIL)
list = new_list(T_OidList);
new_head_elem(list);
ovalue(list->head) = datum;
return list;
}
List *
lappend(List *list, void *datum)
{
check_invariant(list);
if (list == NIL)
list = new_list(T_List);
new_tail_elem(list);
value(list->tail) = datum;
return list;
}
List *
lappendi(List *list, int datum)
{
check_invariant(list);
if (list == NIL)
list = new_list(T_IntList);
new_tail_elem(list);
ivalue(list->tail) = datum;
return list;
}
List *
lappendo(List *list, Oid datum)
{
check_invariant(list);
if (list == NIL)
list = new_list(T_OidList);
new_tail_elem(list);
ovalue(list->tail) = datum;
return list;
}
List *
nconc(List *l1, List *l2)
{
check_invariant(l1);
check_invariant(l2);
/*
* XXX: memory allocation is ambiguous here: does the caller free
* the memory for l1 or l2?
*/
if (l1 == NIL)
return l2;
if (l2 == NIL)
return l1;
if (l1 == l2)
elog(ERROR, "cannot nconc a list to itself");
l1->tail->next = l2->head;
l1->tail = l2->tail;
l1->length += l2->length;
return l1;
}
void *
nth(int n, List *list)
{
ListCell *match;
check_invariant(list);
Assert(n >= 0);
Assert(n < list->length);
/*
* Does the caller actually mean to fetch the tail?
*/
if (n == list->length - 1)
return value(list->tail);
for (match = list->head; n-- > 0; match = match->next)
;
return value(match);
}
/*
* 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.
*/
void
freeList(List *list)
{
while (list != NIL)
{
List *l = list;
list = lnext(list);
pfree(l);
}
}
/*
* equali
* compares two lists of integers
*/
bool
equali(List *list1, List *list2)
{
List *l;
foreach(l, list1)
{
if (list2 == NIL)
return false;
if (lfirsti(l) != lfirsti(list2))
return false;
list2 = lnext(list2);
}
if (list2 != NIL)
return false;
return true;
}
/*
* equalo
* compares two lists of Oids
*/
bool
equalo(List *list1, List *list2)
{
List *l;
foreach(l, list1)
{
if (list2 == NIL)
return false;
if (lfirsto(l) != lfirsto(list2))
return false;
list2 = lnext(list2);
}
if (list2 != NIL)
return false;
return true;
}
/*
* 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.
*
* The result is a fresh List, but it points to the same member nodes
* as were in the inputs.
*/
List *
set_union(List *l1, List *l2)
{
List *retval = listCopy(l1);
List *i;
foreach(i, l2)
{
if (!member(lfirst(i), retval))
retval = lappend(retval, lfirst(i));
}
return retval;
}
/* set_union for Oid lists */
List *
set_uniono(List *l1, List *l2)
{
List *retval = listCopy(l1);
List *i;
foreach(i, l2)
{
if (!oidMember(lfirsto(i), retval))
retval = lappendo(retval, lfirsto(i));
}
return retval;
}
/* set_union when pointer-equality comparison is sufficient */
List *
set_ptrUnion(List *l1, List *l2)
{
List *retval = listCopy(l1);
List *i;
foreach(i, l2)
{
if (!ptrMember(lfirst(i), retval))
retval = lappend(retval, lfirst(i));
}
return retval;
}
/*
* 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.
*
* The result is a fresh List, but it points to the same member nodes
* as were in the inputs.
*/
#ifdef NOT_USED
List *
set_intersect(List *l1, List *l2)
{
List *retval = NIL;
List *i;
foreach(i, l1)
{
if (member(lfirst(i), l2))
retval = lappend(retval, lfirst(i));
}
return retval;
}
#endif
/*
* member()
* nondestructive, returns t iff l1 is a member of the list l2
*/
bool
member(void *l1, List *l2)
{
List *i;
foreach(i, l2)
{
if (equal((Node *) l1, (Node *) lfirst(i)))
return true;
}
return false;
}
/*
* like member(), but use when pointer-equality comparison is sufficient
*/
bool
ptrMember(void *l1, List *l2)
{
List *i;
foreach(i, l2)
{
if (l1 == lfirst(i))
return true;
}
return false;
}
/*
* membership test for integer lists
*/
bool
intMember(int l1, List *l2)
{
List *i;
foreach(i, l2)
{
if (l1 == lfirsti(i))
return true;
}
return false;
}
/*
* membership test for Oid lists
*/
bool
oidMember(Oid l1, List *l2)
{
List *i;
foreach(i, l2)
{
if (l1 == lfirsto(i))
return true;
}
return false;
}
/*
* lremove
* 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 simple pointer comparison.
* See also LispRemove.
*/
List *
lremove(void *elem, List *list)
{
List *l;
List *prev = NIL;
List *result = list;
foreach(l, list)
{
if (elem == lfirst(l))
break;
prev = l;
}
if (l != NIL)
{
if (prev == NIL)
result = lnext(l);
else
lnext(prev) = lnext(l);
pfree(l);
}
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.
*/
List *
LispRemove(void *elem, List *list)
{
List *l;
List *prev = NIL;
List *result = list;
foreach(l, list)
{
if (equal(elem, lfirst(l)))
break;
prev = l;
}
if (l != NIL)
{
if (prev == NIL)
result = lnext(l);
else
lnext(prev) = lnext(l);
pfree(l);
}
return result;
}
/*
* lremovei
* lremove() for integer lists.
*/
List *
lremovei(int elem, List *list)
{
List *l;
List *prev = NIL;
List *result = list;
foreach(l, list)
{
if (elem == lfirsti(l))
break;
prev = l;
}
if (l != NIL)
{
if (prev == NIL)
result = lnext(l);
else
lnext(prev) = lnext(l);
pfree(l);
}
return result;
}
/*
* ltruncate
* Truncate a list to n elements.
* Does nothing if n >= length(list).
* NB: the list is modified in-place!
*/
List *
ltruncate(int n, List *list)
{
List *ptr;
if (n <= 0)
return NIL; /* truncate to zero length */
foreach(ptr, list)
{
if (--n == 0)
{
lnext(ptr) = NIL;
break;
}
}
return list;
}
/*
* set_difference
*
* Return l1 without the elements in l2.
*
* The result is a fresh List, but it points to the same member nodes
* as were in l1.
*/
List *
set_difference(List *l1, List *l2)
{
List *result = NIL;
List *i;
if (l2 == NIL)
return listCopy(l1); /* slightly faster path for empty l2 */
foreach(i, l1)
{
if (!member(lfirst(i), l2))
result = lappend(result, lfirst(i));
}
return result;
}
/*
* set_differenceo
*
* Same as set_difference, but for Oid lists
*/
List *
set_differenceo(List *l1, List *l2)
{
List *result = NIL;
List *i;
if (l2 == NIL)
return listCopy(l1); /* slightly faster path for empty l2 */
foreach(i, l1)
{
if (!oidMember(lfirsto(i), l2))
result = lappendo(result, lfirsto(i));
}
return result;
}
/*
* set_ptrDifference
*
* Same as set_difference, when pointer-equality comparison is sufficient
*/
List *
set_ptrDifference(List *l1, List *l2)
{
List *result = NIL;
List *i;
if (l2 == NIL)
return listCopy(l1); /* slightly faster path for empty l2 */
foreach(i, l1)
{
if (!ptrMember(lfirst(i), l2))
result = lappend(result, lfirst(i));
}
return result;
}
/*
* Reverse a list, non-destructively
*/
#ifdef NOT_USED
List *
lreverse(List *l)
{
List *result = NIL;
List *i;
foreach(i, l)
result = lcons(lfirst(i), result);
return result;
}
#endif
---------------------------(end of broadcast)---------------------------
TIP 3: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to [EMAIL PROTECTED] so that your
message can get through to the mailing list cleanly
