include/list.h

   1 /*
   2  * PgBouncer - Lightweight connection pooler for PostgreSQL.
   3  *
   4  * Copyright (c) 2007-2009  Marko Kreen, Skype Technologies OÜ
   5  *
   6  * Permission to use, copy, modify, and/or distribute this software for any
   7  * purpose with or without fee is hereby granted, provided that the above
   8  * copyright notice and this permission notice appear in all copies.
   9  *
  10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  11  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  12  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  13  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  14  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  15  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  16  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  17  */
  18
  19 /*
  20  * Circular doubly linked list implementation.
  21  *
  22  * Basic idea from <linux/list.h>.
  23  *
  24  * <sys/queue.h> seemed usable, but overcomplicated.
  25  */
  26
  27 #ifndef __LIST_H_
  28 #define __LIST_H_
  29
  30 /* turn on slow checking */
  31 /* #define LIST_DEBUG */
  32
  33 /* give offset of a field inside struct */
  34 #ifndef offsetof
  35 #define offsetof(type, field) ((unsigned long)&(((type *)0)->field))
  36 #endif
  37
  38 /* given pointer to field inside struct, return pointer to struct */
  39 #ifndef container_of
  40 #define container_of(ptr, type, field) ((type *)((char *)(ptr) - offsetof(type, field)))
  41 #endif
  42
  43 /* list type */
  44 typedef struct List List;
  45 struct List {
  46         List *next;
  47         List *prev;
  48 };
  49
  50 #define LIST(var) List var = { &var, &var }
  51
  52 /* initialize struct */
  53 static inline void list_init(List *list)
  54 {
  55         list->next = list->prev = list;
  56 }
  57
  58 /* is list empty? */
  59 static inline bool list_empty(const List *list)
  60 {
  61         return list->next == list;
  62 }
  63
  64 /* add item to the start of the list */
  65 static inline List *list_prepend(List *item, List *list)
  66 {
  67         Assert(list_empty(item));
  68
  69         item->next = list->next;
  70         item->prev = list;
  71         list->next->prev = item;
  72         list->next = item;
  73         return item;
  74 }
  75
  76 /* add item to the end of the list */
  77 static inline List *list_append(List *item, List *list)
  78 {
  79         Assert(list_empty(item));
  80
  81         item->next = list;
  82         item->prev = list->prev;
  83         list->prev->next = item;
  84         list->prev = item;
  85         return item;
  86 }
  87
  88 /* remove item from list */
  89 static inline List *list_del(List *item)
  90 {
  91         item->prev->next = item->next;
  92         item->next->prev = item->prev;
  93         item->next = item->prev = item;
  94         return item;
  95 }
  96
  97 /* remove first from list and return */
  98 static inline List *list_pop(List *list)
  99 {
 100         if (list_empty(list))
 101                 return NULL;
 102         return list_del(list->next);
 103 }
 104
 105 /* remove first from list and return */
 106 static inline List *list_first(const List *list)
 107 {
 108         if (list_empty(list))
 109                 return NULL;
 110         return list->next;
 111 }
 112
 113 /* put all elems in one list in the start of another list */
 114 static inline void list_prepend_list(List *src, List *dst)
 115 {
 116         if (list_empty(src))
 117                 return;
 118         src->next->prev = dst;
 119         src->prev->next = dst->next;
 120         dst->next->prev = src->prev;
 121         dst->next = src->next;
 122
 123         src->next = src->prev = src;
 124 }
 125
 126 /* put all elems in one list in the end of another list */
 127 static inline void list_append_list(List *src, List *dst)
 128 {
 129         if (list_empty(src))
 130                 return;
 131         src->next->prev = dst->prev;
 132         src->prev->next = dst;
 133         dst->prev->next = src->next;
 134         dst->prev = src->prev;
 135
 136         src->next = src->prev = src;
 137 }
 138
 139 /* remove first elem from list and return with casting */
 140 #define list_pop_type(list, typ, field) \
 141         (list_empty(list) ? NULL \
 142          : container_of(list_del((list)->next), typ, field))
 143
 144 /* loop over list */
 145 #define list_for_each(item, list) \
 146         for ((item) = (list)->next; \
 147              (item) != (list); \
 148              (item) = (item)->next)
 149
 150 /* loop over list and allow removing item */
 151 #define list_for_each_safe(item, list, tmp) \
 152         for ((item) = (list)->next, (tmp) = (list)->next->next; \
 153              (item) != (list); \
 154              (item) = (tmp), (tmp) = (tmp)->next)
 155
 156 static inline bool item_in_list(const List *item, const List *list)
 157 {
 158         List *tmp;
 159         list_for_each(tmp, list)
 160                 if (tmp == item)
 161                         return 1;
 162         return 0;
 163 }
 164
 165
 166 /*
 167  * wrapper for List that keeps track of number of items
 168  */
 169
 170 typedef struct StatList StatList;
 171 struct StatList {
 172         List head;
 173         int cur_count;
 174 #ifdef LIST_DEBUG
 175         const char *name;
 176 #endif
 177 };
 178
 179 #ifdef LIST_DEBUG
 180 #define STATLIST(var) StatList var = { {&var.head, &var.head}, 0, #var }
 181 #else
 182 #define STATLIST(var) StatList var = { {&var.head, &var.head}, 0 }
 183 #endif
 184
 185 static inline void statlist_inc_count(StatList *list, int val)
 186 {
 187         list->cur_count += val;
 188 }
 189
 190 static inline void statlist_prepend(List *item, StatList *list)
 191 {
 192         list_prepend(item, &list->head);
 193         statlist_inc_count(list, 1);
 194 }
 195
 196 static inline void statlist_append(List *item, StatList *list)
 197 {
 198         list_append(item, &list->head);
 199         statlist_inc_count(list, 1);
 200 }
 201
 202 static inline void statlist_put_before(List *item, StatList *list, List *pos)
 203 {
 204         list_append(item, pos);
 205         statlist_inc_count(list, 1);
 206 }
 207
 208 static inline void statlist_remove(List *item, StatList *list)
 209 {
 210 #ifdef LIST_DEBUG
 211         /* sanity check */
 212         if (!item_in_list(item, &list->head))
 213                 fatal("item in wrong list, expected: %s", list->name);
 214 #endif
 215
 216         list_del(item);
 217         list->cur_count--;
 218
 219         Assert(list->cur_count >= 0);
 220 }
 221
 222 static inline void statlist_init(StatList *list, const char *name)
 223 {
 224         list_init(&list->head);
 225         list->cur_count = 0;
 226 #ifdef LIST_DEBUG
 227         list->name = name;
 228 #endif
 229 }
 230
 231 static inline int statlist_count(const StatList *list)
 232 {
 233         Assert(list->cur_count > 0 || list_empty(&list->head));
 234         return list->cur_count;
 235 }
 236
 237 static inline List *statlist_pop(StatList *list)
 238 {
 239         List *item = list_pop(&list->head);
 240
 241         if (item)
 242                 list->cur_count--;
 243
 244         Assert(list->cur_count >= 0);
 245
 246         return item;
 247 }
 248
 249 static inline void statlist_prepend_list(StatList *src, StatList *dst)
 250 {
 251         list_prepend_list(&src->head, &dst->head);
 252         statlist_inc_count(dst, src->cur_count);
 253         src->cur_count = 0;
 254 }
 255
 256 static inline void statlist_append_list(StatList *src, StatList *dst)
 257 {
 258         list_append_list(&src->head, &dst->head);
 259         statlist_inc_count(dst, src->cur_count);
 260         src->cur_count = 0;
 261 }
 262
 263 static inline List *statlist_first(const StatList *list)
 264 {
 265         return list_first(&list->head);
 266 }
 267
 268 static inline bool statlist_empty(const StatList *list)
 269 {
 270         return list_empty(&list->head);
 271 }
 272
 273 #define statlist_for_each(item, list) list_for_each(item, &((list)->head))
 274 #define statlist_for_each_safe(item, list, tmp) list_for_each_safe(item, &((list)->head), tmp)
 275
 276 #endif /* __LIST_H_ */
 277