93 return *(Titem_*)NULL; |
93 return *(Titem_*)NULL; |
94 } |
94 } |
95 }; |
95 }; |
96 |
96 |
97 /** @class CHashTableT<Titem, Thash_bits> - simple hash table |
97 /** @class CHashTableT<Titem, Thash_bits> - simple hash table |
98 of pointers allocated elsewhere. |
98 * of pointers allocated elsewhere. |
99 |
99 * |
100 Supports: Add/Find/Remove of Titems. |
100 * Supports: Add/Find/Remove of Titems. |
101 |
101 * |
102 Your Titem must meet some extra requirements to be CHashTableT |
102 * Your Titem must meet some extra requirements to be CHashTableT |
103 compliant: |
103 * compliant: |
104 - its constructor/destructor (if any) must be public |
104 * - its constructor/destructor (if any) must be public |
105 - if the copying of item requires an extra resource management, |
105 * - if the copying of item requires an extra resource management, |
106 you must define also copy constructor |
106 * you must define also copy constructor |
107 - must support nested type (struct, class or typedef) Titem::Key |
107 * - must support nested type (struct, class or typedef) Titem::Key |
108 that defines the type of key class for that item |
108 * that defines the type of key class for that item |
109 - must support public method: |
109 * - must support public method: |
110 const Key& GetKey() const; // return the item's key object |
110 * const Key& GetKey() const; // return the item's key object |
111 |
111 * |
112 In addition, the Titem::Key class must support: |
112 * In addition, the Titem::Key class must support: |
113 - public method that calculates key's hash: |
113 * - public method that calculates key's hash: |
114 int CalcHash() const; |
114 * int CalcHash() const; |
115 - public 'equality' operator to compare the key with another one |
115 * - public 'equality' operator to compare the key with another one |
116 bool operator == (const Key& other) const; |
116 * bool operator == (const Key& other) const; |
117 */ |
117 */ |
118 template <class Titem_, int Thash_bits_> |
118 template <class Titem_, int Thash_bits_> |
119 class CHashTableT { |
119 class CHashTableT { |
120 public: |
120 public: |
121 typedef Titem_ Titem; // make Titem_ visible from outside of class |
121 typedef Titem_ Titem; // make Titem_ visible from outside of class |
122 typedef typename Titem_::Key Tkey; // make Titem_::Key a property of HashTable |
122 typedef typename Titem_::Key Tkey; // make Titem_::Key a property of HashTable |
123 ST_CONST(int, Thash_bits = Thash_bits_); // publish num of hash bits |
123 ST_CONST(int, Thash_bits = Thash_bits_); // publish num of hash bits |
124 ST_CONST(int, Tcapacity = 1 << Thash_bits); // and num of slots 2^bits |
124 ST_CONST(int, Tcapacity = 1 << Thash_bits); // and num of slots 2^bits |
125 |
125 |
126 protected: |
126 protected: |
127 /** each slot contains pointer to the first item in the list, |
127 /** each slot contains pointer to the first item in the list, |
128 Titem contains pointer to the next item - GetHashNext(), SetHashNext() */ |
128 * Titem contains pointer to the next item - GetHashNext(), SetHashNext() */ |
129 typedef CHashTableSlotT<Titem_> Slot; |
129 typedef CHashTableSlotT<Titem_> Slot; |
130 |
130 |
131 Slot* m_slots; // here we store our data (array of blobs) |
131 Slot* m_slots; // here we store our data (array of blobs) |
132 int m_num_items; // item counter |
132 int m_num_items; // item counter |
133 |
133 |