VC CQHashNTBuffer 牛逼的Hash表 UINT32

  1 #pragma once
  2 
  3 #include "Afxmt.h"
  4 
  5 class CQHashNTNode 
  6 {
  7 public:
  8     CQHashNTNode()
  9     {
 10         m_nKeyData = 0;
 11         m_pValueData = NULL;
 12         m_nValueLength = 0;
 13         m_pNext = NULL;
 14         m_nValueSize = 0;
 15     }
 16     CQHashNTNode(UINT32 nKeyData)
 17     {
 18         m_nKeyData = nKeyData;
 19         m_pValueData = NULL;
 20         m_nValueLength = 0;
 21         m_pNext = NULL;
 22         m_nValueSize = 0;
 23     }
 24     CQHashNTNode(UINT32 nKeyData, PUINT8 pValueData, UINT32 nValueLength)
 25     {
 26         m_nKeyData = nKeyData;
 27         m_pValueData = NULL;
 28         m_nValueLength = 0;
 29         m_pNext = NULL;
 30         m_nValueSize = 0;    
 31         if (nValueLength > 0)
 32         {
 33             m_nValueSize = max(64, nValueLength + 32);
 34             m_pValueData = new UINT8[m_nValueSize];
 35             if (pValueData != NULL)
 36             {
 37                 memcpy(m_pValueData, pValueData, nValueLength);
 38                 m_nValueLength = nValueLength;
 39             }
 40         }
 41     }
 42     virtual ~CQHashNTNode()
 43     {
 44         if (m_pValueData != NULL)
 45         {
 46             delete[] m_pValueData;
 47             m_pValueData = NULL;
 48         }
 49     }
 50     
 51 public:
 52     VOID SetValue(PUINT8 pValueData, UINT32 nValueLength)
 53     {
 54         m_nValueLength = nValueLength;
 55         if (m_nValueSize <= nValueLength)
 56         {            
 57             m_nValueSize = max(64, nValueLength + 32);
 58             delete[] m_pValueData;
 59             m_pValueData = new UINT8[m_nValueSize];
 60         }
 61         if (pValueData != NULL)
 62         {
 63             memcpy(m_pValueData, pValueData, nValueLength);
 64         }
 65     }
 66     
 67     VOID SetValue(UINT32 nKeyData)
 68     {
 69         m_nKeyData = nKeyData;
 70     }
 71     
 72     VOID GetValue(PUINT8 & pValueData, UINT32 & nValueSize, UINT32 & nValueLength)
 73     {
 74         if (pValueData == NULL)
 75         {
 76             nValueSize = m_nValueLength + 32;
 77             pValueData = new UINT8[nValueSize];
 78         }
 79         if (nValueSize < m_nValueLength)
 80         {
 81             delete[] pValueData;
 82             pValueData = NULL;
 83             nValueSize = m_nValueLength + 32;
 84             pValueData = new UINT8[nValueSize];
 85         }
 86         memcpy(pValueData, m_pValueData, m_nValueLength);
 87         nValueLength = m_nValueLength;
 88     }
 89     
 90     VOID GetValue(UINT32 & nKeyData)
 91     {
 92         nKeyData = m_nKeyData;
 93     }
 94     
 95     
 96 public:
 97     VOID AddTailValue(UINT8 nValueByte)
 98     {
 99         if (m_pValueData == NULL)
100         {
101             m_nValueSize = 64;
102             m_pValueData = new UINT8[m_nValueSize]; 
103             m_nValueLength = 0;
104         }
105         else if (m_nValueLength >= m_nValueSize)
106         {
107             m_nValueSize = m_nValueLength + 64;
108             PUINT8 pBuffer = new UINT8[m_nValueSize]; 
109             memcpy(pBuffer, m_pValueData, m_nValueLength);
110             delete [] m_pValueData;
111             m_pValueData = pBuffer;
112         }
113         m_pValueData[m_nValueLength++] = nValueByte;
114     }
115     
116     
117 public:
118     BOOL EqualKey(UINT32 nKeyData)
119     {
120         return (nKeyData == m_nKeyData);
121     }
122 
123 public:
124     UINT32 GetHashCode()
125     {
126         return (m_nKeyData & 0x7fffffff);
127     }
128 
129 public:
130     static UINT32 GetHashCode(UINT32 nKeyData)
131     {
132         return (nKeyData & 0x7fffffff);
133     }
134 
135 public:
136     UINT32 m_nKeyData;
137     PUINT8 m_pValueData;
138     UINT32 m_nValueLength;
139     CQHashNTNode * m_pNext;
140 
141 public:
142     UINT32 m_nValueSize;
143 };
144 
145 typedef CQHashNTNode* CQHashNTNodePtr;
146 
147 class CQHashNTBuffer 
148 {
149 private:
150     CQHashNTNodePtr * m_pHashTable;
151     UINT32 m_nTableSize;
152     UINT32 m_nNodeCount;
153     UINT32 m_nCurrentIndex;
154     CQHashNTNode * m_pCurrentNode;
155 
156 public:
157     CQHashNTBuffer()
158     {
159         m_nNodeCount = 0;
160         m_nTableSize = 0;
161         m_pHashTable = NULL;
162     }
163     CQHashNTBuffer(UINT32 nHashSize)
164     {
165         m_nNodeCount = 0;
166         m_nTableSize = nHashSize;
167         m_pHashTable = new CQHashNTNodePtr[nHashSize]();
168         for (int x = 0; x < nHashSize; x++)
169         {
170             m_pHashTable[x] = NULL;
171         }
172     }
173     virtual ~CQHashNTBuffer()
174     {
175         CQHashNTNode *pNode = NULL;
176         CQHashNTNode *pTemp = NULL;
177         for (int x = 0; x < m_nTableSize; x++)
178         {
179             pNode = m_pHashTable[x];
180             while (pNode)
181             {
182                 pTemp = pNode;
183                 pNode = pNode->m_pNext;
184                 delete pTemp;
185             }
186         }
187         delete[] m_pHashTable;
188     }
189 
190 public:
191     BOOL Lookup(UINT32 nKeyData, PUINT8 & pValueData, UINT32 & nValueSize, UINT32 & nValueLength)
192     {
193         BOOL bResult = FALSE;
194         UINT32 nIndex = CQHashNTNode::GetHashCode(nKeyData) % m_nTableSize;
195         if (m_pHashTable[nIndex] != NULL)
196         {
197             CQHashNTNode * pNode = m_pHashTable[nIndex];
198             while (pNode)
199             {
200                 if (pNode->EqualKey(nKeyData))
201                 {
202                     pNode->GetValue(pValueData, nValueSize, nValueLength);
203                     bResult = TRUE;
204                     break;
205                 }
206                 pNode = pNode->m_pNext;
207             }
208         }
209         return bResult;
210     }
211     BOOL Lookup(UINT32 nKeyData, CQHashNTNode * pValueData)
212     {
213         BOOL bResult = FALSE;
214         UINT32 nIndex = CQHashNTNode::GetHashCode(nKeyData) % m_nTableSize;
215         if (m_pHashTable[nIndex] != NULL)
216         {
217             CQHashNTNode * pNode = m_pHashTable[nIndex];
218             while (pNode)
219             {
220                 if (pNode->EqualKey(nKeyData))
221                 {
222                     pNode->GetValue(pValueData->m_pValueData, pValueData->m_nValueSize, pValueData->m_nValueLength);
223                     bResult = TRUE;
224                     break;
225                 }
226                 pNode = pNode->m_pNext;
227             }
228         }
229         return bResult;
230     }
231     BOOL Contains(UINT32 nKeyData) 
232     {
233         BOOL bResult = FALSE;
234         UINT32 nIndex = CQHashNTNode::GetHashCode(nKeyData) % m_nTableSize;
235         if (m_pHashTable[nIndex] != NULL)
236         {
237             CQHashNTNode * pNode = m_pHashTable[nIndex];
238             while (pNode)
239             {
240                 if (pNode->EqualKey(nKeyData))
241                 {
242                     bResult = TRUE;
243                     break;
244                 }
245                 pNode = pNode->m_pNext;
246             }
247         }
248         return bResult;
249     }
250     VOID SetAt(UINT32 nKeyData, PUINT8 pValueData, UINT32 nValueLength)
251     {
252         UINT32 nIndex = CQHashNTNode::GetHashCode(nKeyData) % m_nTableSize;
253         if (m_pHashTable[nIndex] != NULL)
254         {            
255             BOOL bFind = FALSE;
256             CQHashNTNode * pNode = m_pHashTable[nIndex];
257             while (pNode)
258             {
259                 if (pNode->EqualKey(nKeyData))
260                 {
261                     pNode->SetValue(pValueData, nValueLength);
262                     bFind = TRUE;
263                     break;
264                 }
265                 pNode = pNode->m_pNext;
266             }
267             if (!bFind)
268             {
269                 pNode = new CQHashNTNode(nKeyData, pValueData, nValueLength);
270                 pNode->m_pNext = m_pHashTable[nIndex];
271                 m_pHashTable[nIndex] = pNode;
272                 m_nNodeCount += 1;
273             }
274         }
275         else
276         {
277             CQHashNTNode * pNode = new CQHashNTNode(nKeyData, pValueData, nValueLength);
278             pNode->m_pNext = m_pHashTable[nIndex];
279             m_pHashTable[nIndex] = pNode;
280             m_nNodeCount += 1;
281         }
282     }
283     VOID Remove(UINT32 nKeyData)
284     {
285         UINT32 nIndex = CQHashNTNode::GetHashCode(nKeyData) % m_nTableSize;
286         if (m_pHashTable[nIndex] != NULL)
287         {
288             CQHashNTNode * pNode = m_pHashTable[nIndex];
289             CQHashNTNode * pPrev = NULL;
290             while (pNode != NULL)
291             {
292                 if (pNode->EqualKey(nKeyData))
293                 {
294                     if (pPrev == NULL)
295                     {
296                         m_pHashTable[nIndex] = pNode->m_pNext;
297                     }
298                     else 
299                     {
300                         pPrev->m_pNext = pNode->m_pNext;
301                     }
302                     delete pNode;
303                     m_nNodeCount -= 1;
304                     break;
305                 }
306                 pNode = pNode->m_pNext;
307             }
308         }
309     }
310     VOID RemoveAll()
311     {
312         for (UINT32 n = 0; n < m_nTableSize; n++)
313         {
314             if (m_pHashTable[n] != NULL)
315             {
316                 CQHashNTNode * pNode = m_pHashTable[n];
317                 while (pNode)
318                 {
319                     m_pHashTable[n] = pNode->m_pNext;
320                     delete pNode;
321                     pNode = m_pHashTable[n];
322                 }
323             }
324         }
325         m_nNodeCount = 0;
326     }
327     UINT32 GetCount()
328     {
329         return m_nNodeCount;
330     }
331 public:
332     CQHashNTNode * GetHead()
333     {
334         m_nCurrentIndex = 0;
335         m_pCurrentNode = NULL;
336         for (UINT32 n = 0; n < m_nTableSize; n++)
337         {
338             if (m_pHashTable[n] != NULL)
339             {
340                 m_nCurrentIndex = n;
341                 m_pCurrentNode = m_pHashTable[n];
342                 break;
343             }
344         }
345         return m_pCurrentNode;
346     }
347     CQHashNTNode * GetNext()
348     {
349         if (m_pCurrentNode != NULL)
350         {
351             if (m_pCurrentNode->m_pNext != NULL)
352             {
353                 m_pCurrentNode = m_pCurrentNode->m_pNext;
354             }
355             else 
356             {
357                 for (UINT32 n = m_nCurrentIndex; n < m_nTableSize; n++)
358                 {
359                     if (m_pHashTable[n] != NULL)
360                     {
361                         m_nCurrentIndex = n;
362                         m_pCurrentNode = m_pHashTable[n];
363                         break;
364                     }
365                 }
366             }
367         }
368         return m_pCurrentNode;
369     }
370 };