109 lines
2.6 KiB
C++
109 lines
2.6 KiB
C++
|
///////////////////////////////////////////////////////////////////////////////
|
||
|
|
//
|
||
|
|
// Copyright (c) 1999, Microsoft Corp. All rights reserved.
|
||
|
|
//
|
||
|
|
// FILE
|
||
|
|
//
|
||
|
|
// attridx.cpp
|
||
|
|
//
|
||
|
|
// SYNOPSIS
|
||
|
|
//
|
||
|
|
// Defines the class AttributeIndex
|
||
|
|
//
|
||
|
|
// MODIFICATION HISTORY
|
||
|
|
//
|
||
|
|
// 02/04/2000 Original version.
|
||
|
|
//
|
||
|
|
///////////////////////////////////////////////////////////////////////////////
|
||
|
|
|
||
|
|
#include <proxypch.h>
|
||
|
|
#include <attridx.h>
|
||
|
|
#include <attrdnry.h>
|
||
|
|
|
||
|
|
void AttributeIndex::create(
|
||
|
|
const AttributeDefinition* begin,
|
||
|
|
const AttributeDefinition* end,
|
||
|
|
HashFn hash,
|
||
|
|
EqualFn equal,
|
||
|
|
FilterFn filterFn
|
||
|
|
)
|
||
|
|
{
|
||
|
|
const AttributeDefinition* i;
|
||
|
|
|
||
|
|
// Delete any existing index.
|
||
|
|
delete[] table;
|
||
|
|
table = NULL;
|
||
|
|
|
||
|
|
// Same the funtion pointers.
|
||
|
|
hashFn = hash;
|
||
|
|
equalFn = equal;
|
||
|
|
|
||
|
|
// Determine how many entries are in the index.
|
||
|
|
ULONG count;
|
||
|
|
if (filterFn)
|
||
|
|
{
|
||
|
|
count = 0;
|
||
|
|
for (i = begin; i != end; ++i)
|
||
|
|
{
|
||
|
|
if (filterFn(*i)) { ++count; }
|
||
|
|
}
|
||
|
|
}
|
||
|
|
else
|
||
|
|
{
|
||
|
|
count = end - begin;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Buckets should be a power of two.
|
||
|
|
ULONG buckets = 1;
|
||
|
|
while (buckets < count) { buckets <<= 1; }
|
||
|
|
|
||
|
|
// Set the hash mask.
|
||
|
|
mask = buckets - 1;
|
||
|
|
|
||
|
|
// Allocate the buckets and nodes.
|
||
|
|
SIZE_T nbyte = sizeof(Bucket) * buckets + sizeof(Node) * count;
|
||
|
|
table = (Bucket*)operator new(nbyte);
|
||
|
|
Node* node = (Node*)(table + buckets);
|
||
|
|
|
||
|
|
// Zeroize the hash table.
|
||
|
|
memset(table, 0, sizeof(Bucket) * buckets);
|
||
|
|
|
||
|
|
// Iterate through the definitions to be indexed.
|
||
|
|
for (i = begin; i != end; ++i)
|
||
|
|
{
|
||
|
|
// Should we index this one?
|
||
|
|
if (!filterFn || filterFn(*i))
|
||
|
|
{
|
||
|
|
// Yes, so compute the bucket.
|
||
|
|
Bucket* bucket = table + (hashFn(*i) & mask);
|
||
|
|
|
||
|
|
// Insert the node at the head of the linked list.
|
||
|
|
node->next = *bucket;
|
||
|
|
*bucket = node;
|
||
|
|
|
||
|
|
// Store the definition.
|
||
|
|
node->def = i;
|
||
|
|
|
||
|
|
// Advance to the next node.
|
||
|
|
++node;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
const AttributeDefinition* AttributeIndex::find(
|
||
|
|
const AttributeDefinition& key
|
||
|
|
) const throw ()
|
||
|
|
{
|
||
|
|
// Get the appropriate bucket.
|
||
|
|
Bucket* bucket = table + (hashFn(key) & mask);
|
||
|
|
|
||
|
|
// Iterate through the linked list ...
|
||
|
|
for (const Node* node = *bucket; node; node = node->next)
|
||
|
|
{
|
||
|
|
// ... and look for a match.
|
||
|
|
if (equalFn(*node->def, key)) { return node->def; }
|
||
|
|
}
|
||
|
|
|
||
|
|
return NULL;
|
||
|
|
}
|