git.8kb.co.uk Git - pgpool-ii/pgpool-ii_2.2.5/blob - parser/pg_list.h

   1 /*-------------------------------------------------------------------------
   2  *
   3  * pg_list.h
   4  *        interface for PostgreSQL generic linked list package
   5  *
   6  * This package implements singly-linked homogeneous lists.
   7  *
   8  * It is important to have constant-time length, append, and prepend
   9  * operations. To achieve this, we deal with two distinct data
  10  * structures:
  11  *
  12  *              1. A set of "list cells": each cell contains a data field and
  13  *                 a link to the next cell in the list or NULL.
  14  *              2. A single structure containing metadata about the list: the
  15  *                 type of the list, pointers to the head and tail cells, and
  16  *                 the length of the list.
  17  *
  18  * We support three types of lists:
  19  *
  20  *      T_List: lists of pointers
  21  *              (in practice usually pointers to Nodes, but not always;
  22  *              declared as "void *" to minimize casting annoyances)
  23  *      T_IntList: lists of integers
  24  *      T_OidList: lists of Oids
  25  *
  26  * (At the moment, ints and Oids are the same size, but they may not
  27  * always be so; try to be careful to maintain the distinction.)
  28  *
  29  * There is also limited support for lists of TransactionIds; since these
  30  * are used in only one or two places, we don't provide a full implementation,
  31  * but map them onto Oid lists.  This effectively assumes that TransactionId
  32  * is no wider than Oid and both are unsigned types.
  33  *
  34  *
  35  * Portions Copyright (c) 2003-2008, PgPool Global Development Group
  36  * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
  37  * Portions Copyright (c) 1994, Regents of the University of California
  38  *
  39  * $PostgreSQL: pgsql/src/include/nodes/pg_list.h,v 1.56 2007/01/05 22:19:55 momjian Exp $
  40  *
  41  *-------------------------------------------------------------------------
  42  */
  43 #ifndef PG_LIST_H
  44 #define PG_LIST_H
  45
  46 #include <stdio.h>
  47 #include "pool_parser.h"
  48 #include "nodes.h"
  49
  50
  51 typedef struct ListCell ListCell;
  52
  53 typedef struct List
  54 {
  55         NodeTag         type;                   /* T_List, T_IntList, or T_OidList */
  56         int                     length;
  57         ListCell   *head;
  58         ListCell   *tail;
  59 } List;
  60
  61 struct ListCell
  62 {
  63         union
  64         {
  65                 void       *ptr_value;
  66                 int                     int_value;
  67                 Oid                     oid_value;
  68         }                       data;
  69         ListCell   *next;
  70 };
  71
  72 /*
  73  * The *only* valid representation of an empty list is NIL; in other
  74  * words, a non-NIL list is guaranteed to have length >= 1 and
  75  * head/tail != NULL
  76  */
  77 #define NIL                                             ((List *) NULL)
  78
  79 /*
  80  * These routines are used frequently. However, we can't implement
  81  * them as macros, since we want to avoid double-evaluation of macro
  82  * arguments. Therefore, we implement them using GCC inline functions,
  83  * and as regular functions with non-GCC compilers.
  84  */
  85 #ifdef __GNUC__
  86
  87 static __inline__ ListCell *
  88 list_head(List *l)
  89 {
  90         return l ? l->head : NULL;
  91 }
  92
  93 static __inline__ ListCell *
  94 list_tail(List *l)
  95 {
  96         return l ? l->tail : NULL;
  97 }
  98
  99 static __inline__ int
 100 list_length(List *l)
 101 {
 102         return l ? l->length : 0;
 103 }
 104 #else
 105
 106 extern ListCell *list_head(List *l);
 107 extern ListCell *list_tail(List *l);
 108 extern int      list_length(List *l);
 109 #endif   /* __GNUC__ */
 110
 111 /*
 112  * NB: There is an unfortunate legacy from a previous incarnation of
 113  * the List API: the macro lfirst() was used to mean "the data in this
 114  * cons cell". To avoid changing every usage of lfirst(), that meaning
 115  * has been kept. As a result, lfirst() takes a ListCell and returns
 116  * the data it contains; to get the data in the first cell of a
 117  * List, use linitial(). Worse, lsecond() is more closely related to
 118  * linitial() than lfirst(): given a List, lsecond() returns the data
 119  * in the second cons cell.
 120  */
 121
 122 #define lnext(lc)                               ((lc)->next)
 123 #define lfirst(lc)                              ((lc)->data.ptr_value)
 124 #define lfirst_int(lc)                  ((lc)->data.int_value)
 125 #define lfirst_oid(lc)                  ((lc)->data.oid_value)
 126
 127 #define linitial(l)                             lfirst(list_head(l))
 128 #define linitial_int(l)                 lfirst_int(list_head(l))
 129 #define linitial_oid(l)                 lfirst_oid(list_head(l))
 130
 131 #define lsecond(l)                              lfirst(lnext(list_head(l)))
 132 #define lsecond_int(l)                  lfirst_int(lnext(list_head(l)))
 133 #define lsecond_oid(l)                  lfirst_oid(lnext(list_head(l)))
 134
 135 #define lthird(l)                               lfirst(lnext(lnext(list_head(l))))
 136 #define lthird_int(l)                   lfirst_int(lnext(lnext(list_head(l))))
 137 #define lthird_oid(l)                   lfirst_oid(lnext(lnext(list_head(l))))
 138
 139 #define lfourth(l)                              lfirst(lnext(lnext(lnext(list_head(l)))))
 140 #define lfourth_int(l)                  lfirst_int(lnext(lnext(lnext(list_head(l)))))
 141 #define lfourth_oid(l)                  lfirst_oid(lnext(lnext(lnext(list_head(l)))))
 142
 143 #define llast(l)                                lfirst(list_tail(l))
 144 #define llast_int(l)                    lfirst_int(list_tail(l))
 145 #define llast_oid(l)                    lfirst_oid(list_tail(l))
 146
 147 /*
 148  * Convenience macros for building fixed-length lists
 149  */
 150 #define list_make1(x1)                          lcons(x1, NIL)
 151 #define list_make2(x1,x2)                       lcons(x1, list_make1(x2))
 152 #define list_make3(x1,x2,x3)            lcons(x1, list_make2(x2, x3))
 153 #define list_make4(x1,x2,x3,x4)         lcons(x1, list_make3(x2, x3, x4))
 154
 155 #define list_make1_int(x1)                      lcons_int(x1, NIL)
 156 #define list_make2_int(x1,x2)           lcons_int(x1, list_make1_int(x2))
 157 #define list_make3_int(x1,x2,x3)        lcons_int(x1, list_make2_int(x2, x3))
 158 #define list_make4_int(x1,x2,x3,x4) lcons_int(x1, list_make3_int(x2, x3, x4))
 159
 160 #define list_make1_oid(x1)                      lcons_oid(x1, NIL)
 161 #define list_make2_oid(x1,x2)           lcons_oid(x1, list_make1_oid(x2))
 162 #define list_make3_oid(x1,x2,x3)        lcons_oid(x1, list_make2_oid(x2, x3))
 163 #define list_make4_oid(x1,x2,x3,x4) lcons_oid(x1, list_make3_oid(x2, x3, x4))
 164
 165 /*
 166  * Limited support for lists of TransactionIds, mapped onto lists of Oids
 167  */
 168 #define lfirst_xid(lc)                          ((TransactionId) lfirst_oid(lc))
 169 #define lappend_xid(list, datum)        lappend_oid(list, (Oid) (datum))
 170
 171 /*
 172  * foreach -
 173  *        a convenience macro which loops through the list
 174  */
 175 #define foreach(cell, l)        \
 176         for ((cell) = list_head(l); (cell) != NULL; (cell) = lnext(cell))
 177
 178 /*
 179  * for_each_cell -
 180  *        a convenience macro which loops through a list starting from a
 181  *        specified cell
 182  */
 183 #define for_each_cell(cell, initcell)   \
 184         for ((cell) = (initcell); (cell) != NULL; (cell) = lnext(cell))
 185
 186 /*
 187  * forboth -
 188  *        a convenience macro for advancing through two linked lists
 189  *        simultaneously. This macro loops through both lists at the same
 190  *        time, stopping when either list runs out of elements. Depending
 191  *        on the requirements of the call site, it may also be wise to
 192  *        assert that the lengths of the two lists are equal.
 193  */
 194 #define forboth(cell1, list1, cell2, list2)                                                     \
 195         for ((cell1) = list_head(list1), (cell2) = list_head(list2);    \
 196                  (cell1) != NULL && (cell2) != NULL;                                            \
 197                  (cell1) = lnext(cell1), (cell2) = lnext(cell2))
 198
 199 extern List *lappend(List *list, void *datum);
 200 extern List *lappend_int(List *list, int datum);
 201 extern List *lappend_oid(List *list, Oid datum);
 202
 203 extern ListCell *lappend_cell(List *list, ListCell *prev, void *datum);
 204 extern ListCell *lappend_cell_int(List *list, ListCell *prev, int datum);
 205 extern ListCell *lappend_cell_oid(List *list, ListCell *prev, Oid datum);
 206
 207 extern List *lcons(void *datum, List *list);
 208 extern List *lcons_int(int datum, List *list);
 209 extern List *lcons_oid(Oid datum, List *list);
 210
 211 extern List *list_concat(List *list1, List *list2);
 212 extern List *list_truncate(List *list, int new_size);
 213
 214 extern void *list_nth(List *list, int n);
 215 extern int      list_nth_int(List *list, int n);
 216 extern Oid      list_nth_oid(List *list, int n);
 217
 218 extern bool list_member(List *list, void *datum);
 219 extern bool list_member_ptr(List *list, void *datum);
 220 extern bool list_member_int(List *list, int datum);
 221 extern bool list_member_oid(List *list, Oid datum);
 222
 223 extern List *list_delete(List *list, void *datum);
 224 extern List *list_delete_ptr(List *list, void *datum);
 225 extern List *list_delete_int(List *list, int datum);
 226 extern List *list_delete_oid(List *list, Oid datum);
 227 extern List *list_delete_first(List *list);
 228 extern List *list_delete_cell(List *list, ListCell *cell, ListCell *prev);
 229
 230 extern List *list_union(List *list1, List *list2);
 231 extern List *list_union_ptr(List *list1, List *list2);
 232 extern List *list_union_int(List *list1, List *list2);
 233 extern List *list_union_oid(List *list1, List *list2);
 234
 235 extern List *list_difference(List *list1, List *list2);
 236 extern List *list_difference_ptr(List *list1, List *list2);
 237 extern List *list_difference_int(List *list1, List *list2);
 238 extern List *list_difference_oid(List *list1, List *list2);
 239
 240 extern List *list_append_unique(List *list, void *datum);
 241 extern List *list_append_unique_ptr(List *list, void *datum);
 242 extern List *list_append_unique_int(List *list, int datum);
 243 extern List *list_append_unique_oid(List *list, Oid datum);
 244
 245 extern List *list_concat_unique(List *list1, List *list2);
 246 extern List *list_concat_unique_ptr(List *list1, List *list2);
 247 extern List *list_concat_unique_int(List *list1, List *list2);
 248 extern List *list_concat_unique_oid(List *list1, List *list2);
 249
 250 extern void list_free(List *list);
 251 extern void list_free_deep(List *list);
 252
 253 extern List *list_copy(List *list);
 254 extern List *list_copy_tail(List *list, int nskip);
 255
 256 /*
 257  * To ease migration to the new list API, a set of compatibility
 258  * macros are provided that reduce the impact of the list API changes
 259  * as far as possible. Until client code has been rewritten to use the
 260  * new list API, the ENABLE_LIST_COMPAT symbol can be defined before
 261  * including pg_list.h
 262  */
 263 #ifdef ENABLE_LIST_COMPAT
 264
 265 #define lfirsti(lc)                                     lfirst_int(lc)
 266 #define lfirsto(lc)                                     lfirst_oid(lc)
 267
 268 #define makeList1(x1)                           list_make1(x1)
 269 #define makeList2(x1, x2)                       list_make2(x1, x2)
 270 #define makeList3(x1, x2, x3)           list_make3(x1, x2, x3)
 271 #define makeList4(x1, x2, x3, x4)       list_make4(x1, x2, x3, x4)
 272
 273 #define makeListi1(x1)                          list_make1_int(x1)
 274 #define makeListi2(x1, x2)                      list_make2_int(x1, x2)
 275
 276 #define makeListo1(x1)                          list_make1_oid(x1)
 277 #define makeListo2(x1, x2)                      list_make2_oid(x1, x2)
 278
 279 #define lconsi(datum, list)                     lcons_int(datum, list)
 280 #define lconso(datum, list)                     lcons_oid(datum, list)
 281
 282 #define lappendi(list, datum)           lappend_int(list, datum)
 283 #define lappendo(list, datum)           lappend_oid(list, datum)
 284
 285 #define nconc(l1, l2)                           list_concat(l1, l2)
 286
 287 #define nth(n, list)                            list_nth(list, n)
 288
 289 #define member(datum, list)                     list_member(list, datum)
 290 #define ptrMember(datum, list)          list_member_ptr(list, datum)
 291 #define intMember(datum, list)          list_member_int(list, datum)
 292 #define oidMember(datum, list)          list_member_oid(list, datum)
 293
 294 /*
 295  * Note that the old lremove() determined equality via pointer
 296  * comparison, whereas the new list_delete() uses equal(); in order to
 297  * keep the same behavior, we therefore need to map lremove() calls to
 298  * list_delete_ptr() rather than list_delete()
 299  */
 300 #define lremove(elem, list)                     list_delete_ptr(list, elem)
 301 #define LispRemove(elem, list)          list_delete(list, elem)
 302 #define lremovei(elem, list)            list_delete_int(list, elem)
 303 #define lremoveo(elem, list)            list_delete_oid(list, elem)
 304
 305 #define ltruncate(n, list)                      list_truncate(list, n)
 306
 307 #define set_union(l1, l2)                       list_union(l1, l2)
 308 #define set_uniono(l1, l2)                      list_union_oid(l1, l2)
 309 #define set_ptrUnion(l1, l2)            list_union_ptr(l1, l2)
 310
 311 #define set_difference(l1, l2)          list_difference(l1, l2)
 312 #define set_differenceo(l1, l2)         list_difference_oid(l1, l2)
 313 #define set_ptrDifference(l1, l2)       list_difference_ptr(l1, l2)
 314
 315 #define equali(l1, l2)                          equal(l1, l2)
 316 #define equalo(l1, l2)                          equal(l1, l2)
 317
 318 #define freeList(list)                          list_free(list)
 319
 320 #define listCopy(list)                          list_copy(list)
 321
 322 extern int      length(List *list);
 323 #endif   /* ENABLE_LIST_COMPAT */
 324
 325 #endif   /* PG_LIST_H */