lib/ldb/include/dlinklist.h

   1 /*
   2    Unix SMB/CIFS implementation.
   3    some simple double linked list macros
   4
   5    Copyright (C) Andrew Tridgell 1998-2010
   6
   7      ** NOTE! The following LGPL license applies to the ldb
   8      ** library. This does NOT imply that all of Samba is released
   9      ** under the LGPL
  10
  11    This library is free software; you can redistribute it and/or
  12    modify it under the terms of the GNU Lesser General Public
  13    License as published by the Free Software Foundation; either
  14    version 3 of the License, or (at your option) any later version.
  15
  16    This library is distributed in the hope that it will be useful,
  17    but WITHOUT ANY WARRANTY; without even the implied warranty of
  18    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  19    Lesser General Public License for more details.
  20
  21    You should have received a copy of the GNU Lesser General Public
  22    License along with this library; if not, see <http://www.gnu.org/licenses/>.
  23 */
  24
  25 /* To use these macros you must have a structure containing a next and
  26    prev pointer */
  27
  28 #ifndef _DLINKLIST_H
  29 #define _DLINKLIST_H
  30
  31 /*
  32   February 2010 - changed list format to have a prev pointer from the
  33   list head. This makes DLIST_ADD_END() O(1) even though we only have
  34   one list pointer.
  35
  36   The scheme is as follows:
  37
  38      1) with no entries in the list:
  39           list_head == NULL
  40
  41      2) with 1 entry in the list:
  42           list_head->next == NULL
  43           list_head->prev == list_head
  44
  45      3) with 2 entries in the list:
  46           list_head->next == element2
  47           list_head->prev == element2
  48           element2->prev == list_head
  49           element2->next == NULL
  50
  51      4) with N entries in the list:
  52           list_head->next == element2
  53           list_head->prev == elementN
  54           elementN->prev == element{N-1}
  55           elementN->next == NULL
  56
  57   This allows us to find the tail of the list by using
  58   list_head->prev, which means we can add to the end of the list in
  59   O(1) time
  60
  61
  62   Note that the 'type' arguments below are no longer needed, but
  63   are kept for now to prevent an incompatible argument change
  64  */
  65
  66
  67 /*
  68    add an element at the front of a list
  69 */
  70 #define DLIST_ADD(list, p) \
  71 do { \
  72         if (!(list)) { \
  73                 (p)->prev = (list) = (p);  \
  74                 (p)->next = NULL; \
  75         } else { \
  76                 (p)->prev = (list)->prev; \
  77                 (list)->prev = (p); \
  78                 (p)->next = (list); \
  79                 (list) = (p); \
  80         } \
  81 } while (0)
  82
  83 /*
  84    remove an element from a list
  85    Note that the element doesn't have to be in the list. If it
  86    isn't then this is a no-op
  87 */
  88 #define DLIST_REMOVE(list, p) \
  89 do { \
  90         if ((p) == (list)) { \
  91                 if ((p)->next) (p)->next->prev = (p)->prev; \
  92                 (list) = (p)->next; \
  93         } else if ((list) && (p) == (list)->prev) {     \
  94                 (p)->prev->next = NULL; \
  95                 (list)->prev = (p)->prev; \
  96         } else { \
  97                 if ((p)->prev) (p)->prev->next = (p)->next; \
  98                 if ((p)->next) (p)->next->prev = (p)->prev; \
  99         } \
 100         if ((p) != (list)) (p)->next = (p)->prev = NULL;        \
 101 } while (0)
 102
 103 /*
 104    find the head of the list given any element in it.
 105    Note that this costs O(N), so you should avoid this macro
 106    if at all possible!
 107 */
 108 #define DLIST_HEAD(p, result_head) \
 109 do { \
 110        (result_head) = (p); \
 111        while (DLIST_PREV(result_head)) (result_head) = (result_head)->prev; \
 112 } while(0)
 113
 114 /* return the last element in the list */
 115 #define DLIST_TAIL(list) ((list)?(list)->prev:NULL)
 116
 117 /* return the previous element in the list. */
 118 #define DLIST_PREV(p) (((p)->prev && (p)->prev->next != NULL)?(p)->prev:NULL)
 119
 120 /* insert 'p' after the given element 'el' in a list. If el is NULL then
 121    this is the same as a DLIST_ADD() */
 122 #define DLIST_ADD_AFTER(list, p, el) \
 123 do { \
 124         if (!(list) || !(el)) { \
 125                 DLIST_ADD(list, p); \
 126         } else { \
 127                 (p)->prev = (el);   \
 128                 (p)->next = (el)->next;         \
 129                 (el)->next = (p);               \
 130                 if ((p)->next) (p)->next->prev = (p);   \
 131                 if ((list)->prev == (el)) (list)->prev = (p); \
 132         }\
 133 } while (0)
 134
 135
 136 /*
 137    add to the end of a list.
 138    Note that 'type' is ignored
 139 */
 140 #define DLIST_ADD_END(list, p, type)                    \
 141 do { \
 142         if (!(list)) { \
 143                 DLIST_ADD(list, p); \
 144         } else { \
 145                 DLIST_ADD_AFTER(list, p, (list)->prev); \
 146         } \
 147 } while (0)
 148
 149 /* promote an element to the from of a list */
 150 #define DLIST_PROMOTE(list, p) \
 151 do { \
 152           DLIST_REMOVE(list, p); \
 153           DLIST_ADD(list, p); \
 154 } while (0)
 155
 156 /*
 157    demote an element to the end of a list.
 158    Note that 'type' is ignored
 159 */
 160 #define DLIST_DEMOTE(list, p, type)                     \
 161 do { \
 162         DLIST_REMOVE(list, p); \
 163         DLIST_ADD_END(list, p, NULL);           \
 164 } while (0)
 165
 166 /*
 167    concatenate two lists - putting all elements of the 2nd list at the
 168    end of the first list.
 169    Note that 'type' is ignored
 170 */
 171 #define DLIST_CONCATENATE(list1, list2, type)   \
 172 do { \
 173         if (!(list1)) { \
 174                 (list1) = (list2); \
 175         } else { \
 176                 (list1)->prev->next = (list2); \
 177                 if (list2) { \
 178                         void *_tmplist = (void *)(list1)->prev; \
 179                         (list1)->prev = (list2)->prev; \
 180                         (list2)->prev = _tmplist; \
 181                 } \
 182         } \
 183 } while (0)
 184
 185 #endif /* _DLINKLIST_H */