351 lines
7.8 KiB
C++
351 lines
7.8 KiB
C++
//+---------------------------------------------------------------------
|
|
//
|
|
// Microsoft Windows
|
|
// Copyright (C) Microsoft Corporation, 1994 - 1995.
|
|
//
|
|
// File: cspytbl.cxx
|
|
//
|
|
// Contents: Used by CTaskMemory::* (memapi.cxx) to support IMallocSpy
|
|
//
|
|
// Synopsis: The requirements are to efficiently store, locate and remove
|
|
// entries in a table that may have to be expanded. Therefore
|
|
// the choice is a dynamically expandable hash table. It is
|
|
// fast and removals do not require compaction. Expansion is
|
|
// always to twice the current number of entries, so excessive
|
|
// expansions will not be done.
|
|
//
|
|
// Classes: CSpyTable
|
|
//
|
|
// Functions:
|
|
//
|
|
// History: 27-Oct-94 BruceMa Created
|
|
//
|
|
//----------------------------------------------------------------------
|
|
|
|
|
|
#include <ole2int.h>
|
|
#include "cspytbl.hxx"
|
|
|
|
|
|
|
|
|
|
|
|
//+-------------------------------------------------------------------------
|
|
//
|
|
// Member: CSpyTable::CSpyTable, public
|
|
//
|
|
// Synopsis: Constructor
|
|
//
|
|
// Arguments: BOOl * - Indicates construction success
|
|
//
|
|
// Algorithm:
|
|
//
|
|
// History: 27-Oct-94 Brucema Created
|
|
//
|
|
// Notes:
|
|
//
|
|
//--------------------------------------------------------------------------
|
|
CSpyTable::CSpyTable(BOOL *pfOk)
|
|
{
|
|
// Allocate and initialize the hash table
|
|
m_cAllocations = 0;
|
|
m_cEntries = INITIALENTRIES;
|
|
m_table = (LPAENTRY) LocalAlloc(LMEM_FIXED, m_cEntries * sizeof(AENTRY));
|
|
if (m_table == NULL)
|
|
{
|
|
*pfOk = FALSE;
|
|
return;
|
|
}
|
|
|
|
// Initialize the table
|
|
// m_table[*].dwCollision = FALSE;
|
|
// m_table[*].allocation = NULL;
|
|
memset(m_table, 0, m_cEntries * sizeof(AENTRY));
|
|
|
|
// Return success
|
|
*pfOk = TRUE;
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
//+-------------------------------------------------------------------------
|
|
//
|
|
// Member: CSpyTable::~CSpyTable, public
|
|
//
|
|
// Synopsis: Destructor
|
|
//
|
|
// Arguments: -
|
|
//
|
|
// Algorithm:
|
|
//
|
|
// History: 27-Oct-94 Brucema Created
|
|
//
|
|
// Notes:
|
|
//
|
|
//--------------------------------------------------------------------------
|
|
CSpyTable::~CSpyTable()
|
|
{
|
|
// Delete the table
|
|
LocalFree(m_table);
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
//+-------------------------------------------------------------------------
|
|
//
|
|
// Member: CSpyTable::Add, public
|
|
//
|
|
// Synopsis: Add an entry to the hash table
|
|
//
|
|
// Arguments: void * - The allocation to add
|
|
//
|
|
// Algorithm:
|
|
//
|
|
// Returns: TRUE - Entry added
|
|
// FALSE - Memory failure expanding table
|
|
//
|
|
// History: 27-Oct-94 Brucema Created
|
|
//
|
|
// Notes: (1) This can only fail on a memory allocation failure
|
|
//
|
|
// (2) The j == j0 test guarantees the table is full since
|
|
// the algorithm is wrapping at a collision using a prime
|
|
// number which is relatively prime to m_cEntries
|
|
//
|
|
//--------------------------------------------------------------------------
|
|
BOOL CSpyTable::Add(void *allocation)
|
|
{
|
|
ULONG j0, j;
|
|
|
|
// Don't add null entries
|
|
if (allocation == NULL)
|
|
{
|
|
return FALSE;
|
|
}
|
|
|
|
// Search for an available entry
|
|
|
|
// Do until success or the table is full
|
|
j = j0 = ((ULONG) allocation) % m_cEntries;
|
|
do
|
|
{
|
|
j = (j + PRIME) % m_cEntries;
|
|
if (m_table[j].pAllocation != NULL)
|
|
{
|
|
m_table[j].dwCollision = TRUE;
|
|
}
|
|
} until_(m_table[j].pAllocation == NULL || j == j0);
|
|
|
|
// Found an available entry
|
|
if (j != j0)
|
|
{
|
|
m_table[j].pAllocation = allocation;
|
|
m_cAllocations++;
|
|
return TRUE;
|
|
}
|
|
|
|
// The table is full
|
|
else
|
|
{
|
|
// Expand the hash table
|
|
if (!Expand())
|
|
{
|
|
return FALSE;
|
|
}
|
|
|
|
// Call ourself recusively to add
|
|
return Add(allocation);
|
|
}
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
//+-------------------------------------------------------------------------
|
|
//
|
|
// Member: CSpyTable::Remove, public
|
|
//
|
|
// Synopsis: Remove an entry from the table
|
|
//
|
|
// Arguments: void * - The allocation to remove
|
|
//
|
|
// Algorithm:
|
|
//
|
|
// Returns: TRUE - Entry removed
|
|
// FALSE - Entry not found
|
|
//
|
|
// History: 27-Oct-94 Brucema Created
|
|
//
|
|
// Notes:
|
|
//
|
|
//--------------------------------------------------------------------------
|
|
BOOL CSpyTable::Remove(void *allocation)
|
|
{
|
|
ULONG j0, j;
|
|
|
|
// Search for the entry
|
|
if (Find(allocation, &j))
|
|
{
|
|
// Remove the entry
|
|
m_table[j].pAllocation = NULL;
|
|
|
|
// Remove collison markers from here backward until
|
|
// a non-empty entry (if next forward entry is not empty)
|
|
if (m_table[j].dwCollision)
|
|
{
|
|
j0 = (j + PRIME) % m_cEntries;
|
|
if (m_table[j].pAllocation == NULL && !m_table[j].dwCollision)
|
|
{
|
|
j0 = j;
|
|
do
|
|
{
|
|
m_table[j].dwCollision = FALSE;
|
|
j = (j - PRIME + m_cEntries) % m_cEntries;
|
|
} until_(m_table[j].pAllocation != NULL || j == j0);
|
|
}
|
|
}
|
|
m_cAllocations--;
|
|
return TRUE;
|
|
}
|
|
|
|
// Otherwise the entry was not found
|
|
else
|
|
{
|
|
return FALSE;
|
|
}
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
//+-------------------------------------------------------------------------
|
|
//
|
|
// Member: CSpyTable::Find, public
|
|
//
|
|
// Synopsis: Find an entry in the table
|
|
//
|
|
// Arguments: void * - The allocation to find
|
|
// ULONG * - Out parameter to store the index of
|
|
// the found entry
|
|
//
|
|
// Algorithm:
|
|
//
|
|
// Returns: TRUE - Entry found
|
|
// FALSE - Entry not found
|
|
//
|
|
// History: 27-Oct-94 Brucema Created
|
|
//
|
|
// Notes:
|
|
//
|
|
//--------------------------------------------------------------------------
|
|
BOOL CSpyTable::Find(void *allocation, ULONG *pulIndex)
|
|
{
|
|
ULONG j0, j;
|
|
|
|
// Don't search for null entries
|
|
if (allocation == NULL)
|
|
{
|
|
return FALSE;
|
|
}
|
|
|
|
// Search for the entry
|
|
|
|
// Do until success or end of the table is reached
|
|
j = j0 = ((ULONG) allocation) % m_cEntries;
|
|
do
|
|
{
|
|
j = (j + PRIME) % m_cEntries;
|
|
} until_(m_table[j].pAllocation == allocation ||
|
|
(m_table[j].pAllocation == NULL &&
|
|
m_table[j].dwCollision == FALSE) ||
|
|
j == j0);
|
|
|
|
// Return result
|
|
if (m_table[j].pAllocation == allocation)
|
|
{
|
|
*pulIndex = j;
|
|
return TRUE;
|
|
}
|
|
|
|
// Else not found
|
|
else
|
|
{
|
|
return FALSE;
|
|
}
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
//+-------------------------------------------------------------------------
|
|
//
|
|
// Member: CSpyTable::Expand, private
|
|
//
|
|
// Synopsis: Expand the hash table
|
|
//
|
|
// Arguments: -
|
|
//
|
|
// Algorithm:
|
|
//
|
|
// Returns: TRUE - Expansion successful
|
|
// FALSE - Memory allocation failure during expansion
|
|
//
|
|
// History: 27-Oct-94 Brucema Created
|
|
//
|
|
// Notes: To allow starting with a small table but not to do too many
|
|
// expansions in a large application, we expand by twice the
|
|
// current number of entries.
|
|
//
|
|
//--------------------------------------------------------------------------
|
|
BOOL CSpyTable::Expand(void)
|
|
{
|
|
LPAENTRY pOldTable;
|
|
|
|
// Save the current table
|
|
pOldTable = m_table;
|
|
|
|
// Allocate a new table
|
|
m_cEntries *= 2;
|
|
m_table = (LPAENTRY) LocalAlloc(LMEM_FIXED, m_cEntries * sizeof(AENTRY));
|
|
if (m_table == NULL)
|
|
{
|
|
m_table = pOldTable;
|
|
return FALSE;
|
|
}
|
|
|
|
// Initialize it
|
|
for (ULONG j = 0; j < m_cEntries; j++)
|
|
{
|
|
m_table[j].dwCollision = FALSE;
|
|
m_table[j].pAllocation = NULL;
|
|
}
|
|
|
|
// Restore the entries in the old table
|
|
m_cAllocations = 0;
|
|
for (j = 0; j < m_cEntries / 2; j++)
|
|
{
|
|
if (pOldTable[j].pAllocation != NULL)
|
|
{
|
|
Add(pOldTable[j].pAllocation);
|
|
}
|
|
}
|
|
|
|
// Clean up
|
|
LocalFree(pOldTable);
|
|
|
|
return TRUE;
|
|
}
|
|
|