15460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//===- HashBase.h ---------------------------------------------------------===// 25460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// 35460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// The MCLinker Project 45460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// 55460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// This file is distributed under the University of Illinois Open Source 65460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// License. See LICENSE.TXT for details. 75460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// 85460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//===----------------------------------------------------------------------===// 937b74a387bb3993387029859c2d9d051c41c724eStephen Hines#ifndef MCLD_ADT_HASHBASE_H_ 1037b74a387bb3993387029859c2d9d051c41c724eStephen Hines#define MCLD_ADT_HASHBASE_H_ 1137b74a387bb3993387029859c2d9d051c41c724eStephen Hines 125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <llvm/ADT/StringRef.h> 1337b74a387bb3993387029859c2d9d051c41c724eStephen Hines 145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <cstdlib> 155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaonamespace mcld { 175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** forward declaration **/ 1937b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <typename HashTableImplTy> 205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass ChainIteratorBase; 215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2237b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <typename HashTableImplTy> 235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass EntryIteratorBase; 245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class HashBucket 265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief HashBucket is an entry in the hash table. 275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 2837b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <typename HashEntryTy> 2937b74a387bb3993387029859c2d9d051c41c724eStephen Hinesclass HashBucket { 3037b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntryTy entry_type; 325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3337b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int FullHashValue; 3537b74a387bb3993387029859c2d9d051c41c724eStephen Hines entry_type* Entry; 365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3737b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao static entry_type* getEmptyBucket(); 395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao static entry_type* getTombstone(); 405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class HashTableImpl 435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief HashTableImpl is the base class of HashTable. 445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * HashTableImpl uses open-addressing, linear probing hash table. 465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * linear probing hash table obviously has high performance when the 475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * load factor is less than 0.7. 485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * The drawback is that the number of the stored items can notbe more 495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * than the size of the hash table. 505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * MCLinker tries to merge every things in the same HashEntry. It can 525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * keep every thing in the same cache line and improve the locality 535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * efficiently. HashTableImpl provides a template argument to change the 545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * definition of HashEntries. 555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * HashEntryTy must provide getKey() and getKenLength() functions. 575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * Different environments have different demands of HashFunctions. For 595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * example, on-device linkers needs a more light-weight hash function 605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * than static linkers. HashTableImpl also provides a template argument to 615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * change the hash functions. 625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 6337b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <typename HashEntryTy, typename HashFunctionTy> 6437b74a387bb3993387029859c2d9d051c41c724eStephen Hinesclass HashTableImpl { 6537b74a387bb3993387029859c2d9d051c41c724eStephen Hines private: 665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao static const unsigned int NumOfInitBuckets = 16; 675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 6837b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef size_t size_type; 705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashFunctionTy hasher; 715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntryTy entry_type; 725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename HashEntryTy::key_type key_type; 735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashBucket<HashEntryTy> bucket_type; 745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashTableImpl<HashEntryTy, HashFunctionTy> Self; 755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 7637b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableImpl(); 785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao explicit HashTableImpl(unsigned int pInitSize); 795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao virtual ~HashTableImpl(); 805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // ----- observers ----- // 825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool empty() const; 835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 8437b74a387bb3993387029859c2d9d051c41c724eStephen Hines size_t numOfBuckets() const { return m_NumOfBuckets; } 855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 8637b74a387bb3993387029859c2d9d051c41c724eStephen Hines size_t numOfEntries() const { return m_NumOfEntries; } 875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 8837b74a387bb3993387029859c2d9d051c41c724eStephen Hines hasher& hash() { return m_Hasher; } 895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 9037b74a387bb3993387029859c2d9d051c41c724eStephen Hines const hasher& hash() const { return m_Hasher; } 915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 9237b74a387bb3993387029859c2d9d051c41c724eStephen Hines protected: 935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// initialize the hash table. 945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void init(unsigned int pInitSize); 955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 9622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao void clear(); 9722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// lookUpBucketFor - search the index of bucket whose key is p>ey 995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // @return the index of the found bucket 1005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int lookUpBucketFor(const key_type& pKey); 1015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// findKey - finds an element with key pKey 1035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // return the index of the element, or -1 when the element does not exist. 1045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao int findKey(const key_type& pKey) const; 1055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// mayRehash - check the load_factor, compute the new size, and then doRehash 1075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void mayRehash(); 1085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 10937b74a387bb3993387029859c2d9d051c41c724eStephen Hines /// doRehash - re-new the hash table, and rehash all elements into the new 11037b74a387bb3993387029859c2d9d051c41c724eStephen Hines /// buckets 1115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void doRehash(unsigned int pNewSize); 1125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 11337b74a387bb3993387029859c2d9d051c41c724eStephen Hines friend class ChainIteratorBase<Self>; 11437b74a387bb3993387029859c2d9d051c41c724eStephen Hines friend class ChainIteratorBase<const Self>; 11537b74a387bb3993387029859c2d9d051c41c724eStephen Hines friend class EntryIteratorBase<Self>; 11637b74a387bb3993387029859c2d9d051c41c724eStephen Hines friend class EntryIteratorBase<const Self>; 11737b74a387bb3993387029859c2d9d051c41c724eStephen Hines 11837b74a387bb3993387029859c2d9d051c41c724eStephen Hines protected: 1195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // Array of Buckets 1205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bucket_type* m_Buckets; 1215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int m_NumOfBuckets; 1225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int m_NumOfEntries; 1235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int m_NumOfTombstones; 1245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hasher m_Hasher; 1255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include "HashBase.tcc" 1285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 12937b74a387bb3993387029859c2d9d051c41c724eStephen Hines} // namespace mcld 130affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 13137b74a387bb3993387029859c2d9d051c41c724eStephen Hines#endif // MCLD_ADT_HASHBASE_H_ 132