DLHashTable.hpp
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:9k
源码类别:

MySQL数据库

开发平台:

Visual C++

  1. /* Copyright (C) 2003 MySQL AB
  2.    This program is free software; you can redistribute it and/or modify
  3.    it under the terms of the GNU General Public License as published by
  4.    the Free Software Foundation; either version 2 of the License, or
  5.    (at your option) any later version.
  6.    This program is distributed in the hope that it will be useful,
  7.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  8.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  9.    GNU General Public License for more details.
  10.    You should have received a copy of the GNU General Public License
  11.    along with this program; if not, write to the Free Software
  12.    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
  13. #ifndef DL_HASHTABLE_HPP
  14. #define DL_HASHTABLE_HPP
  15. #include <ndb_global.h>
  16. #include "ArrayList.hpp"
  17. /**
  18.  * DLHashTable implements a hashtable using chaining
  19.  *   (with a double linked list)
  20.  *
  21.  * The entries in the hashtable must have the following methods:
  22.  *  -# bool equal(const class T &) const;
  23.  *     Which should return equal if the to objects have the same key
  24.  *  -# Uint32 hashValue() const;
  25.  *     Which should return a 32 bit hashvalue
  26.  */
  27. template <class T>
  28. class DLHashTable {
  29. public:
  30.   DLHashTable(ArrayPool<T> & thePool);
  31.   ~DLHashTable();
  32.   
  33.   /**
  34.    * Set the no of bucket in the hashtable
  35.    *
  36.    * Note, can currently only be called once
  37.    */
  38.   bool setSize(Uint32 noOfElements);
  39.   /**
  40.    * Seize element from pool - return i
  41.    *
  42.    * Note must be either added using <b>add</b> or released 
  43.    * using <b>release</b>
  44.    */
  45.   bool seize(Ptr<T> &);
  46.   /**
  47.    * Add an object to the hashtable
  48.    */
  49.   void add(Ptr<T> &);
  50.   
  51.   /**
  52.    * Find element key in hashtable update Ptr (i & p) 
  53.    *   (using key.equal(...))
  54.    * @return true if found and false otherwise
  55.    */
  56.   bool find(Ptr<T> &, const T & key) const;
  57.   /**
  58.    * Update i & p value according to <b>i</b>
  59.    */
  60.   void getPtr(Ptr<T> &, Uint32 i) const;
  61.   /**
  62.    * Get element using ptr.i (update ptr.p)
  63.    */
  64.   void getPtr(Ptr<T> &) const;
  65.   /**
  66.    * Get P value for i
  67.    */
  68.   T * getPtr(Uint32 i) const;
  69.   /**
  70.    * Remove element (and set Ptr to removed element)
  71.    * Note does not return to pool
  72.    */
  73.   void remove(Ptr<T> &, const T & key);
  74.   /**
  75.    * Remove element
  76.    * Note does not return to pool
  77.    */
  78.   void remove(Uint32 i);
  79.   /**
  80.    * Remove element
  81.    * Note does not return to pool
  82.    */
  83.   void remove(Ptr<T> &);
  84.   /**
  85.    * Remove all elements, but dont return them to pool
  86.    */
  87.   void removeAll();
  88.   
  89.   /**
  90.    * Remove element (and set Ptr to removed element)
  91.    * And return element to pool
  92.    */
  93.   void release(Ptr<T> &, const T & key);
  94.   /**
  95.    * Remove element and return to pool
  96.    */
  97.   void release(Uint32 i);
  98.   /**
  99.    * Remove element and return to pool
  100.    */
  101.   void release(Ptr<T> &);
  102.   
  103.   class Iterator {
  104.   public:
  105.     Ptr<T> curr;
  106.     Uint32 bucket;
  107.     inline bool isNull() const { return curr.isNull();}
  108.     inline void setNull() { curr.setNull(); }
  109.   };
  110.   /**
  111.    * Sets curr.p according to curr.i
  112.    */
  113.   void getPtr(Iterator & iter) const ;
  114.   /**
  115.    * First element in bucket
  116.    */
  117.   bool first(Iterator & iter) const;
  118.   
  119.   /**
  120.    * Next Element
  121.    *
  122.    * param iter - A "fully set" iterator
  123.    */
  124.   bool next(Iterator & iter) const;
  125.   /**
  126.    * Get next element starting from bucket
  127.    *
  128.    * @param bucket - Which bucket to start from
  129.    * @param iter - An "uninitialized" iterator
  130.    */
  131.   bool next(Uint32 bucket, Iterator & iter) const;
  132.   
  133. private:
  134.   Uint32 mask;
  135.   Uint32 * hashValues;
  136.   ArrayPool<T> & thePool;
  137. };
  138. template<class T>
  139. inline
  140. DLHashTable<T>::DLHashTable(ArrayPool<T> & _pool)
  141.   : thePool(_pool)
  142. {
  143.   mask = 0;
  144.   hashValues = 0;
  145. }
  146. template<class T>
  147. inline
  148. DLHashTable<T>::~DLHashTable(){
  149.   if(hashValues != 0)
  150.     delete [] hashValues;
  151. }
  152. template<class T>
  153. inline
  154. bool
  155. DLHashTable<T>::setSize(Uint32 size){
  156.   Uint32 i = 1;
  157.   while(i < size) i *= 2;
  158.   if(mask == (i - 1)){
  159.     /**
  160.      * The size is already set to <b>size</b>
  161.      */
  162.     return true;
  163.   }
  164.   if(mask != 0){
  165.     /**
  166.      * The mask is already set
  167.      */
  168.     return false;
  169.   }
  170.   
  171.   mask = (i - 1);
  172.   hashValues = new Uint32[i];
  173.   for(Uint32 j = 0; j<i; j++)
  174.     hashValues[j] = RNIL;
  175.   
  176.   return true;
  177. }
  178. template<class T>
  179. inline
  180. void
  181. DLHashTable<T>::add(Ptr<T> & obj){
  182.   const Uint32 hv = obj.p->hashValue() & mask;
  183.   const Uint32 i  = hashValues[hv];
  184.   
  185.   if(i == RNIL){
  186.     hashValues[hv] = obj.i;
  187.     obj.p->nextHash = RNIL;
  188.     obj.p->prevHash = RNIL;
  189.   } else {
  190.     
  191.     T * tmp = thePool.getPtr(i);
  192.     tmp->prevHash = obj.i;
  193.     obj.p->nextHash = i;
  194.     obj.p->prevHash = RNIL;
  195.     
  196.     hashValues[hv] = obj.i;
  197.   }
  198. }
  199. /**
  200.  * First element
  201.  */
  202. template<class T>
  203. inline
  204. bool
  205. DLHashTable<T>::first(Iterator & iter) const {
  206.   Uint32 i = 0;
  207.   while(i <= mask && hashValues[i] == RNIL) i++;
  208.   if(i <= mask){
  209.     iter.bucket = i;
  210.     iter.curr.i = hashValues[i];
  211.     iter.curr.p = thePool.getPtr(iter.curr.i);
  212.     return true;
  213.   } else {
  214.     iter.curr.i = RNIL;
  215.   }
  216.   return false;
  217. }
  218. template<class T>
  219. inline
  220. bool
  221. DLHashTable<T>::next(Iterator & iter) const {
  222.   if(iter.curr.p->nextHash == RNIL){
  223.     Uint32 i = iter.bucket + 1;
  224.     while(i <= mask && hashValues[i] == RNIL) i++;
  225.     if(i <= mask){
  226.       iter.bucket = i;
  227.       iter.curr.i = hashValues[i];
  228.       iter.curr.p = thePool.getPtr(iter.curr.i);
  229.       return true;
  230.     } else {
  231.       iter.curr.i = RNIL;
  232.       return false;
  233.     }
  234.   }
  235.   
  236.   iter.curr.i = iter.curr.p->nextHash;
  237.   iter.curr.p = thePool.getPtr(iter.curr.i);
  238.   return true;
  239. }
  240. template<class T>
  241. inline
  242. void
  243. DLHashTable<T>::remove(Ptr<T> & ptr, const T & key){
  244.   const Uint32 hv = key.hashValue() & mask;  
  245.   
  246.   Uint32 i;
  247.   T * p;
  248.   Ptr<T> prev;
  249.   prev.i = RNIL;
  250.   i = hashValues[hv];
  251.   while(i != RNIL){
  252.     p = thePool.getPtr(i);
  253.     if(key.equal(* p)){
  254.       const Uint32 next = p->nextHash;
  255.       if(prev.i == RNIL){
  256. hashValues[hv] = next;
  257.       } else {
  258. prev.p->nextHash = next;
  259.       }
  260.       
  261.       if(next != RNIL){
  262. T * nextP = thePool.getPtr(next);
  263. nextP->prevHash = prev.i;
  264.       }
  265.       ptr.i = i;
  266.       ptr.p = p;
  267.       return;
  268.     }
  269.     prev.p = p;
  270.     prev.i = i;
  271.     i = p->nextHash;
  272.   }
  273.   ptr.i = RNIL;
  274. }
  275. template<class T>
  276. inline
  277. void
  278. DLHashTable<T>::release(Ptr<T> & ptr, const T & key){
  279.   const Uint32 hv = key.hashValue() & mask;  
  280.   
  281.   Uint32 i;
  282.   T * p;
  283.   Ptr<T> prev;
  284.   prev.i = RNIL;
  285.   i = hashValues[hv];
  286.   while(i != RNIL){
  287.     p = thePool.getPtr(i);
  288.     if(key.equal(* p)){
  289.       const Uint32 next = p->nextHash;
  290.       if(prev.i == RNIL){
  291. hashValues[hv] = next;
  292.       } else {
  293. prev.p->nextHash = next;
  294.       }
  295.       
  296.       if(next != RNIL){
  297. T * nextP = thePool.getPtr(next);
  298. nextP->prevHash = prev.i;
  299.       }
  300.       thePool.release(i);
  301.       ptr.i = i;
  302.       ptr.p = p;
  303.       return;
  304.     }
  305.     prev.p = p;
  306.     prev.i = i;
  307.     i = p->nextHash;
  308.   }
  309.   ptr.i = RNIL;
  310. }
  311. template<class T>
  312. inline
  313. void
  314. DLHashTable<T>::remove(Uint32 i){
  315.   Ptr<T> tmp;
  316.   tmp.i = i;
  317.   tmp.p = thePool.getPtr(i);
  318.   remove(tmp);
  319. }
  320. template<class T>
  321. inline
  322. void
  323. DLHashTable<T>::release(Uint32 i){
  324.   Ptr<T> tmp;
  325.   tmp.i = i;
  326.   tmp.p = thePool.getPtr(i);
  327.   release(tmp);
  328. }
  329. template<class T>
  330. inline
  331. void 
  332. DLHashTable<T>::remove(Ptr<T> & ptr){
  333.   const Uint32 next = ptr.p->nextHash;
  334.   const Uint32 prev = ptr.p->prevHash;
  335.   if(prev != RNIL){
  336.     T * prevP = thePool.getPtr(prev);
  337.     prevP->nextHash = next;
  338.   } else {
  339.     const Uint32 hv = ptr.p->hashValue() & mask;  
  340.     hashValues[hv] = next;
  341.   }
  342.   
  343.   if(next != RNIL){
  344.     T * nextP = thePool.getPtr(next);
  345.     nextP->prevHash = prev;
  346.   }
  347. }
  348. template<class T>
  349. inline
  350. void 
  351. DLHashTable<T>::release(Ptr<T> & ptr){
  352.   const Uint32 next = ptr.p->nextHash;
  353.   const Uint32 prev = ptr.p->prevHash;
  354.   if(prev != RNIL){
  355.     T * prevP = thePool.getPtr(prev);
  356.     prevP->nextHash = next;
  357.   } else {
  358.     const Uint32 hv = ptr.p->hashValue() & mask;  
  359.     hashValues[hv] = next;
  360.   }
  361.   
  362.   if(next != RNIL){
  363.     T * nextP = thePool.getPtr(next);
  364.     nextP->prevHash = prev;
  365.   }
  366.   
  367.   thePool.release(ptr.i);
  368. }
  369. template<class T>
  370. inline
  371. void 
  372. DLHashTable<T>::removeAll(){
  373.   for(Uint32 i = 0; i<=mask; i++)
  374.     hashValues[i] = RNIL;
  375. }
  376. template<class T>
  377. inline
  378. bool
  379. DLHashTable<T>::next(Uint32 bucket, Iterator & iter) const {
  380.   while (bucket <= mask && hashValues[bucket] == RNIL) 
  381.     bucket++; 
  382.   
  383.   if (bucket > mask) {
  384.     iter.bucket = bucket;
  385.     iter.curr.i = RNIL;
  386.     return false;
  387.   }
  388.   
  389.   iter.bucket = bucket;
  390.   iter.curr.i = hashValues[bucket];
  391.   iter.curr.p = thePool.getPtr(iter.curr.i);
  392.   return true;
  393. }
  394. template<class T>
  395. inline
  396. bool
  397. DLHashTable<T>::seize(Ptr<T> & ptr){
  398.   if(thePool.seize(ptr)){
  399.     ptr.p->nextHash = ptr.p->prevHash = RNIL;
  400.     return true;
  401.   }
  402.   return false;
  403. }
  404. template<class T>
  405. inline
  406. void
  407. DLHashTable<T>::getPtr(Ptr<T> & ptr, Uint32 i) const {
  408.   ptr.i = i;
  409.   ptr.p = thePool.getPtr(i);
  410. }
  411. template<class T>
  412. inline
  413. void
  414. DLHashTable<T>::getPtr(Ptr<T> & ptr) const {
  415.   thePool.getPtr(ptr);
  416. }
  417. template<class T>
  418. inline
  419. T * 
  420. DLHashTable<T>::getPtr(Uint32 i) const {
  421.   return thePool.getPtr(i);
  422. }
  423. template<class T>
  424. inline
  425. bool
  426. DLHashTable<T>::find(Ptr<T> & ptr, const T & key) const {
  427.   const Uint32 hv = key.hashValue() & mask;  
  428.   
  429.   Uint32 i;
  430.   T * p;
  431.   i = hashValues[hv];
  432.   while(i != RNIL){
  433.     p = thePool.getPtr(i);
  434.     if(key.equal(* p)){
  435.       ptr.i = i;
  436.       ptr.p = p;
  437.       return true;
  438.     }
  439.     i = p->nextHash;
  440.   }
  441.   ptr.i = RNIL;
  442.   ptr.p = NULL;
  443.   return false;
  444. }
  445. #endif