ha0ha.c 8.55 KB
Newer Older
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
/************************************************************************
The hash table with external chains

(c) 1994-1997 Innobase Oy

Created 8/22/1994 Heikki Tuuri
*************************************************************************/

#include "ha0ha.h"
#ifdef UNIV_NONINL
#include "ha0ha.ic"
#endif

#include "buf0buf.h"

/*****************************************************************
Creates a hash table with >= n array cells. The actual number of cells is
chosen to be a prime number slightly bigger than n. */

hash_table_t*
ha_create(
/*======*/
				/* out, own: created table */
	ibool	in_btr_search,	/* in: TRUE if the hash table is used in
				the btr_search module */
	ulint	n,		/* in: number of array cells */
	ulint	n_mutexes,	/* in: number of mutexes to protect the
				hash table: must be a power of 2, or 0 */
	ulint	mutex_level)	/* in: level of the mutexes in the latching
				order: this is used in the debug version */
{
	hash_table_t*	table;
	ulint		i;

	table = hash_create(n);

heikki@hundin.mysql.fi's avatar
heikki@hundin.mysql.fi committed
37 38 39 40 41 42
	if (in_btr_search) {
		table->adaptive = TRUE;
	} else {
		table->adaptive = FALSE;
	}

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
	if (n_mutexes == 0) {
		if (in_btr_search) {
			table->heap = mem_heap_create_in_btr_search(4096);
		} else {
			table->heap = mem_heap_create_in_buffer(4096);
		}

		return(table);
	}
	
	hash_create_mutexes(table, n_mutexes, mutex_level);

	table->heaps = mem_alloc(n_mutexes * sizeof(void*));

	for (i = 0; i < n_mutexes; i++) {
		if (in_btr_search) {
			table->heaps[i] = mem_heap_create_in_btr_search(4096);
		} else {
			table->heaps[i] = mem_heap_create_in_buffer(4096);
		}
	}
	
	return(table);
}

/*****************************************************************
Checks that a hash table node is in the chain. */

ibool
ha_node_in_chain(
/*=============*/
				/* out: TRUE if in chain */
	hash_cell_t*	cell,	/* in: hash table cell */
	ha_node_t*	node)	/* in: external chain node */
{
	ha_node_t*	node2;
	
	node2 = cell->node;

	while (node2 != NULL) {

		if (node2 == node) {

			return(TRUE);
		}

		node2 = node2->next;
	}

	return(FALSE);
}

/*****************************************************************
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. */

ibool
ha_insert_for_fold(
/*===============*/
				/* 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! */
	void*		data)	/* in: data, must not be NULL */
{
	hash_cell_t*	cell;
	ha_node_t*	node;
	ha_node_t*	prev_node;
heikki@hundin.mysql.fi's avatar
heikki@hundin.mysql.fi committed
115
	buf_block_t*	prev_block;
116 117 118 119 120 121 122 123 124 125 126 127 128
	ulint		hash;

	ut_ad(table && data);
	ut_ad(!table->mutexes || mutex_own(hash_get_mutex(table, fold)));
	
	hash = hash_calc_hash(fold, table);

	cell = hash_get_nth_cell(table, hash);

	prev_node = cell->node;

	while (prev_node != NULL) {
		if (prev_node->fold == fold) {
heikki@hundin.mysql.fi's avatar
heikki@hundin.mysql.fi committed
129 130 131 132 133 134
			if (table->adaptive) {
				prev_block = buf_block_align(prev_node->data);
				ut_a(prev_block->n_pointers > 0);
				prev_block->n_pointers--;
				buf_block_align(data)->n_pointers++;
			}
135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157

			prev_node->data = data;

			return(TRUE);
		}

		prev_node = prev_node->next;
	}
	
	/* We have to allocate a new chain node */

	node = mem_heap_alloc(hash_get_heap(table, fold), sizeof(ha_node_t));

	if (node == NULL) {
		/* It was a btr search type memory heap and at the moment
		no more memory could be allocated: return */

		ut_ad(hash_get_heap(table, fold)->type & MEM_HEAP_BTR_SEARCH);

		return(FALSE);
	}
	
	ha_node_set_data(node, data);
heikki@hundin.mysql.fi's avatar
heikki@hundin.mysql.fi committed
158 159 160 161 162

	if (table->adaptive) {
		buf_block_align(data)->n_pointers++;
	}

163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194
	node->fold = fold;

	node->next = NULL;

	prev_node = cell->node;

	if (prev_node == NULL) {

		cell->node = node;

		return(TRUE);
	}
		
	while (prev_node->next != NULL) {

		prev_node = prev_node->next;
	}

	prev_node->next = node;

	return(TRUE);
}	

