1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
|
/******************************************************
The hash table with external chains
(c) 1994-1997 Innobase Oy
Created 8/18/1994 Heikki Tuuri
*******************************************************/
#ifndef ha0ha_h
#define ha0ha_h
#include "univ.i"
#include "hash0hash.h"
#include "page0types.h"
#include "buf0types.h"
/*****************************************************************
Looks for an element in a hash table. */
UNIV_INLINE
void*
ha_search_and_get_data(
/*===================*/
/* out: pointer to the data of the first hash
table node in chain having the fold number,
NULL if not found */
hash_table_t* table, /* in: hash table */
ulint fold); /* in: folded value of the searched data */
/*************************************************************
Looks for an element when we know the pointer to the data and updates
the pointer to data if found. */
UNIV_INTERN
void
ha_search_and_update_if_found_func(
/*===============================*/
hash_table_t* table, /* in: hash table */
ulint fold, /* in: folded value of the searched data */
void* data, /* in: pointer to the data */
#ifdef UNIV_DEBUG
buf_block_t* new_block,/* in: block containing new_data */
#endif
void* new_data);/* in: new pointer to the data */
#ifdef UNIV_DEBUG
# define ha_search_and_update_if_found(table,fold,data,new_block,new_data) \
ha_search_and_update_if_found_func(table,fold,data,new_block,new_data)
#else
# define ha_search_and_update_if_found(table,fold,data,new_block,new_data) \
ha_search_and_update_if_found_func(table,fold,data,new_data)
#endif
/*****************************************************************
Creates a hash table with >= n array cells. The actual number of cells is
chosen to be a prime number slightly bigger than n. */
UNIV_INTERN
hash_table_t*
ha_create_func(
/*===========*/
/* out, own: created table */
ulint n, /* in: number of array cells */
#ifdef UNIV_SYNC_DEBUG
ulint mutex_level, /* in: level of the mutexes in the latching
order: this is used in the debug version */
#endif /* UNIV_SYNC_DEBUG */
ulint n_mutexes); /* in: number of mutexes to protect the
hash table: must be a power of 2 */
#ifdef UNIV_SYNC_DEBUG
# define ha_create(n_c,n_m,level) ha_create_func(n_c,level,n_m)
#else /* UNIV_SYNC_DEBUG */
# define ha_create(n_c,n_m,level) ha_create_func(n_c,n_m)
#endif /* UNIV_SYNC_DEBUG */
/*****************************************************************
Empties a hash table and frees the memory heaps. */
UNIV_INTERN
void
ha_clear(
/*=====*/
hash_table_t* table); /* in, own: hash table */
/*****************************************************************
Inserts an entry into a hash table. If an entry with the same fold number
is found, its node is updated to point to the new data, and no new node
is inserted. */
UNIV_INTERN
ibool
ha_insert_for_fold_func(
/*====================*/
/* out: TRUE if succeed, FALSE if no more
memory could be allocated */
hash_table_t* table, /* in: hash table */
ulint fold, /* in: folded value of data; if a node with
the same fold value already exists, it is
updated to point to the same data, and no new
node is created! */
#ifdef UNIV_DEBUG
buf_block_t* block, /* in: buffer block containing the data */
#endif /* UNIV_DEBUG */
void* data); /* in: data, must not be NULL */
#ifdef UNIV_DEBUG
# define ha_insert_for_fold(t,f,b,d) ha_insert_for_fold_func(t,f,b,d)
#else
# define ha_insert_for_fold(t,f,b,d) ha_insert_for_fold_func(t,f,d)
#endif
/*****************************************************************
Deletes an entry from a hash table. */
UNIV_INTERN
void
ha_delete(
/*======*/
hash_table_t* table, /* in: hash table */
ulint fold, /* in: folded value of data */
void* data); /* in: data, must not be NULL and must exist
in the hash table */
/*************************************************************
Looks for an element when we know the pointer to the data and deletes
it from the hash table if found. */
UNIV_INLINE
ibool
ha_search_and_delete_if_found(
/*==========================*/
/* out: TRUE if found */
hash_table_t* table, /* in: hash table */
ulint fold, /* in: folded value of the searched data */
void* data); /* in: pointer to the data */
/*********************************************************************
Removes from the chain determined by fold all nodes whose data pointer
points to the page given. */
UNIV_INTERN
void
ha_remove_all_nodes_to_page(
/*========================*/
hash_table_t* table, /* in: hash table */
ulint fold, /* in: fold value */
const page_t* page); /* in: buffer page */
/*****************************************************************
Validates a given range of the cells in hash table. */
UNIV_INTERN
ibool
ha_validate(
/*========*/
/* out: TRUE if ok */
hash_table_t* table, /* in: hash table */
ulint start_index, /* in: start index */
ulint end_index); /* in: end index */
/*****************************************************************
Prints info of a hash table. */
UNIV_INTERN
void
ha_print_info(
/*==========*/
FILE* file, /* in: file where to print */
hash_table_t* table); /* in: hash table */
/* The hash table external chain node */
typedef struct ha_node_struct ha_node_t;
struct ha_node_struct {
ha_node_t* next; /* next chain node or NULL if none */
#ifdef UNIV_DEBUG
buf_block_t* block; /* buffer block containing the data, or NULL */
#endif /* UNIV_DEBUG */
void* data; /* pointer to the data */
ulint fold; /* fold value for the data */
};
#ifndef UNIV_NONINL
#include "ha0ha.ic"
#endif
#endif
|