← Back to branch summary

~ubuntu-branches/ubuntu/precise/mysql-5.1/precise

« back to all changes in this revision

Viewing changes to storage/ndb/src/ndbapi/NdbLinHash.hpp

  • Committer: Bazaar Package Importer
  • Author(s): Norbert Tretkowski
  • Date: 2010-03-17 14:56:02 UTC
  • Revision ID: james.westby@ubuntu.com-20100317145602-x7e30l1b2sb5s6w6
Tags: upstream-5.1.45
Import upstream version 5.1.45

Show diffs side-by-side

added added

removed removed

Lines of Context:
storage/ndb/src/ndbapi/NdbLinHash.hpp
 
1
/* Copyright (C) 2003 MySQL AB
 
2
 
 
3
   This program is free software; you can redistribute it and/or modify
 
4
   it under the terms of the GNU General Public License as published by
 
5
   the Free Software Foundation; version 2 of the License.
 
6
 
 
7
   This program is distributed in the hope that it will be useful,
 
8
   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
9
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
10
   GNU General Public License for more details.
 
11
 
 
12
   You should have received a copy of the GNU General Public License
 
13
   along with this program; if not, write to the Free Software
 
14
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
15
 
 
16
#ifndef NdbLinHash_H
 
17
#define NdbLinHash_H
 
18
 
 
19
#include <ndb_types.h>
 
20
 
 
21
#define SEGMENTSIZE 64
 
22
#define SEGMENTLOGSIZE 6
 
23
#define DIRECTORYSIZE 64
 
24
#define DIRINDEX(adress) ((adress) >> SEGMENTLOGSIZE)
 
25
#define SEGINDEX(adress) ((adress) & (SEGMENTSIZE-1))
 
26
 
 
27
#if     !defined(MAXLOADFCTR)
 
28
#define MAXLOADFCTR 2
 
29
#endif
 
30
#if     !defined(MINLOADFCTR)
 
31
#define MINLOADFCTR (MAXLOADFCTR/2)
 
32
#endif
 
33
 
 
34
template<class C> 
 
35
class NdbElement_t {
 
36
public:
 
37
  NdbElement_t();
 
38
  ~NdbElement_t();
 
39
  
 
40
  Uint32 len;
 
41
  Uint32 hash;
 
42
  Uint32 localkey1;
 
43
  Uint32 *str;
 
44
  NdbElement_t<C> *next;
 
45
  C* theData;
 
46
private:
 
47
  NdbElement_t(const NdbElement_t<C> & aElement_t);
 
48
  NdbElement_t & operator = (const NdbElement_t<C> & aElement_t);
 
49
};
 
50
 
 
51
 
 
52
template <class C> 
 
53
class NdbLinHash {
 
54
public:
 
55
  NdbLinHash();
 
56
  ~NdbLinHash();
 
57
  void createHashTable(void);
 
58
  void releaseHashTable(void);
 
59
  
 
60
  int insertKey(const char * str, Uint32 len, Uint32 lkey1, C* data);
 
61
  C *deleteKey(const char * str, Uint32 len);
 
62
 
 
63
  C* getData(const char *, Uint32);
 
64
  Uint32* getKey(const char *, Uint32);
 
65
  
 
66
  void shrinkTable(void);
 
67
  void expandHashTable(void);
 
68
  
 
69
  Uint32 Hash(const char *str, Uint32 len);
 
70
  Uint32 Hash(Uint32 h);
 
71
  
 
72
  NdbElement_t<C> * getNext(NdbElement_t<C> * curr);
 
73
  
 
74
private:
 
75
  void getBucket(Uint32 hash, int * dirindex, int * segindex);
 
76
  
 
77
  struct Segment_t {
 
78
    NdbElement_t<C> * elements[SEGMENTSIZE];
 
79
  };
 
80
 
 
81
  Uint32 p;     /*bucket to be split*/
 
82
  Uint32 max;   /*max is the upper bound*/
 
83
  Int32  slack; /*number of insertions before splits*/
 
84
  Segment_t * directory[DIRECTORYSIZE];
 
85
  
 
86
  NdbLinHash(const NdbLinHash<C> & aLinHash);
 
87
  NdbLinHash<C> & operator = (const NdbLinHash<C> & aLinHash);
 
88
};
 
89
 
 
90
// All template methods must be inline
 
91
 
 
92
template <class C>
 
93
inline
 
