//===--- OnDiskHashTable.h - On-Disk Hash Table Implementation --*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
///
/// \file
/// Defines facilities for reading and writing on-disk hash tables.
///
//===----------------------------------------------------------------------===//
#ifndef LLVM_SUPPORT_ONDISKHASHTABLE_H
#define LLVM_SUPPORT_ONDISKHASHTABLE_H
#include "llvm/Support/Alignment.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/DataTypes.h"
#include "llvm/Support/EndianStream.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <cstdlib>
namespace llvm {
/// Generates an on disk hash table.
///
/// This needs an \c Info that handles storing values into the hash table's
/// payload and computes the hash for a given key. This should provide the
/// following interface:
///
/// \code
/// class ExampleInfo {
/// public:
/// typedef ExampleKey key_type; // Must be copy constructible
/// typedef ExampleKey &key_type_ref;
/// typedef ExampleData data_type; // Must be copy constructible
/// typedef ExampleData &data_type_ref;
/// typedef uint32_t hash_value_type; // The type the hash function returns.
/// typedef uint32_t offset_type; // The type for offsets into the table.
///
/// /// Calculate the hash for Key
/// static hash_value_type ComputeHash(key_type_ref Key);
/// /// Return the lengths, in bytes, of the given Key/Data pair.
/// static std::pair<offset_type, offset_type>
/// EmitKeyDataLength(raw_ostream &Out, key_type_ref Key, data_type_ref Data);
/// /// Write Key to Out. KeyLen is the length from EmitKeyDataLength.
/// static void EmitKey(raw_ostream &Out, key_type_ref Key,
/// offset_type KeyLen);
/// /// Write Data to Out. DataLen is the length from EmitKeyDataLength.
/// static void EmitData(raw_ostream &Out, key_type_ref Key,
/// data_type_ref Data, offset_type DataLen);
/// /// Determine if two keys are equal. Optional, only needed by contains.
/// static bool EqualKey(key_type_ref Key1, key_type_ref Key2);
/// };
/// \endcode
template <typename Info> class OnDiskChainedHashTableGenerator {
/// A single item in the hash table.
class Item {
public:
typename Info::key_type Key;
typename Info::data_type Data;
Item *Next;
const typename Info::hash_value_type Hash;
Item(typename Info::key_type_ref Key, typename Info::data_type_ref Data,
Info &InfoObj)
: Key(Key), Data(Data), Next(nullptr), Hash(InfoObj.ComputeHash(Key)) {}
};
typedef typename Info::offset_type offset_type;
offset_type NumBuckets;
offset_type NumEntries;
llvm::SpecificBumpPtrAllocator<Item> BA;
/// A linked list of values in a particular hash bucket.
struct Bucket {
offset_type Off;
unsigned Length;
Item *Head;
};
Bucket *Buckets;
private:
/// Insert an item into the appropriate hash bucket.
void insert(Bucket *Buckets, size_t Size, Item *E) {
Bucket &B = Buckets[E->Hash & (Size - 1)];
E->Next = B.Head;
++B.Length;
B.Head = E;
}
/// Resize the hash table, moving the old entries into the new buckets.
void resize(size_t NewSize) {
Bucket *NewBuckets = static_cast<Bucket *>(
safe_calloc(NewSize, sizeof(Bucket)));
// Populate NewBuckets with the old entries.
for (size_t I = 0; I < NumBuckets; ++I)
for (Item *E = Buckets[I].Head; E;) {
Item *N = E->Next;
E->Next = nullptr;
insert(NewBuckets, NewSize, E);
E = N;
}
free(Buckets);
NumBuckets = NewSize;
Buckets = NewBuckets;
}
public:
/// Insert an entry into the table.
void insert(typename Info::key_type_ref Key,
typename Info::data_type_ref Data) {
Info InfoObj;
insert(Key, Data, InfoObj);
}
/// Insert an entry into the table.
///
/// Uses the provided Info instead of a stack allocated one.
void insert(typename Info::key_type_ref Key,
typename Info::data_type_ref Data, Info &InfoObj) {
++NumEntries;
if (4 * NumEntries >= 3 * NumBuckets)
resize(NumBuckets * 2);
insert(Buckets, NumBuckets, new (BA.Allocate()) Item(Key, Data, InfoObj));
}
/// Determine whether an entry has been inserted.
bool contains(typename Info::key_type_ref Key, Info &InfoObj) {
unsigned Hash = InfoObj.ComputeHash(Key);
for (Item *I = Buckets[Hash & (NumBuckets - 1)].Head; I; I = I->Next)
if (I->Hash == Hash && InfoObj.EqualKey(I->Key, Key))
return true;
return false;
}
/// Emit the table to Out, which must not be at offset 0.
offset_type Emit(raw_ostream &Out) {
Info InfoObj;
return Emit(Out, InfoObj);
}
/// Emit the table to Out, which must not be at offset 0.
///
/// Uses the provided Info instead of a stack allocated one.
offset_type Emit(raw_ostream &Out, Info &InfoObj) {
using namespace llvm::support;
endian::Writer LE(Out, little);
// Now we're done adding entries, resize the bucket list if it's
// significantly too large. (This only happens if the number of
// entries is small and we're within our initial allocation of
// 64 buckets.) We aim for an occupancy ratio in [3/8, 3/4).
//
// As a special case, if there are two or fewer entries, just
// form a single bucket. A linear scan is fine in that case, and
// this is very common in C++ class lookup tables. This also
// guarantees we produce at least one bucket for an empty table.
//
// FIXME: Try computing a perfect hash function at this point.
unsigned TargetNumBuckets =
NumEntries <= 2 ? 1 : NextPowerOf2(NumEntries * 4 / 3);
if (TargetNumBuckets != NumBuckets)
resize(TargetNumBuckets);
// Emit the payload of the table.
for (offset_type I = 0; I < NumBuckets; ++I) {
Bucket &B = Buckets[I];
if (!B.Head)
continue;
// Store the offset for the data of this bucket.
B.Off = Out.tell();
assert(B.Off && "Cannot write a bucket at offset 0. Please add padding.");
// Write out the number of items in the bucket.
LE.write<uint16_t>(B.Length);
assert(B.Length != 0 && "Bucket has a head but zero length?");
// Write out the entries in the bucket.
for (Item *I = B.Head; I; I = I->Next) {
LE.write<typename Info::hash_value_type>(I->Hash);
const std::pair<offset_type, offset_type> &Len =
InfoObj.EmitKeyDataLength(Out, I->Key, I->Data);
#ifdef NDEBUG
InfoObj.EmitKey(Out, I->Key, Len.first);
InfoObj.EmitData(Out, I->Key, I->Data, Len.second);
#else
// In asserts mode, check that the users length matches the data they
// wrote.
uint64_t KeyStart = Out.tell();
InfoObj.EmitKey(Out, I->Key, Len.first);
uint64_t DataStart = Out.tell();
InfoObj.EmitData(Out, I->Key, I->Data, Len.second);
uint64_t End = Out.tell();
assert(offset_type(DataStart - KeyStart) == Len.first &&
"key length does not match bytes written");
assert(offset_type(End - DataStart) == Len.second &&
"data length does not match bytes written");
#endif
}
}
// Pad with zeros so that we can start the hashtable at an aligned address.
offset_type TableOff = Out.tell();
uint64_t N = offsetToAlignment(TableOff, Align(alignof(offset_type)));
TableOff += N;
while (N--)
LE.write<uint8_t>(0);
// Emit the hashtable itself.
LE.write<offset_type>(NumBuckets);
LE.write<offset_type>(NumEntries);
for (offset_type I = 0; I < NumBuckets; ++I)
LE.write<offset_type>(Buckets[I].Off);
return TableOff;
}
OnDiskChainedHashTableGenerator() {
NumEntries = 0;
NumBuckets = 64;
// Note that we do not need to run the constructors of the individual
// Bucket objects since 'calloc' returns bytes that are all 0.
Buckets = static_cast<Bucket *>(safe_calloc(NumBuckets, sizeof(Bucket)));
}
~OnDiskChainedHashTableGenerator() { std::free(Buckets); }
};
/// Provides lookup on an on disk hash table.
///
/// This needs an \c Info that handles reading values from the hash table's
/// payload and computes the hash for a given key. This should provide the
/// following interface:
///
/// \code
/// class ExampleLookupInfo {
/// public:
/// typedef ExampleData data_type;
/// typedef ExampleInternalKey internal_key_type; // The stored key type.
/// typedef ExampleKey external_key_type; // The type to pass to find().
/// typedef uint32_t hash_value_type; // The type the hash function returns.
/// typedef uint32_t offset_type; // The type for offsets into the table.
///
/// /// Compare two keys for equality.
/// static bool EqualKey(internal_key_type &Key1, internal_key_type &Key2);
/// /// Calculate the hash for the given key.
/// static hash_value_type ComputeHash(internal_key_type &IKey);
/// /// Translate from the semantic type of a key in the hash table to the
/// /// type that is actually stored and used for hashing and comparisons.
/// /// The internal and external types are often the same, in which case this
/// /// can simply return the passed in value.
/// static const internal_key_type &GetInternalKey(external_key_type &EKey);
/// /// Read the key and data length from Buffer, leaving it pointing at the
/// /// following byte.
/// static std::pair<offset_type, offset_type>
/// ReadKeyDataLength(const unsigned char *&Buffer);
/// /// Read the key from Buffer, given the KeyLen as reported from
/// /// ReadKeyDataLength.
/// const internal_key_type &ReadKey(const unsigned char *Buffer,
/// offset_type KeyLen);
/// /// Read the data for Key from Buffer, given the DataLen as reported from
/// /// ReadKeyDataLength.
/// data_type ReadData(StringRef Key, const unsigned char *Buffer,
/// offset_type DataLen);
/// };
/// \endcode
template <typename Info> class OnDiskChainedHashTable {
const typename Info::offset_type NumBuckets;
const typename Info::offset_type NumEntries;
const unsigned char *const Buckets;
const unsigned char *const Base;
Info InfoObj;
public:
typedef Info InfoType;
typedef typename Info::internal_key_type internal_key_type;
typedef typename Info::external_key_type external_key_type;
typedef typename Info::data_type data_type;
typedef typename Info::hash_value_type hash_value_type;
typedef typename Info::offset_type offset_type;
OnDiskChainedHashTable(offset_type NumBuckets, offset_type NumEntries,
const unsigned char *Buckets,
const unsigned char *Base,
const Info &InfoObj = Info())
: NumBuckets(NumBuckets), NumEntries(NumEntries), Buckets(Buckets),
Base(Base), InfoObj(InfoObj) {
assert((reinterpret_cast<uintptr_t>(Buckets) & 0x3) == 0 &&
"'buckets' must have a 4-byte alignment");
}
/// Read the number of buckets and the number of entries from a hash table
/// produced by OnDiskHashTableGenerator::Emit, and advance the Buckets
/// pointer past them.
static std::pair<offset_type, offset_type>
readNumBucketsAndEntries(const unsigned char *&Buckets) {
assert((reinterpret_cast<uintptr_t>(Buckets) & 0x3) == 0 &&
"buckets should be 4-byte aligned.");
using namespace llvm::support;
offset_type NumBuckets =
endian::readNext<offset_type, little, aligned>(Buckets);
offset_type NumEntries =
endian::readNext<offset_type, little, aligned>(Buckets);
return std::make_pair(NumBuckets, NumEntries);
}
offset_type getNumBuckets() const { return NumBuckets; }
offset_type getNumEntries() const { return NumEntries; }
const unsigned char *getBase() const { return Base; }
const unsigned char *getBuckets() const { return Buckets; }
bool isEmpty() const { return NumEntries == 0; }
class iterator {
internal_key_type Key;
const unsigned char *const Data;
const offset_type Len;
Info *InfoObj;
public:
iterator() : Key(), Data(nullptr), Len(0), InfoObj(nullptr) {}
iterator(const internal_key_type K, const unsigned char *D, offset_type L,
Info *InfoObj)
: Key(K), Data(D), Len(L), InfoObj(InfoObj) {}
data_type operator*() const { return InfoObj->ReadData(Key, Data, Len); }
const unsigned char *getDataPtr() const { return Data; }
offset_type getDataLen() const { return Len; }
bool operator==(const iterator &X) const { return X.Data == Data; }
bool operator!=(const iterator &X) const { return X.Data != Data; }
};
/// Look up the stored data for a particular key.
iterator find(const external_key_type &EKey, Info *InfoPtr = nullptr) {
const internal_key_type &IKey = InfoObj.GetInternalKey(EKey);
hash_value_type KeyHash = InfoObj.ComputeHash(IKey);
return find_hashed(IKey, KeyHash, InfoPtr);
}
/// Look up the stored data for a particular key with a known hash.
iterator find_hashed(const internal_key_type &IKey, hash_value_type KeyHash,
Info *InfoPtr = nullptr) {
using namespace llvm::support;
if (!InfoPtr)
InfoPtr = &InfoObj;
// Each bucket is just an offset into the hash table file.
offset_type Idx = KeyHash & (NumBuckets - 1);
const unsigned char *Bucket = Buckets + sizeof(offset_type) * Idx;
offset_type Offset = endian::readNext<offset_type, little, aligned>(Bucket);
if (Offset == 0)
return iterator(); // Empty bucket.
const unsigned char *Items = Base + Offset;
// 'Items' starts with a 16-bit unsigned integer representing the
// number of items in this bucket.
unsigned Len = endian::readNext<uint16_t, little, unaligned>(Items);
for (unsigned i = 0; i < Len; ++i) {
// Read the hash.
hash_value_type ItemHash =
endian::readNext<hash_value_type, little, unaligned>(Items);
// Determine the length of the key and the data.
const std::pair<offset_type, offset_type> &L =
Info::ReadKeyDataLength(Items);
offset_type ItemLen = L.first + L.second;
// Compare the hashes. If they are not the same, skip the entry entirely.
if (ItemHash != KeyHash) {
Items += ItemLen;
continue;
}
// Read the key.
const internal_key_type &X =
InfoPtr->ReadKey((const unsigned char *const)Items, L.first);
// If the key doesn't match just skip reading the value.
if (!InfoPtr->EqualKey(X, IKey)) {
Items += ItemLen;
continue;
}
// The key matches!
return iterator(X, Items + L.first, L.second, InfoPtr);
}
return iterator();
}
iterator end() const { return iterator(); }
Info &getInfoObj() { return InfoObj; }
/// Create the hash table.
///
/// \param Buckets is the beginning of the hash table itself, which follows
/// the payload of entire structure. This is the value returned by
/// OnDiskHashTableGenerator::Emit.
///
/// \param Base is the point from which all offsets into the structure are
/// based. This is offset 0 in the stream that was used when Emitting the
/// table.
static OnDiskChainedHashTable *Create(const unsigned char *Buckets,
const unsigned char *const Base,
const Info &InfoObj = Info()) {
assert(Buckets > Base);
auto NumBucketsAndEntries = readNumBucketsAndEntries(Buckets);
return new OnDiskChainedHashTable<Info>(NumBucketsAndEntries.first,
NumBucketsAndEntries.second,
Buckets, Base, InfoObj);
}
};
/// Provides lookup and iteration over an on disk hash table.
///
/// \copydetails llvm::OnDiskChainedHashTable
template <typename Info>
class OnDiskIterableChainedHashTable : public OnDiskChainedHashTable<Info> {
const unsigned char *Payload;
public:
typedef OnDiskChainedHashTable<Info> base_type;
typedef typename base_type::internal_key_type internal_key_type;
typedef typename base_type::external_key_type external_key_type;
typedef typename base_type::data_type data_type;
typedef typename base_type::hash_value_type hash_value_type;
typedef typename base_type::offset_type offset_type;
private:
/// Iterates over all of the keys in the table.
class iterator_base {
const unsigned char *Ptr;
offset_type NumItemsInBucketLeft;
offset_type NumEntriesLeft;
public:
typedef external_key_type value_type;
iterator_base(const unsigned char *const Ptr, offset_type NumEntries)
: Ptr(Ptr), NumItemsInBucketLeft(0), NumEntriesLeft(NumEntries) {}
iterator_base()
: Ptr(nullptr), NumItemsInBucketLeft(0), NumEntriesLeft(0) {}
friend bool operator==(const iterator_base &X, const iterator_base &Y) {
return X.NumEntriesLeft == Y.NumEntriesLeft;
}
friend bool operator!=(const iterator_base &X, const iterator_base &Y) {
return X.NumEntriesLeft != Y.NumEntriesLeft;
}
/// Move to the next item.
void advance() {
using namespace llvm::support;
if (!NumItemsInBucketLeft) {
// 'Items' starts with a 16-bit unsigned integer representing the
// number of items in this bucket.
NumItemsInBucketLeft =
endian::readNext<uint16_t, little, unaligned>(Ptr);
}
Ptr += sizeof(hash_value_type); // Skip the hash.
// Determine the length of the key and the data.
const std::pair<offset_type, offset_type> &L =
Info::ReadKeyDataLength(Ptr);
Ptr += L.first + L.second;
assert(NumItemsInBucketLeft);
--NumItemsInBucketLeft;
assert(NumEntriesLeft);
--NumEntriesLeft;
}
/// Get the start of the item as written by the trait (after the hash and
/// immediately before the key and value length).
const unsigned char *getItem() const {
return Ptr + (NumItemsInBucketLeft ? 0 : 2) + sizeof(hash_value_type);
}
};
public:
OnDiskIterableChainedHashTable(offset_type NumBuckets, offset_type NumEntries,
const unsigned char *Buckets,
const unsigned char *Payload,
const unsigned char *Base,
const Info &InfoObj = Info())
: base_type(NumBuckets, NumEntries, Buckets, Base, InfoObj),
Payload(Payload) {}
/// Iterates over all of the keys in the table.
class key_iterator : public iterator_base {
Info *InfoObj;
public:
typedef external_key_type value_type;
key_iterator(const unsigned char *const Ptr, offset_type NumEntries,
Info *InfoObj)
: iterator_base(Ptr, NumEntries), InfoObj(InfoObj) {}
key_iterator() : iterator_base(), InfoObj() {}
key_iterator &operator++() {
this->advance();
return *this;
}
key_iterator operator++(int) { // Postincrement
key_iterator tmp = *this;
++*this;
return tmp;
}
internal_key_type getInternalKey() const {
auto *LocalPtr = this->getItem();
// Determine the length of the key and the data.
auto L = Info::ReadKeyDataLength(LocalPtr);
// Read the key.
return InfoObj->ReadKey(LocalPtr, L.first);
}
value_type operator*() const {
return InfoObj->GetExternalKey(getInternalKey());
}
};
key_iterator key_begin() {
return key_iterator(Payload, this->getNumEntries(), &this->getInfoObj());
}
key_iterator key_end() { return key_iterator(); }
iterator_range<key_iterator> keys() {
return make_range(key_begin(), key_end());
}
/// Iterates over all the entries in the table, returning the data.
class data_iterator : public iterator_base {
Info *InfoObj;
public:
typedef data_type value_type;
data_iterator(const unsigned char *const Ptr, offset_type NumEntries,
Info *InfoObj)
: iterator_base(Ptr, NumEntries), InfoObj(InfoObj) {}
data_iterator() : iterator_base(), InfoObj() {}
data_iterator &operator++() { // Preincrement
this->advance();
return *this;
}
data_iterator operator++(int) { // Postincrement
data_iterator tmp = *this;
++*this;
return tmp;
}
value_type operator*() const {
auto *LocalPtr = this->getItem();
// Determine the length of the key and the data.
auto L = Info::ReadKeyDataLength(LocalPtr);
// Read the key.
const internal_key_type &Key = InfoObj->ReadKey(LocalPtr, L.first);
return InfoObj->ReadData(Key, LocalPtr + L.first, L.second);
}
};
data_iterator data_begin() {
return data_iterator(Payload, this->getNumEntries(), &this->getInfoObj());
}
data_iterator data_end() { return data_iterator(); }
iterator_range<data_iterator> data() {
return make_range(data_begin(), data_end());
}
/// Create the hash table.
///
/// \param Buckets is the beginning of the hash table itself, which follows
/// the payload of entire structure. This is the value returned by
/// OnDiskHashTableGenerator::Emit.
///
/// \param Payload is the beginning of the data contained in the table. This
/// is Base plus any padding or header data that was stored, ie, the offset
/// that the stream was at when calling Emit.
///
/// \param Base is the point from which all offsets into the structure are
/// based. This is offset 0 in the stream that was used when Emitting the
/// table.
static OnDiskIterableChainedHashTable *
Create(const unsigned char *Buckets, const unsigned char *const Payload,
const unsigned char *const Base, const Info &InfoObj = Info()) {
assert(Buckets > Base);
auto NumBucketsAndEntries =
OnDiskIterableChainedHashTable<Info>::readNumBucketsAndEntries(Buckets);
return new OnDiskIterableChainedHashTable<Info>(
NumBucketsAndEntries.first, NumBucketsAndEntries.second,
Buckets, Payload, Base, InfoObj);
}
};
} // end namespace llvm
#endif