MongoDB  2.7.0
unordered_fast_key_table.h
1 // unordered_fast_key_table.h
2 
3 /* Copyright 2012 10gen Inc.
4  *
5  * Licensed under the Apache License, Version 2.0 (the "License");
6  * you may not use this file except in compliance with the License.
7  * You may obtain a copy of the License at
8  *
9  * http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  */
17 
18 #pragma once
19 
20 #include <boost/smart_ptr/scoped_array.hpp>
21 
22 #include "mongo/base/disallow_copying.h"
23 
24 namespace mongo {
25 
26  template<typename K_L, typename K_S>
28  K_S operator()( const K_L& a ) const {
29  return K_S(a);
30  }
31  };
32 
33  template< typename K_L, // key lookup
34  typename K_S, // key storage
35  typename V, // value
36  typename H , // hash of K_L
37  typename E, // equal of K_L
38  typename C, // convertor from K_S -> K_L
39  typename C_LS=UnorderedFastKeyTable_LS_C<K_L,K_S> // convertor from K_L -> K_S
40  >
42  public:
43  typedef std::pair<K_S, V> value_type;
44  typedef K_L key_type;
45  typedef V mapped_type;
46 
47  private:
48  struct Entry {
49  Entry()
50  : used( false ), everUsed( false ) {
51  }
52 
53  bool used;
54  bool everUsed;
55  size_t curHash;
56  value_type data;
57  };
58 
59  struct Area {
60  Area( unsigned capacity, double maxProbeRatio );
61  Area( const Area& other );
62 
63  int find( const K_L& key, size_t hash, int* firstEmpty, const UnorderedFastKeyTable& sm ) const;
64 
65  bool transfer( Area* newArea, const UnorderedFastKeyTable& sm ) const;
66 
67  void swap( Area* other ) {
68  using std::swap;
69  swap( _capacity, other->_capacity );
70  swap( _maxProbe, other->_maxProbe );
71  swap( _entries, other->_entries );
72  }
73 
74  unsigned _capacity;
75  unsigned _maxProbe;
76  boost::scoped_array<Entry> _entries;
77  };
78 
79  public:
80  static const unsigned DEFAULT_STARTING_CAPACITY = 20;
81 
88  UnorderedFastKeyTable( unsigned startingCapacity = DEFAULT_STARTING_CAPACITY,
89  double maxProbeRatio = 0.05 );
90 
92 
93  UnorderedFastKeyTable& operator=( const UnorderedFastKeyTable& other ) {
94  other.copyTo( this );
95  return *this;
96  }
97 
98  void copyTo( UnorderedFastKeyTable* out ) const;
99 
103  size_t size() const { return _size; }
104 
105  bool empty() const { return _size == 0; }
106 
107  /*
108  * @return storage space
109  */
110  size_t capacity() const { return _area._capacity; }
111 
112  V& operator[]( const K_L& key ) { return get( key ); }
113 
114  V& get( const K_L& key );
115 
119  size_t erase( const K_L& key );
120 
122  friend class UnorderedFastKeyTable;
123 
124  public:
125  const_iterator() { _position = -1; }
126  const_iterator( const Area* area ) {
127  _area = area;
128  _position = 0;
129  _max = _area->_capacity - 1;
130  _skip();
131  }
132  const_iterator( const Area* area, int pos ) {
133  _area = area;
134  _position = pos;
135  _max = pos;
136  }
137 
138  const value_type* operator->() const { return &_area->_entries[_position].data; }
139 
140  const_iterator operator++() {
141  if ( _position < 0 )
142  return *this;
143  _position++;
144  if ( _position > _max )
145  _position = -1;
146  else
147  _skip();
148  return *this;
149  }
150 
151  bool operator==( const const_iterator& other ) const {
152  return _position == other._position;
153  }
154  bool operator!=( const const_iterator& other ) const {
155  return _position != other._position;
156  }
157 
158  private:
159 
160  void _skip() {
161  while ( true ) {
162  if ( _area->_entries[_position].used )
163  break;
164  if ( _position >= _max ) {
165  _position = -1;
166  break;
167  }
168  ++_position;
169  }
170  }
171 
172  const Area* _area;
173  int _position;
174  int _max; // inclusive
175  };
176 
177  void erase( const_iterator it );
178 
182  const_iterator find( const K_L& key ) const;
183 
184  const_iterator begin() const;
185 
186  const_iterator end() const;
187 
188  private:
189  /*
190  * @param firstEmpty, if we return -1, and firstEmpty != NULL,
191  * this will be set to the first empty bucket we found
192  * @retrun offset into _entries or -1 if not there
193  */
194  int _find( const K_L& key, int hash, int* firstEmpty ) const;
195 
196  void _grow();
197 
198  // ----
199 
200  size_t _size;
201  double _maxProbeRatio;
202  Area _area;
203 
204  H _hash;
205  E _equals;
206  C _convertor;
207  C_LS _convertorOther;
208  };
209 
210 }
211 
212 #include "mongo/util/unordered_fast_key_table_internal.h"
213 
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
Definition: unordered_fast_key_table.h:27
size_t size() const
Definition: unordered_fast_key_table.h:103
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