diff options
| author | Dwight <dmerriman@gmail.com> | 2007-10-19 19:35:48 -0400 |
|---|---|---|
| committer | Dwight <dmerriman@gmail.com> | 2007-10-19 19:35:48 -0400 |
| commit | e73188b5512c82290a4070af4afddac20d0b981e (patch) | |
| tree | cf25c77d94478ecfe372bd2d8a2d59b8817918dd /util/hashtab.h | |
| download | mongo-e73188b5512c82290a4070af4afddac20d0b981e.tar.gz | |
first commit
Diffstat (limited to 'util/hashtab.h')
| -rw-r--r-- | util/hashtab.h | 96 |
1 files changed, 96 insertions, 0 deletions
diff --git a/util/hashtab.h b/util/hashtab.h new file mode 100644 index 00000000000..9c45425d06b --- /dev/null +++ b/util/hashtab.h @@ -0,0 +1,96 @@ +/* hashtab.h
+
+ Simple, fixed size hash table. Darn simple.
+
+ Uses a contiguous block of memory, so you can put it in a memory mapped file very easily.
+*/
+
+#include "../stdafx.h"
+#include <map>
+
+#pragma pack(push)
+#pragma pack(1)
+
+/* you should define:
+
+ int Key::hash() return > 0 always.
+*/
+
+template <
+ class Key,
+ class Type
+>
+class HashTable {
+private:
+ const char *name;
+ struct Node {
+ int hash;
+ Key k;
+ Type value;
+ } *nodes;
+ int n;
+
+ int _find(const Key& k, bool& found) {
+ found = false;
+ int h = k.hash();
+ int i = h % n;
+ int start = i;
+ int chain = 0;
+ while( 1 ) {
+ if( nodes[i].hash == 0 ) {
+ return i;
+ }
+ if( nodes[i].hash == h && nodes[i].k == k ) {
+ found = true;
+ return i;
+ }
+ chain++;
+ i = (i+1) % n;
+ if( i == start ) {
+ cout << "warning: hashtable is full " << name << endl;
+ return -1;
+ }
+ if( chain == 200 )
+ cout << "warning: hashtable long chain " << name << endl;
+ }
+ }
+
+public:
+ /* buf must be all zeroes on initialization. */
+ HashTable(void *buf, int buflen, const char *_name) : name(_name) {
+ int m = sizeof(Node);
+ n = buflen / m;
+ if( (n & 1) == 0 )
+ n--;
+ nodes = (Node *) buf;
+ assert(nodes[n-1].hash == 0);
+ assert(nodes[0].hash == 0);
+ }
+
+ Type* get(const Key& k) {
+ bool found;
+ int i = _find(k, found);
+ if( found )
+ return &nodes[i].value;
+ return 0;
+ }
+
+ void put(const Key& k, const Type& value) {
+ bool found;
+ int i = _find(k, found);
+ if( i < 0 )
+ return;
+ if( !found ) {
+ nodes[i].k = k;
+ nodes[i].hash = k.hash();
+ }
+ else {
+ assert( nodes[i].hash == k.hash() );
+ }
+ nodes[i].value = value;
+ }
+
+};
+
+#pragma pack(pop)
+
|