]>
Commit | Line | Data |
---|---|---|
11fdf7f2 TL |
1 | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
2 | // This source code is licensed under both the GPLv2 (found in the | |
3 | // COPYING file in the root directory) and Apache 2.0 License | |
4 | // (found in the LICENSE.Apache file in the root directory). | |
7c673cae FG |
5 | // |
6 | ||
7 | #pragma once | |
8 | ||
9 | #include <algorithm> | |
10 | #include <array> | |
11 | #include <utility> | |
12 | ||
13 | #include "util/autovector.h" | |
14 | ||
15 | namespace rocksdb { | |
16 | ||
17 | // This is similar to std::unordered_map, except that it tries to avoid | |
18 | // allocating or deallocating memory as much as possible. With | |
19 | // std::unordered_map, an allocation/deallocation is made for every insertion | |
20 | // or deletion because of the requirement that iterators remain valid even | |
21 | // with insertions or deletions. This means that the hash chains will be | |
22 | // implemented as linked lists. | |
23 | // | |
24 | // This implementation uses autovector as hash chains insteads. | |
25 | // | |
26 | template <typename K, typename V, size_t size = 128> | |
27 | class HashMap { | |
28 | std::array<autovector<std::pair<K, V>, 1>, size> table_; | |
29 | ||
30 | public: | |
31 | bool Contains(K key) { | |
32 | auto& bucket = table_[key % size]; | |
33 | auto it = std::find_if( | |
34 | bucket.begin(), bucket.end(), | |
35 | [key](const std::pair<K, V>& p) { return p.first == key; }); | |
36 | return it != bucket.end(); | |
37 | } | |
38 | ||
39 | void Insert(K key, V value) { | |
40 | auto& bucket = table_[key % size]; | |
41 | bucket.push_back({key, value}); | |
42 | } | |
43 | ||
44 | void Delete(K key) { | |
45 | auto& bucket = table_[key % size]; | |
46 | auto it = std::find_if( | |
47 | bucket.begin(), bucket.end(), | |
48 | [key](const std::pair<K, V>& p) { return p.first == key; }); | |
49 | if (it != bucket.end()) { | |
50 | auto last = bucket.end() - 1; | |
51 | if (it != last) { | |
52 | *it = *last; | |
53 | } | |
54 | bucket.pop_back(); | |
55 | } | |
56 | } | |
57 | ||
58 | V& Get(K key) { | |
59 | auto& bucket = table_[key % size]; | |
60 | auto it = std::find_if( | |
61 | bucket.begin(), bucket.end(), | |
62 | [key](const std::pair<K, V>& p) { return p.first == key; }); | |
63 | return it->second; | |
64 | } | |
65 | }; | |
66 | ||
67 | } // namespace rocksdb |