src/libpq/include/nodes/pg_list.h

Ir a la documentación de este archivo.

/*-------------------------------------------------------------------------
 *
 * pg_list.h
 *        interface for PostgreSQL generic linked list package
 *
 * This package implements singly-linked homogeneous lists.
 *
 * It is important to have constant-time length, append, and prepend
 * operations. To achieve this, we deal with two distinct data
 * structures:
 *
 *              1. A set of "list cells": each cell contains a data field and
 *                 a link to the next cell in the list or NULL.
 *              2. A single structure containing metadata about the list: the
 *                 type of the list, pointers to the head and tail cells, and
 *                 the length of the list.
 *
 * We support three types of lists:
 *
 *      T_List: lists of pointers
 *              (in practice usually pointers to Nodes, but not always;
 *              declared as "void *" to minimize casting annoyances)
 *      T_IntList: lists of integers
 *      T_OidList: lists of Oids
 *
 * (At the moment, ints and Oids are the same size, but they may not
 * always be so; try to be careful to maintain the distinction.)
 *
 *
 * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * $PostgreSQL: pgsql/src/include/nodes/pg_list.h,v 1.53 2005/10/15 02:49:45 momjian Exp $
 *
 *-------------------------------------------------------------------------
 */
#ifndef PG_LIST_H
#define PG_LIST_H

#include "nodes/nodes.h"


typedef struct ListCell ListCell;

typedef struct List
{
        NodeTag         type;                   /* T_List, T_IntList, or T_OidList */
        int                     length;
        ListCell   *head;
        ListCell   *tail;
} List;

struct ListCell
{
        union
        {
                void       *ptr_value;
                int                     int_value;
                Oid                     oid_value;
        }                       data;
        ListCell   *next;
};

/*
 * 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)

/*
 * These routines are used frequently. However, we can't implement
 * them as macros, since we want to avoid double-evaluation of macro
 * arguments. Therefore, we implement them using GCC inline functions,
 * and as regular functions with non-GCC compilers.
 */
#ifdef __GNUC__

static __inline__ ListCell *
list_head(List *l)
{
        return l ? l->head : NULL;
}

static __inline__ ListCell *
list_tail(List *l)
{
        return l ? l->tail : NULL;
}

static __inline__ int
list_length(List *l)
{
        return l ? l->length : 0;
}
#else

extern ListCell *list_head(List *l);
extern ListCell *list_tail(List *l);
extern int      list_length(List *l);
#endif   /* __GNUC__ */

/*
 * NB: There is an unfortunate legacy from a previous incarnation of
 * the List API: the macro lfirst() was used to mean "the data in this
 * cons cell". To avoid changing every usage of lfirst(), that meaning
 * has been kept. As a result, lfirst() takes a ListCell and returns
 * the data it contains; to get the data in the first cell of a
 * List, use linitial(). Worse, lsecond() is more closely related to
 * linitial() than lfirst(): given a List, lsecond() returns the data
 * in the second cons cell.
 */

#define lnext(lc)                               ((lc)->next)
#define lfirst(lc)                              ((lc)->data.ptr_value)
#define lfirst_int(lc)                  ((lc)->data.int_value)
#define lfirst_oid(lc)                  ((lc)->data.oid_value)

#define linitial(l)                             lfirst(list_head(l))
#define linitial_int(l)                 lfirst_int(list_head(l))
#define linitial_oid(l)                 lfirst_oid(list_head(l))

#define lsecond(l)                              lfirst(lnext(list_head(l)))
#define lsecond_int(l)                  lfirst_int(lnext(list_head(l)))
#define lsecond_oid(l)                  lfirst_oid(lnext(list_head(l)))

#define lthird(l)                               lfirst(lnext(lnext(list_head(l))))
#define lthird_int(l)                   lfirst_int(lnext(lnext(list_head(l))))
#define lthird_oid(l)                   lfirst_oid(lnext(lnext(list_head(l))))

