1/*****************************************************************************
2
3Copyright (c) 1997, 2015, 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 as published by the Free Software
7Foundation; version 2 of the License.
8
9This program is distributed in the hope that it will be useful, but WITHOUT
10ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
12
13You should have received a copy of the GNU General Public License along with
14this program; if not, write to the Free Software Foundation, Inc.,
1551 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
16
17*****************************************************************************/
18
19/**************************************************//**
20@file include/hash0hash.ic
21The simple hash table utility
22
23Created 5/20/1997 Heikki Tuuri
24*******************************************************/
25
26#include "ut0rnd.h"
27
28/************************************************************//**
29Gets the nth cell in a hash table.
30@return pointer to cell */
31UNIV_INLINE
32hash_cell_t*
33hash_get_nth_cell(
34/*==============*/
35 hash_table_t* table, /*!< in: hash table */
36 ulint n) /*!< in: cell index */
37{
38 ut_ad(table);
39 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
40 ut_ad(n < table->n_cells);
41
42 return(table->array + n);
43}
44
45/*************************************************************//**
46Clears a hash table so that all the cells become empty. */
47UNIV_INLINE
48void
49hash_table_clear(
50/*=============*/
51 hash_table_t* table) /*!< in/out: hash table */
52{
53 ut_ad(table);
54 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
55 memset(table->array, 0x0,
56 table->n_cells * sizeof(*table->array));
57}
58
59/*************************************************************//**
60Returns the number of cells in a hash table.
61@return number of cells */
62UNIV_INLINE
63ulint
64hash_get_n_cells(
65/*=============*/
66 hash_table_t* table) /*!< in: table */
67{
68 ut_ad(table);
69 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
70 return(table->n_cells);
71}
72
73/**************************************************************//**
74Calculates the hash value from a folded value.
75@return hashed value */
76UNIV_INLINE
77ulint
78hash_calc_hash(
79/*===========*/
80 ulint fold, /*!< in: folded value */
81 hash_table_t* table) /*!< in: hash table */
82{
83 ut_ad(table);
84 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
85 return(ut_hash_ulint(fold, table->n_cells));
86}
87
88/************************************************************//**
89Gets the sync object index for a fold value in a hash table.
90@return index */
91UNIV_INLINE
92ulint
93hash_get_sync_obj_index(
94/*====================*/
95 hash_table_t* table, /*!< in: hash table */
96 ulint fold) /*!< in: fold */
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(ut_is_2pow(table->n_sync_obj));
102 return(ut_2pow_remainder(hash_calc_hash(fold, table),
103 table->n_sync_obj));
104}
105
106/************************************************************//**
107Gets the nth heap in a hash table.
108@return mem heap */
109UNIV_INLINE
110mem_heap_t*
111hash_get_nth_heap(
112/*==============*/
113 hash_table_t* table, /*!< in: hash table */
114 ulint i) /*!< in: index of the heap */
115{
116 ut_ad(table);
117 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
118 ut_ad(table->type != HASH_TABLE_SYNC_NONE);
119 ut_ad(i < table->n_sync_obj);
120
121 return(table->heaps[i]);
122}
123
124/************************************************************//**
125Gets the heap for a fold value in a hash table.
126@return mem heap */
127UNIV_INLINE
128mem_heap_t*
129hash_get_heap(
130/*==========*/
131 hash_table_t* table, /*!< in: hash table */
132 ulint fold) /*!< in: fold */
133{
134 ulint i;
135
136 ut_ad(table);
137 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
138
139 if (table->heap) {
140 return(table->heap);
141 }
142
143 i = hash_get_sync_obj_index(table, fold);
144
145 return(hash_get_nth_heap(table, i));
146}
147
148/************************************************************//**
149Gets the nth mutex in a hash table.
150@return mutex */
151UNIV_INLINE
152ib_mutex_t*
153hash_get_nth_mutex(
154/*===============*/
155 hash_table_t* table, /*!< in: hash table */
156 ulint i) /*!< in: index of the mutex */
157{
158 ut_ad(table);
159 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
160 ut_ad(table->type == HASH_TABLE_SYNC_MUTEX);
161 ut_ad(i < table->n_sync_obj);
162
163 return(table->sync_obj.mutexes + i);
164}
165
166/************************************************************//**
167Gets the mutex for a fold value in a hash table.
168@return mutex */
169UNIV_INLINE
170ib_mutex_t*
171hash_get_mutex(
172/*===========*/
173 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->magic_n == HASH_TABLE_MAGIC_N);
180
181 i = hash_get_sync_obj_index(table, fold);
182
183 return(hash_get_nth_mutex(table, i));
184}
185
186/************************************************************//**
187Gets the nth rw_lock in a hash table.
188@return rw_lock */
189UNIV_INLINE
190rw_lock_t*
191hash_get_nth_lock(
192/*==============*/
193 hash_table_t* table, /*!< in: hash table */
194 ulint i) /*!< in: index of the rw_lock */
195{
196 ut_ad(table);
197 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
198 ut_ad(table->type == HASH_TABLE_SYNC_RW_LOCK);
199 ut_ad(i < table->n_sync_obj);
200
201 return(table->sync_obj.rw_locks + i);
202}
203
204/************************************************************//**
205Gets the rw_lock for a fold value in a hash table.
206@return rw_lock */
207UNIV_INLINE
208rw_lock_t*
209hash_get_lock(
210/*==========*/
211 hash_table_t* table, /*!< in: hash table */
212 ulint fold) /*!< in: fold */
213{
214 ulint i;
215
216 ut_ad(table);
217 ut_ad(table->type == HASH_TABLE_SYNC_RW_LOCK);
218 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
219
220 i = hash_get_sync_obj_index(table, fold);
221
222 return(hash_get_nth_lock(table, i));
223}
224
225/** If not appropriate rw_lock for a fold value in a hash table,
226relock S-lock the another rw_lock until appropriate for a fold value.
227@param[in] hash_lock latched rw_lock to be confirmed
228@param[in] table hash table
229@param[in] fold fold value
230@return latched rw_lock */
231UNIV_INLINE
232rw_lock_t*
233hash_lock_s_confirm(
234 rw_lock_t* hash_lock,
235 hash_table_t* table,
236 ulint fold)
237{
238 ut_ad(rw_lock_own(hash_lock, RW_LOCK_S));
239
240 rw_lock_t* hash_lock_tmp = hash_get_lock(table, fold);
241
242 while (hash_lock_tmp != hash_lock) {
243 rw_lock_s_unlock(hash_lock);
244 hash_lock = hash_lock_tmp;
245 rw_lock_s_lock(hash_lock);
246 hash_lock_tmp = hash_get_lock(table, fold);
247 }
248
249 return(hash_lock);
250}
251
252/** If not appropriate rw_lock for a fold value in a hash table,
253relock X-lock the another rw_lock until appropriate for a fold value.
254@param[in] hash_lock latched rw_lock to be confirmed
255@param[in] table hash table
256@param[in] fold fold value
257@return latched rw_lock */
258UNIV_INLINE
259rw_lock_t*
260hash_lock_x_confirm(
261 rw_lock_t* hash_lock,
262 hash_table_t* table,
263 ulint fold)
264{
265 ut_ad(rw_lock_own(hash_lock, RW_LOCK_X));
266
267 rw_lock_t* hash_lock_tmp = hash_get_lock(table, fold);
268
269 while (hash_lock_tmp != hash_lock) {
270 rw_lock_x_unlock(hash_lock);
271 hash_lock = hash_lock_tmp;
272 rw_lock_x_lock(hash_lock);
273 hash_lock_tmp = hash_get_lock(table, fold);
274 }
275
276 return(hash_lock);
277}
278