15460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//===- HashTable.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_TABLE_H 105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#define MCLD_HASH_TABLE_H 115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#ifdef ENABLE_UNITTEST 125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <gtest.h> 135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#endif 145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/ADT/HashBase.h> 1622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/ADT/HashIterator.h> 1722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/ADT/HashEntryFactory.h> 1822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/ADT/Uncopyable.h> 1922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/ADT/TypeTraits.h> 2022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/Support/Allocators.h> 215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <utility> 225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaonamespace mcld { 245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class HashTable 265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief HashTable is a hash table which follows boost::unordered_map, but it 275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * is open addressing and can linear probing. 285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * mcld::HashTable is a linear probing hash table. It does not allocate 305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * the memory space of the entries by itself. Instead, entries are allocated 315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * outside and then emplaced into the hash table. 325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename HashEntryTy, 345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typename HashFunctionTy, 3522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao typename EntryFactoryTy = HashEntryFactory<HashEntryTy> > 365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass HashTable : public HashTableImpl<HashEntryTy, HashFunctionTy>, 375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao private Uncopyable 385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoprivate: 405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashTableImpl<HashEntryTy, HashFunctionTy> BaseTy; 415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef size_t size_type; 445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashFunctionTy hasher; 455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntryTy entry_type; 465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename BaseTy::bucket_type bucket_type; 475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename HashEntryTy::key_type key_type; 485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashIterator<ChainIteratorBase<BaseTy>, 505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao NonConstTraits<HashEntryTy> > chain_iterator; 515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashIterator<ChainIteratorBase<const BaseTy>, 525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ConstTraits<HashEntryTy> > const_chain_iterator; 535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashIterator<EntryIteratorBase<BaseTy>, 555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao NonConstTraits<HashEntryTy> > entry_iterator; 565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashIterator<EntryIteratorBase<const BaseTy>, 575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ConstTraits<HashEntryTy> > const_entry_iterator; 585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef entry_iterator iterator; 605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef const_entry_iterator const_iterator; 615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // ----- constructor ----- // 645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao explicit HashTable(size_type pSize=3); 655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ~HashTable(); 66affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EntryFactoryTy& getEntryFactory() 685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return m_EntryFactory; } 695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // ----- modifiers ----- // 715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void clear(); 725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// insert - insert a new element to the container. The element is 745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // constructed in-place, i.e. no copy or move operations are performed. 755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // If the element already exists, return the element, and set pExist true. 765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao entry_type* insert(const key_type& pKey, bool& pExist); 775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// erase - remove the element with the same key 795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao size_type erase(const key_type& pKey); 805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // ----- lookups ----- // 825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// find - finds an element with key pKey 835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // If the element does not exist, return end() 845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao iterator find(const key_type& pKey); 855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// find - finds an element with key pKey, constant version 875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // If the element does not exist, return end() 885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_iterator find(const key_type& pKey) const; 895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao size_type count(const key_type& pKey) const; 91affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // ----- hash policy ----- // 935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao float load_factor() const; 945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// rehash - if the load factor is larger than 75%, or the empty buckets is 965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // less than 12.5%, the rehash the hash table 975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void rehash(); 985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// rehash - immediately re-new the hash table to the size pCount, and 1005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // rehash all elements. 1015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void rehash(size_type pCount); 1025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // ----- iterators ----- // 1045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao iterator begin(); 1055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao iterator end(); 1065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_entry_iterator begin() const; 1085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_entry_iterator end() const; 1095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao chain_iterator begin(const key_type& pKey); 1115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao chain_iterator end(const key_type& pKey); 1125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_chain_iterator begin(const key_type& pKey) const; 1135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_chain_iterator end(const key_type& pKey) const; 1145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoprivate: 1165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EntryFactoryTy m_EntryFactory; 1175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include "HashTable.tcc" 1215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} // namespace of mcld 1235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#endif 125affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 126