#define lfourth(l)                              lfirst(lnext(lnext(lnext(list_head(l)))))
#define lfourth_int(l)                  lfirst_int(lnext(lnext(lnext(list_head(l)))))
#define lfourth_oid(l)                  lfirst_oid(lnext(lnext(lnext(list_head(l)))))

#define llast(l)                                lfirst(list_tail(l))
#define llast_int(l)                    lfirst_int(list_tail(l))
#define llast_oid(l)                    lfirst_oid(list_tail(l))

/*
 * Convenience macros for building fixed-length lists
 */
#define list_make1(x1)                          lcons(x1, NIL)
#define list_make2(x1,x2)                       lcons(x1, list_make1(x2))
#define list_make3(x1,x2,x3)            lcons(x1, list_make2(x2, x3))
#define list_make4(x1,x2,x3,x4)         lcons(x1, list_make3(x2, x3, x4))

#define list_make1_int(x1)                      lcons_int(x1, NIL)
#define list_make2_int(x1,x2)           lcons_int(x1, list_make1_int(x2))
#define list_make3_int(x1,x2,x3)        lcons_int(x1, list_make2_int(x2, x3))
#define list_make4_int(x1,x2,x3,x4) lcons_int(x1, list_make3_int(x2, x3, x4))

#define list_make1_oid(x1)                      lcons_oid(x1, NIL)
#define list_make2_oid(x1,x2)           lcons_oid(x1, list_make1_oid(x2))
#define list_make3_oid(x1,x2,x3)        lcons_oid(x1, list_make2_oid(x2, x3))
#define list_make4_oid(x1,x2,x3,x4) lcons_oid(x1, list_make3_oid(x2, x3, x4))

/*
 * foreach -
 *        a convenience macro which loops through the list
 */
#define foreach(cell, l)        \
        for ((cell) = list_head(l); (cell) != NULL; (cell) = lnext(cell))

/*
 * for_each_cell -
 *        a convenience macro which loops through a list starting from a
 *        specified cell
 */
#define for_each_cell(cell, initcell)   \
        for ((cell) = (initcell); (cell) != NULL; (cell) = lnext(cell))

/*
 * forboth -
 *        a convenience macro for advancing through two linked lists
 *        simultaneously. This macro loops through both lists at the same
 *        time, stopping when either list runs out of elements. Depending
 *        on the requirements of the call site, it may also be wise to
 *        assert that the lengths of the two lists are equal.
 */
#define forboth(cell1, list1, cell2, list2)                                                     \
        for ((cell1) = list_head(list1), (cell2) = list_head(list2);    \
                 (cell1) != NULL && (cell2) != NULL;                                            \
                 (cell1) = lnext(cell1), (cell2) = lnext(cell2))

extern List *lappend(List *list, void *datum);
extern List *lappend_int(List *list, int datum);
extern List *lappend_oid(List *list, Oid datum);

extern ListCell *lappend_cell(List *list, ListCell *prev, void *datum);
extern ListCell *lappend_cell_int(List *list, ListCell *prev, int datum);
extern ListCell *lappend_cell_oid(List *list, ListCell *prev, Oid datum);

extern List *lcons(void *datum, List *list);
extern List *lcons_int(int datum, List *list);
extern List *lcons_oid(Oid datum, List *list);

extern List *list_concat(List *list1, List *list2);
extern List *list_truncate(List *list, int new_size);

extern void *list_nth(List *list, int n);
extern int      list_nth_int(List *list, int n);
extern Oid      list_nth_oid(List *list, int n);

