ceph/src/include/xlist.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_XLIST_H
  16 #define CEPH_XLIST_H
  17
  18 #include "include/assert.h"
  19 #include <iterator>
  20 #include <cstdlib>
  21
  22 template<typename T>
  23 class xlist {
  24 public:
  25   struct item {
  26     T _item;
  27     item *_prev, *_next;
  28     xlist *_list;
  29
  30     item(T i) : _item(i), _prev(0), _next(0), _list(0) {}
  31     ~item() {
  32       assert(!is_on_list());
  33       //remove_myself();
  34     }
  35
  36     // no copying!
  37     item(const item& other);
  38     const item& operator= (const item& right);
  39
  40
  41     xlist* get_list() { return _list; }
  42     bool is_on_list() const { return _list ? true:false; }
  43     bool remove_myself() {
  44       if (_list) {
  45         _list->remove(this);
  46         assert(_list == 0);
  47         return true;
  48       } else
  49         return false;
  50     }
  51     void move_to_front() {
  52       assert(_list);
  53       _list->push_front(this);
  54     }
  55     void move_to_back() {
  56       assert(_list);
  57       _list->push_back(this);
  58     }
  59   };
  60
  61   typedef item* value_type;
  62   typedef item* const_reference;
  63
  64 private:
  65   item *_front, *_back;
  66   size_t _size;
  67
  68 public:
  69   xlist(const xlist& other) {
  70     _front = other._front;
  71     _back = other._back;
  72     _size = other._size;
  73   }
  74
  75   xlist() : _front(0), _back(0), _size(0) {}
  76   ~xlist() {
  77     assert(_size == 0);
  78     assert(_front == 0);
  79     assert(_back == 0);
  80   }
  81
  82   size_t size() const {
  83     assert((bool)_front == (bool)_size);
  84     return _size;
  85   }
  86   bool empty() const {
  87     assert((bool)_front == (bool)_size);
  88     return _front == 0;
  89   }
  90
  91   void clear() {
  92     while (_front)
  93       remove(_front);
  94     assert((bool)_front == (bool)_size);
  95   }
  96
  97   void push_front(item *i) {
  98     if (i->_list)
  99       i->_list->remove(i);
 100
 101     i->_list = this;
 102     i->_next = _front;
 103     i->_prev = 0;
 104     if (_front)
 105       _front->_prev = i;
 106     else
 107       _back = i;
 108     _front = i;
 109     _size++;
 110   }
 111   void push_back(item *i) {
 112     if (i->_list)
 113       i->_list->remove(i);
 114
 115     i->_list = this;
 116     i->_next = 0;
 117     i->_prev = _back;
 118     if (_back)
 119       _back->_next = i;
 120     else
 121       _front = i;
 122     _back = i;
 123     _size++;
 124   }
 125   void remove(item *i) {
 126     assert(i->_list == this);
 127
 128     if (i->_prev)
 129       i->_prev->_next = i->_next;
 130     else
 131       _front = i->_next;
 132     if (i->_next)
 133       i->_next->_prev = i->_prev;
 134     else
 135       _back = i->_prev;
 136     _size--;
 137
 138     i->_list = 0;
 139     i->_next = i->_prev = 0;
 140     assert((bool)_front == (bool)_size);
 141   }
 142
 143   T front() { return static_cast<T>(_front->_item); }
 144   const T front() const { return static_cast<const T>(_front->_item); }
 145
 146   T back() { return static_cast<T>(_back->_item); }
 147   const T back() const { return static_cast<const T>(_back->_item); }
 148
 149   void pop_front() {
 150     assert(!empty());
 151     remove(_front);
 152   }
 153   void pop_back() {
 154     assert(!empty());
 155     remove(_back);
 156   }
 157
 158   class iterator: std::iterator<std::forward_iterator_tag, T> {
 159   private:
 160     item *cur;
 161   public:
 162     iterator(item *i = 0) : cur(i) {}
 163     T operator*() { return static_cast<T>(cur->_item); }
 164     iterator& operator++() {
 165       assert(cur);
 166       assert(cur->_list);
 167       cur = cur->_next;
 168       return *this;
 169     }
 170     bool end() const { return cur == 0; }
 171     bool operator==(const iterator& rhs) const {
 172       return cur == rhs.cur;
 173     }
 174     bool operator!=(const iterator& rhs) const {
 175       return cur != rhs.cur;
 176     }
 177   };
 178
 179   iterator begin() { return iterator(_front); }
 180   iterator end() { return iterator(NULL); }
 181
 182   class const_iterator: std::iterator<std::forward_iterator_tag, T> {
 183   private:
 184     item *cur;
 185   public:
 186     const_iterator(item *i = 0) : cur(i) {}
 187     const T operator*() { return static_cast<const T>(cur->_item); }
 188     const_iterator& operator++() {
 189       assert(cur);
 190       assert(cur->_list);
 191       cur = cur->_next;
 192       return *this;
 193     }
 194     bool end() const { return cur == 0; }
 195   };
 196
 197   const_iterator begin() const { return const_iterator(_front); }
 198   const_iterator end() const { return const_iterator(NULL); }
 199 };
 200
 201
 202 #endif