1/***************************************************************************** 2 3Copyright (c) 1997, 2018, Oracle and/or its affiliates. All Rights Reserved. 4 5This program is free software; you can redistribute it and/or modify it under 6the terms of the GNU General Public License, version 2.0, as published by the 7Free Software Foundation. 8 9This program is also distributed with certain software (including but not 10limited to OpenSSL) that is licensed under separate terms, as designated in a 11particular file or component or in included license documentation. The authors 12of MySQL hereby grant you an additional permission to link the program and 13your derivative works with the separately licensed software that they have 14included with MySQL. 15 16This program is distributed in the hope that it will be useful, but WITHOUT 17ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 18FOR A PARTICULAR PURPOSE. See the GNU General Public License, version 2.0, 19for more details. 20 21You should have received a copy of the GNU General Public License along with 22this program; if not, write to the Free Software Foundation, Inc., 2351 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 24 25*****************************************************************************/ 26 27/** @file include/hash0hash.ic 28 The simple hash table utility 29 30 Created 5/20/1997 Heikki Tuuri 31 *******************************************************/ 32 33#include "ut0rnd.h" 34 35/** Gets the nth cell in a hash table. 36 @return pointer to cell */ 37UNIV_INLINE 38hash_cell_t *hash_get_nth_cell(hash_table_t *table, /*!< in: hash table */ 39 ulint n) /*!< in: cell index */ 40{ 41 ut_ad(table); 42 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N); 43 ut_ad(n < table->n_cells); 44 45 return (table->cells + n); 46} 47 48/** Clears a hash table so that all the cells become empty. */ 49UNIV_INLINE 50void hash_table_clear(hash_table_t *table) /*!< in/out: hash table */ 51{ 52 ut_ad(table); 53 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N); 54 memset(table->cells, 0x0, table->n_cells * sizeof(*table->cells)); 55} 56 57/** Returns the number of cells in a hash table. 58 @return number of cells */ 59UNIV_INLINE 60ulint hash_get_n_cells(hash_table_t *table) /*!< in: table */ 61{ 62 ut_ad(table); 63 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N); 64 return (table->n_cells); 65} 66 67/** Calculates the hash value from a folded value. 68 @return hashed value */ 69UNIV_INLINE 70ulint hash_calc_hash(ulint fold, /*!< in: folded value */ 71 hash_table_t *table) /*!< in: hash table */ 72{ 73 ut_ad(table); 74 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N); 75 return (ut_hash_ulint(fold, table->n_cells)); 76} 77 78#ifndef UNIV_HOTBACKUP 79/** Gets the sync object index for a fold value in a hash table. 80 @return index */ 81UNIV_INLINE 82ulint hash_get_sync_obj_index(hash_table_t *table, /*!< in: hash table */ 83 ulint fold) /*!< in: fold */ 84{ 85 ut_ad(table); 86 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N); 87 ut_ad(table->type != HASH_TABLE_SYNC_NONE); 88 ut_ad(ut_is_2pow(table->n_sync_obj)); 89 return (ut_2pow_remainder(hash_calc_hash(fold, table), table->n_sync_obj)); 90} 91 92/** Gets the nth heap in a hash table. 93 @return mem heap */ 94UNIV_INLINE 95mem_heap_t *hash_get_nth_heap(hash_table_t *table, /*!< in: hash table */ 96 ulint i) /*!< in: index of the heap */ 97{ 98 ut_ad(table); 99 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N); 100 ut_ad(table->type != HASH_TABLE_SYNC_NONE); 101 ut_ad(i < table->n_sync_obj); 102 103 return (table->heaps[i]); 104} 105 106/** Gets the heap for a fold value in a hash table. 107 @return mem heap */ 108UNIV_INLINE 109mem_heap_t *hash_get_heap(hash_table_t *table, /*!< in: hash table */ 110 ulint fold) /*!< in: fold */ 111{ 112 ulint i; 113 114 ut_ad(table); 115 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N); 116 117 if (table->heap) { 118 return (table->heap); 119 } 120 121 i = hash_get_sync_obj_index(table, fold); 122 123 return (hash_get_nth_heap(table, i)); 124} 125 126/** Gets the nth mutex in a hash table. 127 @return mutex */ 128UNIV_INLINE 129ib_mutex_t *hash_get_nth_mutex(hash_table_t *table, /*!< in: hash table */ 130 ulint i) /*!< in: index of the mutex */ 131{ 132 ut_ad(table); 133 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N); 134 ut_ad(table->type == HASH_TABLE_SYNC_MUTEX); 135 ut_ad(i < table->n_sync_obj); 136 137 return (table->sync_obj.mutexes + i); 138} 139 140/** Gets the mutex for a fold value in a hash table. 141 @return mutex */ 142UNIV_INLINE 143ib_mutex_t *hash_get_mutex(hash_table_t *table, /*!< in: hash table */ 144 ulint fold) /*!< in: fold */ 145{ 146 ulint i; 147 148 ut_ad(table); 149 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N); 150 151 i = hash_get_sync_obj_index(table, fold); 152 153 return (hash_get_nth_mutex(table, i)); 154} 155 156/** Gets the nth rw_lock in a hash table. 157 @return rw_lock */ 158UNIV_INLINE 159rw_lock_t *hash_get_nth_lock(hash_table_t *table, /*!< in: hash table */ 160 ulint i) /*!< in: index of the rw_lock */ 161{ 162 ut_ad(table); 163 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N); 164 ut_ad(table->type == HASH_TABLE_SYNC_RW_LOCK); 165 ut_ad(i < table->n_sync_obj); 166 167 return (table->sync_obj.rw_locks + i); 168} 169 170/** Gets the rw_lock for a fold value in a hash table. 171 @return rw_lock */ 172UNIV_INLINE 173rw_lock_t *hash_get_lock(hash_table_t *table, /*!< in: hash table */ 174 ulint fold) /*!< in: fold */ 175{ 176 ulint i; 177 178 ut_ad(table); 179 ut_ad(table->type == HASH_TABLE_SYNC_RW_LOCK); 180 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N); 181 182 i = hash_get_sync_obj_index(table, fold); 183 184 return (hash_get_nth_lock(table, i)); 185} 186 187/** If not appropriate rw_lock for a fold value in a hash table, 188relock S-lock the another rw_lock until appropriate for a fold value. 189@param[in] hash_lock latched rw_lock to be confirmed 190@param[in] table hash table 191@param[in] fold fold value 192@return latched rw_lock */ 193UNIV_INLINE 194rw_lock_t *hash_lock_s_confirm(rw_lock_t *hash_lock, hash_table_t *table, 195 ulint fold) { 196 ut_ad(rw_lock_own(hash_lock, RW_LOCK_S)); 197 198 rw_lock_t *hash_lock_tmp = hash_get_lock(table, fold); 199 200 while (hash_lock_tmp != hash_lock) { 201 rw_lock_s_unlock(hash_lock); 202 hash_lock = hash_lock_tmp; 203 rw_lock_s_lock(hash_lock); 204 hash_lock_tmp = hash_get_lock(table, fold); 205 } 206 207 return (hash_lock); 208} 209 210/** If not appropriate rw_lock for a fold value in a hash table, 211relock X-lock the another rw_lock until appropriate for a fold value. 212@param[in] hash_lock latched rw_lock to be confirmed 213@param[in] table hash table 214@param[in] fold fold value 215@return latched rw_lock */ 216UNIV_INLINE 217rw_lock_t *hash_lock_x_confirm(rw_lock_t *hash_lock, hash_table_t *table, 218 ulint fold) { 219 ut_ad(rw_lock_own(hash_lock, RW_LOCK_X)); 220 221 rw_lock_t *hash_lock_tmp = hash_get_lock(table, fold); 222 223 while (hash_lock_tmp != hash_lock) { 224 rw_lock_x_unlock(hash_lock); 225 hash_lock = hash_lock_tmp; 226 rw_lock_x_lock(hash_lock); 227 hash_lock_tmp = hash_get_lock(table, fold); 228 } 229 230 return (hash_lock); 231} 232#endif /* !UNIV_HOTBACKUP */ 233