extern bool list_member(List *list, void *datum);
extern bool list_member_ptr(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_delete(List *list, void *datum);
extern List *list_delete_ptr(List *list, void *datum);
extern List *list_delete_int(List *list, int datum);
extern List *list_delete_oid(List *list, Oid datum);
extern List *list_delete_first(List *list);
extern List *list_delete_cell(List *list, ListCell *cell, ListCell *prev);

extern List *list_union(List *list1, List *list2);
extern List *list_union_ptr(List *list1, List *list2);
extern List *list_union_int(List *list1, List *list2);
extern List *list_union_oid(List *list1, List *list2);

extern List *list_difference(List *list1, List *list2);
extern List *list_difference_ptr(List *list1, List *list2);
extern List *list_difference_int(List *list1, List *list2);
extern List *list_difference_oid(List *list1, List *list2);

extern List *list_append_unique(List *list, void *datum);
extern List *list_append_unique_ptr(List *list, void *datum);
extern List *list_append_unique_int(List *list, int datum);
extern List *list_append_unique_oid(List *list, Oid datum);

extern List *list_concat_unique(List *list1, List *list2);
extern List *list_concat_unique_ptr(List *list1, List *list2);
extern List *list_concat_unique_int(List *list1, List *list2);
extern List *list_concat_unique_oid(List *list1, List *list2);

extern void list_free(List *list);
extern void list_free_deep(List *list);

extern List *list_copy(List *list);
extern List *list_copy_tail(List *list, int nskip);

/*
 * To ease migration to the new list API, a set of compatibility
 * macros are provided that reduce the impact of the list API changes
 * as far as possible. Until client code has been rewritten to use the
 * new list API, the ENABLE_LIST_COMPAT symbol can be defined before
 * including pg_list.h
 */
#ifdef ENABLE_LIST_COMPAT

#define lfirsti(lc)                                     lfirst_int(lc)
#define lfirsto(lc)                                     lfirst_oid(lc)

#define makeList1(x1)                           list_make1(x1)
#define makeList2(x1, x2)                       list_make2(x1, x2)
#define makeList3(x1, x2, x3)           list_make3(x1, x2, x3)
#define makeList4(x1, x2, x3, x4)       list_make4(x1, x2, x3, x4)

#define makeListi1(x1)                          list_make1_int(x1)
#define makeListi2(x1, x2)                      list_make2_int(x1, x2)

#define makeListo1(x1)                          list_make1_oid(x1)
#define makeListo2(x1, x2)                      list_make2_oid(x1, x2)

#define lconsi(datum, list)                     lcons_int(datum, list)
#define lconso(datum, list)                     lcons_oid(datum, list)

#define lappendi(list, datum)           lappend_int(list, datum)
#define lappendo(list, datum)           lappend_oid(list, datum)

#define nconc(l1, l2)                           list_concat(l1, l2)

#define nth(n, list)                            list_nth(list, n)

#define member(datum, list)                     list_member(list, datum)
#define ptrMember(datum, list)          list_member_ptr(list, datum)
#define intMember(datum, list)          list_member_int(list, datum)
#define oidMember(datum, list)          list_member_oid(list, datum)

/*
 * Note that the old lremove() determined equality via pointer
 * comparison, whereas the new list_delete() uses equal(); in order to
 * keep the same behavior, we therefore need to map lremove() calls to
 * list_delete_ptr() rather than list_delete()
 */
#define lremove(elem, list)                     list_delete_ptr(list, elem)
#define LispRemove(elem, list)          list_delete(list, elem)
#define lremovei(elem, list)            list_delete_int(list, elem)
#define lremoveo(elem, list)            list_delete_oid(list, elem)

#define ltruncate(n, list)                      list_truncate(list, n)

#define set_union(l1, l2)                       list_union(l1, l2)
#define set_uniono(l1, l2)                      list_union_oid(l1, l2)
#define set_ptrUnion(l1, l2)            list_union_ptr(l1, l2)

#define set_difference(l1, l2)          list_difference(l1, l2)
#define set_differenceo(l1, l2)         list_difference_oid(l1, l2)
#define set_ptrDifference(l1, l2)       list_difference_ptr(l1, l2)

#define equali(l1, l2)                          equal(l1, l2)
#define equalo(l1, l2)                          equal(l1, l2)

#define freeList(list)                          list_free(list)

#define listCopy(list)                          list_copy(list)

extern int      length(List *list);
#endif   /* ENABLE_LIST_COMPAT */

#endif   /* PG_LIST_H */