SystemC  2.3.1
Accellera SystemC proof-of-concept library
sc_hash.h
Go to the documentation of this file.
1 /*****************************************************************************
2 
3  The following code is derived, directly or indirectly, from the SystemC
4  source code Copyright (c) 1996-2014 by all Contributors.
5  All Rights reserved.
6 
7  The contents of this file are subject to the restrictions and limitations
8  set forth in the SystemC Open Source License (the "License");
9  You may not use this file except in compliance with such restrictions and
10  limitations. You may obtain instructions on how to receive a copy of the
11  License at http://www.accellera.org/. Software distributed by Contributors
12  under the License is distributed on an "AS IS" basis, WITHOUT WARRANTY OF
13  ANY KIND, either express or implied. See the License for the specific
14  language governing rights and limitations under the License.
15 
16  *****************************************************************************/
17 
18 /*****************************************************************************
19 
20  sc_hash.cpp -- Implementation of a chained hash table with MTF
21  (move-to-front).
22 
23  Original Author: Stan Y. Liao, Synopsys, Inc.
24 
25  CHANGE LOG AT END OF FILE
26  *****************************************************************************/
27 
28 #ifndef SC_HASH_H
29 #define SC_HASH_H
30 
31 
32 namespace sc_core {
33 
34 extern unsigned default_int_hash_fn(const void*);
35 extern unsigned default_ptr_hash_fn(const void*);
36 extern unsigned default_str_hash_fn(const void*);
37 
38 class sc_phash_elem;
39 class sc_phash_base_iter;
40 template<class K, class C> //template class
41 class sc_pdhash_iter; //decl. -- Amit
42 
45 extern const double PHASH_DEFAULT_GROW_FACTOR;
46 const bool PHASH_DEFAULT_REORDER_FLAG = true;
47 
49  friend class sc_phash_base_iter;
50 
52 
53 public:
54  typedef unsigned (*hash_fn_t)(const void*);
55  typedef int (*cmpr_fn_t)(const void*, const void*);
56 
57 protected:
59  int num_bins;
63  double grow_factor;
64 
65  sc_phash_elem** bins;
66 
69 
70  void rehash();
71  unsigned do_hash(const void* key) const { return (*hash)(key) % num_bins; }
72 
73  sc_phash_elem* add_direct(void* key, void* contents, unsigned hash_val);
74  sc_phash_elem* find_entry_c(unsigned hv, const void* k, sc_phash_elem*** plast);
75  sc_phash_elem* find_entry_q(unsigned hv, const void* k, sc_phash_elem*** plast);
76  sc_phash_elem* find_entry(unsigned hv, const void* k, sc_phash_elem*** plast=0) const
77  {
78  /* Got rid of member func. pointer and replaced with if-else */
79  /* Amit (5/14/99) */
80  if( cmpr == 0 )
81  return ((sc_phash_base*)this)->find_entry_q( hv, k, plast );
82  else
83  return ((sc_phash_base*)this)->find_entry_c( hv, k, plast );
84  }
85 
86 public:
87  sc_phash_base( void* def = 0,
89  int density = PHASH_DEFAULT_MAX_DENSITY,
90  double grow = PHASH_DEFAULT_GROW_FACTOR,
91  bool reorder = PHASH_DEFAULT_REORDER_FLAG,
93  cmpr_fn_t cmpr_fn = 0 );
95 
96  void set_cmpr_fn(cmpr_fn_t);
97  void set_hash_fn(hash_fn_t);
98 
99  bool empty() const { return (num_entries == 0); }
100  unsigned count() const { return num_entries; }
101 
102  void erase();
103  void erase(void (*kfree)(void*));
104  void copy( const sc_phash_base* );
105  void copy( const sc_phash_base& b ) { copy(&b); }
106  void copy( const sc_phash_base& b, void* (*kdup)(const void*), void (*kfree)(void*));
107  int insert( void* k, void* c );
108  int insert( void* k ) { return insert(k, default_value); }
109  int insert( void* k, void* c, void* (*kdup)(const void*) );
110  int insert_if_not_exists(void* k, void* c);
112  int insert_if_not_exists(void* k, void* c, void* (*kdup)(const void*));
113  int remove(const void* k);
114  int remove(const void* k, void** pk, void** pc);
115  int remove(const void* k, void (*kfree)(void*));
116  int remove_by_contents(const void* c);
117  int remove_by_contents(bool (*predicate)(const void*, void*), void* arg);
118  int remove_by_contents(const void* c, void (*kfree)(void*));
119  int remove_by_contents(bool (*predicate)(const void*, void*), void* arg, void (*kfree)(void*));
120  int lookup(const void* k, void** pc) const;
121  bool contains(const void* k) const { return (lookup(k, 0) != 0); }
122  void* operator[](const void* key) const;
123 };
124 
126 protected:
128  sc_phash_elem* entry;
129  sc_phash_elem* next;
130  sc_phash_elem** last;
131  int index;
132 
133 public:
134  void reset(sc_phash_base* t);
135  void reset(sc_phash_base& t) { reset(&t); }
136 
138  : table(t), entry(0), next(0), last(0), index(0)
139  { reset(t); }
141  : table(&t), entry(0), next(0), last(0), index(0)
142  { reset(t); }
144 
145  bool empty() const;
146  void step();
147  void operator++(int) { step(); }
148  void remove();
149  void remove(void (*kfree)(void*));
150  void* key() const;
151  void* contents() const;
152  void* set_contents(void* c);
153 };
154 
155 template< class K, class C >
157 
158 template< class K, class C >
159 class sc_phash : public sc_phash_base {
160  friend class sc_phash_iter<K,C>;
161 
162 public:
164 
165  sc_phash( C def = (C) 0,
167  int density = PHASH_DEFAULT_MAX_DENSITY,
168  double grow = PHASH_DEFAULT_GROW_FACTOR,
169  bool reorder = PHASH_DEFAULT_REORDER_FLAG,
170  hash_fn_t hash_fn = default_ptr_hash_fn,
171  cmpr_fn_t cmpr_fn = 0 )
172  : sc_phash_base((void*) def, size, density, grow, reorder, hash_fn, cmpr_fn) { }
173  ~sc_phash() { }
174 
175  void copy(const sc_phash<K,C>* b) { sc_phash_base::copy(b); }
176  void copy(const sc_phash<K,C>& b) { sc_phash_base::copy(b); }
177  void copy(const sc_phash<K,C>& b, void* (*kdup)(const void*), void (*kfree)(void*)) { sc_phash_base::copy(b, kdup, kfree); }
178 
179  int insert(K k, C c) { return sc_phash_base::insert((void*) k, (void*) c); }
180  int insert(K k) { return sc_phash_base::insert((void*) k, default_value); }
181  int insert(K k, C c, void* (*kdup)(const void*)) { return sc_phash_base::insert((void*) k, (void*) c, kdup); }
182  int insert_if_not_exists(K k, C c)
183  {
184  return sc_phash_base::insert_if_not_exists((void*) k, (void*) c);
185  }
187  {
189  }
190  int insert_if_not_exists(K k, C c, void* (*kdup)(const void*))
191  {
192  return sc_phash_base::insert_if_not_exists((void*) k, (void*) c, kdup);
193  }
194  int remove(K k) { return sc_phash_base::remove((const void*) k); }
195  int remove(K k, K* pk, C* pc)
196  {
197  return sc_phash_base::remove((const void*) k, (void**) pk, (void**) pc);
198  }
199  int remove(K k, void (*kfree)(void*))
200  {
201  return sc_phash_base::remove((const void*) k, kfree);
202  }
204  {
205  return sc_phash_base::remove_by_contents((const void*) c);
206  }
207  int remove_by_contents(bool (*predicate)(const void*, void*), void* arg)
208  {
209  return sc_phash_base::remove_by_contents(predicate, arg);
210  }
211  int remove_by_contents(const void* c, void (*kfree)(void*))
212  {
213  return sc_phash_base::remove_by_contents(c, kfree);
214  }
215  int remove_by_contents(bool (*predicate)(const void*, void*), void* arg, void (*kfree)(void*))
216  {
217  return sc_phash_base::remove_by_contents(predicate, arg, kfree);
218  }
219  int lookup(K k, C* pc) const
220  {
221  return sc_phash_base::lookup((const void*) k, (void**) pc);
222  }
223  bool contains(K k) const
224  {
225  return sc_phash_base::contains((const void*) k);
226  }
227  C operator[](K k) const
228  {
229  return (C) sc_phash_base::operator[]((const void*) k);
230  }
231 };
232 
233 
234 template< class K, class C >
235 class sc_phash_iter : public sc_phash_base_iter {
236 public:
240 
243 
244  K key() const { return (K) sc_phash_base_iter::key(); }
245  C contents() const { return (C) sc_phash_base_iter::contents(); }
247  {
248  return (C) sc_phash_base_iter::set_contents((void*) c);
249  }
250 };
251 
252 
253 
254 
255 
256 template< class K, class C >
257 class sc_pdhash : public sc_phash_base {
258  friend class sc_pdhash_iter<K,C>;
259 
260 private:
261  void* (*kdup)(const void*); //eliminated braces around void* -- Amit
262  void (*kfree)(void*);
263 
264 public:
266  sc_pdhash( C def = (C) 0,
268  int density = PHASH_DEFAULT_MAX_DENSITY,
269  double grow = PHASH_DEFAULT_GROW_FACTOR,
270  bool reorder = PHASH_DEFAULT_REORDER_FLAG,
271  hash_fn_t hash_fn = (hash_fn_t) 0, // defaults added --
272  cmpr_fn_t cmpr_fn = (cmpr_fn_t) 0, // Amit
273  void* (*kdup_fn)(const void*) = 0,
274  void (*kfree_fn)(void*) = 0 )
275  : sc_phash_base((void*) def, size, density, grow, reorder, hash_fn, cmpr_fn)
276  {
277  kdup = kdup_fn;
278  kfree = kfree_fn;
279  }
281  {
282  erase();
283  }
284  void erase()
285  {
286  sc_phash_base::erase(kfree);
287  }
288  void copy(const sc_pdhash<K,C>& b) { sc_phash_base::copy(b, kdup, kfree); }
289  int insert(K k, C c) { return sc_phash_base::insert((void*) k, (void*) c, kdup); }
290  int insert(K k) { return sc_phash_base::insert((void*) k, default_value, kdup); }
291  int insert_if_not_exists(K k, C c)
292  {
293  return sc_phash_base::insert_if_not_exists((void*) k, (void*) c, kdup);
294  }
296  {
297  return sc_phash_base::insert_if_not_exists((void*) k, default_value, kdup);
298  }
299  int remove(K k) { return sc_phash_base::remove((const void*) k, kfree); }
300  int remove(K k, K* pk, C* pc)
301  {
302  return sc_phash_base::remove((const void*) k, (void**) pk, (void**) pc);
303  }
305  {
306  return sc_phash_base::remove_by_contents((const void*) c, kfree);
307  }
308  int remove_by_contents(bool (*predicate)(const void*, void*), void* arg)
309  {
310  return sc_phash_base::remove_by_contents(predicate, arg, kfree);
311  }
312  int lookup(K k, C* pc) const
313  {
314  return sc_phash_base::lookup((const void*) k, (void**) pc);
315  }
316  bool contains(K k) const
317  {
318  return sc_phash_base::contains((const void*) k);
319  }
320  C operator[](K k) const
321  {
322  return (C) sc_phash_base::operator[]((const void*) k);
323  }
324 };
325 
326 template< class K, class C >
327 class sc_pdhash_iter : public sc_phash_base_iter {
328 public:
332 
335 
336  void remove() { sc_phash_base_iter::remove(((sc_pdhash<K,C>*) table)->kfree); }
337  K key() const { return (K) sc_phash_base_iter::key(); }
338  C contents() const { return (C) sc_phash_base_iter::contents(); }
340  {
341  return (C) sc_phash_base_iter::set_contents((void*) c);
342  }
343 };
344 
345 extern int sc_strhash_cmp( const void*, const void* );
346 extern void sc_strhash_kfree(void*);
347 extern void* sc_strhash_kdup(const void*);
348 
349 template< class C > // template class decl.
350 class sc_strhash_iter; // --Amit
351 
352 template< class C >
353 class sc_strhash : public sc_phash_base {
354  friend class sc_strhash_iter<C>;
355 
356 public:
358 
359  sc_strhash( C def = (C) 0,
361  int density = PHASH_DEFAULT_MAX_DENSITY,
362  double grow = PHASH_DEFAULT_GROW_FACTOR,
363  bool reorder = PHASH_DEFAULT_REORDER_FLAG,
364  unsigned (*hash_fn)(const void*) = default_str_hash_fn,
365  int (*cmpr_fn)(const void*, const void*) = sc_strhash_cmp )
366  : sc_phash_base((void*) def, size, density, grow, reorder, hash_fn, cmpr_fn)
367  {
368 
369  }
371  {
372  erase();
373  }
374 
378 
379  int insert(char* k, C c) { return sc_phash_base::insert((void*) k, (void*) c, sc_strhash_kdup); }
380  int insert(char* k) { return sc_phash_base::insert((void*) k, default_value, sc_strhash_kdup); }
381  int insert_if_not_exists(char* k, C c)
382  {
383  return sc_phash_base::insert_if_not_exists((void*) k, (void*) c, sc_strhash_kdup);
384  }
385  int insert_if_not_exists(char* k)
386  {
388  }
389  int remove(const char* k) { return sc_phash_base::remove((const void*) k, sc_strhash_kfree); }
390  int remove(const char* k, char** pk, C* pc)
391  {
392  return sc_phash_base::remove((const void*) k, (void**) pk, (void**) pc);
393  }
395  {
396  return sc_phash_base::remove_by_contents((const void*) c, sc_strhash_kfree);
397  }
398  int remove_by_contents(bool (*predicate)(const void*, void*), void* arg)
399  {
400  return sc_phash_base::remove_by_contents(predicate, arg, sc_strhash_kfree);
401  }
402  int lookup(const char* k, C* pc) const
403  {
404  return sc_phash_base::lookup((const void*) k, (void** )pc);
405  }
406  bool contains(const char* k) const
407  {
408  return sc_phash_base::contains((const void*) k);
409  }
410  C operator[](const char* k) const
411  {
412  return (C) sc_phash_base::operator[]((const void*) k);
413  }
414 };
415 
416 template<class C>
417 class sc_strhash_iter : public sc_phash_base_iter {
418 public:
422 
425 
427  const char* key() { return (const char*) sc_phash_base_iter::key(); }
430  {
431  return (C) sc_phash_base_iter::set_contents((void*) c);
432  }
433 };
434 
435 } // namespace sc_core
436 
437 // $Log: sc_hash.h,v $
438 // Revision 1.5 2011/08/29 18:04:32 acg
439 // Philipp A. Hartmann: miscellaneous clean ups.
440 //
441 // Revision 1.4 2011/08/26 20:46:16 acg
442 // Andy Goodrich: moved the modification log to the end of the file to
443 // eliminate source line number skew when check-ins are done.
444 //
445 // Revision 1.3 2011/08/24 22:05:56 acg
446 // Torsten Maehne: initialization changes to remove warnings.
447 //
448 // Revision 1.2 2011/02/18 20:38:43 acg
449 // Andy Goodrich: Updated Copyright notice.
450 //
451 // Revision 1.1.1.1 2006/12/15 20:20:06 acg
452 // SystemC 2.3
453 //
454 // Revision 1.3 2006/01/13 18:53:10 acg
455 // Andy Goodrich: Added $Log command so that CVS comments are reproduced in
456 // the source.
457 
458 #endif
C operator[](K k) const
Definition: sc_hash.h:320
void * set_contents(void *c)
sc_phash_iter(sc_phash< K, C > *t)
Definition: sc_hash.h:237
sc_phash_iter< K, C > iterator
Definition: sc_hash.h:163
unsigned default_int_hash_fn(const void *)
int insert_if_not_exists(void *k, void *c)
int remove(const void *k)
sc_pdhash_iter(sc_pdhash< K, C > *t)
Definition: sc_hash.h:329
bool contains(const void *k) const
Definition: sc_hash.h:121
C operator[](K k) const
Definition: sc_hash.h:227
unsigned default_str_hash_fn(const void *)
bool contains(const char *k) const
Definition: sc_hash.h:406
sc_phash(C def=(C) 0, int size=PHASH_DEFAULT_INIT_TABLE_SIZE, int density=PHASH_DEFAULT_MAX_DENSITY, double grow=PHASH_DEFAULT_GROW_FACTOR, bool reorder=PHASH_DEFAULT_REORDER_FLAG, hash_fn_t hash_fn=default_ptr_hash_fn, cmpr_fn_t cmpr_fn=0)
Definition: sc_hash.h:165
unsigned do_hash(const void *key) const
Definition: sc_hash.h:71
void reset(sc_phash< K, C > *t)
Definition: sc_hash.h:241
void set_hash_fn(hash_fn_t)
sc_pdhash_iter(sc_pdhash< K, C > &t)
Definition: sc_hash.h:330
bool empty() const
Definition: sc_hash.h:99
int lookup(const void *k, void **pc) const
void copy(const sc_strhash< C > &b)
Definition: sc_hash.h:377
int insert(void *k)
Definition: sc_hash.h:108
int insert(K k, C c, void *(*kdup)(const void *))
Definition: sc_hash.h:181
int remove_by_contents(C c)
Definition: sc_hash.h:304
sc_phash_base * table
Definition: sc_hash.h:127
uint64 const sc_uint_base int b
Definition: sc_fxval.h:1003
int remove_by_contents(bool(*predicate)(const void *, void *), void *arg)
Definition: sc_hash.h:398
sc_phash_elem * find_entry_c(unsigned hv, const void *k, sc_phash_elem ***plast)
void copy(const sc_phash_base *)
void copy(const sc_strhash< C > *b)
Definition: sc_hash.h:376
sc_strhash_iter(sc_strhash< C > *t)
Definition: sc_hash.h:419
int insert_if_not_exists(K k, C c)
Definition: sc_hash.h:182
int remove_by_contents(bool(*predicate)(const void *, void *), void *arg, void(*kfree)(void *))
Definition: sc_hash.h:215
int insert(K k)
Definition: sc_hash.h:180
void * sc_strhash_kdup(const void *)
int(* cmpr_fn_t)(const void *, const void *)
Definition: sc_hash.h:55
const int PHASH_DEFAULT_INIT_TABLE_SIZE
Definition: sc_hash.h:44
void reset(sc_pdhash< K, C > &t)
Definition: sc_hash.h:334
sc_strhash(C def=(C) 0, int size=PHASH_DEFAULT_INIT_TABLE_SIZE, int density=PHASH_DEFAULT_MAX_DENSITY, double grow=PHASH_DEFAULT_GROW_FACTOR, bool reorder=PHASH_DEFAULT_REORDER_FLAG, unsigned(*hash_fn)(const void *)=default_str_hash_fn, int(*cmpr_fn)(const void *, const void *)=sc_strhash_cmp)
Definition: sc_hash.h:359
sc_phash_elem * find_entry(unsigned hv, const void *k, sc_phash_elem ***plast=0) const
Definition: sc_hash.h:76
bool contains(K k) const
Definition: sc_hash.h:316
int lookup(K k, C *pc) const
Definition: sc_hash.h:312
void copy(const sc_pdhash< K, C > &b)
Definition: sc_hash.h:288
const char * key()
Definition: sc_hash.h:427
unsigned default_ptr_hash_fn(const void *)
sc_phash_elem * next
Definition: sc_hash.h:129
int insert(K k)
Definition: sc_hash.h:290
const double PHASH_DEFAULT_GROW_FACTOR
sc_phash_base_iter(sc_phash_base *t)
Definition: sc_hash.h:137
int insert(K k, C c)
Definition: sc_hash.h:289
void copy(const sc_phash< K, C > &b)
Definition: sc_hash.h:176
sc_phash_elem ** last
Definition: sc_hash.h:130
sc_phash_elem ** bins
Definition: sc_hash.h:65
sc_phash_elem * find_entry_q(unsigned hv, const void *k, sc_phash_elem ***plast)
sc_phash_elem * add_direct(void *key, void *contents, unsigned hash_val)
void copy(const sc_phash_base &b)
Definition: sc_hash.h:105
int remove_by_contents(const void *c, void(*kfree)(void *))
Definition: sc_hash.h:211
void set_cmpr_fn(cmpr_fn_t)
sc_pdhash_iter< K, C > iterator
Definition: sc_hash.h:265
C contents() const
Definition: sc_hash.h:245
int insert_if_not_exists(K k)
Definition: sc_hash.h:295
int lookup(K k, C *pc) const
Definition: sc_hash.h:219
sc_strhash_iter(sc_strhash< C > &t)
Definition: sc_hash.h:420
void copy(const sc_phash< K, C > &b, void *(*kdup)(const void *), void(*kfree)(void *))
Definition: sc_hash.h:177
int insert_if_not_exists(void *k)
Definition: sc_hash.h:111
C operator[](const char *k) const
Definition: sc_hash.h:410
void sc_strhash_kfree(void *)
unsigned count() const
Definition: sc_hash.h:100
void copy(const sc_phash< K, C > *b)
Definition: sc_hash.h:175
int insert_if_not_exists(K k, C c, void *(*kdup)(const void *))
Definition: sc_hash.h:190
int insert(K k, C c)
Definition: sc_hash.h:179
sc_strhash_iter< C > iterator
Definition: sc_hash.h:357
bool contains(K k) const
Definition: sc_hash.h:223
int insert_if_not_exists(K k, C c)
Definition: sc_hash.h:291
void reset(sc_phash< K, C > &t)
Definition: sc_hash.h:242
int insert(char *k, C c)
Definition: sc_hash.h:379
void reset(sc_strhash< C > &t)
Definition: sc_hash.h:424
int insert(void *k, void *c)
int insert_if_not_exists(char *k, C c)
Definition: sc_hash.h:381
int insert_if_not_exists(char *k)
Definition: sc_hash.h:385
const int PHASH_DEFAULT_MAX_DENSITY
Definition: sc_hash.h:43
sc_pdhash(C def=(C) 0, int size=PHASH_DEFAULT_INIT_TABLE_SIZE, int density=PHASH_DEFAULT_MAX_DENSITY, double grow=PHASH_DEFAULT_GROW_FACTOR, bool reorder=PHASH_DEFAULT_REORDER_FLAG, hash_fn_t hash_fn=(hash_fn_t) 0, cmpr_fn_t cmpr_fn=(cmpr_fn_t) 0, void *(*kdup_fn)(const void *)=0, void(*kfree_fn)(void *)=0)
Definition: sc_hash.h:266
int remove_by_contents(const void *c)
int remove_by_contents(bool(*predicate)(const void *, void *), void *arg)
Definition: sc_hash.h:308
sc_phash_base(void *def=0, int size=PHASH_DEFAULT_INIT_TABLE_SIZE, int density=PHASH_DEFAULT_MAX_DENSITY, double grow=PHASH_DEFAULT_GROW_FACTOR, bool reorder=PHASH_DEFAULT_REORDER_FLAG, hash_fn_t hash_fn=default_ptr_hash_fn, cmpr_fn_t cmpr_fn=0)
unsigned(* hash_fn_t)(const void *)
Definition: sc_hash.h:54
void reset(sc_pdhash< K, C > *t)
Definition: sc_hash.h:333
sc_phash_base_iter(sc_phash_base &t)
Definition: sc_hash.h:140
int insert(char *k)
Definition: sc_hash.h:380
int remove_by_contents(bool(*predicate)(const void *, void *), void *arg)
Definition: sc_hash.h:207
void reset(sc_phash_base &t)
Definition: sc_hash.h:135
int remove_by_contents(C c)
Definition: sc_hash.h:203
int sc_strhash_cmp(const void *, const void *)
int lookup(const char *k, C *pc) const
Definition: sc_hash.h:402
sc_phash_elem * entry
Definition: sc_hash.h:128
int remove_by_contents(C c)
Definition: sc_hash.h:394
sc_phash_iter(sc_phash< K, C > &t)
Definition: sc_hash.h:238
void reset(sc_phash_base *t)
void reset(sc_strhash< C > *t)
Definition: sc_hash.h:423
const bool PHASH_DEFAULT_REORDER_FLAG
Definition: sc_hash.h:46
void * operator[](const void *key) const
int insert_if_not_exists(K k)
Definition: sc_hash.h:186
C contents() const
Definition: sc_hash.h:338