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 static_assert( 50 std::numeric_limits<NumBits>::max() >= sizeof(Unsigned) * CHAR_BIT, 51 "An unsigned char is not enough to contain the number of bits in your platform. Please report this issue."); 52 53 struct HashFunction { 54 Unsigned a; 55 NumBits shift; // shift==(sizeof(Unsigned)*CHAR_BIT - num_bits) 56 57 HashFunction(); 58 59 Unsigned hash(Unsigned x) const; 60 }; 61 62 static NumBits pickNumBits(std::size_t n); 63 64 struct CandidateValuesRange { 65 value_type* begin; 66 value_type* end; 67 }; 68 69 HashFunction hash_function; 70 // Given a key x, if p=lookup_table[hash_function.hash(x)] the candidate places for x are [p.first, p.second). These 71 // pointers 72 // point to the values[] vector, but it might be either the one of this object or the one of an object that was 73 // shallow-copied 74 // into this one. 75 FixedSizeVector<CandidateValuesRange> lookup_table; 76 FixedSizeVector<value_type> values; 77 78 Unsigned hash(const Key& key) const; 79 80 // Inserts a range [elems_begin, elems_end) of new (key,value) pairs with hash h. The keys must not exist in the map. 81 // Before calling this, ensure that the capacity of `values' is sufficient to contain the new values without 82 // re-allocating. 83 void insert(std::size_t h, const value_type* elems_begin, const value_type* elems_end); 84 85 public: 86 // Constructs an *invalid* map (as if this map was just moved from). 87 SemistaticMap() = default; 88 89 /** 90 * Iter must be a forward iterator with value type std::pair<Key, Value>. 91 * 92 * The MemoryPool is only used during construction, the constructed object *can* outlive the memory pool. 93 */ 94 template <typename Iter> 95 SemistaticMap(Iter begin, Iter end, std::size_t num_values, MemoryPool& memory_pool); 96 97 // Creates a shallow copy of `map' with the additional elements in new_elements. 98 // The keys in new_elements must be unique and must not be present in `map'. 99 // The new map will share data with `map', so must be destroyed before `map' is destroyed. 100 // NOTE: If more than O(1) elements are added, calls to at() and find() on the result will *not* be O(1). 101 // This is O(new_elements.size()*log(new_elements.size())). 102 SemistaticMap(const SemistaticMap<Key, Value>& map, 103 std::vector<value_type, ArenaAllocator<value_type>>&& new_elements); 104 105 SemistaticMap(SemistaticMap&&) = default; 106 SemistaticMap(const SemistaticMap&) = delete; 107 108 ~SemistaticMap(); 109 110 SemistaticMap& operator=(SemistaticMap&&) = default; 111 SemistaticMap& operator=(const SemistaticMap&) = delete; 112 113 // Precondition: `key' must exist in the map. 114 // Unlike std::map::at(), this yields undefined behavior if the precondition isn't satisfied (instead of throwing). 115 const Value& at(Key key) const; 116 117 // Prefer using at() when possible, this is slightly slower. 118 // Returns nullptr if the key was not found. 119 const Value* find(Key key) const; 120 }; 121 122 } // namespace impl 123 } // namespace fruit 124 125 #include <fruit/impl/data_structures/semistatic_map.defn.h> 126 127 // semistatic_map.templates.h is NOT included here to reduce the transitive includes. Include it when needed (in .cpp 128 // files). 129 130 #endif // SEMISTATIC_MAP_H 131