hash0hash.ic

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

Copyright (c) 1997, 2025, Oracle and/or its affiliates.

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

This program is designed to work with certain software (including
but not limited to OpenSSL) that is licensed under separate terms,
as designated in a particular file or component or in included license
documentation.  The authors of MySQL hereby grant you an additional
permission to link the program and your derivative works with the
separately licensed software that they have either included with
the program or referenced in the documentation.

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, version 2.0,
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 St, Fifth Floor, Boston, MA 02110-1301  USA

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

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

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

#include "ut0rnd.h"

static inline hash_cell_t *hash_get_nth_cell(hash_table_t *table, size_t n) {
  ut_ad(table);
  ut_ad(table->magic_n == hash_table_t::HASH_TABLE_MAGIC_N);
  ut_ad(n < table->get_n_cells());

  return &table->cells[n];
}

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

static inline size_t hash_get_n_cells(hash_table_t const *table) {
  ut_ad(table);
  ut_ad(table->magic_n == hash_table_t::HASH_TABLE_MAGIC_N);
  return table->get_n_cells();
}

static inline uint64_t hash_calc_cell_id(uint64_t hash_value,
                                         hash_table_t const *table) {
  ut_ad(table);
  ut_ad(table->magic_n == hash_table_t::HASH_TABLE_MAGIC_N);
  return hash_value % table->get_n_cells_fast_modulo();
}

#ifndef UNIV_HOTBACKUP
/** Gets the sync object index for a hash value in a hash table.
 @return index */
static inline uint64_t hash_get_sync_obj_index(
    hash_table_t *table, /*!< in: hash table */
    uint64_t hash_value) /*!< in: hash value */
{
  ut_ad(table);
  ut_ad(table->magic_n == hash_table_t::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_cell_id(hash_value, table),
                           table->n_sync_obj);
}

/** Gets the heap for a hash value in a hash table.
 @return mem heap */
static inline mem_heap_t *hash_get_heap(
    hash_table_t *table) /*!< in: hash table */
{
  ut_ad(table);
  ut_ad(table->magic_n == hash_table_t::HASH_TABLE_MAGIC_N);
  ut_ad(table->n_sync_obj == 0);
  ut_ad(table->type == HASH_TABLE_SYNC_NONE);
  ut_ad(table->heap != nullptr);
  return table->heap;
}

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

  return table->rw_locks + i;
}

/** Gets the rw_lock for a hash value in a hash table.
 @return rw_lock */
static inline rw_lock_t *hash_get_lock(
    hash_table_t *table, /*!< in: hash table */
    uint64_t hash_value) /*!< in: hash value */
{
  ut_ad(table);
  ut_ad(table->type == HASH_TABLE_SYNC_RW_LOCK);
  ut_ad(table->magic_n == hash_table_t::HASH_TABLE_MAGIC_N);

  const auto i = hash_get_sync_obj_index(table, hash_value);

  return hash_get_nth_lock(table, i);
}

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

  rw_lock_t *hash_lock_tmp = hash_get_lock(table, hash_value);

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

  return hash_lock;
}

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

  rw_lock_t *hash_lock_tmp = hash_get_lock(table, hash_value);

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

  return hash_lock;
}
#endif /* !UNIV_HOTBACKUP */

/** Assert that the synchronization object in a hash operation involving
 possible change in the hash table is held.
 We assert that the specific rw_lock is held in exclusive mode.
 @param[in] table   The hash table
 @param[in] hash_value    The hash value for which the modification is performed
 */
static inline void hash_assert_can_modify(hash_table_t *table,
                                          uint64_t hash_value) {
#ifdef UNIV_DEBUG
  if (table->type == HASH_TABLE_SYNC_RW_LOCK) {
#ifndef UNIV_HOTBACKUP
    rw_lock_t *lock = hash_get_lock(table, hash_value);
    ut_ad(rw_lock_own(lock, RW_LOCK_X));
#endif /*!UNIV_HOTBACKUP*/
  } else {
    ut_ad(table->type == HASH_TABLE_SYNC_NONE);
  }
#endif /* UNIV_DEBUG */
}

/** Assert that the synchronization object in a hash search operation is held.
 We assert that the specific rw_lock is held either in x-mode or s-mode.
 @param[in] table   The hash table
 @param[in] hash_value    The hash value for which the search is performed
 */
static inline void hash_assert_can_search(hash_table_t *table,
                                          uint64_t hash_value) {
#ifdef UNIV_DEBUG
  if (table->type == HASH_TABLE_SYNC_RW_LOCK) {
#ifndef UNIV_HOTBACKUP
    rw_lock_t *lock = hash_get_lock(table, hash_value);
    ut_ad(rw_lock_own(lock, RW_LOCK_X) || rw_lock_own(lock, RW_LOCK_S));
#endif /*!UNIV_HOTBACKUP*/
  } else {
    ut_ad(table->type == HASH_TABLE_SYNC_NONE);
  }
#endif
}