1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
|
/*
* Copyright 2014 Google Inc. All rights reserved.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef SEMISTATIC_MAP_H
#define SEMISTATIC_MAP_H
#include <fruit/impl/data_structures/fixed_size_vector.h>
#include "arena_allocator.h"
#include "memory_pool.h"
#include <climits>
#include <cstdint>
#include <limits>
#include <vector>
namespace fruit {
namespace impl {
/**
* Provides a subset of the interface of std::map, and also has these additional assumptions:
* - Key must be default constructible and trivially copyable
* - Value must be default constructible and trivially copyable
*
* Also, while insertion of elements after construction is supported, inserting more than O(1) elements
* after construction will raise the cost of any further lookups to more than O(1).
*/
template <typename Key, typename Value>
class SemistaticMap {
private:
using Unsigned = std::uintptr_t;
using NumBits = unsigned char;
using value_type = std::pair<Key, Value>;
static constexpr unsigned char beta = 4;
static_assert(
std::numeric_limits<NumBits>::max() >= sizeof(Unsigned) * CHAR_BIT,
"An unsigned char is not enough to contain the number of bits in your platform. Please report this issue.");
struct HashFunction {
Unsigned a;
NumBits shift; // shift==(sizeof(Unsigned)*CHAR_BIT - num_bits)
HashFunction();
Unsigned hash(Unsigned x) const;
};
static NumBits pickNumBits(std::size_t n);
struct CandidateValuesRange {
value_type* begin;
value_type* end;
};
HashFunction hash_function;
// Given a key x, if p=lookup_table[hash_function.hash(x)] the candidate places for x are [p.first, p.second). These
// pointers
// point to the values[] vector, but it might be either the one of this object or the one of an object that was
// shallow-copied
// into this one.
FixedSizeVector<CandidateValuesRange> lookup_table;
FixedSizeVector<value_type> values;
Unsigned hash(const Key& key) const;
// Inserts a range [elems_begin, elems_end) of new (key,value) pairs with hash h. The keys must not exist in the map.
// Before calling this, ensure that the capacity of `values' is sufficient to contain the new values without
// re-allocating.
void insert(std::size_t h, const value_type* elems_begin, const value_type* elems_end);
public:
// Constructs an *invalid* map (as if this map was just moved from).
SemistaticMap() = default;
/**
* Iter must be a forward iterator with value type std::pair<Key, Value>.
*
* The MemoryPool is only used during construction, the constructed object *can* outlive the memory pool.
*/
template <typename Iter>
SemistaticMap(Iter begin, Iter end, std::size_t num_values, MemoryPool& memory_pool);
// Creates a shallow copy of `map' with the additional elements in new_elements.
// The keys in new_elements must be unique and must not be present in `map'.
// The new map will share data with `map', so must be destroyed before `map' is destroyed.
// NOTE: If more than O(1) elements are added, calls to at() and find() on the result will *not* be O(1).
// This is O(new_elements.size()*log(new_elements.size())).
SemistaticMap(const SemistaticMap<Key, Value>& map,
std::vector<value_type, ArenaAllocator<value_type>>&& new_elements);
SemistaticMap(SemistaticMap&&) noexcept = default;
SemistaticMap(const SemistaticMap&) = delete;
~SemistaticMap();
SemistaticMap& operator=(SemistaticMap&&) noexcept = default;
SemistaticMap& operator=(const SemistaticMap&) = delete;
// Precondition: `key' must exist in the map.
// Unlike std::map::at(), this yields undefined behavior if the precondition isn't satisfied (instead of throwing).
const Value& at(Key key) const;
// Prefer using at() when possible, this is slightly slower.
// Returns nullptr if the key was not found.
const Value* find(Key key) const;
};
} // namespace impl
} // namespace fruit
#include <fruit/impl/data_structures/semistatic_map.defn.h>
// semistatic_map.templates.h is NOT included here to reduce the transitive includes. Include it when needed (in .cpp
// files).
#endif // SEMISTATIC_MAP_H
|
