1 /*****************************************************************************
2
3 Copyright (c) 1994, 2021, Oracle and/or its affiliates.
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License, version 2.0,
7 as published by the Free Software Foundation.
8
9 This program is also distributed with certain software (including
10 but not limited to OpenSSL) that is licensed under separate terms,
11 as designated in a particular file or component or in included license
12 documentation. The authors of MySQL hereby grant you an additional
13 permission to link the program and your derivative works with the
14 separately licensed software that they have included with MySQL.
15
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU General Public License, version 2.0, for more details.
20
21 You should have received a copy of the GNU General Public License along with
22 this program; if not, write to the Free Software Foundation, Inc.,
23 51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
24
25 *****************************************************************************/
26
27 /**************************************************//**
28 @file innodb_list.h
29
30 Created 03/15/2011 Jimmy Yang (most macros and defines are adopted
31 from utility files in the InnoDB. Namely,
32 ut/ut0lst.c, ut0rnd.c and hash0hash.c etc.)
33 *******************************************************/
34
35 #include <stdlib.h>
36 #include <string.h>
37 #include "innodb_utility.h"
38
39 #define UT_HASH_RANDOM_MASK 1463735687
40 #define UT_HASH_RANDOM_MASK2 1653893711
41 #define UT_RANDOM_1 1.0412321
42 #define UT_RANDOM_2 1.1131347
43 #define UT_RANDOM_3 1.0132677
44
45 /*************************************************************//**
46 Folds a pair of ib_ulint_ts.
47 @return folded value */
48 static
49 ib_ulint_t
ut_fold_ib_ulint_t_pair(ib_ulint_t n1,ib_ulint_t n2)50 ut_fold_ib_ulint_t_pair(
51 /*====================*/
52 ib_ulint_t n1, /*!< in: ib_ulint_t */
53 ib_ulint_t n2) /*!< in: ib_ulint_t */
54 {
55 return(((((n1 ^ n2 ^ UT_HASH_RANDOM_MASK2) << 8) + n1)
56 ^ UT_HASH_RANDOM_MASK) + n2);
57 }
58
59 /*************************************************************//**
60 Folds a character string ending in the null character.
61 @return folded value */
62 ib_ulint_t
ut_fold_string(const char * str)63 ut_fold_string(
64 /*===========*/
65 const char* str) /*!< in: null-terminated string */
66 {
67 ib_ulint_t fold = 0;
68
69 while (*str != '\0') {
70 fold = ut_fold_ib_ulint_t_pair(fold, (ib_ulint_t)(*str));
71 str++;
72 }
73
74 return(fold);
75 }
76
77 /***********************************************************//**
78 Looks for a prime number slightly greater than the given argument.
79 The prime is chosen so that it is not near any power of 2.
80 @return prime */
81 static
82 ib_ulint_t
ut_find_prime(ib_ulint_t n)83 ut_find_prime(
84 /*==========*/
85 ib_ulint_t n) /*!< in: positive number > 100 */
86 {
87 ib_ulint_t pow2;
88 ib_ulint_t i;
89
90 n += 100;
91
92 pow2 = 1;
93 while (pow2 * 2 < n) {
94 pow2 = 2 * pow2;
95 }
96
97 if ((double) n < 1.05 * (double) pow2) {
98 n = (ib_ulint_t) ((double) n * UT_RANDOM_1);
99 }
100
101 pow2 = 2 * pow2;
102
103 if ((double) n > 0.95 * (double) pow2) {
104 n = (ib_ulint_t) ((double) n * UT_RANDOM_2);
105 }
106
107 if (n > pow2 - 20) {
108 n += 30;
109 }
110
111 /* Now we have n far enough from powers of 2. To make
112 n more random (especially, if it was not near
113 a power of 2), we then multiply it by a random number. */
114
115 n = (ib_ulint_t) ((double) n * UT_RANDOM_3);
116
117 for (;; n++) {
118 i = 2;
119 while (i * i <= n) {
120 if (n % i == 0) {
121 goto next_n;
122 }
123 i++;
124 }
125
126 /* Found a prime */
127 break;
128 next_n: ;
129 }
130
131 return(n);
132 }
133
134 /*************************************************************//**
135 Creates a hash table with >= n array cells. The actual number of cells is
136 chosen to be a prime number slightly bigger than n.
137 @return own: created table */
138 hash_table_t*
hash_create(ib_ulint_t n)139 hash_create(
140 /*========*/
141 ib_ulint_t n) /*!< in: number of array cells */
142 {
143 hash_cell_t* array;
144 ib_ulint_t prime;
145 hash_table_t* table;
146
147 prime = ut_find_prime(n);
148
149 table = (hash_table_t*) malloc(sizeof(hash_table_t));
150
151 array = (hash_cell_t*) malloc(sizeof(hash_cell_t) * prime);
152
153 /* The default type of hash_table is HASH_TABLE_SYNC_NONE i.e.:
154 the caller is responsible for access control to the table. */
155 table->array = array;
156 table->n_cells = prime;
157
158 /* Initialize the cell array */
159 memset(table->array, 0x0, table->n_cells * sizeof(*table->array));
160
161 return(table);
162 }
163
164 /*******************************************************//**
165 The following function generates a hash value for a ulint integer
166 to a hash table of size table_size, which should be a prime
167 or some random number for the hash table to work reliably.
168 @return hash value */
169 static
170 ib_ulint_t
ut_hash_ulint(ib_ulint_t key,ib_ulint_t table_size)171 ut_hash_ulint(
172 /*==========*/
173 ib_ulint_t key, /*!< in: value to be hashed */
174 ib_ulint_t table_size) /*!< in: hash table size */
175 {
176 key = key ^ UT_HASH_RANDOM_MASK2;
177
178 return(key % table_size);
179 }
180
181 /**************************************************************//**
182 Calculates the hash value from a folded value.
183 @return hashed value */
184 ib_ulint_t
hash_calc_hash(ib_ulint_t fold,hash_table_t * table)185 hash_calc_hash(
186 /*===========*/
187 ib_ulint_t fold, /*!< in: folded value */
188 hash_table_t* table) /*!< in: hash table */
189 {
190 return(ut_hash_ulint(fold, table->n_cells));
191 }
192
193 /************************************************************//**
194 Gets the nth cell in a hash table.
195 @return pointer to cell */
196 inline
197 hash_cell_t*
hash_get_nth_cell(hash_table_t * table,ib_ulint_t n)198 hash_get_nth_cell(
199 /*==============*/
200 hash_table_t* table, /*!< in: hash table */
201 ib_ulint_t n) /*!< in: cell index */
202 {
203 return(table->array + n);
204 }
205
206