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).
   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