/***************************************************************
Deletes a hash node. */

void
ha_delete_hash_node(
/*================*/
	hash_table_t*	table,		/* in: hash table */
	ha_node_t*	del_node)	/* in: node to be deleted */
{
heikki@hundin.mysql.fi's avatar
heikki@hundin.mysql.fi committed
195 196 197 198 199
	if (table->adaptive) {
		ut_a(buf_block_align(del_node->data)->n_pointers > 0);
		buf_block_align(del_node->data)->n_pointers--;
	}

200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219
	HASH_DELETE_AND_COMPACT(ha_node_t, next, table, del_node);
}

/*****************************************************************
Deletes an entry from a hash table. */

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 */
{
	ha_node_t*	node;

	ut_ad(!table->mutexes || mutex_own(hash_get_mutex(table, fold)));

	node = ha_search_with_data(table, fold, data);

heikki@hundin.mysql.fi's avatar
heikki@hundin.mysql.fi committed
220
	ut_a(node);
221 222 223 224

	ha_delete_hash_node(table, node);
}	

heikki@hundin.mysql.fi's avatar
heikki@hundin.mysql.fi committed
225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253
/*************************************************************
Looks for an element when we know the pointer to the data, and updates
the pointer to data, if found. */

void
ha_search_and_update_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 */
	void*		new_data)/* in: new pointer to the data */
{
	ha_node_t*	node;

	ut_ad(!table->mutexes || mutex_own(hash_get_mutex(table, fold)));

	node = ha_search_with_data(table, fold, data);

	if (node) {
		if (table->adaptive) {
			ut_a(buf_block_align(node->data)->n_pointers > 0);
			buf_block_align(node->data)->n_pointers--;
			buf_block_align(new_data)->n_pointers++;
		}

		node->data = new_data;
	}
}

254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283
/*********************************************************************
Removes from the chain determined by fold all nodes whose data pointer
points to the page given. */

void
ha_remove_all_nodes_to_page(
/*========================*/
	hash_table_t*	table,	/* in: hash table */
	ulint		fold,	/* in: fold value */
	page_t*		page)	/* in: buffer page */
{
	ha_node_t*	node;

	ut_ad(!table->mutexes || mutex_own(hash_get_mutex(table, fold)));

	node = ha_chain_get_first(table, fold);

	while (node) {
		if (buf_frame_align(ha_node_get_data(node)) == page) {

			/* Remove the hash node */

			ha_delete_hash_node(table, node);

			/* Start again from the first node in the chain
			because the deletion may compact the heap of
			nodes and move other nodes! */

			node = ha_chain_get_first(table, fold);
		} else {
heikki@hundin.mysql.fi's avatar
heikki@hundin.mysql.fi committed
284
			node = ha_chain_get_next(node);
285 286
		}
	}
heikki@hundin.mysql.fi's avatar
heikki@hundin.mysql.fi committed
287
#ifdef UNIV_DEBUG
heikki@hundin.mysql.fi's avatar
heikki@hundin.mysql.fi committed
288 289 290 291 292 293 294
	/* Check that all nodes really got deleted */
	
	node = ha_chain_get_first(table, fold);

	while (node) {
		ut_a(buf_frame_align(ha_node_get_data(node)) != page);

heikki@hundin.mysql.fi's avatar
heikki@hundin.mysql.fi committed
295
		node = ha_chain_get_next(node);
heikki@hundin.mysql.fi's avatar
heikki@hundin.mysql.fi committed
296
	}
heikki@hundin.mysql.fi's avatar
heikki@hundin.mysql.fi committed
297
#endif
298 299 300 301 302 303 304 305 306 307 308 309 310
}

