Return to map_s.ctt CVS log

Up to [WindowsNT SDKs] / mstools / mfc / samples / templdef

Annotation of mstools/mfc/samples/templdef/map_s.ctt, revision 1.1

1.1     ! root        1: /////////////////////////////////////////////////////////////////////////////
        !             2: // class CMapStringTo - a mapping from CStrings to 'VALUE's.
        !             3: //
        !             4: // This is a part of the Microsoft Foundation Classes C++ library.
        !             5: // Copyright (C) 1992 Microsoft Corporation
        !             6: // All rights reserved.
        !             7: //
        !             8: // This source code is only intended as a supplement to the
        !             9: // Microsoft Foundation Classes Reference and Microsoft
        !            10: // QuickHelp documentation provided with the library.
        !            11: // See these sources for detailed information regarding the
        !            12: // Microsoft Foundation Classes product.
        !            13: /////////////////////////////////////////////////////////////////////////////
        !            14: 
        !            15: //$DECLARE_TEMPLATE
        !            16: 
        !            17: /////////////////////////////////////////////////////////////////////////////
        !            18: 
        !            19: template<class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE>
        !            20: class CMapStringTo<VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE> : public CObject
        !            21: {
        !            22: #if IS_SERIAL
        !            23:        DECLARE_SERIAL(CMapStringTo)
        !            24: #else
        !            25:        DECLARE_DYNAMIC(CMapStringTo)
        !            26: #endif //!IS_SERIAL
        !            27: protected:
        !            28:        // Association
        !            29:        struct CAssoc
        !            30:        {
        !            31:                CAssoc* pNext;
        !            32:                UINT    nHashValue; // needed for efficient iteration
        !            33:                CString key;
        !            34:                VALUE   value;
        !            35:        };
        !            36: public:
        !            37: 
        !            38: // Construction
        !            39:        CMapStringTo(int nBlockSize=10);
        !            40: 
        !            41: // Attributes
        !            42:        // number of elements
        !            43:        int     GetCount() const
        !            44:                                { return m_nCount; }
        !            45:        BOOL    IsEmpty() const
        !            46:                                { return m_nCount == 0; }
        !            47:        // Lookup
        !            48:        BOOL    Lookup(const char* key, VALUE& rValue) const;
        !            49: 
        !            50: // Operations
        !            51:        // Lookup and add if not there
        !            52:        VALUE&  operator[](const char* key);
        !            53: 
        !            54:        // add a new (key, value) pair
        !            55:        void    SetAt(const char* key, ARG_VALUE newValue)
        !            56:                                { (*this)[key] = newValue; }
        !            57: 
        !            58:        // removing existing (key, ?) pair
        !            59:        BOOL    RemoveKey(const char* key);
        !            60:        void    RemoveAll();
        !            61: 
        !            62:        // iterating all (key, value) pairs
        !            63:        POSITION GetStartPosition() const
        !            64:                                { return (m_nCount == 0) ? NULL : BEFORE_START_POSITION; }
        !            65:        void    GetNextAssoc(POSITION& rNextPosition, CString& rKey, VALUE& rValue) const;
        !            66: 
        !            67:        // advanced features for derived classes
        !            68:        UINT    GetHashTableSize() const
        !            69:                                { return m_nHashTableSize; }
        !            70:        void    InitHashTable(UINT hashSize);
        !            71: 
        !            72: // Overridables: special non-virtual (see map implementation for details)
        !            73:        // Routine used to user-provided hash keys
        !            74:        UINT    HashKey(const char* key) const;
        !            75: 
        !            76: // Implementation
        !            77: protected:
        !            78:        CAssoc** m_pHashTable;
        !            79:        UINT    m_nHashTableSize;
        !            80:        int     m_nCount;
        !            81:        CAssoc* m_pFreeList;
        !            82:        struct CPlex* m_pBlocks;
        !            83:        int     m_nBlockSize;
        !            84: 
        !            85:        CAssoc* NewAssoc();
        !            86:        void    FreeAssoc(CAssoc*);
        !            87:        CAssoc* GetAssocAt(const char*, UINT&) const;
        !            88: 
        !            89: public:
        !            90:        ~CMapStringTo();
        !            91: #if IS_SERIAL
        !            92:        void    Serialize(CArchive&);
        !            93: #endif //IS_SERIAL
        !            94: #ifdef _DEBUG
        !            95:        void    Dump(CDumpContext&) const;
        !            96:        void    AssertValid() const;
        !            97: #endif
        !            98: };
        !            99: 
        !           100: //$IMPLEMENT_TEMPLATE
        !           101: /////////////////////////////////////////////////////////////////////////////
        !           102: //
        !           103: // Implementation of Map from CString to VALUE
        !           104: //
        !           105: /////////////////////////////////////////////////////////////////////////////
        !           106: 
        !           107: #include "afxcoll.h"
        !           108: #pragma hdrstop
        !           109: 
        !           110: #include "plex.h"
        !           111: 
        !           112: #ifdef AFX_COLL_SEG
        !           113: #pragma code_seg(AFX_COLL_SEG)
        !           114: #endif
        !           115: 
        !           116: #if IS_SERIAL
        !           117: IMPLEMENT_SERIAL(CMapStringTo, CObject, 0);
        !           118: #else
        !           119: IMPLEMENT_DYNAMIC(CMapStringTo, CObject);
        !           120: #endif //!IS_SERIAL
        !           121: 
        !           122: #ifdef _DEBUG
        !           123: #undef THIS_FILE
        !           124: static char BASED_CODE THIS_FILE[] = __FILE__;
        !           125: #endif
        !           126: 
        !           127: #if HAS_CREATE
        !           128: #include "elements.h"       // used for special creation
        !           129: #endif
        !           130: 
        !           131: #define new DEBUG_NEW
        !           132: 
        !           133: extern const CString NEAR afxEmptyString;   // for creating empty key strings
        !           134: 
        !           135: /////////////////////////////////////////////////////////////////////////////
        !           136: 
        !           137: template<class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE>
        !           138: CMapStringTo<VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::CMapStringTo(int nBlockSize)
        !           139: {
        !           140:        ASSERT(nBlockSize > 0);
        !           141: 
        !           142:        m_pHashTable = NULL;
        !           143:        m_nHashTableSize = 17;      // default size
        !           144:        m_nCount = 0;
        !           145:        m_pFreeList = NULL;
        !           146:        m_pBlocks = NULL;
        !           147:        m_nBlockSize = nBlockSize;
        !           148: }
        !           149: 
        !           150: template<class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE>
        !           151: inline UINT CMapStringTo<VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::HashKey(const char* key) const
        !           152: {
        !           153:        register UINT nHash = 0;
        !           154:        while (*key)
        !           155:                nHash = (nHash<<5) + nHash + *key++;
        !           156:        return nHash;
        !           157: }
        !           158: 
        !           159: template<class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE>
        !           160: void CMapStringTo<VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::InitHashTable(UINT nHashSize)
        !           161: //
        !           162: // Used to force allocation of a hash table or to override the default
        !           163: //   hash table size of (which is fairly small)
        !           164: {
        !           165:        ASSERT_VALID(this);
        !           166:        ASSERT(m_nCount == 0);
        !           167:        ASSERT(nHashSize > 0);
        !           168: 
        !           169:        // if had a hash table - get rid of it
        !           170:        if (m_pHashTable != NULL)
        !           171:                delete m_pHashTable;
        !           172:        m_pHashTable = NULL;
        !           173: 
        !           174:        m_pHashTable = new CAssoc* [nHashSize];
        !           175:        memset(m_pHashTable, 0, sizeof(CAssoc*) * nHashSize);
        !           176:        m_nHashTableSize = nHashSize;
        !           177: }
        !           178: 
        !           179: template<class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE>
        !           180: void CMapStringTo<VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::RemoveAll()
        !           181: {
        !           182:        ASSERT_VALID(this);
        !           183: 
        !           184:        if (m_pHashTable != NULL)
        !           185:        {
        !           186:                // destroy elements
        !           187:                for (UINT nHash = 0; nHash < m_nHashTableSize; nHash++)
        !           188:                {
        !           189:                        register CAssoc* pAssoc;
        !           190:                        for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL;
        !           191:                          pAssoc = pAssoc->pNext)
        !           192:                        {
        !           193:                                pAssoc->key.Empty();        // free up string data
        !           194: #if HAS_CREATE
        !           195:                                DestructElement(&pAssoc->value);
        !           196: #endif
        !           197:                        }
        !           198:                }
        !           199: 
        !           200:                // free hash table
        !           201:                delete m_pHashTable;
        !           202:                m_pHashTable = NULL;
        !           203:        }
        !           204: 
        !           205:        m_nCount = 0;
        !           206:        m_pFreeList = NULL;
        !           207:        m_pBlocks->FreeDataChain();
        !           208:        m_pBlocks = NULL;
        !           209: }
        !           210: 
        !           211: template<class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE>
        !           212: CMapStringTo<VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::~CMapStringTo()
        !           213: {
        !           214:        RemoveAll();
        !           215:        ASSERT(m_nCount == 0);
        !           216: }
        !           217: 
        !           218: /////////////////////////////////////////////////////////////////////////////
        !           219: // Assoc helpers
        !           220: // same as CList implementation except we store CAssoc's not CNode's
        !           221: //    and CAssoc's are singly linked all the time
        !           222: 
        !           223: template<class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE>
        !           224: CMapStringTo<VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::CAssoc* CMapStringTo::NewAssoc()
        !           225: {
        !           226:        if (m_pFreeList == NULL)
        !           227:        {
        !           228:                // add another block
        !           229:                CPlex* newBlock = CPlex::Create(m_pBlocks, m_nBlockSize, 
        !           230:                                                        sizeof(CMapStringTo::CAssoc));
        !           231:                // chain them into free list
        !           232:                register CMapStringTo::CAssoc* pAssoc = 
        !           233:                                (CMapStringTo::CAssoc*) newBlock->data();
        !           234:                // free in reverse order to make it easier to debug
        !           235:                pAssoc += m_nBlockSize - 1;
        !           236:                for (int i = m_nBlockSize-1; i >= 0; i--, pAssoc--)
        !           237:                {
        !           238:                        pAssoc->pNext = m_pFreeList;
        !           239:                        m_pFreeList = pAssoc;
        !           240:                }
        !           241:        }
        !           242:        ASSERT(m_pFreeList != NULL); // we must have something
        !           243: 
        !           244:        CMapStringTo::CAssoc* pAssoc = m_pFreeList;
        !           245:        m_pFreeList = m_pFreeList->pNext;
        !           246:        m_nCount++;
        !           247:        ASSERT(m_nCount > 0);       // make sure we don't overflow
        !           248:        memcpy(&pAssoc->key, &afxEmptyString, sizeof(CString));
        !           249: #if HAS_CREATE
        !           250:        ConstructElement(&pAssoc->value);
        !           251: #else
        !           252:        memset(&pAssoc->value, 0, sizeof(VALUE));
        !           253: #endif
        !           254:        return pAssoc;
        !           255: }
        !           256: 
        !           257: template<class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE>
        !           258: void CMapStringTo<VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::FreeAssoc(CMapStringTo::CAssoc* pAssoc)
        !           259: {
        !           260:        pAssoc->key.Empty();        // free up string data
        !           261: #if HAS_CREATE
        !           262:        DestructElement(&pAssoc->value);
        !           263: #endif
        !           264:        pAssoc->pNext = m_pFreeList;
        !           265:        m_pFreeList = pAssoc;
        !           266:        m_nCount--;
        !           267:        ASSERT(m_nCount >= 0);      // make sure we don't underflow
        !           268: }
        !           269: 
        !           270: template<class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE>
        !           271: CMapStringTo<VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::CAssoc*
        !           272: CMapStringTo<VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::GetAssocAt(const char* key, UINT& nHash) const
        !           273: // find association (or return NULL)
        !           274: {
        !           275:        nHash = HashKey(key) % m_nHashTableSize;
        !           276: 
        !           277:        if (m_pHashTable == NULL)
        !           278:                return NULL;
        !           279: 
        !           280:        // see if it exists
        !           281:        register CAssoc* pAssoc;
        !           282:        for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext)
        !           283:        {
        !           284:                if (pAssoc->key == key)
        !           285:                        return pAssoc;
        !           286:        }
        !           287:        return NULL;
        !           288: }
        !           289: 
        !           290: /////////////////////////////////////////////////////////////////////////////
        !           291: 
        !           292: template<class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE>
        !           293: BOOL CMapStringTo<VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::Lookup(const char* key, VALUE& rValue) const
        !           294: {
        !           295:        ASSERT_VALID(this);
        !           296: 
        !           297:        UINT nHash;
        !           298:        register CAssoc* pAssoc = GetAssocAt(key, nHash);
        !           299:        if (pAssoc == NULL)
        !           300:                return FALSE;       // not in map
        !           301: 
        !           302:        rValue = pAssoc->value;
        !           303:        return TRUE;
        !           304: }
        !           305: 
        !           306: template<class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE>
        !           307: VALUE& CMapStringTo<VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::operator[](const char* key)
        !           308: {
        !           309:        ASSERT_VALID(this);
        !           310: 
        !           311:        UINT nHash;
        !           312:        register CAssoc* pAssoc;
        !           313:        if ((pAssoc = GetAssocAt(key, nHash)) == NULL)
        !           314:        {
        !           315:                if (m_pHashTable == NULL)
        !           316:                        InitHashTable(m_nHashTableSize);
        !           317: 
        !           318:                // it doesn't exist, add a new Association
        !           319:                pAssoc = NewAssoc();
        !           320:                pAssoc->nHashValue = nHash;
        !           321:                pAssoc->key = key;
        !           322:                // 'pAssoc->value' is a constructed object, nothing more
        !           323: 
        !           324:                // put into hash table
        !           325:                pAssoc->pNext = m_pHashTable[nHash];
        !           326:                m_pHashTable[nHash] = pAssoc;
        !           327:        }
        !           328:        return pAssoc->value;           // return new reference
        !           329: }
        !           330: 
        !           331: 
        !           332: template<class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE>
        !           333: BOOL CMapStringTo<VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::RemoveKey(const char* key)
        !           334: // remove key - return TRUE if removed
        !           335: {
        !           336:        ASSERT_VALID(this);
        !           337: 
        !           338:        if (m_pHashTable == NULL)
        !           339:                return FALSE;       // nothing in the table
        !           340: 
        !           341:        CAssoc** ppAssocPrev;
        !           342:        ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize];
        !           343: 
        !           344:        CAssoc* pAssoc;
        !           345:        for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext)
        !           346:        {
        !           347:                if (pAssoc->key == key)
        !           348:                {
        !           349:                        // remove it
        !           350:                        *ppAssocPrev = pAssoc->pNext;       // remove from list
        !           351:                        FreeAssoc(pAssoc);
        !           352:                        return TRUE;
        !           353:                }
        !           354:                ppAssocPrev = &pAssoc->pNext;
        !           355:        }
        !           356:        return FALSE;   // not found
        !           357: }
        !           358: 
        !           359: 
        !           360: /////////////////////////////////////////////////////////////////////////////
        !           361: // Iterating
        !           362: 
        !           363: template<class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE>
        !           364: void CMapStringTo<VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::GetNextAssoc(POSITION& rNextPosition,
        !           365:        CString& rKey, VALUE& rValue) const
        !           366: {
        !           367:        ASSERT_VALID(this);
        !           368:        ASSERT(m_pHashTable != NULL);       // never call on empty map
        !           369: 
        !           370:        register CAssoc* pAssocRet = (CAssoc*)rNextPosition;
        !           371:        ASSERT(pAssocRet != NULL);
        !           372: 
        !           373:        if (pAssocRet == (CAssoc*) BEFORE_START_POSITION)
        !           374:        {
        !           375:                // find the first association
        !           376:                for (UINT nBucket = 0; nBucket < m_nHashTableSize; nBucket++)
        !           377:                        if ((pAssocRet = m_pHashTable[nBucket]) != NULL)
        !           378:                                break;
        !           379:                ASSERT(pAssocRet != NULL);  // must find something
        !           380:        }
        !           381: 
        !           382:        // find next association
        !           383:        register CAssoc* pAssocNext;
        !           384:        if ((pAssocNext = pAssocRet->pNext) == NULL)
        !           385:        {
        !           386:                // go to next bucket
        !           387:                for (UINT nBucket = pAssocRet->nHashValue + 1;
        !           388:                  nBucket < m_nHashTableSize; nBucket++)
        !           389:                        if ((pAssocNext = m_pHashTable[nBucket]) != NULL)
        !           390:                                break;
        !           391:        }
        !           392: 
        !           393:        rNextPosition = (POSITION) pAssocNext;
        !           394: 
        !           395:        // fill in return data
        !           396:        rKey = pAssocRet->key;
        !           397:        rValue = pAssocRet->value;
        !           398: }
        !           399: 
        !           400: /////////////////////////////////////////////////////////////////////////////
        !           401: // Serialization
        !           402: 
        !           403: #if IS_SERIAL
        !           404: template<class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE>
        !           405: void CMapStringTo<VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::Serialize(CArchive& ar)
        !           406: {
        !           407:        ASSERT_VALID(this);
        !           408: 
        !           409:        CObject::Serialize(ar);
        !           410: 
        !           411:        if (ar.IsStoring())
        !           412:        {
        !           413:                ar << (WORD) m_nCount;
        !           414:                if (m_nCount == 0)
        !           415:                        return; // nothing more to do
        !           416: 
        !           417:                ASSERT(m_pHashTable != NULL);
        !           418:                for (UINT nHash = 0; nHash < m_nHashTableSize; nHash++)
        !           419:                {
        !           420:                        register CAssoc* pAssoc;
        !           421:                        for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL;
        !           422:                          pAssoc = pAssoc->pNext)
        !           423:                        {
        !           424:                                ar << pAssoc->key;
        !           425:                                ar << pAssoc->value;
        !           426:                        }
        !           427:                }
        !           428:        }
        !           429:        else
        !           430:        {
        !           431:                WORD wNewCount;
        !           432:                ar >> wNewCount;
        !           433:                while (wNewCount--)
        !           434:                {
        !           435:                        CString newKey;
        !           436:                        VALUE newValue;
        !           437:                        ar >> newKey;
        !           438:                        ar >> newValue;
        !           439:                        SetAt(newKey, newValue);
        !           440:                }
        !           441:        }
        !           442: }
        !           443: #endif //IS_SERIAL
        !           444: 
        !           445: /////////////////////////////////////////////////////////////////////////////
        !           446: // Diagnostics
        !           447: 
        !           448: #ifdef _DEBUG
        !           449: 
        !           450: template<class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE>
        !           451: void CMapStringTo<VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::Dump(CDumpContext& dc) const
        !           452: {
        !           453:        ASSERT_VALID(this);
        !           454: 
        !           455: #define MAKESTRING(x) #x
        !           456:        dc << "A " MAKESTRING(CMapStringTo) " with " << m_nCount << " elements\n";
        !           457: #undef MAKESTRING
        !           458:        if (dc.GetDepth() > 0)
        !           459:        {
        !           460:                // Dump in format "[key] -> value"
        !           461:                dc << "\n";
        !           462:                POSITION pos = GetStartPosition();
        !           463:                CString key;
        !           464:                VALUE val;
        !           465:                while (pos != NULL)
        !           466:                {
        !           467:                        GetNextAssoc(pos, key, val);
        !           468:                        dc << "\n\t[" << key << "] = " << val;
        !           469:                }
        !           470:        }
        !           471: }
        !           472: 
        !           473: template<class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE>
        !           474: void CMapStringTo<VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::AssertValid() const
        !           475: {
        !           476:        CObject::AssertValid();
        !           477: 
        !           478:        ASSERT(m_nHashTableSize > 0);
        !           479:        ASSERT(m_nCount == 0 || m_pHashTable != NULL);
        !           480:                         // non-empty map should have hash table
        !           481: }
        !           482: #endif //_DEBUG
        !           483: 
        !           484: /////////////////////////////////////////////////////////////////////////////

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.