#ifndef LLVM_SUPPORT_ON_DISK_HASH_TABLE_H
#define LLVM_SUPPORT_ON_DISK_HASH_TABLE_H
#include "llvm/Support/Allocator.h"
#include "llvm/Support/AlignOf.h"
#include "llvm/Support/DataTypes.h"
#include "llvm/Support/EndianStream.h"
#include "llvm/Support/Host.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <cstdlib>
namespace llvm {
template <typename Info> class OnDiskChainedHashTableGenerator {
typedef typename Info::offset_type offset_type;
offset_type NumBuckets;
offset_type NumEntries;
llvm::BumpPtrAllocator BA;
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(0), Hash(InfoObj.ComputeHash(Key)) {}
};
class Bucket {
public:
offset_type Off;
Item *Head;
unsigned Length;
Bucket() {}
};
Bucket *Buckets;
private:
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;
}
void resize(size_t NewSize) {
Bucket *NewBuckets = (Bucket *)std::calloc(NewSize, sizeof(Bucket));
for (size_t I = 0; I < NumBuckets; ++I)
for (Item *E = Buckets[I].Head; E;) {
Item *N = E->Next;
E->Next = 0;
insert(NewBuckets, NewSize, E);
E = N;
}
free(Buckets);
NumBuckets = NewSize;
Buckets = NewBuckets;
}
public:
void insert(typename Info::key_type_ref Key,
typename Info::data_type_ref Data) {
Info InfoObj;
insert(Key, Data, InfoObj);
}
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>()) Item(Key, Data, InfoObj));
}
offset_type Emit(raw_ostream &Out) {
Info InfoObj;
return Emit(Out, InfoObj);
}
offset_type Emit(raw_ostream &Out, Info &InfoObj) {
using namespace llvm::support;
endian::Writer<little> LE(Out);
for (offset_type I = 0; I < NumBuckets; ++I) {
Bucket &B = Buckets[I];
if (!B.Head)
continue;
B.Off = Out.tell();
assert(B.Off && "Cannot write a bucket at offset 0. Please add padding.");
LE.write<uint16_t>(B.Length);
assert(B.Length != 0 && "Bucket has a head but zero length?");
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);
InfoObj.EmitKey(Out, I->Key, Len.first);
InfoObj.EmitData(Out, I->Key, I->Data, Len.second);
}
}
offset_type TableOff = Out.tell();
uint64_t N = llvm::OffsetToAlignment(TableOff, alignOf<offset_type>());
TableOff += N;
while (N--)
LE.write<uint8_t>(0);
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;
Buckets = (Bucket *)std::calloc(NumBuckets, sizeof(Bucket));
}
~OnDiskChainedHashTableGenerator() { std::free(Buckets); }
};
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 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");
}
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() : Data(0), Len(0) {}
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); }
bool operator==(const iterator &X) const { return X.Data == Data; }
bool operator!=(const iterator &X) const { return X.Data != Data; }
};
iterator find(const external_key_type &EKey, Info *InfoPtr = 0) {
if (!InfoPtr)
InfoPtr = &InfoObj;
using namespace llvm::support;
const internal_key_type &IKey = InfoObj.GetInternalKey(EKey);
hash_value_type KeyHash = InfoObj.ComputeHash(IKey);
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(); const unsigned char *Items = Base + Offset;
unsigned Len = endian::readNext<uint16_t, little, unaligned>(Items);
for (unsigned i = 0; i < Len; ++i) {
hash_value_type ItemHash =
endian::readNext<hash_value_type, little, unaligned>(Items);
const std::pair<offset_type, offset_type> &L =
Info::ReadKeyDataLength(Items);
offset_type ItemLen = L.first + L.second;
if (ItemHash != KeyHash) {
Items += ItemLen;
continue;
}
const internal_key_type &X =
InfoPtr->ReadKey((const unsigned char *const)Items, L.first);
if (!InfoPtr->EqualKey(X, IKey)) {
Items += ItemLen;
continue;
}
return iterator(X, Items + L.first, L.second, InfoPtr);
}
return iterator();
}
iterator end() const { return iterator(); }
Info &getInfoObj() { return InfoObj; }
static OnDiskChainedHashTable *Create(const unsigned char *Buckets,
const unsigned char *const Base,
const Info &InfoObj = Info()) {
using namespace llvm::support;
assert(Buckets > Base);
assert((reinterpret_cast<uintptr_t>(Buckets) & 0x3) == 0 &&
"buckets should be 4-byte aligned.");
offset_type NumBuckets =
endian::readNext<offset_type, little, aligned>(Buckets);
offset_type NumEntries =
endian::readNext<offset_type, little, aligned>(Buckets);
return new OnDiskChainedHashTable<Info>(NumBuckets, NumEntries, Buckets,
Base, InfoObj);
}
};
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;
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) {}
class key_iterator {
const unsigned char *Ptr;
offset_type NumItemsInBucketLeft;
offset_type NumEntriesLeft;
Info *InfoObj;
public:
typedef external_key_type value_type;
key_iterator(const unsigned char *const Ptr, offset_type NumEntries,
Info *InfoObj)
: Ptr(Ptr), NumItemsInBucketLeft(0), NumEntriesLeft(NumEntries),
InfoObj(InfoObj) {}
key_iterator()
: Ptr(0), NumItemsInBucketLeft(0), NumEntriesLeft(0), InfoObj(0) {}
friend bool operator==(const key_iterator &X, const key_iterator &Y) {
return X.NumEntriesLeft == Y.NumEntriesLeft;
}
friend bool operator!=(const key_iterator &X, const key_iterator &Y) {
return X.NumEntriesLeft != Y.NumEntriesLeft;
}
key_iterator &operator++() { using namespace llvm::support;
if (!NumItemsInBucketLeft) {
NumItemsInBucketLeft =
endian::readNext<uint16_t, little, unaligned>(Ptr);
}
Ptr += sizeof(hash_value_type); const std::pair<offset_type, offset_type> &L =
Info::ReadKeyDataLength(Ptr);
Ptr += L.first + L.second;
assert(NumItemsInBucketLeft);
--NumItemsInBucketLeft;
assert(NumEntriesLeft);
--NumEntriesLeft;
return *this;
}
key_iterator operator++(int) { key_iterator tmp = *this; ++*this; return tmp;
}
value_type operator*() const {
const unsigned char *LocalPtr = Ptr;
if (!NumItemsInBucketLeft)
LocalPtr += 2; LocalPtr += sizeof(hash_value_type);
const std::pair<offset_type, offset_type> &L =
Info::ReadKeyDataLength(LocalPtr);
const internal_key_type &Key = InfoObj->ReadKey(LocalPtr, L.first);
return InfoObj->GetExternalKey(Key);
}
};
key_iterator key_begin() {
return key_iterator(Payload, this->getNumEntries(), &this->getInfoObj());
}
key_iterator key_end() { return key_iterator(); }
class data_iterator {
const unsigned char *Ptr;
offset_type NumItemsInBucketLeft;
offset_type NumEntriesLeft;
Info *InfoObj;
public:
typedef data_type value_type;
data_iterator(const unsigned char *const Ptr, offset_type NumEntries,
Info *InfoObj)
: Ptr(Ptr), NumItemsInBucketLeft(0), NumEntriesLeft(NumEntries),
InfoObj(InfoObj) {}
data_iterator()
: Ptr(0), NumItemsInBucketLeft(0), NumEntriesLeft(0), InfoObj(0) {}
bool operator==(const data_iterator &X) const {
return X.NumEntriesLeft == NumEntriesLeft;
}
bool operator!=(const data_iterator &X) const {
return X.NumEntriesLeft != NumEntriesLeft;
}
data_iterator &operator++() { using namespace llvm::support;
if (!NumItemsInBucketLeft) {
NumItemsInBucketLeft =
endian::readNext<uint16_t, little, unaligned>(Ptr);
}
Ptr += sizeof(hash_value_type); const std::pair<offset_type, offset_type> &L =
Info::ReadKeyDataLength(Ptr);
Ptr += L.first + L.second;
assert(NumItemsInBucketLeft);
--NumItemsInBucketLeft;
assert(NumEntriesLeft);
--NumEntriesLeft;
return *this;
}
data_iterator operator++(int) { data_iterator tmp = *this; ++*this; return tmp;
}
value_type operator*() const {
const unsigned char *LocalPtr = Ptr;
if (!NumItemsInBucketLeft)
LocalPtr += 2; LocalPtr += sizeof(hash_value_type);
const std::pair<offset_type, offset_type> &L =
Info::ReadKeyDataLength(LocalPtr);
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(); }
static OnDiskIterableChainedHashTable *
Create(const unsigned char *Buckets, const unsigned char *const Payload,
const unsigned char *const Base, const Info &InfoObj = Info()) {
using namespace llvm::support;
assert(Buckets > Base);
assert((reinterpret_cast<uintptr_t>(Buckets) & 0x3) == 0 &&
"buckets should be 4-byte aligned.");
offset_type NumBuckets =
endian::readNext<offset_type, little, aligned>(Buckets);
offset_type NumEntries =
endian::readNext<offset_type, little, aligned>(Buckets);
return new OnDiskIterableChainedHashTable<Info>(
NumBuckets, NumEntries, Buckets, Payload, Base, InfoObj);
}
};
}
#endif // LLVM_SUPPORT_ON_DISK_HASH_TABLE_H