include/c++/util/list.h

   1 #ifndef _UTIL_LIST_H
   2 #define _UTIL_LIST_H
   3
   4 #include <assert.h>
   5
   6 namespace Util
   7 {
   8         // Linked lists with nodes embedded in the data.
   9         //
  10         // Duplicating for auto-init is ugly, but at least it's implementation
  11         // ugliness; inheriting would cause interface ugliness, with users
  12         // required to either declare ListAutoInit for the vastly common case,
  13         // or else use ListNoAutoInit pointers when following prev or next.
  14         //
  15         // Maybe some sort of templatization could be done.
  16
  17         struct ListNoAutoInit {
  18                 ListNoAutoInit *prev, *next;
  19
  20                 void init()
  21                 {
  22                         prev = next = this;
  23                 }
  24
  25                 bool empty()
  26                 {
  27                         return next == this;
  28                 }
  29
  30                 void del()
  31                 {
  32                         prev->next = next;
  33                         next->prev = prev;
  34                         init();
  35                 }
  36
  37                 void add_front(ListNoAutoInit *newelem)
  38                 {
  39                         assert(newelem->empty());
  40
  41                         newelem->prev = this;
  42                         next->prev = newelem;
  43                         newelem->next = next;
  44                         next = newelem;
  45                 }
  46
  47                 void add_back(ListNoAutoInit *newelem)
  48                 {
  49                         assert(newelem->empty());
  50
  51                         newelem->next = this;
  52                         prev->next = newelem;
  53                         newelem->prev = prev;
  54                         prev = newelem;
  55                 }
  56
  57                 template<typename T, int offset>
  58                 T *entry()
  59                 {
  60                         return reinterpret_cast<T *>(reinterpret_cast<ulong>(this) - offset);
  61                 }
  62         };
  63
  64         struct List {
  65                 List *prev, *next;
  66
  67                 List()
  68                 {
  69                         init();
  70                 }
  71
  72                 void init()
  73                 {
  74                         prev = next = this;
  75                 }
  76
  77                 bool empty()
  78                 {
  79                         return next == this;
  80                 }
  81
  82                 void del()
  83                 {
  84                         prev->next = next;
  85                         next->prev = prev;
  86                         init();
  87                 }
  88
  89                 void add_front(List *newelem)
  90                 {
  91                         assert(newelem->empty());
  92
  93                         newelem->prev = this;
  94                         next->prev = newelem;
  95                         newelem->next = next;
  96                         next = newelem;
  97                 }
  98
  99                 void add_back(List *newelem)
 100                 {
 101                         assert(newelem->empty());
 102
 103                         newelem->next = this;
 104                         prev->next = newelem;
 105                         newelem->prev = prev;
 106                         prev = newelem;
 107                 }
 108
 109                 template<typename T, int offset>
 110                 T *entry()
 111                 {
 112                         return reinterpret_cast<T *>(reinterpret_cast<ulong>(this) - offset);
 113                 }
 114         };
 115
 116         // Ick.  We can't pass in "member" as a template parameter, and
 117         // it'd be annoying to have to manually use offsetof all over
 118         // the place.  Use this as if it were a member function, but
 119         // be careful of the global name.
 120
 121         #define listentry(T, member) entry<T, offsetof(T, member)>()
 122 }
 123
 124 #endif