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-2019, PostgreSQL Global Development Group 31 * Portions Copyright (c) 1994, Regents of the University of California 32 * 33 * src/include/nodes/pg_list.h 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. 75 */ 76 static inline ListCell * 77 list_head(const List *l) 78 { 79 return l ? l->head : NULL; 80 } 81 82 static inline ListCell * 83 list_tail(List *l) 84 { 85 return l ? l->tail : NULL; 86 } 87 88 static inline int 89 list_length(const List *l) 90 { 91 return l ? l->length : 0; 92 } 93 94 /* 95 * NB: There is an unfortunate legacy from a previous incarnation of 96 * the List API: the macro lfirst() was used to mean "the data in this 97 * cons cell". To avoid changing every usage of lfirst(), that meaning 98 * has been kept. As a result, lfirst() takes a ListCell and returns 99 * the data it contains; to get the data in the first cell of a 100 * List, use linitial(). Worse, lsecond() is more closely related to 101 * linitial() than lfirst(): given a List, lsecond() returns the data 102 * in the second cons cell. 103 */ 104 105 #define lnext(lc) ((lc)->next) 106 #define lfirst(lc) ((lc)->data.ptr_value) 107 #define lfirst_int(lc) ((lc)->data.int_value) 108 #define lfirst_oid(lc) ((lc)->data.oid_value) 109 #define lfirst_node(type,lc) castNode(type, lfirst(lc)) 110 111 #define linitial(l) lfirst(list_head(l)) 112 #define linitial_int(l) lfirst_int(list_head(l)) 113 #define linitial_oid(l) lfirst_oid(list_head(l)) 114 #define linitial_node(type,l) castNode(type, linitial(l)) 115 116 #define lsecond(l) lfirst(lnext(list_head(l))) 117 #define lsecond_int(l) lfirst_int(lnext(list_head(l))) 118 #define lsecond_oid(l) lfirst_oid(lnext(list_head(l))) 119 #define lsecond_node(type,l) castNode(type, lsecond(l)) 120 121 #define lthird(l) lfirst(lnext(lnext(list_head(l)))) 122 #define lthird_int(l) lfirst_int(lnext(lnext(list_head(l)))) 123 #define lthird_oid(l) lfirst_oid(lnext(lnext(list_head(l)))) 124 #define lthird_node(type,l) castNode(type, lthird(l)) 125 126 #define lfourth(l) lfirst(lnext(lnext(lnext(list_head(l))))) 127 #define lfourth_int(l) lfirst_int(lnext(lnext(lnext(list_head(l))))) 128 #define lfourth_oid(l) lfirst_oid(lnext(lnext(lnext(list_head(l))))) 129 #define lfourth_node(type,l) castNode(type, lfourth(l)) 130 131 #define llast(l) lfirst(list_tail(l)) 132 #define llast_int(l) lfirst_int(list_tail(l)) 133 #define llast_oid(l) lfirst_oid(list_tail(l)) 134 #define llast_node(type,l) castNode(type, llast(l)) 135 136 /* 137 * Convenience macros for building fixed-length lists 138 */ 139 #define list_make1(x1) lcons(x1, NIL) 140 #define list_make2(x1,x2) lcons(x1, list_make1(x2)) 141 #define list_make3(x1,x2,x3) lcons(x1, list_make2(x2, x3)) 142 #define list_make4(x1,x2,x3,x4) lcons(x1, list_make3(x2, x3, x4)) 143 #define list_make5(x1,x2,x3,x4,x5) lcons(x1, list_make4(x2, x3, x4, x5)) 144 145 #define list_make1_int(x1) lcons_int(x1, NIL) 146 #define list_make2_int(x1,x2) lcons_int(x1, list_make1_int(x2)) 147 #define list_make3_int(x1,x2,x3) lcons_int(x1, list_make2_int(x2, x3)) 148 #define list_make4_int(x1,x2,x3,x4) lcons_int(x1, list_make3_int(x2, x3, x4)) 149 #define list_make5_int(x1,x2,x3,x4,x5) lcons_int(x1, list_make4_int(x2, x3, x4, x5)) 150 151 #define list_make1_oid(x1) lcons_oid(x1, NIL) 152 #define list_make2_oid(x1,x2) lcons_oid(x1, list_make1_oid(x2)) 153 #define list_make3_oid(x1,x2,x3) lcons_oid(x1, list_make2_oid(x2, x3)) 154 #define list_make4_oid(x1,x2,x3,x4) lcons_oid(x1, list_make3_oid(x2, x3, x4)) 155 #define list_make5_oid(x1,x2,x3,x4,x5) lcons_oid(x1, list_make4_oid(x2, x3, x4, x5)) 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 /* 186 * for_both_cell - 187 * a convenience macro which loops through two lists starting from the 188 * specified cells of each. This macro loops through both lists at the same 189 * time, stopping when either list runs out of elements. Depending on the 190 * requirements of the call site, it may also be wise to assert that the 191 * lengths of the two lists are equal, and initcell1 and initcell2 are at 192 * the same position in the respective lists. 193 */ 194 #define for_both_cell(cell1, initcell1, cell2, initcell2) \ 195 for ((cell1) = (initcell1), (cell2) = (initcell2); \ 196 (cell1) != NULL && (cell2) != NULL; \ 197 (cell1) = lnext(cell1), (cell2) = lnext(cell2)) 198 199 /* 200 * forthree - 201 * the same for three lists 202 */ 203 #define forthree(cell1, list1, cell2, list2, cell3, list3) \ 204 for ((cell1) = list_head(list1), (cell2) = list_head(list2), (cell3) = list_head(list3); \ 205 (cell1) != NULL && (cell2) != NULL && (cell3) != NULL; \ 206 (cell1) = lnext(cell1), (cell2) = lnext(cell2), (cell3) = lnext(cell3)) 207 208 /* 209 * forfour - 210 * the same for four lists 211 */ 212 #define forfour(cell1, list1, cell2, list2, cell3, list3, cell4, list4) \ 213 for ((cell1) = list_head(list1), (cell2) = list_head(list2), \ 214 (cell3) = list_head(list3), (cell4) = list_head(list4); \ 215 (cell1) != NULL && (cell2) != NULL && \ 216 (cell3) != NULL && (cell4) != NULL; \ 217 (cell1) = lnext(cell1), (cell2) = lnext(cell2), \ 218 (cell3) = lnext(cell3), (cell4) = lnext(cell4)) 219 220 /* 221 * forfive - 222 * the same for five lists 223 */ 224 #define forfive(cell1, list1, cell2, list2, cell3, list3, cell4, list4, cell5, list5) \ 225 for ((cell1) = list_head(list1), (cell2) = list_head(list2), \ 226 (cell3) = list_head(list3), (cell4) = list_head(list4), \ 227 (cell5) = list_head(list5); \ 228 (cell1) != NULL && (cell2) != NULL && (cell3) != NULL && \ 229 (cell4) != NULL && (cell5) != NULL; \ 230 (cell1) = lnext(cell1), (cell2) = lnext(cell2), \ 231 (cell3) = lnext(cell3), (cell4) = lnext(cell4), \ 232 (cell5) = lnext(cell5)) 233 234 extern List *lappend(List *list, void *datum); 235 extern List *lappend_int(List *list, int datum); 236 extern List *lappend_oid(List *list, Oid datum); 237 238 extern ListCell *lappend_cell(List *list, ListCell *prev, void *datum); 239 extern ListCell *lappend_cell_int(List *list, ListCell *prev, int datum); 240 extern ListCell *lappend_cell_oid(List *list, ListCell *prev, Oid datum); 241 242 extern List *lcons(void *datum, List *list); 243 extern List *lcons_int(int datum, List *list); 244 extern List *lcons_oid(Oid datum, List *list); 245 246 extern List *list_concat(List *list1, List *list2); 247 extern List *list_truncate(List *list, int new_size); 248 249 extern ListCell *list_nth_cell(const List *list, int n); 250 extern void *list_nth(const List *list, int n); 251 extern int list_nth_int(const List *list, int n); 252 extern Oid list_nth_oid(const List *list, int n); 253 #define list_nth_node(type,list,n) castNode(type, list_nth(list, n)) 254 255 extern bool list_member(const List *list, const void *datum); 256 extern bool list_member_ptr(const List *list, const void *datum); 257 extern bool list_member_int(const List *list, int datum); 258 extern bool list_member_oid(const List *list, Oid datum); 259 260 extern List *list_delete(List *list, void *datum); 261 extern List *list_delete_ptr(List *list, void *datum); 262 extern List *list_delete_int(List *list, int datum); 263 extern List *list_delete_oid(List *list, Oid datum); 264 extern List *list_delete_first(List *list); 265 extern List *list_delete_cell(List *list, ListCell *cell, ListCell *prev); 266 267 extern List *list_union(const List *list1, const List *list2); 268 extern List *list_union_ptr(const List *list1, const List *list2); 269 extern List *list_union_int(const List *list1, const List *list2); 270 extern List *list_union_oid(const List *list1, const List *list2); 271 272 extern List *list_intersection(const List *list1, const List *list2); 273 extern List *list_intersection_int(const List *list1, const List *list2); 274 275 /* currently, there's no need for list_intersection_ptr etc */ 276 277 extern List *list_difference(const List *list1, const List *list2); 278 extern List *list_difference_ptr(const List *list1, const List *list2); 279 extern List *list_difference_int(const List *list1, const List *list2); 280 extern List *list_difference_oid(const List *list1, const List *list2); 281 282 extern List *list_append_unique(List *list, void *datum); 283 extern List *list_append_unique_ptr(List *list, void *datum); 284 extern List *list_append_unique_int(List *list, int datum); 285 extern List *list_append_unique_oid(List *list, Oid datum); 286 287 extern List *list_concat_unique(List *list1, List *list2); 288 extern List *list_concat_unique_ptr(List *list1, List *list2); 289 extern List *list_concat_unique_int(List *list1, List *list2); 290 extern List *list_concat_unique_oid(List *list1, List *list2); 291 292 extern void list_free(List *list); 293 extern void list_free_deep(List *list); 294 295 extern List *list_copy(const List *list); 296 extern List *list_copy_tail(const List *list, int nskip); 297 298 typedef int (*list_qsort_comparator) (const void *a, const void *b); 299 extern List *list_qsort(const List *list, list_qsort_comparator cmp); 300 301 /* 302 * To ease migration to the new list API, a set of compatibility 303 * macros are provided that reduce the impact of the list API changes 304 * as far as possible. Until client code has been rewritten to use the 305 * new list API, the ENABLE_LIST_COMPAT symbol can be defined before 306 * including pg_list.h 307 */ 308 #ifdef ENABLE_LIST_COMPAT 309 310 #define lfirsti(lc) lfirst_int(lc) 311 #define lfirsto(lc) lfirst_oid(lc) 312 313 #define makeList1(x1) list_make1(x1) 314 #define makeList2(x1, x2) list_make2(x1, x2) 315 #define makeList3(x1, x2, x3) list_make3(x1, x2, x3) 316 #define makeList4(x1, x2, x3, x4) list_make4(x1, x2, x3, x4) 317 318 #define makeListi1(x1) list_make1_int(x1) 319 #define makeListi2(x1, x2) list_make2_int(x1, x2) 320 321 #define makeListo1(x1) list_make1_oid(x1) 322 #define makeListo2(x1, x2) list_make2_oid(x1, x2) 323 324 #define lconsi(datum, list) lcons_int(datum, list) 325 #define lconso(datum, list) lcons_oid(datum, list) 326 327 #define lappendi(list, datum) lappend_int(list, datum) 328 #define lappendo(list, datum) lappend_oid(list, datum) 329 330 #define nconc(l1, l2) list_concat(l1, l2) 331 332 #define nth(n, list) list_nth(list, n) 333 334 #define member(datum, list) list_member(list, datum) 335 #define ptrMember(datum, list) list_member_ptr(list, datum) 336 #define intMember(datum, list) list_member_int(list, datum) 337 #define oidMember(datum, list) list_member_oid(list, datum) 338 339 /* 340 * Note that the old lremove() determined equality via pointer 341 * comparison, whereas the new list_delete() uses equal(); in order to 342 * keep the same behavior, we therefore need to map lremove() calls to 343 * list_delete_ptr() rather than list_delete() 344 */ 345 #define lremove(elem, list) list_delete_ptr(list, elem) 346 #define LispRemove(elem, list) list_delete(list, elem) 347 #define lremovei(elem, list) list_delete_int(list, elem) 348 #define lremoveo(elem, list) list_delete_oid(list, elem) 349 350 #define ltruncate(n, list) list_truncate(list, n) 351 352 #define set_union(l1, l2) list_union(l1, l2) 353 #define set_uniono(l1, l2) list_union_oid(l1, l2) 354 #define set_ptrUnion(l1, l2) list_union_ptr(l1, l2) 355 356 #define set_difference(l1, l2) list_difference(l1, l2) 357 #define set_differenceo(l1, l2) list_difference_oid(l1, l2) 358 #define set_ptrDifference(l1, l2) list_difference_ptr(l1, l2) 359 360 #define equali(l1, l2) equal(l1, l2) 361 #define equalo(l1, l2) equal(l1, l2) 362 363 #define freeList(list) list_free(list) 364 365 #define listCopy(list) list_copy(list) 366 367 extern int length(List *list); 368 #endif /* ENABLE_LIST_COMPAT */ 369 370 #endif /* PG_LIST_H */ 371