/// \brief Defines facilities for reading and writing on-disk hash tables.
///
//===----------------------------------------------------------------------===//
-#ifndef LLVM_SUPPORT_ON_DISK_HASH_TABLE_H
-#define LLVM_SUPPORT_ON_DISK_HASH_TABLE_H
+#ifndef LLVM_SUPPORT_ONDISKHASHTABLE_H
+#define LLVM_SUPPORT_ONDISKHASHTABLE_H
-#include "llvm/Support/Allocator.h"
#include "llvm/Support/AlignOf.h"
+#include "llvm/Support/Allocator.h"
#include "llvm/Support/DataTypes.h"
#include "llvm/Support/EndianStream.h"
#include "llvm/Support/Host.h"
/// 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<unsigned, unsigned>
+/// 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, unsigned KeyLen);
+/// 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, unsigned DataLen);
+/// data_type_ref Data, offset_type DataLen);
/// };
/// \endcode
template <typename Info> class OnDiskChainedHashTableGenerator {
- unsigned NumBuckets;
- unsigned NumEntries;
- llvm::BumpPtrAllocator BA;
-
/// \brief A single item in the hash table.
class Item {
public:
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)) {}
+ : 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;
+
/// \brief A linked list of values in a particular hash bucket.
- class Bucket {
- public:
- uint32_t Off;
- Item *Head;
+ struct Bucket {
+ offset_type Off;
unsigned Length;
-
- Bucket() {}
+ Item *Head;
};
Bucket *Buckets;
void resize(size_t NewSize) {
Bucket *NewBuckets = (Bucket *)std::calloc(NewSize, sizeof(Bucket));
// Populate NewBuckets with the old entries.
- for (unsigned I = 0; I < NumBuckets; ++I)
+ for (size_t I = 0; I < NumBuckets; ++I)
for (Item *E = Buckets[I].Head; E;) {
Item *N = E->Next;
- E->Next = 0;
+ E->Next = nullptr;
insert(NewBuckets, NewSize, E);
E = N;
}
++NumEntries;
if (4 * NumEntries >= 3 * NumBuckets)
resize(NumBuckets * 2);
- insert(Buckets, NumBuckets,
- new (BA.Allocate<Item>()) Item(Key, Data, InfoObj));
+ insert(Buckets, NumBuckets, new (BA.Allocate()) Item(Key, Data, InfoObj));
}
/// \brief Emit the table to Out, which must not be at offset 0.
- uint32_t Emit(raw_ostream &Out) {
+ offset_type Emit(raw_ostream &Out) {
Info InfoObj;
return Emit(Out, InfoObj);
}
/// \brief Emit the table to Out, which must not be at offset 0.
///
/// Uses the provided Info instead of a stack allocated one.
- uint32_t Emit(raw_ostream &Out, Info &InfoObj) {
+ offset_type Emit(raw_ostream &Out, Info &InfoObj) {
using namespace llvm::support;
endian::Writer<little> LE(Out);
// Emit the payload of the table.
- for (unsigned I = 0; I < NumBuckets; ++I) {
+ for (offset_type I = 0; I < NumBuckets; ++I) {
Bucket &B = Buckets[I];
if (!B.Head)
continue;
// 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<unsigned, unsigned> &Len =
+ 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);
}
// Pad with zeros so that we can start the hashtable at an aligned address.
- uint32_t TableOff = Out.tell();
- uint64_t N = llvm::OffsetToAlignment(TableOff, alignOf<uint32_t>());
+ offset_type TableOff = Out.tell();
+ uint64_t N = llvm::OffsetToAlignment(TableOff, alignOf<offset_type>());
TableOff += N;
while (N--)
LE.write<uint8_t>(0);
// Emit the hashtable itself.
- LE.write<uint32_t>(NumBuckets);
- LE.write<uint32_t>(NumEntries);
- for (unsigned I = 0; I < NumBuckets; ++I)
- LE.write<uint32_t>(Buckets[I].Off);
+ 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;
}
/// 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);
/// 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<unsigned, unsigned>
+/// 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,
-/// unsigned KeyLen);
+/// 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,
-/// unsigned DataLen);
+/// offset_type DataLen);
/// };
/// \endcode
template <typename Info> class OnDiskChainedHashTable {
- const unsigned NumBuckets;
- const unsigned NumEntries;
+ const typename Info::offset_type NumBuckets;
+ const typename Info::offset_type NumEntries;
const unsigned char *const Buckets;
const unsigned char *const Base;
Info InfoObj;
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(unsigned NumBuckets, unsigned NumEntries,
+ OnDiskChainedHashTable(offset_type NumBuckets, offset_type NumEntries,
const unsigned char *Buckets,
const unsigned char *Base,
const Info &InfoObj = Info())
"'buckets' must have a 4-byte alignment");
}
- unsigned getNumBuckets() const { return NumBuckets; }
- unsigned getNumEntries() const { return NumEntries; }
+ /// 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; }
class iterator {
internal_key_type Key;
const unsigned char *const Data;
- const unsigned Len;
+ const offset_type Len;
Info *InfoObj;
public:
- iterator() : Data(0), Len(0) {}
- iterator(const internal_key_type K, const unsigned char *D, unsigned L,
+ iterator() : Data(nullptr), 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) {}
};
/// \brief Look up the stored data for a particular key.
- iterator find(const external_key_type &EKey, Info *InfoPtr = 0) {
- if (!InfoPtr)
- InfoPtr = &InfoObj;
-
- using namespace llvm::support;
+ 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);
+ }
+
+ /// \brief 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;
- // Each bucket is just a 32-bit offset into the hash table file.
- unsigned Idx = KeyHash & (NumBuckets - 1);
- const unsigned char *Bucket = Buckets + sizeof(uint32_t) * Idx;
+ if (!InfoPtr)
+ InfoPtr = &InfoObj;
- unsigned Offset = endian::readNext<uint32_t, little, aligned>(Bucket);
+ // 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;
endian::readNext<hash_value_type, little, unaligned>(Items);
// Determine the length of the key and the data.
- const std::pair<unsigned, unsigned> &L = Info::ReadKeyDataLength(Items);
- unsigned ItemLen = L.first + L.second;
+ 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) {
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.");
-
- unsigned NumBuckets = endian::readNext<uint32_t, little, aligned>(Buckets);
- unsigned NumEntries = endian::readNext<uint32_t, little, aligned>(Buckets);
- return new OnDiskChainedHashTable<Info>(NumBuckets, NumEntries, Buckets,
- Base, InfoObj);
+ auto NumBucketsAndEntries = readNumBucketsAndEntries(Buckets);
+ return new OnDiskChainedHashTable<Info>(NumBucketsAndEntries.first,
+ NumBucketsAndEntries.second,
+ Buckets, Base, InfoObj);
}
};
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(unsigned NumBuckets, unsigned 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) {}
-
+private:
/// \brief Iterates over all of the keys in the table.
- class key_iterator {
+ class iterator_base {
const unsigned char *Ptr;
- unsigned NumItemsInBucketLeft;
- unsigned NumEntriesLeft;
- Info *InfoObj;
+ offset_type NumItemsInBucketLeft;
+ offset_type NumEntriesLeft;
public:
typedef external_key_type value_type;
- key_iterator(const unsigned char *const Ptr, unsigned NumEntries,
- Info *InfoObj)
- : Ptr(Ptr), NumItemsInBucketLeft(0), NumEntriesLeft(NumEntries),
- InfoObj(InfoObj) {}
- key_iterator()
- : Ptr(0), NumItemsInBucketLeft(0), NumEntriesLeft(0), InfoObj(0) {}
+ 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 key_iterator &X, const key_iterator &Y) {
+ friend bool operator==(const iterator_base &X, const iterator_base &Y) {
return X.NumEntriesLeft == Y.NumEntriesLeft;
}
- friend bool operator!=(const key_iterator &X, const key_iterator &Y) {
+ friend bool operator!=(const iterator_base &X, const iterator_base &Y) {
return X.NumEntriesLeft != Y.NumEntriesLeft;
}
- key_iterator &operator++() { // Preincrement
+ /// Move to the next item.
+ void advance() {
using namespace llvm::support;
if (!NumItemsInBucketLeft) {
// 'Items' starts with a 16-bit unsigned integer representing the
}
Ptr += sizeof(hash_value_type); // Skip the hash.
// Determine the length of the key and the data.
- const std::pair<unsigned, unsigned> &L = Info::ReadKeyDataLength(Ptr);
+ 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) {}
+
+ /// \brief 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;
+ key_iterator tmp = *this;
+ ++*this;
+ return tmp;
}
- value_type operator*() const {
- const unsigned char *LocalPtr = Ptr;
- if (!NumItemsInBucketLeft)
- LocalPtr += 2; // number of items in bucket
- LocalPtr += sizeof(hash_value_type); // Skip the hash.
+ internal_key_type getInternalKey() const {
+ auto *LocalPtr = this->getItem();
// Determine the length of the key and the data.
- const std::pair<unsigned, unsigned> &L =
- Info::ReadKeyDataLength(LocalPtr);
+ auto L = Info::ReadKeyDataLength(LocalPtr);
// Read the key.
- const internal_key_type &Key = InfoObj->ReadKey(LocalPtr, L.first);
- return InfoObj->GetExternalKey(Key);
+ return InfoObj->ReadKey(LocalPtr, L.first);
+ }
+
+ value_type operator*() const {
+ return InfoObj->GetExternalKey(getInternalKey());
}
};
}
/// \brief Iterates over all the entries in the table, returning the data.
- class data_iterator {
- const unsigned char *Ptr;
- unsigned NumItemsInBucketLeft;
- unsigned NumEntriesLeft;
+ class data_iterator : public iterator_base {
Info *InfoObj;
public:
typedef data_type value_type;
- data_iterator(const unsigned char *const Ptr, unsigned NumEntries,
+ 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;
- }
+ : iterator_base(Ptr, NumEntries), InfoObj(InfoObj) {}
+ data_iterator() : iterator_base(), InfoObj() {}
data_iterator &operator++() { // Preincrement
- 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<unsigned, unsigned> &L = Info::ReadKeyDataLength(Ptr);
- Ptr += L.first + L.second;
- assert(NumItemsInBucketLeft);
- --NumItemsInBucketLeft;
- assert(NumEntriesLeft);
- --NumEntriesLeft;
+ this->advance();
return *this;
}
data_iterator operator++(int) { // Postincrement
- data_iterator tmp = *this; ++*this; return tmp;
+ data_iterator tmp = *this;
+ ++*this;
+ return tmp;
}
value_type operator*() const {
- const unsigned char *LocalPtr = Ptr;
- if (!NumItemsInBucketLeft)
- LocalPtr += 2; // number of items in bucket
- LocalPtr += sizeof(hash_value_type); // Skip the hash.
+ auto *LocalPtr = this->getItem();
// Determine the length of the key and the data.
- const std::pair<unsigned, unsigned> &L =
- Info::ReadKeyDataLength(LocalPtr);
+ auto L = Info::ReadKeyDataLength(LocalPtr);
// Read the key.
const internal_key_type &Key = InfoObj->ReadKey(LocalPtr, L.first);
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.");
-
- unsigned NumBuckets = endian::readNext<uint32_t, little, aligned>(Buckets);
- unsigned NumEntries = endian::readNext<uint32_t, little, aligned>(Buckets);
+ auto NumBucketsAndEntries =
+ OnDiskIterableChainedHashTable<Info>::readNumBucketsAndEntries(Buckets);
return new OnDiskIterableChainedHashTable<Info>(
- NumBuckets, NumEntries, Buckets, Payload, Base, InfoObj);
+ NumBucketsAndEntries.first, NumBucketsAndEntries.second,
+ Buckets, Payload, Base, InfoObj);
}
};
} // end namespace llvm
-#endif // LLVM_SUPPORT_ON_DISK_HASH_TABLE_H
+#endif
projects / oota-llvm.git / blobdiff