You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
136 lines
2.5 KiB
136 lines
2.5 KiB
/*++
|
|
|
|
Copyright (c) 1995 Microsoft Corporation
|
|
|
|
Module Name:
|
|
|
|
BList.cxx
|
|
|
|
Abstract:
|
|
|
|
Implements out of line methods on blists.
|
|
|
|
Author:
|
|
|
|
Mario Goertzel [MarioGo]
|
|
|
|
Revision History:
|
|
|
|
MarioGo 95-03-02 Bits 'n pieces
|
|
MarioGo 95-09-07 Was blist.inl, change from template to generic class for PPC.
|
|
--*/
|
|
|
|
#include<or.hxx>
|
|
|
|
ULONG
|
|
CBList::Hash(PVOID p)
|
|
{
|
|
ULONG t = PtrToUlong(p);
|
|
|
|
return ( ((t << 9) ^ (t >> 5) ^ (t >> 15)) % _ulmaxData);
|
|
}
|
|
|
|
ORSTATUS
|
|
CBList::Insert(PVOID p)
|
|
{
|
|
if ( _data == 0
|
|
|| _ulcElements > (_ulmaxData - (_ulmaxData/8 + 1)))
|
|
{
|
|
// Table getting full, grow it.
|
|
// See Kenuth on linear probe hash performance as the table fills.
|
|
|
|
ULONG i, ulmaxOldData = _ulmaxData;
|
|
PVOID *ppOldData = _data;
|
|
_data = new PVOID[_ulmaxData * 2];
|
|
|
|
if (0 == _data)
|
|
{
|
|
_data = ppOldData;
|
|
return(OR_NOMEM);
|
|
}
|
|
|
|
_ulmaxData *= 2;
|
|
_ulcElements = 0;
|
|
|
|
OrMemorySet(_data, 0, _ulmaxData*sizeof(PVOID));
|
|
|
|
if (ppOldData)
|
|
{
|
|
for(i = 0; i < ulmaxOldData; i++)
|
|
{
|
|
if (ppOldData[i])
|
|
{
|
|
ORSTATUS status = Insert(ppOldData[i]);
|
|
ASSERT(status == OR_OK);
|
|
}
|
|
}
|
|
|
|
delete ppOldData;
|
|
}
|
|
}
|
|
|
|
register ULONG i = Hash(p);
|
|
|
|
while(_data[i])
|
|
{
|
|
i = (i + 1) % _ulmaxData;
|
|
}
|
|
|
|
_data[i] = p;
|
|
_ulcElements++;
|
|
|
|
return(OR_OK);
|
|
}
|
|
|
|
PVOID
|
|
CBList::Remove(PVOID p)
|
|
{
|
|
register ULONG i, hash;
|
|
|
|
if (_data)
|
|
{
|
|
i = hash = Hash(p);
|
|
|
|
if (_data[i] != p)
|
|
{
|
|
do
|
|
{
|
|
i = (i + 1) % _ulmaxData;
|
|
}
|
|
while(_data[i] != p && i != hash);
|
|
}
|
|
|
|
if (_data[i] == p)
|
|
{
|
|
_data[i] = 0;
|
|
_ulcElements--;
|
|
return(p);
|
|
}
|
|
|
|
ASSERT(i == hash);
|
|
}
|
|
|
|
return(0);
|
|
}
|
|
|
|
BOOL
|
|
CBList::Member(PVOID p)
|
|
{
|
|
int i, hash;
|
|
|
|
if (0 == _data)
|
|
return(FALSE);
|
|
|
|
i = hash = Hash(p);
|
|
if (_data[i] == p)
|
|
return(TRUE);
|
|
|
|
do
|
|
{
|
|
i = (i + 1) % _ulmaxData;
|
|
}
|
|
while(_data[i] != p && i != hash);
|
|
|
|
return(_data[i] == p);
|
|
}
|
|
|