MongoDB  2.7.0
lruishmap.h
1 // lru-ish map.h
2 
3 /* Copyright 2009 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 "mongo/pch.h"
21 #include "mongo/util/goodies.h"
22 
23 namespace mongo {
24 
25  /* Your K object must define:
26  int hash() - must always return > 0.
27  operator==
28  */
29 
30  template <class K, class V, int MaxChain>
31  class LRUishMap {
32  public:
33  LRUishMap(int _n) {
34  n = nextPrime(_n);
35  keys = new K[n];
36  hashes = new int[n];
37  for ( int i = 0; i < n; i++ ) hashes[i] = 0;
38  }
39  ~LRUishMap() {
40  delete[] keys;
41  delete[] hashes;
42  }
43 
44  int _find(const K& k, bool& found) {
45  int h = k.hash();
46  verify( h > 0 );
47  int j = h % n;
48  int first = j;
49  for ( int i = 0; i < MaxChain; i++ ) {
50  if ( hashes[j] == h ) {
51  if ( keys[j] == k ) {
52  found = true;
53  return j;
54  }
55  }
56  else if ( hashes[j] == 0 ) {
57  found = false;
58  return j;
59  }
60  }
61  found = false;
62  return first;
63  }
64 
65  V* find(const K& k) {
66  bool found;
67  int j = _find(k, found);
68  return found ? &values[j] : 0;
69  }
70 
71  private:
72  int n;
73  K *keys;
74  int *hashes;
75  V *values;
76  };
77 
78 } // namespace mongo
Definition: lruishmap.h:31