Packages
rocksdb
2.1.0
3.1.1
3.1.0
3.0.0
2.6.2
2.6.1
retired
2.6.0
retired
2.5.0
2.4.1
2.4.0
2.3.0
2.2.0
2.1.0
2.0.0
1.9.0
1.8.0
1.7.0
1.6.0
1.5.1
1.5.0
1.4.0
1.3.2
1.3.1
1.3.0
1.2.0
1.1.1
1.1.0
1.0.0
0.26.2
0.26.1
0.26.0
0.25.0
0.24.0
0.23.3
0.23.2
0.23.1
0.23.0
0.22.0
0.21.0
0.20.1
0.20.0
0.19.0
0.18.0
0.17.0
0.16.0
0.15.0
0.14.0
0.13.1
0.13.0
0.12.0
0.11.0
0.10.0
0.9.1
0.9.0
0.8.2
0.8.1
0.8.0
0.7.1
0.7.0
0.6.4
0.6.3
0.6.2
0.6.1
0.6.0
RocksDB for Erlang
Current section
Files
Jump to
Current section
Files
deps/rocksdb/util/hash_map.h
// Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
// This source code is licensed under both the GPLv2 (found in the
// COPYING file in the root directory) and Apache 2.0 License
// (found in the LICENSE.Apache file in the root directory).
//
#pragma once
#include <algorithm>
#include <array>
#include <utility>
#include "util/autovector.h"
namespace ROCKSDB_NAMESPACE {
// This is similar to std::unordered_map, except that it tries to avoid
// allocating or deallocating memory as much as possible. With
// std::unordered_map, an allocation/deallocation is made for every insertion
// or deletion because of the requirement that iterators remain valid even
// with insertions or deletions. This means that the hash chains will be
// implemented as linked lists.
//
// This implementation uses autovector as hash chains insteads.
//
template <typename K, typename V, size_t size = 128>
class HashMap {
std::array<autovector<std::pair<K, V>, 1>, size> table_;
public:
bool Contains(K key) {
auto& bucket = table_[key % size];
auto it = std::find_if(
bucket.begin(), bucket.end(),
[key](const std::pair<K, V>& p) { return p.first == key; });
return it != bucket.end();
}
void Insert(K key, const V& value) {
auto& bucket = table_[key % size];
bucket.push_back({key, value});
}
void Delete(K key) {
auto& bucket = table_[key % size];
auto it = std::find_if(
bucket.begin(), bucket.end(),
[key](const std::pair<K, V>& p) { return p.first == key; });
if (it != bucket.end()) {
auto last = bucket.end() - 1;
if (it != last) {
*it = *last;
}
bucket.pop_back();
}
}
V& Get(K key) {
auto& bucket = table_[key % size];
auto it = std::find_if(
bucket.begin(), bucket.end(),
[key](const std::pair<K, V>& p) { return p.first == key; });
return it->second;
}
};
} // namespace ROCKSDB_NAMESPACE