HashTable.h revision abe0db302735bbdf9cd84caee2a36e6c4538fc4d
120111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber//===- HashTable.h ---------------------------------------------------------===// 220111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber// 320111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber// The MCLinker Project 420111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber// 520111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber// This file is distributed under the University of Illinois Open Source 620111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber// License. See LICENSE.TXT for details. 720111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber// 820111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber//===----------------------------------------------------------------------===// 920111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber 1020111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber#ifndef MCLD_HASH_TABLE_H 1120111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber#define MCLD_HASH_TABLE_H 1220111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber#ifdef ENABLE_UNITTEST 1320111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber#include <gtest.h> 1420111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber#endif 1520111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber 1620111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber#include "mcld/ADT/HashBase.h" 1720111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber#include "mcld/ADT/HashIterator.h" 1820111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber#include "mcld/ADT/Uncopyable.h" 1920111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber#include "mcld/ADT/TypeTraits.h" 20f1d5aa162c02a16b7195a43a9bcea4d592600ac4James Dong#include "mcld/Support/Allocators.h" 2120111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber#include <utility> 2220111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber 2320111aa043c5f404472bc63b90bc5aad906b1101Andreas Hubernamespace mcld 2420111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber{ 2520111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber 2620111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber/** \class HashTable 2720111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber * \brief HashTable is a hash table which follows boost::unordered_map, but it 2820111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber * is open addressing and can linear probing. 2920111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber * 3020111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber * mcld::HashTable is a linear probing hash table. It does not allocate 3120111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber * the memory space of the entries by itself. Instead, entries are allocated 3220111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber * outside and then emplaced into the hash table. 3320111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber */ 3420111aa043c5f404472bc63b90bc5aad906b1101Andreas Hubertemplate<typename HashEntryTy, 3520111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber typename HashFunctionTy, 3620111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber typename EntryFactoryTy> 3720111aa043c5f404472bc63b90bc5aad906b1101Andreas Huberclass HashTable : public HashTableImpl<HashEntryTy, HashFunctionTy>, 3820111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber private Uncopyable 3920111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber{ 4020111aa043c5f404472bc63b90bc5aad906b1101Andreas Huberprivate: 4120111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber typedef HashTableImpl<HashEntryTy, HashFunctionTy> BaseTy; 4220111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber 4320111aa043c5f404472bc63b90bc5aad906b1101Andreas Huberpublic: 4420111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber typedef size_t size_type; 4520111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber typedef HashFunctionTy hasher; 4620111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber typedef HashEntryTy entry_type; 4720111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber typedef typename BaseTy::bucket_type bucket_type; 4820111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber typedef typename HashEntryTy::key_type key_type; 4920111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber 5020111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber typedef HashIterator<ChainIteratorBase<BaseTy>, 5120111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber NonConstTraits<HashEntryTy> > chain_iterator; 5220111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber typedef HashIterator<ChainIteratorBase<const BaseTy>, 5320111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber ConstTraits<HashEntryTy> > const_chain_iterator; 5420111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber 5520111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber typedef HashIterator<EntryIteratorBase<BaseTy>, 5620111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber NonConstTraits<HashEntryTy> > entry_iterator; 5720111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber typedef HashIterator<EntryIteratorBase<const BaseTy>, 5820111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber ConstTraits<HashEntryTy> > const_entry_iterator; 5920111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber 6020111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber typedef entry_iterator iterator; 6148c948b1137e7bbdb161b51908657ab72ac5e2daAndreas Huber typedef const_entry_iterator const_iterator; 6248c948b1137e7bbdb161b51908657ab72ac5e2daAndreas Huber 6348c948b1137e7bbdb161b51908657ab72ac5e2daAndreas Huberpublic: 6448c948b1137e7bbdb161b51908657ab72ac5e2daAndreas Huber // ----- constructor ----- // 6520111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber explicit HashTable(size_type pSize=3); 6620111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber ~HashTable(); 6720111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber 6820111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber EntryFactoryTy& getEntryFactory() 6920111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber { return m_EntryFactory; } 7020111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber 7120111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber // ----- modifiers ----- // 7220111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber void clear(); 73f5ab57c2d5e02af7483c94eddb177e4f5c9e9892Andreas Huber 74f5ab57c2d5e02af7483c94eddb177e4f5c9e9892Andreas Huber /// insert - insert a new element to the container. The element is 75f5ab57c2d5e02af7483c94eddb177e4f5c9e9892Andreas Huber // constructed in-place, i.e. no copy or move operations are performed. 76f5ab57c2d5e02af7483c94eddb177e4f5c9e9892Andreas Huber // If the element already exists, return the element, and set pExist true. 77f5ab57c2d5e02af7483c94eddb177e4f5c9e9892Andreas Huber entry_type* insert(const key_type& pKey, bool& pExist); 78f5ab57c2d5e02af7483c94eddb177e4f5c9e9892Andreas Huber 79f5ab57c2d5e02af7483c94eddb177e4f5c9e9892Andreas Huber /// erase - remove the element with the same key 80f5ab57c2d5e02af7483c94eddb177e4f5c9e9892Andreas Huber size_type erase(const key_type& pKey); 81f5ab57c2d5e02af7483c94eddb177e4f5c9e9892Andreas Huber 82f5ab57c2d5e02af7483c94eddb177e4f5c9e9892Andreas Huber // ----- lookups ----- // 83f5ab57c2d5e02af7483c94eddb177e4f5c9e9892Andreas Huber /// find - finds an element with key pKey 84f5ab57c2d5e02af7483c94eddb177e4f5c9e9892Andreas Huber // If the element does not exist, return end() 85f5ab57c2d5e02af7483c94eddb177e4f5c9e9892Andreas Huber iterator find(const key_type& pKey); 862cf9c5073ca3342ee52673ad68763fadd2c2be79James Dong 8720111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber /// find - finds an element with key pKey, constant version 8820111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber // If the element does not exist, return end() 8920111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber const_iterator find(const key_type& pKey) const; 9020111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber 9120111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber size_type count(const key_type& pKey) const; 9220111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber 9320111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber // ----- hash policy ----- // 9420111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber float load_factor() const; 9520111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber 9620111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber /// rehash - if the load factor is larger than 75%, or the empty buckets is 9720111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber // less than 12.5%, the rehash the hash table 9820111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber void rehash(); 992cf9c5073ca3342ee52673ad68763fadd2c2be79James Dong 10020111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber /// rehash - immediately re-new the hash table to the size pCount, and 10120111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber // rehash all elements. 10220111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber void rehash(size_type pCount); 10320111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber 10420111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber // ----- iterators ----- // 10520111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber iterator begin(); 10620111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber iterator end(); 1070c89199745bc1bf05b997fc7c342017807676b6fAndreas Huber 10820111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber const_entry_iterator begin() const; 10920111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber const_entry_iterator end() const; 11020111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber 11120111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber chain_iterator begin(const key_type& pKey); 11220111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber chain_iterator end(const key_type& pKey); 11320111aa043c5f404472bc63b90bc5aad906b1101Andreas Huber const_chain_iterator begin(const key_type& pKey) const; 1142cf9c5073ca3342ee52673ad68763fadd2c2be79James Dong const_chain_iterator end(const key_type& pKey) const; 11548c948b1137e7bbdb161b51908657ab72ac5e2daAndreas Huber 11648c948b1137e7bbdb161b51908657ab72ac5e2daAndreas Huberprivate: 11748c948b1137e7bbdb161b51908657ab72ac5e2daAndreas Huber EntryFactoryTy m_EntryFactory; 11848c948b1137e7bbdb161b51908657ab72ac5e2daAndreas Huber 11948c948b1137e7bbdb161b51908657ab72ac5e2daAndreas Huber}; 12048c948b1137e7bbdb161b51908657ab72ac5e2daAndreas Huber 12148c948b1137e7bbdb161b51908657ab72ac5e2daAndreas Huber#include "HashTable.tcc" 12248c948b1137e7bbdb161b51908657ab72ac5e2daAndreas Huber 12348c948b1137e7bbdb161b51908657ab72ac5e2daAndreas Huber} // namespace of mcld 12448c948b1137e7bbdb161b51908657ab72ac5e2daAndreas Huber 12548c948b1137e7bbdb161b51908657ab72ac5e2daAndreas Huber#endif 12648c948b1137e7bbdb161b51908657ab72ac5e2daAndreas Huber