-// -*- 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