← 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/kernel/vm/DLHashTable2.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/kernel/vm/DLHashTable2.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 DL_HASHTABLE2_HPP
 
17
#define DL_HASHTABLE2_HPP
 
18
 
 
19
#include <ndb_global.h>
 
20
#include "ArrayPool.hpp"
 
21
 
 
22
/**
 
23
 * DLHashTable2 is a DLHashTable variant meant for cases where different
 
24
 * DLHashTable instances share a common pool (based on a union U).
 
25
 *
 
26
 * Calls T constructor after seize from pool and T destructor before
 
27
 * release (in all forms) into pool.
 
28
 */
 
29
template <class T, class U>
 
30
class DLHashTable2 {
 
31
public:
 
32
  DLHashTable2(ArrayPool<U> & thePool);
 
33
  ~DLHashTable2();
 
34
  
 
35
  /**
 
36
   * Set the no of bucket in the hashtable
 
37
   *
 
38
   * Note, can currently only be called once
 
39
   */
 
40
  bool setSize(Uint32 noOfElements);
 
41
 
 
42
  /**
 
43
   * Seize element from pool - return i
 
44
   *
 
45
   * Note *must* be added using <b>add</b> (even before hash.release)
 
46
   *             or be released using pool
 
47
   */
 
48
  bool seize(Ptr<T> &);
 
49
 
 
50
  /**
 
51
   * Add an object to the hashtable
 
52
   */
 
53
  void add(Ptr<T> &);
 
54
  
 
55
  /**
 
56
   * Find element key in hashtable update Ptr (i & p) 
 
57
   *   (using key.equal(...))
 
58
   * @return true if found and false otherwise
 
59
   */
 
60
  bool find(Ptr<T> &, const T & key) const;
 
61
 
 
62
  /**
 
63
   * Update i & p value according to <b>i</b>
 
64
   */
 
65
  void getPtr(Ptr<T> &, Uint32 i) const;
 
66
 
 
67
  /**
 
68
   * Get element using ptr.i (update ptr.p)
 
69
   */
 
70
  void getPtr(Ptr<T> &) const;
 
71
 
 
72
  /**
 
73
   * Get P value for i
 
74
   */
 
75
  T * getPtr(Uint32 i) const;
 
76
 
 
77
  /**
 
78
   * Remove element (and set Ptr to removed element)
 
79
   * Note does not return to pool
 
80
   */
 
81
  void remove(Ptr<T> &, const T & key);
 
82
 
 
83
  /**
 
84
   * Remove element
 
85
   * Note does not return to pool
 
86
   */
 
87
  void remove(Uint32 i);
 
88
 
 
89
  /**
 
90
   * Remove element
 
91
   * Note does not return to pool
 
92
   */
 
93
  void remove(Ptr<T> &);
 
94
 
 
95
  /**
 
96
   * Remove all elements, but dont return them to pool
 
97
   */
 
98
  void removeAll();
 
99
  
 
100
  /**
 
101
   * Remove element (and set Ptr to removed element)
 
102
   * And return element to pool
 
103
   */
 
104
  void release(Ptr<T> &, const T & key);
 
105
 
 
106
  /**
 
107
   * Remove element and return to pool
 
108
   */
 
109
  void release(Uint32 i);
 
110
 
 
111
  /**
 
112
   * Remove element and return to pool
 
113
   */
 
114
  void release(Ptr<T> &);
 
115
  
 
116
  class Iterator {
 
117
  public:
 
118
    Ptr<T> curr;
 
119
    Uint32 bucket;
 
120
    inline bool isNull() const { return curr.isNull();}
 
121
    inline void setNull() { curr.setNull(); }
 
122
  };
 
123
 
 
124
  /**
 
125
   * Sets curr.p according to curr.i
 
126
   */
 
127
  void getPtr(Iterator & iter) const ;
 
128
 
 
129
  /**
 
130
   * First element in bucket
 
131
   */
 
132
  bool first(Iterator & iter) const;
 
133
  
 
134
  /**
 
135
   * Next Element
 
136
   *
 
137
   * param iter - A "fully set" iterator
 
138
   */
 
139
  bool next(Iterator & iter) const;
 
140
 
 
141
  /**
 
142
   * Get next element starting from bucket
 
143
   *
 
144
   * @param bucket - Which bucket to start from
 
145
   * @param iter - An "uninitialized" iterator
 
146
   */
 
147
  bool next(Uint32 bucket, Iterator & iter) const;
 
148
 
 
149
  inline bool isEmpty() const { Iterator iter; return ! first(iter); }
 
150
  
 
151
private:
 
152
  Uint32 mask;
 
153
  Uint32 * hashValues;
 
154
  ArrayPool<U> & thePool;
 
155
};
 
