VisitedLinkTable.cpp [plain text]
#include "config.h"
#include "VisitedLinkTable.h"
#include "SharedMemory.h"
using namespace WebCore;
namespace WebKit {
VisitedLinkTable::VisitedLinkTable()
: m_tableSize(0)
, m_tableSizeMask(0)
, m_table(nullptr)
{
}
VisitedLinkTable::~VisitedLinkTable()
{
}
#if !ASSERT_DISABLED
static inline bool isPowerOf2(unsigned v)
{
return !(v & (v - 1)) && v;
}
#endif
void VisitedLinkTable::setSharedMemory(PassRefPtr<SharedMemory> sharedMemory)
{
m_sharedMemory = sharedMemory;
ASSERT(m_sharedMemory);
ASSERT(!(m_sharedMemory->size() % sizeof(LinkHash)));
m_table = static_cast<LinkHash*>(m_sharedMemory->data());
m_tableSize = m_sharedMemory->size() / sizeof(LinkHash);
ASSERT(isPowerOf2(m_tableSize));
m_tableSizeMask = m_tableSize - 1;
}
static inline unsigned doubleHash(unsigned key)
{
key = ~key + (key >> 23);
key ^= (key << 12);
key ^= (key >> 7);
key ^= (key << 2);
key ^= (key >> 20);
return key;
}
bool VisitedLinkTable::addLinkHash(LinkHash linkHash)
{
ASSERT(m_sharedMemory);
int k = 0;
LinkHash* table = m_table;
int sizeMask = m_tableSizeMask;
unsigned h = static_cast<unsigned>(linkHash);
int i = h & sizeMask;
LinkHash* entry;
while (1) {
entry = table + i;
if (!*entry)
break;
if (*entry == linkHash)
return false;
if (!k)
k = 1 | doubleHash(h);
i = (i + k) & sizeMask;
}
*entry = linkHash;
return true;
}
bool VisitedLinkTable::isLinkVisited(LinkHash linkHash) const
{
if (!m_sharedMemory)
return false;
int k = 0;
LinkHash* table = m_table;
int sizeMask = m_tableSizeMask;
unsigned h = static_cast<unsigned>(linkHash);
int i = h & sizeMask;
LinkHash* entry;
while (1) {
entry = table + i;
if (!*entry)
break;
if (*entry == linkHash)
return true;
if (!k)
k = 1 | doubleHash(h);
i = (i + k) & sizeMask;
}
return false;
}
void VisitedLinkTable::clear()
{
m_tableSize = 0;
m_tableSizeMask = 0;
m_sharedMemory = nullptr;
}
}