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