← Back to branch summary

~ubuntu-branches/ubuntu/utopic/mongodb/utopic

« back to all changes in this revision

Viewing changes to src/mongo/util/hashtab.h

  • Committer: Package Import Robot
  • Author(s): James Page
  • Date: 2014-07-03 09:23:46 UTC
  • mfrom: (1.3.10) (44.1.14 sid)
  • Revision ID: package-import@ubuntu.com-20140703092346-c5bvt46wnzougyly
Tags: 1:2.6.3-0ubuntu1
https://launchpad.net/bugs/1295723
https://launchpad.net/bugs/1294455
* New upstream stable release:
  - Dropped patches, included upstream:
    + 0003-All-platforms-but-Windows-find-hash-in-std-tr1.patch
    + 0008-Use-system-libstemmer.patch
    + 0011-Use-a-signed-char-to-store-BSONType-enumerations.patch
    + 0001-SERVER-12064-Atomic-operations-for-gcc-non-Intel-arc.patch
    + 0002-SERVER-12065-Support-ARM-and-AArch64-builds.patch
  - d/p/*: Refreshed/rebased remaining patches.
  - Use system provided libyaml-cpp:
    + d/control: Add libyaml-cpp-dev to BD's.
    + d/rules: Enable --with-system-yaml option.
    + d/p/fix-yaml-detection.patch: Fix detection of libyaml-cpp library.
  - d/mongodb-server.mongodb.upstart: Sync changes from upstream.
  - d/control,mongodb-dev.*: Drop mongodb-dev package; it has no reverse
    dependencies and upstream no longer install header files.
  - d/NEWS: Point users to upstream upgrade documentation for upgrades
    from 2.4 to 2.6.
* Merge from Debian unstable.
* d/control: BD on libv8-3.14-dev to ensure that transitioning to new v8
  versions is a explicit action due to changes in behaviour in >= 3.25
  (LP: #1295723).
* d/mongodb-server.prerm: Dropped debug echo call from maintainer script
  (LP: #1294455).

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/mongo/util/hashtab.h
1
 
/* hashtab.h
2
 
 
3
 
   Simple, fixed size hash table.  Darn simple.
4
 
 
5
 
   Uses a contiguous block of memory, so you can put it in a memory mapped file very easily.
6
 
*/
7
 
 
8
 
/*    Copyright 2009 10gen Inc.
9
 
 *
10
 
 *    Licensed under the Apache License, Version 2.0 (the "License");
11
 
 *    you may not use this file except in compliance with the License.
12
 
 *    You may obtain a copy of the License at
13
 
 *
14
 
 *    http://www.apache.org/licenses/LICENSE-2.0
15
 
 *
16
 
 *    Unless required by applicable law or agreed to in writing, software
17
 
 *    distributed under the License is distributed on an "AS IS" BASIS,
18
 
 *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
19
 
 *    See the License for the specific language governing permissions and
20
 
 *    limitations under the License.
21
 
 */
22
 
 
23
 
#pragma once
24
 
 
25
 
#include "mongo/pch.h"
26
 
#include <map>
27
 
#include "../db/dur.h"
28
 
 
29
 
namespace mongo {
30
 
 
31
 
#pragma pack(1)
32
 
 
33
 
    /* you should define:
34
 
 
35
 
       int Key::hash() return > 0 always.
36
 
    */
37
 
 
38
 
    template <class Key,class Type>
39
 
    class HashTable : boost::noncopyable {
40
 
    public:
41
 
        const char *name;
42
 
        struct Node {
43
 
            int hash;
44
 
            Key k;
45
 
            Type value;
46
 
            bool inUse() {
47
 
                return hash != 0;
48
 
            }
49
 
            void setUnused() {
50
 
                hash = 0;
51
 
            }
52
 
        };
53
 
        void* _buf;
54
 
        int n; // number of hashtable buckets
55
 
        int maxChain;
56
 
 
57
 
        Node& nodes(int i) {
58
 
            Node *nodes = (Node *) _buf;
59
 
            return nodes[i];
60
 
        }
61
 
 
62
 
