libs/minisat/Map.h

   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
  64     vec<Pair>* table;
  65     int        cap;
  66     int        size;
  67
  68     // Don't allow copying (error prone):
  69     Map<K,D,H,E>&  operator = (Map<K,D,H,E>& other);
  70                    Map        (Map<K,D,H,E>& other);
  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