156
 
 
157
template<class T, class U>
 
158
inline
 
159
DLHashTable2<T, U>::DLHashTable2(ArrayPool<U> & _pool)
 
160
  : thePool(_pool)
 
161
{
 
162
  mask = 0;
 
163
  hashValues = 0;
 
164
}
 
165
 
 
166
template<class T, class U>
 
167
inline
 
168
DLHashTable2<T, U>::~DLHashTable2(){
 
169
  if(hashValues != 0)
 
170
    delete [] hashValues;
 
171
}
 
172
 
 
173
template<class T, class U>
 
174
inline
 
175
bool
 
176
DLHashTable2<T, U>::setSize(Uint32 size){
 
177
  Uint32 i = 1;
 
178
  while(i < size) i *= 2;
 
179
 
 
180
  if(mask == (i - 1)){
 
181
    /**
 
182
     * The size is already set to <b>size</b>
 
183
     */
 
184
    return true;
 
185
  }
 
186
 
 
187
  if(mask != 0){
 
188
    /**
 
189
     * The mask is already set
 
190
     */
 
191
    return false;
 
192
  }
 
193
  
 
194
  mask = (i - 1);
 
195
  hashValues = new Uint32[i];
 
196
  for(Uint32 j = 0; j<i; j++)
 
197
    hashValues[j] = RNIL;
 
198
  
 
199
  return true;
 
200
}
 
201
 
 
202
template<class T, class U>
 
203
inline
 
204
void
 
205
DLHashTable2<T, U>::add(Ptr<T> & obj){
 
206
  const Uint32 hv = obj.p->hashValue() & mask;
 
207
  const Uint32 i  = hashValues[hv];
 
208
  
 
209
  if(i == RNIL){
 
210
    hashValues[hv] = obj.i;
 
211
    obj.p->nextHash = RNIL;
 
212
    obj.p->prevHash = RNIL;
 
213
  } else {
 
214
    
 
215
    T * tmp = (T*)thePool.getPtr(i);    // cast
 
216
    tmp->prevHash = obj.i;
 
217
    obj.p->nextHash = i;
 
218
    obj.p->prevHash = RNIL;
 
219
    
 
220
    hashValues[hv] = obj.i;
 
221
  }
 
222
}
 
223
 
 
224
/**
 
225
 * First element
 
226
 */
 
227
template<class T, class U>
 
228
inline
 
229
bool
 
230
DLHashTable2<T, U>::first(Iterator & iter) const {
 
231
  Uint32 i = 0;
 
232
  while(i <= mask && hashValues[i] == RNIL) i++;
 
233
  if(i <= mask){
 
234
    iter.bucket = i;
 
235
    iter.curr.i = hashValues[i];
 
236
    iter.curr.p = (T*)thePool.getPtr(iter.curr.i);      // cast
 
237
    return true;
 
238
  } else {
 
239
    iter.curr.i = RNIL;
 
240
  }
 
241
  return false;
 
242
}
 
243
 
 
244
template<class T, class U>
 
245
inline
 
246
bool
 
247
DLHashTable2<T, U>::next(Iterator & iter) const {
 
248
  if(iter.curr.p->nextHash == RNIL){
 
249
    Uint32 i = iter.bucket + 1;
 
250
    while(i <= mask && hashValues[i] == RNIL) i++;
 
251
    if(i <= mask){
 
252
      iter.bucket = i;
 
253
      iter.curr.i = hashValues[i];
 
254
      iter.curr.p = (T*)thePool.getPtr(iter.curr.i);    // cast
 
255
      return true;
 
256
    } else {
 
257
      iter.curr.i = RNIL;
 
258
      return false;
 
259
    }
 
260
  }
 
261
  
 
262
  iter.curr.i = iter.curr.p->nextHash;
 
263
  iter.curr.p = (T*)thePool.getPtr(iter.curr.i);        // cast
 
264
  return true;
 
265
}
 
266
 
 
267
template<class T, class U>
 
268
inline
 
269
void
 
