Adding upstream version 1:10.5.12.upstream/1%10.5.12upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 236 insertions, 0 deletions

diff --git a/storage/innobase/include/hash0hash.h b/storage/innobase/include/hash0hash.h
new file mode 100644
index 00000000..981ff5a0
--- /dev/null
+++ b/storage/innobase/include/hash0hash.h
@@ -0,0 +1,236 @@
+/*****************************************************************************
+
+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<NODE_TYPE*>(\
+			HASH_GET_FIRST((OLD_TABLE), i2222));\
+\
+		while (node2222) {\
+			NODE_TYPE*	next2222 = static_cast<NODE_TYPE*>(\
+				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<hash_cell_t*>(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); }
+};