Index: ps/trunk/source/lib/adts/dyn_hash_tbl.h =================================================================== --- ps/trunk/source/lib/adts/dyn_hash_tbl.h (revision 25518) +++ ps/trunk/source/lib/adts/dyn_hash_tbl.h (nonexistent) @@ -1,238 +0,0 @@ -/* Copyright (C) 2011 Wildfire Games. - * - * Permission is hereby granted, free of charge, to any person obtaining - * a copy of this software and associated documentation files (the - * "Software"), to deal in the Software without restriction, including - * without limitation the rights to use, copy, modify, merge, publish, - * distribute, sublicense, and/or sell copies of the Software, and to - * permit persons to whom the Software is furnished to do so, subject to - * the following conditions: - * - * The above copyright notice and this permission notice shall be included - * in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, - * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF - * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. - * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY - * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, - * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE - * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. - */ - -/* - * dynamic (grow-able) hash table - */ - -#ifndef INCLUDED_ADTS_DYN_HASH_TBL -#define INCLUDED_ADTS_DYN_HASH_TBL - -#include // strcmp - -#include "lib/fnv_hash.h" - -template class DHT_Traits -{ -public: - static const size_t initial_entries = 16; - size_t hash(Key key) const; - bool equal(Key k1, Key k2) const; - Key get_key(T t) const; -}; - -template<> class DHT_Traits -{ -public: - static const size_t initial_entries = 512; - size_t hash(const char* key) const - { - return (size_t)fnv_lc_hash(key); - } - bool equal(const char* k1, const char* k2) const - { - return !strcmp(k1, k2); - } - const char* get_key(const char* t) const - { - return t; - } -}; - - -// intended for pointer types -template > -class DynHashTbl -{ - T* tbl; - u16 num_entries; - u16 max_entries; // when initialized, = 2**n for faster modulo - Traits tr; - - T& get_slot(Key key) const - { - size_t hash = tr.hash(key); - ENSURE(max_entries != 0); // otherwise, mask will be incorrect - const size_t mask = max_entries-1; - for(;;) - { - T& t = tbl[hash & mask]; - // empty slot encountered => not found - if(!t) - return t; - // keys are actually equal => found it - if(tr.equal(key, tr.get_key(t))) - return t; - // keep going (linear probing) - hash++; - } - } - - void expand_tbl() - { - // alloc a new table (but don't assign it to unless successful) - T* old_tbl = tbl; - tbl = (T*)calloc(max_entries*2, sizeof(T)); - if(!tbl) - { - tbl = old_tbl; - throw std::bad_alloc(); - } - - max_entries *= 2; - // must be set before get_slot - - // newly initialized, nothing to copy - done - if(!old_tbl) - return; - - // re-hash from old table into the new one - for(size_t i = 0; i < max_entries/2u; i++) - { - T t = old_tbl[i]; - if(t) - get_slot(tr.get_key(t)) = t; - } - free(old_tbl); - } - - -public: - - DynHashTbl() - { - tbl = 0; - clear(); - } - - ~DynHashTbl() - { - free(tbl); - } - - void clear() - { - // must remain usable after calling clear, so shrink the table to - // its initial size but don't deallocate it completely - SAFE_FREE(tbl); - num_entries = 0; - // rationale: must not set to 0 because expand_tbl only doubles the size. - // don't keep the previous size when clearing because it may have become - // huge and there is no provision for shrinking. - max_entries = tr.initial_entries/2; // will be doubled in expand_tbl - expand_tbl(); - } - - void insert(const Key key, const T t) - { - // more than 75% full - increase table size. - // do so before determining slot; this will invalidate previous pnodes. - if(num_entries*4 >= max_entries*3) - expand_tbl(); - - T& slot = get_slot(key); - ENSURE(slot == 0); // not already present - slot = t; - num_entries++; - } - - T find(Key key) const - { - return get_slot(key); - } - - size_t size() const - { - return num_entries; - } - - - class iterator - { - public: - typedef std::forward_iterator_tag iterator_category; - typedef T value_type; - typedef ptrdiff_t difference_type; - typedef const T* pointer; - typedef const T& reference; - - iterator() - { - } - iterator(T* pos_, T* end_) : pos(pos_), end(end_) - { - } - T& operator*() const - { - return *pos; - } - iterator& operator++() // pre - { - do - pos++; - while(pos != end && *pos == 0); - return (*this); - } - bool operator==(const iterator& rhs) const - { - return pos == rhs.pos; - } - bool operator<(const iterator& rhs) const - { - return (pos < rhs.pos); - } - - // derived - const T* operator->() const - { - return &**this; - } - bool operator!=(const iterator& rhs) const - { - return !(*this == rhs); - } - iterator operator++(int) // post - { - iterator tmp = *this; ++*this; return tmp; - } - - protected: - T* pos; - T* end; - // only used when incrementing (avoid going beyond end of table) - }; - - iterator begin() const - { - T* pos = tbl; - while(pos != tbl+max_entries && *pos == 0) - pos++; - return iterator(pos, tbl+max_entries); - } - iterator end() const - { - return iterator(tbl+max_entries, 0); - } -}; - - -#endif // #ifndef INCLUDED_ADTS_DYN_HASH_TBL Property changes on: ps/trunk/source/lib/adts/dyn_hash_tbl.h ___________________________________________________________________ Deleted: svn:eol-style ## -1 +0,0 ## -native \ No newline at end of property