add cursor without table lock?

[Jianghi]

will you add this feature?

#ifndef CUCKOOHASH_UNSAFE_ITER_HH
#define CUCKOOHASH_UNSAFE_ITER_HH
// inner class of cuckoohash_map
class const_cursor {
public:
const_cursor() { }
bool good() const { return good; }
// Return true if the iterators are from the same locked table and
// location, false otherwise.
bool operator==(const const_cursor &it) const {
if (!good && !it.good_)
return true;
return buckets_ == it.buckets_ && index_ == it.index_ &&
slot_ == it.slot_;
}

bool operator!=(const const_cursor &it) const {
return !(operator==(it));
}

const_pointer operator->() const { return &copyed_value_; }

// Advance the iterator to the next item in the table, or to the end
// of the table. Returns the iterator at its new position.
const_cursor &operator++() {
// 只需此处加锁即可
// Move forward until we get to a slot that is occupied, or we
// get to the end
++slot_;
for (; index_ < buckets_->size(); ++index_) {
for (; slot_ < slot_per_bucket(); ++slot_) {
if ((*buckets_)[index_].occupied(slot_)) {
fill_copyed_value();
return *this;
}
}
slot_ = 0;
}
assert(std::make_pair(index_, slot_) == end_pos(*buckets_));
return *this;
}

// Advance the iterator to the next item in the table, or to the end
// of the table. Returns the iterator at its old position.
const_cursor operator++(int) {
const_cursor old(*this);
++(*this);
return old;
}

size_type partition() const { return index_; }

private:
// cuckoohash_map's value

std::reference_wrapper<cuckoohash_map> map_;
size_type hp_;
buckets_t *buckets_;
// local value
bool good_ {false};
size_type index_ {0};
size_type slot_ {0};
value_type copyed_value_;

// Returns the position signifying the end of the table
static std::pair<size_type, size_type> end_pos(const buckets_t &buckets) {
return std::make_pair(buckets.size(), 0);
}

// The private constructor is used by cuckoohash_map to create
// iterators from scratch. If the given index_-slot_ pair is at the
// end of the table, or the given spot is occupied, stay. Otherwise,
// step forward to the next data item, or to the end of the table.
const_cursor(cuckoohash_map &map, size_type index,
size_type slot) noexcept
: map_(map), index_(index), slot_(slot) {
hp_ = map_.get().hashpower();
buckets_ = std::addressof(map_.get().buckets_);
if (std::make_pair(index_, slot_) != end_pos(*buckets_)) {
good_ = true;
if ((*buckets_)[index_].occupied(slot_)) {
fill_copyed_value();
} else {
operator++();
}
}
}
void fill_copyed_value() {
try {
auto locker = map_.get().lock_one(hp_, index_, normal_mode());
auto ref = (*buckets_)[index_].kvpair(slot_);
const_cast<key_type>(&copyed_value_.first) = ref.first;
copyed_value_.second = ref.second;
} catch (...) {
good_ = false;
}
}

friend class cuckoohash_map;
};

class key_cursor {
public:
key_cursor() {}
bool good() const { return good_; }
// Return true if the iterators are from the same locked table and
// location, false otherwise.
bool operator==(const key_cursor &it) const {
if (!good_ && !it.good_)
return true;
return buckets_ == it.buckets_ && index_ == it.index_ &&
slot_ == it.slot_;
}

bool operator!=(const key_cursor &it) const {
return !(operator==(it));
}

const key_type& operator*() const { return copyed_key_; }

// Advance the iterator to the next item in the table, or to the end
// of the table. Returns the iterator at its new position.
key_cursor &operator++() {
// 只需此处加锁即可
// Move forward until we get to a slot that is occupied, or we
// get to the end
++slot_;
for (; index_ < buckets_->size(); ++index_) {
for (; slot_ < slot_per_bucket(); ++slot_) {
if ((*buckets_)[index_].occupied(slot_)) {
fill_copyed_key();
return *this;
}
}
slot_ = 0;
}
assert(std::make_pair(index_, slot_) == end_pos(*buckets_));
return *this;
}

// Advance the iterator to the next item in the table, or to the end
// of the table. Returns the iterator at its old position.
key_cursor operator++(int) {
key_cursor old(*this);
++(*this);
return old;
}
size_type partition() const { return index_; }

private:
// cuckoohash_map's value

std::reference_wrapper<cuckoohash_map> map_;
size_type hp_;
buckets_t *buckets_;
// local value
bool good_ {false};
size_type index_ {0};
size_type slot_ {0};
key_type copyed_key_;

// Returns the position signifying the end of the table
static std::pair<size_type, size_type> end_pos(const buckets_t &buckets) {
return std::make_pair(buckets.size(), 0);
}

// The private constructor is used by cuckoohash_map to create
// iterators from scratch. If the given index_-slot_ pair is at the
// end of the table, or the given spot is occupied, stay. Otherwise,
// step forward to the next data item, or to the end of the table.
key_cursor(cuckoohash_map &map, size_type index,
size_type slot) noexcept
: map_(map), index_(index), slot_(slot) {
hp_ = map_.get().hashpower();
buckets_ = std::addressof(map_.get().buckets_);
if (std::make_pair(index_, slot_) != end_pos(*buckets_)) {
good_ = true;
if ((*buckets_)[index_].occupied(slot_)) {
fill_copyed_key();
} else {
operator++();
}
}
}
void fill_copyed_key() {
try {
auto locker = map_.get().lock_one(hp_, index_, normal_mode());
copyed_key_ = (*buckets_)[index_].key(slot_);
} catch (...) {
good_ = false;
}
}

friend class cuckoohash_map;
};

// // 注意 endpos = container.end()，每次调用 end 会有额外的成本
// auto cursor = container.begin();
// auto endpos = container.end();
// for (; cursor!= endpos; ++cursor) {
// // cursor->first;
// // cursor->second;
// }
// // 注意需要检查 cursor 的状态来判断是否完整遍历
// if (!cursor.good()) {
// // 遍历过程出现 rehash, 提前结束
// }
const_cursor begin() {
return const_cursor(*this, 0, 0);
}
const_cursor end() {
const auto end_pos = const_cursor::end_pos(buckets_);
return const_cursor(*this,
static_cast<size_type>(end_pos.first),
static_cast<size_type>(end_pos.second));
}

// // 注意 endpos = container.end()，每次调用 end 会有额外的成本
// auto key_cursor = container.key_begin();
// auto key_endpos = container.key_end();
// int key_count = 0;
// for (; key_cursor != key_endpos; ++key_cursor) {
// ++key_count;
// LOG_EVERY_N(INFO, 1000) << "fill key: " << *key_cursor;
// }
// // 注意需要检查 key_cursor 的状态来判断是否完整遍历
// if (!key_cursor.good()) {
// // 遍历过程出现 rehash, 提前结束
// }
key_cursor key_begin() {
return key_cursor(*this, 0, 0);
}
key_cursor key_end() {
const auto end_pos = key_cursor::end_pos(buckets_);
return key_cursor(*this,
static_cast<size_type>(end_pos.first),
static_cast<size_type>(end_pos.second));
}

#endif // _CUCKOOHASH_UNSAFE_ITER_HH