418 lines
15 KiB
C++
Executable File
418 lines
15 KiB
C++
Executable File
#ifndef ADDRESS_INDEX_H_
|
|
#define ADDRESS_INDEX_H_
|
|
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
#include <stdio.h>
|
|
|
|
// *****************************************************************************
|
|
// * union AddressReference :
|
|
// * This union contains all of the components that are necessary to locate
|
|
// * and validate a memory address from within an AddressIndex object.
|
|
// *
|
|
// * The index entry contains the location of the pointer within the address
|
|
// * array.
|
|
// *
|
|
// * The checksum entry contains the checksum value that should be located
|
|
// * at the specified index within the checksum array.
|
|
// *
|
|
// *****************************************************************************
|
|
typedef union
|
|
{
|
|
unsigned rawData;
|
|
struct {
|
|
unsigned index : 24;
|
|
unsigned checksum : 8;
|
|
} value;
|
|
} AddressReference;
|
|
|
|
|
|
// *****************************************************************************
|
|
// * class AddressIndex:
|
|
// * This class is used to allow an array to be dereferenced using an integer
|
|
// * code that contains an array index and a checksum value. Both of these
|
|
// * values are validated before the user is allowed to access the data.
|
|
// *****************************************************************************
|
|
class AddressIndex
|
|
{
|
|
friend class AddressIndexIterator;
|
|
|
|
private:
|
|
enum {START_ARRAY_SIZE=1024};
|
|
|
|
// *********************************************************************
|
|
// * population : this integer identifies the exact number of data items
|
|
// * that currently exist in the list.
|
|
// *********************************************************************
|
|
int population;
|
|
|
|
// *********************************************************************
|
|
// * maxEntries : this integer identifies the maximum number of entries
|
|
// * that this object can contain.
|
|
// *********************************************************************
|
|
int maxEntries;
|
|
|
|
// *********************************************************************
|
|
// * curEntry : this integer identifies the currently selected entry.
|
|
// *********************************************************************
|
|
int curEntry;
|
|
|
|
// *********************************************************************
|
|
// * checksum : this is an array of bytes that are used to identify the
|
|
// * checksum for a specific address. This checksum is used to validate
|
|
// * that the address has not been changed externally.
|
|
// *********************************************************************
|
|
unsigned char * checksum;
|
|
|
|
// *********************************************************************
|
|
// * address : this is the array of addresses that will be stored and
|
|
// * retrieved using this object.
|
|
// *********************************************************************
|
|
void ** address;
|
|
|
|
|
|
public:
|
|
inline AddressIndex ( void );
|
|
inline ~AddressIndex ( void );
|
|
|
|
inline unsigned insert( void * ptr );
|
|
|
|
inline void remove( void * ptr );
|
|
inline void remove( unsigned idx );
|
|
|
|
inline unsigned find ( void * ptr );
|
|
inline void * find ( unsigned idx );
|
|
};
|
|
|
|
|
|
class AddressIndexIterator
|
|
{
|
|
private:
|
|
AddressIndex * index;
|
|
int current;
|
|
|
|
public:
|
|
inline AddressIndexIterator (AddressIndex * Index);
|
|
inline ~AddressIndexIterator( void );
|
|
|
|
inline void * first ( void );
|
|
inline void * operator ++ ( void );
|
|
inline void * operator ++ ( int x );
|
|
inline unsigned key ( void );
|
|
inline void * data ( void );
|
|
};
|
|
|
|
|
|
|
|
// *****************************************************************************
|
|
// * AddressIndex::AddressIndex :
|
|
// * This is the constructor for the AddressIndex class. It is allocates a
|
|
// * default number of entries in the checksum and address arrays and then
|
|
// * initializes the data values to 0.
|
|
// *
|
|
// * Note that these arrays must be allocated using malloc because we will
|
|
// * use realloc later to expand there size if necessary.
|
|
// *****************************************************************************
|
|
inline AddressIndex::AddressIndex ( void )
|
|
: population(0),maxEntries(0),curEntry(0),checksum(NULL),address(NULL)
|
|
{
|
|
maxEntries = START_ARRAY_SIZE;
|
|
checksum = (unsigned char *)malloc(sizeof(unsigned char)*maxEntries);
|
|
address = (void **) malloc(sizeof(void *) *maxEntries);
|
|
memset(checksum, 1, sizeof(unsigned char)*maxEntries);
|
|
memset(address, 0, sizeof(void *) *maxEntries);
|
|
}
|
|
|
|
|
|
// *****************************************************************************
|
|
// * AddressIndex::~AddressIndex :
|
|
// * This is the destructor for the object. It will deallocate any memory
|
|
// * that has been assigned to the checksum or address objects.
|
|
// *
|
|
// * Note that these arrays must be deallocated using the free library call
|
|
// * because they were allocated using either malloc or realloc.
|
|
// *****************************************************************************
|
|
inline AddressIndex::~AddressIndex ( void )
|
|
{
|
|
if(checksum!=NULL) free(checksum);
|
|
if(address!=NULL) free(address);
|
|
}
|
|
|
|
|
|
// *****************************************************************************
|
|
// * AddressIndex::insert :
|
|
// * This method is used to insert a void * pointer into the AddressIndex
|
|
// * object. It returns an unsigned integer result which is the rawData
|
|
// * component of an AddressReference object.
|
|
// *****************************************************************************
|
|
inline unsigned AddressIndex::insert ( void * ptr )
|
|
{
|
|
AddressReference result;
|
|
|
|
// *********************************************************************
|
|
// * Initial all entries within the AddressReference object before
|
|
// * starting.
|
|
// *********************************************************************
|
|
result.rawData = 0U;
|
|
|
|
// *********************************************************************
|
|
// * If the pointer provided by the user is NULL, then it cannot be
|
|
// * inserted into the list... Otherwise,
|
|
// *
|
|
// * From the current position in the array, we are going to walk
|
|
// * forward until we find an empty slot. An empty slot is indicated
|
|
// * by the value NULL in its address.
|
|
// *
|
|
// * If the end of the list is reached before an empty slot can be found
|
|
// * then special considerations will be made as described below.
|
|
// *********************************************************************
|
|
if(ptr!=NULL)
|
|
{
|
|
while(curEntry<maxEntries && address[curEntry]!=NULL) curEntry++;
|
|
|
|
// *************************************************************
|
|
// * If curEntry>=maxEntries then an empty slot was not located.
|
|
// * The following options should be considered...
|
|
// *************************************************************
|
|
|
|
// *************************************************************
|
|
// * 1) If the population of the table is less than half of the
|
|
// * maximum number of entries... go back to the beginning
|
|
// * and search the table for an empty slot.
|
|
// *************************************************************
|
|
if(curEntry>=maxEntries && population<(maxEntries/2))
|
|
{
|
|
curEntry = 0;
|
|
while(curEntry<maxEntries && address[curEntry]!=NULL)
|
|
{
|
|
curEntry++;
|
|
}
|
|
}
|
|
|
|
// *************************************************************
|
|
// * 2) If the population of the table is more than half of the
|
|
// * maximum number of entries... double the size of the
|
|
// * table and continue from the current cursor position.
|
|
// * Note: the newly allocated data at the end of the buffer
|
|
// * must be initialized to 0.
|
|
// *************************************************************
|
|
else if(curEntry>=maxEntries)
|
|
{
|
|
curEntry = maxEntries;
|
|
maxEntries*=2;
|
|
checksum = (unsigned char *)realloc(checksum, sizeof(char *)*maxEntries);
|
|
address = (void **) realloc(address, sizeof(void *)*maxEntries);
|
|
memset(&checksum[curEntry], 0, sizeof(char *)*curEntry);
|
|
memset(&address [curEntry], 0, sizeof(void *)*curEntry);
|
|
}
|
|
|
|
// *************************************************************
|
|
// * At this time the curEntry index points to the insertion
|
|
// * point that should be used. Place the index and checksum
|
|
// * information into the result object and update the
|
|
// * population count.
|
|
// *************************************************************
|
|
checksum[curEntry] = (checksum[curEntry]==255?1:(checksum[curEntry]+1));
|
|
address [curEntry] = ptr;
|
|
|
|
result.value.index = curEntry;
|
|
result.value.checksum = checksum[curEntry];
|
|
|
|
population++;
|
|
}
|
|
|
|
// *********************************************************************
|
|
// * Return the rawData portion of the AddressReference to the caller
|
|
// * as an unsigned integer.
|
|
// *********************************************************************
|
|
return result.rawData;
|
|
}
|
|
|
|
|
|
// *****************************************************************************
|
|
// * AddressIndex::remove :
|
|
// * This function will locate an entry by searching the array for a
|
|
// * specific pointer. If the entry is found it will be deleted. Direct
|
|
// * searching is one of the most time consuming approaches to locating
|
|
// * data, therefore the remove function that uses an unsigned integer
|
|
// * identifier should be used whenever possible.
|
|
// *****************************************************************************
|
|
inline void AddressIndex::remove ( void * ptr)
|
|
{
|
|
if(ptr!=NULL)
|
|
{
|
|
for(int idx=0; idx<maxEntries && address[idx]!=ptr; idx++);
|
|
if(idx<maxEntries)
|
|
{
|
|
address[idx]=NULL;
|
|
population--;
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
// *****************************************************************************
|
|
// * AddressIndex::remove :
|
|
// * This function will locate a specific entry based on the long integer
|
|
// * identifier. If the entry is valid and has a matching checksum, then
|
|
// * it will be removed from the list.
|
|
// *****************************************************************************
|
|
inline void AddressIndex::remove ( unsigned idx )
|
|
{
|
|
AddressReference ref;
|
|
ref.rawData = idx;
|
|
|
|
if(ref.value.index<maxEntries &&
|
|
ref.value.checksum==checksum[ref.value.index])
|
|
{
|
|
address[ref.value.index] = NULL;
|
|
population--;
|
|
}
|
|
}
|
|
|
|
|
|
// *****************************************************************************
|
|
// * AddressIndex::find :
|
|
// * This function will locate an entry within the list using a pointer to
|
|
// * its memory address and will return an unsigned integer indicating its
|
|
// * location. If the returned bvalue is 0, then the ptr was not found...
|
|
// *****************************************************************************
|
|
inline unsigned AddressIndex::find ( void * ptr )
|
|
{
|
|
AddressReference result;
|
|
int idx;
|
|
result.rawData = 0U;
|
|
|
|
for(idx=0; idx<maxEntries && address[idx]!=ptr; idx++);
|
|
if(idx<maxEntries)
|
|
{
|
|
result.value.index =idx;
|
|
result.value.checksum = checksum[idx];
|
|
}
|
|
|
|
return result.rawData;
|
|
}
|
|
|
|
|
|
// *****************************************************************************
|
|
// * AddressIndex::find :
|
|
// * This function will obtain a pointer to the data item using the user
|
|
// * provided unsigned index. A value of NULL will be returned if the
|
|
// * data item could not be located or if the unsigned index was invalid.
|
|
// *****************************************************************************
|
|
inline void * AddressIndex::find ( unsigned idx )
|
|
{
|
|
void * result = NULL;
|
|
AddressReference ref;
|
|
|
|
ref.rawData = idx;
|
|
|
|
if(ref.value.index<maxEntries &&
|
|
ref.value.checksum==checksum[ref.value.index])
|
|
{
|
|
result = address[ref.value.index];
|
|
}
|
|
|
|
return result;
|
|
}
|
|
|
|
// *****************************************************************************
|
|
// * AddressIndexIterator::AddressIndexIterator:
|
|
// * Simple constructor for the AddressIndexIterator class.
|
|
// *****************************************************************************
|
|
inline AddressIndexIterator::AddressIndexIterator (AddressIndex * Index)
|
|
: index(Index), current (0)
|
|
{}
|
|
|
|
|
|
// *****************************************************************************
|
|
// * AddressIndexIterator::~AddressIndexIterator :
|
|
// * Destructor for the AddressIndexIterator... does nothing.
|
|
// *****************************************************************************
|
|
inline AddressIndexIterator::~AddressIndexIterator( void ) {}
|
|
|
|
|
|
// *****************************************************************************
|
|
// * AddressIndexIterator::first :
|
|
// * Repositions to the first entry in the AddressIndex.
|
|
// *****************************************************************************
|
|
inline void * AddressIndexIterator::first( void )
|
|
{
|
|
current = 0;
|
|
|
|
while(index->population &&
|
|
current<index->maxEntries &&
|
|
index->address[current]==NULL)
|
|
{
|
|
current++;
|
|
}
|
|
return (index->population && current<index->maxEntries)?index->address[current]:NULL;
|
|
}
|
|
|
|
|
|
// *****************************************************************************
|
|
// * AddressIndexIterator::operator ++ :
|
|
// * Repositions to the next entry in the AddressIndex.
|
|
// *****************************************************************************
|
|
inline void * AddressIndexIterator::operator ++ ( void )
|
|
{
|
|
current++;
|
|
|
|
while(index->population &&
|
|
current<index->maxEntries &&
|
|
index->address[current]==NULL)
|
|
{
|
|
current++;
|
|
}
|
|
return (index->population && current<index->maxEntries)?index->address[current]:NULL;
|
|
}
|
|
|
|
|
|
// *****************************************************************************
|
|
// * AddressIndexIterator::operator ++ :
|
|
// * Repositions to the next entry in the AddressIndex.
|
|
// *****************************************************************************
|
|
inline void * AddressIndexIterator::operator ++ ( int x )
|
|
{
|
|
current++;
|
|
|
|
while(x==0 &&
|
|
index->population &&
|
|
current<index->maxEntries &&
|
|
index->address[current]==NULL)
|
|
{
|
|
current++;
|
|
}
|
|
return (x==0 && index->population && current<index->maxEntries)?index->address[current]:NULL;
|
|
}
|
|
|
|
// *****************************************************************************
|
|
// * AddressIndexIterator::key :
|
|
// * This method will return the AddressIndex key value of the current entry.
|
|
// *****************************************************************************
|
|
inline unsigned AddressIndexIterator::key ( void )
|
|
{
|
|
AddressReference result;
|
|
|
|
result.rawData = 0;
|
|
if(current<index->maxEntries && index->address[current]!=NULL)
|
|
{
|
|
result.value.index = current;
|
|
result.value.checksum = index->checksum[current];
|
|
}
|
|
return result.rawData;
|
|
}
|
|
|
|
|
|
// *****************************************************************************
|
|
// * AddressIndexIterator::data :
|
|
// * This method will return the data value of the current entry.
|
|
// *****************************************************************************
|
|
inline void * AddressIndexIterator::data ( void )
|
|
{
|
|
return(current<index->maxEntries)?index->address[current]:NULL;
|
|
}
|
|
|
|
|
|
#endif /* ADDRESS_INDEX_H_ */
|