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