abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Map.h
Go to the documentation of this file.
1 /*******************************************************************************************[Map.h]
2 Copyright (c) 2006-2010, Niklas Sorensson
3 
4 Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
5 associated documentation files (the "Software"), to deal in the Software without restriction,
6 including without limitation the rights to use, copy, modify, merge, publish, distribute,
7 sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
8 furnished to do so, subject to the following conditions:
9 
10 The above copyright notice and this permission notice shall be included in all copies or
11 substantial portions of the Software.
12 
13 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
14 NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
15 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
16 DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT
17 OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
18 **************************************************************************************************/
19 
20 #ifndef Minisat_Map_h
21 #define Minisat_Map_h
22 
23 #include "IntTypes.h"
24 #include "Vec.h"
25 
26 namespace Minisat {
27 
28 //=================================================================================================
29 // Default hash/equals functions
30 //
31 
32 template<class K> struct Hash { uint32_t operator()(const K& k) const { return hash(k); } };
33 template<class K> struct Equal { bool operator()(const K& k1, const K& k2) const { return k1 == k2; } };
34 
35 template<class K> struct DeepHash { uint32_t operator()(const K* k) const { return hash(*k); } };
36 template<class K> struct DeepEqual { bool operator()(const K* k1, const K* k2) const { return *k1 == *k2; } };
37 
38 static inline uint32_t hash(uint32_t x){ return x; }
39 static inline uint32_t hash(uint64_t x){ return (uint32_t)x; }
40 static inline uint32_t hash(int32_t x) { return (uint32_t)x; }
41 static inline uint32_t hash(int64_t x) { return (uint32_t)x; }
42 
43 
44 //=================================================================================================
45 // Some primes
46 //
47 
48 static const int nprimes = 25;
49 static const int primes [nprimes] = { 31, 73, 151, 313, 643, 1291, 2593, 5233, 10501, 21013, 42073, 84181, 168451, 337219, 674701, 1349473, 2699299, 5398891, 10798093, 21596719, 43193641, 86387383, 172775299, 345550609, 691101253 };
50 
51 //=================================================================================================
52 // Hash table implementation of Maps
53 //
54 
55 template<class K, class D, class H = Hash<K>, class E = Equal<K> >
56 class Map {
57  public:
58  struct Pair { K key; D data; };
59 
60  private:
61  H hash;
62  E equals;
63 
65  int cap;
66  int size;
67 
68  // Don't allow copying (error prone):
70  Map (Map<K,D,H,E>& other) { assert(0); }
71 
72  bool checkCap(int new_size) const { return new_size > cap; }
73 
74  int32_t index (const K& k) const { return hash(k) % cap; }
75  void _insert (const K& k, const D& d) {
76  vec<Pair>& ps = table[index(k)];
77  ps.push(); ps.last().key = k; ps.last().data = d; }
78 
79  void rehash () {
80  const vec<Pair>* old = table;
81 
82  int old_cap = cap;
83  int newsize = primes[0];
84  for (int i = 1; newsize <= cap && i < nprimes; i++)
85  newsize = primes[i];
86 
87  table = new vec<Pair>[newsize];
88  cap = newsize;
89 
90  for (int i = 0; i < old_cap; i++){
91  for (int j = 0; j < old[i].size(); j++){
92  _insert(old[i][j].key, old[i][j].data); }}
93 
94  delete [] old;
95 
96  // printf(" --- rehashing, old-cap=%d, new-cap=%d\n", cap, newsize);
97  }
98 
99 
100  public:
101 
102  Map () : table(NULL), cap(0), size(0) {}
103  Map (const H& h, const E& e) : hash(h), equals(e), table(NULL), cap(0), size(0){}
104  ~Map () { delete [] table; }
105 
106  // PRECONDITION: the key must already exist in the map.
107  const D& operator [] (const K& k) const
108  {
109  assert(size != 0);
110  const D* res = NULL;
111  const vec<Pair>& ps = table[index(k)];
112  for (int i = 0; i < ps.size(); i++)
113  if (equals(ps[i].key, k))
114  res = &ps[i].data;
115  assert(res != NULL);
116  return *res;
117  }
118 
119  // PRECONDITION: the key must already exist in the map.
120  D& operator [] (const K& k)
121  {
122  assert(size != 0);
123  D* res = NULL;
124  vec<Pair>& ps = table[index(k)];
125  for (int i = 0; i < ps.size(); i++)
126  if (equals(ps[i].key, k))
127  res = &ps[i].data;
128  assert(res != NULL);
129  return *res;
130  }
131 
132  // PRECONDITION: the key must *NOT* exist in the map.
133  void insert (const K& k, const D& d) { if (checkCap(size+1)) rehash(); _insert(k, d); size++; }
134  bool peek (const K& k, D& d) const {
135  if (size == 0) return false;
136  const vec<Pair>& ps = table[index(k)];
137  for (int i = 0; i < ps.size(); i++)
138  if (equals(ps[i].key, k)){
139  d = ps[i].data;
140  return true; }
141  return false;
142  }
143 
144  bool has (const K& k) const {
145  if (size == 0) return false;
146  const vec<Pair>& ps = table[index(k)];
147  for (int i = 0; i < ps.size(); i++)
148  if (equals(ps[i].key, k))
149  return true;
150  return false;
151  }
152 
153  // PRECONDITION: the key must exist in the map.
154  void remove(const K& k) {
155  assert(table != NULL);
156  vec<Pair>& ps = table[index(k)];
157  int j = 0;
158  for (; j < ps.size() && !equals(ps[j].key, k); j++);
159  assert(j < ps.size());
160  ps[j] = ps.last();
161  ps.pop();
162  size--;
163  }
164 
165  void clear () {
166  cap = size = 0;
167  delete [] table;
168  table = NULL;
169  }
170 
171  int elems() const { return size; }
172  int bucket_count() const { return cap; }
173 
174  // NOTE: the hash and equality objects are not moved by this method:
175  void moveTo(Map& other){
176  delete [] other.table;
177 
178  other.table = table;
179  other.cap = cap;
180  other.size = size;
181 
182  table = NULL;
183  size = cap = 0;
184  }
185 
186  // NOTE: given a bit more time, I could make a more C++-style iterator out of this:
187  const vec<Pair>& bucket(int i) const { return table[i]; }
188 };
189 
190 //=================================================================================================
191 }
192 
193 #endif
void insert(const K &k, const D &d)
Definition: Map.h:133
const vec< Pair > & bucket(int i) const
Definition: Map.h:187
int elems() const
Definition: Map.h:171
int cap
Definition: Map.h:65
Map(const H &h, const E &e)
Definition: Map.h:103
Map< K, D, H, E > & operator=(Map< K, D, H, E > &other)
Definition: Map.h:69
void moveTo(Map &other)
Definition: Map.h:175
H hash
Definition: Map.h:61
bool operator()(const K &k1, const K &k2) const
Definition: Map.h:33
E equals
Definition: Map.h:62
Map(Map< K, D, H, E > &other)
Definition: Map.h:70
int size
Definition: Map.h:66
void push(void)
Definition: Vec.h:73
bool operator()(const K *k1, const K *k2) const
Definition: Map.h:36
const D & operator[](const K &k) const
Definition: Map.h:107
int size(void) const
Definition: Vec.h:63
bool checkCap(int new_size) const
Definition: Map.h:72
bool peek(const K &k, D &d) const
Definition: Map.h:134
vec< Pair > * table
Definition: Map.h:64
int bucket_count() const
Definition: Map.h:172
static uint32_t hash(uint32_t x)
Definition: Map.h:38
~Map()
Definition: Map.h:104
int32_t index(const K &k) const
Definition: Map.h:74
void rehash()
Definition: Map.h:79
uint32_t operator()(const K *k) const
Definition: Map.h:35
T * data
Definition: Vec.h:39
void _insert(const K &k, const D &d)
Definition: Map.h:75
enum keys key
bool has(const K &k) const
Definition: Map.h:144
void clear()
Definition: Map.h:165
uint32_t operator()(const K &k) const
Definition: Map.h:32
#define assert(ex)
Definition: util_old.h:213
static const int nprimes
Definition: Map.h:48
const T & last(void) const
Definition: Vec.h:82
static const int primes[nprimes]
Definition: Map.h:49