MongoDB  2.0.3
hashtab.h
00001 /* hashtab.h
00002 
00003    Simple, fixed size hash table.  Darn simple.
00004 
00005    Uses a contiguous block of memory, so you can put it in a memory mapped file very easily.
00006 */
00007 
00008 /*    Copyright 2009 10gen Inc.
00009  *
00010  *    Licensed under the Apache License, Version 2.0 (the "License");
00011  *    you may not use this file except in compliance with the License.
00012  *    You may obtain a copy of the License at
00013  *
00014  *    http://www.apache.org/licenses/LICENSE-2.0
00015  *
00016  *    Unless required by applicable law or agreed to in writing, software
00017  *    distributed under the License is distributed on an "AS IS" BASIS,
00018  *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00019  *    See the License for the specific language governing permissions and
00020  *    limitations under the License.
00021  */
00022 
00023 #pragma once
00024 
00025 #include "../pch.h"
00026 #include <map>
00027 #include "../db/dur.h"
00028 
00029 namespace mongo {
00030 
00031 #pragma pack(1)
00032 
00033     /* you should define:
00034 
00035        int Key::hash() return > 0 always.
00036     */
00037 
00038     template <
00039     class Key,
00040           class Type
00041           >
00042     class HashTable : boost::noncopyable {
00043     public:
00044         const char *name;
00045         struct Node {
00046             int hash;
00047             Key k;
00048             Type value;
00049             bool inUse() {
00050                 return hash != 0;
00051             }
00052             void setUnused() {
00053                 hash = 0;
00054             }
00055         };
00056         void* _buf;
00057         int n; // number of hashtable buckets
00058         int maxChain;
00059 
00060         Node& nodes(int i) {
00061             Node *nodes = (Node *) _buf;
00062             return nodes[i];
00063         }
00064 
00065         int _find(const Key& k, bool& found) {
00066             found = false;
00067             int h = k.hash();
00068             int i = h % n;
00069             int start = i;
00070             int chain = 0;
00071             int firstNonUsed = -1;
00072             while ( 1 ) {
00073                 if ( !nodes(i).inUse() ) {
00074                     if ( firstNonUsed < 0 )
00075                         firstNonUsed = i;
00076                 }
00077 
00078                 if ( nodes(i).hash == h && nodes(i).k == k ) {
00079                     if ( chain >= 200 )
00080                         out() << "warning: hashtable " << name << " long chain " << endl;
00081                     found = true;
00082                     return i;
00083                 }
00084                 chain++;
00085                 i = (i+1) % n;
00086                 if ( i == start ) {
00087                     // shouldn't get here / defensive for infinite loops
00088                     out() << "error: hashtable " << name << " is full n:" << n << endl;
00089                     return -1;
00090                 }
00091                 if( chain >= maxChain ) {
00092                     if ( firstNonUsed >= 0 )
00093                         return firstNonUsed;
00094                     out() << "error: hashtable " << name << " max chain reached:" << maxChain << endl;
00095                     return -1;
00096                 }
00097             }
00098         }
00099 
00100     public:
00101         /* buf must be all zeroes on initialization. */
00102         HashTable(void* buf, int buflen, const char *_name) : name(_name) {
00103             int m = sizeof(Node);
00104             // out() << "hashtab init, buflen:" << buflen << " m:" << m << endl;
00105             n = buflen / m;
00106             if ( (n & 1) == 0 )
00107                 n--;
00108             maxChain = (int) (n * 0.05);
00109             _buf = buf;
00110             //nodes = (Node *) buf;
00111 
00112             if ( sizeof(Node) != 628 ) {
00113                 out() << "HashTable() " << _name << " sizeof(node):" << sizeof(Node) << " n:" << n << " sizeof(Key): " << sizeof(Key) << " sizeof(Type):" << sizeof(Type) << endl;
00114                 assert( sizeof(Node) == 628 );
00115             }
00116 
00117         }
00118 
00119         Type* get(const Key& k) {
00120             bool found;
00121             int i = _find(k, found);
00122             if ( found )
00123                 return &nodes(i).value;
00124             return 0;
00125         }
00126 
00127         void kill(const Key& k) {
00128             bool found;
00129             int i = _find(k, found);
00130             if ( i >= 0 && found ) {
00131                 Node* n = &nodes(i);
00132                 n = getDur().writing(n);
00133                 n->k.kill();
00134                 n->setUnused();
00135             }
00136         }
00137 
00139         bool put(const Key& k, const Type& value) {
00140             bool found;
00141             int i = _find(k, found);
00142             if ( i < 0 )
00143                 return false;
00144             Node* n = getDur().writing( &nodes(i) );
00145             if ( !found ) {
00146                 n->k = k;
00147                 n->hash = k.hash();
00148             }
00149             else {
00150                 assert( n->hash == k.hash() );
00151             }
00152             n->value = value;
00153             return true;
00154         }
00155 
00156         typedef void (*IteratorCallback)( const Key& k , Type& v );
00157         void iterAll( IteratorCallback callback ) {
00158             for ( int i=0; i<n; i++ ) {
00159                 if ( nodes(i).inUse() ) {
00160                     callback( nodes(i).k , nodes(i).value );
00161                 }
00162             }
00163         }
00164 
00165         // TODO: should probably use boost::bind for this, but didn't want to look at it
00166         typedef void (*IteratorCallback2)( const Key& k , Type& v , void * extra );
00167         void iterAll( IteratorCallback2 callback , void * extra ) {
00168             for ( int i=0; i<n; i++ ) {
00169                 if ( nodes(i).inUse() ) {
00170                     callback( nodes(i).k , nodes(i).value , extra );
00171                 }
00172             }
00173         }
00174 
00175     };
00176 
00177 #pragma pack()
00178 
00179 } // namespace mongo