]>
git.proxmox.com Git - ceph.git/blob - ceph/src/rocksdb/util/hash_map.h
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).
13 #include "util/autovector.h"
15 namespace ROCKSDB_NAMESPACE
{
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.
24 // This implementation uses autovector as hash chains insteads.
26 template <typename K
, typename V
, size_t size
= 128>
28 std::array
<autovector
<std::pair
<K
, V
>, 1>, size
> table_
;
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();
39 void Insert(K key
, const V
& value
) {
40 auto& bucket
= table_
[key
% size
];
41 bucket
.push_back({key
, value
});
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;
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
; });
67 } // namespace ROCKSDB_NAMESPACE