MySQL 5.6.14 Source Code Document
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
DLHashTable.hpp
1 /*
2  Copyright (C) 2003-2006, 2008 MySQL AB, 2009, 2010 Sun Microsystems, Inc.
3  All rights reserved. Use is subject to license terms.
4 
5  This program is free software; you can redistribute it and/or modify
6  it under the terms of the GNU General Public License as published by
7  the Free Software Foundation; version 2 of the License.
8 
9  This program is distributed in the hope that it will be useful,
10  but WITHOUT ANY WARRANTY; without even the implied warranty of
11  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  GNU General Public License for more details.
13 
14  You should have received a copy of the GNU General Public License
15  along with this program; if not, write to the Free Software
16  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
17 */
18 
19 #ifndef DL_HASHTABLE_HPP
20 #define DL_HASHTABLE_HPP
21 
22 #include <ndb_global.h>
23 #include "ArrayPool.hpp"
24 
35 template <typename P, typename T, typename U = T>
36 class DLHashTableImpl
37 {
38 public:
39  DLHashTableImpl(P & thePool);
40  ~DLHashTableImpl();
41 
47  bool setSize(Uint32 noOfElements);
48 
55  bool seize(Ptr<T> &);
56 
60  void add(Ptr<T> &);
61 
67  bool find(Ptr<T> &, const T & key) const;
68 
72  void getPtr(Ptr<T> &, Uint32 i) const;
73 
77  void getPtr(Ptr<T> &) const;
78 
82  T * getPtr(Uint32 i) const;
83 
88  void remove(Ptr<T> &, const T & key);
89 
94  void remove(Uint32 i);
95 
100  void remove(Ptr<T> &);
101 
105  void removeAll();
106 
110  void release(Uint32 i);
111 
115  void release(Ptr<T> &);
116 
117  class Iterator {
118  public:
119  Ptr<T> curr;
120  Uint32 bucket;
121  inline bool isNull() const { return curr.isNull();}
122  inline void setNull() { curr.setNull(); }
123  };
124 
128  void getPtr(Iterator & iter) const ;
129 
133  bool first(Iterator & iter) const;
134 
140  bool next(Iterator & iter) const;
141 
148  bool next(Uint32 bucket, Iterator & iter) const;
149 
150 private:
151  Uint32 mask;
152  Uint32 * hashValues;
153  P & thePool;
154 };
155 
156 template <typename P, typename T, typename U>
157 inline
158 DLHashTableImpl<P, T, U>::DLHashTableImpl(P & _pool)
159  : thePool(_pool)
160 {
161  // Require user defined constructor on T since we fiddle
162  // with T's members
163  ASSERT_TYPE_HAS_CONSTRUCTOR(T);
164 
165  mask = 0;
166  hashValues = 0;
167 }
168 
169 template <typename P, typename T, typename U>
170 inline
171 DLHashTableImpl<P, T, U>::~DLHashTableImpl()
172 {
173  if(hashValues != 0)
174  delete [] hashValues;
175 }
176 
177 template <typename P, typename T, typename U>
178 inline
179 bool
180 DLHashTableImpl<P, T, U>::setSize(Uint32 size)
181 {
182  Uint32 i = 1;
183  while(i < size) i *= 2;
184 
185  if(mask == (i - 1))
186  {
190  return true;
191  }
192 
193  if(mask != 0)
194  {
198  return false;
199  }
200 
201  mask = (i - 1);
202  hashValues = new Uint32[i];
203  for(Uint32 j = 0; j<i; j++)
204  hashValues[j] = RNIL;
205 
206  return true;
207 }
208 
209 template <typename P, typename T, typename U>
210 inline
211 void
212 DLHashTableImpl<P, T, U>::add(Ptr<T> & obj)
213 {
214  const Uint32 hv = obj.p->hashValue() & mask;
215  const Uint32 i = hashValues[hv];
216 
217  if(i == RNIL)
218  {
219  hashValues[hv] = obj.i;
220  obj.p->U::nextHash = RNIL;
221  obj.p->U::prevHash = RNIL;
222  }
223  else
224  {
225  T * tmp = thePool.getPtr(i);
226  tmp->U::prevHash = obj.i;
227  obj.p->U::nextHash = i;
228  obj.p->U::prevHash = RNIL;
229 
230  hashValues[hv] = obj.i;
231  }
232 }
233 
237 template <typename P, typename T, typename U>
238 inline
239 bool
240 DLHashTableImpl<P, T, U>::first(Iterator & iter) const
241 {
242  Uint32 i = 0;
243  while(i <= mask && hashValues[i] == RNIL) i++;
244  if(i <= mask)
245  {
246  iter.bucket = i;
247  iter.curr.i = hashValues[i];
248  iter.curr.p = thePool.getPtr(iter.curr.i);
249  return true;
250  }
251  else
252  {
253  iter.curr.i = RNIL;
254  }
255  return false;
256 }
257 
258 template <typename P, typename T, typename U>
259 inline
260 bool
261 DLHashTableImpl<P, T, U>::next(Iterator & iter) const
262 {
263  if(iter.curr.p->U::nextHash == RNIL)
264  {
265  Uint32 i = iter.bucket + 1;
266  while(i <= mask && hashValues[i] == RNIL) i++;
267  if(i <= mask)
268  {
269  iter.bucket = i;
270  iter.curr.i = hashValues[i];
271  iter.curr.p = thePool.getPtr(iter.curr.i);
272  return true;
273  }
274  else
275  {
276  iter.curr.i = RNIL;
277  return false;
278  }
279  }
280 
281  iter.curr.i = iter.curr.p->U::nextHash;
282  iter.curr.p = thePool.getPtr(iter.curr.i);
283  return true;
284 }
285 
286 template <typename P, typename T, typename U>
287 inline
288 void
289 DLHashTableImpl<P, T, U>::remove(Ptr<T> & ptr, const T & key)
290 {
291  const Uint32 hv = key.hashValue() & mask;
292 
293  Uint32 i;
294  T * p;
295  Ptr<T> prev;
296  LINT_INIT(prev.p);
297  prev.i = RNIL;
298 
299  i = hashValues[hv];
300  while(i != RNIL)
301  {
302  p = thePool.getPtr(i);
303  if(key.equal(* p))
304  {
305  const Uint32 next = p->U::nextHash;
306  if(prev.i == RNIL)
307  {
308  hashValues[hv] = next;
309  }
310  else
311  {
312  prev.p->U::nextHash = next;
313  }
314 
315  if(next != RNIL)
316  {
317  T * nextP = thePool.getPtr(next);
318  nextP->U::prevHash = prev.i;
319  }
320 
321  ptr.i = i;
322  ptr.p = p;
323  return;
324  }
325  prev.p = p;
326  prev.i = i;
327  i = p->U::nextHash;
328  }
329  ptr.i = RNIL;
330 }
331 
332 template <typename P, typename T, typename U>
333 inline
334 void
335 DLHashTableImpl<P, T, U>::remove(Uint32 i)
336 {
337  Ptr<T> tmp;
338  tmp.i = i;
339  tmp.p = thePool.getPtr(i);
340  remove(tmp);
341 }
342 
343 template <typename P, typename T, typename U>
344 inline
345 void
346 DLHashTableImpl<P, T, U>::release(Uint32 i)
347 {
348  Ptr<T> tmp;
349  tmp.i = i;
350  tmp.p = thePool.getPtr(i);
351  release(tmp);
352 }
353 
354 template <typename P, typename T, typename U>
355 inline
356 void
357 DLHashTableImpl<P, T, U>::remove(Ptr<T> & ptr)
358 {
359  const Uint32 next = ptr.p->U::nextHash;
360  const Uint32 prev = ptr.p->U::prevHash;
361 
362  if(prev != RNIL)
363  {
364  T * prevP = thePool.getPtr(prev);
365  prevP->U::nextHash = next;
366  }
367  else
368  {
369  const Uint32 hv = ptr.p->hashValue() & mask;
370  if (hashValues[hv] == ptr.i)
371  {
372  hashValues[hv] = next;
373  }
374  else
375  {
376  // Will add assert in 5.1
377  assert(false);
378  }
379  }
380 
381  if(next != RNIL)
382  {
383  T * nextP = thePool.getPtr(next);
384  nextP->U::prevHash = prev;
385  }
386 }
387 
388 template <typename P, typename T, typename U>
389 inline
390 void
391 DLHashTableImpl<P, T, U>::release(Ptr<T> & ptr)
392 {
393  const Uint32 next = ptr.p->U::nextHash;
394  const Uint32 prev = ptr.p->U::prevHash;
395 
396  if(prev != RNIL)
397  {
398  T * prevP = thePool.getPtr(prev);
399  prevP->U::nextHash = next;
400  }
401  else
402  {
403  const Uint32 hv = ptr.p->hashValue() & mask;
404  if (hashValues[hv] == ptr.i)
405  {
406  hashValues[hv] = next;
407  }
408  else
409  {
410  assert(false);
411  // Will add assert in 5.1
412  }
413  }
414 
415  if(next != RNIL)
416  {
417  T * nextP = thePool.getPtr(next);
418  nextP->U::prevHash = prev;
419  }
420 
421  thePool.release(ptr);
422 }
423 
424 template <typename P, typename T, typename U>
425 inline
426 void
427 DLHashTableImpl<P, T, U>::removeAll()
428 {
429  for(Uint32 i = 0; i<=mask; i++)
430  hashValues[i] = RNIL;
431 }
432 
433 template <typename P, typename T, typename U>
434 inline
435 bool
436 DLHashTableImpl<P, T, U>::next(Uint32 bucket, Iterator & iter) const
437 {
438  while (bucket <= mask && hashValues[bucket] == RNIL)
439  bucket++;
440 
441  if (bucket > mask)
442  {
443  iter.bucket = bucket;
444  iter.curr.i = RNIL;
445  return false;
446  }
447 
448  iter.bucket = bucket;
449  iter.curr.i = hashValues[bucket];
450  iter.curr.p = thePool.getPtr(iter.curr.i);
451  return true;
452 }
453 
454 template <typename P, typename T, typename U>
455 inline
456 bool
457 DLHashTableImpl<P, T, U>::seize(Ptr<T> & ptr)
458 {
459  if(thePool.seize(ptr)){
460  ptr.p->U::nextHash = ptr.p->U::prevHash = RNIL;
461  return true;
462  }
463  return false;
464 }
465 
466 template <typename P, typename T, typename U>
467 inline
468 void
469 DLHashTableImpl<P, T, U>::getPtr(Ptr<T> & ptr, Uint32 i) const
470 {
471  ptr.i = i;
472  ptr.p = thePool.getPtr(i);
473 }
474 
475 template <typename P, typename T, typename U>
476 inline
477 void
478 DLHashTableImpl<P, T, U>::getPtr(Ptr<T> & ptr) const
479 {
480  thePool.getPtr(ptr);
481 }
482 
483 template <typename P, typename T, typename U>
484 inline
485 T *
486 DLHashTableImpl<P, T, U>::getPtr(Uint32 i) const
487 {
488  return thePool.getPtr(i);
489 }
490 
491 template <typename P, typename T, typename U>
492 inline
493 bool
494 DLHashTableImpl<P, T, U>::find(Ptr<T> & ptr, const T & key) const
495 {
496  const Uint32 hv = key.hashValue() & mask;
497 
498  Uint32 i;
499  T * p;
500 
501  i = hashValues[hv];
502  while(i != RNIL)
503  {
504  p = thePool.getPtr(i);
505  if(key.equal(* p))
506  {
507  ptr.i = i;
508  ptr.p = p;
509  return true;
510  }
511  i = p->U::nextHash;
512  }
513  ptr.i = RNIL;
514  ptr.p = NULL;
515  return false;
516 }
517 
518 // Specializations
519 
520 template <typename T, typename U = T>
521 class DLHashTable : public DLHashTableImpl<ArrayPool<T>, T, U>
522 {
523 public:
524  DLHashTable(ArrayPool<T> & p) : DLHashTableImpl<ArrayPool<T>, T, U>(p) {}
525 };
526 
527 #endif