270
DLHashTable2<T, U>::remove(Ptr<T> & ptr, const T & key){
 
271
  const Uint32 hv = key.hashValue() & mask;  
 
272
  
 
273
  Uint32 i;
 
274
  T * p;
 
275
  Ptr<T> prev;
 
276
  prev.i = RNIL;
 
277
 
 
278
  i = hashValues[hv];
 
279
  while(i != RNIL){
 
280
    p = (T*)thePool.getPtr(i);  // cast
 
281
    if(key.equal(* p)){
 
282
      const Uint32 next = p->nextHash;
 
283
      if(prev.i == RNIL){
 
284
        hashValues[hv] = next;
 
285
      } else {
 
286
        prev.p->nextHash = next;
 
287
      }
 
288
      
 
289
      if(next != RNIL){
 
290
        T * nextP = (T*)thePool.getPtr(next);   // cast
 
291
        nextP->prevHash = prev.i;
 
292
      }
 
293
 
 
294
      ptr.i = i;
 
295
      ptr.p = p;
 
296
      return;
 
297
    }
 
298
    prev.p = p;
 
299
    prev.i = i;
 
300
    i = p->nextHash;
 
301
  }
 
302
  ptr.i = RNIL;
 
303
}
 
304
 
 
305
template<class T, class U>
 
306
inline
 
307
void
 
308
DLHashTable2<T, U>::release(Ptr<T> & ptr, const T & key){
 
309
  const Uint32 hv = key.hashValue() & mask;  
 
310
  
 
311
  Uint32 i;
 
312
  T * p;
 
313
  Ptr<T> prev;
 
314
  prev.i = RNIL;
 
315
 
 
316
  i = hashValues[hv];
 
317
  while(i != RNIL){
 
318
    p = (T*)thePool.getPtr(i);  // cast
 
319
    if(key.equal(* p)){
 
320
      const Uint32 next = p->nextHash;
 
321
      if(prev.i == RNIL){
 
322
        hashValues[hv] = next;
 
323
      } else {
 
324
        prev.p->nextHash = next;
 
325
      }
 
326
      
 
327
      if(next != RNIL){
 
328
        T * nextP = (T*)thePool.getPtr(next);   // cast
 
329
        nextP->prevHash = prev.i;
 
330
      }
 
331
 
 
332
      p->~T();  // dtor
 
333
      thePool.release(i);
 
334
      ptr.i = i;
 
335
      ptr.p = p;        // invalid
 
336
      return;
 
337
    }
 
338
    prev.p = p;
 
339
    prev.i = i;
 
340
    i = p->nextHash;
 
341
  }
 
342
  ptr.i = RNIL;
 
343
}
 
344
 
 
345
template<class T, class U>
 
346
inline
 
347
void
 
348
DLHashTable2<T, U>::remove(Uint32 i){
 
349
  Ptr<T> tmp;
 
350
  tmp.i = i;
 
351
  tmp.p = (T*)thePool.getPtr(i);        // cast
 
352
  remove(tmp);
 
353
}
 
354
 
 
355
template<class T, class U>
 
356
inline
 
357
void
 
358
DLHashTable2<T, U>::release(Uint32 i){
 
359
  Ptr<T> tmp;
 
360
  tmp.i = i;
 
361
  tmp.p = (T*)thePool.getPtr(i);        // cast
 
362
  release(tmp);
 
363
}
 
364
 
 
365
template<class T, class U>
 
366
inline
 
367
void 
 
368
DLHashTable2<T, U>::remove(Ptr<T> & ptr){
 
369
  const Uint32 next = ptr.p->nextHash;
 
370
  const Uint32 prev = ptr.p->prevHash;
 
371
 
 
372
  if(prev != RNIL){
 
373
    T * prevP = (T*)thePool.getPtr(prev);       // cast
 
374
    prevP->nextHash = next;
 
375
  } else {
 
376
    const Uint32 hv = ptr.p->hashValue() & mask;  
 
377
    if (hashValues[hv] == ptr.i)
 
378
    {
 
379
      hashValues[hv] = next;
 
380
    }
 
381
    else
 
382
    {
 
383
      // Will add assert in 5.1
 
384
    }
 
385
  }
 
386
  
 
387
  if(next != RNIL){
 
388
    T * nextP = (T*)thePool.getPtr(next);       // cast
 
389
    nextP->prevHash = prev;
 
390
  }
 
391
}
 
392
 
 
393
template<class T, class U>
 
394
inline
 
395
void 
 
