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