1/***************************************************************************** 2 3Copyright (c) 1994, 2019, 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/ha0ha.ic 28 The hash table with external chains 29 30 Created 8/18/1994 Heikki Tuuri 31 *************************************************************************/ 32 33#include "btr0types.h" 34#include "mem0mem.h" 35#include "ut0rnd.h" 36 37/** Deletes a hash node. */ 38void ha_delete_hash_node(hash_table_t *table, /*!< in: hash table */ 39 ha_node_t *del_node); /*!< in: node to be deleted */ 40 41/** Gets a hash node data. 42 @return pointer to the data */ 43UNIV_INLINE 44const rec_t *ha_node_get_data(const ha_node_t *node) /*!< in: hash chain node */ 45{ 46 return (node->data); 47} 48 49/** Sets hash node data. */ 50UNIV_INLINE 51void ha_node_set_data_func( 52 ha_node_t *node, /*!< in: hash chain node */ 53#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG 54 buf_block_t *block, /*!< in: buffer block containing the data */ 55#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */ 56 const rec_t *data) /*!< in: pointer to the data */ 57{ 58#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG 59 node->block = block; 60#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */ 61 node->data = data; 62} 63 64#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG 65/** Sets hash node data. 66@param n in: hash chain node 67@param b in: buffer block containing the data 68@param d in: pointer to the data */ 69#define ha_node_set_data(n, b, d) ha_node_set_data_func(n, b, d) 70#else /* UNIV_AHI_DEBUG || UNIV_DEBUG */ 71/** Sets hash node data. 72@param n in: hash chain node 73@param b in: buffer block containing the data 74@param d in: pointer to the data */ 75#define ha_node_set_data(n, b, d) ha_node_set_data_func(n, d) 76#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */ 77 78/** Gets the next node in a hash chain. 79 @return next node, NULL if none */ 80UNIV_INLINE 81ha_node_t *ha_chain_get_next(const ha_node_t *node) /*!< in: hash chain node */ 82{ 83 return (node->next); 84} 85 86/** Gets the first node in a hash chain. 87 @return first node, NULL if none */ 88UNIV_INLINE 89ha_node_t *ha_chain_get_first( 90 hash_table_t *table, /*!< in: hash table */ 91 ulint fold) /*!< in: fold value determining the chain */ 92{ 93 return ( 94 (ha_node_t *)hash_get_nth_cell(table, hash_calc_hash(fold, table))->node); 95} 96 97#ifdef UNIV_DEBUG 98/** Assert that the synchronization object in a hash operation involving 99 possible change in the hash table is held. 100 Note that in case of mutexes we assert that mutex is owned while in case 101 of rw-locks we assert that it is held in exclusive mode. */ 102UNIV_INLINE 103void hash_assert_can_modify(hash_table_t *table, /*!< in: hash table */ 104 ulint fold) /*!< in: fold value */ 105{ 106 if (table->type == HASH_TABLE_SYNC_MUTEX) { 107 ut_ad(mutex_own(hash_get_mutex(table, fold))); 108 } else if (table->type == HASH_TABLE_SYNC_RW_LOCK) { 109#if defined(UNIV_DEBUG) && !defined(UNIV_HOTBACKUP) 110 rw_lock_t *lock = hash_get_lock(table, fold); 111 ut_ad(rw_lock_own(lock, RW_LOCK_X)); 112#endif 113 } else { 114 ut_ad(table->type == HASH_TABLE_SYNC_NONE); 115 } 116} 117 118/** Assert that the synchronization object in a hash search operation is held. 119 Note that in case of mutexes we assert that mutex is owned while in case 120 of rw-locks we assert that it is held either in x-mode or s-mode. */ 121UNIV_INLINE 122void hash_assert_can_search(hash_table_t *table, /*!< in: hash table */ 123 ulint fold) /*!< in: fold value */ 124{ 125 if (table->type == HASH_TABLE_SYNC_MUTEX) { 126 ut_ad(mutex_own(hash_get_mutex(table, fold))); 127 } else if (table->type == HASH_TABLE_SYNC_RW_LOCK) { 128#if defined(UNIV_DEBUG) && !defined(UNIV_HOTBACKUP) 129 rw_lock_t *lock = hash_get_lock(table, fold); 130 ut_ad(rw_lock_own(lock, RW_LOCK_X) || rw_lock_own(lock, RW_LOCK_S)); 131#endif 132 } else { 133 ut_ad(table->type == HASH_TABLE_SYNC_NONE); 134 } 135} 136#endif /* UNIV_DEBUG */ 137 138/** Looks for an element in a hash table. 139 @return pointer to the data of the first hash table node in chain 140 having the fold number, NULL if not found */ 141UNIV_INLINE 142const rec_t *ha_search_and_get_data( 143 hash_table_t *table, /*!< in: hash table */ 144 ulint fold) /*!< in: folded value of the searched data */ 145{ 146 hash_assert_can_search(table, fold); 147 ut_ad(btr_search_enabled); 148 149 for (const ha_node_t *node = ha_chain_get_first(table, fold); node != nullptr; 150 node = ha_chain_get_next(node)) { 151 if (node->fold == fold) { 152 return (node->data); 153 } 154 } 155 156 return (nullptr); 157} 158 159/** Looks for an element when we know the pointer to the data. 160 @return pointer to the hash table node, NULL if not found in the table */ 161UNIV_INLINE 162ha_node_t *ha_search_with_data( 163 hash_table_t *table, /*!< in: hash table */ 164 ulint fold, /*!< in: folded value of the searched data */ 165 const rec_t *data) /*!< in: pointer to the data */ 166{ 167 ha_node_t *node; 168 169 hash_assert_can_search(table, fold); 170 171 ut_ad(btr_search_enabled); 172 173 node = ha_chain_get_first(table, fold); 174 175 while (node) { 176 if (node->data == data) { 177 return (node); 178 } 179 180 node = ha_chain_get_next(node); 181 } 182 183 return (nullptr); 184} 185 186/** Looks for an element when we know the pointer to the data, and deletes 187 it from the hash table, if found. 188 @return true if found */ 189UNIV_INLINE 190ibool ha_search_and_delete_if_found( 191 hash_table_t *table, /*!< in: hash table */ 192 ulint fold, /*!< in: folded value of the searched data */ 193 const rec_t *data) /*!< in: pointer to the data */ 194{ 195 ha_node_t *node; 196 197 hash_assert_can_modify(table, fold); 198 ut_ad(btr_search_enabled); 199 200 node = ha_search_with_data(table, fold, data); 201 202 if (node) { 203 ha_delete_hash_node(table, node); 204 205 return (TRUE); 206 } 207 208 return (FALSE); 209} 210