396
DLHashTable2<T, U>::release(Ptr<T> & ptr){
 
397
  const Uint32 next = ptr.p->nextHash;
 
398
  const Uint32 prev = ptr.p->prevHash;
 
399
 
 
400
  if(prev != RNIL){
 
401
    T * prevP = (T*)thePool.getPtr(prev);       // cast
 
402
    prevP->nextHash = next;
 
403
  } else {
 
404
    const Uint32 hv = ptr.p->hashValue() & mask;  
 
405
    if (hashValues[hv] == ptr.i)
 
406
    {
 
407
      hashValues[hv] = next;
 
408
    }
 
409
    else
 
410
    {
 
411
      // Will add assert in 5.1
 
412
    }
 
413
  }
 
414
  
 
415
  if(next != RNIL){
 
416
    T * nextP = (T*)thePool.getPtr(next);       // cast
 
417
    nextP->prevHash = prev;
 
418
  }
 
419
  
 
420
  thePool.release(ptr.i);
 
421
}
 
422
 
 
423
template<class T, class U>
 
424
inline
 
425
void 
 
426
DLHashTable2<T, U>::removeAll(){
 
427
  for(Uint32 i = 0; i<=mask; i++)
 
428
    hashValues[i] = RNIL;
 
429
}
 
430
 
 
431
template<class T, class U>
 
432
inline
 
433
bool
 
434
DLHashTable2<T, U>::next(Uint32 bucket, Iterator & iter) const {
 
435
  while (bucket <= mask && hashValues[bucket] == RNIL) 
 
436
    bucket++; 
 
437
  
 
438
  if (bucket > mask) {
 
439
    iter.bucket = bucket;
 
440
    iter.curr.i = RNIL;
 
441
    return false;
 
442
  }
 
443
  
 
444
  iter.bucket = bucket;
 
445
  iter.curr.i = hashValues[bucket];
 
446
  iter.curr.p = (T*)thePool.getPtr(iter.curr.i);        // cast
 
447
  return true;
 
448
}
 
449
 
 
450
template<class T, class U>
 
451
inline
 
452
bool
 
453
DLHashTable2<T, U>::seize(Ptr<T> & ptr){
 
454
  Ptr<U> ptr2;
 
455
  thePool.seize(ptr2);
 
456
  ptr.i = ptr2.i;
 
457
  ptr.p = (T*)ptr2.p;   // cast
 
458
  if (ptr.p != NULL){
 
459
    ptr.p->nextHash = RNIL;
 
460
    ptr.p->prevHash = RNIL;
 
461
    new (ptr.p) T;      // ctor
 
462
  }
 
463
  return !ptr.isNull();
 
464
}
 
465
 
 
466
template<class T, class U>
 
467
inline
 
468
void
 
469
DLHashTable2<T, U>::getPtr(Ptr<T> & ptr, Uint32 i) const {
 
470
  ptr.i = i;
 
471
  ptr.p = (T*)thePool.getPtr(i);        // cast
 
472
}
 
473
 
 
474
template<class T, class U>
 
475
inline
 
476
void
 
477
DLHashTable2<T, U>::getPtr(Ptr<T> & ptr) const {
 
478
  Ptr<U> ptr2;
 
479
  thePool.getPtr(ptr2);
 
480
  ptr.i = ptr2.i;
 
481
  ptr.p = (T*)ptr2.p;   // cast
 
482
}
 
483
 
 
484
template<class T, class U>
 
485
inline
 
486
T * 
 
487
DLHashTable2<T, U>::getPtr(Uint32 i) const {
 
488
  return (T*)thePool.getPtr(i); // cast
 
489
}
 
490
 
 
491
template<class T, class U>
 
492
inline
 
493
bool
 
494
DLHashTable2<T, U>::find(Ptr<T> & ptr, const T & key) const {
 
495
  const Uint32 hv = key.hashValue() & mask;  
 
496
  
 
497
  Uint32 i;
 
498
  T * p;
 
499
 
 
500
  i = hashValues[hv];
 
501
  while(i != RNIL){
 
502
    p = (T*)thePool.getPtr(i);  // cast
 
503
    if(key.equal(* p)){
 
504
      ptr.i = i;
 
505
      ptr.p = p;
 
506
      return true;
 
507
    }
 
508
    i = p->nextHash;
 
509
  }
 
510
  ptr.i = RNIL;
 
511
  ptr.p = NULL;
 
512
  return false;
 
513
}
 
514
#endif