94
NdbLinHash<C>::NdbLinHash() { 
 
95
}
 
96
 
 
97
template <class C>
 
98
inline
 
99
NdbLinHash<C>::NdbLinHash(const NdbLinHash<C>& aLinHash) 
 
100
{
 
101
}
 
102
 
 
103
template <class C>
 
104
inline
 
105
NdbLinHash<C>::~NdbLinHash()
 
106
{
 
107
}
 
108
 
 
109
template <class C>
 
110
inline
 
111
Uint32
 
112
NdbLinHash<C>::Hash( const char* str, Uint32 len )
 
113
{
 
114
  Uint32 h = 0;
 
115
  while(len >= 4){
 
116
    h = (h << 5) + h + str[0];
 
117
    h = (h << 5) + h + str[1];
 
118
    h = (h << 5) + h + str[2];
 
119
    h = (h << 5) + h + str[3];
 
120
    len -= 4;
 
121
    str += 4;
 
122
  }
 
123
  
 
124
  while(len > 0){
 
125
    h = (h << 5) + h + *str++;
 
126
    len--;
 
127
  }
 
128
  return h;
 
129
}
 
130
 
 
131
template <class C>
 
132
inline
 
133
Uint32
 
134
NdbLinHash<C>::Hash( Uint32 h ){
 
135
  return h;
 
136
}
 
137
 
 
138
template <class C>
 
139
inline
 
140
NdbElement_t<C>::NdbElement_t() :
 
141
  len(0),
 
142
  hash(0),
 
143
  localkey1(0),
 
144
  str(NULL),
 
145
  next(NULL),
 
146
  theData(NULL)
 
147
{ 
 
148
}
 
149
 
 
150
template <class C>
 
151
inline
 
152
NdbElement_t<C>::~NdbElement_t()
 
153
{
 
154
  delete []str;
 
155
}
 
156
 
 
157
 
 
158
/* Initialize the hashtable HASH_T  */
 
159
template <class C>
 
160
inline
 
161
void
 
162
NdbLinHash<C>::createHashTable() {
 
163
  p = 0;
 
164
  max = SEGMENTSIZE - 1;
 
165
  slack = SEGMENTSIZE * MAXLOADFCTR;
 
166
  directory[0] = new Segment_t();
 
167
  int i;
 
168
 
 
169
  /* The first segment cleared before used */
 
170
  for(i  = 0; i < SEGMENTSIZE; i++ )
 
171
    directory[0]->elements[i] = 0;
 
172
  
 
173
  /* clear the rest of the directory */
 
174
  for(i = 1; i < DIRECTORYSIZE; i++)
 
175
    directory[i] = 0;
 
176
}
 
177
 
 
178
template <class C>
 
179
inline
 
180
void
 
181
NdbLinHash<C>::getBucket(Uint32 hash, int * dir, int * seg){
 
182
  Uint32 adress = hash & max;
 
183
  if(adress < p)
 
184
    adress = hash & (2 * max + 1);
 
185
  
 
186
  * dir = DIRINDEX(adress);
 
187
  * seg = SEGINDEX(adress);
 
188
}
 
189
 
 
190
template <class C>
 
191
inline
 
192
Int32
 
193
NdbLinHash<C>::insertKey( const char* str, Uint32 len, Uint32 lkey1, C* data )
 
194
{ 
 
195
  const Uint32 hash = Hash(str, len);
 
196
  int dir, seg;
 
197
  getBucket(hash, &dir, &seg);
 
198
  
 
199
  NdbElement_t<C> **chainp = &directory[dir]->elements[seg];
 
200
  
 
201
  /**
 
202
   * Check if the string already are in the hash table
 
203
   * chain=chainp will copy the contents of HASH_T into chain  
 
204
   */
 
205
  NdbElement_t<C> * oldChain = 0;  
 
206
  NdbElement_t<C> * chain;
 
207
  for(chain = *chainp; chain != 0; chain = chain->next){
 
208
    if(chain->len == len && !memcmp(chain->str, str, len)) 
 
209
      return -1; /* Element already exists */
 
210
    else 
 
211
      oldChain = chain;
 
212
  }
 
213
 
 
214
  /* New entry */
 
215
  chain = new NdbElement_t<C>();
 
216
  chain->len = len;
 
217
  chain->hash = hash;
 
218
  chain->localkey1 = lkey1;
 
219
  chain->next = 0;
 
220
  chain->theData = data;
 
221
  len++; // Null terminated
 
222
  chain->str = new Uint32[((len + 3) >> 2)];
 
223
  memcpy( &chain->str[0], str, len);
 
224
  if (oldChain != 0) 
 
225
    oldChain->next = chain;
 
226
  else
 
227
    *chainp =  chain; 
 
228
  
 
229
#if 0
 
230
  if(--(slack) < 0)
 
231
    expandHashTable(); 
 
232
#endif
 
233
  
 
234
  return chain->localkey1;
 
235
}
 
