summaryrefslogtreecommitdiffstats
path: root/src/include/elist.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/include/elist.h')
-rw-r--r--src/include/elist.h193
1 files changed, 193 insertions, 0 deletions
diff --git a/src/include/elist.h b/src/include/elist.h
new file mode 100644
index 000000000..38be35dbf
--- /dev/null
+++ b/src/include/elist.h
@@ -0,0 +1,193 @@
+// -*- 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() {
+ ceph_assert(!is_on_list());
+ }
+
+ item(const item& other) = delete;
+ const item& operator= (const item& right) = delete;
+
+
+ bool empty() const { return _prev == this; }
+ bool is_on_list() const { return !empty(); }
+
+ bool remove_myself() {
+ if (_next == this) {
+ ceph_assert(_prev == this);
+ return false;
+ }
+ _next->_prev = _prev;
+ _prev->_next = _next;
+ _prev = _next = this;
+ return true;
+ }
+
+ void insert_after(item *other) {
+ ceph_assert(other->empty());
+ other->_prev = this;
+ other->_next = _next;
+ _next->_prev = other;
+ _next = other;
+ }
+ void insert_before(item *other) {
+ ceph_assert(other->empty());
+ other->_next = this;
+ other->_prev = _prev;
+ _prev->_next = other;
+ _prev = other;
+ }
+
+ T get_item(size_t offset) {
+ ceph_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() {
+ ceph_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) {
+ ceph_assert(!_head.empty());
+ return _head._next->get_item(o ? o : item_offset);
+ }
+ T back(size_t o=0) {
+ ceph_assert(!_head.empty());
+ return _head._prev->get_item(o ? o : item_offset);
+ }
+
+ void pop_front() {
+ ceph_assert(!empty());
+ _head._next->remove_myself();
+ }
+ void pop_back() {
+ ceph_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) {
+ ceph_assert(item_offset > 0);
+ }
+ T operator*() {
+ return cur->get_item(item_offset);
+ }
+ iterator& operator++() {
+ ceph_assert(cur);
+ ceph_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