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