112027Sjungma@eit.uni-kl.de/***************************************************************************** 212027Sjungma@eit.uni-kl.de 312027Sjungma@eit.uni-kl.de Licensed to Accellera Systems Initiative Inc. (Accellera) under one or 412027Sjungma@eit.uni-kl.de more contributor license agreements. See the NOTICE file distributed 512027Sjungma@eit.uni-kl.de with this work for additional information regarding copyright ownership. 612027Sjungma@eit.uni-kl.de Accellera licenses this file to you under the Apache License, Version 2.0 712027Sjungma@eit.uni-kl.de (the "License"); you may not use this file except in compliance with the 812027Sjungma@eit.uni-kl.de License. You may obtain a copy of the License at 912027Sjungma@eit.uni-kl.de 1012027Sjungma@eit.uni-kl.de http://www.apache.org/licenses/LICENSE-2.0 1112027Sjungma@eit.uni-kl.de 1212027Sjungma@eit.uni-kl.de Unless required by applicable law or agreed to in writing, software 1312027Sjungma@eit.uni-kl.de distributed under the License is distributed on an "AS IS" BASIS, 1412027Sjungma@eit.uni-kl.de WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or 1512027Sjungma@eit.uni-kl.de implied. See the License for the specific language governing 1612027Sjungma@eit.uni-kl.de permissions and limitations under the License. 1712027Sjungma@eit.uni-kl.de 1812027Sjungma@eit.uni-kl.de *****************************************************************************/ 1912027Sjungma@eit.uni-kl.de 2012027Sjungma@eit.uni-kl.de/***************************************************************************** 2112027Sjungma@eit.uni-kl.de 2212027Sjungma@eit.uni-kl.de sc_hash.cpp -- Implementation of a chained hash table with MTF 2312027Sjungma@eit.uni-kl.de (move-to-front). 2412027Sjungma@eit.uni-kl.de 2512027Sjungma@eit.uni-kl.de Original Author: Stan Y. Liao, Synopsys, Inc. 2612027Sjungma@eit.uni-kl.de 2712027Sjungma@eit.uni-kl.de CHANGE LOG AT END OF FILE 2812027Sjungma@eit.uni-kl.de *****************************************************************************/ 2912027Sjungma@eit.uni-kl.de 3012027Sjungma@eit.uni-kl.de#include <assert.h> 3112027Sjungma@eit.uni-kl.de#include <stdlib.h> // duplicate (c)stdlib.h headers for Solaris 3212027Sjungma@eit.uni-kl.de#include <cstdlib> 3312027Sjungma@eit.uni-kl.de#include <cstddef> 3412027Sjungma@eit.uni-kl.de#include <string.h> 3512027Sjungma@eit.uni-kl.de 3612027Sjungma@eit.uni-kl.de#include "sysc/kernel/sc_cmnhdr.h" 3712027Sjungma@eit.uni-kl.de#include "sysc/utils/sc_hash.h" 3812027Sjungma@eit.uni-kl.de#include "sysc/utils/sc_mempool.h" 3912027Sjungma@eit.uni-kl.de 4012027Sjungma@eit.uni-kl.denamespace sc_core { 4112027Sjungma@eit.uni-kl.de 4212027Sjungma@eit.uni-kl.de// we can't assume global availability of uintptr_t, 4312027Sjungma@eit.uni-kl.de// approximate it by size_t 4412027Sjungma@eit.uni-kl.detypedef std::size_t uintptr_t; 4512027Sjungma@eit.uni-kl.de 4612027Sjungma@eit.uni-kl.deconst double PHASH_DEFAULT_GROW_FACTOR = 2.0; 4712027Sjungma@eit.uni-kl.de 4812027Sjungma@eit.uni-kl.declass sc_phash_elem { 4912027Sjungma@eit.uni-kl.de friend class sc_phash_base; 5012027Sjungma@eit.uni-kl.de friend class sc_phash_base_iter; 5112027Sjungma@eit.uni-kl.de 5212027Sjungma@eit.uni-kl.deprivate: 5312027Sjungma@eit.uni-kl.de void* key; 5412027Sjungma@eit.uni-kl.de void* contents; 5512027Sjungma@eit.uni-kl.de sc_phash_elem* next; 5612027Sjungma@eit.uni-kl.de 5712027Sjungma@eit.uni-kl.de sc_phash_elem( void* k, void* c, sc_phash_elem* n ) 5812027Sjungma@eit.uni-kl.de : key(k), contents(c), next(n) { } 5912027Sjungma@eit.uni-kl.de sc_phash_elem() : key(0), contents(0), next(0) { } 6012027Sjungma@eit.uni-kl.de ~sc_phash_elem() { } 6112027Sjungma@eit.uni-kl.de 6212027Sjungma@eit.uni-kl.de static void* operator new(std::size_t sz) 6312027Sjungma@eit.uni-kl.de { return sc_mempool::allocate(sz); } 6412027Sjungma@eit.uni-kl.de static void operator delete(void* p, std::size_t sz) 6512027Sjungma@eit.uni-kl.de { sc_mempool::release(p, sz); } 6612027Sjungma@eit.uni-kl.de}; 6712027Sjungma@eit.uni-kl.de 6812027Sjungma@eit.uni-kl.de 6912027Sjungma@eit.uni-kl.desc_phash_base::sc_phash_base( 7012027Sjungma@eit.uni-kl.de void* def, 7112027Sjungma@eit.uni-kl.de int size, 7212027Sjungma@eit.uni-kl.de int density, 7312027Sjungma@eit.uni-kl.de double grow, 7412027Sjungma@eit.uni-kl.de bool reorder, 7512027Sjungma@eit.uni-kl.de unsigned (*hash_fn)(const void*), 7612027Sjungma@eit.uni-kl.de int (*cmp_fn)(const void*, const void*) 7712027Sjungma@eit.uni-kl.de) : 7812027Sjungma@eit.uni-kl.de default_value(def), num_bins(0), num_entries(0), max_density(density), 7912027Sjungma@eit.uni-kl.de reorder_flag(reorder), grow_factor(grow), bins(0), hash(hash_fn), 8012027Sjungma@eit.uni-kl.de cmpr(cmp_fn) 8112027Sjungma@eit.uni-kl.de{ 8212027Sjungma@eit.uni-kl.de if (size <= 0) 8312027Sjungma@eit.uni-kl.de size = PHASH_DEFAULT_INIT_TABLE_SIZE; 8412027Sjungma@eit.uni-kl.de else if ((size % 2) == 0) 8512027Sjungma@eit.uni-kl.de size += 1; 8612027Sjungma@eit.uni-kl.de num_bins = size; 8712027Sjungma@eit.uni-kl.de bins = new sc_phash_elem*[size]; 8812027Sjungma@eit.uni-kl.de for (int i = 0; i < size; ++i) 8912027Sjungma@eit.uni-kl.de bins[i] = 0; 9012027Sjungma@eit.uni-kl.de} 9112027Sjungma@eit.uni-kl.de 9212027Sjungma@eit.uni-kl.devoid 9312027Sjungma@eit.uni-kl.desc_phash_base::set_cmpr_fn(cmpr_fn_t c) 9412027Sjungma@eit.uni-kl.de{ 9512027Sjungma@eit.uni-kl.de cmpr = c; 9612027Sjungma@eit.uni-kl.de} 9712027Sjungma@eit.uni-kl.de 9812027Sjungma@eit.uni-kl.devoid 9912027Sjungma@eit.uni-kl.desc_phash_base::set_hash_fn(hash_fn_t h) 10012027Sjungma@eit.uni-kl.de{ 10112027Sjungma@eit.uni-kl.de hash = h; 10212027Sjungma@eit.uni-kl.de} 10312027Sjungma@eit.uni-kl.de 10412027Sjungma@eit.uni-kl.desc_phash_base::~sc_phash_base() 10512027Sjungma@eit.uni-kl.de{ 10612027Sjungma@eit.uni-kl.de sc_phash_elem* ptr; 10712027Sjungma@eit.uni-kl.de sc_phash_elem* next; 10812027Sjungma@eit.uni-kl.de 10912027Sjungma@eit.uni-kl.de for (int i = 0; i < num_bins; ++i) { 11012027Sjungma@eit.uni-kl.de ptr = bins[i]; 11112027Sjungma@eit.uni-kl.de while (ptr != 0) { 11212027Sjungma@eit.uni-kl.de next = ptr->next; 11312027Sjungma@eit.uni-kl.de delete ptr; 11412027Sjungma@eit.uni-kl.de ptr = next; 11512027Sjungma@eit.uni-kl.de } 11612027Sjungma@eit.uni-kl.de } 11712027Sjungma@eit.uni-kl.de delete[] bins; 11812027Sjungma@eit.uni-kl.de} 11912027Sjungma@eit.uni-kl.de 12012027Sjungma@eit.uni-kl.devoid 12112027Sjungma@eit.uni-kl.desc_phash_base::rehash() 12212027Sjungma@eit.uni-kl.de{ 12312027Sjungma@eit.uni-kl.de sc_phash_elem* ptr; 12412027Sjungma@eit.uni-kl.de sc_phash_elem* next; 12512027Sjungma@eit.uni-kl.de sc_phash_elem** old_bins = bins; 12612027Sjungma@eit.uni-kl.de 12712027Sjungma@eit.uni-kl.de int old_num_bins = num_bins; 12812027Sjungma@eit.uni-kl.de unsigned hash_val; 12912027Sjungma@eit.uni-kl.de 13012027Sjungma@eit.uni-kl.de num_bins = (int) (grow_factor * old_num_bins); 13112027Sjungma@eit.uni-kl.de if (num_bins % 2 == 0) 13212027Sjungma@eit.uni-kl.de ++num_bins; 13312027Sjungma@eit.uni-kl.de 13412027Sjungma@eit.uni-kl.de num_entries = 0; 13512027Sjungma@eit.uni-kl.de bins = new sc_phash_elem*[num_bins]; 13612027Sjungma@eit.uni-kl.de memset( bins, 0, sizeof(sc_phash_elem*) * num_bins ); 13712027Sjungma@eit.uni-kl.de 13812027Sjungma@eit.uni-kl.de for (int i = 0; i < old_num_bins; ++i) { 13912027Sjungma@eit.uni-kl.de ptr = old_bins[i]; 14012027Sjungma@eit.uni-kl.de while (ptr != 0) { 14112027Sjungma@eit.uni-kl.de next = ptr->next; 14212027Sjungma@eit.uni-kl.de hash_val = do_hash(ptr->key); 14312027Sjungma@eit.uni-kl.de ptr->next = bins[hash_val]; 14412027Sjungma@eit.uni-kl.de bins[hash_val] = ptr; 14512027Sjungma@eit.uni-kl.de ++num_entries; 14612027Sjungma@eit.uni-kl.de ptr = next; 14712027Sjungma@eit.uni-kl.de } 14812027Sjungma@eit.uni-kl.de } 14912027Sjungma@eit.uni-kl.de delete[] old_bins; 15012027Sjungma@eit.uni-kl.de} 15112027Sjungma@eit.uni-kl.de 15212027Sjungma@eit.uni-kl.desc_phash_elem* 15312027Sjungma@eit.uni-kl.desc_phash_base::find_entry_q( unsigned hash_val, const void* key, sc_phash_elem*** plast ) 15412027Sjungma@eit.uni-kl.de{ 15512027Sjungma@eit.uni-kl.de sc_phash_elem** last = &(bins[hash_val]); 15612027Sjungma@eit.uni-kl.de sc_phash_elem* ptr = *last; 15712027Sjungma@eit.uni-kl.de 15812027Sjungma@eit.uni-kl.de /* The (ptr->key != key) here is meant by the "q" */ 15912027Sjungma@eit.uni-kl.de while ((ptr != 0) && (ptr->key != key)) { 16012027Sjungma@eit.uni-kl.de /* ^^ right here */ 16112027Sjungma@eit.uni-kl.de last = &(ptr->next); 16212027Sjungma@eit.uni-kl.de ptr = *last; 16312027Sjungma@eit.uni-kl.de } 16412027Sjungma@eit.uni-kl.de if ((ptr != 0) && reorder_flag) { 16512027Sjungma@eit.uni-kl.de *last = ptr->next; 16612027Sjungma@eit.uni-kl.de ptr->next = bins[hash_val]; 16712027Sjungma@eit.uni-kl.de bins[hash_val] = ptr; 16812027Sjungma@eit.uni-kl.de last = &(bins[hash_val]); 16912027Sjungma@eit.uni-kl.de } 17012027Sjungma@eit.uni-kl.de if (plast) *plast = last; 17112027Sjungma@eit.uni-kl.de return ptr; 17212027Sjungma@eit.uni-kl.de} 17312027Sjungma@eit.uni-kl.de 17412027Sjungma@eit.uni-kl.desc_phash_elem* 17512027Sjungma@eit.uni-kl.desc_phash_base::find_entry_c( unsigned hash_val, const void* key, sc_phash_elem*** plast ) 17612027Sjungma@eit.uni-kl.de{ 17712027Sjungma@eit.uni-kl.de sc_phash_elem** last = &(bins[hash_val]); 17812027Sjungma@eit.uni-kl.de sc_phash_elem* ptr = *last; 17912027Sjungma@eit.uni-kl.de 18012027Sjungma@eit.uni-kl.de while ((ptr != 0) && ((*cmpr)(ptr->key, key) != 0)) { 18112027Sjungma@eit.uni-kl.de last = &(ptr->next); 18212027Sjungma@eit.uni-kl.de ptr = *last; 18312027Sjungma@eit.uni-kl.de } 18412027Sjungma@eit.uni-kl.de /* Bring to front */ 18512027Sjungma@eit.uni-kl.de if ((ptr != 0) && reorder_flag) { 18612027Sjungma@eit.uni-kl.de *last = ptr->next; 18712027Sjungma@eit.uni-kl.de ptr->next = bins[hash_val]; 18812027Sjungma@eit.uni-kl.de bins[hash_val] = ptr; 18912027Sjungma@eit.uni-kl.de last = &(bins[hash_val]); 19012027Sjungma@eit.uni-kl.de } 19112027Sjungma@eit.uni-kl.de if (plast) *plast = last; 19212027Sjungma@eit.uni-kl.de return ptr; 19312027Sjungma@eit.uni-kl.de} 19412027Sjungma@eit.uni-kl.de 19512027Sjungma@eit.uni-kl.desc_phash_elem* 19612027Sjungma@eit.uni-kl.desc_phash_base::add_direct( void* key, void* contents, unsigned hash_val ) 19712027Sjungma@eit.uni-kl.de{ 19812027Sjungma@eit.uni-kl.de if (num_entries / num_bins >= max_density) { 19912027Sjungma@eit.uni-kl.de rehash(); 20012027Sjungma@eit.uni-kl.de hash_val = do_hash(key); 20112027Sjungma@eit.uni-kl.de } 20212027Sjungma@eit.uni-kl.de 20312027Sjungma@eit.uni-kl.de sc_phash_elem* new_entry = new sc_phash_elem(key, contents, bins[hash_val]); 20412027Sjungma@eit.uni-kl.de bins[hash_val] = new_entry; 20512027Sjungma@eit.uni-kl.de ++num_entries; 20612027Sjungma@eit.uni-kl.de return new_entry; 20712027Sjungma@eit.uni-kl.de} 20812027Sjungma@eit.uni-kl.de 20912027Sjungma@eit.uni-kl.devoid 21012027Sjungma@eit.uni-kl.desc_phash_base::erase() 21112027Sjungma@eit.uni-kl.de{ 21212027Sjungma@eit.uni-kl.de for (int i = 0; i < num_bins; ++i) { 21312027Sjungma@eit.uni-kl.de sc_phash_elem* ptr = bins[i]; 21412027Sjungma@eit.uni-kl.de while (ptr != 0) { 21512027Sjungma@eit.uni-kl.de sc_phash_elem* next = ptr->next; 21612027Sjungma@eit.uni-kl.de delete ptr; 21712027Sjungma@eit.uni-kl.de ptr = next; 21812027Sjungma@eit.uni-kl.de --num_entries; 21912027Sjungma@eit.uni-kl.de } 22012027Sjungma@eit.uni-kl.de bins[i] = 0; 22112027Sjungma@eit.uni-kl.de } 22212027Sjungma@eit.uni-kl.de assert(num_entries == 0); 22312027Sjungma@eit.uni-kl.de} 22412027Sjungma@eit.uni-kl.de 22512027Sjungma@eit.uni-kl.devoid 22612027Sjungma@eit.uni-kl.desc_phash_base::erase(void (*kfree)(void*)) 22712027Sjungma@eit.uni-kl.de{ 22812027Sjungma@eit.uni-kl.de for (int i = 0; i < num_bins; ++i) { 22912027Sjungma@eit.uni-kl.de sc_phash_elem* ptr = bins[i]; 23012027Sjungma@eit.uni-kl.de while (ptr != 0) { 23112027Sjungma@eit.uni-kl.de sc_phash_elem* next = ptr->next; 23212027Sjungma@eit.uni-kl.de (*kfree)(ptr->key); 23312027Sjungma@eit.uni-kl.de delete ptr; 23412027Sjungma@eit.uni-kl.de ptr = next; 23512027Sjungma@eit.uni-kl.de --num_entries; 23612027Sjungma@eit.uni-kl.de } 23712027Sjungma@eit.uni-kl.de bins[i] = 0; 23812027Sjungma@eit.uni-kl.de } 23912027Sjungma@eit.uni-kl.de assert(num_entries == 0); 24012027Sjungma@eit.uni-kl.de} 24112027Sjungma@eit.uni-kl.de 24212027Sjungma@eit.uni-kl.devoid 24312027Sjungma@eit.uni-kl.desc_phash_base::copy( const sc_phash_base* b ) 24412027Sjungma@eit.uni-kl.de{ 24512027Sjungma@eit.uni-kl.de erase(); 24612027Sjungma@eit.uni-kl.de iterator iter((sc_phash_base*) b); /* cast away the const */ 24712027Sjungma@eit.uni-kl.de for ( ; ! iter.empty(); iter++) 24812027Sjungma@eit.uni-kl.de insert( iter.key(), iter.contents() ); 24912027Sjungma@eit.uni-kl.de} 25012027Sjungma@eit.uni-kl.de 25112027Sjungma@eit.uni-kl.devoid 25212027Sjungma@eit.uni-kl.desc_phash_base::copy(const sc_phash_base& b, void* (*kdup)(const void*), void (*kfree)(void*)) 25312027Sjungma@eit.uni-kl.de{ 25412027Sjungma@eit.uni-kl.de erase(kfree); 25512027Sjungma@eit.uni-kl.de iterator iter((sc_phash_base&) b); 25612027Sjungma@eit.uni-kl.de for ( ; ! iter.empty(); iter++) 25712027Sjungma@eit.uni-kl.de insert( (*kdup)(iter.key()), iter.contents() ); 25812027Sjungma@eit.uni-kl.de} 25912027Sjungma@eit.uni-kl.de 26012027Sjungma@eit.uni-kl.deint 26112027Sjungma@eit.uni-kl.desc_phash_base::insert( void* k, void* c ) 26212027Sjungma@eit.uni-kl.de{ 26312027Sjungma@eit.uni-kl.de unsigned hash_val = do_hash(k); 26412027Sjungma@eit.uni-kl.de sc_phash_elem* ptr = find_entry( hash_val, k ); 26512027Sjungma@eit.uni-kl.de if (ptr == 0) { 26612027Sjungma@eit.uni-kl.de (void) add_direct(k, c, hash_val); 26712027Sjungma@eit.uni-kl.de return 0; 26812027Sjungma@eit.uni-kl.de } 26912027Sjungma@eit.uni-kl.de else { 27012027Sjungma@eit.uni-kl.de ptr->contents = c; 27112027Sjungma@eit.uni-kl.de return 1; 27212027Sjungma@eit.uni-kl.de } 27312027Sjungma@eit.uni-kl.de} 27412027Sjungma@eit.uni-kl.de 27512027Sjungma@eit.uni-kl.deint 27612027Sjungma@eit.uni-kl.desc_phash_base::insert( void* k, void* c, void* (*kdup)(const void*) ) 27712027Sjungma@eit.uni-kl.de{ 27812027Sjungma@eit.uni-kl.de unsigned hash_val = do_hash(k); 27912027Sjungma@eit.uni-kl.de sc_phash_elem* ptr = find_entry( hash_val, k ); 28012027Sjungma@eit.uni-kl.de if (ptr == 0) { 28112027Sjungma@eit.uni-kl.de (void) add_direct((*kdup)(k), c, hash_val); 28212027Sjungma@eit.uni-kl.de return 0; 28312027Sjungma@eit.uni-kl.de } 28412027Sjungma@eit.uni-kl.de else { 28512027Sjungma@eit.uni-kl.de ptr->contents = c; 28612027Sjungma@eit.uni-kl.de return 1; 28712027Sjungma@eit.uni-kl.de } 28812027Sjungma@eit.uni-kl.de} 28912027Sjungma@eit.uni-kl.de 29012027Sjungma@eit.uni-kl.deint 29112027Sjungma@eit.uni-kl.desc_phash_base::insert_if_not_exists( void* k, void* c ) 29212027Sjungma@eit.uni-kl.de{ 29312027Sjungma@eit.uni-kl.de unsigned hash_val = do_hash(k); 29412027Sjungma@eit.uni-kl.de sc_phash_elem* ptr = find_entry( hash_val, k ); 29512027Sjungma@eit.uni-kl.de if (ptr == 0) { 29612027Sjungma@eit.uni-kl.de (void) add_direct( k, c, hash_val ); 29712027Sjungma@eit.uni-kl.de return 0; 29812027Sjungma@eit.uni-kl.de } 29912027Sjungma@eit.uni-kl.de else 30012027Sjungma@eit.uni-kl.de return 1; 30112027Sjungma@eit.uni-kl.de} 30212027Sjungma@eit.uni-kl.de 30312027Sjungma@eit.uni-kl.deint 30412027Sjungma@eit.uni-kl.desc_phash_base::insert_if_not_exists( void* k, void* c, void* (*kdup)(const void*) ) 30512027Sjungma@eit.uni-kl.de{ 30612027Sjungma@eit.uni-kl.de unsigned hash_val = do_hash(k); 30712027Sjungma@eit.uni-kl.de sc_phash_elem* ptr = find_entry( hash_val, k ); 30812027Sjungma@eit.uni-kl.de if (ptr == 0) { 30912027Sjungma@eit.uni-kl.de (void) add_direct( (*kdup)(k), c, hash_val ); 31012027Sjungma@eit.uni-kl.de return 0; 31112027Sjungma@eit.uni-kl.de } 31212027Sjungma@eit.uni-kl.de else 31312027Sjungma@eit.uni-kl.de return 1; 31412027Sjungma@eit.uni-kl.de} 31512027Sjungma@eit.uni-kl.de 31612027Sjungma@eit.uni-kl.deint 31712027Sjungma@eit.uni-kl.desc_phash_base::remove( const void* k ) 31812027Sjungma@eit.uni-kl.de{ 31912027Sjungma@eit.uni-kl.de unsigned hash_val = do_hash(k); 32012027Sjungma@eit.uni-kl.de sc_phash_elem** last; 32112027Sjungma@eit.uni-kl.de sc_phash_elem* ptr = find_entry( hash_val, k, &last ); 32212027Sjungma@eit.uni-kl.de 32312027Sjungma@eit.uni-kl.de if (ptr == 0) 32412027Sjungma@eit.uni-kl.de return 0; 32512027Sjungma@eit.uni-kl.de 32612027Sjungma@eit.uni-kl.de assert(*last == ptr); 32712027Sjungma@eit.uni-kl.de *last = ptr->next; 32812027Sjungma@eit.uni-kl.de delete ptr; 32912027Sjungma@eit.uni-kl.de --num_entries; 33012027Sjungma@eit.uni-kl.de return 1; 33112027Sjungma@eit.uni-kl.de} 33212027Sjungma@eit.uni-kl.de 33312027Sjungma@eit.uni-kl.deint 33412027Sjungma@eit.uni-kl.desc_phash_base::remove( const void* k, void** pk, void** pc ) 33512027Sjungma@eit.uni-kl.de{ 33612027Sjungma@eit.uni-kl.de unsigned hash_val = do_hash(k); 33712027Sjungma@eit.uni-kl.de sc_phash_elem** last; 33812027Sjungma@eit.uni-kl.de sc_phash_elem* ptr = find_entry( hash_val, k, &last ); 33912027Sjungma@eit.uni-kl.de 34012027Sjungma@eit.uni-kl.de if (ptr == 0) { 34112027Sjungma@eit.uni-kl.de *pk = 0; 34212027Sjungma@eit.uni-kl.de *pc = 0; 34312027Sjungma@eit.uni-kl.de return 0; 34412027Sjungma@eit.uni-kl.de } 34512027Sjungma@eit.uni-kl.de else { 34612027Sjungma@eit.uni-kl.de *pk = ptr->key; 34712027Sjungma@eit.uni-kl.de *pc = ptr->contents; 34812027Sjungma@eit.uni-kl.de } 34912027Sjungma@eit.uni-kl.de 35012027Sjungma@eit.uni-kl.de assert(*last == ptr); 35112027Sjungma@eit.uni-kl.de *last = ptr->next; 35212027Sjungma@eit.uni-kl.de delete ptr; 35312027Sjungma@eit.uni-kl.de --num_entries; 35412027Sjungma@eit.uni-kl.de return 1; 35512027Sjungma@eit.uni-kl.de} 35612027Sjungma@eit.uni-kl.de 35712027Sjungma@eit.uni-kl.deint 35812027Sjungma@eit.uni-kl.desc_phash_base::remove(const void* k, void (*kfree)(void*)) 35912027Sjungma@eit.uni-kl.de{ 36012027Sjungma@eit.uni-kl.de void* rk; 36112027Sjungma@eit.uni-kl.de void* rc; 36212027Sjungma@eit.uni-kl.de if (remove(k, &rk, &rc)) { 36312027Sjungma@eit.uni-kl.de (*kfree)(rk); 36412027Sjungma@eit.uni-kl.de return 1; 36512027Sjungma@eit.uni-kl.de } 36612027Sjungma@eit.uni-kl.de else 36712027Sjungma@eit.uni-kl.de return 0; 36812027Sjungma@eit.uni-kl.de} 36912027Sjungma@eit.uni-kl.de 37012027Sjungma@eit.uni-kl.deint 37112027Sjungma@eit.uni-kl.desc_phash_base::remove_by_contents( const void* c ) 37212027Sjungma@eit.uni-kl.de{ 37312027Sjungma@eit.uni-kl.de sc_phash_elem** last; 37412027Sjungma@eit.uni-kl.de sc_phash_elem* ptr; 37512027Sjungma@eit.uni-kl.de 37612027Sjungma@eit.uni-kl.de int num_removed = 0; 37712027Sjungma@eit.uni-kl.de for (int i = 0; i < num_bins; ++i) { 37812027Sjungma@eit.uni-kl.de last = &(bins[i]); 37912027Sjungma@eit.uni-kl.de ptr = *last; 38012027Sjungma@eit.uni-kl.de while (ptr != 0) { 38112027Sjungma@eit.uni-kl.de if (ptr->contents != c) { 38212027Sjungma@eit.uni-kl.de last = &(ptr->next); 38312027Sjungma@eit.uni-kl.de ptr = *last; 38412027Sjungma@eit.uni-kl.de } 38512027Sjungma@eit.uni-kl.de else { 38612027Sjungma@eit.uni-kl.de *last = ptr->next; 38712027Sjungma@eit.uni-kl.de delete ptr; 38812027Sjungma@eit.uni-kl.de ptr = *last; 38912027Sjungma@eit.uni-kl.de --num_entries; 39012027Sjungma@eit.uni-kl.de ++num_removed; 39112027Sjungma@eit.uni-kl.de } 39212027Sjungma@eit.uni-kl.de } 39312027Sjungma@eit.uni-kl.de } 39412027Sjungma@eit.uni-kl.de return num_removed; 39512027Sjungma@eit.uni-kl.de} 39612027Sjungma@eit.uni-kl.de 39712027Sjungma@eit.uni-kl.deint 39812027Sjungma@eit.uni-kl.desc_phash_base::remove_by_contents( bool (*predicate)(const void* c, void* arg), void* arg ) 39912027Sjungma@eit.uni-kl.de{ 40012027Sjungma@eit.uni-kl.de sc_phash_elem** last; 40112027Sjungma@eit.uni-kl.de sc_phash_elem* ptr; 40212027Sjungma@eit.uni-kl.de 40312027Sjungma@eit.uni-kl.de int num_removed = 0; 40412027Sjungma@eit.uni-kl.de for (int i = 0; i < num_bins; ++i) { 40512027Sjungma@eit.uni-kl.de last = &(bins[i]); 40612027Sjungma@eit.uni-kl.de ptr = *last; 40712027Sjungma@eit.uni-kl.de while (ptr != 0) { 40812027Sjungma@eit.uni-kl.de if (! (*predicate)(ptr->contents, arg)) { 40912027Sjungma@eit.uni-kl.de last = &(ptr->next); 41012027Sjungma@eit.uni-kl.de ptr = *last; 41112027Sjungma@eit.uni-kl.de } 41212027Sjungma@eit.uni-kl.de else { 41312027Sjungma@eit.uni-kl.de *last = ptr->next; 41412027Sjungma@eit.uni-kl.de delete ptr; 41512027Sjungma@eit.uni-kl.de ptr = *last; 41612027Sjungma@eit.uni-kl.de --num_entries; 41712027Sjungma@eit.uni-kl.de ++num_removed; 41812027Sjungma@eit.uni-kl.de } 41912027Sjungma@eit.uni-kl.de } 42012027Sjungma@eit.uni-kl.de } 42112027Sjungma@eit.uni-kl.de return num_removed; 42212027Sjungma@eit.uni-kl.de} 42312027Sjungma@eit.uni-kl.de 42412027Sjungma@eit.uni-kl.deint 42512027Sjungma@eit.uni-kl.desc_phash_base::remove_by_contents( const void* c, void (*kfree)(void*) ) 42612027Sjungma@eit.uni-kl.de{ 42712027Sjungma@eit.uni-kl.de sc_phash_elem** last; 42812027Sjungma@eit.uni-kl.de sc_phash_elem* ptr; 42912027Sjungma@eit.uni-kl.de 43012027Sjungma@eit.uni-kl.de int num_removed = 0; 43112027Sjungma@eit.uni-kl.de for (int i = 0; i < num_bins; ++i) { 43212027Sjungma@eit.uni-kl.de last = &(bins[i]); 43312027Sjungma@eit.uni-kl.de ptr = *last; 43412027Sjungma@eit.uni-kl.de while (ptr != 0) { 43512027Sjungma@eit.uni-kl.de if (ptr->contents != c) { 43612027Sjungma@eit.uni-kl.de last = &(ptr->next); 43712027Sjungma@eit.uni-kl.de ptr = *last; 43812027Sjungma@eit.uni-kl.de } 43912027Sjungma@eit.uni-kl.de else { 44012027Sjungma@eit.uni-kl.de *last = ptr->next; 44112027Sjungma@eit.uni-kl.de (*kfree)(ptr->key); 44212027Sjungma@eit.uni-kl.de delete ptr; 44312027Sjungma@eit.uni-kl.de ptr = *last; 44412027Sjungma@eit.uni-kl.de --num_entries; 44512027Sjungma@eit.uni-kl.de ++num_removed; 44612027Sjungma@eit.uni-kl.de } 44712027Sjungma@eit.uni-kl.de } 44812027Sjungma@eit.uni-kl.de } 44912027Sjungma@eit.uni-kl.de return num_removed; 45012027Sjungma@eit.uni-kl.de} 45112027Sjungma@eit.uni-kl.de 45212027Sjungma@eit.uni-kl.deint 45312027Sjungma@eit.uni-kl.desc_phash_base::remove_by_contents( bool (*predicate)(const void*, void*), void* arg, void (*kfree)(void*)) 45412027Sjungma@eit.uni-kl.de{ 45512027Sjungma@eit.uni-kl.de sc_phash_elem** last; 45612027Sjungma@eit.uni-kl.de sc_phash_elem* ptr; 45712027Sjungma@eit.uni-kl.de 45812027Sjungma@eit.uni-kl.de int num_removed = 0; 45912027Sjungma@eit.uni-kl.de for (int i = 0; i < num_bins; ++i) { 46012027Sjungma@eit.uni-kl.de last = &(bins[i]); 46112027Sjungma@eit.uni-kl.de ptr = *last; 46212027Sjungma@eit.uni-kl.de while (ptr != 0) { 46312027Sjungma@eit.uni-kl.de if (! (*predicate)(ptr->contents, arg)) { 46412027Sjungma@eit.uni-kl.de last = &(ptr->next); 46512027Sjungma@eit.uni-kl.de ptr = *last; 46612027Sjungma@eit.uni-kl.de } 46712027Sjungma@eit.uni-kl.de else { 46812027Sjungma@eit.uni-kl.de *last = ptr->next; 46912027Sjungma@eit.uni-kl.de (*kfree)(ptr->key); 47012027Sjungma@eit.uni-kl.de delete ptr; 47112027Sjungma@eit.uni-kl.de ptr = *last; 47212027Sjungma@eit.uni-kl.de --num_entries; 47312027Sjungma@eit.uni-kl.de ++num_removed; 47412027Sjungma@eit.uni-kl.de } 47512027Sjungma@eit.uni-kl.de } 47612027Sjungma@eit.uni-kl.de } 47712027Sjungma@eit.uni-kl.de return num_removed; 47812027Sjungma@eit.uni-kl.de} 47912027Sjungma@eit.uni-kl.de 48012027Sjungma@eit.uni-kl.deint 48112027Sjungma@eit.uni-kl.desc_phash_base::lookup( const void* k, void** c_ptr ) const 48212027Sjungma@eit.uni-kl.de{ 48312027Sjungma@eit.uni-kl.de unsigned hash_val = do_hash(k); 48412027Sjungma@eit.uni-kl.de sc_phash_elem* ptr = find_entry( hash_val, k ); 48512027Sjungma@eit.uni-kl.de if (ptr == 0) { 48612027Sjungma@eit.uni-kl.de if (c_ptr != 0) *c_ptr = default_value; 48712027Sjungma@eit.uni-kl.de return 0; 48812027Sjungma@eit.uni-kl.de } 48912027Sjungma@eit.uni-kl.de else { 49012027Sjungma@eit.uni-kl.de if (c_ptr != 0) *c_ptr = ptr->contents; 49112027Sjungma@eit.uni-kl.de return 1; 49212027Sjungma@eit.uni-kl.de } 49312027Sjungma@eit.uni-kl.de} 49412027Sjungma@eit.uni-kl.de 49512027Sjungma@eit.uni-kl.devoid* 49612027Sjungma@eit.uni-kl.desc_phash_base::operator[]( const void* key ) const 49712027Sjungma@eit.uni-kl.de{ 49812027Sjungma@eit.uni-kl.de void* contents; 49912027Sjungma@eit.uni-kl.de lookup( key, &contents ); 50012027Sjungma@eit.uni-kl.de return contents; 50112027Sjungma@eit.uni-kl.de} 50212027Sjungma@eit.uni-kl.de 50312027Sjungma@eit.uni-kl.de/***************************************************************************/ 50412027Sjungma@eit.uni-kl.de 50512027Sjungma@eit.uni-kl.devoid 50612027Sjungma@eit.uni-kl.desc_phash_base_iter::reset( sc_phash_base* t ) 50712027Sjungma@eit.uni-kl.de{ 50812027Sjungma@eit.uni-kl.de table = t; 50912027Sjungma@eit.uni-kl.de index = 0; 51012027Sjungma@eit.uni-kl.de entry = 0; 51112027Sjungma@eit.uni-kl.de next = 0; 51212027Sjungma@eit.uni-kl.de 51312027Sjungma@eit.uni-kl.de for (int i = index; i < table->num_bins; ++i) { 51412027Sjungma@eit.uni-kl.de if (table->bins[i] != 0) { 51512027Sjungma@eit.uni-kl.de index = i + 1; 51612027Sjungma@eit.uni-kl.de last = &(table->bins[i]); 51712027Sjungma@eit.uni-kl.de entry = *last; 51812027Sjungma@eit.uni-kl.de next = entry->next; 51912027Sjungma@eit.uni-kl.de break; 52012027Sjungma@eit.uni-kl.de } 52112027Sjungma@eit.uni-kl.de } 52212027Sjungma@eit.uni-kl.de} 52312027Sjungma@eit.uni-kl.de 52412027Sjungma@eit.uni-kl.debool 52512027Sjungma@eit.uni-kl.desc_phash_base_iter::empty() const 52612027Sjungma@eit.uni-kl.de{ 52712027Sjungma@eit.uni-kl.de return (entry == 0); 52812027Sjungma@eit.uni-kl.de} 52912027Sjungma@eit.uni-kl.de 53012027Sjungma@eit.uni-kl.devoid 53112027Sjungma@eit.uni-kl.desc_phash_base_iter::step() 53212027Sjungma@eit.uni-kl.de{ 53312027Sjungma@eit.uni-kl.de if (entry) { 53412027Sjungma@eit.uni-kl.de last = &(entry->next); 53512027Sjungma@eit.uni-kl.de } 53612027Sjungma@eit.uni-kl.de entry = next; 53712027Sjungma@eit.uni-kl.de if (! entry) { 53812027Sjungma@eit.uni-kl.de for (int i = index; i < table->num_bins; ++i) { 53912027Sjungma@eit.uni-kl.de if (table->bins[i] != 0) { 54012027Sjungma@eit.uni-kl.de index = i + 1; 54112027Sjungma@eit.uni-kl.de last = &(table->bins[i]); 54212027Sjungma@eit.uni-kl.de entry = *last; 54312027Sjungma@eit.uni-kl.de next = entry->next; 54412027Sjungma@eit.uni-kl.de break; 54512027Sjungma@eit.uni-kl.de } 54612027Sjungma@eit.uni-kl.de } 54712027Sjungma@eit.uni-kl.de } 54812027Sjungma@eit.uni-kl.de else { 54912027Sjungma@eit.uni-kl.de next = entry->next; 55012027Sjungma@eit.uni-kl.de } 55112027Sjungma@eit.uni-kl.de} 55212027Sjungma@eit.uni-kl.de 55312027Sjungma@eit.uni-kl.devoid 55412027Sjungma@eit.uni-kl.desc_phash_base_iter::remove() 55512027Sjungma@eit.uni-kl.de{ 55612027Sjungma@eit.uni-kl.de delete entry; 55712027Sjungma@eit.uni-kl.de *last = next; 55812027Sjungma@eit.uni-kl.de entry = 0; 55912027Sjungma@eit.uni-kl.de --table->num_entries; 56012027Sjungma@eit.uni-kl.de step(); 56112027Sjungma@eit.uni-kl.de} 56212027Sjungma@eit.uni-kl.de 56312027Sjungma@eit.uni-kl.devoid 56412027Sjungma@eit.uni-kl.desc_phash_base_iter::remove(void (*kfree)(void*)) 56512027Sjungma@eit.uni-kl.de{ 56612027Sjungma@eit.uni-kl.de (*kfree)(entry->key); 56712027Sjungma@eit.uni-kl.de delete entry; 56812027Sjungma@eit.uni-kl.de *last = next; 56912027Sjungma@eit.uni-kl.de entry = 0; 57012027Sjungma@eit.uni-kl.de --table->num_entries; 57112027Sjungma@eit.uni-kl.de step(); 57212027Sjungma@eit.uni-kl.de} 57312027Sjungma@eit.uni-kl.de 57412027Sjungma@eit.uni-kl.devoid* 57512027Sjungma@eit.uni-kl.desc_phash_base_iter::key() const 57612027Sjungma@eit.uni-kl.de{ 57712027Sjungma@eit.uni-kl.de return entry->key; 57812027Sjungma@eit.uni-kl.de} 57912027Sjungma@eit.uni-kl.de 58012027Sjungma@eit.uni-kl.devoid* 58112027Sjungma@eit.uni-kl.desc_phash_base_iter::contents() const 58212027Sjungma@eit.uni-kl.de{ 58312027Sjungma@eit.uni-kl.de return entry->contents; 58412027Sjungma@eit.uni-kl.de} 58512027Sjungma@eit.uni-kl.de 58612027Sjungma@eit.uni-kl.devoid* 58712027Sjungma@eit.uni-kl.desc_phash_base_iter::set_contents( void* c ) 58812027Sjungma@eit.uni-kl.de{ 58912027Sjungma@eit.uni-kl.de return entry->contents = c; 59012027Sjungma@eit.uni-kl.de} 59112027Sjungma@eit.uni-kl.de 59212027Sjungma@eit.uni-kl.de/****************************************************************************/ 59312027Sjungma@eit.uni-kl.de 59412027Sjungma@eit.uni-kl.deunsigned 59512027Sjungma@eit.uni-kl.dedefault_ptr_hash_fn(const void* p) 59612027Sjungma@eit.uni-kl.de{ 59712027Sjungma@eit.uni-kl.de return static_cast<unsigned>(((uintptr_t)(p) >> 2) * 2654435789U); 59812027Sjungma@eit.uni-kl.de 59912027Sjungma@eit.uni-kl.de} 60012027Sjungma@eit.uni-kl.de 60112027Sjungma@eit.uni-kl.deunsigned 60212027Sjungma@eit.uni-kl.dedefault_int_hash_fn(const void* p) 60312027Sjungma@eit.uni-kl.de{ 60412027Sjungma@eit.uni-kl.de return static_cast<unsigned>((uintptr_t)(p) * 3141592661U); 60512027Sjungma@eit.uni-kl.de} 60612027Sjungma@eit.uni-kl.de 60712027Sjungma@eit.uni-kl.de 60812027Sjungma@eit.uni-kl.deunsigned 60912027Sjungma@eit.uni-kl.dedefault_str_hash_fn(const void* p) 61012027Sjungma@eit.uni-kl.de{ 61112027Sjungma@eit.uni-kl.de if (!p) return 0; 61212027Sjungma@eit.uni-kl.de 61312027Sjungma@eit.uni-kl.de const char* x = (const char*) p; 61412027Sjungma@eit.uni-kl.de unsigned int h = 0; 61512027Sjungma@eit.uni-kl.de unsigned int g; 61612027Sjungma@eit.uni-kl.de 61712027Sjungma@eit.uni-kl.de while (*x != 0) { 61812027Sjungma@eit.uni-kl.de h = (h << 4) + *x++; 61912027Sjungma@eit.uni-kl.de if ((g = h & 0xf0000000) != 0) 62012027Sjungma@eit.uni-kl.de h = (h ^ (g >> 24)) ^ g; 62112027Sjungma@eit.uni-kl.de } 62212027Sjungma@eit.uni-kl.de return h; 62312027Sjungma@eit.uni-kl.de} 62412027Sjungma@eit.uni-kl.de 62512027Sjungma@eit.uni-kl.deint 62612027Sjungma@eit.uni-kl.desc_strhash_cmp( const void* a, const void* b ) 62712027Sjungma@eit.uni-kl.de{ 62812027Sjungma@eit.uni-kl.de return strcmp( (const char*) a, (const char*) b ); 62912027Sjungma@eit.uni-kl.de} 63012027Sjungma@eit.uni-kl.de 63112027Sjungma@eit.uni-kl.devoid* 63212027Sjungma@eit.uni-kl.desc_strhash_kdup(const void* k) 63312027Sjungma@eit.uni-kl.de{ 63412027Sjungma@eit.uni-kl.de char* result = (char*) malloc( strlen((const char*)k)+1 ); 63512027Sjungma@eit.uni-kl.de strcpy(result, (const char*) k); 63612027Sjungma@eit.uni-kl.de return result; 63712027Sjungma@eit.uni-kl.de} 63812027Sjungma@eit.uni-kl.de 63912027Sjungma@eit.uni-kl.devoid 64012027Sjungma@eit.uni-kl.desc_strhash_kfree(void* k) 64112027Sjungma@eit.uni-kl.de{ 64212027Sjungma@eit.uni-kl.de if (k) free((char*) k); 64312027Sjungma@eit.uni-kl.de} 64412027Sjungma@eit.uni-kl.de } // namespace sc_core 64512027Sjungma@eit.uni-kl.de 64612027Sjungma@eit.uni-kl.de// $Log: sc_hash.cpp,v $ 64712027Sjungma@eit.uni-kl.de// Revision 1.5 2011/08/26 20:42:30 acg 64812027Sjungma@eit.uni-kl.de// Andy Goodrich: 64912027Sjungma@eit.uni-kl.de// (1) Replaced strdup with new and strcpy to eliminate issue with the 65012027Sjungma@eit.uni-kl.de// Greenhills compiler. 65112027Sjungma@eit.uni-kl.de// (2) Moved modification log to the end of the file to eliminate line 65212027Sjungma@eit.uni-kl.de// skew when check-ins are done. 65312027Sjungma@eit.uni-kl.de// 65412027Sjungma@eit.uni-kl.de// Revision 1.4 2011/08/24 22:05:56 acg 65512027Sjungma@eit.uni-kl.de// Torsten Maehne: initialization changes to remove warnings. 65612027Sjungma@eit.uni-kl.de// 65712027Sjungma@eit.uni-kl.de// Revision 1.3 2011/05/05 17:46:04 acg 65812027Sjungma@eit.uni-kl.de// Philip A. Hartmann: changes in "swap" support. 65912027Sjungma@eit.uni-kl.de// 66012027Sjungma@eit.uni-kl.de// Revision 1.2 2011/02/18 20:38:43 acg 66112027Sjungma@eit.uni-kl.de// Andy Goodrich: Updated Copyright notice. 66212027Sjungma@eit.uni-kl.de// 66312027Sjungma@eit.uni-kl.de// Revision 1.1.1.1 2006/12/15 20:20:06 acg 66412027Sjungma@eit.uni-kl.de// SystemC 2.3 66512027Sjungma@eit.uni-kl.de// 66612027Sjungma@eit.uni-kl.de// Revision 1.3 2006/01/13 18:53:10 acg 66712027Sjungma@eit.uni-kl.de// Andy Goodrich: Added $Log command so that CVS comments are reproduced in 66812027Sjungma@eit.uni-kl.de// the source. 66912027Sjungma@eit.uni-kl.de 67012027Sjungma@eit.uni-kl.de// taf 671