ug4
hash.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2009-2015: G-CSC, Goethe University Frankfurt
3  * Author: Sebastian Reiter
4  *
5  * This file is part of UG4.
6  *
7  * UG4 is free software: you can redistribute it and/or modify it under the
8  * terms of the GNU Lesser General Public License version 3 (as published by the
9  * Free Software Foundation) with the following additional attribution
10  * requirements (according to LGPL/GPL v3 §7):
11  *
12  * (1) The following notice must be displayed in the Appropriate Legal Notices
13  * of covered and combined works: "Based on UG4 (www.ug4.org/license)".
14  *
15  * (2) The following notice must be displayed at a prominent place in the
16  * terminal output of covered works: "Based on UG4 (www.ug4.org/license)".
17  *
18  * (3) The following bibliography is recommended for citation and must be
19  * preserved in all covered files:
20  * "Reiter, S., Vogel, A., Heppner, I., Rupp, M., and Wittum, G. A massively
21  * parallel geometric multigrid solver on hierarchically distributed grids.
22  * Computing and visualization in science 16, 4 (2013), 151-164"
23  * "Vogel, A., Reiter, S., Rupp, M., Nägel, A., and Wittum, G. UG4 -- a novel
24  * flexible software system for simulating pde based models on high performance
25  * computers. Computing and visualization in science 16, 4 (2013), 165-179"
26  *
27  * This program is distributed in the hope that it will be useful,
28  * but WITHOUT ANY WARRANTY; without even the implied warranty of
29  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30  * GNU Lesser General Public License for more details.
31  */
32 
33 #ifndef __H__UG__hash__
34 #define __H__UG__hash__
35 
36 #include <vector>
37 #include <utility>
38 #include "hash_iterator.h"
39 #include "hash_function.h"
40 
41 namespace ug{
42 
44 
46 template <class TKey, class TValue>
47 class Hash
48 {
49  private:
50  struct Entry;
51 
52  public:
53  typedef TKey key_t;
54  typedef TValue value_t;
56 // typedef const_hash_iterator<key_t, value_t, Entry> const_iterator;
57 
58  Hash();
59  Hash(size_t hashSize);
60 
61  void resize_hash(size_t size);
62  size_t hash_size() const;
63 
64 // void enable_auto_hash_resize(float maxElemToHashSizeRatio,
65 // float bestElemToHashSizeRatio);
66 //
67 // void disable_auto_hash_resize();
68 
69 
71 
72  void reserve(size_t size);
73 
75 
78  size_t capacity() const;
79 
81  size_t size() const;
82 
83  void clear();
84 
85  bool empty() const;
86  bool has_entry(const key_t& key) const;
87 
88  value_t& get_entry(const key_t& key);
89  const value_t& get_entry(const key_t& key) const;
90  bool get_entry(value_t& valOut, const key_t& key) const;
91 
92  void insert(const key_t& key, const value_t& val);
93  void erase(const key_t& key);
94 
95  iterator begin(const key_t& key);
96  iterator end(const key_t& key);
97 
98 // const_iterator begin(const key_t& key) const;
99 // const_iterator end(const key_t& key) const;
100 
101  private:
102  size_t hash_index(const key_t& key) const;
103  size_t find_entry(const key_t& key) const;
104  inline size_t invalid_index() const {return -1;}
105 
106  struct Entry{
109  size_t next;
110 
111  Entry() {}
112  Entry(const key_t& k, const value_t& v) :
113  key(k), value(v), next(-1)
114  {}
115  };
116 
117  std::vector<Entry> m_entries;
118  size_t m_numEntries;
120 
123  std::vector<std::pair<size_t, size_t> > m_hashList;
124 
125 };
126 
127 }// end of namespace
128 
129 
130 #include "hash_impl.hpp"
131 
132 #endif
Definition: hash.h:48
void insert(const key_t &key, const value_t &val)
Definition: hash_impl.hpp:199
TValue value_t
Definition: hash.h:54
size_t m_numEntries
Definition: hash.h:118
std::vector< Entry > m_entries
Definition: hash.h:117
value_t & get_entry(const key_t &key)
Definition: hash_impl.hpp:158
size_t capacity() const
returns the capacity of the container in which key-value-pairs are stored.
Definition: hash_impl.hpp:121
size_t invalid_index() const
Definition: hash.h:104
bool has_entry(const key_t &key) const
Definition: hash_impl.hpp:150
iterator begin(const key_t &key)
Definition: hash_impl.hpp:263
bool empty() const
Definition: hash_impl.hpp:142
TKey key_t
Definition: hash.h:50
size_t hash_size() const
Definition: hash_impl.hpp:105
void erase(const key_t &key)
Definition: hash_impl.hpp:227
size_t hash_index(const key_t &key) const
Definition: hash_impl.hpp:280
iterator end(const key_t &key)
Definition: hash_impl.hpp:273
size_t find_entry(const key_t &key) const
Definition: hash_impl.hpp:287
void reserve(size_t size)
Reserves memory for key-value-pair storage.
Definition: hash_impl.hpp:113
size_t size() const
returns the number of key-value-pairs currently stored in the hash
std::vector< std::pair< size_t, size_t > > m_hashList
Definition: hash.h:123
void resize_hash(size_t size)
Definition: hash_impl.hpp:66
void clear()
Definition: hash_impl.hpp:129
Hash()
Definition: hash_impl.hpp:46
size_t m_firstUnusedEntry
Definition: hash.h:119
hash_iterator< key_t, value_t, Entry > iterator
Definition: hash.h:55
this iterator is used by the hash class to provide access to the elements of a given key
Definition: hash_iterator.h:42
the ug namespace
Definition: hash.h:106
Entry()
Definition: hash.h:111
key_t key
Definition: hash.h:107
size_t next
Definition: hash.h:109
value_t value
Definition: hash.h:108
Entry(const key_t &k, const value_t &v)
Definition: hash.h:112