1/*****************************************************************************
2
3Copyright (c) 1994, 2016, Oracle and/or its affiliates. All Rights Reserved.
4Copyright (c) 2018, MariaDB Corporation.
5
6This program is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free Software
8Foundation; version 2 of the License.
9
10This program is distributed in the hope that it will be useful, but WITHOUT
11ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
12FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
13
14You should have received a copy of the GNU General Public License along with
15this program; if not, write to the Free Software Foundation, Inc.,
1651 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
17
18*****************************************************************************/
19
20/**************************************************//**
21@file include/ha0ha.h
22The hash table with external chains
23
24Created 8/18/1994 Heikki Tuuri
25*******************************************************/
26
27#ifndef ha0ha_h
28#define ha0ha_h
29
30#include "univ.i"
31
32#include "hash0hash.h"
33#include "page0types.h"
34#include "buf0types.h"
35#include "rem0types.h"
36
37#ifdef BTR_CUR_HASH_ADAPT
38/*************************************************************//**
39Looks for an element in a hash table.
40@return pointer to the data of the first hash table node in chain
41having the fold number, NULL if not found */
42UNIV_INLINE
43const rec_t*
44ha_search_and_get_data(
45/*===================*/
46 hash_table_t* table, /*!< in: hash table */
47 ulint fold); /*!< in: folded value of the searched data */
48/*********************************************************//**
49Looks for an element when we know the pointer to the data and updates
50the pointer to data if found.
51@return TRUE if found */
52ibool
53ha_search_and_update_if_found_func(
54/*===============================*/
55 hash_table_t* table, /*!< in/out: hash table */
56 ulint fold, /*!< in: folded value of the searched data */
57 const rec_t* data, /*!< in: pointer to the data */
58#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
59 buf_block_t* new_block,/*!< in: block containing new_data */
60#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
61 const rec_t* new_data);/*!< in: new pointer to the data */
62
63#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
64/** Looks for an element when we know the pointer to the data and
65updates the pointer to data if found.
66@param table in/out: hash table
67@param fold in: folded value of the searched data
68@param data in: pointer to the data
69@param new_block in: block containing new_data
70@param new_data in: new pointer to the data */
71# define ha_search_and_update_if_found(table,fold,data,new_block,new_data) \
72 ha_search_and_update_if_found_func(table,fold,data,new_block,new_data)
73#else /* UNIV_AHI_DEBUG || UNIV_DEBUG */
74/** Looks for an element when we know the pointer to the data and
75updates the pointer to data if found.
76@param table in/out: hash table
77@param fold in: folded value of the searched data
78@param data in: pointer to the data
79@param new_block ignored: block containing new_data
80@param new_data in: new pointer to the data */
81# define ha_search_and_update_if_found(table,fold,data,new_block,new_data) \
82 ha_search_and_update_if_found_func(table,fold,data,new_data)
83#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
84#endif /* BTR_CUR_HASH_ADAPT */
85
86/*************************************************************//**
87Creates a hash table with at least n array cells. The actual number
88of cells is chosen to be a prime number slightly bigger than n.
89@return own: created table */
90hash_table_t*
91ib_create(
92/*======*/
93 ulint n, /*!< in: number of array cells */
94 latch_id_t id, /*!< in: latch ID */
95 ulint n_mutexes,/*!< in: number of mutexes to protect the
96 hash table: must be a power of 2, or 0 */
97 ulint type); /*!< in: type of datastructure for which
98 the memory heap is going to be used e.g.:
99 MEM_HEAP_FOR_BTR_SEARCH or
100 MEM_HEAP_FOR_PAGE_HASH */
101
102/** Recreate a hash table with at least n array cells. The actual number
103of cells is chosen to be a prime number slightly bigger than n.
104The new cells are all cleared. The heaps are recreated.
105The sync objects are reused.
106@param[in,out] table hash table to be resuzed (to be freed later)
107@param[in] n number of array cells
108@return resized new table */
109hash_table_t*
110ib_recreate(
111 hash_table_t* table,
112 ulint n);
113
114/*************************************************************//**
115Empties a hash table and frees the memory heaps. */
116void
117ha_clear(
118/*=====*/
119 hash_table_t* table); /*!< in, own: hash table */
120
121#ifdef BTR_CUR_HASH_ADAPT
122/*************************************************************//**
123Inserts an entry into a hash table. If an entry with the same fold number
124is found, its node is updated to point to the new data, and no new node
125is inserted.
126@return TRUE if succeed, FALSE if no more memory could be allocated */
127ibool
128ha_insert_for_fold_func(
129/*====================*/
130 hash_table_t* table, /*!< in: hash table */
131 ulint fold, /*!< in: folded value of data; if a node with
132 the same fold value already exists, it is
133 updated to point to the same data, and no new
134 node is created! */
135#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
136 buf_block_t* block, /*!< in: buffer block containing the data */
137#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
138 const rec_t* data); /*!< in: data, must not be NULL */
139
140#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
141/**
142Inserts an entry into a hash table. If an entry with the same fold number
143is found, its node is updated to point to the new data, and no new node
144is inserted.
145@return TRUE if succeed, FALSE if no more memory could be allocated
146@param t in: hash table
147@param f in: folded value of data
148@param b in: buffer block containing the data
149@param d in: data, must not be NULL */
150# define ha_insert_for_fold(t,f,b,d) do { \
151 ha_insert_for_fold_func(t,f,b,d); \
152 MONITOR_INC(MONITOR_ADAPTIVE_HASH_ROW_ADDED); \
153} while(0)
154#else /* UNIV_AHI_DEBUG || UNIV_DEBUG */
155/**
156Inserts an entry into a hash table. If an entry with the same fold number
157is found, its node is updated to point to the new data, and no new node
158is inserted.
159@return TRUE if succeed, FALSE if no more memory could be allocated
160@param t in: hash table
161@param f in: folded value of data
162@param b ignored: buffer block containing the data
163@param d in: data, must not be NULL */
164# define ha_insert_for_fold(t,f,b,d) do { \
165 ha_insert_for_fold_func(t,f,d); \
166 MONITOR_INC(MONITOR_ADAPTIVE_HASH_ROW_ADDED); \
167} while (0)
168#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
169
170/*********************************************************//**
171Looks for an element when we know the pointer to the data and deletes
172it from the hash table if found.
173@return TRUE if found */
174UNIV_INLINE
175ibool
176ha_search_and_delete_if_found(
177/*==========================*/
178 hash_table_t* table, /*!< in: hash table */
179 ulint fold, /*!< in: folded value of the searched data */
180 const rec_t* data); /*!< in: pointer to the data */
181
182/*****************************************************************//**
183Removes from the chain determined by fold all nodes whose data pointer
184points to the page given. */
185void
186ha_remove_all_nodes_to_page(
187/*========================*/
188 hash_table_t* table, /*!< in: hash table */
189 ulint fold, /*!< in: fold value */
190 const page_t* page); /*!< in: buffer page */
191#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
192/*************************************************************//**
193Validates a given range of the cells in hash table.
194@return TRUE if ok */
195ibool
196ha_validate(
197/*========*/
198 hash_table_t* table, /*!< in: hash table */
199 ulint start_index, /*!< in: start index */
200 ulint end_index); /*!< in: end index */
201#endif /* defined UNIV_AHI_DEBUG || defined UNIV_DEBUG */
202
203/** The hash table external chain node */
204struct ha_node_t {
205 ulint fold; /*!< fold value for the data */
206 ha_node_t* next; /*!< next chain node or NULL if none */
207#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
208 buf_block_t* block; /*!< buffer block containing the data, or NULL */
209#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
210 const rec_t* data; /*!< pointer to the data */
211};
212#endif /* BTR_CUR_HASH_ADAPT */
213
214#if defined UNIV_DEBUG && defined BTR_CUR_HASH_ADAPT
215/********************************************************************//**
216Assert that the synchronization object in a hash operation involving
217possible change in the hash table is held.
218Note that in case of mutexes we assert that mutex is owned while in case
219of rw-locks we assert that it is held in exclusive mode. */
220UNIV_INLINE
221void
222hash_assert_can_modify(
223/*===================*/
224 hash_table_t* table, /*!< in: hash table */
225 ulint fold); /*!< in: fold value */
226/********************************************************************//**
227Assert that the synchronization object in a hash search operation is held.
228Note that in case of mutexes we assert that mutex is owned while in case
229of rw-locks we assert that it is held either in x-mode or s-mode. */
230UNIV_INLINE
231void
232hash_assert_can_search(
233/*===================*/
234 hash_table_t* table, /*!< in: hash table */
235 ulint fold); /*!< in: fold value */
236#else /* UNIV_DEBUG */
237#define hash_assert_can_modify(t, f)
238#define hash_assert_can_search(t, f)
239#endif /* UNIV_DEBUG */
240
241#include "ha0ha.ic"
242
243#endif
244