SEGS  0.4.2
Super Entity Game Server
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
CoXHash.h
Go to the documentation of this file.
1 /*
2  * SEGS - Super Entity Game Server
3  * http://www.segs.io/
4  * Copyright (c) 2006 - 2018 SEGS Team (see Authors.txt)
5  * This software is licensed! (See License.txt for details)
6  */
7 
8 #pragma once
9 #include <cassert>
10 #include <string>
11 #include <vector>
12 #include <stdint.h>
13 #include <QtCore/QString>
14 #define mix(a,b,c) \
15 { \
16  a -= b; a -= c; a ^= (c>>13); \
17  b -= c; b -= a; b ^= (a<<8); \
18  c -= a; c -= b; c ^= (b>>13); \
19  a -= b; a -= c; a ^= (c>>12); \
20  b -= c; b -= a; b ^= (a<<16); \
21  c -= a; c -= b; c ^= (b>>5); \
22  a -= b; a -= c; a ^= (c>>3); \
23  b -= c; b -= a; b ^= (a<<10); \
24  c -= a; c -= b; c ^= (b>>15); \
25 }
26 template<class V>
28 {
29  static uint32_t hash(const uint8_t *k,uint32_t length,uint32_t initval)
30  {
31  uint32_t a,b,c,len;
32 
33  /* Set up the internal state */
34  len = length;
35  a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
36  c = initval; /* the previous hash value */
37  /*---------------------------------------- handle most of the key */
38  while (len >= 12)
39  {
40  a += (k[0] +((uint32_t)k[1]<<8) +((uint32_t)k[2]<<16) +((uint32_t)k[3]<<24));
41  b += (k[4] +((uint32_t)k[5]<<8) +((uint32_t)k[6]<<16) +((uint32_t)k[7]<<24));
42  c += (k[8] +((uint32_t)k[9]<<8) +((uint32_t)k[10]<<16)+((uint32_t)k[11]<<24));
43  mix(a,b,c);
44  k += 12; len -= 12;
45  }
46  /*------------------------------------- handle the last 11 bytes */
47  c += length;
48  switch(len) /* all the case statements fall through */
49  {
50  case 11: c+=((uint32_t)k[10]<<24);
51  case 10: c+=((uint32_t)k[9]<<16);
52  case 9 : c+=((uint32_t)k[8]<<8);
53  /* the first byte of c is reserved for the length */
54  case 8 : b+=((uint32_t)k[7]<<24);
55  case 7 : b+=((uint32_t)k[6]<<16);
56  case 6 : b+=((uint32_t)k[5]<<8);
57  case 5 : b+=k[4];
58  case 4 : a+=((uint32_t)k[3]<<24);
59  case 3 : a+=((uint32_t)k[2]<<16);
60  case 2 : a+=((uint32_t)k[1]<<8);
61  case 1 : a+=k[0];
62  /* case 0: nothing left to add */
63  }
64  mix(a,b,c);
65  return c;
66  }
67  uint32_t operator()(const V &val,uint32_t prev_val) const
68  {
69  return hash((const uint8_t *)&val,sizeof(V),prev_val);
70  }
71 };
72 //extern template struct JenkinsHash<std::string>;
73 #undef mix
74 
75 template<class KEY,class VALUE>
77 {
78 protected:
79  struct HashEntry
80  {
82  {
83  }
84  uint32_t key_hash;
86  VALUE stored_val;
87  uint32_t entry_flags;
88  };
89  std::vector<HashEntry> m_storage;
90 
91  size_t max_size;
92  size_t in_use;
93  uint32_t m_flags;
94 
96 public:
98  {}
99  virtual ~CoxHashCommon() {}
100  virtual uint32_t find_index(const KEY &key, uint32_t &index_tgt, uint32_t &key_tgt, bool a5) const=0;
101  virtual uint32_t next_size(uint32_t sz)=0;
102 
103  void resize(uint32_t new_size)
104  {
105  uint32_t entry_idx;
106  uint32_t prev_val;
107  std::vector<HashEntry> old_entries;
108  std::swap(old_entries,m_storage);
109  in_use=0;
110  m_storage.resize(size_t(this->next_size(new_size)));
111  for(size_t idx=0; idx<old_entries.size(); ++idx)
112  {
113  if(old_entries[idx].key_hash==0) // || 0==old_entries[idx].entry_flags&1
114  continue;
115  if(find_index(old_entries[idx].stored_key,entry_idx,prev_val,1)==2)
116  assert(0);
117  m_storage[entry_idx] = old_entries[idx];
118  m_storage[entry_idx].key_hash = prev_val;
119  in_use++;
120  }
121  }
122  HashEntry *insert_entry(const KEY &k,VALUE v)
123  {
124  size_t watermark = (m_storage.size()*3)/4; // when we are filled upt 75% of our capacity
125  uint32_t entry_idx=0;
126  uint32_t prev_val=0;
127  if(in_use>=watermark || in_use>=m_storage.size())
128  {
129  uint32_t factor=1;
130  if ( in_use >= watermark || in_use >= m_storage.size() - 1 )
131  factor=2;
132  resize(factor*m_storage.size());
133  }
134  if(this->find_index(k,entry_idx,prev_val,true))
135  {
136  return 0;
137  }
138  m_storage[entry_idx].stored_key = k;
139  m_storage[entry_idx].stored_val = v;
140  m_storage[entry_idx].key_hash = prev_val;
141  in_use++;
142  return &m_storage[entry_idx];
143  }
144  const KEY *key_for_idx(int idx) const
145  {
146  idx-=1;
147  if(idx >= 0 && idx < (int)m_storage.size())
148  if(m_storage[idx].key_hash!=0)
149  return &m_storage[idx].stored_key;
150  return 0;
151  }
152  void init(uint32_t sz,uint32_t flags)
153  {
154  m_flags=flags;
155  in_use=0;
156  m_storage.resize(size_t(next_size(sz))); // reserve hash map entries
157  }
158 };
159 template<class VALUE>
160 class CoXHashMap : public CoxHashCommon<QString,VALUE>
161 {
162  enum{
163  HAS_KEY_NAMES = 1,
164  SKIP_CLASHES = 4,
165  CHECK_COLLISIONS = 8,
166  SINGLE_BYTE = 0x20,
167  };
169 public:
171  uint32_t find_index(const QString &key, uint32_t &index_tgt, uint32_t &key_tgt, bool a5) const;
172  uint32_t next_size(uint32_t sz)
173  {
174  if(sz==0)
175  return 0;
176  uint32_t bit=1U<<31;
177  int highest_bit;
178  for(highest_bit=31; highest_bit>=0; --highest_bit)
179  {
180  if(sz&bit) // is the bit set ?
181  break;
182  bit>>=1;
183  }
184  if(sz!=bit) // size is not power of 2
185  bit<<=1;
186  return bit;
187  }
188 };
190 {
191  bool operator()(uint32_t a,uint32_t b)
192  {
193  return a!=b;
194  }
195 };
196 
197 template<class KEY,class VALUE,class COMPARE_FUNCTOR>
198 class CoXGenericHashMap : public CoxHashCommon<KEY,VALUE>
199 {
200 protected:
201  static COMPARE_FUNCTOR comp;
202 public:
203  CoXGenericHashMap() = default;
204  uint32_t next_size(uint32_t sz)
205  {
206  size_t idx;
207  static uint32_t prime_sizes[] = {
208  11, 19, 37, 73, 109, 163, 251, 367,
209  557, 823, 1237, 1861, 2777, 4177, 6247, 9371,
210  14057, 21089, 31627, 47431, 71143, 106721, 160073, 240101,
211  360163, 540217, 810343, 1215497,1823231,2734867,4102283,6153409,
212  9230113,13845163,16313537,32452867
213  };
214  for(idx=0; idx<36; ++idx)
215  if(prime_sizes[idx]>=sz)
216  return prime_sizes[idx];
217  return prime_sizes[35];
218  }
219  void init(uint32_t sz)
220  {
221  if(sz>0)
222  {
223  this->m_storage.resize(size_t(next_size(sz))); // reserve hash map entries
224  }
225  else
226  {
227  this->m_storage.resize(32);
228  }
229  }
230  uint32_t find_index(const KEY &needle,uint32_t &entry_idx,uint32_t &prev_val_out,bool a5) const;
231 };
232 
Definition: CoXHash.h:198
size_t in_use
Definition: CoXHash.h:92
uint32_t find_index(const QString &key, uint32_t &index_tgt, uint32_t &key_tgt, bool a5) const
Definition: CoXHash.cpp:28
HashEntry * insert_entry(const KEY &k, VALUE v)
Definition: CoXHash.h:122
CoXGenericHashMap< uint32_t, uint32_t, IntCompare > ColorHash
Definition: CoXHash.h:234
uint32_t m_flags
Definition: CoXHash.h:93
CoXGenericHashMap()=default
virtual uint32_t next_size(uint32_t sz)=0
Keybind & k
Definition: keybind_serializers.cpp:197
uint32_t next_size(uint32_t sz)
Definition: CoXHash.h:172
Definition: CoXHash.h:160
KEY stored_key
Definition: CoXHash.h:85
CoXHashMap< QString > StringHash
Definition: CoXHash.h:233
HashEntry()
Definition: CoXHash.h:81
uint32_t next_size(uint32_t sz)
Definition: CoXHash.h:204
Definition: CoXHash.h:189
virtual uint32_t find_index(const KEY &key, uint32_t &index_tgt, uint32_t &key_tgt, bool a5) const =0
void init(uint32_t sz, uint32_t flags)
Definition: CoXHash.h:152
void init(uint32_t sz)
Definition: CoXHash.h:219
VALUE stored_val
Definition: CoXHash.h:86
uint32_t operator()(const V &val, uint32_t prev_val) const
Definition: CoXHash.h:67
static COMPARE_FUNCTOR comp
Definition: CoXHash.h:201
std::vector< HashEntry > m_storage
Definition: CoXHash.h:89
Definition: CoXHash.h:76
void resize(uint32_t new_size)
Definition: CoXHash.h:103
bool operator()(uint32_t a, uint32_t b)
Definition: CoXHash.h:191
virtual ~CoxHashCommon()
Definition: CoXHash.h:99
size_t max_size
Definition: CoXHash.h:91
CoXHashMap()
Definition: CoXHash.h:170
#define mix(a, b, c)
Definition: CoXHash.h:14
Definition: CoXHash.h:27
Definition: CoXHash.h:79
CoxHashCommon()
Definition: CoXHash.h:97
uint32_t key_hash
Definition: CoXHash.h:84
static uint32_t hash(const uint8_t *k, uint32_t length, uint32_t initval)
Definition: CoXHash.h:29
uint32_t find_index(const KEY &needle, uint32_t &entry_idx, uint32_t &prev_val_out, bool a5) const
Definition: CoXHash.cpp:83
const KEY * key_for_idx(int idx) const
Definition: CoXHash.h:144
static JenkinsHash< KEY > hash
Definition: CoXHash.h:95
uint32_t entry_flags
Definition: CoXHash.h:87