// Advance the iterator to the next item in the table, or to the end
// of the table. Returns the iterator at its new position.
constcursor &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_perbucket(); ++slot) {
if ((buckets)[index].occupied(slot_)) {
fill_copyed_value();
return this;
}
}
slot_ = 0;
}
assert(std::makepair(index, slot_) == endpos(*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;
}
sizetype partition() const { return index; }
private:
// cuckoohash_map's value
std::reference_wrapper map_;
sizetype hp;
bucketst *buckets;
// local value
bool good_ {false};
sizetype index {0};
sizetype slot {0};
value_type copyedvalue;
// 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);
}
// Advance the iterator to the next item in the table, or to the end
// of the table. Returns the iterator at its new position.
keycursor &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_perbucket(); ++slot) {
if ((buckets)[index].occupied(slot_)) {
fill_copyed_key();
return this;
}
}
slot_ = 0;
}
assert(std::makepair(index, slot_) == endpos(*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;
}
sizetype partition() const { return index; }
private:
// cuckoohash_map's value
std::reference_wrapper map_;
sizetype hp;
bucketst *buckets;
// local value
bool good_ {false};
sizetype index {0};
sizetype slot {0};
key_type copyedkey;
// 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 cuckoohashmap 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,
sizetype slot) noexcept
: map(map), index(index), slot(slot) {
hp = map.get().hashpower();
buckets = std::addressof(map.get().buckets_);
if (std::makepair(index, slot_) != endpos(*buckets)) {
good = true;
if ((*buckets)[index].occupied(slot)) {
fill_copyed_key();
} else {
operator++();
}
}
}
void fill_copyedkey() {
try {
auto locker = map.get().lockone(hp, index_, normal_mode());
copyedkey = (*buckets)[index].key(slot);
} catch (...) {
good = false;
}
}
will you add this feature?
ifndef _CUCKOOHASH_UNSAFE_ITER_HH
define _CUCKOOHASH_UNSAFE_ITER_HH
// inner class of cuckoohash_map class const_cursor { public: constcursor() { } bool good() const { return good; } // Return true if the iterators are from the same locked table and // location, false otherwise. bool operator==(const constcursor &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 ©edvalue; }
// Advance the iterator to the next item in the table, or to the end // of the table. Returns the iterator at its new position. constcursor &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_perbucket(); ++slot) { if ((buckets)[index].occupied(slot_)) { fill_copyed_value(); return this; } } slot_ = 0; } assert(std::makepair(index, slot_) == endpos(*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; }
sizetype partition() const { return index; }
private: // cuckoohash_map's value
std::reference_wrapper map_;
sizetype hp;
bucketst *buckets;
// local value
bool good_ {false};
sizetype index {0};
sizetype slot {0};
value_type copyedvalue;
// 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 cuckoohashmap 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, sizetype slot) noexcept : map(map), index(index), slot(slot) { hp = map.get().hashpower(); buckets = std::addressof(map.get().buckets_); if (std::makepair(index, slot_) != endpos(*buckets)) { good = true; if ((*buckets)[index].occupied(slot)) { fill_copyed_value(); } else { operator++(); } } } void fill_copyedvalue() { try { auto locker = map.get().lockone(hp, index_, normalmode()); auto ref = (*buckets)[index].kvpair(slot); const_cast<key_type>(©edvalue.first) = ref.first; copyedvalue.second = ref.second; } catch (...) { good_ = false; } }
friend class cuckoohash_map; };
class key_cursor { public: keycursor() {} bool good() const { return good; } // Return true if the iterators are from the same locked table and // location, false otherwise. bool operator==(const keycursor &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 copyedkey; }
// Advance the iterator to the next item in the table, or to the end // of the table. Returns the iterator at its new position. keycursor &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_perbucket(); ++slot) { if ((buckets)[index].occupied(slot_)) { fill_copyed_key(); return this; } } slot_ = 0; } assert(std::makepair(index, slot_) == endpos(*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; } sizetype partition() const { return index; }
private: // cuckoohash_map's value
std::reference_wrapper map_;
sizetype hp;
bucketst *buckets;
// local value
bool good_ {false};
sizetype index {0};
sizetype slot {0};
key_type copyedkey;
// 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 cuckoohashmap 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, sizetype slot) noexcept : map(map), index(index), slot(slot) { hp = map.get().hashpower(); buckets = std::addressof(map.get().buckets_); if (std::makepair(index, slot_) != endpos(*buckets)) { good = true; if ((*buckets)[index].occupied(slot)) { fill_copyed_key(); } else { operator++(); } } } void fill_copyedkey() { try { auto locker = map.get().lockone(hp, index_, normal_mode()); copyedkey = (*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::endpos(buckets); return const_cursor(this, static_cast(end_pos.first),
static_cast(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::endpos(buckets); return key_cursor(*this, static_cast(end_pos.first),
static_cast(end_pos.second));
}
endif // _CUCKOOHASH_UNSAFE_ITER_HH