/*****************************************************************************

Copyright (c) 1997, 2015, Oracle and/or its affiliates. All Rights Reserved.

This program is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free Software
Foundation; version 2 of the License.

This program is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with
this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA

*****************************************************************************/

/**************************************************//**
@file include/hash0hash.ic
The simple hash table utility

Created 5/20/1997 Heikki Tuuri
*******************************************************/

#include "ut0rnd.h"

/************************************************************//**
Gets the nth cell in a hash table.
@return pointer to cell */
UNIV_INLINE
hash_cell_t*
hash_get_nth_cell(
/*==============*/
	hash_table_t*	table,	/*!< in: hash table */
	ulint		n)	/*!< in: cell index */
{
	ut_ad(table);
	ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
	ut_ad(n < table->n_cells);

	return(table->array + n);
}

/*************************************************************//**
Clears a hash table so that all the cells become empty. */
UNIV_INLINE
void
hash_table_clear(
/*=============*/
	hash_table_t*	table)	/*!< in/out: hash table */
{
	ut_ad(table);
	ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
	memset(table->array, 0x0,
	       table->n_cells * sizeof(*table->array));
}

/*************************************************************//**
Returns the number of cells in a hash table.
@return number of cells */
UNIV_INLINE
ulint
hash_get_n_cells(
/*=============*/
	hash_table_t*	table)	/*!< in: table */
{
	ut_ad(table);
	ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
	return(table->n_cells);
}

/**************************************************************//**
Calculates the hash value from a folded value.
@return hashed value */
UNIV_INLINE
ulint
hash_calc_hash(
/*===========*/
	ulint		fold,	/*!< in: folded value */
	hash_table_t*	table)	/*!< in: hash table */
{
	ut_ad(table);
	ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
	return(ut_hash_ulint(fold, table->n_cells));
}

/************************************************************//**
Gets the sync object index for a fold value in a hash table.
@return index */
UNIV_INLINE
ulint
hash_get_sync_obj_index(
/*====================*/
	hash_table_t*	table,	/*!< in: hash table */
	ulint		fold)	/*!< in: fold */
{
	ut_ad(table);
	ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
	ut_ad(table->type != HASH_TABLE_SYNC_NONE);
	ut_ad(ut_is_2pow(table->n_sync_obj));
	return(ut_2pow_remainder(hash_calc_hash(fold, table),
				 table->n_sync_obj));
}

/************************************************************//**
Gets the nth heap in a hash table.
@return mem heap */
UNIV_INLINE
mem_heap_t*
hash_get_nth_heap(
/*==============*/
	hash_table_t*	table,	/*!< in: hash table */
	ulint		i)	/*!< in: index of the heap */
{
	ut_ad(table);
	ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
	ut_ad(table->type != HASH_TABLE_SYNC_NONE);
	ut_ad(i < table->n_sync_obj);

	return(table->heaps[i]);
}

/************************************************************//**
Gets the heap for a fold value in a hash table.
@return mem heap */
UNIV_INLINE
mem_heap_t*
hash_get_heap(
/*==========*/
	hash_table_t*	table,	/*!< in: hash table */
	ulint		fold)	/*!< in: fold */
{
	ulint	i;

	ut_ad(table);
	ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);

	if (table->heap) {
		return(table->heap);
	}

	i = hash_get_sync_obj_index(table, fold);

	return(hash_get_nth_heap(table, i));
}

/************************************************************//**
Gets the nth mutex in a hash table.
@return mutex */
UNIV_INLINE
ib_mutex_t*
hash_get_nth_mutex(
/*===============*/
	hash_table_t*	table,	/*!< in: hash table */
	ulint		i)	/*!< in: index of the mutex */
{
	ut_ad(table);
	ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
	ut_ad(table->type == HASH_TABLE_SYNC_MUTEX);
	ut_ad(i < table->n_sync_obj);

	return(table->sync_obj.mutexes + i);
}

/************************************************************//**
Gets the mutex for a fold value in a hash table.
@return mutex */
UNIV_INLINE
ib_mutex_t*
hash_get_mutex(
/*===========*/
	hash_table_t*	table,	/*!< in: hash table */
	ulint		fold)	/*!< in: fold */
{
	ulint	i;

	ut_ad(table);
	ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);

	i = hash_get_sync_obj_index(table, fold);

	return(hash_get_nth_mutex(table, i));
}

/************************************************************//**
Gets the nth rw_lock in a hash table.
@return rw_lock */
UNIV_INLINE
rw_lock_t*
hash_get_nth_lock(
/*==============*/
	hash_table_t*	table,	/*!< in: hash table */
	ulint		i)	/*!< in: index of the rw_lock */
{
	ut_ad(table);
	ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
	ut_ad(table->type == HASH_TABLE_SYNC_RW_LOCK);
	ut_ad(i < table->n_sync_obj);

	return(table->sync_obj.rw_locks + i);
}

/************************************************************//**
Gets the rw_lock for a fold value in a hash table.
@return rw_lock */
UNIV_INLINE
rw_lock_t*
hash_get_lock(
/*==========*/
	hash_table_t*	table,	/*!< in: hash table */
	ulint		fold)	/*!< in: fold */
{
	ulint	i;

	ut_ad(table);
	ut_ad(table->type == HASH_TABLE_SYNC_RW_LOCK);
	ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);

	i = hash_get_sync_obj_index(table, fold);

	return(hash_get_nth_lock(table, i));
}

/** If not appropriate rw_lock for a fold value in a hash table,
relock S-lock the another rw_lock until appropriate for a fold value.
@param[in]	hash_lock	latched rw_lock to be confirmed
@param[in]	table		hash table
@param[in]	fold		fold value
@return	latched rw_lock */
UNIV_INLINE
rw_lock_t*
hash_lock_s_confirm(
	rw_lock_t*	hash_lock,
	hash_table_t*	table,
	ulint		fold)
{
	ut_ad(rw_lock_own(hash_lock, RW_LOCK_S));

	rw_lock_t*	hash_lock_tmp = hash_get_lock(table, fold);

	while (hash_lock_tmp != hash_lock) {
		rw_lock_s_unlock(hash_lock);
		hash_lock = hash_lock_tmp;
		rw_lock_s_lock(hash_lock);
		hash_lock_tmp = hash_get_lock(table, fold);
	}

	return(hash_lock);
}

/** If not appropriate rw_lock for a fold value in a hash table,
relock X-lock the another rw_lock until appropriate for a fold value.
@param[in]	hash_lock	latched rw_lock to be confirmed
@param[in]	table		hash table
@param[in]	fold		fold value
@return	latched rw_lock */
UNIV_INLINE
rw_lock_t*
hash_lock_x_confirm(
	rw_lock_t*	hash_lock,
	hash_table_t*	table,
	ulint		fold)
{
	ut_ad(rw_lock_own(hash_lock, RW_LOCK_X));

	rw_lock_t*	hash_lock_tmp = hash_get_lock(table, fold);

	while (hash_lock_tmp != hash_lock) {
		rw_lock_x_unlock(hash_lock);
		hash_lock = hash_lock_tmp;
		rw_lock_x_lock(hash_lock);
		hash_lock_tmp = hash_get_lock(table, fold);
	}

	return(hash_lock);
}