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#include <assert.h>
31#include <stdlib.h> // duplicate (c)stdlib.h headers for Solaris
32#include <cstdlib>
33#include <cstddef>
34#include <string.h>
35
36#include "sysc/kernel/sc_cmnhdr.h"
37#include "sysc/utils/sc_hash.h"
38#include "sysc/utils/sc_mempool.h"
39
40namespace sc_core {
41
42// we can't assume global availability of uintptr_t,
43// approximate it by size_t
44typedef std::size_t uintptr_t;
45
46const double PHASH_DEFAULT_GROW_FACTOR     = 2.0;
47
48class sc_phash_elem {
49    friend class sc_phash_base;
50    friend class sc_phash_base_iter;
51
52private:
53    void* key;
54    void* contents;
55    sc_phash_elem* next;
56
57    sc_phash_elem( void* k, void* c, sc_phash_elem* n )
58        : key(k), contents(c), next(n) { }
59    sc_phash_elem() : key(0), contents(0), next(0) { }
60    ~sc_phash_elem() { }
61
62    static void* operator new(std::size_t sz)
63        { return sc_mempool::allocate(sz); }
64    static void operator delete(void* p, std::size_t sz)
65        { sc_mempool::release(p, sz);      }
66};
67
68
69sc_phash_base::sc_phash_base(
70    void* def,
71    int size,
72    int density,
73    double grow,
74    bool reorder,
75    unsigned (*hash_fn)(const void*),
76    int (*cmp_fn)(const void*, const void*)
77) :
78    default_value(def), num_bins(0), num_entries(0), max_density(density),
79    reorder_flag(reorder), grow_factor(grow), bins(0), hash(hash_fn),
80    cmpr(cmp_fn)
81{
82    if (size <= 0)
83        size = PHASH_DEFAULT_INIT_TABLE_SIZE;
84    else if ((size % 2) == 0)
85        size += 1;
86    num_bins = size;
87    bins = new sc_phash_elem*[size];
88    for (int i = 0; i < size; ++i)
89        bins[i] = 0;
90}
91
92void
93sc_phash_base::set_cmpr_fn(cmpr_fn_t c)
94{
95    cmpr = c;
96}
97
98void
99sc_phash_base::set_hash_fn(hash_fn_t h)
100{
101    hash = h;
102}
103
104sc_phash_base::~sc_phash_base()
105{
106    sc_phash_elem* ptr;
107    sc_phash_elem* next;
108
109    for (int i = 0; i < num_bins; ++i) {
110        ptr = bins[i];
111        while (ptr != 0) {
112            next = ptr->next;
113            delete ptr;
114            ptr = next;
115        }
116    }
117    delete[] bins;
118}
119
120void
121sc_phash_base::rehash()
122{
123    sc_phash_elem* ptr;
124    sc_phash_elem* next;
125    sc_phash_elem** old_bins = bins;
126
127    int old_num_bins = num_bins;
128    unsigned hash_val;
129
130    num_bins = (int) (grow_factor * old_num_bins);
131    if (num_bins % 2 == 0)
132        ++num_bins;
133
134    num_entries = 0;
135    bins = new sc_phash_elem*[num_bins];
136    memset( bins, 0, sizeof(sc_phash_elem*) * num_bins );
137
138    for (int i = 0; i < old_num_bins; ++i) {
139        ptr = old_bins[i];
140        while (ptr != 0) {
141            next = ptr->next;
142            hash_val = do_hash(ptr->key);
143            ptr->next = bins[hash_val];
144            bins[hash_val] = ptr;
145            ++num_entries;
146            ptr = next;
147        }
148    }
149    delete[] old_bins;
150}
151
152sc_phash_elem*
153sc_phash_base::find_entry_q( unsigned hash_val, const void* key, sc_phash_elem*** plast )
154{
155    sc_phash_elem** last = &(bins[hash_val]);
156    sc_phash_elem*  ptr  = *last;
157
158    /* The (ptr->key != key) here is meant by the "q" */
159    while ((ptr != 0) && (ptr->key != key)) {
160        /*                         ^^ right here */
161        last = &(ptr->next);
162        ptr  = *last;
163    }
164    if ((ptr != 0) && reorder_flag) {
165        *last = ptr->next;
166        ptr->next = bins[hash_val];
167        bins[hash_val] = ptr;
168        last = &(bins[hash_val]);
169    }
170    if (plast) *plast = last;
171    return ptr;
172}
173
174sc_phash_elem*
175sc_phash_base::find_entry_c( unsigned hash_val, const void* key, sc_phash_elem*** plast )
176{
177    sc_phash_elem** last = &(bins[hash_val]);
178    sc_phash_elem*  ptr  = *last;
179
180    while ((ptr != 0) && ((*cmpr)(ptr->key, key) != 0)) {
181        last = &(ptr->next);
182        ptr = *last;
183    }
184        /* Bring to front */
185    if ((ptr != 0) && reorder_flag) {
186        *last = ptr->next;
187        ptr->next = bins[hash_val];
188        bins[hash_val] = ptr;
189        last = &(bins[hash_val]);
190    }
191    if (plast) *plast = last;
192    return ptr;
193}
194
195sc_phash_elem*
196sc_phash_base::add_direct( void* key, void* contents, unsigned hash_val )
197{
198    if (num_entries / num_bins >= max_density) {
199        rehash();
200        hash_val = do_hash(key);
201    }
202
203    sc_phash_elem* new_entry = new sc_phash_elem(key, contents, bins[hash_val]);
204    bins[hash_val] = new_entry;
205    ++num_entries;
206    return new_entry;
207}
208
209void
210sc_phash_base::erase()
211{
212    for (int i = 0; i < num_bins; ++i) {
213        sc_phash_elem* ptr = bins[i];
214        while (ptr != 0) {
215            sc_phash_elem* next = ptr->next;
216            delete ptr;
217            ptr = next;
218            --num_entries;
219        }
220        bins[i] = 0;
221    }
222    assert(num_entries == 0);
223}
224
225void
226sc_phash_base::erase(void (*kfree)(void*))
227{
228    for (int i = 0; i < num_bins; ++i) {
229        sc_phash_elem* ptr = bins[i];
230        while (ptr != 0) {
231            sc_phash_elem* next = ptr->next;
232            (*kfree)(ptr->key);
233            delete ptr;
234            ptr = next;
235            --num_entries;
236        }
237        bins[i] = 0;
238    }
239    assert(num_entries == 0);
240}
241
242void
243sc_phash_base::copy( const sc_phash_base* b )
244{
245    erase();
246    iterator iter((sc_phash_base*) b);  /* cast away the const */
247    for ( ; ! iter.empty(); iter++)
248        insert( iter.key(), iter.contents() );
249}
250
251void
252sc_phash_base::copy(const sc_phash_base& b, void* (*kdup)(const void*), void (*kfree)(void*))
253{
254    erase(kfree);
255    iterator iter((sc_phash_base&) b);
256    for ( ; ! iter.empty(); iter++)
257        insert( (*kdup)(iter.key()), iter.contents() );
258}
259
260int
261sc_phash_base::insert( void* k, void* c )
262{
263    unsigned hash_val = do_hash(k);
264    sc_phash_elem* ptr = find_entry( hash_val, k );
265    if (ptr == 0) {
266        (void) add_direct(k, c, hash_val);
267        return 0;
268    }
269    else {
270        ptr->contents = c;
271        return 1;
272    }
273}
274
275int
276sc_phash_base::insert( void* k, void* c, void* (*kdup)(const void*) )
277{
278    unsigned hash_val = do_hash(k);
279    sc_phash_elem* ptr = find_entry( hash_val, k );
280    if (ptr == 0) {
281        (void) add_direct((*kdup)(k), c, hash_val);
282        return 0;
283    }
284    else {
285        ptr->contents = c;
286        return 1;
287    }
288}
289
290int
291sc_phash_base::insert_if_not_exists( void* k, void* c )
292{
293    unsigned hash_val = do_hash(k);
294    sc_phash_elem* ptr = find_entry( hash_val, k );
295    if (ptr == 0) {
296        (void) add_direct( k, c, hash_val );
297        return 0;
298    }
299    else
300        return 1;
301}
302
303int
304sc_phash_base::insert_if_not_exists( void* k, void* c, void* (*kdup)(const void*) )
305{
306    unsigned hash_val = do_hash(k);
307    sc_phash_elem* ptr = find_entry( hash_val, k );
308    if (ptr == 0) {
309        (void) add_direct( (*kdup)(k), c, hash_val );
310        return 0;
311    }
312    else
313        return 1;
314}
315
316int
317sc_phash_base::remove( const void* k )
318{
319    unsigned hash_val = do_hash(k);
320    sc_phash_elem** last;
321    sc_phash_elem*  ptr = find_entry( hash_val, k, &last );
322
323    if (ptr == 0)
324        return 0;
325
326    assert(*last == ptr);
327    *last = ptr->next;
328    delete ptr;
329    --num_entries;
330    return 1;
331}
332
333int
334sc_phash_base::remove( const void* k, void** pk, void** pc )
335{
336    unsigned hash_val = do_hash(k);
337    sc_phash_elem** last;
338    sc_phash_elem*  ptr = find_entry( hash_val, k, &last );
339
340    if (ptr == 0) {
341        *pk = 0;
342        *pc = 0;
343        return 0;
344    }
345    else {
346        *pk = ptr->key;
347        *pc = ptr->contents;
348    }
349
350    assert(*last == ptr);
351    *last = ptr->next;
352    delete ptr;
353    --num_entries;
354    return 1;
355}
356
357int
358sc_phash_base::remove(const void* k, void (*kfree)(void*))
359{
360    void* rk;
361    void* rc;
362    if (remove(k, &rk, &rc)) {
363        (*kfree)(rk);
364        return 1;
365    }
366    else
367        return 0;
368}
369
370int
371sc_phash_base::remove_by_contents( const void* c )
372{
373    sc_phash_elem** last;
374    sc_phash_elem*  ptr;
375
376    int num_removed = 0;
377    for (int i = 0; i < num_bins; ++i) {
378        last = &(bins[i]);
379        ptr = *last;
380        while (ptr != 0) {
381            if (ptr->contents != c) {
382                last = &(ptr->next);
383                ptr  = *last;
384            }
385            else {
386                *last = ptr->next;
387                delete ptr;
388                ptr = *last;
389                --num_entries;
390                ++num_removed;
391            }
392        }
393    }
394    return num_removed;
395}
396
397int
398sc_phash_base::remove_by_contents( bool (*predicate)(const void* c, void* arg), void* arg )
399{
400    sc_phash_elem** last;
401    sc_phash_elem*  ptr;
402
403    int num_removed = 0;
404    for (int i = 0; i < num_bins; ++i) {
405        last = &(bins[i]);
406        ptr = *last;
407        while (ptr != 0) {
408            if (! (*predicate)(ptr->contents, arg)) {
409                last = &(ptr->next);
410                ptr  = *last;
411            }
412            else {
413                *last = ptr->next;
414                delete ptr;
415                ptr = *last;
416                --num_entries;
417                ++num_removed;
418            }
419        }
420    }
421    return num_removed;
422}
423
424int
425sc_phash_base::remove_by_contents( const void* c, void (*kfree)(void*) )
426{
427    sc_phash_elem** last;
428    sc_phash_elem*  ptr;
429
430    int num_removed = 0;
431    for (int i = 0; i < num_bins; ++i) {
432        last = &(bins[i]);
433        ptr = *last;
434        while (ptr != 0) {
435            if (ptr->contents != c) {
436                last = &(ptr->next);
437                ptr  = *last;
438            }
439            else {
440                *last = ptr->next;
441                (*kfree)(ptr->key);
442                delete ptr;
443                ptr = *last;
444                --num_entries;
445                ++num_removed;
446            }
447        }
448    }
449    return num_removed;
450}
451
452int
453sc_phash_base::remove_by_contents( bool (*predicate)(const void*, void*), void* arg, void (*kfree)(void*))
454{
455    sc_phash_elem** last;
456    sc_phash_elem*  ptr;
457
458    int num_removed = 0;
459    for (int i = 0; i < num_bins; ++i) {
460        last = &(bins[i]);
461        ptr = *last;
462        while (ptr != 0) {
463            if (! (*predicate)(ptr->contents, arg)) {
464                last = &(ptr->next);
465                ptr  = *last;
466            }
467            else {
468                *last = ptr->next;
469                (*kfree)(ptr->key);
470                delete ptr;
471                ptr = *last;
472                --num_entries;
473                ++num_removed;
474            }
475        }
476    }
477    return num_removed;
478}
479
480int
481sc_phash_base::lookup( const void* k, void** c_ptr ) const
482{
483    unsigned hash_val = do_hash(k);
484    sc_phash_elem* ptr = find_entry( hash_val, k );
485    if (ptr == 0) {
486        if (c_ptr != 0) *c_ptr = default_value;
487        return 0;
488    }
489    else {
490        if (c_ptr != 0) *c_ptr = ptr->contents;
491        return 1;
492    }
493}
494
495void*
496sc_phash_base::operator[]( const void* key ) const
497{
498    void* contents;
499    lookup( key, &contents );
500    return contents;
501}
502
503/***************************************************************************/
504
505void
506sc_phash_base_iter::reset( sc_phash_base* t )
507{
508    table = t;
509    index = 0;
510    entry = 0;
511    next  = 0;
512
513    for (int i = index; i < table->num_bins; ++i) {
514        if (table->bins[i] != 0) {
515            index = i + 1;
516            last  = &(table->bins[i]);
517            entry = *last;
518            next  = entry->next;
519            break;
520        }
521    }
522}
523
524bool
525sc_phash_base_iter::empty() const
526{
527    return (entry == 0);
528}
529
530void
531sc_phash_base_iter::step()
532{
533    if (entry) {
534        last = &(entry->next);
535    }
536    entry = next;
537    if (! entry) {
538        for (int i = index; i < table->num_bins; ++i) {
539            if (table->bins[i] != 0) {
540                index = i + 1;
541                last = &(table->bins[i]);
542                entry = *last;
543                next = entry->next;
544                break;
545            }
546        }
547    }
548    else {
549        next = entry->next;
550    }
551}
552
553void
554sc_phash_base_iter::remove()
555{
556    delete entry;
557    *last = next;
558    entry = 0;
559    --table->num_entries;
560    step();
561}
562
563void
564sc_phash_base_iter::remove(void (*kfree)(void*))
565{
566    (*kfree)(entry->key);
567    delete entry;
568    *last = next;
569    entry = 0;
570    --table->num_entries;
571    step();
572}
573
574void*
575sc_phash_base_iter::key() const
576{
577    return entry->key;
578}
579
580void*
581sc_phash_base_iter::contents() const
582{
583    return entry->contents;
584}
585
586void*
587sc_phash_base_iter::set_contents( void* c )
588{
589    return entry->contents = c;
590}
591
592/****************************************************************************/
593
594unsigned
595default_ptr_hash_fn(const void* p)
596{
597    return static_cast<unsigned>(((uintptr_t)(p) >> 2) * 2654435789U);
598
599}
600
601unsigned
602default_int_hash_fn(const void* p)
603{
604    return static_cast<unsigned>((uintptr_t)(p) * 3141592661U);
605}
606
607
608unsigned
609default_str_hash_fn(const void* p)
610{
611    if (!p) return 0;
612
613    const char* x = (const char*) p;
614    unsigned int h = 0;
615    unsigned int g;
616
617    while (*x != 0) {
618        h = (h << 4) + *x++;
619        if ((g = h & 0xf0000000) != 0)
620            h = (h ^ (g >> 24)) ^ g;
621    }
622    return h;
623}
624
625int
626sc_strhash_cmp( const void* a, const void* b )
627{
628    return strcmp( (const char*) a, (const char*) b );
629}
630
631void*
632sc_strhash_kdup(const void* k)
633{
634    char* result = (char*) malloc( strlen((const char*)k)+1 );
635    strcpy(result, (const char*) k);
636    return result;
637}
638
639void
640sc_strhash_kfree(void* k)
641{
642    if (k) free((char*) k);
643}
644 } // namespace sc_core
645
646// $Log: sc_hash.cpp,v $
647// Revision 1.5  2011/08/26 20:42:30  acg
648//  Andy Goodrich:
649//    (1) Replaced strdup with new and strcpy to eliminate issue with the
650//        Greenhills compiler.
651//    (2) Moved modification log to the end of the file to eliminate line
652//        skew when check-ins are done.
653//
654// Revision 1.4  2011/08/24 22:05:56  acg
655//  Torsten Maehne: initialization changes to remove warnings.
656//
657// Revision 1.3  2011/05/05 17:46:04  acg
658//  Philip A. Hartmann: changes in "swap" support.
659//
660// Revision 1.2  2011/02/18 20:38:43  acg
661//  Andy Goodrich: Updated Copyright notice.
662//
663// Revision 1.1.1.1  2006/12/15 20:20:06  acg
664// SystemC 2.3
665//
666// Revision 1.3  2006/01/13 18:53:10  acg
667// Andy Goodrich: Added $Log command so that CVS comments are reproduced in
668// the source.
669
670// taf
671