/***************************************************************************** Copyright (c) 1997, 2016, Oracle and/or its affiliates. All Rights Reserved. Copyright (c) 2018, 2020, MariaDB Corporation. 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, Fifth Floor, Boston, MA 02110-1335 USA *****************************************************************************/ /**************************************************//** @file include/hash0hash.h The simple hash table utility Created 5/20/1997 Heikki Tuuri *******************************************************/ #pragma once #include "ut0rnd.h" struct hash_table_t; struct hash_cell_t{ void* node; /*!< hash chain node, NULL if none */ }; typedef void* hash_node_t; /*******************************************************************//** Inserts a struct to a hash table. */ #define HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA)\ do {\ hash_cell_t* cell3333;\ TYPE* struct3333;\ \ (DATA)->NAME = NULL;\ \ cell3333 = &(TABLE)->array[(TABLE)->calc_hash(FOLD)]; \ \ if (cell3333->node == NULL) {\ cell3333->node = DATA;\ } else {\ struct3333 = (TYPE*) cell3333->node;\ \ while (struct3333->NAME != NULL) {\ \ struct3333 = (TYPE*) struct3333->NAME;\ }\ \ struct3333->NAME = DATA;\ }\ } while (0) /*******************************************************************//** Inserts a struct to the head of hash table. */ #define HASH_PREPEND(TYPE, NAME, TABLE, FOLD, DATA) \ do { \ hash_cell_t* cell3333; \ TYPE* struct3333; \ \ (DATA)->NAME = NULL; \ \ cell3333 = &(TABLE)->array[(TABLE)->calc_hash(FOLD)]; \ \ if (cell3333->node == NULL) { \ cell3333->node = DATA; \ DATA->NAME = NULL; \ } else { \ struct3333 = (TYPE*) cell3333->node; \ \ DATA->NAME = struct3333; \ \ cell3333->node = DATA; \ } \ } while (0) #ifdef UNIV_HASH_DEBUG # define HASH_ASSERT_VALID(DATA) ut_a((void*) (DATA) != (void*) -1) # define HASH_INVALIDATE(DATA, NAME) *(void**) (&DATA->NAME) = (void*) -1 #else # define HASH_ASSERT_VALID(DATA) do {} while (0) # define HASH_INVALIDATE(DATA, NAME) do {} while (0) #endif /*******************************************************************//** Deletes a struct from a hash table. */ #define HASH_DELETE(TYPE, NAME, TABLE, FOLD, DATA)\ do {\ hash_cell_t* cell3333;\ TYPE* struct3333;\ \ cell3333 = &(TABLE)->array[(TABLE)->calc_hash(FOLD)]; \ \ if (cell3333->node == DATA) {\ HASH_ASSERT_VALID(DATA->NAME);\ cell3333->node = DATA->NAME;\ } else {\ struct3333 = (TYPE*) cell3333->node;\ \ while (struct3333->NAME != DATA) {\ \ struct3333 = (TYPE*) struct3333->NAME;\ ut_a(struct3333);\ }\ \ struct3333->NAME = DATA->NAME;\ }\ HASH_INVALIDATE(DATA, NAME);\ } while (0) #define HASH_REPLACE(TYPE, NAME, TABLE, FOLD, DATA_OLD, DATA_NEW) \ do { \ (DATA_NEW)->NAME = (DATA_OLD)->NAME; \ \ hash_cell_t& cell3333 \ = (TABLE)->array[(TABLE)->calc_hash(FOLD)]; \ TYPE** struct3333 = (TYPE**)&cell3333.node; \ while (*struct3333 != DATA_OLD) { \ struct3333 = &((*struct3333)->NAME); \ } \ *struct3333 = DATA_NEW; \ } while (0) /*******************************************************************//** Gets the first struct in a hash chain, NULL if none. */ #define HASH_GET_FIRST(TABLE, HASH_VAL) (TABLE)->array[HASH_VAL].node /*******************************************************************//** Gets the next struct in a hash chain, NULL if none. */ #define HASH_GET_NEXT(NAME, DATA) ((DATA)->NAME) /********************************************************************//** Looks for a struct in a hash table. */ #define HASH_SEARCH(NAME, TABLE, FOLD, TYPE, DATA, ASSERTION, TEST)\ {\ (DATA) = (TYPE) HASH_GET_FIRST(TABLE, (TABLE)->calc_hash(FOLD)); \ HASH_ASSERT_VALID(DATA);\ \ while ((DATA) != NULL) {\ ASSERTION;\ if (TEST) {\ break;\ } else {\ HASH_ASSERT_VALID(HASH_GET_NEXT(NAME, DATA));\ (DATA) = (TYPE) HASH_GET_NEXT(NAME, DATA);\ }\ }\ } /********************************************************************//** Looks for an item in all hash buckets. */ #define HASH_SEARCH_ALL(NAME, TABLE, TYPE, DATA, ASSERTION, TEST) \ do { \ ulint i3333; \ \ for (i3333 = (TABLE)->n_cells; i3333--; ) { \ (DATA) = (TYPE) HASH_GET_FIRST(TABLE, i3333); \ \ while ((DATA) != NULL) { \ HASH_ASSERT_VALID(DATA); \ ASSERTION; \ \ if (TEST) { \ break; \ } \ \ (DATA) = (TYPE) HASH_GET_NEXT(NAME, DATA); \ } \ \ if ((DATA) != NULL) { \ break; \ } \ } \ } while (0) /****************************************************************//** Move all hash table entries from OLD_TABLE to NEW_TABLE. */ #define HASH_MIGRATE(OLD_TABLE, NEW_TABLE, NODE_TYPE, PTR_NAME, FOLD_FUNC) \ do {\ ulint i2222;\ ulint cell_count2222;\ \ cell_count2222 = (OLD_TABLE)->n_cells; \ \ for (i2222 = 0; i2222 < cell_count2222; i2222++) {\ NODE_TYPE* node2222 = static_cast(\ HASH_GET_FIRST((OLD_TABLE), i2222));\ \ while (node2222) {\ NODE_TYPE* next2222 = static_cast(\ node2222->PTR_NAME);\ ulint fold2222 = FOLD_FUNC(node2222);\ \ HASH_INSERT(NODE_TYPE, PTR_NAME, (NEW_TABLE),\ fold2222, node2222);\ \ node2222 = next2222;\ }\ }\ } while (0) /** Hash table with singly-linked overflow lists */ struct hash_table_t { /** number of elements in array (a prime number) */ ulint n_cells; /** the hash array */ hash_cell_t *array; /** Create the hash table. @param n the lower bound of n_cells */ void create(ulint n) { n_cells= ut_find_prime(n); array= static_cast(ut_zalloc_nokey(n_cells * sizeof *array)); } /** Clear the hash table. */ void clear() { memset(array, 0, n_cells * sizeof *array); } /** Free the hash table. */ void free() { ut_free(array); array= nullptr; } ulint calc_hash(ulint fold) const { return ut_hash_ulint(fold, n_cells); } };