236
 
 
237
 
 
238
template <class C>
 
239
inline
 
240
Uint32*
 
241
NdbLinHash<C>::getKey( const char* str, Uint32 len )
 
242
{
 
243
  const Uint32 tHash = Hash(str, len);
 
244
  int dir, seg;
 
245
  getBucket(tHash, &dir, &seg);
 
246
  
 
247
  NdbElement_t<C> ** keyp = &directory[dir]->elements[seg];
 
248
  
 
249
  /*Check if the string are in the hash table*/
 
250
  for(NdbElement_t<C> * key = *keyp; key != 0; key = key->next ) {
 
251
    if(key->len == len && !memcmp(key->str, str, len)) {
 
252
      return &key->localkey1;  
 
253
    }
 
254
  }
 
255
  return NULL ; /* The key was not found */     
 
256
}
 
257
 
 
258
template <class C>
 
259
inline
 
260
C*
 
261
NdbLinHash<C>::getData( const char* str, Uint32 len ){
 
262
  
 
263
  const Uint32 tHash = Hash(str, len);
 
264
  int dir, seg;
 
265
  getBucket(tHash, &dir, &seg);
 
266
  
 
267
  NdbElement_t<C> ** keyp = &directory[dir]->elements[seg];
 
268
    
 
269
  /*Check if the string are in the hash table*/
 
270
  for(NdbElement_t<C> * key = *keyp; key != 0; key = key->next ) {
 
271
    if(key->len == len && !memcmp(key->str, str, len)) {
 
272
      return key->theData;  
 
273
    }
 
274
  }
 
275
  return NULL ; /* The key was not found */     
 
276
}
 
277
 
 
278
template <class C>
 
279
inline
 
280
C *
 
281
NdbLinHash<C>::deleteKey ( const char* str, Uint32 len){
 
282
  const Uint32 hash = Hash(str, len);
 
283
  int dir, seg;
 
284
  getBucket(hash, &dir, &seg);
 
285
  
 
286
  NdbElement_t<C> *oldChain = 0;
 
287
  NdbElement_t<C> **chainp = &directory[dir]->elements[seg];
 
288
  for(NdbElement_t<C> * chain = *chainp; chain != 0; chain = chain->next){
 
289
    if(chain->len == len && !memcmp(chain->str, str, len)){
 
290
      C *data= chain->theData;
 
291
      if (oldChain == 0) {
 
292
        * chainp = chain->next;
 
293
      } else {
 
294
        oldChain->next = chain->next;
 
295
      }
 
296
      delete chain;
 
297
      return data;
 
298
    } else {
 
299
      oldChain = chain;
 
300
    }
 
301
  }
 
302
  return 0; /* Element doesn't exist */
 
303
}
 
304
 
 
305
template <class C>
 
306
inline
 
307
void 
 
308
NdbLinHash<C>::releaseHashTable( void ){
 
309
  NdbElement_t<C>* tNextElement;
 
310
  NdbElement_t<C>* tElement;
 
311
  
 
312
  //Traverse the whole directory structure
 
313
  for(int countd = 0; countd < DIRECTORYSIZE;countd++ ){
 
314
    if (directory[countd] != 0) {
 
315
      //Traverse whole hashtable
 
316
      for(int counts = 0; counts < SEGMENTSIZE; counts++ )
 
317
        if (directory[countd]->elements[counts] != 0) {
 
318
          tElement = directory[countd]->elements[counts];
 
319
          //Delete all elements even those who is linked
 
320
          do {
 
321
            tNextElement = tElement->next;             
 
322
            delete tElement;
 
323
            tElement = tNextElement;
 
324
          } while (tNextElement != 0);
 
325
        }
 
326
      delete directory[countd];
 
327
    }   
 
328
  }
 
329
}
 
330
 
 
331
template <class C>
 
332
inline
 
333
void
 
