1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
4 * Ceph - scalable distributed file system
6 * Copyright (C) 2004-2006 Sage Weil <sage@newdream.net>
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.
19 * elist: embedded list.
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.
29 #define member_offset(cls, member) ((size_t)(&((cls*)1)->member) - 1)
37 item(T i=0) : _prev(this), _next(this) {}
39 assert(!is_on_list());
43 item(const item& other);
44 const item& operator= (const item& right);
47 bool empty() const { return _prev == this; }
48 bool is_on_list() const { return !empty(); }
50 bool remove_myself() {
52 assert(_prev == this);
61 void insert_after(item *other) {
62 assert(other->empty());
68 void insert_before(item *other) {
69 assert(other->empty());
76 T get_item(size_t offset) {
78 return (T)(((char *)this) - offset);
87 elist(const elist& other);
88 const elist& operator=(const elist& other);
90 elist(size_t o) : _head(NULL), item_offset(o) {}
92 assert(_head.empty());
100 while (!_head.empty())
104 void push_front(item *i) {
107 _head.insert_after(i);
109 void push_back(item *i) {
112 _head.insert_before(i);
115 T front(size_t o=0) {
116 assert(!_head.empty());
117 return _head._next->get_item(o ? o : item_offset);
120 assert(!_head.empty());
121 return _head._prev->get_item(o ? o : item_offset);
126 _head._next->remove_myself();
130 _head._prev->remove_myself();
139 MAGIC, CURRENT, CACHE_NEXT
149 iterator(item *h, size_t o, mode_t m) :
150 head(h), cur(h->_next), next(cur->_next), item_offset(o),
152 assert(item_offset > 0);
155 return cur->get_item(item_offset);
157 iterator& operator++() {
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... :/
168 } else if (mode == CURRENT)
170 else if (mode == CACHE_NEXT)
182 iterator begin(size_t o=0) {
183 return iterator(&_head, o ? o : item_offset, MAGIC);
185 iterator begin_use_current(size_t o=0) {
186 return iterator(&_head, o ? o : item_offset, CURRENT);
188 iterator begin_cache_next(size_t o=0) {
189 return iterator(&_head, o ? o : item_offset, CACHE_NEXT);