Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. #if !defined(HASH_TABLE_H)
  2. #define HASH_TABLE_H
  3.  
  4. template <class T, class TypeString, class HashFunction>
  5. class THashTable
  6. {
  7. public:
  8.    THashTable(int _m = -1) {MemInit(_m);}
  9.    ~THashTable() {null();}
  10.  
  11.    int hash1(const TypeString &x) const {return func1(x);}
  12.    int hash2(const TypeString &x) const {return 2*func2(x) + 1;}
  13.  
  14.    void null();
  15.    int IsNull() const {return M >= 0;}
  16.    int NumElem() const {return n;}
  17.    int MaxNumElem() const {return stack_size;}
  18.    int GetM() const {return M;}
  19.    int TableSize() const {return 1 << M;}
  20.  
  21.    void resize(int _m);
  22.    void push(const T &x);
  23.    T *find(const TypeString &x);
  24.    void pop();
  25.  
  26.    T &last() {return stack[n-1];}
  27.    const T &last() const {return stack[n-1];}
  28.    T &first() {return stack[0];}
  29.    const T &first() const {return stack[0];}
  30.    T &operator[](int i) {return stack[i];}
  31.    const T &operator[](int i) const {return stack[i];}
  32.    T *operator()() {return stack;}
  33.    const T *operator()() const {return stack;}
  34. protected:
  35.    void _push(const T &x);
  36.    int _find_pointer(const T *p) const;
  37.    int _find(const TypeString &x) const;
  38.    void MemInit(int _m);
  39. protected:
  40.    int M;
  41.    int stack_size;
  42.    int n;
  43.    T **table;
  44.    T *stack;
  45. protected:
  46.    HashFunction func1, func2;
  47. };
  48.  
  49. template <class T, class TypeString, class HashFunction>
  50. void THashTable<T, TypeString, HashFunction>::null()
  51. {
  52.   if (table) delete[] table;
  53.   if (stack) delete[] stack;
  54.   M = -1;
  55.   table = 0;
  56.   stack = 0;
  57.   stack_size = 0;
  58.   n = 0;
  59.   func1.init(-1);
  60.   func2.init(-1);
  61. }
  62.  
  63. template <class T, class TypeString, class HashFunction>
  64. void THashTable<T, TypeString, HashFunction>::resize(int _m)
  65. {
  66.   delete[] table;
  67.   T *stp = stack;
  68.   int np = n;
  69.   MemInit(_m);
  70.   for (int i = 0; i < np && n < stack_size; i++) _push(stp[i]);
  71.   if (stp) delete[] stp;
  72. }
  73.  
  74. template <class T, class TypeString, class HashFunction>
  75. inline void THashTable<T, TypeString, HashFunction>::push(const T &x)
  76. {
  77.   if (n == stack_size) resize(M + 1);
  78.   _push(x);
  79. }
  80.  
  81. template <class T, class TypeString, class HashFunction>
  82. inline T *THashTable<T, TypeString, HashFunction>::find(const TypeString &x)
  83. {
  84.   int i = _find(x);
  85.   if (i >= 0) return table[i];
  86.   else return 0;
  87. }
  88.  
  89. template <class T, class TypeString, class HashFunction>
  90. inline void THashTable<T, TypeString, HashFunction>::pop()
  91. {
  92.   if (n > 0)
  93.   {
  94.     n--;
  95.     int i = _find_pointer(stack + n);
  96.     if (i >= 0) table[i] = NULL;
  97.   }
  98. }
  99.  
  100. template <class T, class TypeString, class HashFunction>
  101. void THashTable<T, TypeString, HashFunction>::_push(const T &x)
  102. {
  103.   int h1 = hash1(x);
  104.   int h2 = hash2(x);
  105.   int i = h1;
  106.   stack[n] = x;
  107.   do
  108.   {
  109.     if (table[i] == NULL)
  110.     {
  111.       table[i] = stack + n;
  112.       break;
  113.     }
  114.     i = (i + h2) & ((1 << M) - 1);
  115.   }
  116.   while (i != h1);
  117.   n++;
  118. }
  119.  
  120. template <class T, class TypeString, class HashFunction>
  121. int THashTable<T, TypeString, HashFunction>::_find_pointer(const T *p) const
  122. {
  123.   if (n > 0)
  124.   {
  125.     int h1 = hash1(*p);
  126.     int h2 = hash2(*p);
  127.     int i = h1;
  128.     do
  129.     {
  130.       if (table[i] == NULL) break;
  131.       if (table[i] == p) return i;
  132.       i = (i + h2) & ((1 << M) - 1);
  133.     }
  134.     while (i != h1);
  135.   }
  136.   return -1;
  137. }
  138.  
  139. template <class T, class TypeString, class HashFunction>
  140. int THashTable<T, TypeString, HashFunction>::_find(const TypeString &x) const
  141. {
  142.   if (n > 0)
  143.   {
  144.     int h1 = hash1(x);
  145.     int h2 = hash2(x);
  146.     int i = h1;
  147.     do
  148.     {
  149.       if (table[i] == NULL) break;
  150.       if ((*table[i]) == x) return i;
  151.       i = (i + h2) & ((1 << M) - 1);
  152.     }
  153.     while (i != h1);
  154.   }
  155.   return -1;
  156. }
  157.  
  158. template <class T, class TypeString, class HashFunction>
  159. void THashTable<T, TypeString, HashFunction>::MemInit(int _m)
  160. {
  161.   M = _m;
  162.   if (M < 0)
  163.   {
  164.     M = -1;
  165.     stack_size = 0;
  166.     table = 0;
  167.     stack = 0;
  168.     n = 0;
  169.     func1.init(-1);
  170.     func2.init(-1);
  171.   }
  172.   else
  173.   {
  174.     if (M < 3) M = 3;
  175.     stack_size = (1 << M) / 3;
  176.     table = new T*[1 << M];
  177.     for (int i = 0; i < (1 << M); i++) table[i] = NULL;
  178.     stack = new T[stack_size];
  179.     n = 0;
  180.     func1.init(M);
  181.     func2.init(M-1);
  182.   }
  183. }
  184.  
  185. #endif  // HASH_TABLE_H
  186.