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