src/ceph/src/include/elist.h

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3 /*
   4  * Ceph - scalable distributed file system
   5  *
   6  * Copyright (C) 2004-2006 Sage Weil <sage@newdream.net>
   7  *
   8  * This is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License version 2.1, as published by the Free Software
  11  * Foundation.  See file COPYING.
  12  *
  13  */
  14
  15 #ifndef CEPH_ELIST_H
  16 #define CEPH_ELIST_H
  17
  18 /*
  19  * elist: embedded list.
  20  *
  21  * requirements:
  22  *   - elist<T>::item be embedded in the parent class
  23  *   - items are _always_ added to the list via the same elist<T>::item at the same
  24  *     fixed offset in the class.
  25  *   - begin(), front(), back() methods take the member offset as an argument for traversal.
  26  *
  27  */
  28
  29 #define member_offset(cls, member) ((size_t)(&((cls*)1)->member) - 1)
  30
  31 template<typename T>
  32 class elist {
  33 public:
  34   struct item {
  35     item *_prev, *_next;
  36
  37     item(T i=0) : _prev(this), _next(this) {}
  38     ~item() {
  39       assert(!is_on_list());
  40     }
  41
  42     // no copying!
  43     item(const item& other);
  44     const item& operator= (const item& right);
  45
  46
  47     bool empty() const { return _prev == this; }
  48     bool is_on_list() const { return !empty(); }
  49
  50     bool remove_myself() {
  51       if (_next == this) {
  52         assert(_prev == this);
  53         return false;
  54       }
  55       _next->_prev = _prev;
  56       _prev->_next = _next;
  57       _prev = _next = this;
  58       return true;
  59     }
  60
  61     void insert_after(item *other) {
  62       assert(other->empty());
  63       other->_prev = this;
  64       other->_next = _next;
  65       _next->_prev = other;
  66       _next = other;
  67     }
  68     void insert_before(item *other) {
  69       assert(other->empty());
  70       other->_next = this;
  71       other->_prev = _prev;
  72       _prev->_next = other;
  73       _prev = other;
  74     }
  75
  76     T get_item(size_t offset) {
  77       assert(offset);
  78       return (T)(((char *)this) - offset);
  79     }
  80   };
  81
  82 private:
  83   item _head;
  84   size_t item_offset;
  85
  86 public:
  87   elist(const elist& other);
  88   const elist& operator=(const elist& other);
  89
  90   elist(size_t o) : _head(NULL), item_offset(o) {}
  91   ~elist() {
  92     assert(_head.empty());
  93   }
  94
  95   bool empty() const {
  96     return _head.empty();
  97   }
  98
  99   void clear() {
 100     while (!_head.empty())
 101       pop_front();
 102   }
 103
 104   void push_front(item *i) {
 105     if (!i->empty())
 106       i->remove_myself();
 107     _head.insert_after(i);
 108   }
 109   void push_back(item *i) {
 110     if (!i->empty())
 111       i->remove_myself();
 112     _head.insert_before(i);
 113   }
 114
 115   T front(size_t o=0) {
 116     assert(!_head.empty());
 117     return _head._next->get_item(o ? o : item_offset);
 118   }
 119   T back(size_t o=0) {
 120     assert(!_head.empty());
 121     return _head._prev->get_item(o ? o : item_offset);
 122   }
 123
 124   void pop_front() {
 125     assert(!empty());
 126     _head._next->remove_myself();
 127   }
 128   void pop_back() {
 129     assert(!empty());
 130     _head._prev->remove_myself();
 131   }
 132
 133   void clear_list() {
 134     while (!empty())
 135       pop_front();
 136   }
 137
 138   enum mode_t {
 139     MAGIC, CURRENT, CACHE_NEXT
 140   };
 141
 142   class iterator {
 143   private:
 144     item *head;
 145     item *cur, *next;
 146     size_t item_offset;
 147     mode_t mode;
 148   public:
 149     iterator(item *h, size_t o, mode_t m) :
 150       head(h), cur(h->_next), next(cur->_next), item_offset(o),
 151       mode(m) {
 152       assert(item_offset > 0);
 153     }
 154     T operator*() {
 155       return cur->get_item(item_offset);
 156     }
 157     iterator& operator++() {
 158       assert(cur);
 159       assert(cur != head);
 160       if (mode == MAGIC) {
 161         // if 'cur' appears to be valid, use that.  otherwise,
 162         // use cached 'next'.
 163         // this is a bit magic, and probably a bad idea... :/
 164         if (cur->empty())
 165           cur = next;
 166         else
 167           cur = cur->_next;
 168       } else if (mode == CURRENT)
 169         cur = cur->_next;
 170       else if (mode == CACHE_NEXT)
 171         cur = next;
 172       else
 173         ceph_abort();
 174       next = cur->_next;
 175       return *this;
 176     }
 177     bool end() const {
 178       return cur == head;
 179     }
 180   };
 181
 182   iterator begin(size_t o=0) {
 183     return iterator(&_head, o ? o : item_offset, MAGIC);
 184   }
 185   iterator begin_use_current(size_t o=0) {
 186     return iterator(&_head, o ? o : item_offset, CURRENT);
 187   }
 188   iterator begin_cache_next(size_t o=0) {
 189     return iterator(&_head, o ? o : item_offset, CACHE_NEXT);
 190   }
 191 };
 192
 193
 194 #endif