1 /***************************************************************************** 2 3 Copyright (c) 1997, 2016, Oracle and/or its affiliates. All Rights Reserved. 4 Copyright (c) 2018, 2022, MariaDB Corporation. 5 6 This program is free software; you can redistribute it and/or modify it under 7 the terms of the GNU General Public License as published by the Free Software 8 Foundation; version 2 of the License. 9 10 This program is distributed in the hope that it will be useful, but WITHOUT 11 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 12 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. 13 14 You should have received a copy of the GNU General Public License along with 15 this program; if not, write to the Free Software Foundation, Inc., 16 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA 17 18 *****************************************************************************/ 19 20 /**************************************************//** 21 @file include/hash0hash.h 22 The simple hash table utility 23 24 Created 5/20/1997 Heikki Tuuri 25 *******************************************************/ 26 27 #pragma once 28 #include "ut0rnd.h" 29 30 struct hash_table_t; 31 struct hash_cell_t 32 { 33 /** singly-linked, nullptr terminated list of hash buckets */ 34 void *node; 35 36 /** Insert an element after another. 37 @tparam T type of the element 38 @param after the element after which to insert 39 @param insert the being-inserted element 40 @param next the next-element pointer in T */ 41 template<typename T> insert_afterhash_cell_t42 void insert_after(T &after, T &insert, T *T::*next) 43 { 44 #ifdef UNIV_DEBUG 45 for (const T *c= static_cast<const T*>(node); c; c= c->*next) 46 if (c == &after) 47 goto found; 48 ut_error; 49 found: 50 #endif 51 insert.*next= after.*next; 52 after.*next= &insert; 53 } 54 }; 55 typedef void* hash_node_t; 56 57 /*******************************************************************//** 58 Inserts a struct to a hash table. */ 59 60 #define HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA)\ 61 do {\ 62 hash_cell_t* cell3333;\ 63 TYPE* struct3333;\ 64 \ 65 (DATA)->NAME = NULL;\ 66 \ 67 cell3333 = &(TABLE)->array[(TABLE)->calc_hash(FOLD)]; \ 68 \ 69 if (cell3333->node == NULL) {\ 70 cell3333->node = DATA;\ 71 } else {\ 72 struct3333 = (TYPE*) cell3333->node;\ 73 \ 74 while (struct3333->NAME != NULL) {\ 75 \ 76 struct3333 = (TYPE*) struct3333->NAME;\ 77 }\ 78 \ 79 struct3333->NAME = DATA;\ 80 }\ 81 } while (0) 82 83 /*******************************************************************//** 84 Inserts a struct to the head of hash table. */ 85 86 #define HASH_PREPEND(TYPE, NAME, TABLE, FOLD, DATA) \ 87 do { \ 88 hash_cell_t* cell3333; \ 89 TYPE* struct3333; \ 90 \ 91 (DATA)->NAME = NULL; \ 92 \ 93 cell3333 = &(TABLE)->array[(TABLE)->calc_hash(FOLD)]; \ 94 \ 95 if (cell3333->node == NULL) { \ 96 cell3333->node = DATA; \ 97 DATA->NAME = NULL; \ 98 } else { \ 99 struct3333 = (TYPE*) cell3333->node; \ 100 \ 101 DATA->NAME = struct3333; \ 102 \ 103 cell3333->node = DATA; \ 104 } \ 105 } while (0) 106 #ifdef UNIV_HASH_DEBUG 107 # define HASH_ASSERT_VALID(DATA) ut_a((void*) (DATA) != (void*) -1) 108 # define HASH_INVALIDATE(DATA, NAME) *(void**) (&DATA->NAME) = (void*) -1 109 #else 110 # define HASH_ASSERT_VALID(DATA) do {} while (0) 111 # define HASH_INVALIDATE(DATA, NAME) do {} while (0) 112 #endif 113 114 /*******************************************************************//** 115 Deletes a struct from a hash table. */ 116 117 #define HASH_DELETE(TYPE, NAME, TABLE, FOLD, DATA)\ 118 do {\ 119 hash_cell_t* cell3333;\ 120 TYPE* struct3333;\ 121 \ 122 cell3333 = &(TABLE)->array[(TABLE)->calc_hash(FOLD)]; \ 123 \ 124 if (cell3333->node == DATA) {\ 125 HASH_ASSERT_VALID(DATA->NAME);\ 126 cell3333->node = DATA->NAME;\ 127 } else {\ 128 struct3333 = (TYPE*) cell3333->node;\ 129 \ 130 while (struct3333->NAME != DATA) {\ 131 \ 132 struct3333 = (TYPE*) struct3333->NAME;\ 133 ut_a(struct3333);\ 134 }\ 135 \ 136 struct3333->NAME = DATA->NAME;\ 137 }\ 138 HASH_INVALIDATE(DATA, NAME);\ 139 } while (0) 140 141 #define HASH_REPLACE(TYPE, NAME, TABLE, FOLD, DATA_OLD, DATA_NEW) \ 142 do { \ 143 (DATA_NEW)->NAME = (DATA_OLD)->NAME; \ 144 \ 145 hash_cell_t& cell3333 \ 146 = (TABLE)->array[(TABLE)->calc_hash(FOLD)]; \ 147 TYPE** struct3333 = (TYPE**)&cell3333.node; \ 148 while (*struct3333 != DATA_OLD) { \ 149 struct3333 = &((*struct3333)->NAME); \ 150 } \ 151 *struct3333 = DATA_NEW; \ 152 } while (0) 153 /*******************************************************************//** 154 Gets the first struct in a hash chain, NULL if none. */ 155 156 #define HASH_GET_FIRST(TABLE, HASH_VAL) (TABLE)->array[HASH_VAL].node 157 158 /*******************************************************************//** 159 Gets the next struct in a hash chain, NULL if none. */ 160 161 #define HASH_GET_NEXT(NAME, DATA) ((DATA)->NAME) 162 163 /********************************************************************//** 164 Looks for a struct in a hash table. */ 165 #define HASH_SEARCH(NAME, TABLE, FOLD, TYPE, DATA, ASSERTION, TEST)\ 166 {\ 167 (DATA) = (TYPE) HASH_GET_FIRST(TABLE, (TABLE)->calc_hash(FOLD)); \ 168 HASH_ASSERT_VALID(DATA);\ 169 \ 170 while ((DATA) != NULL) {\ 171 ASSERTION;\ 172 if (TEST) {\ 173 break;\ 174 } else {\ 175 HASH_ASSERT_VALID(HASH_GET_NEXT(NAME, DATA));\ 176 (DATA) = (TYPE) HASH_GET_NEXT(NAME, DATA);\ 177 }\ 178 }\ 179 } 180 181 /********************************************************************//** 182 Looks for an item in all hash buckets. */ 183 #define HASH_SEARCH_ALL(NAME, TABLE, TYPE, DATA, ASSERTION, TEST) \ 184 do { \ 185 ulint i3333; \ 186 \ 187 for (i3333 = (TABLE)->n_cells; i3333--; ) { \ 188 (DATA) = (TYPE) HASH_GET_FIRST(TABLE, i3333); \ 189 \ 190 while ((DATA) != NULL) { \ 191 HASH_ASSERT_VALID(DATA); \ 192 ASSERTION; \ 193 \ 194 if (TEST) { \ 195 break; \ 196 } \ 197 \ 198 (DATA) = (TYPE) HASH_GET_NEXT(NAME, DATA); \ 199 } \ 200 \ 201 if ((DATA) != NULL) { \ 202 break; \ 203 } \ 204 } \ 205 } while (0) 206 207 /****************************************************************//** 208 Move all hash table entries from OLD_TABLE to NEW_TABLE. */ 209 210 #define HASH_MIGRATE(OLD_TABLE, NEW_TABLE, NODE_TYPE, PTR_NAME, FOLD_FUNC) \ 211 do {\ 212 ulint i2222;\ 213 ulint cell_count2222;\ 214 \ 215 cell_count2222 = (OLD_TABLE)->n_cells; \ 216 \ 217 for (i2222 = 0; i2222 < cell_count2222; i2222++) {\ 218 NODE_TYPE* node2222 = static_cast<NODE_TYPE*>(\ 219 HASH_GET_FIRST((OLD_TABLE), i2222));\ 220 \ 221 while (node2222) {\ 222 NODE_TYPE* next2222 = static_cast<NODE_TYPE*>(\ 223 node2222->PTR_NAME);\ 224 ulint fold2222 = FOLD_FUNC(node2222);\ 225 \ 226 HASH_INSERT(NODE_TYPE, PTR_NAME, (NEW_TABLE),\ 227 fold2222, node2222);\ 228 \ 229 node2222 = next2222;\ 230 }\ 231 }\ 232 } while (0) 233 234 /** Hash table with singly-linked overflow lists */ 235 struct hash_table_t 236 { 237 /** number of elements in array (a prime number) */ 238 ulint n_cells; 239 /** the hash array */ 240 hash_cell_t *array; 241 242 /** Create the hash table. 243 @param n the lower bound of n_cells */ createhash_table_t244 void create(ulint n) 245 { 246 n_cells= ut_find_prime(n); 247 array= static_cast<hash_cell_t*>(ut_zalloc_nokey(n_cells * sizeof *array)); 248 } 249 250 /** Clear the hash table. */ clearhash_table_t251 void clear() { memset(array, 0, n_cells * sizeof *array); } 252 253 /** Free the hash table. */ freehash_table_t254 void free() { ut_free(array); array= nullptr; } 255 calc_hashhash_table_t256 ulint calc_hash(ulint fold) const { return ut_hash_ulint(fold, n_cells); } 257 }; 258