c_cpp/lib/klib/cpp/khashl.hpp

   1 #ifndef __AC_KHASHL_HPP
   2 #define __AC_KHASHL_HPP
   3
   4 #include <functional> // for std::equal_to
   5 #include <cstdlib>    // for malloc() etc
   6 #include <cstring>    // for memset()
   7 #include <stdint.h>   // for uint32_t
   8
   9 /* // ==> Code example <==
  10 #include <cstdio>
  11 #include "khashl.hpp"
  12
  13 int main(void)
  14 {
  15         klib::KHashMap<uint32_t, int, std::hash<uint32_t> > h; // NB: C++98 doesn't have std::hash
  16         uint32_t k;
  17         int absent;
  18         h[43] = 1, h[53] = 2, h[63] = 3, h[73] = 4;       // one way to insert
  19         k = h.put(53, &absent), h.value(k) = -2;          // another way to insert
  20         if (!absent) printf("already in the table\n");    //   which allows to test presence
  21         if (h.get(33) == h.end()) printf("not found!\n"); // test presence without insertion
  22         h.del(h.get(43));               // deletion
  23         for (k = 0; k != h.end(); ++k)  // traversal
  24                 if (h.occupied(k))          // some buckets are not occupied; skip them
  25                         printf("%u => %d\n", h.key(k), h.value(k));
  26         return 0;
  27 }
  28 */
  29
  30 namespace klib {
  31
  32 /***********
  33  * HashSet *
  34  ***********/
  35
  36 template<class T, class Hash, class Eq = std::equal_to<T>, typename khint_t = uint32_t>
  37 class KHashSet {
  38         khint_t bits, count;
  39         uint32_t *used;
  40         T *keys;
  41         static inline uint32_t __kh_used(const uint32_t *flag, khint_t i) { return flag[i>>5] >> (i&0x1fU) & 1U; };
  42         static inline void __kh_set_used(uint32_t *flag, khint_t i) { flag[i>>5] |= 1U<<(i&0x1fU); };
  43         static inline void __kh_set_unused(uint32_t *flag, khint_t i) { flag[i>>5] &= ~(1U<<(i&0x1fU)); };
  44         static inline khint_t __kh_fsize(khint_t m) { return m<32? 1 : m>>5; }
  45         static inline khint_t __kh_h2b(uint32_t hash, khint_t bits) { return hash * 2654435769U >> (32 - bits); }
  46         static inline khint_t __kh_h2b(uint64_t hash, khint_t bits) { return hash * 11400714819323198485ULL >> (64 - bits); }
  47 public:
  48         KHashSet() : bits(0), count(0), used(0), keys(0) {};
  49         ~KHashSet() { std::free(used); std::free(keys); };
  50         inline khint_t n_buckets() const { return used? khint_t(1) << bits : 0; }
  51         inline khint_t end() const { return n_buckets(); }
  52         inline khint_t size() const { return count; }
  53         inline T &key(khint_t x) { return keys[x]; };
  54         inline bool occupied(khint_t x) const { return (__kh_used(used, x) != 0); }
  55         void clear(void) {
  56                 if (!used) return;
  57                 memset(used, 0, __kh_fsize(n_buckets()) * sizeof(uint32_t));
  58                 count = 0;
  59         }
  60         khint_t get(const T &key) const {
  61                 khint_t i, last, mask, nb;
  62                 if (keys == 0) return 0;
  63                 nb = n_buckets();
  64                 mask = nb - khint_t(1);
  65                 i = last = __kh_h2b(Hash()(key), bits);
  66                 while (__kh_used(used, i) && !Eq()(keys[i], key)) {
  67                         i = (i + khint_t(1)) & mask;
  68                         if (i == last) return nb;
  69                 }
  70                 return !__kh_used(used, i)? nb : i;
  71         }
  72         int resize(khint_t new_nb) {
  73                 uint32_t *new_used = 0;
  74                 khint_t j = 0, x = new_nb, nb, new_bits, new_mask;
  75                 while ((x >>= khint_t(1)) != 0) ++j;
  76                 if (new_nb & (new_nb - 1)) ++j;
  77                 new_bits = j > 2? j : 2;
  78                 new_nb = khint_t(1) << new_bits;
  79                 if (count > (new_nb>>1) + (new_nb>>2)) return 0; /* requested size is too small */
  80                 new_used = (uint32_t*)std::malloc(__kh_fsize(new_nb) * sizeof(uint32_t));
  81                 memset(new_used, 0, __kh_fsize(new_nb) * sizeof(uint32_t));
  82                 if (!new_used) return -1; /* not enough memory */
  83                 nb = n_buckets();
  84                 if (nb < new_nb) { /* expand */
  85                         T *new_keys = (T*)std::realloc(keys, new_nb * sizeof(T));
  86                         if (!new_keys) { std::free(new_used); return -1; }
  87                         keys = new_keys;
  88                 } /* otherwise shrink */
  89                 new_mask = new_nb - 1;
  90                 for (j = 0; j != nb; ++j) {
  91                         if (!__kh_used(used, j)) continue;
  92                         T key = keys[j];
  93                         __kh_set_unused(used, j);
  94                         while (1) { /* kick-out process; sort of like in Cuckoo hashing */
  95                                 khint_t i;
  96                                 i = __kh_h2b(Hash()(key), new_bits);
  97                                 while (__kh_used(new_used, i)) i = (i + khint_t(1)) & new_mask;
  98                                 __kh_set_used(new_used, i);
  99                                 if (i < nb && __kh_used(used, i)) { /* kick out the existing element */
 100                                         { T tmp = keys[i]; keys[i] = key; key = tmp; }
 101                                         __kh_set_unused(used, i); /* mark it as deleted in the old hash table */
 102                                 } else { /* write the element and jump out of the loop */
 103                                         keys[i] = key;
 104                                         break;
 105                                 }
 106                         }
 107                 }
 108                 if (nb > new_nb) /* shrink the hash table */
 109                         keys = (T*)std::realloc(keys, new_nb * sizeof(T));
 110                 std::free(used); /* free the working space */
 111                 used = new_used, bits = new_bits;
 112                 return 0;
 113         }
 114         khint_t put(const T &key, int *absent_ = 0) {
 115                 khint_t nb, i, last, mask;
 116                 int absent = -1;
 117                 nb = n_buckets();
 118                 if (count >= (nb>>1) + (nb>>2)) { /* rehashing */
 119                         if (resize(nb + khint_t(1)) < 0) {
 120                                 if (absent_) *absent_ = -1;
 121                                 return nb;
 122                         }
 123                         nb = n_buckets();
 124                 } /* TODO: to implement automatically shrinking; resize() already support shrinking */
 125                 mask = nb - 1;
 126                 i = last = __kh_h2b(Hash()(key), bits);
 127                 while (__kh_used(used, i) && !Eq()(keys[i], key)) {
 128                         i = (i + 1U) & mask;
 129                         if (i == last) break;
 130                 }
 131                 if (!__kh_used(used, i)) { /* not present at all */
 132                         keys[i] = key;
 133                         __kh_set_used(used, i);
 134                         ++count, absent = 1;
 135                 } else absent = 0; /* Don't touch keys[i] if present */
 136                 if (absent_) *absent_ = absent;
 137                 return i;
 138         }
 139         int del(khint_t i) {
 140                 khint_t j = i, k, mask, nb = n_buckets();
 141                 if (keys == 0 || i >= nb) return 0;
 142                 mask = nb - khint_t(1);
 143                 while (1) {
 144                         j = (j + khint_t(1)) & mask;
 145                         if (j == i || !__kh_used(used, j)) break; /* j==i only when the table is completely full */
 146                         k = __kh_h2b(Hash()(keys[j]), bits);
 147                         if ((j > i && (k <= i || k > j)) || (j < i && (k <= i && k > j)))
 148                                 keys[i] = keys[j], i = j;
 149                 }
 150                 __kh_set_unused(used, i);
 151                 --count;
 152                 return 1;
 153         }
 154 };
 155
 156 /***********
 157  * HashMap *
 158  ***********/
 159
 160 template<class KType, class VType>
 161 struct KHashMapBucket { KType key; VType val; };
 162
 163 template<class T, class Hash, typename khint_t>
 164 struct KHashMapHash { khint_t operator() (const T &a) const { return Hash()(a.key); } };
 165
 166 template<class T, class Eq>
 167 struct KHashMapEq { bool operator() (const T &a, const T &b) const { return Eq()(a.key, b.key); } };
 168
 169 template<class KType, class VType, class Hash, class Eq=std::equal_to<KType>, typename khint_t=uint32_t>
 170 class KHashMap : public KHashSet<KHashMapBucket<KType, VType>,
 171                 KHashMapHash<KHashMapBucket<KType, VType>, Hash, khint_t>,
 172                 KHashMapEq<KHashMapBucket<KType, VType>, Eq>, khint_t>
 173 {
 174         typedef KHashMapBucket<KType, VType> bucket_t;
 175         typedef KHashSet<bucket_t, KHashMapHash<bucket_t, Hash, khint_t>, KHashMapEq<bucket_t, Eq>, khint_t> hashset_t;
 176 public:
 177         khint_t get(const KType &key) const {
 178                 bucket_t t = { key, VType() };
 179                 return hashset_t::get(t);
 180         }
 181         khint_t put(const KType &key, int *absent) {
 182                 bucket_t t = { key, VType() };
 183                 return hashset_t::put(t, absent);
 184         }
 185         inline KType &key(khint_t i) { return hashset_t::key(i).key; }
 186         inline VType &value(khint_t i) { return hashset_t::key(i).val; }
 187         inline VType &operator[] (const KType &key) {
 188                 bucket_t t = { key, VType() };
 189                 return value(hashset_t::put(t));
 190         }
 191 };
 192
 193 /****************************
 194  * HashSet with cached hash *
 195  ****************************/
 196
 197 template<class KType, typename khint_t>
 198 struct KHashSetCachedBucket { KType key; khint_t hash; };
 199
 200 template<class T, typename khint_t>
 201 struct KHashCachedHash { khint_t operator() (const T &a) const { return a.hash; } };
 202
 203 template<class T, class Eq>
 204 struct KHashCachedEq { bool operator() (const T &a, const T &b) const { return a.hash == b.hash && Eq()(a.key, b.key); } };
 205
 206 template<class KType, class Hash, class Eq = std::equal_to<KType>, typename khint_t = uint32_t>
 207 class KHashSetCached : public KHashSet<KHashSetCachedBucket<KType, khint_t>,
 208                 KHashCachedHash<KHashSetCachedBucket<KType, khint_t>, khint_t>,
 209                 KHashCachedEq<KHashSetCachedBucket<KType, khint_t>, Eq>, khint_t>
 210 {
 211         typedef KHashSetCachedBucket<KType, khint_t> bucket_t;
 212         typedef KHashSet<bucket_t, KHashCachedHash<bucket_t, khint_t>, KHashCachedEq<bucket_t, Eq>, khint_t> hashset_t;
 213 public:
 214         khint_t get(const KType &key) const {
 215                 bucket_t t = { key, Hash()(key) };
 216                 return hashset_t::get(t);
 217         }
 218         khint_t put(const KType &key, int *absent) {
 219                 bucket_t t = { key, Hash()(key) };
 220                 return hashset_t::put(t, absent);
 221         }
 222         inline KType &key(khint_t i) { return hashset_t::key(i).key; }
 223 };
 224
 225 /****************************
 226  * HashMap with cached hash *
 227  ****************************/
 228
 229 template<class KType, class VType, typename khint_t>
 230 struct KHashMapCachedBucket { KType key; VType val; khint_t hash; };
 231
 232 template<class KType, class VType, class Hash, class Eq = std::equal_to<KType>, typename khint_t = uint32_t>
 233 class KHashMapCached : public KHashSet<KHashMapCachedBucket<KType, VType, khint_t>,
 234                 KHashCachedHash<KHashMapCachedBucket<KType, VType, khint_t>, khint_t>,
 235                 KHashCachedEq<KHashMapCachedBucket<KType, VType, khint_t>, Eq>, khint_t>
 236 {
 237         typedef KHashMapCachedBucket<KType, VType, khint_t> bucket_t;
 238         typedef KHashSet<bucket_t, KHashCachedHash<bucket_t, khint_t>, KHashCachedEq<bucket_t, Eq>, khint_t> hashset_t;
 239 public:
 240         khint_t get(const KType &key) const {
 241                 bucket_t t = { key, VType(), Hash()(key) };
 242                 return hashset_t::get(t);
 243         }
 244         khint_t put(const KType &key, int *absent) {
 245                 bucket_t t = { key, VType(), Hash()(key) };
 246                 return hashset_t::put(t, absent);
 247         }
 248         inline KType &key(khint_t i) { return hashset_t::key(i).key; }
 249         inline VType &value(khint_t i) { return hashset_t::key(i).val; }
 250         inline VType &operator[] (const KType &key) {
 251                 bucket_t t = { key, VType(), Hash()(key) };
 252                 return value(hashset_t::put(t));
 253         }
 254 };
 255
 256 }
 257
 258 #endif /* __AC_KHASHL_HPP */