1 /*
2  * Copyright (C) 2014 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef ART_LIBARTBASE_BASE_HASH_MAP_H_
18 #define ART_LIBARTBASE_BASE_HASH_MAP_H_
19 
20 #include <utility>
21 
22 #include "hash_set.h"
23 
24 namespace art {
25 
26 template <typename Key, typename Value, typename HashFn>
27 class HashMapHashWrapper {
28  public:
HashMapHashWrapper()29   HashMapHashWrapper() : hash_fn_(HashFn()) {}
HashMapHashWrapper(const HashFn & hashfn)30   explicit HashMapHashWrapper(const HashFn& hashfn) : hash_fn_(hashfn) {}
operator()31   size_t operator()(const Key& key) const {
32     return hash_fn_(key);
33   }
34 
operator()35   size_t operator()(const std::pair<Key, Value>& pair) const {
36     return hash_fn_(pair.first);
37   }
38 
39  private:
40   HashFn hash_fn_;
41 };
42 
43 template <typename Key, typename Value, typename PredFn>
44 class HashMapPredWrapper {
45  public:
HashMapPredWrapper()46   HashMapPredWrapper() : pred_fn_(PredFn()) {}
HashMapPredWrapper(const PredFn & predfn)47   explicit HashMapPredWrapper(const PredFn& predfn) : pred_fn_(predfn) {}
operator()48   bool operator()(const std::pair<Key, Value>& a, const std::pair<Key, Value>& b) const {
49     return pred_fn_(a.first, b.first);
50   }
51 
52   template <typename Element>
operator()53   bool operator()(const std::pair<Key, Value>& a, const Element& element) const {
54     return pred_fn_(a.first, element);
55   }
56 
57  private:
58   PredFn pred_fn_;
59 };
60 
61 template <typename Key, typename Value>
62 class DefaultMapEmptyFn {
63  public:
MakeEmpty(std::pair<Key,Value> & item)64   void MakeEmpty(std::pair<Key, Value>& item) const {
65     item = std::pair<Key, Value>();
66   }
IsEmpty(const std::pair<Key,Value> & item)67   bool IsEmpty(const std::pair<Key, Value>& item) const {
68     return item.first == Key();
69   }
70 };
71 
72 template <class Key,
73           class Value,
74           class EmptyFn = DefaultMapEmptyFn<Key, Value>,
75           class HashFn = DefaultHashFn<Key>,
76           class Pred = DefaultPred<Key>,
77           class Alloc = std::allocator<std::pair<Key, Value>>>
78 class HashMap : public HashSet<std::pair<Key, Value>,
79                                EmptyFn,
80                                HashMapHashWrapper<Key, Value, HashFn>,
81                                HashMapPredWrapper<Key, Value, Pred>,
82                                Alloc> {
83  private:
84   using Base = HashSet<std::pair<Key, Value>,
85                        EmptyFn,
86                        HashMapHashWrapper<Key, Value, HashFn>,
87                        HashMapPredWrapper<Key, Value, Pred>,
88                        Alloc>;
89 
90  public:
91   // Inherit constructors.
92   using Base::Base;
HashMap(HashFn hashfn,Pred pred)93   HashMap(HashFn hashfn, Pred pred)
94       : Base(HashMapHashWrapper<Key, Value, HashFn>(hashfn),
95              HashMapPredWrapper<Key, Value, Pred>(pred)) {}
96 
97   // Used to insert a new mapping.
Overwrite(const Key & k,const Value & v)98   typename Base::iterator Overwrite(const Key& k, const Value& v) {
99     auto res = Base::insert({ k, v }).first;
100     *res = { k, v };
101     return res;
102   }
103 };
104 
105 }  // namespace art
106 
107 #endif  // ART_LIBARTBASE_BASE_HASH_MAP_H_
108