334
NdbLinHash<C>::shrinkTable( void )
 
335
{
 
336
  Segment_t *lastseg;
 
337
  NdbElement_t<C> **chainp;
 
338
  Uint32 oldlast = p + max;
 
339
 
 
340
  if( oldlast == 0 )
 
341
    return;
 
342
 
 
343
  // Adjust the state variables.
 
344
  if( p == 0 ) {
 
345
    max >>= 1;
 
346
    p = max;
 
347
  }
 
348
  else
 
349
    --(p);
 
350
    
 
351
  // Update slack after shrink.
 
352
    
 
353
  slack -= MAXLOADFCTR;
 
354
 
 
355
  // Insert the chain oldlast at the end of chain p.
 
356
    
 
357
  chainp = &directory[DIRINDEX(p)]->elements[SEGINDEX(p)];
 
358
  while( *chainp != 0 ) {
 
359
    chainp = &((*chainp)->next);
 
360
    lastseg = directory[DIRINDEX(oldlast)];
 
361
    *chainp = lastseg->elements[SEGINDEX(oldlast)];
 
362
 
 
363
    // If necessary free last segment.
 
364
    if( SEGINDEX(oldlast) == 0)
 
365
      delete lastseg;
 
366
  }
 
367
}
 
368
 
 
369
template <class C>
 
370
inline
 
371
void 
 
372
NdbLinHash<C>::expandHashTable( void )
 
373
{
 
374
 
 
375
  NdbElement_t<C>       **oldbucketp, *chain, *headofold, *headofnew, *next;
 
376
  Uint32                maxp = max + 1;
 
377
  Uint32                newadress = maxp + p;
 
378
 
 
379
 
 
380
  // Still room in the adress space?
 
381
  if( newadress >= DIRECTORYSIZE * SEGMENTSIZE ) {
 
382
    return;
 
383
  }  
 
384
  
 
385
  // If necessary, create a new segment.
 
386
  if( SEGINDEX(newadress) == 0 )
 
387
    directory[DIRINDEX(newadress)] = new Segment_t();
 
388
    
 
389
  // Locate the old (to be split) bucket.
 
390
  oldbucketp = &directory[DIRINDEX(p)]->elements[SEGINDEX(p)];
 
391
    
 
392
  // Adjust the state variables.
 
393
  p++;      
 
394
  if( p > max ) {
 
395
    max = 2 *max + 1;
 
396
    p = 0;
 
397
  }
 
398
            
 
399
  // Update slack after expandation.
 
400
  slack += MAXLOADFCTR;
 
401
    
 
402
  // Relocate records to the new bucket.
 
403
  headofold = 0;
 
404
  headofnew = 0;
 
405
    
 
406
  for( chain = *oldbucketp; chain != 0; chain = next ) {
 
407
    next = chain->next;
 
408
    if( chain->hash & maxp ) {
 
409
      chain->next = headofnew;
 
410
      headofnew = chain;
 
411
    }
 
412
    else {
 
413
      chain->next = headofold;
 
414
      headofold = chain;
 
415
    }
 
416
  }
 
417
  *oldbucketp = headofold;
 
418
  directory[DIRINDEX(newadress)]->elements[SEGINDEX(newadress)] = headofnew;
 
419
}
 
420
 
 
421
template <class C>
 
422
inline
 
423
NdbElement_t<C> *
 
424
NdbLinHash<C>::getNext(NdbElement_t<C> * curr){
 
425
  if(curr != 0 && curr->next != 0)
 
426
    return curr->next;
 
427
  
 
428
  int dir = 0, seg = 0;
 
429
  int counts;
 
430
  if(curr != 0)
 
431
  {
 
432
    getBucket(curr->hash, &dir, &seg);
 
433
    counts = seg + 1;
 
434
  }
 
435
  else
 
436
  {
 
437
    counts = 0;
 
438
  }
 
439
  
 
440
  for(int countd = dir; countd < DIRECTORYSIZE;countd++ ){
 
441
    if (directory[countd] != 0) {
 
442
      for(; counts < SEGMENTSIZE; counts++ ){
 
443
        if (directory[countd]->elements[counts] != 0) {
 
444
          return directory[countd]->elements[counts];
 
445
        }   
 
446
      }
 
447
    }
 
448
    counts = 0;
 
449
  }
 
450
 
 
451
  return 0;
 
452
}
 
453
 
 
454
#endif