home *** CD-ROM | disk | FTP | other *** search
/ io Programmo 40 / IOPROG_40.ISO / SOFT / NETFrameworkSDK.exe / comsdk.cab / samples1.exe / Debugger / DebuggerUtil.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2000-06-23  |  7.3 KB  |  207 lines
  1. #include "stdafx.h"
  2.  
  3.  
  4. //
  5. //
  6. // CHashTable
  7. //
  8. //
  9.  
  10. //*****************************************************************************
  11. // This is the second part of construction where we do all of the work that
  12. // can fail.  We also take the array of structs here because the calling class
  13. // presumably needs to allocate it in its NewInit.
  14. //*****************************************************************************
  15. HRESULT CHashTable::NewInit(            // Return status.
  16.     BYTE        *pcEntries,             // Array of structs we are managing.
  17.     USHORT      iEntrySize)             // Size of the entries.
  18. {
  19.     _ASSERTE(iEntrySize >= sizeof(FREEHASHENTRY));
  20.  
  21.     // Allocate the bucket chain array and init it.
  22.     if ((m_piBuckets = new USHORT [m_iBuckets]) == NULL)
  23.         return E_OUTOFMEMORY;
  24.     memset(m_piBuckets, 0xff, m_iBuckets * sizeof(USHORT));
  25.  
  26.     // Save the array of structs we are managing.
  27.     m_pcEntries = pcEntries;
  28.     m_iEntrySize = iEntrySize;
  29.     return (S_OK);
  30. }
  31.  
  32. //*****************************************************************************
  33. // Add the struct at the specified index in m_pcEntries to the hash chains.
  34. //*****************************************************************************
  35. BYTE *CHashTable::Add(                  // New entry.
  36.     USHORT      iHash,                  // Hash value of entry to add.
  37.     USHORT      iIndex)                 // Index of struct in m_pcEntries.
  38. {
  39.     HASHENTRY   *psEntry;               // The struct we are adding.
  40.  
  41.     // Get a pointer to the entry we are adding.
  42.     psEntry = EntryPtr(iIndex);
  43.  
  44.     // Compute the hash value for the entry.
  45.     iHash %= m_iBuckets;
  46.  
  47.     _ASSERTE(m_piBuckets[iHash] != iIndex &&
  48.         (m_piBuckets[iHash] == 0xffff || EntryPtr(m_piBuckets[iHash])->iPrev != iIndex));
  49.  
  50.     // Setup this entry.
  51.     psEntry->iPrev = 0xffff;
  52.     psEntry->iNext = m_piBuckets[iHash];
  53.  
  54.     // Link it into the hash chain.
  55.     if (m_piBuckets[iHash] != 0xffff)
  56.         EntryPtr(m_piBuckets[iHash])->iPrev = iIndex;
  57.     m_piBuckets[iHash] = iIndex;
  58.     return ((BYTE *) psEntry);
  59. }
  60.  
  61. //*****************************************************************************
  62. // Delete the struct at the specified index in m_pcEntries from the hash chains.
  63. //*****************************************************************************
  64. void CHashTable::Delete(
  65.     USHORT      iHash,                  // Hash value of entry to delete.
  66.     USHORT      iIndex)                 // Index of struct in m_pcEntries.
  67. {
  68.     HASHENTRY   *psEntry;               // Struct to delete.
  69.     
  70.     // Get a pointer to the entry we are deleting.
  71.     psEntry = EntryPtr(iIndex);
  72.     Delete(iHash, psEntry);
  73. }
  74.  
  75. //*****************************************************************************
  76. // Delete the struct at the specified index in m_pcEntries from the hash chains.
  77. //*****************************************************************************
  78. void CHashTable::Delete(
  79.     USHORT      iHash,                  // Hash value of entry to delete.
  80.     HASHENTRY   *psEntry)               // The struct to delete.
  81. {
  82.     // Compute the hash value for the entry.
  83.     iHash %= m_iBuckets;
  84.  
  85.     _ASSERTE(psEntry->iPrev != psEntry->iNext || psEntry->iPrev == 0xffff);
  86.  
  87.     // Fix the predecessor.
  88.     if (psEntry->iPrev == 0xffff)
  89.         m_piBuckets[iHash] = psEntry->iNext;
  90.     else
  91.         EntryPtr(psEntry->iPrev)->iNext = psEntry->iNext;
  92.  
  93.     // Fix the successor.
  94.     if (psEntry->iNext != 0xffff)
  95.         EntryPtr(psEntry->iNext)->iPrev = psEntry->iPrev;
  96. }
  97.  
  98. //*****************************************************************************
  99. // The item at the specified index has been moved, update the previous and
  100. // next item.
  101. //*****************************************************************************
  102. void CHashTable::Move(
  103.     USHORT      iHash,                  // Hash value for the item.
  104.     USHORT      iNew)                   // New location.
  105. {
  106.     HASHENTRY   *psEntry;               // The struct we are deleting.
  107.  
  108.     psEntry = EntryPtr(iNew);
  109.     _ASSERTE(psEntry->iPrev != iNew && psEntry->iNext != iNew);
  110.  
  111.     if (psEntry->iPrev != 0xffff)
  112.         EntryPtr(psEntry->iPrev)->iNext = iNew;
  113.     else
  114.         m_piBuckets[iHash % m_iBuckets] = iNew;
  115.     if (psEntry->iNext != 0xffff)
  116.         EntryPtr(psEntry->iNext)->iPrev = iNew;
  117. }
  118.  
  119. //*****************************************************************************
  120. // Search the hash table for an entry with the specified key value.
  121. //*****************************************************************************
  122. BYTE *CHashTable::Find(                 // Index of struct in m_pcEntries.
  123.     USHORT      iHash,                  // Hash value of the item.
  124.     BYTE        *pcKey)                 // The key to match.
  125. {
  126.     USHORT      iNext;                  // Used to traverse the chains.
  127.     HASHENTRY   *psEntry;               // Used to traverse the chains.
  128.  
  129.     // Start at the top of the chain.
  130.     iNext = m_piBuckets[iHash % m_iBuckets];
  131.  
  132.     // Search until we hit the end.
  133.     while (iNext != 0xffff)
  134.     {
  135.         // Compare the keys.
  136.         psEntry = EntryPtr(iNext);
  137.         if (!Cmp(pcKey, psEntry))
  138.             return ((BYTE *) psEntry);
  139.  
  140.         // Advance to the next item in the chain.
  141.         iNext = psEntry->iNext;
  142.     }
  143.  
  144.     // We couldn't find it.
  145.     return (0);
  146. }
  147.  
  148. //*****************************************************************************
  149. // Search the hash table for the next entry with the specified key value.
  150. //*****************************************************************************
  151. USHORT CHashTable::FindNext(            // Index of struct in m_pcEntries.
  152.     BYTE        *pcKey,                 // The key to match.
  153.     USHORT      iIndex)                 // Index of previous match.
  154. {
  155.     USHORT      iNext;                  // Used to traverse the chains.
  156.     HASHENTRY   *psEntry;               // Used to traverse the chains.
  157.  
  158.     // Start at the next entry in the chain.
  159.     iNext = EntryPtr(iIndex)->iNext;
  160.  
  161.     // Search until we hit the end.
  162.     while (iNext != 0xffff)
  163.     {
  164.         // Compare the keys.
  165.         psEntry = EntryPtr(iNext);
  166.         if (!Cmp(pcKey, psEntry))
  167.             return (iNext);
  168.  
  169.         // Advance to the next item in the chain.
  170.         iNext = psEntry->iNext;
  171.     }
  172.  
  173.     // We couldn't find it.
  174.     return (0xffff);
  175. }
  176.  
  177. //*****************************************************************************
  178. // Returns the next entry in the list.
  179. //*****************************************************************************
  180. BYTE *CHashTable::FindNextEntry(        // The next entry, or0 for end of list.
  181.     HASHFIND    *psSrch)                // Search object.
  182. {
  183.     HASHENTRY   *psEntry;               // Used to traverse the chains.
  184.  
  185.     for (;;)
  186.     {
  187.         // See if we already have one to use and if so, use it.
  188.         if (psSrch->iNext != 0xffff)
  189.         {
  190.             psEntry = EntryPtr(psSrch->iNext);
  191.             psSrch->iNext = psEntry->iNext;
  192.             return ((BYTE *) psEntry);
  193.         }
  194.  
  195.         // Advance to the next bucket.
  196.         if (psSrch->iBucket < m_iBuckets)
  197.             psSrch->iNext = m_piBuckets[psSrch->iBucket++];
  198.         else
  199.             break;
  200.     }
  201.  
  202.     // There were no more entries to be found.
  203.     return (0);
  204. }
  205.  
  206.  
  207.