| /* |
| <:copyright-BRCM:2016:DUAL/GPL:standard |
| |
| Broadcom Proprietary and Confidential.(c) 2016 Broadcom |
| All Rights Reserved |
| |
| Unless you and Broadcom execute a separate written software license |
| agreement governing use of this software, this software is licensed |
| to you under the terms of the GNU General Public License version 2 |
| (the "GPL"), available at http://www.broadcom.com/licenses/GPLv2.php, |
| with the following added to such license: |
| |
| As a special exception, the copyright holders of this software give |
| you permission to link this software with independent modules, and |
| to copy and distribute the resulting executable under terms of your |
| choice, provided that you also meet, for each linked independent |
| module, the terms and conditions of the license of that module. |
| An independent module is a module which is not derived from this |
| software. The special exception does not apply to any modifications |
| of the software. |
| |
| Not withstanding the above, under no circumstances may you combine |
| this software in any way with any other Broadcom software provided |
| under a license other than the GPL, without Broadcom's express prior |
| written consent. |
| |
| :> |
| */ |
| #include "bcmos_hash_table.h" |
| |
| #define ht_overhead sizeof(void *) |
| |
| /** Create a hash table using a block pool |
| * \param[in] pool_parm pointer to block pool parameters |
| * \param[in] max_data_entries Maximum entries the hash table needs to hold |
| * \param[in] entry_size Size of each entry in bytes |
| * \param[in] key_size Size of each key in bytes |
| * \return pointer to newly created hash table |
| */ |
| static hash_table *hash_table_create_in_pool(bcmos_blk_pool_parm *pool_parm, |
| uint32_t max_data_entries, |
| uint16_t entry_size, |
| uint8_t key_size) |
| { |
| uint32_t lookup_table_entries = max_data_entries + (max_data_entries / 4); |
| hash_table *ht; |
| bcmos_errno err; |
| |
| if (pool_parm == NULL) |
| { |
| BUG(); |
| return NULL; |
| } |
| |
| entry_size += key_size; |
| |
| ht = bcmos_alloc(sizeof(hash_table)); |
| if (ht == NULL) |
| { |
| BUG(); |
| return NULL; |
| } |
| |
| ht->obj_len = entry_size; |
| ht->key_len = key_size; |
| ht->data_offset = ht_overhead; |
| ht->ht_lookup_tbl_entries = lookup_table_entries; |
| ht->ht_max_data_entries = max_data_entries; |
| ht->look_up_entries_tbl = bcmos_alloc(lookup_table_entries * sizeof(ht_block)); |
| |
| if (ht->look_up_entries_tbl == NULL) |
| { |
| bcmos_free(ht); |
| BUG(); |
| return NULL; |
| } |
| |
| ht->ht_cur_entries = 0; |
| err = bcmos_blk_pool_create(&ht->key_data_pool, pool_parm); |
| |
| if (err != BCM_ERR_OK) |
| { |
| bcmos_free(ht->look_up_entries_tbl); |
| bcmos_free(ht); |
| BUG(); |
| return NULL; |
| } |
| |
| if (ht->ht_max_data_entries > ht->ht_lookup_tbl_entries) |
| { |
| BUG(); |
| } |
| |
| ht->obj_len -= ht->key_len; |
| |
| memset(ht->look_up_entries_tbl, 0, lookup_table_entries * sizeof(ht_block)); |
| return ht; |
| } |
| |
| hash_table *hash_table_create(uint32_t max_data_entries, |
| uint16_t entry_size, |
| uint8_t key_size, |
| char *pool_name) |
| { |
| bcmos_blk_pool_parm parm = {0}; |
| |
| parm.name = pool_name; |
| parm.blk_size = entry_size + key_size + ht_overhead; |
| parm.num_blks = max_data_entries; |
| |
| return hash_table_create_in_pool(&parm, max_data_entries, entry_size, key_size); |
| } |
| |
| /** Hash a length of bytes into a uint32_t |
| * \param[in] key Bytes to hash |
| * \param[in] len Number of bytes in key |
| * \return The hash as a uint32_t |
| */ |
| static uint32_t get_hash_for_key(const uint8_t *key, uint8_t len) |
| { |
| uint32_t hash = 5381; |
| uint8_t i; |
| const uint8_t *tmp = key; |
| for (i = 0; i < len; tmp++, i++) |
| { |
| hash = ((hash << 5) + hash) + (*tmp); |
| } |
| |
| return hash; |
| } |
| |
| /** Gets a hash key used for the keyDataPool in the HashTable |
| * \param[in] ht Associated hashtable we are getting hash for key for |
| * \param[in] key Key we are getting hash for |
| * \return An index into the keyDataPool |
| */ |
| static uint32_t get_hash_val_for_key(const hash_table *ht, const uint8_t *key) |
| { |
| return get_hash_for_key(key, ht->key_len) % ht->ht_lookup_tbl_entries; |
| } |
| |
| /** Returns the location of the key within an HtBlock |
| * \param[in] ht Hash table in question |
| * \param[in] block HtBlock in question |
| * \return pointer to the data within the block |
| */ |
| static uint8_t *get_key_from_block_in_table(const hash_table *ht, ht_block *block) |
| { |
| return(uint8_t *) block + ht->data_offset + ht->obj_len; |
| } |
| |
| /** Gets and populates a HtBlock with all of its data |
| * \param[in] next Next block in this buckets chain |
| * \param[in] ht Hash table in question |
| * \param[in] key This blocks key |
| * \param[in] val This blocks data |
| * \return The block that we allocated and returned |
| */ |
| static ht_block *fill_ht_block(ht_block *next, |
| hash_table *ht, |
| const uint8_t *key, |
| const void *val) |
| { |
| ht_block *dest_block = bcmos_blk_pool_alloc(&ht->key_data_pool); |
| |
| if (dest_block != NULL) |
| { |
| /* storage is nextobj ptr, hash obj, |
| key which keeps all uint32_t aligned. */ |
| dest_block->next_chain = next; |
| |
| if (val != NULL) |
| { |
| memcpy((uint8_t *) dest_block + ht->data_offset, val, ht->obj_len); |
| } |
| else |
| { |
| memset((uint8_t *) dest_block + ht->data_offset,0,ht->obj_len); |
| } |
| |
| /* Need to put key in after obj */ |
| memcpy( |
| (uint8_t *) dest_block + ht->data_offset + ht->obj_len, |
| key, |
| ht->key_len); |
| } |
| |
| return dest_block; |
| } |
| |
| /** Determine whether two keys in a particular hash table match |
| * \param[in] ht Hashtable |
| * \param[in] key_a first key to compare |
| * \param[in] key_b second key to compare |
| * \return whether they are the same |
| */ |
| static bcmos_bool is_key_match(const hash_table *ht, const uint8_t *key_a, const uint8_t *key_b) |
| { |
| return memcmp(key_a, key_b, ht->key_len) == 0; |
| } |
| |
| /** Searches a chained bucket looking for an instance of the key. If found returns the block if found the key in. |
| * Prev guy is set to the block in the chain before the block we returned (except in the case * where there is no |
| * block before the one we returned. |
| * \param[in] ht HashTable in question |
| * \param[in] key_to_find Key we wonder if exists |
| * \param[in] chain_start Where to start looking in the chain |
| * \param[in] prev_block The previous guy before the block we returned (if exists) |
| * \return The block that matches doesExists (if exists) |
| */ |
| static ht_block *get_key_loc_in_chain( |
| const hash_table *ht, |
| const uint8_t *key_to_find, |
| ht_block *chain_start, |
| ht_block **prev_block) |
| { |
| *prev_block = NULL; |
| while (chain_start != NULL) |
| { |
| if (is_key_match(ht, key_to_find, get_key_from_block_in_table(ht, chain_start))) |
| { |
| return chain_start; |
| } |
| *prev_block = chain_start; |
| chain_start = chain_start->next_chain; |
| } |
| return NULL; |
| } |
| |
| bcmos_bool hash_table_remove(hash_table *ht, const uint8_t *key) |
| { |
| uint32_t hash_val = get_hash_val_for_key(ht, key); |
| ht_block *prev_entry; |
| ht_block *entry = get_key_loc_in_chain( |
| ht, |
| key, |
| ht->look_up_entries_tbl[hash_val].next_chain, |
| &prev_entry); |
| |
| if (entry == NULL) |
| { |
| /* No one to delete */ |
| return BCMOS_FALSE; |
| } |
| else |
| { |
| ht->ht_cur_entries--; |
| if (prev_entry == NULL) |
| { |
| /* last entry */ |
| ht->look_up_entries_tbl[hash_val].next_chain = entry->next_chain; |
| } |
| else |
| { |
| prev_entry->next_chain = entry->next_chain; |
| } |
| bcmos_blk_pool_free(entry); |
| return BCMOS_TRUE; |
| } |
| } |
| |
| /** Returns a pointer to the data within the HT |
| * \param[in] ht Hashtable in question |
| * \param[in] block_ptr HtBlock that we wonder where its data is |
| */ |
| static void *get_ht_data_ptr(const hash_table *ht, ht_block *block_ptr) |
| { |
| return(uint8_t*)block_ptr + ht->data_offset; |
| } |
| |
| |
| /** Get an entry in the hash table |
| * \param[in] ht pointer to hash table |
| * \param[in] key pointer to key data |
| * \param[in] hash_val hash value of key |
| * \return pointer to hash table entry |
| */ |
| static inline void *ht_get_internal(const hash_table *ht, |
| const uint8_t *key, |
| uint32_t hash_val) |
| { |
| ht_block *tmp; |
| ht_block *ret; |
| ret = get_key_loc_in_chain( |
| ht, |
| key, |
| ht->look_up_entries_tbl[hash_val].next_chain, |
| &tmp); |
| if (ret != NULL) |
| { |
| return get_ht_data_ptr(ht,ret); |
| } |
| else |
| { |
| return ret; |
| } |
| } |
| |
| void *hash_table_get(const hash_table *ht, const uint8_t *key) |
| { |
| uint32_t hashVal = get_hash_val_for_key(ht, key); |
| return ht_get_internal(ht,key,hashVal); |
| } |
| |
| void *hash_table_put(hash_table *ht, const uint8_t *key, const void *val) |
| { |
| void *ret_block; |
| uint32_t hash_val; |
| if (ht->ht_cur_entries >= ht->ht_max_data_entries) |
| { |
| return NULL; |
| } |
| hash_val = get_hash_val_for_key(ht, key); |
| |
| ret_block = ht_get_internal((const hash_table *) ht, key, hash_val); |
| if (ret_block != NULL) |
| { |
| /* replace existing value with new value */ |
| if (val != NULL) |
| { |
| memcpy(ret_block, val, ht->obj_len); |
| } |
| else |
| { |
| memset(ret_block, 0, ht->obj_len); |
| } |
| return ret_block; |
| } |
| else |
| { |
| ht_block *new_block=fill_ht_block( |
| ht->look_up_entries_tbl[hash_val].next_chain, ht, key, val); |
| if (new_block != NULL) |
| { |
| ht->look_up_entries_tbl[hash_val].next_chain = new_block; |
| ht->ht_cur_entries++; |
| return get_ht_data_ptr(ht,new_block); |
| } |
| else |
| { |
| return NULL; |
| } |
| } |
| |
| } |
| |
| ht_iterator ht_iterator_get(const hash_table *ht) |
| { |
| ht_iterator to_ret; |
| to_ret.ht = ht; |
| to_ret.cur_idx = 0; |
| to_ret.removed_at = BCMOS_FALSE; |
| to_ret.still_valid = BCMOS_TRUE; |
| to_ret.cur_block = NULL; |
| return to_ret; |
| } |
| |
| ht_iterator ht_iterator_get_by_key(const hash_table *ht, const uint8_t *key) |
| { |
| ht_block *tmp; |
| uint32_t hash_val = get_hash_val_for_key(ht, key); |
| ht_iterator to_ret = {}; |
| to_ret.ht = ht; |
| to_ret.removed_at = BCMOS_FALSE; |
| to_ret.cur_block = get_key_loc_in_chain(ht, key, ht->look_up_entries_tbl[hash_val].next_chain, &tmp); |
| to_ret.still_valid = (to_ret.cur_block != NULL); |
| to_ret.cur_idx = hash_val; |
| |
| return to_ret; |
| } |
| |
| /** Advance linear scan iterator |
| * \param[in] it Iterator to advance |
| */ |
| static void ht_iterator_scan_adv(ht_iterator *it) |
| { |
| if (it->cur_block != NULL) |
| { |
| it->cur_block = it->cur_block->next_chain; |
| if (it->cur_block != NULL) |
| { |
| it->still_valid = BCMOS_TRUE; |
| return; |
| } |
| else |
| { |
| it->cur_idx++; |
| } |
| } |
| /* find non null entry */ |
| while (it->cur_idx < it->ht->ht_lookup_tbl_entries) |
| { |
| if (it->ht->look_up_entries_tbl[it->cur_idx].next_chain != NULL) |
| { |
| it->cur_block = it->ht->look_up_entries_tbl[it->cur_idx].next_chain; |
| it->still_valid = BCMOS_TRUE; |
| return; |
| } |
| else |
| { |
| it->cur_idx++; |
| } |
| } |
| it->still_valid = BCMOS_FALSE; |
| } |
| |
| void ht_iterator_deref(const ht_iterator *hti, uint8_t **key, void **obj) |
| { |
| if (!hti->still_valid) |
| { |
| BCMOS_TRACE_ERR("%s: Invalid deref\n", __FUNCTION__); |
| } |
| else |
| { |
| *key = get_key_from_block_in_table(hti->ht, hti->cur_block); |
| *obj = get_ht_data_ptr(hti->ht, hti->cur_block); /* to data */ |
| } |
| } |
| |
| void ht_iterator_remove_at(hash_table *ht, ht_iterator *it) |
| { |
| if (ht != it->ht) |
| { |
| BCMOS_TRACE_ERR("%s: Incorrect writeable hash table pointer\n", __FUNCTION__); |
| } |
| else if (it->removed_at) |
| { |
| BCMOS_TRACE_ERR("%s: No delete twice\n", __FUNCTION__); |
| } |
| else |
| { |
| uint8_t *key; |
| uint8_t *obj; |
| ht_iterator_deref(it, &key, (void **) &obj); |
| it->removed_at = BCMOS_TRUE; |
| it->still_valid = ht_iterator_next(it); |
| if (!hash_table_remove(ht, key)) |
| { |
| BCMOS_TRACE_ERR("%s: Remove error\n", __FUNCTION__); |
| } |
| } |
| } |
| |
| bcmos_bool ht_iterator_next(ht_iterator *it) |
| { |
| if (it->still_valid) |
| { |
| if (it->removed_at) |
| { |
| it->removed_at = BCMOS_FALSE; |
| } |
| else |
| { |
| ht_iterator_scan_adv(it); |
| } |
| } |
| return it->still_valid; /* No entry found */ |
| } |
| |
| void hash_table_clear(hash_table *ht) |
| { |
| ht_iterator it = ht_iterator_get(ht); |
| while (ht_iterator_next(&it)) |
| { |
| ht_iterator_remove_at(ht, &it); |
| } |
| } |