1/*
2 * Copyright (C) 2016 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#ifndef Map_h
27#define Map_h
28
29#include "BInline.h"
30#include "Sizes.h"
31#include "Vector.h"
32
33namespace bmalloc {
34
35class SmallPage;
36
37template<typename Key, typename Value, typename Hash> class Map {
38 static_assert(std::is_trivially_destructible<Key>::value, "Map must have a trivial destructor.");
39 static_assert(std::is_trivially_destructible<Value>::value, "Map must have a trivial destructor.");
40public:
41 struct Bucket {
42 Key key;
43 Value value;
44 };
45
46 size_t size() { return m_keyCount; }
47 size_t capacity() { return m_table.size(); }
48
49 // key must be in the map.
50 Value& get(const Key& key)
51 {
52 auto& bucket = find(key, [&](const Bucket& bucket) { return bucket.key == key; });
53 return bucket.value;
54 }
55
56 void set(const Key& key, const Value& value)
57 {
58 if (shouldGrow())
59 rehash();
60
61 auto& bucket = find(key, [&](const Bucket& bucket) { return !bucket.key || bucket.key == key; });
62 if (!bucket.key) {
63 bucket.key = key;
64 ++m_keyCount;
65 }
66 bucket.value = value;
67 }
68
69 // key must be in the map.
70 Value remove(const Key& key)
71 {
72 if (shouldShrink())
73 rehash();
74
75 auto& bucket = find(key, [&](const Bucket& bucket) { return bucket.key == key; });
76 Value value = bucket.value;
77 bucket.key = Key();
78 --m_keyCount;
79 return value;
80 }
81
82private:
83 static const unsigned minCapacity = 16;
84 static const unsigned maxLoad = 2;
85 static const unsigned rehashLoad = 4;
86 static const unsigned minLoad = 8;
87
88 bool shouldGrow() { return m_keyCount * maxLoad >= capacity(); }
89 bool shouldShrink() { return m_keyCount * minLoad <= capacity() && capacity() > minCapacity; }
90
91 void rehash();
92
93 template<typename Predicate>
94 Bucket& find(const Key& key, const Predicate& predicate)
95 {
96 for (unsigned h = Hash::hash(key); ; ++h) {
97 unsigned i = h & m_tableMask;
98
99 Bucket& bucket = m_table[i];
100 if (predicate(bucket))
101 return bucket;
102 }
103 }
104
105 unsigned m_keyCount;
106 unsigned m_tableMask;
107 Vector<Bucket> m_table;
108};
109
110template<typename Key, typename Value, typename Hash>
111void Map<Key, Value, Hash>::rehash()
112{
113 auto oldTable = std::move(m_table);
114
115 size_t newCapacity = std::max(minCapacity, m_keyCount * rehashLoad);
116 m_table.grow(newCapacity);
117
118 m_keyCount = 0;
119 m_tableMask = newCapacity - 1;
120
121 for (auto& bucket : oldTable) {
122 if (!bucket.key)
123 continue;
124
125 BASSERT(!shouldGrow());
126 set(bucket.key, bucket.value);
127 }
128}
129
130template<typename Key, typename Value, typename Hash> const unsigned Map<Key, Value, Hash>::minCapacity;
131
132} // namespace bmalloc
133
134#endif // Map_h
135