]>
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 | ||
1e59de90 | 162 | class iterator { |
7c673cae FG |
163 | private: |
164 | item *cur; | |
165 | public: | |
1e59de90 TL |
166 | using iterator_category = std::forward_iterator_tag; |
167 | using value_type = T; | |
168 | using difference_type = std::ptrdiff_t; | |
169 | using pointer = T*; | |
170 | using reference = T&; | |
7c673cae FG |
171 | iterator(item *i = 0) : cur(i) {} |
172 | T operator*() { return static_cast<T>(cur->_item); } | |
173 | iterator& operator++() { | |
11fdf7f2 TL |
174 | ceph_assert(cur); |
175 | ceph_assert(cur->_list); | |
7c673cae FG |
176 | cur = cur->_next; |
177 | return *this; | |
178 | } | |
179 | bool end() const { return cur == 0; } | |
1e59de90 TL |
180 | friend bool operator==(const iterator& lhs, const iterator& rhs) { |
181 | return lhs.cur == rhs.cur; | |
7c673cae | 182 | } |
1e59de90 TL |
183 | friend bool operator!=(const iterator& lhs, const iterator& rhs) { |
184 | return lhs.cur != rhs.cur; | |
7c673cae FG |
185 | } |
186 | }; | |
187 | ||
188 | iterator begin() { return iterator(_front); } | |
189 | iterator end() { return iterator(NULL); } | |
190 | ||
1e59de90 | 191 | class const_iterator { |
7c673cae FG |
192 | private: |
193 | item *cur; | |
194 | public: | |
1e59de90 TL |
195 | using iterator_category = std::forward_iterator_tag; |
196 | using value_type = T; | |
197 | using difference_type = std::ptrdiff_t; | |
198 | using pointer = const T*; | |
199 | using reference = const T&; | |
200 | ||
7c673cae FG |
201 | const_iterator(item *i = 0) : cur(i) {} |
202 | const T operator*() { return static_cast<const T>(cur->_item); } | |
203 | const_iterator& operator++() { | |
11fdf7f2 TL |
204 | ceph_assert(cur); |
205 | ceph_assert(cur->_list); | |
7c673cae FG |
206 | cur = cur->_next; |
207 | return *this; | |
208 | } | |
209 | bool end() const { return cur == 0; } | |
1e59de90 TL |
210 | friend bool operator==(const const_iterator& lhs, |
211 | const const_iterator& rhs) { | |
212 | return lhs.cur == rhs.cur; | |
11fdf7f2 | 213 | } |
1e59de90 TL |
214 | friend bool operator!=(const const_iterator& lhs, |
215 | const const_iterator& rhs) { | |
216 | return lhs.cur != rhs.cur; | |
11fdf7f2 | 217 | } |
7c673cae FG |
218 | }; |
219 | ||
220 | const_iterator begin() const { return const_iterator(_front); } | |
221 | const_iterator end() const { return const_iterator(NULL); } | |
11fdf7f2 TL |
222 | |
223 | friend std::ostream &operator<<(std::ostream &oss, const xlist<T> &list) { | |
224 | bool first = true; | |
225 | for (const auto &item : list) { | |
226 | if (!first) { | |
227 | oss << ", "; | |
228 | } | |
229 | oss << *item; /* item should be a pointer */ | |
230 | first = false; | |
231 | } | |
232 | return oss; | |
233 | } | |
7c673cae FG |
234 | }; |
235 | ||
236 | ||
237 | #endif |