Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/Tools/3dsmaxExport/LEXIExporter/SharedUtilities/Sources/FastMap.h @ 6

Last change on this file since 6 was 6, checked in by anonymous, 17 years ago

=…
File size: 8.9 KB
RevLine 
[6]1/*
2-----------------------------------------------------------------------------
3This source file is part of LEXIExporter
4
5Copyright 2006 NDS Limited
6
7Author(s):
8Lasse Tassing
9
10This program is free software; you can redistribute it and/or modify it under
11the terms of the GNU Lesser General Public License as published by the Free Software
12Foundation; either version 2 of the License, or (at your option) any later
13version.
14
15This program is distributed in the hope that it will be useful, but WITHOUT
16ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
17FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
18
19You should have received a copy of the GNU Lesser General Public License along with
20this program; if not, write to the Free Software Foundation, Inc., 59 Temple
21Place - Suite 330, Boston, MA 02111-1307, USA, or go to
22http://www.gnu.org/copyleft/lesser.txt.
23-----------------------------------------------------------------------------
24*/
25
26#ifndef __FAST_MAP__
27#define __FAST_MAP__
28
29// NOTE! The fastmap<> is NOT threadsafe - you must implement own protection if needed.
30// (only case should be lookup while remove/clear/map is used)
31template<class _T> class fastmap
32{
33public:
34        // Destructor
35        virtual ~fastmap() 
36        {
37                clear(); 
38                delete[] m_pHTable;
39        };
40
41        //! Base constructor
42        fastmap(int iInitSize=50, int iGrowSize=20)
43        {
44                m_iGrowSize=iGrowSize;
45                m_iSize=ClosestPrime(iInitSize);
46                m_iCount=0;
47                m_pHTable=new SItem*[m_iSize];
48                for(unsigned int i=0; i < m_iSize; i++)
49                        m_pHTable[i] = NULL;
50        }
51
52        //! Copy constructor
53        fastmap(const fastmap& other)
54        {
55                m_iGrowSize = 20;
56                m_iSize = ClosestPrime(50);
57                m_iCount = 0;
58                m_pHTable = new SItem*[m_iSize];
59                for(unsigned int i = 0; i < m_iSize; i++) m_pHTable[i] = NULL;
60
61                assign(other);
62        }
63
64        // Assign
65        void assign(const fastmap& other)
66        {
67                clear();
68
69                for(unsigned int i = 0; i < other.m_iSize; i++)
70                {
71                        const SItem* pCur = other.m_pHTable[i];
72                        while(pCur)
73                        {
74                                map(pCur->Key, pCur->Item);
75                                pCur = pCur->Next;
76                        }
77                }
78        }
79
80        // Assign operator
81        fastmap& operator = (const fastmap& other)
82        {
83                assign(other);
84                return *this;
85        }
86
87        fastmap<_T>*    clone(void)
88        {
89                fastmap<_T> *pNew=new fastmap<_T>;
90                pNew->m_iGrowSize=m_iGrowSize;
91                pNew->m_iSize=m_iSize;
92                pNew->m_iCount=m_iCount;
93                pNew->m_pHTable=new SItem*[m_iSize];
94
95                for(unsigned int i=0; i < m_iSize; i++)
96                {
97                        pNew->m_pHTable[i]=NULL;
98                        SItem *pSrc=m_pHTable[i];
99                        SItem *pDst;
100                        SItem *pPrev=NULL;
101                        while(pSrc!=NULL)
102                        {
103                                pDst=new SItem;
104                                pDst->Key=_strdup(pSrc->Key);
105                                pDst->Item=pSrc->Item;
106                                pDst->Next=NULL;
107                                if(!pPrev) pNew->m_pHTable[i]=pDst;
108                                else pPrev->Next=pDst;
109                                pPrev=pDst;                             
110                                pSrc=pSrc->Next;
111                        }
112                }
113                return pNew;
114        }
115
116        unsigned int size() const { return m_iCount; }
117        unsigned int capacity() const { return m_iSize; }
118        unsigned int growSize() const { return m_iGrowSize; }   
119
120        void reserve(int iItems)
121        {
122                SItem** pOldTable = m_pHTable;
123                unsigned int iOldSize = m_iSize;
124                unsigned int iKey;
125                if(iItems > m_iSize)
126                {                       
127                        m_iSize = ClosestPrime(iItems);
128                        m_pHTable=new SItem*[m_iSize];
129                        for(unsigned int t = 0; t < m_iSize; t++)
130                                m_pHTable[t] = NULL;
131                        SItem* p;
132                        SItem* tp;
133                        for(unsigned int i = 0; i < iOldSize; i++)
134                        {
135                                p = pOldTable[i];
136                                while (p != NULL)
137                                {       
138                                        iKey = CalculateKey(p->Key);
139                                        iKey = iKey % m_iSize;
140                                        tp = p->Next;
141                                        p->Next = m_pHTable[iKey];
142                                        m_pHTable[iKey] = p;
143                                        p = tp;
144                                }
145                        }                       
146                        delete[] pOldTable;
147                }
148        }
149
150        //! Clear map
151        void clear(void)
152        {
153                SItem* p;
154                SItem* tp;
155                // Run through the table & free elements
156                for(unsigned int i = 0; i < m_iSize; i++)
157                {
158                        p = m_pHTable[i];
159                        while (p != NULL)
160                        {
161                                tp = p;
162                                p = p->Next;
163                                free(tp->Key);  // delete char * buffer
164                                delete tp;                      // delete the SItem instance
165                        }
166                        m_pHTable[i] = NULL;
167                }
168                m_iCount=0;
169        }
170
171        //! Erase a key
172        bool erase(const char *pszKey)
173        {
174                unsigned int iKey = CalculateKey(pszKey);
175                iKey = iKey % m_iSize;
176                SItem* m_pDelItem = m_pHTable[iKey];
177                SItem** m_pLastItem = &m_pHTable[iKey];
178                bool bDeleted = false; 
179
180                //check for end of collision list
181                while(m_pDelItem != NULL)
182                {
183                        if(!strcmp(pszKey, m_pDelItem->Key))
184                        {
185                                *m_pLastItem = m_pDelItem->Next;
186                                bDeleted=true;
187                                free(m_pDelItem->Key);  // delete char * buffer
188                                delete m_pDelItem;                      // delete SItem instance
189                                m_iCount--;
190                                break;
191                        }
192                        else
193                        {
194                                m_pLastItem = &m_pDelItem->Next;
195                                m_pDelItem = m_pDelItem->Next;
196                        }
197                }       
198                return bDeleted;
199        }
200
201        // Search for a key
202        bool find(const char *pszKey, _T &item) const
203        {
204                unsigned int iKey = CalculateKey(pszKey);
205                iKey = iKey % m_iSize;
206                SItem* m_pSearchItem = m_pHTable[iKey];
207                while(m_pSearchItem!=NULL)
208                {
209                        if(!strcmp(pszKey, m_pSearchItem->Key))
210                        {       
211                                item=m_pSearchItem->Item;
212                                return true;
213                        }
214                        m_pSearchItem = m_pSearchItem->Next;
215                }
216                return false; 
217        }       
218
219        //! setup a value map
220        void map(const char *pszKey, _T cVal, _T &olditem)
221        {               
222                unsigned int iKey = CalculateKey(pszKey);
223                iKey = iKey % m_iSize;
224
225                // Search for existing key
226                SItem* m_pSearchItem = m_pHTable[iKey];
227                while(m_pSearchItem!=NULL)
228                {
229                        if(!strcmp(pszKey, m_pSearchItem->Key))
230                        {       // key found
231                                olditem=m_pSearchItem->Item;
232                                m_pSearchItem->Item=cVal;
233                                return;
234                        }
235                        m_pSearchItem = m_pSearchItem->Next;
236                }
237
238                // Key was not found, insert new
239                SItem* pNewItem = new SItem;
240                pNewItem->Key = _strdup(pszKey);
241                pNewItem->Item = cVal;
242                pNewItem->Next = m_pHTable[iKey];
243                m_pHTable[iKey] = pNewItem;
244                m_iCount++;
245                ReHash();
246        }
247
248        //! setup a value map
249        void map(const char *pszKey, _T cVal)
250        {               
251                unsigned int iKey = CalculateKey(pszKey);
252                iKey = iKey % m_iSize;
253               
254                // Key was not found, insert new
255                SItem* pNewItem = new SItem;
256                pNewItem->Key = _strdup(pszKey);
257                pNewItem->Item = cVal;
258                pNewItem->Next = m_pHTable[iKey];
259                m_pHTable[iKey] = pNewItem;
260                m_iCount++;
261                ReHash();
262        }
263
264        //! Get key names
265        fastvector< const char * >      keys(void) const
266        {
267                fastvector<const char *> lList;
268                lList.reserve(m_iSize);
269                for(unsigned int i = 0; i < m_iSize; i++)
270                {
271                        SItem *pCur=m_pHTable[i];
272                        while(pCur!=NULL)
273                        {                               
274                                lList.push_back(pCur->Key);
275                                pCur=pCur->Next;
276                        }
277                }
278                return lList;
279        }
280
281        //! Get list of data elements
282        fastvector< _T >        data(void) const
283        {
284                fastvector< _T > lList;
285                lList.reserve(m_iSize);
286                for(unsigned int i = 0; i < m_iSize; i++)
287                {
288                        SItem *pCur=m_pHTable[i];
289                        while(pCur!=NULL)
290                        {                               
291                                lList.push_back(pCur->Item);
292                                pCur=pCur->Next;
293                        }
294                }
295                return lList;
296        }
297
298        struct SDataPair
299        {
300                SDataPair(const char *pKey, _T data) { pszKey=pKey; Data=data; };
301                const char *pszKey;
302                _T Data;
303        };
304
305        // Get list of keys AND data
306        fastvector< SDataPair > iterate(void) const
307        {
308                fastvector< SDataPair > lList;
309                lList.reserve(m_iSize);
310                for(unsigned int i = 0; i < m_iSize; i++)
311                {
312                        SItem *pCur=m_pHTable[i];
313                        while(pCur!=NULL)
314                        {                               
315                                lList.push_back(SDataPair(pCur->Key,pCur->Item));
316                                pCur=pCur->Next;
317                        }
318                }
319                return lList;
320        }
321
322        // Get list of keys AND data
323        vector< SDataPair >     iterateVector(void) const
324        {
325                vector< SDataPair > lList;
326                lList.reserve(m_iSize);
327                for(unsigned int i = 0; i < m_iSize; i++)
328                {
329                        SItem *pCur=m_pHTable[i];
330                        while(pCur!=NULL)
331                        {                               
332                                lList.push_back(SDataPair(pCur->Key,pCur->Item));
333                                pCur=pCur->Next;
334                        }
335                }
336                return lList;
337        }
338
339private:
340        //! Check if need to expand the hash table
341        void ReHash(void)
342        {
343                SItem** pOldTable = m_pHTable;
344                unsigned int iOldSize = m_iSize;
345                unsigned int iKey;
346                if (m_iCount > m_iSize)
347                {
348                        m_iSize = ClosestPrime(m_iSize+m_iGrowSize);
349                        m_pHTable=new SItem*[m_iSize];
350                        for(unsigned int t = 0; t < m_iSize; t++)
351                                m_pHTable[t] = NULL;
352                        SItem* p;
353                        SItem* tp;
354                        for(unsigned int i = 0; i < iOldSize; i++)
355                        {
356                                p = pOldTable[i];
357                                while (p != NULL)
358                                {       
359                                        iKey = CalculateKey(p->Key);
360                                        iKey = iKey % m_iSize;
361                                        tp = p->Next;
362                                        p->Next = m_pHTable[iKey];
363                                        m_pHTable[iKey] = p;
364                                        p = tp;
365                                }
366                        }                       
367                        delete[] pOldTable;
368                }
369        }
370
371        // Find the closest prime to the parameter
372        unsigned int ClosestPrime(unsigned int iNumber) const
373        {
374                unsigned int iPNumber=iNumber;
375                if(iNumber%2==0) iPNumber++;
376                while (true)
377                {
378                unsigned int iHNumber=iPNumber/2;
379                unsigned int i;
380                for(i=3;i<=iHNumber;i++)
381                        if(iPNumber%i)
382                                iHNumber=iPNumber/i+1;
383                        else
384                                break;
385                if (i>iHNumber)
386                        break;
387                else
388                        iPNumber+=2;
389                };
390                return iPNumber;
391        }
392
393        // Calculate the hash key from a char buffer (Remember to mod with m_iSize)
394        unsigned int CalculateKey(const char *pszStr) const
395        {
396                unsigned short iLow=0, iHigh=0;
397                while(*pszStr)
398                {
399                        iLow+=*pszStr++;
400                        iHigh+=iLow+3;
401                }
402                return (iLow)|(iHigh<<16);
403        }
404
405        // The internal hash structure
406        typedef struct _SItem
407        {
408                char    *Key;
409                _T              Item;
410                _SItem  *Next;
411        } SItem;
412
413        // The hash table
414        SItem **m_pHTable;
415
416        // Number of keys inserted
417        unsigned int m_iCount;
418
419        // Number of entries in hash table
420        unsigned int m_iSize;
421
422        // Number of entries of which to grow
423        unsigned int m_iGrowSize;         
424};
425
426#endif  // End sentry
Note: See TracBrowser for help on using the repository browser.