Inexor
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
cube_hash.hpp
Go to the documentation of this file.
1 
7 #pragma once
8 
12 #include <string.h>
13 
14 static inline uint memhash(const void *ptr, int len)
15 {
16  const uchar *data = (const uchar *)ptr;
17  uint h = 5381;
18  for(int i= 0; i<len; i++) h = ((h<<5)+h)^data[i];
19  return h;
20 }
21 
22 static inline uint hthash(const stringslice &s) { return memhash(s.str, s.len); }
23 
24 static inline bool htcmp(const stringslice &x, const char *y)
25 {
26  return x.len == (int)strlen(y) && !memcmp(x.str, y, x.len);
27 }
28 
29 static inline uint hthash(int key)
30 {
31  return key;
32 }
33 
35 static inline bool htcmp(int x, int y)
36 {
37  return x==y;
38 }
39 
40 // simple bernstein hashing algorithm
41 // invented by Dan Bernstein
42 static inline uint hthash(const char *key)
43 {
44  uint h = 5381;
45  for(int i = 0, k; (k = key[i]); i++) h = ((h<<5)+h)^k;
46  return h;
47 }
48 
49 static inline bool htcmp(const char *x, const char *y)
50 {
51  return !strcmp(x, y);
52 }
53 
54 template<class H, class E, class K, class T> struct hashbase
55 {
56  typedef E elemtype;
57  typedef K keytype;
58  typedef T datatype;
59 
60  enum { CHUNKSIZE = 64 };
61 
62  struct chain
63  {
64  E elem;
66  };
67  struct chainchunk
68  {
71  };
72 
73  int size;
74  int numelems;
75  chain **chains;
76 
77  chainchunk *chunks;
78  chain *unused;
79 
80  enum { DEFAULTSIZE = 1<<10 };
81 
83  : size(size)
84  {
85  numelems = 0;
86  chunks = nullptr;
87  unused = nullptr;
88  chains = new chain *[size];
89  memset(chains, 0, size*sizeof(chain *));
90  }
91 
93  {
94  delete[] chains;
95  chains = nullptr;
96  deletechunks();
97  }
98 
99  chain *insert(uint h)
100  {
101  if(!unused)
102  {
103  chainchunk *chunk = new chainchunk;
104  chunk->next = chunks;
105  chunks = chunk;
106  loopi(CHUNKSIZE-1) chunk->chains[i].next = &chunk->chains[i+1];
107  chunk->chains[CHUNKSIZE-1].next = unused;
108  unused = chunk->chains;
109  }
110  chain *c = unused;
111  unused = unused->next;
112  c->next = chains[h];
113  chains[h] = c;
114  numelems++;
115  return c;
116  }
117 
118  template<class U>
119  T &insert(uint h, const U &key)
120  {
121  chain *c = insert(h);
122  H::setkey(c->elem, key);
123  return H::getdata(c->elem);
124  }
125 
126 #define HTFIND(success, fail) \
127  uint h = hthash(key)&(this->size-1); \
128  for(chain *c = this->chains[h]; c; c = c->next) \
129  { \
130  if(htcmp(key, H::getkey(c->elem))) return success H::getdata(c->elem); \
131  } \
132  return (fail);
133 
134  template<class U>
135  T *access(const U &key)
136  {
137  HTFIND(&, NULL);
138  }
139 
140  template<class U, class V>
141  T &access(const U &key, const V &elem)
142  {
143  HTFIND(, insert(h, key) = elem);
144  }
145 
146  template<class U>
147  T &operator[](const U &key)
148  {
149  HTFIND(, insert(h, key));
150  }
151 
152  template<class U>
153  T &find(const U &key, T &notfound)
154  {
155  HTFIND(, notfound);
156  }
157 
158  template<class U>
159  const T &find(const U &key, const T &notfound)
160  {
161  HTFIND(, notfound);
162  }
163 
164  template<class U>
165  bool remove(const U &key)
166  {
167  uint h = hthash(key)&(size-1);
168  for(chain **p = &chains[h], *c = chains[h]; c; p = &c->next, c = c->next)
169  {
170  if(htcmp(key, H::getkey(c->elem)))
171  {
172  *p = c->next;
173  c->elem.~E();
174  new (&c->elem) E;
175  c->next = unused;
176  unused = c;
177  numelems--;
178  return true;
179  }
180  }
181  return false;
182  }
183 
185  {
186  for(chainchunk *nextchunk; chunks; chunks = nextchunk)
187  {
188  nextchunk = chunks->next;
189  delete chunks;
190  }
191  }
192 
193  void clear()
194  {
195  if(!numelems) return;
196  memset(chains, 0, size*sizeof(chain *));
197  numelems = 0;
198  unused = nullptr;
199  deletechunks();
200  }
201 
202  static inline chain *enumnext(void *i) { return ((chain *)i)->next; }
203  static inline K &enumkey(void *i) { return H::getkey(((chain *)i)->elem); }
204  static inline T &enumdata(void *i) { return H::getdata(((chain *)i)->elem); }
205 };
206 
207 template<class T> struct hashset : hashbase<hashset<T>, T, T, T>
208 {
209  typedef hashbase<hashset<T>, T, T, T> basetype;
210 
212 
213  static inline const T &getkey(const T &elem) { return elem; }
214  static inline T &getdata(T &elem) { return elem; }
215  template<class K> static inline void setkey(T &elem, const K &key) {}
216 
217  template<class V>
218  T &add(const V &elem)
219  {
220  return basetype::access(elem, elem);
221  }
222 };
223 
224 template<class T> struct hashnameset : hashbase<hashnameset<T>, T, const char *, T>
225 {
226  typedef hashbase<hashnameset<T>, T, const char *, T> basetype;
227 
229 
230  template<class U> static inline const char *getkey(const U &elem) { return elem.name; }
231  template<class U> static inline const char *getkey(U *elem) { return elem->name; }
232  static inline T &getdata(T &elem) { return elem; }
233  template<class K> static inline void setkey(T &elem, const K &key) {}
234 
235  template<class V>
236  T &add(const V &elem)
237  {
238  return basetype::access(getkey(elem), elem);
239  }
240 };
241 
242 template<class K, class T> struct hashtableentry
243 {
244  K key;
245  T data;
246 };
247 
248 template<class K, class T> struct hashtable : hashbase<hashtable<K, T>, hashtableentry<K, T>, K, T>
249 {
251  typedef typename basetype::elemtype elemtype;
252 
254 
255  static inline K &getkey(elemtype &elem) { return elem.key; }
256  static inline T &getdata(elemtype &elem) { return elem.data; }
257  template<class U> static inline void setkey(elemtype &elem, const U &key) { elem.key = key; }
258 };
259 
260 #define enumeratekt(ht,k,e,t,f,b) loopi((ht).size) for(void *ec = (ht).chains[i]; ec;) { k &e = (ht).enumkey(ec); t &f = (ht).enumdata(ec); ec = (ht).enumnext(ec); b; }
261 #define enumerate(ht,t,e,b) loopi((ht).size) for(void *ec = (ht).chains[i]; ec;) { t &e = (ht).enumdata(ec); ec = (ht).enumnext(ec); b; }
262 
Definition: cube_hash.hpp:54
K key
Definition: cube_hash.hpp:244
hashbase< hashset< T >, T, T, T > basetype
Definition: cube_hash.hpp:209
T & access(const U &key, const V &elem)
Definition: cube_hash.hpp:141
hashtable(int size=basetype::DEFAULTSIZE)
Definition: cube_hash.hpp:253
hashnameset(int size=basetype::DEFAULTSIZE)
Definition: cube_hash.hpp:228
hashbase< hashnameset< T >, T, const char *, T > basetype
Definition: cube_hash.hpp:226
unsigned int uint
Definition: cube_types.hpp:9
static K & enumkey(void *i)
Definition: cube_hash.hpp:203
T & operator[](const U &key)
Definition: cube_hash.hpp:147
void clear()
Definition: cube_hash.hpp:193
Definition: cube_hash.hpp:62
Definition: cube_hash.hpp:60
static T & getdata(elemtype &elem)
Definition: cube_hash.hpp:256
static const char * getkey(const U &elem)
Definition: cube_hash.hpp:230
E elemtype
Definition: cube_hash.hpp:56
E elem
Definition: cube_hash.hpp:64
static uint memhash(const void *ptr, int len)
Legacy Hashing algorithms and hashmap-implementation.
Definition: cube_hash.hpp:14
T & insert(uint h, const U &key)
Definition: cube_hash.hpp:119
T datatype
Definition: cube_hash.hpp:58
static void setkey(T &elem, const K &key)
Definition: cube_hash.hpp:215
static const char * getkey(U *elem)
Definition: cube_hash.hpp:231
Definition: cube_hash.hpp:207
const char * str
Definition: cube_tools.hpp:78
T & add(const V &elem)
Definition: cube_hash.hpp:218
Definition: cube_hash.hpp:80
hashset(int size=basetype::DEFAULTSIZE)
Definition: cube_hash.hpp:211
static const T & getkey(const T &elem)
Definition: cube_hash.hpp:213
static T & enumdata(void *i)
Definition: cube_hash.hpp:204
static bool htcmp(const stringslice &x, const char *y)
Definition: cube_hash.hpp:24
else loopi(numargs)
Definition: command.cpp:3019
#define NULL
Definition: cube_types.hpp:35
static void setkey(T &elem, const K &key)
Definition: cube_hash.hpp:233
int size
Definition: cube_hash.hpp:73
Definition: cube_hash.hpp:242
basetype::elemtype elemtype
Definition: cube_hash.hpp:251
const T & find(const U &key, const T &notfound)
Definition: cube_hash.hpp:159
static T & getdata(T &elem)
Definition: cube_hash.hpp:214
T & find(const U &key, T &notfound)
Definition: cube_hash.hpp:153
static T & getdata(T &elem)
Definition: cube_hash.hpp:232
chainchunk * chunks
Definition: cube_hash.hpp:77
static K & getkey(elemtype &elem)
Definition: cube_hash.hpp:255
hashbase< hashtable< K, T >, hashtableentry< K, T >, K, T > basetype
Definition: cube_hash.hpp:250
hashbase(int size=DEFAULTSIZE)
Definition: cube_hash.hpp:82
Definition: cube_tools.hpp:76
K keytype
Definition: cube_hash.hpp:57
unsigned char uchar
Basic type definitions.
Definition: cube_types.hpp:7
static void setkey(elemtype &elem, const U &key)
Definition: cube_hash.hpp:257
T data
Definition: cube_hash.hpp:245
GLuint GLuint GLintptr GLsizeiptr size
Definition: glexts.hpp:412
T & add(const V &elem)
Definition: cube_hash.hpp:236
static uint hthash(const stringslice &s)
Definition: cube_hash.hpp:22
chain ** chains
Definition: cube_hash.hpp:75
chain * next
Definition: cube_hash.hpp:65
~hashbase()
Definition: cube_hash.hpp:92
T * access(const U &key)
Definition: cube_hash.hpp:135
int numelems
Definition: cube_hash.hpp:74
static chain * enumnext(void *i)
Definition: cube_hash.hpp:202
chain * insert(uint h)
Definition: cube_hash.hpp:99
chain chains[CHUNKSIZE]
Definition: cube_hash.hpp:69
chain * unused
Definition: cube_hash.hpp:78
unsigned long long int chunk
Definition: crypto.cpp:26
Definition: cube_hash.hpp:67
Definition: cube_hash.hpp:224
int len
Definition: cube_tools.hpp:79
chainchunk * next
Definition: cube_hash.hpp:70
Definition: cube_hash.hpp:248
#define HTFIND(success, fail)
Definition: cube_hash.hpp:126
void deletechunks()
Definition: cube_hash.hpp:184