19#include "mongo/util/assert_util.h"
20#include "mongo/util/debug_util.h"
23 template<
typename K_L,
typename K_S,
typename V,
typename H,
typename E,
typename C,
typename C_LS >
24 inline UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::Area::Area(
unsigned capacity,
26 : _capacity( capacity ),
27 _maxProbe( static_cast<unsigned>( capacity * maxProbeRatio ) ),
28 _entries( new Entry[_capacity] ) {
31 template<
typename K_L,
typename K_S,
typename V,
typename H,
typename E,
typename C,
typename C_LS >
32 inline UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::Area::Area(
const Area& other )
33 : _capacity( other._capacity ),
34 _maxProbe( other._maxProbe ),
35 _entries( new Entry[_capacity] ) {
36 for (
unsigned i = 0; i < _capacity; i++ ) {
37 _entries[i] = other._entries[i];
41 template<
typename K_L,
typename K_S,
typename V,
typename H,
typename E,
typename C,
typename C_LS >
42 inline int UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::Area::find(
46 const UnorderedFastKeyTable& sm )
const {
50 for (
unsigned probe = 0; probe < _maxProbe; probe++ ) {
51 unsigned pos = (hash + probe) % _capacity;
53 if ( ! _entries[pos].used ) {
55 if ( firstEmpty && *firstEmpty == -1 )
57 if ( ! _entries[pos].everUsed )
62 if ( _entries[pos].curHash != hash ) {
67 if ( ! sm._equals(key, sm._convertor( _entries[pos].data.first ) ) ) {
80 template<
typename K_L,
typename K_S,
typename V,
typename H,
typename E,
typename C,
typename C_LS >
81 inline bool UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::Area::transfer(
83 const UnorderedFastKeyTable& sm)
const {
84 for (
unsigned i = 0; i < _capacity; i++ ) {
85 if ( ! _entries[i].used )
89 int loc = newArea->find( sm._convertor( _entries[i].data.first ),
95 if ( firstEmpty < 0 ) {
99 newArea->_entries[firstEmpty] = _entries[i];
104 template<
typename K_L,
typename K_S,
typename V,
typename H,
typename E,
typename C,
typename C_LS >
106 unsigned startingCapacity,
107 double maxProbeRatio)
108 : _maxProbeRatio( maxProbeRatio ), _area( startingCapacity, maxProbeRatio ) {
112 template<
typename K_L,
typename K_S,
typename V,
typename H,
typename E,
typename C,
typename C_LS >
115 : _size( other._size ),
116 _maxProbeRatio( other._maxProbeRatio ),
117 _area( other._area ),
118 _hash( other._hash ),
119 _equals( other._equals ),
120 _convertor( other._convertor ),
121 _convertorOther( other._convertorOther ) {
124 template<
typename K_L,
typename K_S,
typename V,
typename H,
typename E,
typename C,
typename C_LS >
127 out->_maxProbeRatio = _maxProbeRatio;
129 out->_area.swap( &x );
132 template<
typename K_L,
typename K_S,
typename V,
typename H,
typename E,
typename C,
typename C_LS >
133 inline V& UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::get(
const K_L& key ) {
135 const size_t hash = _hash( key );
137 for (
int numGrowTries = 0; numGrowTries < 5; numGrowTries++ ) {
139 int pos = _area.find( key, hash, &firstEmpty, *
this );
141 return _area._entries[pos].data.second;
145 if ( firstEmpty >= 0 ) {
147 _area._entries[firstEmpty].used =
true;
148 _area._entries[firstEmpty].everUsed =
true;
149 _area._entries[firstEmpty].curHash = hash;
150 _area._entries[firstEmpty].data.first = _convertorOther(key);
151 return _area._entries[firstEmpty].data.second;
157 msgasserted( 16471,
"UnorderedFastKeyTable couldn't add entry after growing many times" );
160 template<
typename K_L,
typename K_S,
typename V,
typename H,
typename E,
typename C,
typename C_LS >
163 const size_t hash = _hash( key );
164 int pos = _area.find( key, hash, NULL, *
this );
170 _area._entries[pos].used =
false;
171 _area._entries[pos].data.second = V();
175 template<
typename K_L,
typename K_S,
typename V,
typename H,
typename E,
typename C,
typename C_LS >
177 dassert(it._position >= 0);
178 dassert(it._area == &_area);
181 _area._entries[it._position].used =
false;
182 _area._entries[it._position].data.second = V();
185 template<
typename K_L,
typename K_S,
typename V,
typename H,
typename E,
typename C,
typename C_LS >
187 unsigned capacity = _area._capacity;
188 for (
int numGrowTries = 0; numGrowTries < 5; numGrowTries++ ) {
190 Area newArea( capacity, _maxProbeRatio );
191 bool success = _area.transfer( &newArea, *
this );
195 _area.swap( &newArea );
199 "UnorderedFastKeyTable::_grow couldn't add entry after growing many times" );
202 template<
typename K_L,
typename K_S,
typename V,
typename H,
typename E,
typename C,
typename C_LS >
207 int pos = _area.find( key, _hash(key), 0, *
this );
213 template<
typename K_L,
typename K_S,
typename V,
typename H,
typename E,
typename C,
typename C_LS >
216 return const_iterator();
219 template<
typename K_L,
typename K_S,
typename V,
typename H,
typename E,
typename C,
typename C_LS >
220 inline typename UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::const_iterator
221 UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::begin()
const {
222 return const_iterator( &_area );
Definition unordered_fast_key_table.h:121
Definition unordered_fast_key_table.h:41
UnorderedFastKeyTable(unsigned startingCapacity=DEFAULT_STARTING_CAPACITY, double maxProbeRatio=0.05)
Definition unordered_fast_key_table_internal.h:105
const_iterator find(const K_L &key) const
Definition unordered_fast_key_table_internal.h:204
size_t erase(const K_L &key)
Definition unordered_fast_key_table_internal.h:161
the main MongoDB namespace
Definition bulk_operation_builder.h:24