        int _find(const Key& k, bool& found) {
63
 
            found = false;
64
 
            int h = k.hash();
65
 
            int i = h % n;
66
 
            int start = i;
67
 
            int chain = 0;
68
 
            int firstNonUsed = -1;
69
 
            while ( 1 ) {
70
 
                if ( !nodes(i).inUse() ) {
71
 
                    if ( firstNonUsed < 0 )
72
 
                        firstNonUsed = i;
73
 
                }
74
 
 
75
 
                if ( nodes(i).hash == h && nodes(i).k == k ) {
76
 
                    if ( chain >= 200 )
77
 
                        out() << "warning: hashtable " << name << " long chain " << endl;
78
 
                    found = true;
79
 
                    return i;
80
 
                }
81
 
                chain++;
82
 
                i = (i+1) % n;
83
 
                if ( i == start ) {
84
 
                    // shouldn't get here / defensive for infinite loops
85
 
                    out() << "error: hashtable " << name << " is full n:" << n << endl;
86
 
                    return -1;
87
 
                }
88
 
                if( chain >= maxChain ) {
89
 
                    if ( firstNonUsed >= 0 )
90
 
                        return firstNonUsed;
91
 
                    out() << "error: hashtable " << name << " max chain reached:" << maxChain << endl;
92
 
                    return -1;
93
 
                }
94
 
            }
95
 
        }
96
 
 
97
 
    public:
98
 
        /* buf must be all zeroes on initialization. */
99
 
        HashTable(void* buf, int buflen, const char *_name) : name(_name) {
100
 
            int m = sizeof(Node);
101
 
            // out() << "hashtab init, buflen:" << buflen << " m:" << m << endl;
102
 
            n = buflen / m;
103
 
            if ( (n & 1) == 0 )
104
 
                n--;
105
 
            maxChain = (int) (n * 0.05);
106
 
            _buf = buf;
107
 
            //nodes = (Node *) buf;
108
 
 
109
 
            if ( sizeof(Node) != 628 ) {
110
 
                out() << "HashTable() " << _name << " sizeof(node):" << sizeof(Node) << " n:" << n << " sizeof(Key): " << sizeof(Key) << " sizeof(Type):" << sizeof(Type) << endl;
111
 
                verify( sizeof(Node) == 628 );
112
 
            }
113
 
 
114
 
        }
115
 
 
116
 
        Type* get(const Key& k) {
117
 
            bool found;
118
 
            int i = _find(k, found);
119
 
            if ( found )
120
 
                return &nodes(i).value;
121
 
            return 0;
122
 
        }
123
 
 
124
 
        void kill(const Key& k) {
125
 
            bool found;
126
 
            int i = _find(k, found);
127
 
            if ( i >= 0 && found ) {
128
 
                Node* n = &nodes(i);
129
 
                n = getDur().writing(n);
130
 
                n->k.kill();
131
 
                n->setUnused();
132
 
            }
133
 
        }
134
 
 
135
 
        /** returns false if too full */
136
 
        bool put(const Key& k, const Type& value) {
137
 
            bool found;
138
 
            int i = _find(k, found);
139
 
            if ( i < 0 )
140
 
                return false;
141
 
            Node* n = getDur().writing( &nodes(i) );
142
 
            if ( !found ) {
143
 
                n->k = k;
144
 
                n->hash = k.hash();
145
 
            }
146
 
            else {
147
 
                verify( n->hash == k.hash() );
148
 
            }
149
 
            n->value = value;
150
 
            return true;
151
 
        }
152
 
 
153
 
        typedef void (*IteratorCallback)( const Key& k , Type& v );
154
 
        void iterAll( IteratorCallback callback ) {
155
 
            for ( int i=0; i<n; i++ ) {
156
 
                if ( nodes(i).inUse() ) {
157
 
                    callback( nodes(i).k , nodes(i).value );
158
 
                }
159
 
            }
160
 
        }
161
 
 
162
 
        // TODO: should probably use boost::bind for this, but didn't want to look at it
163
 
        typedef void (*IteratorCallback2)( const Key& k , Type& v , void * extra );
164
 
        void iterAll( IteratorCallback2 callback , void * extra ) {
165
 
            for ( int i=0; i<n; i++ ) {
166
 
                if ( nodes(i).inUse() ) {
167
 
                    callback( nodes(i).k , nodes(i).value , extra );
168
 
                }
169
 
            }
170
 
        }
171
 
 
172
 
    };
173
 
 
174
 
#pragma pack()
175
 
 
176
 
} // namespace mongo