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 */
 135 #define DLIST_ADD_END(list, p) \
 136 do { \
 137         if (!(list)) { \
 138                 DLIST_ADD(list, p); \
 139         } else { \
 140                 DLIST_ADD_AFTER(list, p, (list)->prev); \
 141         } \
 142 } while (0)
 143
 144 /* promote an element to the front of a list */
 145 #define DLIST_PROMOTE(list, p) \
 146 do { \
 147           DLIST_REMOVE(list, p); \
 148           DLIST_ADD(list, p); \
 149 } while (0)
 150
 151 /*
 152    demote an element to the end of a list.
 153    Note that 'type' is ignored
 154 */
 155 #define DLIST_DEMOTE(list, p, type)                     \
 156 do { \
 157         DLIST_REMOVE(list, p); \
 158         DLIST_ADD_END(list, p); \
 159 } while (0)
 160
 161 /*
 162    concatenate two lists - putting all elements of the 2nd list at the
 163    end of the first list.
 164    Note that 'type' is ignored
 165 */
 166 #define DLIST_CONCATENATE(list1, list2, type)   \
 167 do { \
 168         if (!(list1)) { \
 169                 (list1) = (list2); \
 170         } else { \
 171                 (list1)->prev->next = (list2); \
 172                 if (list2) { \
 173                         void *_tmplist = (void *)(list1)->prev; \
 174                         (list1)->prev = (list2)->prev; \
 175                         (list2)->prev = _tmplist; \
 176                 } \
 177         } \
 178 } while (0)
 179
 180 #endif /* _DLINKLIST_H */