/*****************************************************************
Validates a hash table. */

ibool
ha_validate(
/*========*/
				/* out: TRUE if ok */
	hash_table_t*	table)	/* in: hash table */
{
	hash_cell_t*	cell;
	ha_node_t*	node;
heikki@hundin.mysql.fi's avatar
heikki@hundin.mysql.fi committed
311
	ibool		ok	= TRUE;
312 313 314 315 316 317 318 319 320
	ulint		i;

	for (i = 0; i < hash_get_n_cells(table); i++) {

		cell = hash_get_nth_cell(table, i);

		node = cell->node;

		while (node) {
heikki@hundin.mysql.fi's avatar
heikki@hundin.mysql.fi committed
321 322 323 324 325 326 327 328 329
			if (hash_calc_hash(node->fold, table) != i) {
				ut_print_timestamp(stderr);
				fprintf(stderr,
"InnoDB: Error: hash table node fold value %lu does not\n"
"InnoDB: match with the cell number %lu.\n",
					node->fold, i);

				ok = FALSE;
			}
330 331 332 333 334

			node = node->next;
		}
	}

heikki@hundin.mysql.fi's avatar
heikki@hundin.mysql.fi committed
335
	return(ok);
336 337 338 339 340 341 342 343
}	

/*****************************************************************
Prints info of a hash table. */

void
ha_print_info(
/*==========*/
heikki@hundin.mysql.fi's avatar
heikki@hundin.mysql.fi committed
344 345
	char*		buf,	/* in/out: buffer where to print */
	char*		buf_end,/* in: buffer end */
346 347 348
	hash_table_t*	table)	/* in: hash table */
{
	hash_cell_t*	cell;
heikki@hundin.mysql.fi's avatar
heikki@hundin.mysql.fi committed
349 350 351 352
/*	ha_node_t*	node;
	ulint		nodes	= 0;
	ulint		len	= 0;
	ulint		max_len	= 0; */
heikki@hundin.mysql.fi's avatar
heikki@hundin.mysql.fi committed
353
	ulint		cells	= 0;
heikki@hundin.mysql.fi's avatar
heikki@hundin.mysql.fi committed
354
	ulint		n_bufs;
355 356
	ulint		i;
	
heikki@hundin.mysql.fi's avatar
heikki@hundin.mysql.fi committed
357 358 359 360
	if (buf_end - buf < 200) {
		return;
	}

361 362 363 364 365 366 367
	for (i = 0; i < hash_get_n_cells(table); i++) {

		cell = hash_get_nth_cell(table, i);

		if (cell->node) {

			cells++;
heikki@hundin.mysql.fi's avatar
heikki@hundin.mysql.fi committed
368
/*
369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387
			len = 0;

			node = cell->node;

			for (;;) {
				len++;
				nodes++;

				if (ha_chain_get_next(table, node) == NULL) {

					break;
				}

				node = node->next;
			}

			if (len > max_len) {
				max_len = len;
			}
heikki@hundin.mysql.fi's avatar
heikki@hundin.mysql.fi committed
388
*/
389 390 391
		}
	}

heikki@hundin.mysql.fi's avatar
heikki@hundin.mysql.fi committed
392 393 394 395
	buf += sprintf(buf,
"Hash table size %lu, used cells %lu", hash_get_n_cells(table), cells);

	if (table->heaps == NULL && table->heap != NULL) {
heikki@hundin.mysql.fi's avatar
heikki@hundin.mysql.fi committed
396 397 398 399 400 401 402 403 404 405 406

		/* This calculation is intended for the adaptive hash
		index: how many buffer frames we have reserved? */

		n_bufs = UT_LIST_GET_LEN(table->heap->base) - 1;

		if (table->heap->free_block) {
			n_bufs++;
		}
				
	        buf += sprintf(buf, ", node heap has %lu buffer(s)\n", n_bufs);
heikki@hundin.mysql.fi's avatar
heikki@hundin.mysql.fi committed
407
	}
408
}