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