include/linux/dlists.h

   1 #ifndef DLISTS_H
   2 #define DLISTS_H
   3 /*
   4  * include/linux/dlists.h - macros for double linked lists
   5  *
   6  * Copyright (C) 1997, Thomas Schoebel-Theuer,
   7  * <schoebel@informatik.uni-stuttgart.de>.
   8  */
   9
  10 /* dlists are cyclic ringlists, so the last element cannot be tested
  11  * for NULL. Use the following construct for traversing cyclic lists:
  12  * ptr = anchor;
  13  * if(ptr) do {
  14  *      ...
  15  *      ptr = ptr->{something}_{next,prev};
  16  * } while(ptr != anchor);
  17  * The effort here is paid off with much simpler inserts/removes.
  18  * Examples for usage of these macros can be found in fs/ninode.c.
  19  * To access the last element in constant time, simply use
  20  * anchor->{something}_prev.
  21  */
  22
  23 #define DEF_GENERIC_INSERT(CHANGE,PREFIX,NAME,TYPE,NEXT,PREV) \
  24 static inline void PREFIX##NAME(TYPE ** anchor, TYPE * elem)\
  25 {\
  26         TYPE * oldfirst = *anchor;\
  27         if(!oldfirst) {\
  28                 elem->NEXT = elem->PREV = *anchor = elem;\
  29         } else {\
  30                 elem->PREV = oldfirst->PREV;\
  31                 elem->NEXT = oldfirst;\
  32                 oldfirst->PREV->NEXT = elem;\
  33                 oldfirst->PREV = elem;\
  34                 if(CHANGE)\
  35                         *anchor = elem;\
  36         }\
  37 }
  38
  39 /* insert_* is always at the first position */
  40 #define DEF_INSERT(NAME,TYPE,NEXT,PREV) \
  41                    DEF_GENERIC_INSERT(1,insert_,NAME,TYPE,NEXT,PREV)
  42
  43 /* append_* is always at the tail  */
  44 #define DEF_APPEND(NAME,TYPE,NEXT,PREV) \
  45                    DEF_GENERIC_INSERT(0,append_,NAME,TYPE,NEXT,PREV)
  46
  47 /* use this to insert _before_ oldelem somewhere in the middle of the list.
  48  * the list must not be empty, and oldelem must be already a member.*/
  49 #define DEF_INSERT_MIDDLE(NAME,TYPE) \
  50 static inline void insert_middle_##NAME(TYPE ** anchor, TYPE * oldelem, TYPE * elem)\
  51 {\
  52         int status = (oldelem == *anchor);\
  53         insert_##NAME(&oldelem, elem);\
  54         if(status)\
  55                 *anchor = oldelem;\
  56 }
  57
  58 /* remove can be done with any element in the list */
  59 #define DEF_REMOVE(NAME,TYPE,NEXT,PREV) \
  60 static inline void remove_##NAME(TYPE ** anchor, TYPE * elem)\
  61 {\
  62         TYPE * next = elem->NEXT;\
  63         if(next == elem) {\
  64                 *anchor = NULL;\
  65         } else {\
  66                 TYPE * prev = elem->PREV;\
  67                 prev->NEXT = next;\
  68                 next->PREV = prev;\
  69                 elem->NEXT = elem->PREV = NULL;/*leave this during debugging*/\
  70                 if(*anchor == elem)\
  71                         *anchor = next;\
  72         }\
  73 }
  74
  75
  76 /* According to ideas from David S. Miller, here is a slightly
  77  * more efficient plug-in compatible version using non-cyclic lists,
  78  * but allowing neither backward traversals nor constant time access
  79  * to the last element.
  80  * Note that although the interface is the same, the PPREV pointer must be
  81  * declared doubly indirect and the test for end-of-list is different. */
  82
  83 /* as above, this inserts always at the head */
  84 #define DEF_LIN_INSERT(NAME,TYPE,NEXT,PPREV) \
  85 static inline void insert_##NAME(TYPE ** anchor, TYPE * elem)\
  86 {\
  87         TYPE * first;\
  88         if((elem->NEXT = first = *anchor))\
  89                 first->PPREV = &elem->NEXT;\
  90         *anchor = elem;\
  91         elem->PPREV = anchor;\
  92 }
  93
  94 /* as above, this works with any list element */
  95 #define DEF_LIN_REMOVE(NAME,TYPE,NEXT,PPREV) \
  96 static inline void remove_##NAME(TYPE ** anchor, TYPE * elem)\
  97 {\
  98         TYPE * pprev;\
  99         if((pprev = elem->PPREV)) {\
 100                 TYPE * next;\
 101                 if((next = elem->NEXT))\
 102                         next->PPREV = pprev;\
 103                 *pprev = next;\
 104                 elem->PPREV = elem->NEXT = NULL; /*leave this for debugging*/\
 105         }\
 106 }
 107
 108 #endif