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//===----------------------------------------------------------------------===// 987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#ifndef MCLD_ADT_HASHBASE_H 1087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#define MCLD_ADT_HASHBASE_H 115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <llvm/ADT/StringRef.h> 125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <cstdlib> 135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaonamespace mcld { 155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** forward declaration **/ 175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename HashTableImplTy> 185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass ChainIteratorBase; 195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename HashTableImplTy> 215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass EntryIteratorBase; 225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class HashBucket 245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief HashBucket is an entry in the hash table. 255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename HashEntryTy> 275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass HashBucket 285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntryTy entry_type; 315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int FullHashValue; 345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao entry_type *Entry; 355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao static entry_type* getEmptyBucket(); 385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao static entry_type* getTombstone(); 395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 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 */ 635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename HashEntryTy, 645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typename HashFunctionTy> 655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass HashTableImpl 665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoprivate: 685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao static const unsigned int NumOfInitBuckets = 16; 695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef size_t size_type; 725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashFunctionTy hasher; 735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntryTy entry_type; 745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename HashEntryTy::key_type key_type; 755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashBucket<HashEntryTy> bucket_type; 765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashTableImpl<HashEntryTy, HashFunctionTy> Self; 775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableImpl(); 815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao explicit HashTableImpl(unsigned int pInitSize); 825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao virtual ~HashTableImpl(); 835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // ----- observers ----- // 855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool empty() const; 865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao size_t numOfBuckets() const 885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return m_NumOfBuckets; } 895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao size_t numOfEntries() const 915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return m_NumOfEntries; } 925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hasher& hash() 945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return m_Hasher; } 955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const hasher& hash() const 975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return m_Hasher; } 985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoprotected: 1005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// initialize the hash table. 1015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void init(unsigned int pInitSize); 1025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 10322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao void clear(); 10422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 1055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// lookUpBucketFor - search the index of bucket whose key is p>ey 1065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // @return the index of the found bucket 1075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int lookUpBucketFor(const key_type& pKey); 1085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// findKey - finds an element with key pKey 1105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // return the index of the element, or -1 when the element does not exist. 1115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao int findKey(const key_type& pKey) const; 1125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// mayRehash - check the load_factor, compute the new size, and then doRehash 1145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void mayRehash(); 1155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// doRehash - re-new the hash table, and rehash all elements into the new buckets 1175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void doRehash(unsigned int pNewSize); 1185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaofriend class ChainIteratorBase<Self>; 1205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaofriend class ChainIteratorBase<const Self>; 1215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaofriend class EntryIteratorBase<Self>; 1225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaofriend class EntryIteratorBase<const Self>; 1235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoprotected: 1245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // Array of Buckets 1255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bucket_type* m_Buckets; 1265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int m_NumOfBuckets; 1275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int m_NumOfEntries; 1285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int m_NumOfTombstones; 1295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hasher m_Hasher; 1305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include "HashBase.tcc" 1345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} // namespace of mcld 1365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#endif 138affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 139