hashtable.h revision 1.1.1.2
1 /* 2 * Copyright 2024-2025 The OpenSSL Project Authors. All Rights Reserved. 3 * 4 * Licensed under the Apache License 2.0 (the "License"). You may not use 5 * this file except in compliance with the License. You can obtain a copy 6 * in the file LICENSE in the source distribution or at 7 * https://www.openssl.org/source/license.html 8 */ 9 10 #ifndef OPENSSL_HASHTABLE_H 11 #define OPENSSL_HASHTABLE_H 12 #pragma once 13 14 #include <stddef.h> 15 #include <stdint.h> 16 #include <openssl/e_os2.h> 17 #include <internal/rcu.h> 18 #include "crypto/context.h" 19 20 typedef struct ht_internal_st HT; 21 22 /* 23 * Represents a key to a hashtable 24 */ 25 typedef struct ht_key_header_st { 26 size_t keysize; 27 uint8_t *keybuf; 28 } HT_KEY; 29 30 /* 31 * Represents a value in the hash table 32 */ 33 typedef struct ht_value_st { 34 void *value; 35 uintptr_t *type_id; 36 HT_KEY key; 37 } HT_VALUE; 38 39 /* 40 * Represents a list of values filtered from a hash table 41 */ 42 typedef struct ht_value_list_st { 43 size_t list_len; 44 HT_VALUE **list; 45 } HT_VALUE_LIST; 46 47 /* 48 * Hashtable configuration 49 */ 50 typedef struct ht_config_st { 51 OSSL_LIB_CTX *ctx; 52 void (*ht_free_fn)(HT_VALUE *obj); 53 uint64_t (*ht_hash_fn)(uint8_t *key, size_t keylen); 54 size_t init_neighborhoods; 55 uint32_t collision_check; 56 uint32_t lockless_reads; 57 } HT_CONFIG; 58 59 /* 60 * Hashtable key rules 61 * Any struct can be used to formulate a hash table key, as long as the 62 * following rules 63 * 1) The first element of the struct defining the key must be an HT_KEY 64 * 2) All struct elements must have a compile time defined length 65 * 3) Pointers can be used, but the value of the pointer, rather than 66 * the contents of the address it points to will be used to compute 67 * the hash 68 * The key definition macros will assist with enforcing these rules 69 */ 70 71 /* 72 * Starts the definition of a hash table key 73 */ 74 #define HT_START_KEY_DEFN(keyname) \ 75 typedef struct keyname##_st { \ 76 HT_KEY key_header; \ 77 struct { 78 79 /* 80 * Ends a hash table key definitions 81 */ 82 #define HT_END_KEY_DEFN(keyname) \ 83 } \ 84 keyfields; \ 85 } \ 86 keyname; 87 88 /* 89 * Defines a field in a hash table key 90 */ 91 #define HT_DEF_KEY_FIELD(name, type) type name; 92 93 /* 94 * convenience macro to define a static char 95 * array field in a hash table key 96 */ 97 #define HT_DEF_KEY_FIELD_CHAR_ARRAY(name, size) \ 98 HT_DEF_KEY_FIELD(name[size], char) 99 100 /* 101 * Defines a uint8_t (blob) field in a hash table key 102 */ 103 #define HT_DEF_KEY_FIELD_UINT8T_ARRAY(name, size) \ 104 HT_DEF_KEY_FIELD(name[size], uint8_t) 105 106 /* 107 * Initializes a key 108 */ 109 #define HT_INIT_KEY(key) \ 110 do { \ 111 memset((key), 0, sizeof(*(key))); \ 112 (key)->key_header.keysize = (sizeof(*(key)) - sizeof(HT_KEY)); \ 113 (key)->key_header.keybuf = (((uint8_t *)key) + sizeof(HT_KEY)); \ 114 } while (0) 115 116 /* 117 * Resets a hash table key to a known state 118 */ 119 #define HT_KEY_RESET(key) memset((key)->key_header.keybuf, 0, (key)->key_header.keysize) 120 121 /* 122 * Sets a scalar field in a hash table key 123 */ 124 #define HT_SET_KEY_FIELD(key, member, value) (key)->keyfields.member = value; 125 126 /* 127 * Sets a string field in a hash table key, preserving 128 * null terminator 129 */ 130 #define HT_SET_KEY_STRING(key, member, value) \ 131 do { \ 132 if ((value) != NULL) \ 133 strncpy((key)->keyfields.member, value, sizeof((key)->keyfields.member) - 1); \ 134 } while (0) 135 136 /* 137 * This is the same as HT_SET_KEY_STRING, except that it uses 138 * ossl_ht_strcase to make the value being passed case insensitive 139 * This is useful for instances in which we want upper and lower case 140 * key value to hash to the same entry 141 */ 142 #define HT_SET_KEY_STRING_CASE(key, member, value) \ 143 do { \ 144 ossl_ht_strcase((key)->keyfields.member, value, sizeof((key)->keyfields.member) - 1); \ 145 } while (0) 146 147 /* 148 * Same as HT_SET_KEY_STRING but also takes length of the string. 149 */ 150 #define HT_SET_KEY_STRING_N(key, member, value, len) \ 151 do { \ 152 if ((value) != NULL) { \ 153 if (len < sizeof((key)->keyfields.member)) \ 154 strncpy((key)->keyfields.member, value, len); \ 155 else \ 156 strncpy((key)->keyfields.member, value, sizeof((key)->keyfields.member) - 1); \ 157 } \ 158 } while (0) 159 160 /* Same as HT_SET_KEY_STRING_CASE but also takes length of the string. */ 161 #define HT_SET_KEY_STRING_CASE_N(key, member, value, len) \ 162 do { \ 163 if (len < sizeof((key)->keyfields.member)) \ 164 ossl_ht_strcase((key)->keyfields.member, value, len); \ 165 else \ 166 ossl_ht_strcase((key)->keyfields.member, value, sizeof((key)->keyfields.member) - 1); \ 167 } while (0) 168 169 /* 170 * Sets a uint8_t (blob) field in a hash table key 171 */ 172 #define HT_SET_KEY_BLOB(key, member, value, len) \ 173 do { \ 174 if (value != NULL) \ 175 memcpy((key)->keyfields.member, value, len); \ 176 } while (0) 177 178 /* 179 * Converts a defined key type to an HT_KEY 180 */ 181 #define TO_HT_KEY(key) &(key)->key_header 182 183 /* 184 * Converts an HT_KEY back to its defined 185 * type 186 */ 187 #define FROM_HT_KEY(key, type) (type)(key) 188 189 /* 190 * Implements the following type safe operations for a hash table 191 * ossl_ht_NAME_TYPE_insert - insert a value to a hash table of type TYPE 192 * ossl_ht_NAME_TYPE_get - gets a value of a specific type from the hash table 193 * ossl_ht_NAME_TYPE_from_value - converts an HT_VALUE to its type 194 * ossl_ht_NAME_TYPE_to_value - converts a TYPE to an HT_VALUE 195 * ossl_ht_NAME_TYPE_type - boolean to detect if a value is of TYPE 196 */ 197 #define IMPLEMENT_HT_VALUE_TYPE_FNS(vtype, name, pfx) \ 198 static uintptr_t name##_##vtype##_id = 0; \ 199 pfx ossl_unused int ossl_ht_##name##_##vtype##_insert(HT *h, HT_KEY *key, \ 200 vtype *data, \ 201 vtype **olddata) \ 202 { \ 203 HT_VALUE inval; \ 204 HT_VALUE *oval = NULL; \ 205 int rc; \ 206 \ 207 inval.value = data; \ 208 inval.type_id = &name##_##vtype##_id; \ 209 rc = ossl_ht_insert(h, key, &inval, olddata == NULL ? NULL : &oval); \ 210 if (oval != NULL) \ 211 *olddata = (vtype *)oval->value; \ 212 return rc; \ 213 } \ 214 \ 215 pfx ossl_unused vtype *ossl_ht_##name##_##vtype##_from_value(HT_VALUE *v) \ 216 { \ 217 uintptr_t *expect_type = &name##_##vtype##_id; \ 218 if (v == NULL) \ 219 return NULL; \ 220 if (v->type_id != expect_type) \ 221 return NULL; \ 222 return (vtype *)v->value; \ 223 } \ 224 \ 225 pfx ossl_unused vtype *ossl_unused ossl_ht_##name##_##vtype##_get(HT *h, \ 226 HT_KEY *key, \ 227 HT_VALUE **v) \ 228 { \ 229 HT_VALUE *vv; \ 230 vv = ossl_ht_get(h, key); \ 231 if (vv == NULL) \ 232 return NULL; \ 233 *v = ossl_rcu_deref(&vv); \ 234 return ossl_ht_##name##_##vtype##_from_value(*v); \ 235 } \ 236 \ 237 pfx ossl_unused HT_VALUE *ossl_ht_##name##_##vtype##_to_value(vtype *data, \ 238 HT_VALUE *v) \ 239 { \ 240 v->type_id = &name##_##vtype##_id; \ 241 v->value = data; \ 242 return v; \ 243 } \ 244 \ 245 pfx ossl_unused int ossl_ht_##name##_##vtype##_type(HT_VALUE *h) \ 246 { \ 247 return h->type_id == &name##_##vtype##_id; \ 248 } 249 250 #define DECLARE_HT_VALUE_TYPE_FNS(vtype, name) \ 251 int ossl_ht_##name##_##vtype##_insert(HT *h, HT_KEY *key, vtype *data, \ 252 vtype **olddata); \ 253 vtype *ossl_ht_##name##_##vtype##_from_value(HT_VALUE *v); \ 254 vtype *ossl_unused ossl_ht_##name##_##vtype##_get(HT *h, \ 255 HT_KEY *key, \ 256 HT_VALUE **v); \ 257 HT_VALUE *ossl_ht_##name##_##vtype##_to_value(vtype *data, HT_VALUE *v); \ 258 int ossl_ht_##name##_##vtype##_type(HT_VALUE *h); 259 260 /* 261 * Helper function to construct case insensitive keys 262 */ 263 static void ossl_unused ossl_ht_strcase(char *tgt, const char *src, int len) 264 { 265 int i; 266 #if defined(CHARSET_EBCDIC) && !defined(CHARSET_EBCDIC_TEST) 267 const long int case_adjust = ~0x40; 268 #else 269 const long int case_adjust = ~0x20; 270 #endif 271 272 if (src == NULL) 273 return; 274 275 for (i = 0; src[i] != '\0' && i < len; i++) 276 tgt[i] = case_adjust & src[i]; 277 } 278 279 /* 280 * Create a new hashtable 281 */ 282 HT *ossl_ht_new(const HT_CONFIG *conf); 283 284 /* 285 * Frees a hash table, potentially freeing all elements 286 */ 287 void ossl_ht_free(HT *htable); 288 289 /* 290 * Lock the table for reading 291 */ 292 void ossl_ht_read_lock(HT *htable); 293 294 /* 295 * Lock the table for writing 296 */ 297 void ossl_ht_write_lock(HT *htable); 298 299 /* 300 * Read unlock 301 */ 302 void ossl_ht_read_unlock(HT *htable); 303 304 /* 305 * Write unlock 306 */ 307 void ossl_ht_write_unlock(HT *htable); 308 309 /* 310 * Empties a hash table, potentially freeing all elements 311 */ 312 int ossl_ht_flush(HT *htable); 313 314 /* 315 * Inserts an element to a hash table, optionally returning 316 * replaced data to caller 317 * Returns 1 if the insert was successful, 0 on error 318 */ 319 int ossl_ht_insert(HT *htable, HT_KEY *key, HT_VALUE *data, 320 HT_VALUE **olddata); 321 322 /* 323 * Deletes a value from a hash table, based on key 324 * Returns 1 if the key was removed, 0 if they key was not found 325 */ 326 int ossl_ht_delete(HT *htable, HT_KEY *key); 327 328 /* 329 * Returns number of elements in the hash table 330 */ 331 size_t ossl_ht_count(HT *htable); 332 333 /* 334 * Iterates over each element in the table. 335 * aborts the loop when cb returns 0 336 * Contents of elements in the list may be modified during 337 * this traversal, assuming proper thread safety is observed while doing 338 * so (holding the table write lock is sufficient). However, elements of the 339 * table may not be inserted or removed while iterating. 340 */ 341 void ossl_ht_foreach_until(HT *htable, int (*cb)(HT_VALUE *obj, void *arg), 342 void *arg); 343 /* 344 * Returns a list of elements in a hash table based on 345 * filter function return value. Returns NULL on error, 346 * or an HT_VALUE_LIST object on success. Note it is possible 347 * That a list will be returned with 0 entries, if none were found. 348 * The zero length list must still be freed via ossl_ht_value_list_free 349 */ 350 HT_VALUE_LIST *ossl_ht_filter(HT *htable, size_t max_len, 351 int (*filter)(HT_VALUE *obj, void *arg), 352 void *arg); 353 /* 354 * Frees the list returned from ossl_ht_filter 355 */ 356 void ossl_ht_value_list_free(HT_VALUE_LIST *list); 357 358 /* 359 * Fetches a value from the hash table, based 360 * on key. Returns NULL if the element was not found. 361 */ 362 HT_VALUE *ossl_ht_get(HT *htable, HT_KEY *key); 363 364 #endif 365
Indexes created Wed Mar 04 15:26:31 UTC 2026