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