19378ba44b3f46d697653003c784be87746e138d2Douglas Gregor//===--- OnDiskHashTable.h - On-Disk Hash Table Implementation --*- C++ -*-===// 29378ba44b3f46d697653003c784be87746e138d2Douglas Gregor// 39378ba44b3f46d697653003c784be87746e138d2Douglas Gregor// The LLVM Compiler Infrastructure 49378ba44b3f46d697653003c784be87746e138d2Douglas Gregor// 59378ba44b3f46d697653003c784be87746e138d2Douglas Gregor// This file is distributed under the University of Illinois Open Source 69378ba44b3f46d697653003c784be87746e138d2Douglas Gregor// License. See LICENSE.TXT for details. 79378ba44b3f46d697653003c784be87746e138d2Douglas Gregor// 89378ba44b3f46d697653003c784be87746e138d2Douglas Gregor//===----------------------------------------------------------------------===// 99378ba44b3f46d697653003c784be87746e138d2Douglas Gregor// 109378ba44b3f46d697653003c784be87746e138d2Douglas Gregor// This file defines facilities for reading and writing on-disk hash 119378ba44b3f46d697653003c784be87746e138d2Douglas Gregor// tables. 129378ba44b3f46d697653003c784be87746e138d2Douglas Gregor// 139378ba44b3f46d697653003c784be87746e138d2Douglas Gregor//===----------------------------------------------------------------------===// 149378ba44b3f46d697653003c784be87746e138d2Douglas Gregor#ifndef LLVM_CLANG_BASIC_ON_DISK_HASH_TABLE_H 159378ba44b3f46d697653003c784be87746e138d2Douglas Gregor#define LLVM_CLANG_BASIC_ON_DISK_HASH_TABLE_H 169378ba44b3f46d697653003c784be87746e138d2Douglas Gregor 179378ba44b3f46d697653003c784be87746e138d2Douglas Gregor#include "llvm/Support/Allocator.h" 1803013fa9a0bf1ef4b907f5fec006c8f4000fdd21Michael J. Spencer#include "llvm/Support/DataTypes.h" 199378ba44b3f46d697653003c784be87746e138d2Douglas Gregor#include "llvm/Support/MathExtras.h" 209378ba44b3f46d697653003c784be87746e138d2Douglas Gregor#include "llvm/Support/raw_ostream.h" 2103013fa9a0bf1ef4b907f5fec006c8f4000fdd21Michael J. Spencer#include "llvm/Support/Host.h" 229378ba44b3f46d697653003c784be87746e138d2Douglas Gregor#include <cassert> 239378ba44b3f46d697653003c784be87746e138d2Douglas Gregor#include <cstdlib> 249378ba44b3f46d697653003c784be87746e138d2Douglas Gregor 259378ba44b3f46d697653003c784be87746e138d2Douglas Gregornamespace clang { 269378ba44b3f46d697653003c784be87746e138d2Douglas Gregor 279378ba44b3f46d697653003c784be87746e138d2Douglas Gregornamespace io { 289378ba44b3f46d697653003c784be87746e138d2Douglas Gregor 299378ba44b3f46d697653003c784be87746e138d2Douglas Gregortypedef uint32_t Offset; 309378ba44b3f46d697653003c784be87746e138d2Douglas Gregor 318cc488fefb2fb04bc8d5398da29f0182f97934cfChris Lattnerinline void Emit8(raw_ostream& Out, uint32_t V) { 329378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Out << (unsigned char)(V); 339378ba44b3f46d697653003c784be87746e138d2Douglas Gregor} 349378ba44b3f46d697653003c784be87746e138d2Douglas Gregor 358cc488fefb2fb04bc8d5398da29f0182f97934cfChris Lattnerinline void Emit16(raw_ostream& Out, uint32_t V) { 369378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Out << (unsigned char)(V); 379378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Out << (unsigned char)(V >> 8); 389378ba44b3f46d697653003c784be87746e138d2Douglas Gregor assert((V >> 16) == 0); 399378ba44b3f46d697653003c784be87746e138d2Douglas Gregor} 409378ba44b3f46d697653003c784be87746e138d2Douglas Gregor 418cc488fefb2fb04bc8d5398da29f0182f97934cfChris Lattnerinline void Emit24(raw_ostream& Out, uint32_t V) { 42be08ac7afbb2aca5f6718687787658a928599b21Kovarththanan Rajaratnam Out << (unsigned char)(V); 43be08ac7afbb2aca5f6718687787658a928599b21Kovarththanan Rajaratnam Out << (unsigned char)(V >> 8); 44be08ac7afbb2aca5f6718687787658a928599b21Kovarththanan Rajaratnam Out << (unsigned char)(V >> 16); 45be08ac7afbb2aca5f6718687787658a928599b21Kovarththanan Rajaratnam assert((V >> 24) == 0); 46be08ac7afbb2aca5f6718687787658a928599b21Kovarththanan Rajaratnam} 47be08ac7afbb2aca5f6718687787658a928599b21Kovarththanan Rajaratnam 488cc488fefb2fb04bc8d5398da29f0182f97934cfChris Lattnerinline void Emit32(raw_ostream& Out, uint32_t V) { 499378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Out << (unsigned char)(V); 509378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Out << (unsigned char)(V >> 8); 519378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Out << (unsigned char)(V >> 16); 529378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Out << (unsigned char)(V >> 24); 539378ba44b3f46d697653003c784be87746e138d2Douglas Gregor} 549378ba44b3f46d697653003c784be87746e138d2Douglas Gregor 558cc488fefb2fb04bc8d5398da29f0182f97934cfChris Lattnerinline void Emit64(raw_ostream& Out, uint64_t V) { 569378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Out << (unsigned char)(V); 579378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Out << (unsigned char)(V >> 8); 589378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Out << (unsigned char)(V >> 16); 599378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Out << (unsigned char)(V >> 24); 609378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Out << (unsigned char)(V >> 32); 619378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Out << (unsigned char)(V >> 40); 629378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Out << (unsigned char)(V >> 48); 639378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Out << (unsigned char)(V >> 56); 649378ba44b3f46d697653003c784be87746e138d2Douglas Gregor} 659378ba44b3f46d697653003c784be87746e138d2Douglas Gregor 668cc488fefb2fb04bc8d5398da29f0182f97934cfChris Lattnerinline void Pad(raw_ostream& Out, unsigned A) { 679378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Offset off = (Offset) Out.tell(); 689378ba44b3f46d697653003c784be87746e138d2Douglas Gregor uint32_t n = ((uintptr_t)(off+A-1) & ~(uintptr_t)(A-1)) - off; 699378ba44b3f46d697653003c784be87746e138d2Douglas Gregor for (; n ; --n) 709378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Emit8(Out, 0); 719378ba44b3f46d697653003c784be87746e138d2Douglas Gregor} 729378ba44b3f46d697653003c784be87746e138d2Douglas Gregor 739378ba44b3f46d697653003c784be87746e138d2Douglas Gregorinline uint16_t ReadUnalignedLE16(const unsigned char *&Data) { 749378ba44b3f46d697653003c784be87746e138d2Douglas Gregor uint16_t V = ((uint16_t)Data[0]) | 759378ba44b3f46d697653003c784be87746e138d2Douglas Gregor ((uint16_t)Data[1] << 8); 769378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Data += 2; 779378ba44b3f46d697653003c784be87746e138d2Douglas Gregor return V; 789378ba44b3f46d697653003c784be87746e138d2Douglas Gregor} 799378ba44b3f46d697653003c784be87746e138d2Douglas Gregor 809378ba44b3f46d697653003c784be87746e138d2Douglas Gregorinline uint32_t ReadUnalignedLE32(const unsigned char *&Data) { 819378ba44b3f46d697653003c784be87746e138d2Douglas Gregor uint32_t V = ((uint32_t)Data[0]) | 829378ba44b3f46d697653003c784be87746e138d2Douglas Gregor ((uint32_t)Data[1] << 8) | 839378ba44b3f46d697653003c784be87746e138d2Douglas Gregor ((uint32_t)Data[2] << 16) | 849378ba44b3f46d697653003c784be87746e138d2Douglas Gregor ((uint32_t)Data[3] << 24); 859378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Data += 4; 869378ba44b3f46d697653003c784be87746e138d2Douglas Gregor return V; 879378ba44b3f46d697653003c784be87746e138d2Douglas Gregor} 889378ba44b3f46d697653003c784be87746e138d2Douglas Gregor 899378ba44b3f46d697653003c784be87746e138d2Douglas Gregorinline uint64_t ReadUnalignedLE64(const unsigned char *&Data) { 909378ba44b3f46d697653003c784be87746e138d2Douglas Gregor uint64_t V = ((uint64_t)Data[0]) | 919378ba44b3f46d697653003c784be87746e138d2Douglas Gregor ((uint64_t)Data[1] << 8) | 929378ba44b3f46d697653003c784be87746e138d2Douglas Gregor ((uint64_t)Data[2] << 16) | 939378ba44b3f46d697653003c784be87746e138d2Douglas Gregor ((uint64_t)Data[3] << 24) | 949378ba44b3f46d697653003c784be87746e138d2Douglas Gregor ((uint64_t)Data[4] << 32) | 959378ba44b3f46d697653003c784be87746e138d2Douglas Gregor ((uint64_t)Data[5] << 40) | 969378ba44b3f46d697653003c784be87746e138d2Douglas Gregor ((uint64_t)Data[6] << 48) | 979378ba44b3f46d697653003c784be87746e138d2Douglas Gregor ((uint64_t)Data[7] << 56); 989378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Data += 8; 999378ba44b3f46d697653003c784be87746e138d2Douglas Gregor return V; 1009378ba44b3f46d697653003c784be87746e138d2Douglas Gregor} 1019378ba44b3f46d697653003c784be87746e138d2Douglas Gregor 1029378ba44b3f46d697653003c784be87746e138d2Douglas Gregorinline uint32_t ReadLE32(const unsigned char *&Data) { 1039378ba44b3f46d697653003c784be87746e138d2Douglas Gregor // Hosts that directly support little-endian 32-bit loads can just 1049378ba44b3f46d697653003c784be87746e138d2Douglas Gregor // use them. Big-endian hosts need a bswap. 1059378ba44b3f46d697653003c784be87746e138d2Douglas Gregor uint32_t V = *((uint32_t*)Data); 1069378ba44b3f46d697653003c784be87746e138d2Douglas Gregor if (llvm::sys::isBigEndianHost()) 1079378ba44b3f46d697653003c784be87746e138d2Douglas Gregor V = llvm::ByteSwap_32(V); 1089378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Data += 4; 1099378ba44b3f46d697653003c784be87746e138d2Douglas Gregor return V; 1109378ba44b3f46d697653003c784be87746e138d2Douglas Gregor} 1119378ba44b3f46d697653003c784be87746e138d2Douglas Gregor 1129378ba44b3f46d697653003c784be87746e138d2Douglas Gregor} // end namespace io 1139378ba44b3f46d697653003c784be87746e138d2Douglas Gregor 1149378ba44b3f46d697653003c784be87746e138d2Douglas Gregortemplate<typename Info> 1159378ba44b3f46d697653003c784be87746e138d2Douglas Gregorclass OnDiskChainedHashTableGenerator { 1169378ba44b3f46d697653003c784be87746e138d2Douglas Gregor unsigned NumBuckets; 1179378ba44b3f46d697653003c784be87746e138d2Douglas Gregor unsigned NumEntries; 1189378ba44b3f46d697653003c784be87746e138d2Douglas Gregor llvm::BumpPtrAllocator BA; 1191eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1209378ba44b3f46d697653003c784be87746e138d2Douglas Gregor class Item { 1219378ba44b3f46d697653003c784be87746e138d2Douglas Gregor public: 1229378ba44b3f46d697653003c784be87746e138d2Douglas Gregor typename Info::key_type key; 1239378ba44b3f46d697653003c784be87746e138d2Douglas Gregor typename Info::data_type data; 1249378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Item *next; 1259378ba44b3f46d697653003c784be87746e138d2Douglas Gregor const uint32_t hash; 1261eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1275d26768e2661faa7ce0b55ffff4be8b3969fbbf5Argyrios Kyrtzidis Item(typename Info::key_type_ref k, typename Info::data_type_ref d, 1285d26768e2661faa7ce0b55ffff4be8b3969fbbf5Argyrios Kyrtzidis Info &InfoObj) 1295d26768e2661faa7ce0b55ffff4be8b3969fbbf5Argyrios Kyrtzidis : key(k), data(d), next(0), hash(InfoObj.ComputeHash(k)) {} 1309378ba44b3f46d697653003c784be87746e138d2Douglas Gregor }; 1311eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1321eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump class Bucket { 1339378ba44b3f46d697653003c784be87746e138d2Douglas Gregor public: 1349378ba44b3f46d697653003c784be87746e138d2Douglas Gregor io::Offset off; 135b346d2f419ec7d7ce6b20780d518490338efa7deNick Lewycky Item* head; 1369378ba44b3f46d697653003c784be87746e138d2Douglas Gregor unsigned length; 1371eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1389378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Bucket() {} 1399378ba44b3f46d697653003c784be87746e138d2Douglas Gregor }; 1401eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1419378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Bucket* Buckets; 1421eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1439378ba44b3f46d697653003c784be87746e138d2Douglas Gregorprivate: 1449378ba44b3f46d697653003c784be87746e138d2Douglas Gregor void insert(Bucket* b, size_t size, Item* E) { 1459378ba44b3f46d697653003c784be87746e138d2Douglas Gregor unsigned idx = E->hash & (size - 1); 1469378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Bucket& B = b[idx]; 1479378ba44b3f46d697653003c784be87746e138d2Douglas Gregor E->next = B.head; 1489378ba44b3f46d697653003c784be87746e138d2Douglas Gregor ++B.length; 1499378ba44b3f46d697653003c784be87746e138d2Douglas Gregor B.head = E; 1509378ba44b3f46d697653003c784be87746e138d2Douglas Gregor } 1511eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1529378ba44b3f46d697653003c784be87746e138d2Douglas Gregor void resize(size_t newsize) { 1539378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Bucket* newBuckets = (Bucket*) std::calloc(newsize, sizeof(Bucket)); 1549378ba44b3f46d697653003c784be87746e138d2Douglas Gregor // Populate newBuckets with the old entries. 1559378ba44b3f46d697653003c784be87746e138d2Douglas Gregor for (unsigned i = 0; i < NumBuckets; ++i) 1569378ba44b3f46d697653003c784be87746e138d2Douglas Gregor for (Item* E = Buckets[i].head; E ; ) { 1579378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Item* N = E->next; 1589378ba44b3f46d697653003c784be87746e138d2Douglas Gregor E->next = 0; 1599378ba44b3f46d697653003c784be87746e138d2Douglas Gregor insert(newBuckets, newsize, E); 1609378ba44b3f46d697653003c784be87746e138d2Douglas Gregor E = N; 1619378ba44b3f46d697653003c784be87746e138d2Douglas Gregor } 1621eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1639378ba44b3f46d697653003c784be87746e138d2Douglas Gregor free(Buckets); 1649378ba44b3f46d697653003c784be87746e138d2Douglas Gregor NumBuckets = newsize; 1659378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Buckets = newBuckets; 1661eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 1671eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1689378ba44b3f46d697653003c784be87746e138d2Douglas Gregorpublic: 1691eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1709378ba44b3f46d697653003c784be87746e138d2Douglas Gregor void insert(typename Info::key_type_ref key, 1719378ba44b3f46d697653003c784be87746e138d2Douglas Gregor typename Info::data_type_ref data) { 1725d26768e2661faa7ce0b55ffff4be8b3969fbbf5Argyrios Kyrtzidis Info InfoObj; 1735d26768e2661faa7ce0b55ffff4be8b3969fbbf5Argyrios Kyrtzidis insert(key, data, InfoObj); 1745d26768e2661faa7ce0b55ffff4be8b3969fbbf5Argyrios Kyrtzidis } 1755d26768e2661faa7ce0b55ffff4be8b3969fbbf5Argyrios Kyrtzidis 1765d26768e2661faa7ce0b55ffff4be8b3969fbbf5Argyrios Kyrtzidis void insert(typename Info::key_type_ref key, 1775d26768e2661faa7ce0b55ffff4be8b3969fbbf5Argyrios Kyrtzidis typename Info::data_type_ref data, Info &InfoObj) { 1789378ba44b3f46d697653003c784be87746e138d2Douglas Gregor 1799378ba44b3f46d697653003c784be87746e138d2Douglas Gregor ++NumEntries; 1809378ba44b3f46d697653003c784be87746e138d2Douglas Gregor if (4*NumEntries >= 3*NumBuckets) resize(NumBuckets*2); 1815d26768e2661faa7ce0b55ffff4be8b3969fbbf5Argyrios Kyrtzidis insert(Buckets, NumBuckets, new (BA.Allocate<Item>()) Item(key, data, 1825d26768e2661faa7ce0b55ffff4be8b3969fbbf5Argyrios Kyrtzidis InfoObj)); 1839378ba44b3f46d697653003c784be87746e138d2Douglas Gregor } 1841eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1858cc488fefb2fb04bc8d5398da29f0182f97934cfChris Lattner io::Offset Emit(raw_ostream &out) { 18624022803af76734534d7b506137142d8df5b457dDouglas Gregor Info InfoObj; 18724022803af76734534d7b506137142d8df5b457dDouglas Gregor return Emit(out, InfoObj); 18824022803af76734534d7b506137142d8df5b457dDouglas Gregor } 18924022803af76734534d7b506137142d8df5b457dDouglas Gregor 1908cc488fefb2fb04bc8d5398da29f0182f97934cfChris Lattner io::Offset Emit(raw_ostream &out, Info &InfoObj) { 1919378ba44b3f46d697653003c784be87746e138d2Douglas Gregor using namespace clang::io; 1929378ba44b3f46d697653003c784be87746e138d2Douglas Gregor 1939378ba44b3f46d697653003c784be87746e138d2Douglas Gregor // Emit the payload of the table. 1949378ba44b3f46d697653003c784be87746e138d2Douglas Gregor for (unsigned i = 0; i < NumBuckets; ++i) { 1959378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Bucket& B = Buckets[i]; 1969378ba44b3f46d697653003c784be87746e138d2Douglas Gregor if (!B.head) continue; 1971eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1989378ba44b3f46d697653003c784be87746e138d2Douglas Gregor // Store the offset for the data of this bucket. 1999378ba44b3f46d697653003c784be87746e138d2Douglas Gregor B.off = out.tell(); 200f0aaf7a59729a4ae0146e3464ee987745be95829Douglas Gregor assert(B.off && "Cannot write a bucket at offset 0. Please add padding."); 201f0aaf7a59729a4ae0146e3464ee987745be95829Douglas Gregor 2029378ba44b3f46d697653003c784be87746e138d2Douglas Gregor // Write out the number of items in the bucket. 2039378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Emit16(out, B.length); 204b346d2f419ec7d7ce6b20780d518490338efa7deNick Lewycky assert(B.length != 0 && "Bucket has a head but zero length?"); 2051eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2069378ba44b3f46d697653003c784be87746e138d2Douglas Gregor // Write out the entries in the bucket. 2079378ba44b3f46d697653003c784be87746e138d2Douglas Gregor for (Item *I = B.head; I ; I = I->next) { 2089378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Emit32(out, I->hash); 2091eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump const std::pair<unsigned, unsigned>& Len = 21024022803af76734534d7b506137142d8df5b457dDouglas Gregor InfoObj.EmitKeyDataLength(out, I->key, I->data); 21124022803af76734534d7b506137142d8df5b457dDouglas Gregor InfoObj.EmitKey(out, I->key, Len.first); 21224022803af76734534d7b506137142d8df5b457dDouglas Gregor InfoObj.EmitData(out, I->key, I->data, Len.second); 2139378ba44b3f46d697653003c784be87746e138d2Douglas Gregor } 2149378ba44b3f46d697653003c784be87746e138d2Douglas Gregor } 2151eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2169378ba44b3f46d697653003c784be87746e138d2Douglas Gregor // Emit the hashtable itself. 2179378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Pad(out, 4); 2189378ba44b3f46d697653003c784be87746e138d2Douglas Gregor io::Offset TableOff = out.tell(); 2199378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Emit32(out, NumBuckets); 2209378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Emit32(out, NumEntries); 2219378ba44b3f46d697653003c784be87746e138d2Douglas Gregor for (unsigned i = 0; i < NumBuckets; ++i) Emit32(out, Buckets[i].off); 2221eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2239378ba44b3f46d697653003c784be87746e138d2Douglas Gregor return TableOff; 2249378ba44b3f46d697653003c784be87746e138d2Douglas Gregor } 2251eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2269378ba44b3f46d697653003c784be87746e138d2Douglas Gregor OnDiskChainedHashTableGenerator() { 2279378ba44b3f46d697653003c784be87746e138d2Douglas Gregor NumEntries = 0; 2281eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump NumBuckets = 64; 2299378ba44b3f46d697653003c784be87746e138d2Douglas Gregor // Note that we do not need to run the constructors of the individual 2309378ba44b3f46d697653003c784be87746e138d2Douglas Gregor // Bucket objects since 'calloc' returns bytes that are all 0. 2319378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Buckets = (Bucket*) std::calloc(NumBuckets, sizeof(Bucket)); 2329378ba44b3f46d697653003c784be87746e138d2Douglas Gregor } 2331eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2349378ba44b3f46d697653003c784be87746e138d2Douglas Gregor ~OnDiskChainedHashTableGenerator() { 2359378ba44b3f46d697653003c784be87746e138d2Douglas Gregor std::free(Buckets); 2369378ba44b3f46d697653003c784be87746e138d2Douglas Gregor } 2379378ba44b3f46d697653003c784be87746e138d2Douglas Gregor}; 2389378ba44b3f46d697653003c784be87746e138d2Douglas Gregor 2399378ba44b3f46d697653003c784be87746e138d2Douglas Gregortemplate<typename Info> 2409378ba44b3f46d697653003c784be87746e138d2Douglas Gregorclass OnDiskChainedHashTable { 2419378ba44b3f46d697653003c784be87746e138d2Douglas Gregor const unsigned NumBuckets; 2429378ba44b3f46d697653003c784be87746e138d2Douglas Gregor const unsigned NumEntries; 2439378ba44b3f46d697653003c784be87746e138d2Douglas Gregor const unsigned char* const Buckets; 2449378ba44b3f46d697653003c784be87746e138d2Douglas Gregor const unsigned char* const Base; 245668c1a4fdcc56bdd050256b1688e116fe84b72dbDouglas Gregor Info InfoObj; 246668c1a4fdcc56bdd050256b1688e116fe84b72dbDouglas Gregor 2479378ba44b3f46d697653003c784be87746e138d2Douglas Gregorpublic: 2489378ba44b3f46d697653003c784be87746e138d2Douglas Gregor typedef typename Info::internal_key_type internal_key_type; 2499378ba44b3f46d697653003c784be87746e138d2Douglas Gregor typedef typename Info::external_key_type external_key_type; 2509378ba44b3f46d697653003c784be87746e138d2Douglas Gregor typedef typename Info::data_type data_type; 2511eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2529378ba44b3f46d697653003c784be87746e138d2Douglas Gregor OnDiskChainedHashTable(unsigned numBuckets, unsigned numEntries, 2539378ba44b3f46d697653003c784be87746e138d2Douglas Gregor const unsigned char* buckets, 254668c1a4fdcc56bdd050256b1688e116fe84b72dbDouglas Gregor const unsigned char* base, 255668c1a4fdcc56bdd050256b1688e116fe84b72dbDouglas Gregor const Info &InfoObj = Info()) 2569378ba44b3f46d697653003c784be87746e138d2Douglas Gregor : NumBuckets(numBuckets), NumEntries(numEntries), 257668c1a4fdcc56bdd050256b1688e116fe84b72dbDouglas Gregor Buckets(buckets), Base(base), InfoObj(InfoObj) { 2589378ba44b3f46d697653003c784be87746e138d2Douglas Gregor assert((reinterpret_cast<uintptr_t>(buckets) & 0x3) == 0 && 2599378ba44b3f46d697653003c784be87746e138d2Douglas Gregor "'buckets' must have a 4-byte alignment"); 2609378ba44b3f46d697653003c784be87746e138d2Douglas Gregor } 2619378ba44b3f46d697653003c784be87746e138d2Douglas Gregor 2629378ba44b3f46d697653003c784be87746e138d2Douglas Gregor unsigned getNumBuckets() const { return NumBuckets; } 2639378ba44b3f46d697653003c784be87746e138d2Douglas Gregor unsigned getNumEntries() const { return NumEntries; } 2649378ba44b3f46d697653003c784be87746e138d2Douglas Gregor const unsigned char* getBase() const { return Base; } 2659378ba44b3f46d697653003c784be87746e138d2Douglas Gregor const unsigned char* getBuckets() const { return Buckets; } 2669378ba44b3f46d697653003c784be87746e138d2Douglas Gregor 2679378ba44b3f46d697653003c784be87746e138d2Douglas Gregor bool isEmpty() const { return NumEntries == 0; } 2681eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2699378ba44b3f46d697653003c784be87746e138d2Douglas Gregor class iterator { 2709378ba44b3f46d697653003c784be87746e138d2Douglas Gregor internal_key_type key; 2719378ba44b3f46d697653003c784be87746e138d2Douglas Gregor const unsigned char* const data; 2729378ba44b3f46d697653003c784be87746e138d2Douglas Gregor const unsigned len; 273668c1a4fdcc56bdd050256b1688e116fe84b72dbDouglas Gregor Info *InfoObj; 2749378ba44b3f46d697653003c784be87746e138d2Douglas Gregor public: 2759378ba44b3f46d697653003c784be87746e138d2Douglas Gregor iterator() : data(0), len(0) {} 276668c1a4fdcc56bdd050256b1688e116fe84b72dbDouglas Gregor iterator(const internal_key_type k, const unsigned char* d, unsigned l, 277668c1a4fdcc56bdd050256b1688e116fe84b72dbDouglas Gregor Info *InfoObj) 278668c1a4fdcc56bdd050256b1688e116fe84b72dbDouglas Gregor : key(k), data(d), len(l), InfoObj(InfoObj) {} 2791eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2801eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump data_type operator*() const { return InfoObj->ReadData(key, data, len); } 2811eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump bool operator==(const iterator& X) const { return X.data == data; } 2829378ba44b3f46d697653003c784be87746e138d2Douglas Gregor bool operator!=(const iterator& X) const { return X.data != data; } 2831eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump }; 2841eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 285668c1a4fdcc56bdd050256b1688e116fe84b72dbDouglas Gregor iterator find(const external_key_type& eKey, Info *InfoPtr = 0) { 286668c1a4fdcc56bdd050256b1688e116fe84b72dbDouglas Gregor if (!InfoPtr) 287668c1a4fdcc56bdd050256b1688e116fe84b72dbDouglas Gregor InfoPtr = &InfoObj; 288668c1a4fdcc56bdd050256b1688e116fe84b72dbDouglas Gregor 2899378ba44b3f46d697653003c784be87746e138d2Douglas Gregor using namespace io; 2905d26768e2661faa7ce0b55ffff4be8b3969fbbf5Argyrios Kyrtzidis const internal_key_type& iKey = InfoObj.GetInternalKey(eKey); 2915d26768e2661faa7ce0b55ffff4be8b3969fbbf5Argyrios Kyrtzidis unsigned key_hash = InfoObj.ComputeHash(iKey); 2921eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 293668c1a4fdcc56bdd050256b1688e116fe84b72dbDouglas Gregor // Each bucket is just a 32-bit offset into the hash table file. 2949378ba44b3f46d697653003c784be87746e138d2Douglas Gregor unsigned idx = key_hash & (NumBuckets - 1); 2959378ba44b3f46d697653003c784be87746e138d2Douglas Gregor const unsigned char* Bucket = Buckets + sizeof(uint32_t)*idx; 2961eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2979378ba44b3f46d697653003c784be87746e138d2Douglas Gregor unsigned offset = ReadLE32(Bucket); 2989378ba44b3f46d697653003c784be87746e138d2Douglas Gregor if (offset == 0) return iterator(); // Empty bucket. 2999378ba44b3f46d697653003c784be87746e138d2Douglas Gregor const unsigned char* Items = Base + offset; 3001eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3019378ba44b3f46d697653003c784be87746e138d2Douglas Gregor // 'Items' starts with a 16-bit unsigned integer representing the 3029378ba44b3f46d697653003c784be87746e138d2Douglas Gregor // number of items in this bucket. 3039378ba44b3f46d697653003c784be87746e138d2Douglas Gregor unsigned len = ReadUnalignedLE16(Items); 3041eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3059378ba44b3f46d697653003c784be87746e138d2Douglas Gregor for (unsigned i = 0; i < len; ++i) { 3069378ba44b3f46d697653003c784be87746e138d2Douglas Gregor // Read the hash. 3079378ba44b3f46d697653003c784be87746e138d2Douglas Gregor uint32_t item_hash = ReadUnalignedLE32(Items); 3081eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3099378ba44b3f46d697653003c784be87746e138d2Douglas Gregor // Determine the length of the key and the data. 3101eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump const std::pair<unsigned, unsigned>& L = Info::ReadKeyDataLength(Items); 3119378ba44b3f46d697653003c784be87746e138d2Douglas Gregor unsigned item_len = L.first + L.second; 3129378ba44b3f46d697653003c784be87746e138d2Douglas Gregor 3139378ba44b3f46d697653003c784be87746e138d2Douglas Gregor // Compare the hashes. If they are not the same, skip the entry entirely. 3149378ba44b3f46d697653003c784be87746e138d2Douglas Gregor if (item_hash != key_hash) { 3159378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Items += item_len; 3169378ba44b3f46d697653003c784be87746e138d2Douglas Gregor continue; 3179378ba44b3f46d697653003c784be87746e138d2Douglas Gregor } 3181eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3199378ba44b3f46d697653003c784be87746e138d2Douglas Gregor // Read the key. 3209378ba44b3f46d697653003c784be87746e138d2Douglas Gregor const internal_key_type& X = 321f0aaf7a59729a4ae0146e3464ee987745be95829Douglas Gregor InfoPtr->ReadKey((const unsigned char* const) Items, L.first); 3229378ba44b3f46d697653003c784be87746e138d2Douglas Gregor 3239378ba44b3f46d697653003c784be87746e138d2Douglas Gregor // If the key doesn't match just skip reading the value. 324cfbf1c7536e016dc275139dd842d4a5f059a749fDouglas Gregor if (!InfoPtr->EqualKey(X, iKey)) { 3259378ba44b3f46d697653003c784be87746e138d2Douglas Gregor Items += item_len; 3269378ba44b3f46d697653003c784be87746e138d2Douglas Gregor continue; 3279378ba44b3f46d697653003c784be87746e138d2Douglas Gregor } 3281eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3299378ba44b3f46d697653003c784be87746e138d2Douglas Gregor // The key matches! 330668c1a4fdcc56bdd050256b1688e116fe84b72dbDouglas Gregor return iterator(X, Items + L.first, L.second, InfoPtr); 3319378ba44b3f46d697653003c784be87746e138d2Douglas Gregor } 3321eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3339378ba44b3f46d697653003c784be87746e138d2Douglas Gregor return iterator(); 3349378ba44b3f46d697653003c784be87746e138d2Douglas Gregor } 3351eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3369378ba44b3f46d697653003c784be87746e138d2Douglas Gregor iterator end() const { return iterator(); } 3371eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 33895f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor /// \brief Iterates over all of the keys in the table. 33995f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor class key_iterator { 34095f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor const unsigned char* Ptr; 34195f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor unsigned NumItemsInBucketLeft; 34295f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor unsigned NumEntriesLeft; 34395f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor Info *InfoObj; 34495f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor public: 34595f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor typedef external_key_type value_type; 34695f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor 34795f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor key_iterator(const unsigned char* const Ptr, unsigned NumEntries, 34895f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor Info *InfoObj) 34995f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor : Ptr(Ptr), NumItemsInBucketLeft(0), NumEntriesLeft(NumEntries), 35095f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor InfoObj(InfoObj) { } 35195f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor key_iterator() 35295f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor : Ptr(0), NumItemsInBucketLeft(0), NumEntriesLeft(0), InfoObj(0) { } 35395f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor 35495f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor friend bool operator==(const key_iterator &X, const key_iterator &Y) { 35595f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor return X.NumEntriesLeft == Y.NumEntriesLeft; 35695f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor } 35795f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor friend bool operator!=(const key_iterator& X, const key_iterator &Y) { 35895f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor return X.NumEntriesLeft != Y.NumEntriesLeft; 35995f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor } 36070042f5d1ca378138f90b7b9384023701f5d03d8David Blaikie 36195f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor key_iterator& operator++() { // Preincrement 36295f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor if (!NumItemsInBucketLeft) { 36395f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor // 'Items' starts with a 16-bit unsigned integer representing the 36495f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor // number of items in this bucket. 36595f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor NumItemsInBucketLeft = io::ReadUnalignedLE16(Ptr); 36695f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor } 36795f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor Ptr += 4; // Skip the hash. 36895f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor // Determine the length of the key and the data. 36995f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor const std::pair<unsigned, unsigned>& L = Info::ReadKeyDataLength(Ptr); 37095f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor Ptr += L.first + L.second; 37195f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor assert(NumItemsInBucketLeft); 37295f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor --NumItemsInBucketLeft; 37395f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor assert(NumEntriesLeft); 37495f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor --NumEntriesLeft; 37595f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor return *this; 37695f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor } 37795f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor key_iterator operator++(int) { // Postincrement 37895f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor key_iterator tmp = *this; ++*this; return tmp; 37995f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor } 38095f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor 38195f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor value_type operator*() const { 38295f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor const unsigned char* LocalPtr = Ptr; 38395f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor if (!NumItemsInBucketLeft) 38495f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor LocalPtr += 2; // number of items in bucket 38595f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor LocalPtr += 4; // Skip the hash. 38695f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor 38795f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor // Determine the length of the key and the data. 38895f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor const std::pair<unsigned, unsigned>& L 38995f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor = Info::ReadKeyDataLength(LocalPtr); 39095f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor 39195f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor // Read the key. 39295f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor const internal_key_type& Key = InfoObj->ReadKey(LocalPtr, L.first); 39395f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor return InfoObj->GetExternalKey(Key); 39495f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor } 39595f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor }; 39695f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor 39795f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor key_iterator key_begin() { 39895f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor return key_iterator(Base + 4, getNumEntries(), &InfoObj); 39995f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor } 40095f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor key_iterator key_end() { return key_iterator(); } 40195f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor 402b346d2f419ec7d7ce6b20780d518490338efa7deNick Lewycky /// \brief Iterates over all the entries in the table, returning the data. 403b346d2f419ec7d7ce6b20780d518490338efa7deNick Lewycky class data_iterator { 404f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis const unsigned char* Ptr; 405f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis unsigned NumItemsInBucketLeft; 406f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis unsigned NumEntriesLeft; 407f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis Info *InfoObj; 408f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis public: 409b346d2f419ec7d7ce6b20780d518490338efa7deNick Lewycky typedef data_type value_type; 410f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis 411b346d2f419ec7d7ce6b20780d518490338efa7deNick Lewycky data_iterator(const unsigned char* const Ptr, unsigned NumEntries, 412f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis Info *InfoObj) 413f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis : Ptr(Ptr), NumItemsInBucketLeft(0), NumEntriesLeft(NumEntries), 414f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis InfoObj(InfoObj) { } 415b346d2f419ec7d7ce6b20780d518490338efa7deNick Lewycky data_iterator() 416f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis : Ptr(0), NumItemsInBucketLeft(0), NumEntriesLeft(0), InfoObj(0) { } 417f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis 418b346d2f419ec7d7ce6b20780d518490338efa7deNick Lewycky bool operator==(const data_iterator& X) const { 419f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis return X.NumEntriesLeft == NumEntriesLeft; 420f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis } 421b346d2f419ec7d7ce6b20780d518490338efa7deNick Lewycky bool operator!=(const data_iterator& X) const { 422f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis return X.NumEntriesLeft != NumEntriesLeft; 423f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis } 42470042f5d1ca378138f90b7b9384023701f5d03d8David Blaikie 425b346d2f419ec7d7ce6b20780d518490338efa7deNick Lewycky data_iterator& operator++() { // Preincrement 426f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis if (!NumItemsInBucketLeft) { 427f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis // 'Items' starts with a 16-bit unsigned integer representing the 428f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis // number of items in this bucket. 429f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis NumItemsInBucketLeft = io::ReadUnalignedLE16(Ptr); 430f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis } 431f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis Ptr += 4; // Skip the hash. 432f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis // Determine the length of the key and the data. 433f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis const std::pair<unsigned, unsigned>& L = Info::ReadKeyDataLength(Ptr); 434f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis Ptr += L.first + L.second; 435f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis assert(NumItemsInBucketLeft); 436f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis --NumItemsInBucketLeft; 437f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis assert(NumEntriesLeft); 438f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis --NumEntriesLeft; 439f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis return *this; 440f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis } 441b346d2f419ec7d7ce6b20780d518490338efa7deNick Lewycky data_iterator operator++(int) { // Postincrement 442b346d2f419ec7d7ce6b20780d518490338efa7deNick Lewycky data_iterator tmp = *this; ++*this; return tmp; 443f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis } 444f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis 445f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis value_type operator*() const { 446f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis const unsigned char* LocalPtr = Ptr; 447f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis if (!NumItemsInBucketLeft) 448f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis LocalPtr += 2; // number of items in bucket 449f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis LocalPtr += 4; // Skip the hash. 450f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis 451f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis // Determine the length of the key and the data. 45270042f5d1ca378138f90b7b9384023701f5d03d8David Blaikie const std::pair<unsigned, unsigned>& L =Info::ReadKeyDataLength(LocalPtr); 453f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis 454f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis // Read the key. 455f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis const internal_key_type& Key = 456f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis InfoObj->ReadKey(LocalPtr, L.first); 457b346d2f419ec7d7ce6b20780d518490338efa7deNick Lewycky return InfoObj->ReadData(Key, LocalPtr + L.first, L.second); 458f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis } 459f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis }; 46070042f5d1ca378138f90b7b9384023701f5d03d8David Blaikie 461b346d2f419ec7d7ce6b20780d518490338efa7deNick Lewycky data_iterator data_begin() { 462b346d2f419ec7d7ce6b20780d518490338efa7deNick Lewycky return data_iterator(Base + 4, getNumEntries(), &InfoObj); 463f08b1bb341fde5c755ec3dbe7e1b3114fb7438dbArgyrios Kyrtzidis } 464b346d2f419ec7d7ce6b20780d518490338efa7deNick Lewycky data_iterator data_end() { return data_iterator(); } 4651eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 466b4dc485a2b38ea98ba7da01596fd0e8438120346Douglas Gregor Info &getInfoObj() { return InfoObj; } 46770042f5d1ca378138f90b7b9384023701f5d03d8David Blaikie 4689378ba44b3f46d697653003c784be87746e138d2Douglas Gregor static OnDiskChainedHashTable* Create(const unsigned char* buckets, 469668c1a4fdcc56bdd050256b1688e116fe84b72dbDouglas Gregor const unsigned char* const base, 470668c1a4fdcc56bdd050256b1688e116fe84b72dbDouglas Gregor const Info &InfoObj = Info()) { 4719378ba44b3f46d697653003c784be87746e138d2Douglas Gregor using namespace io; 4729378ba44b3f46d697653003c784be87746e138d2Douglas Gregor assert(buckets > base); 4739378ba44b3f46d697653003c784be87746e138d2Douglas Gregor assert((reinterpret_cast<uintptr_t>(buckets) & 0x3) == 0 && 4749378ba44b3f46d697653003c784be87746e138d2Douglas Gregor "buckets should be 4-byte aligned."); 4751eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4769378ba44b3f46d697653003c784be87746e138d2Douglas Gregor unsigned numBuckets = ReadLE32(buckets); 4779378ba44b3f46d697653003c784be87746e138d2Douglas Gregor unsigned numEntries = ReadLE32(buckets); 4789378ba44b3f46d697653003c784be87746e138d2Douglas Gregor return new OnDiskChainedHashTable<Info>(numBuckets, numEntries, buckets, 479668c1a4fdcc56bdd050256b1688e116fe84b72dbDouglas Gregor base, InfoObj); 4801eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 4819378ba44b3f46d697653003c784be87746e138d2Douglas Gregor}; 4829378ba44b3f46d697653003c784be87746e138d2Douglas Gregor 4839378ba44b3f46d697653003c784be87746e138d2Douglas Gregor} // end namespace clang 4849378ba44b3f46d697653003c784be87746e138d2Douglas Gregor 4851eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump#endif 486