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). 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_NAMESPACE { 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: Contains(K key)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 Insert(K key,const V & value)39 void Insert(K key, const V& value) { 40 auto& bucket = table_[key % size]; 41 bucket.push_back({key, value}); 42 } 43 Delete(K key)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 Get(K key)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_NAMESPACE 68