Shad Ansari | 2f7f9be | 2017-06-07 13:34:53 -0700 | [diff] [blame^] | 1 | /* |
| 2 | <:copyright-BRCM:2016:DUAL/GPL:standard |
| 3 | |
| 4 | Broadcom Proprietary and Confidential.(c) 2016 Broadcom |
| 5 | All Rights Reserved |
| 6 | |
| 7 | Unless you and Broadcom execute a separate written software license |
| 8 | agreement governing use of this software, this software is licensed |
| 9 | to you under the terms of the GNU General Public License version 2 |
| 10 | (the "GPL"), available at http://www.broadcom.com/licenses/GPLv2.php, |
| 11 | with the following added to such license: |
| 12 | |
| 13 | As a special exception, the copyright holders of this software give |
| 14 | you permission to link this software with independent modules, and |
| 15 | to copy and distribute the resulting executable under terms of your |
| 16 | choice, provided that you also meet, for each linked independent |
| 17 | module, the terms and conditions of the license of that module. |
| 18 | An independent module is a module which is not derived from this |
| 19 | software. The special exception does not apply to any modifications |
| 20 | of the software. |
| 21 | |
| 22 | Not withstanding the above, under no circumstances may you combine |
| 23 | this software in any way with any other Broadcom software provided |
| 24 | under a license other than the GPL, without Broadcom's express prior |
| 25 | written consent. |
| 26 | |
| 27 | :> |
| 28 | */ |
| 29 | |
| 30 | #ifndef BCMOS_HASH_TABLE_H_ |
| 31 | #define BCMOS_HASH_TABLE_H_ |
| 32 | |
| 33 | #include "bcmos_system.h" |
| 34 | |
| 35 | typedef struct ht_block ht_block; |
| 36 | struct ht_block |
| 37 | { |
| 38 | ht_block *next_chain; |
| 39 | }; |
| 40 | |
| 41 | typedef struct |
| 42 | { |
| 43 | uint16_t obj_len; |
| 44 | uint8_t key_len; |
| 45 | uint32_t data_offset; |
| 46 | uint32_t ht_lookup_tbl_entries; |
| 47 | uint32_t ht_max_data_entries; |
| 48 | bcmos_blk_pool key_data_pool; |
| 49 | ht_block *look_up_entries_tbl; |
| 50 | uint32_t ht_cur_entries; |
| 51 | } hash_table; |
| 52 | |
| 53 | typedef struct |
| 54 | { |
| 55 | const hash_table *ht; |
| 56 | uint32_t cur_idx; |
| 57 | ht_block *cur_block; |
| 58 | bcmos_bool removed_at; |
| 59 | bcmos_bool still_valid; |
| 60 | } ht_iterator; |
| 61 | |
| 62 | /** Create a hash table |
| 63 | * \param[in] max_data_entries Maximum entries the hash table needs to hold |
| 64 | * \param[in] entry_size Size of each entry in bytes |
| 65 | * \param[in] key_size Size of each key in bytes |
| 66 | * \param[in] pool_name Friendly name to identify the hash table's memory pool |
| 67 | * \return pointer to newly created hash table |
| 68 | */ |
| 69 | hash_table *hash_table_create(uint32_t max_data_entries, |
| 70 | uint16_t entry_size, |
| 71 | uint8_t key_size, |
| 72 | char *pool_name); |
| 73 | |
| 74 | /** Removes all entries from a HashTable. |
| 75 | * \param[in] ht Hash table to remove all entries from |
| 76 | */ |
| 77 | void hash_table_clear(hash_table *ht); |
| 78 | |
| 79 | /** Gets a pointer to an entry within the hash table (if exists) |
| 80 | * \param[in] ht Hashtable in question |
| 81 | * \param[in] key Key to look for. |
| 82 | * \return Non null if we found a data item associated with KEY. |
| 83 | */ |
| 84 | void *hash_table_get(const hash_table *ht, const uint8_t *key); |
| 85 | |
| 86 | /** Returns pointers to the key and value that an iterator is pointing at. Warning: key may not be uint32_t aligned. |
| 87 | * DO NOT DELETE THE ELEMENT THE ITERATOR POINTS AT AND AND TRY TO USE THE ITERATOR SUBSEQUENTLY. If you need to do |
| 88 | * this use ht_iterator_remove_at |
| 89 | * \param[in] hti Iterator |
| 90 | * \param[in] key Pointer to key to fill |
| 91 | * \param[in] obj Pointer to obj to fill. |
| 92 | */ |
| 93 | void ht_iterator_deref(const ht_iterator *hti, uint8_t **key, void **obj); |
| 94 | |
| 95 | /** Get an interator for traversing a hashtable. |
| 96 | * \param[in] ht Hashtable to traverse |
| 97 | * \return The iterator. |
| 98 | */ |
| 99 | ht_iterator ht_iterator_get(const hash_table *ht); |
| 100 | |
| 101 | /** Get an interator for traversing a hashtable based on an entry's key. |
| 102 | * \param[in] ht Hashtable to traverse |
| 103 | * \param[in] key key of entry to return |
| 104 | * \return The iterator. |
| 105 | */ |
| 106 | ht_iterator ht_iterator_get_by_key(const hash_table *ht, const uint8_t *key); |
| 107 | |
| 108 | /** Advances a HashTable iterator to the next location within the HashTable. |
| 109 | * \param[in] it Iterator to advance |
| 110 | * \return TRUE if there was a next element |
| 111 | */ |
| 112 | bcmos_bool ht_iterator_next(ht_iterator *it); |
| 113 | |
| 114 | /** Deletes the entry where the iterator points to and advances the iterator returning whether the advance worked or |
| 115 | * not. |
| 116 | * \param[in] ht Writable reference to the hash table (the iterator only has read permission) |
| 117 | * \param[in] it Itreator pointing at entry to delete. |
| 118 | */ |
| 119 | void ht_iterator_remove_at(hash_table *ht, ht_iterator *it); |
| 120 | |
| 121 | /** Attempts to associate key with val in the hash table. If key already exists overwrites what was at key with val. |
| 122 | * Otherwise allocates an entry within the hashtable for key and copies val into it. |
| 123 | * \param[in] ht Hashtable to add or modify |
| 124 | * \param[in] key Key to try and associate with val. |
| 125 | * \param[in] val Val to associate |
| 126 | * \return NULL if fail, else pointer to just added block. |
| 127 | */ |
| 128 | void *hash_table_put(hash_table *ht, const uint8_t *key, const void *val); |
| 129 | |
| 130 | /** Removes an entry (if exists) from the hash table. |
| 131 | * \param[in] ht HashTable to remove from. |
| 132 | * \param[in] key Key to remove |
| 133 | * \return BCMOS_TRUE if anything was removed, otherwise BCMOS_FALSE. |
| 134 | */ |
| 135 | bcmos_bool hash_table_remove(hash_table *ht, const uint8_t *key); |
| 136 | |
| 137 | #endif /* Hash.h */ |