| 259 | |
| 260 | template <typename Key, typename Value> |
| 261 | WebCache<Key, Value>::Node* WebCache<Key, Value>::sieve_evict() { |
| 262 | if (_sieve_queue.empty()) { |
| 263 | return nullptr; |
| 264 | } |
| 265 | if (_sieve_hand == nullptr) { |
| 266 | _sieve_hand = &_sieve_queue.back(); |
| 267 | } |
| 268 | Node* result = nullptr; |
| 269 | const size_t queue_size_before = _sieve_queue.size(); |
| 270 | |
| 271 | auto hand = _sieve_queue.iterator_to(*_sieve_hand); |
| 272 | const auto rev_it = typename SieveQueue::reverse_iterator(std::next(hand)); |
| 273 | for (auto it = rev_it; it != _sieve_queue.rend(); ++it) { |
| 274 | Node& node = (*it); |
| 275 | if (node.visited) { |
| 276 | node.visited = false; |
| 277 | --hand; |
| 278 | } else { |
| 279 | hand = std::prev(_sieve_queue.erase(std::next(it).base())); |
| 280 | result = &node; |
| 281 | break; |
| 282 | } |
| 283 | } |
| 284 | // every node was visited. we need still need to evict the tail |
| 285 | if (result == nullptr) { |
| 286 | result = &_sieve_queue.back(); |
| 287 | _sieve_queue.pop_back(); |
| 288 | } |
| 289 | |
| 290 | ceph_assertf( |
| 291 | queue_size_before == 0 || (queue_size_before - _sieve_queue.size()) == 1, |
| 292 | "%d -> %d capacity:%d", queue_size_before, _sieve_queue.size(), |
| 293 | _capacity); |
| 294 | _sieve_hand = (hand == _sieve_queue.begin()) ? &_sieve_queue.back() : &*hand; |
| 295 | return result; |
| 296 | } |
| 297 | |
| 298 | template <typename Key, typename Value> |
| 299 | WebCache<Key, Value>::WebCache(size_t capacity, ceph::timespan ttl) |