1/***************************************************************************** 2 3Copyright (c) 1994, 2011, Oracle and/or its affiliates. All Rights Reserved. 4 5This program is free software; you can redistribute it and/or modify 6it under the terms of the GNU General Public License, version 2.0, 7as published by the Free Software Foundation. 8 9This program is also distributed with certain software (including 10but not limited to OpenSSL) that is licensed under separate terms, 11as designated in a particular file or component or in included license 12documentation. The authors of MySQL hereby grant you an additional 13permission to link the program and your derivative works with the 14separately licensed software that they have included with MySQL. 15 16This program is distributed in the hope that it will be useful, 17but WITHOUT ANY WARRANTY; without even the implied warranty of 18MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 19GNU General Public License, version 2.0, for 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 Street, Suite 500, Boston, MA 02110-1335 USA 24 25*****************************************************************************/ 26 27/********************************************************************//** 28@file include/ha0ha.ic 29The hash table with external chains 30 31Created 8/18/1994 Heikki Tuuri 32*************************************************************************/ 33 34#include "ut0rnd.h" 35#include "mem0mem.h" 36#include "btr0types.h" 37 38/***********************************************************//** 39Deletes a hash node. */ 40UNIV_INTERN 41void 42ha_delete_hash_node( 43/*================*/ 44 hash_table_t* table, /*!< in: hash table */ 45 ha_node_t* del_node); /*!< in: node to be deleted */ 46 47/******************************************************************//** 48Gets a hash node data. 49@return pointer to the data */ 50UNIV_INLINE 51const rec_t* 52ha_node_get_data( 53/*=============*/ 54 const ha_node_t* node) /*!< in: hash chain node */ 55{ 56 return(node->data); 57} 58 59/******************************************************************//** 60Sets hash node data. */ 61UNIV_INLINE 62void 63ha_node_set_data_func( 64/*==================*/ 65 ha_node_t* node, /*!< in: hash chain node */ 66#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG 67 buf_block_t* block, /*!< in: buffer block containing the data */ 68#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */ 69 const rec_t* data) /*!< in: pointer to the data */ 70{ 71#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG 72 node->block = block; 73#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */ 74 node->data = data; 75} 76 77#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG 78/** Sets hash node data. 79@param n in: hash chain node 80@param b in: buffer block containing the data 81@param d in: pointer to the data */ 82# define ha_node_set_data(n,b,d) ha_node_set_data_func(n,b,d) 83#else /* UNIV_AHI_DEBUG || UNIV_DEBUG */ 84/** Sets hash node data. 85@param n in: hash chain node 86@param b in: buffer block containing the data 87@param d in: pointer to the data */ 88# define ha_node_set_data(n,b,d) ha_node_set_data_func(n,d) 89#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */ 90 91/******************************************************************//** 92Gets the next node in a hash chain. 93@return next node, NULL if none */ 94UNIV_INLINE 95ha_node_t* 96ha_chain_get_next( 97/*==============*/ 98 ha_node_t* node) /*!< in: hash chain node */ 99{ 100 return(node->next); 101} 102 103/******************************************************************//** 104Gets the first node in a hash chain. 105@return first node, NULL if none */ 106UNIV_INLINE 107ha_node_t* 108ha_chain_get_first( 109/*===============*/ 110 hash_table_t* table, /*!< in: hash table */ 111 ulint fold) /*!< in: fold value determining the chain */ 112{ 113 return((ha_node_t*) 114 hash_get_nth_cell(table, hash_calc_hash(fold, table))->node); 115} 116 117#ifdef UNIV_DEBUG 118/********************************************************************//** 119Assert that the synchronization object in a hash operation involving 120possible change in the hash table is held. 121Note that in case of mutexes we assert that mutex is owned while in case 122of rw-locks we assert that it is held in exclusive mode. */ 123UNIV_INLINE 124void 125hash_assert_can_modify( 126/*===================*/ 127 hash_table_t* table, /*!< in: hash table */ 128 ulint fold) /*!< in: fold value */ 129{ 130 if (table->type == HASH_TABLE_SYNC_MUTEX) { 131 ut_ad(mutex_own(hash_get_mutex(table, fold))); 132 } else if (table->type == HASH_TABLE_SYNC_RW_LOCK) { 133# ifdef UNIV_SYNC_DEBUG 134 prio_rw_lock_t* lock = hash_get_lock(table, fold); 135 ut_ad(rw_lock_own(lock, RW_LOCK_EX)); 136# endif 137 } else { 138 ut_ad(table->type == HASH_TABLE_SYNC_NONE); 139 } 140} 141 142/********************************************************************//** 143Assert that the synchronization object in a hash search operation is held. 144Note that in case of mutexes we assert that mutex is owned while in case 145of rw-locks we assert that it is held either in x-mode or s-mode. */ 146UNIV_INLINE 147void 148hash_assert_can_search( 149/*===================*/ 150 hash_table_t* table, /*!< in: hash table */ 151 ulint fold) /*!< in: fold value */ 152{ 153 if (table->type == HASH_TABLE_SYNC_MUTEX) { 154 ut_ad(mutex_own(hash_get_mutex(table, fold))); 155 } else if (table->type == HASH_TABLE_SYNC_RW_LOCK) { 156# ifdef UNIV_SYNC_DEBUG 157 prio_rw_lock_t* lock = hash_get_lock(table, fold); 158 ut_ad(rw_lock_own(lock, RW_LOCK_EX) 159 || rw_lock_own(lock, RW_LOCK_SHARED)); 160# endif 161 } else { 162 ut_ad(table->type == HASH_TABLE_SYNC_NONE); 163 } 164} 165#endif /* UNIV_DEBUG */ 166 167/*************************************************************//** 168Looks for an element in a hash table. 169@return pointer to the data of the first hash table node in chain 170having the fold number, NULL if not found */ 171UNIV_INLINE 172const rec_t* 173ha_search_and_get_data( 174/*===================*/ 175 hash_table_t* table, /*!< in: hash table */ 176 ulint fold) /*!< in: folded value of the searched data */ 177{ 178 ha_node_t* node; 179 180 hash_assert_can_search(table, fold); 181 ut_ad(btr_search_enabled); 182 183 node = ha_chain_get_first(table, fold); 184 185 while (node) { 186 if (node->fold == fold) { 187 188 return(node->data); 189 } 190 191 node = ha_chain_get_next(node); 192 } 193 194 return(NULL); 195} 196 197/*********************************************************//** 198Looks for an element when we know the pointer to the data. 199@return pointer to the hash table node, NULL if not found in the table */ 200UNIV_INLINE 201ha_node_t* 202ha_search_with_data( 203/*================*/ 204 hash_table_t* table, /*!< in: hash table */ 205 ulint fold, /*!< in: folded value of the searched data */ 206 const rec_t* data) /*!< in: pointer to the data */ 207{ 208 ha_node_t* node; 209 210 hash_assert_can_search(table, fold); 211 212 ut_ad(btr_search_enabled); 213 214 node = ha_chain_get_first(table, fold); 215 216 while (node) { 217 if (node->data == data) { 218 219 return(node); 220 } 221 222 node = ha_chain_get_next(node); 223 } 224 225 return(NULL); 226} 227 228/*********************************************************//** 229Looks for an element when we know the pointer to the data, and deletes 230it from the hash table, if found. 231@return TRUE if found */ 232UNIV_INLINE 233ibool 234ha_search_and_delete_if_found( 235/*==========================*/ 236 hash_table_t* table, /*!< in: hash table */ 237 ulint fold, /*!< in: folded value of the searched data */ 238 const rec_t* data) /*!< in: pointer to the data */ 239{ 240 ha_node_t* node; 241 242 hash_assert_can_modify(table, fold); 243 ut_ad(btr_search_enabled); 244 245 node = ha_search_with_data(table, fold, data); 246 247 if (node) { 248 ha_delete_hash_node(table, node); 249 250 return(TRUE); 251 } 252 253 return(FALSE); 254} 255