1 /* 2 * Copyright (c) 2015 Cray Inc. All rights reserved. 3 * 4 * This software is available to you under a choice of one of two 5 * licenses. You may choose to be licensed under the terms of the GNU 6 * General Public License (GPL) Version 2, available from the file 7 * COPYING in the main directory of this source tree, or the 8 * BSD license below: 9 * 10 * Redistribution and use in source and binary forms, with or 11 * without modification, are permitted provided that the following 12 * conditions are met: 13 * 14 * - Redistributions of source code must retain the above 15 * copyright notice, this list of conditions and the following 16 * disclaimer. 17 * 18 * - Redistributions in binary form must reproduce the above 19 * copyright notice, this list of conditions and the following 20 * disclaimer in the documentation and/or other materials 21 * provided with the distribution. 22 * 23 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 24 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 25 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 26 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 27 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 28 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 29 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 30 * SOFTWARE. 31 */ 32 33 #ifndef GNIX_HASHTABLE_H_ 34 #define GNIX_HASHTABLE_H_ 35 36 #include <stdint.h> 37 #include <pthread.h> 38 39 #include <ofi.h> 40 #include <ofi_list.h> 41 42 #include "gnix_util.h" 43 44 typedef uint64_t gnix_ht_key_t; 45 46 typedef enum gnix_ht_state { 47 GNIX_HT_STATE_UNINITIALIZED = 0, 48 GNIX_HT_STATE_READY, 49 GNIX_HT_STATE_DEAD, 50 } gnix_ht_state_e; 51 52 typedef struct gnix_ht_entry { 53 struct dlist_entry entry; 54 gnix_ht_key_t key; 55 void *value; 56 } gnix_ht_entry_t; 57 58 typedef struct gnix_ht_lk_lh { 59 rwlock_t lh_lock; 60 struct dlist_entry head; 61 } gnix_ht_lk_lh_t; 62 63 typedef struct gnix_ht_lf_lh { 64 struct dlist_entry head; 65 } gnix_ht_lf_lh_t; 66 67 enum gnix_ht_increase { 68 GNIX_HT_INCREASE_ADD = 0, 69 GNIX_HT_INCREASE_MULT 70 }; 71 72 /** 73 * Set of attributes that can be passed to the gnix_ht_init. 74 * 75 * @var ht_initial_size initial number of buckets allocated 76 * @var ht_maximum_size maximum number of buckets to allocate on resize 77 * @var ht_increase_step additive or multiplicative factor to increase by. 78 * If additive, the new_size = (old_size + increase) 79 * If multiplicative, the new size = (old_size * 80 * increase) 81 * @var ht_increase_type based on the gnix_ht_increase enum, this 82 * influences whether the increase of the bucket 83 * count is additive or multiplicative 84 * @var ht_collision_thresh threshold for resizing based on insertion 85 * collisions. The threshold is based on the 86 * average number of collisions per insertion, 87 * multiplied by 100. If you want an average bucket 88 * depth of 4, you would want to see 3-4 collisions 89 * on average, so the appropriate threshold would be 90 * ~400. 91 * @var ht_hash_seed seed value that affects how items are hashed 92 * internally. Using the same seed value and the same 93 * insertion pattern will allow for repeatable 94 * results. 95 * @var ht_internal_locking if non-zero, uses a version of the hash table with 96 * internal locking implemented 97 * 98 * @var destructor if non-NULL, will be called with value when 99 * destroying the hash table 100 */ 101 typedef struct gnix_hashtable_attr { 102 int ht_initial_size; 103 int ht_maximum_size; 104 int ht_increase_step; 105 int ht_increase_type; 106 int ht_collision_thresh; 107 uint64_t ht_hash_seed; 108 int ht_internal_locking; 109 void (*destructor)(void *); 110 } gnix_hashtable_attr_t; 111 112 struct gnix_hashtable; 113 struct gnix_hashtable_iter; 114 115 typedef struct gnix_hashtable_ops { 116 int (*init)(struct gnix_hashtable *); 117 int (*destroy)(struct gnix_hashtable *); 118 int (*insert)(struct gnix_hashtable *, gnix_ht_entry_t *, uint64_t *); 119 int (*remove)(struct gnix_hashtable *, gnix_ht_key_t); 120 void *(*lookup)(struct gnix_hashtable *, gnix_ht_key_t); 121 int (*resize)(struct gnix_hashtable *, int, int); 122 struct dlist_entry *(*retrieve_list)(struct gnix_hashtable *, int bucket); 123 void *(*iter_next)(struct gnix_hashtable_iter *); 124 } gnix_hashtable_ops_t; 125 126 /** 127 * Hashtable structure 128 * 129 * @var ht_lock reader/writer lock for protecting internal structures 130 * during a resize 131 * @var ht_state internal state mechanism for detecting valid state 132 * transitions 133 * @var ht_attr attributes for the hash map to follow after init 134 * @var ht_ops function table for internal hash map calls 135 * @var ht_elements number of items in the hash map 136 * @var ht_collisions number of insertion collisions since the last resize 137 * @var ht_insertions number of insertions since the last resize 138 * @var ht_size number of hash buckets 139 * @var ht_tbl array of hash buckets 140 */ 141 typedef struct gnix_hashtable { 142 pthread_rwlock_t ht_lock; 143 gnix_ht_state_e ht_state; 144 gnix_hashtable_attr_t ht_attr; 145 gnix_hashtable_ops_t *ht_ops; 146 ofi_atomic32_t ht_elements; 147 ofi_atomic32_t ht_collisions; 148 ofi_atomic32_t ht_insertions; 149 int ht_size; 150 union { 151 gnix_ht_lf_lh_t *ht_lf_tbl; 152 gnix_ht_lk_lh_t *ht_lk_tbl; 153 }; 154 } gnix_hashtable_t; 155 156 struct gnix_hashtable_iter { 157 struct gnix_hashtable *ht; 158 int cur_idx; 159 gnix_ht_entry_t *cur_entry; 160 }; 161 162 #define GNIX_HASHTABLE_ITERATOR(_ht, _iter) \ 163 struct gnix_hashtable_iter _iter = { \ 164 .ht = (_ht), \ 165 .cur_idx = 0, \ 166 .cur_entry = NULL \ 167 } 168 #define GNIX_HASHTABLE_ITERATOR_KEY(_iter) ((_iter).cur_entry->key) 169 170 /** 171 * Initializes the hash table with provided attributes, if any 172 * 173 * @param ht pointer to the hash table structure 174 * @param attr pointer to the hash table attributes to initialize with 175 * @return 0 on success, -FI_EINVAL on initialization error, or 176 * -FI_ENOMEM if allocation of the bucket array fails 177 */ 178 int _gnix_ht_init(gnix_hashtable_t *ht, gnix_hashtable_attr_t *attr); 179 180 /** 181 * Destroys the hash table 182 * 183 * @param ht pointer to the hash table structure 184 * @return 0 on success, -FI_EINVAL upon passing an uninitialized 185 * or dead structure 186 */ 187 int _gnix_ht_destroy(gnix_hashtable_t *ht); 188 189 /** 190 * Inserts an entry into the map with the provided key 191 * 192 * @param ht pointer to the hash table structure 193 * @param key key used to hash the entry 194 * @param entry entry to be stored 195 * @return 0 on success, -FI_ENOSPC when another entry with the same key 196 * exists in the hashtable, or -FI_EINVAL when called on a 197 * dead or uninitialized hash table 198 */ 199 int _gnix_ht_insert(gnix_hashtable_t *ht, gnix_ht_key_t key, void *entry); 200 201 /** 202 * Removes an entry from the map with the provided key 203 * 204 * @param ht pointer to the hash table structure 205 * @param key key used to hash the entry 206 * @return 0 on success, -FI_ENOENT when the key doesn't exist in 207 * the hash table, or -FI_EINVAL when called on a dead or 208 * uninitialized hash table 209 */ 210 int _gnix_ht_remove(gnix_hashtable_t *ht, gnix_ht_key_t key); 211 212 /** 213 * Looks up an entry in the hash table using key 214 * 215 * @param ht pointer to the hash table structure 216 * @param key key used to hash the entry 217 * @return NULL if the key did not exist in the hash table, or the 218 * entry if the key exists in the hash table 219 */ 220 void *_gnix_ht_lookup(gnix_hashtable_t *ht, gnix_ht_key_t key); 221 222 /** 223 * Tests to see if the hash table is empty 224 * 225 * @param ht pointer to the hash table structure 226 * @return true if the hash table is empty, false if not 227 */ 228 int _gnix_ht_empty(gnix_hashtable_t *ht); 229 230 /** 231 * Return next element in the hashtable 232 * 233 * @param iter pointer to the hashtable iterator 234 * @return pointer to next element in the hashtable 235 */ 236 void *_gnix_ht_iterator_next(struct gnix_hashtable_iter *iter); 237 238 /* Hastable iteration macros */ 239 #define ht_lf_for_each(ht, ht_entry) \ 240 dlist_for_each(ht->ht_lf_tbl->head, ht_entry, entry) \ 241 242 #define ht_lk_for_each(ht, ht_entry) \ 243 dlist_for_each(ht.ht_lk_tbl->head, ht_entry, entry) 244 245 #define ht_entry_value(ht_entry) \ 246 ht_entry->value 247 248 #endif /* GNIX_HASHTABLE_H_ */ 249