MongoDB  2.7.0
unordered_fast_key_table_internal.h
1 // unordered_fast_key_table_internal.h
2 
3 
4 /* Copyright 2012 10gen Inc.
5  *
6  * Licensed under the Apache License, Version 2.0 (the "License");
7  * you may not use this file except in compliance with the License.
8  * You may obtain a copy of the License at
9  *
10  * http://www.apache.org/licenses/LICENSE-2.0
11  *
12  * Unless required by applicable law or agreed to in writing, software
13  * distributed under the License is distributed on an "AS IS" BASIS,
14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15  * See the License for the specific language governing permissions and
16  * limitations under the License.
17  */
18 
19 #include "mongo/util/assert_util.h"
20 
21 namespace mongo {
22  template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS >
23  inline UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::Area::Area(unsigned capacity,
24  double maxProbeRatio)
25  : _capacity( capacity ),
26  _maxProbe( static_cast<unsigned>( capacity * maxProbeRatio ) ),
27  _entries( new Entry[_capacity] ) {
28  }
29 
30  template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS >
31  inline UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::Area::Area(const Area& other )
32  : _capacity( other._capacity ),
33  _maxProbe( other._maxProbe ),
34  _entries( new Entry[_capacity] ) {
35  for ( unsigned i = 0; i < _capacity; i++ ) {
36  _entries[i] = other._entries[i];
37  }
38  }
39 
40  template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS >
41  inline int UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::Area::find(
42  const K_L& key,
43  size_t hash,
44  int* firstEmpty,
45  const UnorderedFastKeyTable& sm ) const {
46  if ( firstEmpty )
47  *firstEmpty = -1;
48 
49  for ( unsigned probe = 0; probe < _maxProbe; probe++ ) {
50  unsigned pos = (hash + probe) % _capacity;
51 
52  if ( ! _entries[pos].used ) {
53  // space is empty
54  if ( firstEmpty && *firstEmpty == -1 )
55  *firstEmpty = pos;
56  if ( ! _entries[pos].everUsed )
57  return -1;
58  continue;
59  }
60 
61  if ( _entries[pos].curHash != hash ) {
62  // space has something else
63  continue;
64  }
65 
66  if ( ! sm._equals(key, sm._convertor( _entries[pos].data.first ) ) ) {
67  // hashes match
68  // strings are not equals
69  continue;
70  }
71 
72  // hashes and strings are equal
73  // yay!
74  return pos;
75  }
76  return -1;
77  }
78 
79  template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS >
80  inline bool UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::Area::transfer(
81  Area* newArea,
82  const UnorderedFastKeyTable& sm) const {
83  for ( unsigned i = 0; i < _capacity; i++ ) {
84  if ( ! _entries[i].used )
85  continue;
86 
87  int firstEmpty = -1;
88  int loc = newArea->find( sm._convertor( _entries[i].data.first ),
89  _entries[i].curHash,
90  &firstEmpty,
91  sm );
92 
93  verify( loc == -1 );
94  if ( firstEmpty < 0 ) {
95  return false;
96  }
97 
98  newArea->_entries[firstEmpty] = _entries[i];
99  }
100  return true;
101  }
102 
103  template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS >
105  unsigned startingCapacity,
106  double maxProbeRatio)
107  : _maxProbeRatio( maxProbeRatio ), _area( startingCapacity, maxProbeRatio ) {
108  _size = 0;
109  }
110 
111  template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS >
113  const UnorderedFastKeyTable& other )
114  : _size( other._size ),
115  _maxProbeRatio( other._maxProbeRatio ),
116  _area( other._area ),
117  _hash( other._hash ),
118  _equals( other._equals ),
119  _convertor( other._convertor ),
120  _convertorOther( other._convertorOther ) {
121  }
122 
123  template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS >
124  inline void UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::copyTo( UnorderedFastKeyTable* out ) const {
125  out->_size = _size;
126  out->_maxProbeRatio = _maxProbeRatio;
127  Area x( _area );
128  out->_area.swap( &x );
129  }
130 
131  template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS >
132  inline V& UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::get( const K_L& key ) {
133 
134  const size_t hash = _hash( key );
135 
136  for ( int numGrowTries = 0; numGrowTries < 5; numGrowTries++ ) {
137  int firstEmpty = -1;
138  int pos = _area.find( key, hash, &firstEmpty, *this );
139  if ( pos >= 0 )
140  return _area._entries[pos].data.second;
141 
142  // key not in map
143  // need to add
144  if ( firstEmpty >= 0 ) {
145  _size++;
146  _area._entries[firstEmpty].used = true;
147  _area._entries[firstEmpty].everUsed = true;
148  _area._entries[firstEmpty].curHash = hash;
149  _area._entries[firstEmpty].data.first = _convertorOther(key);
150  return _area._entries[firstEmpty].data.second;
151  }
152 
153  // no space left in map
154  _grow();
155  }
156  msgasserted( 16471, "UnorderedFastKeyTable couldn't add entry after growing many times" );
157  }
158 
159  template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS >
161 
162  const size_t hash = _hash( key );
163  int pos = _area.find( key, hash, NULL, *this );
164 
165  if ( pos < 0 )
166  return 0;
167 
168  _area._entries[pos].used = false;
169  _area._entries[pos].data.second = V();
170  return 1;
171  }
172 
173  template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS >
175  dassert(it._position >= 0);
176  dassert(it._area == &_area);
177 
178  _area._entries[it._position].used = false;
179  _area._entries[it._position].data.second = V();
180  }
181 
182  template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS >
183  inline void UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::_grow() {
184  unsigned capacity = _area._capacity;
185  for ( int numGrowTries = 0; numGrowTries < 5; numGrowTries++ ) {
186  capacity *= 2;
187  Area newArea( capacity, _maxProbeRatio );
188  bool success = _area.transfer( &newArea, *this );
189  if ( !success ) {
190  continue;
191  }
192  _area.swap( &newArea );
193  return;
194  }
195  msgasserted( 16845,
196  "UnorderedFastKeyTable::_grow couldn't add entry after growing many times" );
197  }
198 
199  template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS >
200  inline typename UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::const_iterator
202  if ( _size == 0 )
203  return const_iterator();
204  int pos = _area.find( key, _hash(key), 0, *this );
205  if ( pos < 0 )
206  return const_iterator();
207  return const_iterator( &_area, pos );
208  }
209 
210  template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS >
213  return const_iterator();
214  }
215 
216  template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS >
217  inline typename UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::const_iterator
218  UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::begin() const {
219  return const_iterator( &_area );
220  }
221 }
const_iterator find(const K_L &key) const
Definition: unordered_fast_key_table_internal.h:201
LogstreamBuilder out()
Synonym for log().
Definition: log.h:79
size_t erase(const K_L &key)
Definition: unordered_fast_key_table_internal.h:160
UnorderedFastKeyTable(unsigned startingCapacity=DEFAULT_STARTING_CAPACITY, double maxProbeRatio=0.05)
Definition: unordered_fast_key_table_internal.h:104
Definition: unordered_fast_key_table.h:41
Definition: unordered_fast_key_table.h:121