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//===----------------------------------------------------------------------===// 95460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#ifndef MCLD_HASH_BASE_H 105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#define MCLD_HASH_BASE_H 115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#ifdef ENABLE_UNITTEST 125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <gtest.h> 135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#endif 145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <llvm/ADT/StringRef.h> 155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <cstdlib> 165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaonamespace mcld { 185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** forward declaration **/ 205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename HashTableImplTy> 215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass ChainIteratorBase; 225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename HashTableImplTy> 245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass EntryIteratorBase; 255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class HashBucket 275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief HashBucket is an entry in the hash table. 285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename HashEntryTy> 305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass HashBucket 315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntryTy entry_type; 345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int FullHashValue; 375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao entry_type *Entry; 385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao static entry_type* getEmptyBucket(); 415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao static entry_type* getTombstone(); 425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class HashTableImpl 465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief HashTableImpl is the base class of HashTable. 475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * HashTableImpl uses open-addressing, linear probing hash table. 495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * linear probing hash table obviously has high performance when the 505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * load factor is less than 0.7. 515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * The drawback is that the number of the stored items can notbe more 525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * than the size of the hash table. 535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * MCLinker tries to merge every things in the same HashEntry. It can 555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * keep every thing in the same cache line and improve the locality 565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * efficiently. HashTableImpl provides a template argument to change the 575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * definition of HashEntries. 585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * HashEntryTy must provide getKey() and getKenLength() functions. 605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * Different environments have different demands of HashFunctions. For 625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * example, on-device linkers needs a more light-weight hash function 635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * than static linkers. HashTableImpl also provides a template argument to 645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * change the hash functions. 655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename HashEntryTy, 675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typename HashFunctionTy> 685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass HashTableImpl 695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoprivate: 715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao static const unsigned int NumOfInitBuckets = 16; 725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef size_t size_type; 755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashFunctionTy hasher; 765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntryTy entry_type; 775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename HashEntryTy::key_type key_type; 785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashBucket<HashEntryTy> bucket_type; 795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashTableImpl<HashEntryTy, HashFunctionTy> Self; 805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableImpl(); 845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao explicit HashTableImpl(unsigned int pInitSize); 855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao virtual ~HashTableImpl(); 865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // ----- observers ----- // 885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool empty() const; 895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao size_t numOfBuckets() const 915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return m_NumOfBuckets; } 925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao size_t numOfEntries() const 945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return m_NumOfEntries; } 955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hasher& hash() 975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return m_Hasher; } 985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const hasher& hash() const 1005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return m_Hasher; } 1015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoprotected: 1035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// initialize the hash table. 1045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void init(unsigned int pInitSize); 1055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// lookUpBucketFor - search the index of bucket whose key is p>ey 1075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // @return the index of the found bucket 1085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int lookUpBucketFor(const key_type& pKey); 1095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// findKey - finds an element with key pKey 1115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // return the index of the element, or -1 when the element does not exist. 1125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao int findKey(const key_type& pKey) const; 1135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// mayRehash - check the load_factor, compute the new size, and then doRehash 1155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void mayRehash(); 1165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// doRehash - re-new the hash table, and rehash all elements into the new buckets 1185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void doRehash(unsigned int pNewSize); 1195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaofriend class ChainIteratorBase<Self>; 1215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaofriend class ChainIteratorBase<const Self>; 1225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaofriend class EntryIteratorBase<Self>; 1235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaofriend class EntryIteratorBase<const Self>; 1245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoprotected: 1255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // Array of Buckets 1265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bucket_type* m_Buckets; 1275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int m_NumOfBuckets; 1285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int m_NumOfEntries; 1295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int m_NumOfTombstones; 1305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hasher m_Hasher; 1315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include "HashBase.tcc" 1355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} // namespace of mcld 1375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#endif 139affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 140