initial code repo

[stor4nfv.git] / src / ceph / src / include / elist.h

diff --git a/src/ceph/src/include/elist.h b/src/ceph/src/include/elist.h
new file mode 100644 (file)
index 0000000..1bf3df8
--- /dev/null
+++ b/src/ceph/src/include/elist.h
@@ -0,0 +1,194 @@
+// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- 
+// vim: ts=8 sw=2 smarttab
+/*
+ * Ceph - scalable distributed file system
+ *
+ * Copyright (C) 2004-2006 Sage Weil <sage@newdream.net>
+ *
+ * This is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License version 2.1, as published by the Free Software 
+ * Foundation.  See file COPYING.
+ * 
+ */
+
+#ifndef CEPH_ELIST_H
+#define CEPH_ELIST_H
+
+/*
+ * elist: embedded list.
+ *
+ * requirements:
+ *   - elist<T>::item be embedded in the parent class
+ *   - items are _always_ added to the list via the same elist<T>::item at the same
+ *     fixed offset in the class.
+ *   - begin(), front(), back() methods take the member offset as an argument for traversal.
+ *
+ */
+
+#define member_offset(cls, member) ((size_t)(&((cls*)1)->member) - 1)
+
+template<typename T>
+class elist {
+public:
+  struct item {
+    item *_prev, *_next;
+    
+    item(T i=0) : _prev(this), _next(this) {}
+    ~item() { 
+      assert(!is_on_list());
+    }
+
+    // no copying!
+    item(const item& other);
+    const item& operator= (const item& right);
+
+    
+    bool empty() const { return _prev == this; }
+    bool is_on_list() const { return !empty(); }
+
+    bool remove_myself() {
+      if (_next == this) {
+       assert(_prev == this);
+       return false;
+      }
+      _next->_prev = _prev;
+      _prev->_next = _next;
+      _prev = _next = this;
+      return true;
+    }
+
+    void insert_after(item *other) {
+      assert(other->empty());
+      other->_prev = this;
+      other->_next = _next;
+      _next->_prev = other;
+      _next = other;
+    }
+    void insert_before(item *other) {
+      assert(other->empty());
+      other->_next = this;
+      other->_prev = _prev;
+      _prev->_next = other;
+      _prev = other;
+    }
+
+    T get_item(size_t offset) {
+      assert(offset);
+      return (T)(((char *)this) - offset); 
+    }
+  };
+
+private:
+  item _head;
+  size_t item_offset;
+
+public:
+  elist(const elist& other);
+  const elist& operator=(const elist& other);
+
+  elist(size_t o) : _head(NULL), item_offset(o) {}
+  ~elist() { 
+    assert(_head.empty());
+  }
+
+  bool empty() const {
+    return _head.empty();
+  }
+
+  void clear() {
+    while (!_head.empty())
+      pop_front();
+  }
+
+  void push_front(item *i) {
+    if (!i->empty()) 
+      i->remove_myself();
+    _head.insert_after(i);
+  }
+  void push_back(item *i) {
+    if (!i->empty()) 
+      i->remove_myself();
+    _head.insert_before(i);
+  }
+
+  T front(size_t o=0) {
+    assert(!_head.empty());
+    return _head._next->get_item(o ? o : item_offset);
+  }
+  T back(size_t o=0) {
+    assert(!_head.empty());
+    return _head._prev->get_item(o ? o : item_offset);
+  }
+
+  void pop_front() {
+    assert(!empty());
+    _head._next->remove_myself();
+  }
+  void pop_back() {
+    assert(!empty());
+    _head._prev->remove_myself();
+  }
+
+  void clear_list() {
+    while (!empty())
+      pop_front();
+  }
+
+  enum mode_t {
+    MAGIC, CURRENT, CACHE_NEXT
+  };
+
+  class iterator {
+  private:
+    item *head;
+    item *cur, *next;
+    size_t item_offset;
+    mode_t mode;
+  public:
+    iterator(item *h, size_t o, mode_t m) :
+      head(h), cur(h->_next), next(cur->_next), item_offset(o),
+      mode(m) {
+      assert(item_offset > 0);
+    }
+    T operator*() {
+      return cur->get_item(item_offset);
+    }
+    iterator& operator++() {
+      assert(cur);
+      assert(cur != head);
+      if (mode == MAGIC) {
+       // if 'cur' appears to be valid, use that.  otherwise,
+       // use cached 'next'.
+       // this is a bit magic, and probably a bad idea... :/
+       if (cur->empty())
+         cur = next;
+       else
+         cur = cur->_next;
+      } else if (mode == CURRENT)
+       cur = cur->_next;
+      else if (mode == CACHE_NEXT)
+       cur = next;
+      else
+       ceph_abort();
+      next = cur->_next;
+      return *this;
+    }
+    bool end() const {
+      return cur == head;
+    }
+  };
+
+  iterator begin(size_t o=0) {
+    return iterator(&_head, o ? o : item_offset, MAGIC);
+  }
+  iterator begin_use_current(size_t o=0) {
+    return iterator(&_head, o ? o : item_offset, CURRENT);
+  }
+  iterator begin_cache_next(size_t o=0) {
+    return iterator(&_head, o ? o : item_offset, CACHE_NEXT);
+  }
+};
+
+
+#endif