File memory_hash.c¶
File List > base > memory_hash.c
Go to the documentation of this file
/*
* Copyright 2008 Search Solution Corporation
* Copyright 2016 CUBRID Corporation
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*
*/
/*
* memory_hash.c - memory hash table
*/
#ident "$Id$"
/*
* The structure of the hash table is approximately as follows;
*
* Hash Table header
* -----------------
* |hash_fun |
* |cmp_fun |
* |table_name |
* |Ptr to entries-----> The entries
* |size | -------------------
* |rehash_at | | key, data, next |--> ... -> key, data, next
* |num_entries | | . |
* |num_collisions | | . |
* ----------------- | . |
* -------------------
*/
#include "config.h"
#include <stdio.h>
#include <assert.h>
#include "memory_hash.h"
#include "chartype.h"
#include "misc_string.h"
#include "error_manager.h"
#include "memory_alloc.h"
#include "message_catalog.h"
#include "environment_variable.h"
#include "set_object.h"
#include "language_support.h"
#include "intl_support.h"
#include "object_primitive.h"
#include "object_representation.h"
#include "dbtype.h"
// XXX: SHOULD BE THE LAST INCLUDE HEADER
#include "memory_wrapper.hpp"
#if __WORDSIZE == 32
#define GET_PTR_FOR_HASH(key) ((unsigned int)(key))
#else
#define GET_PTR_FOR_HASH(key) (((UINT64)(key)) & 0xFFFFFFFFUL)
#endif
/* constants for rehash */
static const float MHT_REHASH_TRESHOLD = 0.7f;
static const float MHT_REHASH_FACTOR = 1.3f;
/* options for mht_put() */
enum mht_put_opt
{
MHT_OPT_DEFAULT = 0,
MHT_OPT_KEEP_KEY = 1,
MHT_OPT_INSERT_ONLY = 2,
MHT_OPT_INSERT_IF_NOT_EXISTS = 4
};
typedef enum mht_put_opt MHT_PUT_OPT;
/*
* A table of prime numbers.
*
* Some prime numbers which were picked randomly.
* This table contains more smaller prime numbers.
* Some of the prime numbers included are:
* between 1000 and 2000, prime numbers that are farther than 50 units.
* between 2000 and 7000, prime numbers that are farther than 100 units.
* between 7000 and 12000, prime numbers that are farther than 200 units.
* between 12000 and 17000, prime numbers that are farther than 400 units.
* between 17000 and 22000, prime numbers that are farther than 800 units.
* above 22000, prime numbers that are farther than 1000 units.
*
* Note: if x is a prime number, the n is prime if X**(n-1) mod n == 1
*/
static unsigned int mht_1str_pseudo_key (const void *key, int key_size);
static unsigned int mht_3str_pseudo_key (const void *key, int key_size, const unsigned int max_value);
static unsigned int mht_4str_pseudo_key (const void *key, int key_size);
static unsigned int mht_5str_pseudo_key (const void *key, int key_size);
static int mht_rehash (MHT_TABLE * ht);
static const void *mht_put_internal (MHT_TABLE * ht, const void *key, void *data, MHT_PUT_OPT opt);
static const void *mht_put2_internal (MHT_TABLE * ht, const void *key, void *data, MHT_PUT_OPT opt);
static const void *mht_put_hls_internal (MHT_HLS_TABLE * ht, const void *key, void *data, MHT_PUT_OPT opt);
static unsigned int mht_get_shiftmult32 (unsigned int key, const unsigned int ht_size);
#if defined (ENABLE_UNUSED_FUNCTION)
static unsigned int mht_get32_next_power_of_2 (unsigned int const ht_size);
static unsigned int mht_get_linear_hash32 (const unsigned int key, const unsigned int ht_size);
#endif /* ENABLE_UNUSED_FUNCTION */
/*
* Several hasing functions for different data types
*/
/*
* mht_1str_pseudo_key() - hash string key into pseudo integer key
* return: pseudo integer key
* key(in): string key to hash
* key_size(in): size of key or -1 when unknown
*
* Note: It generates a pseudo integer key based on Gosling's emacs hash
* function.
*/
static unsigned int
mht_1str_pseudo_key (const void *key, int key_size)
{
unsigned const char *byte_p = (unsigned char *) key;
unsigned int pseudo_key;
assert (key != NULL);
for (pseudo_key = 0;; byte_p++)
{
if (key_size == -1)
{
if (!(*byte_p))
{
break;
}
}
else
{
if (key_size <= 0)
{
break;
}
}
pseudo_key = (pseudo_key << 5) - pseudo_key + *byte_p;
if (key_size > 0)
{
key_size--;
}
}
return pseudo_key;
}
/*
* mht_2str_pseudo_key() - hash string key into pseudo integer key
* return: pseudo integer key
* key(in): string key to hash
* key_size(in): size of key or -1 when unknown
*
* Note: It generates a pseudo integer key based on hash function from
* Aho, Sethi, and Ullman's dragon book; pp. 436.
* This function can handles strings when they are binary different.
* For collation dependent function use 'mht2str'.
*/
unsigned int
mht_2str_pseudo_key (const void *key, int key_size)
{
unsigned const char *byte_p = (unsigned char *) key;
unsigned int pseudo_key;
unsigned int i;
assert (key != NULL);
for (pseudo_key = 0;; byte_p++)
{
if (key_size == -1)
{
if (!(*byte_p))
{
break;
}
}
else
{
if (key_size <= 0)
{
break;
}
}
pseudo_key = (pseudo_key << 4) + *byte_p;
i = pseudo_key & 0xf0000000;
if (i != 0)
{
pseudo_key ^= i >> 24;
pseudo_key ^= i;
}
if (key_size > 0)
{
key_size--;
}
}
return pseudo_key;
}
/*
* mht_3str_pseudo_key() - hash string key into pseudo integer key
* return: pseudo integer key
* key(in): string key to hash
* key_size(in): size of key or -1 when unknown
* max_value(in) : generally a prime number which represents the size of hash
* table
*
* Note: It generates a pseudo integer key based on hash function from
* Sedgewick's Algorithm book. The function needs a prime number for
* the range. This prime number is usually the hash table size.
*/
static unsigned int
mht_3str_pseudo_key (const void *key, int key_size, const unsigned int max_value)
{
unsigned const char *byte_p = (unsigned char *) key;
unsigned int pseudo_key = 0;
assert (key != NULL);
for (pseudo_key = 0;; byte_p++)
{
if (key_size == -1)
{
if (!(*byte_p))
{
break;
}
}
else
{
if (key_size <= 0)
{
break;
}
}
pseudo_key = (pseudo_key * 32 + *byte_p++) % max_value;
if (key_size > 0)
{
key_size--;
}
}
return pseudo_key;
}
/*
* mht_4str_pseudo_key() - hash string key into pseudo integer key
* return: pseudo integer key
* key(in): string key to hash
* key_size(in): size of key or -1 when unknown
*
* Note: It generates four values between 0 and 255, concatenate them,
* and returns the result.
* Based on Fast Hashing of Variable-Length Text Strings
* by Peter K. Pearson Communications of the ACM, June 1990.
*/
static unsigned int
mht_4str_pseudo_key (const void *key, int key_size)
{
/* a permutation of values 0 to 255 */
unsigned char tbl[] = {
166, 231, 148, 061, 050, 131, 000, 057, 126, 223,
044, 245, 138, 251, 24, 113, 86, 215, 196, 173,
226, 115, 48, 169, 46, 207, 92, 101, 58, 235,
72, 225, 6, 199, 244, 29, 146, 99, 96, 25,
222, 191, 140, 213, 234, 219, 120, 81, 182, 183,
36, 141, 66, 83, 144, 137, 142, 175, 188, 69,
154, 203, 168, 193, 102, 167, 84, 253, 242, 67,
192, 249, 62, 159, 236, 181, 74, 187, 216, 49,
22, 151, 132, 109, 162, 51, 240, 105, 238, 143,
28, 37, 250, 171, 8, 161, 198, 135, 180, 221,
82, 35, 32, 217, 158, 127, 76, 149, 170, 155,
56, 17, 118, 119, 228, 77, 2, 19, 80, 73, 78,
111, 124, 5, 90, 139, 104, 129, 38, 103, 20,
189, 178, 3, 128, 185, 254, 95, 172, 117, 10,
123, 152, 241, 214, 87, 68, 45, 98, 243, 176,
41, 174, 79, 220, 229, 186, 107, 200, 97, 134,
71, 116, 157, 18, 227, 224, 153, 94, 63, 12,
85, 106, 91, 248, 209, 54, 55, 164, 13, 194,
211, 16, 9, 14, 47, 60, 197, 26, 75, 40,
65, 230, 39, 212, 125, 114, 195, 64, 121, 190,
31, 108, 53, 202, 59, 88, 177, 150, 23, 4,
237, 34, 179, 112, 233, 110, 15, 156, 165, 122,
43, 136, 33, 70, 7, 52, 93, 210, 163, 160,
89, 30, 255, 204, 21, 42, 27, 184, 145, 246,
247, 100, 205, 130, 147, 208, 201, 206, 239, 252,
133, 218, 11, 232, 1, 0
};
unsigned int byte1, byte2, byte3, byte4;
unsigned const char *byte_p = (unsigned char *) key;
assert (key != NULL);
byte1 = tbl[*byte_p];
byte2 = tbl[(unsigned int) (*byte_p + 1) % 256];
byte3 = tbl[(unsigned int) (*byte_p + 2) % 256];
byte4 = tbl[(unsigned int) (*byte_p + 3) % 256];
if (key_size == -1)
{
if (*byte_p)
{
byte_p++;
}
}
else if (key_size > 0)
{
byte_p++;
key_size--;
}
for (;; byte_p++)
{
if (key_size == -1)
{
if (!(*byte_p))
{
break;
}
}
else
{
if (key_size <= 0)
{
break;
}
}
/*
* Each of the following hash values,
* generates a value between 0 and 255
*/
byte1 = tbl[byte1 ^ *byte_p];
byte2 = tbl[byte2 ^ *byte_p];
byte3 = tbl[byte3 ^ *byte_p];
byte4 = tbl[byte4 ^ *byte_p];
if (key_size > 0)
{
key_size--;
}
}
/* Concatenate all the values */
return (byte1 | (byte2 << 8) | (byte3 << 16) | (byte4 << 24));
}
/*
* mht_5str_pseudo_key() - hash string key into pseudo integer key
* return: pseudo integer key
* key(in): string key to hash
* key_size(in): size of key or -1 when unknown
*
* Note: Based on hash method reported by Diniel J. Bernstein.
*/
static unsigned int
mht_5str_pseudo_key (const void *key, int key_size)
{
unsigned int hash = 5381;
int i = 0;
char *k;
assert (key != NULL);
k = (char *) key;
if (key_size == -1)
{
int c;
while ((c = *(k + i++)) != 0)
{
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
}
}
else
{
for (; i < key_size; i++)
{
hash = ((hash << 5) + hash) + *(k + i);
}
}
hash += ~(hash << 9);
hash ^= ((hash >> 14) | (i << 18)); /* >>> */
hash += (hash << 4);
hash ^= ((hash >> 10) | (i << 22)); /* >>> */
return hash;
}
/*
* mht_1strlowerhash - hash a string key (in lowercase)
* return: hash value
* key(in): key to hash
* ht_size(in): size of hash table
*
* Note: Taken from Gosling's emacs
* This handles only ASCII characters; for charset-independent version
* use 'intl_identifier_mht_1strlowerhash'
*/
unsigned int
mht_1strlowerhash (const void *key, const unsigned int ht_size)
{
unsigned int hash;
unsigned const char *byte_p = (unsigned char *) key;
unsigned int ch;
assert (key != NULL);
for (hash = 0; *byte_p; byte_p++)
{
/* TODO: Original comment originally this way but due to compiler problems on the PC, it doesn't always work
* consistently: hash = (hash << 5) - hash + tolower(*key++); */
ch = char_tolower (*byte_p);
hash = (hash << 5) - hash + ch;
}
return hash % ht_size;
}
/*
* mht_1strhash - hash a string key
* return: hash value
* key(in): key to hash
* ht_size(in): size of hash table
*
* Note: Taken from Gosling's emacs
*/
unsigned int
mht_1strhash (const void *key, const unsigned int ht_size)
{
assert (key != NULL);
return mht_1str_pseudo_key (key, -1) % ht_size;
}
/*
* mht_2strhash - hash a string key
* return: hash value
* key(in): key to hash
* ht_size(in): size of hash table
*
* Note: Form to hash strings.
* Taken from Aho, Sethi, and Ullman's dragon book; pp. 436.
* This function uses 'mht_2str_pseudo_key'.
* For collation dependent function use 'mht2str'.
*/
unsigned int
mht_2strhash (const void *key, const unsigned int ht_size)
{
assert (key != NULL);
return mht_2str_pseudo_key (key, -1) % ht_size;
}
/*
* mht_3strhash - hash a string key
* return: hash value
* key(in): key to hash
* ht_size(in): size of hash table
*
* Note: Form to hash strings.
* Taken from Sedgewick's Algorithm book
*/
unsigned int
mht_3strhash (const void *key, const unsigned int ht_size)
{
assert (key != NULL);
return mht_3str_pseudo_key (key, -1, ht_size);
}
/*
* mht_4strhash - hash a string key
* return: hash value
* key(in): key to hash
* ht_size(in): size of hash table
*
* Note: Form to hash strings.
* It generates four values between 0 and 255, concatenate them
* and applies the mod.
*
* Based on Fast Hashing of Variable-Length Text Strings
* by Peter K. Pearson
* Communications of the ACM, June 1990.
*/
unsigned int
mht_4strhash (const void *key, const unsigned int ht_size)
{
assert (key != NULL);
return mht_4str_pseudo_key (key, -1) % ht_size;
}
/*
* mht_5strhash - hash a string key
* return: hash value
* key(in): key to hash
* ht_size(in): size of hash table
*
* Note: Based on hash method reported by Diniel J. Bernstein.
*/
unsigned int
mht_5strhash (const void *key, const unsigned int ht_size)
{
return mht_5str_pseudo_key (key, -1) % ht_size;
}
/*
* mht_numash - hash an integer key
* return: hash value
* key(in): void pointer to integer key to hash
* ht_size(in): size of hash table
*/
unsigned int
mht_numhash (const void *key, const unsigned int ht_size)
{
assert (key != NULL);
return (*(const unsigned int *) key) % ht_size;
}
/*
* mht_ptrhash - hash a pointer key (hash memory pointers)
* return: hash value
* key(in): pointer value key to hash
* ht_size(in): size of hash table
*/
unsigned int
mht_ptrhash (const void *key, const unsigned int ht_size)
{
assert (key != NULL);
return GET_PTR_FOR_HASH (key) % ht_size;
}
/*
* mht_valhash - hash a DB_VALUE key
* return: hash value
* key(in): pointer to DB_VALUE key to hash
* ht_size(in): size of hash table
*/
unsigned int
mht_valhash (const void *key, const unsigned int ht_size)
{
unsigned int hash = 0;
const DB_VALUE *val = (const DB_VALUE *) key;
int t_n;
DB_VALUE t_val;
if (key != NULL)
{
switch (db_value_type (val))
{
case DB_TYPE_NULL:
hash = 0;
break;
case DB_TYPE_INTEGER:
hash = (unsigned int) db_get_int (val);
break;
case DB_TYPE_SHORT:
hash = (unsigned int) db_get_short (val);
break;
case DB_TYPE_BIGINT:
{
DB_BIGINT bigint;
unsigned int x, y;
bigint = db_get_bigint (val);
x = bigint >> 32;
y = (unsigned int) bigint;
hash = x ^ y;
break;
}
case DB_TYPE_FLOAT:
hash = (unsigned int) db_get_float (val);
break;
case DB_TYPE_DOUBLE:
hash = (unsigned int) db_get_double (val);
break;
case DB_TYPE_NUMERIC:
hash = mht_1str_pseudo_key (db_get_numeric (val), -1);
break;
case DB_TYPE_CHAR:
case DB_TYPE_VARCHAR:
hash = mht_1str_pseudo_key (db_get_string (val), db_get_string_size (val));
break;
case DB_TYPE_BIT:
case DB_TYPE_VARBIT:
hash = mht_1str_pseudo_key (db_get_bit (val, &t_n), -1);
break;
case DB_TYPE_TIME:
{
unsigned int *time = db_get_time (val);
hash = (unsigned int) (*time);
break;
}
case DB_TYPE_TIMESTAMP:
case DB_TYPE_TIMESTAMPLTZ:
{
DB_TIMESTAMP *time_st = db_get_timestamp (val);
hash = (unsigned int) (*time_st);
break;
}
case DB_TYPE_TIMESTAMPTZ:
{
DB_TIMESTAMPTZ *ts_tz = db_get_timestamptz (val);
hash = (unsigned int) (ts_tz->timestamp);
}
break;
case DB_TYPE_DATETIME:
case DB_TYPE_DATETIMELTZ:
{
DB_DATETIME *datetime;
datetime = db_get_datetime (val);
hash = (unsigned int) (datetime->date ^ datetime->time);
}
break;
case DB_TYPE_DATETIMETZ:
{
DB_DATETIMETZ *dt_tz;
dt_tz = db_get_datetimetz (val);
hash = (unsigned int) (dt_tz->datetime.date ^ dt_tz->datetime.time);
}
break;
case DB_TYPE_DATE:
{
DB_DATE *date = db_get_date (val);
hash = (unsigned int) (*date);
break;
}
case DB_TYPE_MONETARY:
{
DB_MONETARY *mon = db_get_monetary (val);
hash = (unsigned int) mon->amount;
break;
}
case DB_TYPE_SET:
case DB_TYPE_MULTISET:
case DB_TYPE_SEQUENCE:
db_make_null (&t_val);
{
DB_SET *set;
set = db_get_set (val);
if (set_get_element (set, 0, &t_val) == NO_ERROR)
{
hash = mht_valhash (&t_val, ht_size);
(void) pr_clear_value (&t_val);
t_n = set_size (set);
if ((t_n > 0) && set_get_element (set, t_n - 1, &t_val) == NO_ERROR)
{
hash += mht_valhash (&t_val, ht_size);
(void) pr_clear_value (&t_val);
}
}
}
break;
case DB_TYPE_OBJECT:
hash = GET_PTR_FOR_HASH (db_get_object (val));
break;
case DB_TYPE_OID:
hash = (unsigned int) OID_PSEUDO_KEY (db_get_oid (val));
break;
case DB_TYPE_MIDXKEY:
db_make_null (&t_val);
{
DB_MIDXKEY *midxkey;
midxkey = db_get_midxkey (val);
if (pr_midxkey_get_element_nocopy (midxkey, 0, &t_val, NULL, NULL) == NO_ERROR)
{
hash = mht_valhash (&t_val, ht_size);
t_n = midxkey->size;
if (t_n > 0 && pr_midxkey_get_element_nocopy (midxkey, t_n - 1, &t_val, NULL, NULL) == NO_ERROR)
{
hash += mht_valhash (&t_val, ht_size);
}
}
}
break;
case DB_TYPE_POINTER:
hash = GET_PTR_FOR_HASH (db_get_pointer (val));
break;
case DB_TYPE_BLOB:
case DB_TYPE_CLOB:
case DB_TYPE_SUB:
case DB_TYPE_ERROR:
case DB_TYPE_VOBJ:
case DB_TYPE_DB_VALUE:
case DB_TYPE_RESULTSET:
case DB_TYPE_TABLE:
default:
hash = GET_PTR_FOR_HASH (val);
break;
}
}
return hash % ht_size;
}
/*
* Compare functions for datatypes
*/
/*
* mht_compare_ints_are_equal - compare two integer keys
* return: 0 or 1 (key1 == key2)
* key1(in): pointer to integer key1
* key2(in): pointer to integer key2
*/
int
mht_compare_ints_are_equal (const void *key1, const void *key2)
{
return ((*(const int *) key1 == *(const int *) key2));
}
/*
* mht_logpageid_compare_equal - compare two LOG_PAGEID keys
* return: 0 or 1 (key1 == key2)
* key1(in): pointer to LOG_PAGEID key1
* key2(in): pointer to LOG_PAGEID key2
*/
int
mht_compare_logpageids_are_equal (const void *key1, const void *key2)
{
return ((*(const LOG_PAGEID *) key1 == *(const LOG_PAGEID *) key2));
}
/*
* mht_compare_identifiers_equal - compare two identifiers keys (ignoring case)
* return: 0 or 1 (key1 == key2)
* key1(in): pointer to string key1
* key2(in): pointer to string key2
*/
int
mht_compare_identifiers_equal (const void *key1, const void *key2)
{
return ((intl_identifier_casecmp ((const char *) key1, (const char *) key2)) == 0);
}
/*
* mht_compare_strings_are_equal - compare two string keys (case sensitive)
* return: 0 or 1 (key1 == key2)
* key1(in): pointer to string key1
* key2(in): pointer to string key2
*/
int
mht_compare_strings_are_equal (const void *key1, const void *key2)
{
return ((strcmp ((const char *) key1, (const char *) key2)) == 0);
}
/*
* mht_compare_ptrs_are_equal - compare two pointer keys
* return: 0 or 1 (key1 == key2)
* key1(in): pointer key1
* key2(in): pointer key2
*/
int
mht_compare_ptrs_are_equal (const void *key1, const void *key2)
{
return (key1 == key2);
}
/*
* mht_compare_dbvalues_are_equal - compare two DB_VALUEs
* return: 0 or 1 (key1 == key2)
* key1(in): pointer to DB_VALUE key1
* key2(in): pointer to DB_VALUE key2
*/
int
mht_compare_dbvalues_are_equal (const void *key1, const void *key2)
{
return ((key1 == key2) || (tp_value_compare ((DB_VALUE *) key1, (DB_VALUE *) key2, 1, 1) == DB_EQ));
}
/*
* mht_calculate_htsize - find a good hash table size
* return: adjusted hash table size
* ht_size(in): given hash table size
*
* Note: Find a good size for a hash table. A prime number is the best
* size for a hash table, unfortunately prime numbers are
* difficult to found. If the given htsize, falls among the
* prime numbers known by this module, a close prime number to
* the given htsize value is returned, otherwise, a power of two
* is returned.
*/
#define NPRIMES 170
static const unsigned int mht_Primes[NPRIMES] = {
11, 23, 37, 53, 67, 79, 97, 109, 127, 149,
167, 191, 211, 227, 251, 269, 293, 311, 331, 349,
367, 389, 409, 431, 449, 467, 487, 509, 541, 563,
587, 607, 631, 653, 673, 521, 541, 557, 569, 587,
599, 613, 641, 673, 701, 727, 751, 787, 821, 853,
881, 907, 941, 977, 1039, 1087, 1129, 1171, 1213, 1259,
1301, 1361, 1409, 1471, 1523, 1579, 1637, 1693, 1747, 1777,
1823, 1867, 1913, 1973, 2017, 2129, 2237, 2339, 2441, 2543,
2647, 2749, 2851, 2953, 3061, 3163, 3271, 3373, 3491, 3593,
3697, 3803, 3907, 4013, 4177, 4337, 4493, 4649, 4801, 4957,
5059, 5167, 5273, 5381, 5483, 5591, 5693, 5801, 5903, 6007,
6113, 6217, 6317, 6421, 6521, 6637, 6737, 6841, 6847, 7057,
7283, 7487, 7687, 7901, 8101, 8311, 8513, 8713, 8923, 9127,
9337, 9539, 9739, 9941, 10141, 10343, 10559, 10771, 10973, 11177,
11383, 11587, 11789, 12007, 12409, 12809, 13217, 13619, 14029, 14431,
14831, 15233, 15641, 16057, 16477, 16879, 17291, 18097, 18899, 19699,
20507, 21313, 22123, 23131, 24133, 25147, 26153, 27179, 28181, 29123
};
#define NPRIMES_POW2 30
static const unsigned int mht_prime_for_pow2[] = {
5, /* 2^2 = 4 */
11, /* 2^3 = 8 */
17, /* 2^4 = 16 */
37, /* 2^5 = 32 */
67, /* 2^6 = 64 */
131, /* 2^7 = 128 */
263, /* 2^8 = 256 */
521, /* 2^9 = 512 */
1031, /* 2^10 = 1024 */
2053, /* 2^11 = 2048 */
4099, /* 2^12 = 4096 */
8209, /* 2^13 = 8192 */
16411, /* 2^14 = 16384 */
32771, /* 2^15 = 32768 */
65537, /* 2^16 = 65536 */
131101, /* 2^17 = 131072 */
262147, /* 2^18 = 262144 */
524309, /* 2^19 = 524288 */
1048583, /* 2^20 = 1048576 */
2097169, /* 2^21 = 2097152 */
4194319, /* 2^22 = 4194304 */
8388617, /* 2^23 = 8388608 */
16777259, /* 2^24 = 16777216 */
33554467, /* 2^25 = 33554432 */
67108879, /* 2^26 = 67108864 */
134217757, /* 2^27 = 134217728 */
268435459, /* 2^28 = 268435456 */
536870923, /* 2^29 = 536870912 */
1073741833, /* 2^30 = 1073741824 */
2147483659 /* 2^31 = 2147483648 */
};
unsigned int
mht_calculate_htsize (unsigned int ht_size)
{
int left, right, middle; /* indices for binary search */
if (ht_size > mht_Primes[NPRIMES - 1])
{
/* get a power of two */
if (!((ht_size & (ht_size - 1)) == 0))
{
/* Turn off some bits but the left most one */
while (!(ht_size & (ht_size - 1)))
{
ht_size &= (ht_size - 1);
}
ht_size <<= 1;
}
}
else
{
/* we can assign a primary number; binary search */
for (middle = 0, left = 0, right = NPRIMES - 1; left <= right;)
{
middle = CEIL_PTVDIV ((left + right), 2);
if (ht_size == mht_Primes[middle])
{
break;
}
else if (ht_size > mht_Primes[middle])
{
left = middle + 1;
}
else
{
right = middle - 1;
}
}
/* If we didn't find the size, get the larger size and not the small one */
if (ht_size > mht_Primes[middle] && middle < (NPRIMES - 1))
{
middle++;
}
ht_size = mht_Primes[middle];
}
return ht_size;
}
unsigned int
mht_calculate_htsize_for_pow2 (unsigned int ht_size)
{
int i = 0;
assert (ht_size > 0);
/* Too large: fallback to UINT_MAX */
if (ht_size > mht_prime_for_pow2[NPRIMES_POW2 - 1])
{
return UINT_MAX;
}
while (i < NPRIMES_POW2 && (1U << (i + 2)) < ht_size)
{
++i;
}
return mht_prime_for_pow2[i];
}
/*
* mht_create - create a hash table
* return: hash table
* name(in): name of hash table
* est_size(in): estimated number of entries
* hash_func(in): hash function
* cmp_func(in): key compare function
*
* Note: Create a new hash table. The estimated number of entries for
* the hash table may be adjusted (to a prime number) in order to
* obtain certain favorable circumstances when the table is
* created, when the table is almost full and there are at least
* 5% of collisions. 'hash_func' must return an integer between 0 and
* table_size - 1. 'cmp_func' must return TRUE if key1 = key2,
* otherwise, FALSE.
*/
MHT_TABLE *
mht_create (const char *name, int est_size, unsigned int (*hash_func) (const void *key, unsigned int ht_size),
int (*cmp_func) (const void *key1, const void *key2))
{
MHT_TABLE *ht;
HENTRY_PTR *hvector; /* Entries of hash table */
unsigned int ht_estsize;
size_t size;
assert (hash_func != NULL && cmp_func != NULL);
/* Get a good number of entries for hash table */
if (est_size <= 0)
{
est_size = 2;
}
ht_estsize = mht_calculate_htsize ((unsigned int) est_size);
/* Allocate the header information for hash table */
ht = (MHT_TABLE *) malloc (DB_SIZEOF (MHT_TABLE));
if (ht == NULL)
{
er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, DB_SIZEOF (MHT_TABLE));
return NULL;
}
/* Initialize the chunky memory manager */
ht->heap_id = db_create_fixed_heap (DB_SIZEOF (HENTRY), MAX (2, ht_estsize / 2 + 1));
if (ht->heap_id == 0)
{
er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, DB_SIZEOF (HENTRY));
free_and_init (ht);
return NULL;
}
/* Allocate the hash table entry pointers */
size = ht_estsize * DB_SIZEOF (*hvector);
hvector = (HENTRY_PTR *) malloc (size);
if (hvector == NULL)
{
er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, size);
db_destroy_fixed_heap (ht->heap_id);
free_and_init (ht);
return NULL;
}
ht->hash_func = hash_func;
ht->cmp_func = cmp_func;
ht->name = name;
ht->table = hvector;
ht->act_head = NULL;
ht->act_tail = NULL;
ht->lru_head = NULL;
ht->lru_tail = NULL;
ht->prealloc_entries = NULL;
ht->size = ht_estsize;
ht->rehash_at = (unsigned int) (ht_estsize * MHT_REHASH_TRESHOLD);
ht->nentries = 0;
ht->nprealloc_entries = 0;
ht->ncollisions = 0;
ht->build_lru_list = false;
/* Initialize each of the hash entries */
for (; ht_estsize > 0; ht_estsize--)
{
*hvector++ = NULL;
}
return ht;
}
/*
* mht_create_hls - create a hash table
* return: hash table
* name(in): name of hash table
* est_size(in): estimated number of entries
* hash_func(in): hash function
* cmp_func(in): key compare function
*
* Note: Create a new hash table for HASH LIST SCAN.
* The estimated number of entries for the hash table is fixed in HASH LIST SCAN.
* rehashing hash table is not needed becaues of that.
* key comparison is performed in executor.
*/
MHT_HLS_TABLE *
mht_create_hls (const char *name, int est_size, unsigned int (*hash_func) (const void *key, unsigned int ht_size),
int (*cmp_func) (const void *key1, const void *key2))
{
MHT_HLS_TABLE *ht;
HENTRY_HLS_PTR *hvector; /* Entries of hash table */
unsigned int ht_estsize;
size_t size;
/* Get a good number of entries for hash table */
if (est_size <= 0)
{
est_size = 2;
}
ht_estsize = CEIL_PTVDIV (est_size, MHT_REHASH_TRESHOLD);
ht_estsize = mht_calculate_htsize_for_pow2 ((unsigned int) ht_estsize);
/* Allocate the header information for hash table */
ht = (MHT_HLS_TABLE *) malloc (DB_SIZEOF (MHT_HLS_TABLE));
if (ht == NULL)
{
er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, DB_SIZEOF (MHT_HLS_TABLE));
return NULL;
}
/* Initialize the chunky memory manager */
ht->heap_id = db_create_fixed_heap (DB_SIZEOF (HENTRY_HLS), MAX (2, ht_estsize / 2 + 1));
if (ht->heap_id == 0)
{
er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, DB_SIZEOF (HENTRY_HLS));
free_and_init (ht);
return NULL;
}
/* Allocate the hash table entry pointers */
size = ht_estsize * DB_SIZEOF (*hvector);
hvector = (HENTRY_HLS_PTR *) malloc (size);
if (hvector == NULL)
{
er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, size);
db_destroy_fixed_heap (ht->heap_id);
free_and_init (ht);
return NULL;
}
ht->hash_func = hash_func;
ht->cmp_func = cmp_func;
ht->name = name;
ht->table = hvector;
ht->prealloc_entries = NULL;
ht->size = ht_estsize;
ht->nentries = 0;
ht->nprealloc_entries = 0;
ht->ncollisions = 0;
ht->build_lru_list = false;
/* Initialize each of the hash entries */
for (; ht_estsize > 0; ht_estsize--)
{
*hvector++ = NULL;
}
return ht;
}
/*
* mht_rehash - rehash all entires of a hash table
* return: error code
* ht(in/out): hash table to rehash
*
* Note: Expand a hash table. All entries are rehashed onto a larger
* hash table of entries.
*/
static int
mht_rehash (MHT_TABLE * ht)
{
HENTRY_PTR *new_hvector; /* New entries of hash table */
HENTRY_PTR *hvector; /* Entries of hash table */
HENTRY_PTR hentry; /* A hash table entry. linked list */
HENTRY_PTR next_hentry = NULL; /* Next element in linked list */
float rehash_factor;
unsigned int hash;
unsigned int est_size;
size_t size;
unsigned int i;
/* Find an estimated size for hash table entries */
rehash_factor = (float) (1.0 + ((float) ht->ncollisions / (float) ht->nentries));
if (MHT_REHASH_FACTOR > rehash_factor)
{
est_size = (unsigned int) (ht->size * MHT_REHASH_FACTOR);
}
else
{
est_size = (unsigned int) (ht->size * rehash_factor);
}
est_size = mht_calculate_htsize (est_size);
/* Allocate a new vector to keep the estimated hash entries */
size = est_size * DB_SIZEOF (*hvector);
new_hvector = (HENTRY_PTR *) malloc (size);
if (new_hvector == NULL)
{
er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, size);
return ER_OUT_OF_VIRTUAL_MEMORY;
}
/* Initialize all entries */
memset (new_hvector, 0x00, size);
/* Now rehash the current entries onto the vector of hash entries table */
for (ht->ncollisions = 0, hvector = ht->table, i = 0; i < ht->size; hvector++, i++)
{
/* Go over each linked list */
for (hentry = *hvector; hentry != NULL; hentry = next_hentry)
{
next_hentry = hentry->next;
hash = (*ht->hash_func) (hentry->key, est_size);
if (hash >= est_size)
{
hash %= est_size;
}
/* Link the new entry with any previous elements */
hentry->next = new_hvector[hash];
if (hentry->next != NULL)
{
ht->ncollisions++;
}
new_hvector[hash] = hentry;
}
}
/* Now move to new vector of entries */
free_and_init (ht->table);
ht->table = new_hvector;
ht->size = est_size;
ht->rehash_at = (int) (est_size * MHT_REHASH_TRESHOLD);
return NO_ERROR;
}
/*
* mht_destroy - destroy a hash table
* return: void
* ht(in/out): hash table
*
* Note: ht is set as a side effect
*/
void
mht_destroy (MHT_TABLE * ht)
{
assert (ht != NULL);
free_and_init (ht->table);
/* release hash table entry storage */
db_destroy_fixed_heap (ht->heap_id);
free_and_init (ht);
}
/*
* mht_destroy_hls - destroy a hash table
* return: void
* ht(in/out): hash table
*
* Note: ht is set as a side effect
*/
void
mht_destroy_hls (MHT_HLS_TABLE * ht)
{
assert (ht != NULL);
free_and_init (ht->table);
/* release hash table entry storage */
db_destroy_fixed_heap (ht->heap_id);
free_and_init (ht);
}
/*
* mht_clear - remove and free all entries of hash table
* return: error code
* ht(in/out): hash table
* rem_func(in): removal function
* func_args(in): removal function arguments
*/
int
mht_clear (MHT_TABLE * ht, int (*rem_func) (const void *key, void *data, void *args), void *func_args)
{
HENTRY_PTR *hvector; /* Entries of hash table */
HENTRY_PTR hentry; /* A hash table entry. linked list */
HENTRY_PTR next_hentry = NULL; /* Next element in linked list */
unsigned int i, error_code;
assert (ht != NULL);
/*
* Go over the hash table, removing all entries and setting the vector
* entries to NULL.
*/
for (hvector = ht->table, i = 0; i < ht->size; hvector++, i++)
{
/* Go over the linked list for this hash table entry */
for (hentry = *hvector; hentry != NULL; hentry = next_hentry)
{
/* free */
if (rem_func)
{
error_code = (*rem_func) (hentry->key, hentry->data, func_args);
if (error_code != NO_ERROR)
{
return error_code;
}
hentry->key = NULL;
hentry->data = NULL;
}
next_hentry = hentry->next;
/* Save the entries for future insertions */
ht->nprealloc_entries++;
hentry->next = ht->prealloc_entries;
ht->prealloc_entries = hentry;
}
*hvector = NULL;
}
ht->act_head = NULL;
ht->act_tail = NULL;
ht->lru_head = NULL;
ht->lru_tail = NULL;
ht->ncollisions = 0;
ht->nentries = 0;
return NO_ERROR;
}
/*
* mht_hls_clear - remove and free all entries of hash table
* return: error code
* ht(in/out): hash table
* rem_func(in): removal function
* func_args(in): removal function arguments
*/
int
mht_clear_hls (MHT_HLS_TABLE * ht, int (*rem_func) (const void *key, void *data, void *args), void *func_args)
{
HENTRY_HLS_PTR *hvector; /* Entries of hash table */
HENTRY_HLS_PTR hentry; /* A hash table entry. linked list */
HENTRY_HLS_PTR next_hentry = NULL; /* Next element in linked list */
unsigned int i, error_code;
assert (ht != NULL);
/*
* Go over the hash table, removing all entries and setting the vector
* entries to NULL.
*/
for (hvector = ht->table, i = 0; i < ht->size; hvector++, i++)
{
/* Go over the linked list for this hash table entry */
for (hentry = *hvector; hentry != NULL; hentry = next_hentry)
{
/* free */
if (rem_func)
{
error_code = (*rem_func) (NULL, hentry->data, func_args);
if (error_code != NO_ERROR)
{
return error_code;
}
hentry->data = NULL;
}
next_hentry = hentry->next;
/* Save the entries for future insertions */
ht->nprealloc_entries++;
hentry->next = ht->prealloc_entries;
ht->prealloc_entries = hentry;
}
*hvector = NULL;
}
ht->ncollisions = 0;
ht->nentries = 0;
return NO_ERROR;
}
/*
* mht_dump - display all entries of hash table
* return: TRUE/FALSE
* out_fp(in): FILE stream where to dump; if NULL, stdout
* ht(in): hash table to print
* print_id_opt(in): option for printing hash index vector id
* print_func(in): supplied printing function
* func_args(in): arguments to be passed to print_func
*
* Note: Dump the header of hash table, and for each entry in hash table,
* call function "print_func" on three arguments: the key of the entry,
* the data associated with the key, and args, in order to print the entry
* print_id_opt - Print hash index ? Will run faster if we do not need to
* print this information
*/
int
mht_dump (THREAD_ENTRY * thread_p, FILE * out_fp, const MHT_TABLE * ht, const int print_id_opt,
int (*print_func) (THREAD_ENTRY * thread_p, FILE * fp, const void *key, void *data, void *args),
void *func_args)
{
HENTRY_PTR *hvector; /* Entries of hash table */
HENTRY_PTR hentry; /* A hash table entry. linked list */
unsigned int i;
int cont = TRUE;
assert (ht != NULL);
if (out_fp == NULL)
{
out_fp = stdout;
}
fprintf (out_fp,
"HTABLE NAME = %s, SIZE = %d, REHASH_AT = %d,\n" "NENTRIES = %d, NPREALLOC = %d, NCOLLISIONS = %d\n\n",
ht->name, ht->size, ht->rehash_at, ht->nentries, ht->nprealloc_entries, ht->ncollisions);
if (print_id_opt == -1)
{
/* noting to do */
}
else if (print_id_opt)
{
/* Need to print the index vector id. Therefore, scan the whole table */
for (hvector = ht->table, i = 0; i < ht->size; hvector++, i++)
{
if (*hvector != NULL)
{
fprintf (out_fp, "HASH AT %d\n", i);
/* Go over the linked list */
for (hentry = *hvector; cont == TRUE && hentry != NULL; hentry = hentry->next)
{
cont = (*print_func) (thread_p, out_fp, hentry->key, hentry->data, func_args);
}
}
}
}
else
{
/* Quick scan by following only the active entries */
for (hentry = ht->act_head; cont == TRUE && hentry != NULL; hentry = hentry->act_next)
{
cont = (*print_func) (thread_p, out_fp, hentry->key, hentry->data, func_args);
}
}
fprintf (out_fp, "\n");
return (cont);
}
/*
* mht_dump_hls - display all entries of hash table for HASH LIST SCAN
* return: TRUE/FALSE
* out_fp(in): FILE stream where to dump; if NULL, stdout
* ht(in): hash table to print
* print_id_opt(in): option for printing hash index vector id
* print_func(in): supplied printing function
* func_args(in): arguments to be passed to print_func
*
* Note: Dump the header of hash table, and for each entry in hash table,
* call function "print_func" on three arguments: the key of the entry,
* the data associated with the key, and args, in order to print the entry
* print_id_opt - Print hash index ? Will run faster if we do not need to
* print this information
*/
int
mht_dump_hls (THREAD_ENTRY * thread_p, FILE * out_fp, const MHT_HLS_TABLE * ht, const int print_id_opt,
int (*print_func) (THREAD_ENTRY * thread_p, FILE * fp, const void *data, const void *type_list,
void *args), const void *type_list, void *func_args)
{
HENTRY_HLS_PTR *hvector; /* Entries of hash table */
HENTRY_HLS_PTR hentry; /* A hash table entry. linked list */
unsigned int i;
int cont = TRUE;
assert (ht != NULL);
if (out_fp == NULL)
{
out_fp = stdout;
}
fprintf (out_fp,
"\nHTABLE NAME = %s, SIZE = %d," "NENTRIES = %d, NPREALLOC = %d, NCOLLISIONS = %d\n\n",
ht->name, ht->size, ht->nentries, ht->nprealloc_entries, ht->ncollisions);
if (print_id_opt)
{
/* Need to print the index vector id. Therefore, scan the whole table */
for (hvector = ht->table, i = 0; i < ht->size; hvector++, i++)
{
if (*hvector != NULL)
{
fprintf (out_fp, "HASH AT %d\n", i);
/* Go over the linked list */
for (hentry = *hvector; cont == TRUE && hentry != NULL; hentry = hentry->next)
{
fprintf (out_fp, " KEY %10u, ", hentry->key);
cont = (*print_func) (thread_p, out_fp, hentry->data, type_list, func_args);
}
fprintf (out_fp, "\n");
}
}
}
return (cont);
}
/*
* mht_get - find data associated with key
* return: the data associated with the key, or NULL if not found
* ht(in): hash table
* key(in): hashing key
*
* Note: Find the entry in hash table whose key is the value of the given key
*/
void *
mht_get (MHT_TABLE * ht, const void *key)
{
unsigned int hash;
HENTRY_PTR hentry;
assert (ht != NULL);
assert (key != NULL);
/*
* Hash the key and make sure that the return value is between 0 and size
* of hash table
*/
hash = (*ht->hash_func) (key, ht->size);
if (hash >= ht->size)
{
hash %= ht->size;
}
/* now search the linked list */
for (hentry = ht->table[hash]; hentry != NULL; hentry = hentry->next)
{
if (hentry->key == key || (*ht->cmp_func) (hentry->key, key))
{
mht_adjust_lru_list (ht, hentry);
/* return value */
return hentry->data;
}
}
return NULL;
}
/*
* mht_adjust_lru_list -
* ht(in): hash table
* hentry(in): hash entry
*/
int
mht_adjust_lru_list (MHT_TABLE * ht, HENTRY_PTR hentry)
{
assert (ht && hentry);
if (ht && hentry && ht->build_lru_list && ht->lru_tail != hentry)
{
if (ht->lru_head == hentry)
{
ht->lru_head = hentry->lru_next;
}
/* unlink */
hentry->lru_next->lru_prev = hentry->lru_prev;
if (hentry->lru_prev)
{
hentry->lru_prev->lru_next = hentry->lru_next;
}
/* add at end */
ht->lru_tail->lru_next = hentry;
hentry->lru_prev = ht->lru_tail;
hentry->lru_next = NULL;
ht->lru_tail = hentry;
}
return NO_ERROR;
}
/*
* mht_get2 - Find the next data associated with the key; Search the entry next
* to the last result
* return: the data associated with the key, or NULL if not found
* ht(in):
* key(in):
* last(in/out):
*
* NOTE: This call does not affect the LRU list.
*/
void *
mht_get2 (const MHT_TABLE * ht, const void *key, void **last)
{
unsigned int hash;
HENTRY_PTR hentry;
assert (ht != NULL && key != NULL);
/*
* Hash the key and make sure that the return value is between 0 and size
* of hash table
*/
hash = (*ht->hash_func) (key, ht->size);
if (hash >= ht->size)
{
hash %= ht->size;
}
/* now search the linked list */
for (hentry = ht->table[hash]; hentry != NULL; hentry = hentry->next)
{
if (hentry->key == key || (*ht->cmp_func) (hentry->key, key))
{
if (last == NULL)
{
return hentry->data;
}
else if (*((HENTRY_PTR *) last) == NULL)
{
*((HENTRY_PTR *) last) = hentry;
return hentry->data;
}
else if (*((HENTRY_PTR *) last) == hentry)
{
/* found the last result; go forward one more step to get next the above 'if' will be true when the next
* one is found */
*((HENTRY_PTR *) last) = NULL;
}
}
}
return NULL;
}
/*
* mht_get_hls - Find the data associated with the key;
* return: the data associated with the key, or NULL if not found
* ht(in):
* key(in):
* last(in/out):
*
* NOTE: This call does not affect the LRU list.
*/
void *
mht_get_hls (const MHT_HLS_TABLE * ht, const void *key, void **last)
{
unsigned int hash, hash_idx;
HENTRY_HLS_PTR hentry;
assert (ht != NULL && key != NULL);
/*
* Hash the key and make sure that the return value is between 0 and size of hash table
*/
hash = *((unsigned int *) key);
if (hash >= ht->size)
{
hash_idx = hash % ht->size;
}
else
{
hash_idx = hash;
}
/* In HASH LIST SCAN, only hash key comparison is performed. */
for (hentry = ht->table[hash_idx]; hentry != NULL; hentry = hentry->next)
{
if (hentry->key == hash)
{
*((HENTRY_HLS_PTR *) last) = hentry;
return hentry->data;
}
}
return NULL;
}
/*
* mht_get_next_hls - Search the entry next to the last result
* return: the data associated with the key, or NULL if not found
* ht(in):
* key(in):
* last(in/out):
*
* NOTE: This call does not affect the LRU list.
*/
void *
mht_get_next_hls (const MHT_HLS_TABLE * ht, const void *key, void **last)
{
unsigned int hash;
HENTRY_HLS_PTR hentry;
assert (ht != NULL && key != NULL && last != NULL);
if ((*(HENTRY_HLS_PTR *) last)->next == NULL)
{
return NULL;
}
/* Hash the key and make sure that the return value is between 0 and size of hash table */
hash = *((unsigned int *) key);
for (hentry = (*(HENTRY_HLS_PTR *) last)->next; hentry != NULL; hentry = hentry->next)
{
if (hentry->key == hash)
{
*((HENTRY_HLS_PTR *) last) = hentry;
return hentry->data;
}
}
return NULL;
}
/*
* mht_put_internal - internal function for mht_put(), mht_put_new(), and
* mht_put_data();
* insert an entry associating key with data
* return:
* For option MHT_OPT_DEFAULT, MHT_OPT_KEEP_KEY, MHT_OPT_INSERT_ONLY,
* returns key if insertion was OK, otherwise, it returns NULL.
* For option MHT_OPT_INSERT_IF_NOT_EXISTS,
* returns existing data if duplicated key was found, or return
* inserted data if insertion was OK, otherwise, it returns NULL.
* ht(in/out): hash table (set as a side effect)
* key(in): hashing key
* data(in): data associated with hashing key
* opt(in): options;
* MHT_OPT_DEFAULT - change data and the key as given of the hash
* entry; replace the old entry with the new one
* if there is an entry with the same key
* MHT_OPT_KEEP_KEY - change data but the key of the hash entry
* MHT_OPT_INSERT_ONLY - do not replace the existing hash entry
* even if there is an etnry with the same key
* MHT_OPT_INSERT_IF_NOT_EXISTS - only insert if the key not exists,
* do nothing if the same key exists.
*/
static const void *
mht_put_internal (MHT_TABLE * ht, const void *key, void *data, MHT_PUT_OPT opt)
{
unsigned int hash;
HENTRY_PTR hentry;
assert (ht != NULL && key != NULL);
/*
* Hash the key and make sure that the return value is between 0 and size
* of hash table
*/
hash = (*ht->hash_func) (key, ht->size);
if (hash >= ht->size)
{
hash %= ht->size;
}
if (!(opt & MHT_OPT_INSERT_ONLY))
{
/* Now search the linked list.. Is there any entry with the given key ? */
for (hentry = ht->table[hash]; hentry != NULL; hentry = hentry->next)
{
if (hentry->key == key || (*ht->cmp_func) (hentry->key, key))
{
if (opt & MHT_OPT_INSERT_IF_NOT_EXISTS)
{
/* Return data for this option */
return hentry->data;
}
/* Replace the old data with the new one */
if (!(opt & MHT_OPT_KEEP_KEY))
{
hentry->key = key;
}
hentry->data = data;
return key;
}
}
}
/* This is a new entry */
if (ht->nprealloc_entries > 0)
{
ht->nprealloc_entries--;
hentry = ht->prealloc_entries;
ht->prealloc_entries = ht->prealloc_entries->next;
}
else
{
hentry = (HENTRY_PTR) db_fixed_alloc (ht->heap_id, DB_SIZEOF (HENTRY));
if (hentry == NULL)
{
return NULL;
}
}
if (ht->build_lru_list)
{
/* link new entry to LRU list */
hentry->lru_next = NULL;
hentry->lru_prev = ht->lru_tail;
if (ht->lru_tail)
{
ht->lru_tail->lru_next = hentry;
}
ht->lru_tail = hentry;
if (ht->lru_head == NULL)
{
ht->lru_head = hentry;
}
}
/*
* Link the new entry to the double link list of active entries and the
* hash itself. The previous entry should point to new one.
*/
hentry->key = key;
hentry->data = data;
hentry->act_next = NULL;
hentry->act_prev = ht->act_tail;
/* Double link tail entry should point to newly created entry */
if (ht->act_tail != NULL)
{
ht->act_tail->act_next = hentry;
}
ht->act_tail = hentry;
if (ht->act_head == NULL)
{
ht->act_head = hentry;
}
hentry->next = ht->table[hash];
if (hentry->next != NULL)
{
ht->ncollisions++;
}
ht->table[hash] = hentry;
ht->nentries++;
/*
* Rehash if almost all entries of hash table are used and there are at least
* 5% of collisions
*/
if (ht->nentries > ht->rehash_at && ht->ncollisions > (ht->nentries * 0.05))
{
if (mht_rehash (ht) < 0)
{
return NULL;
}
}
return (opt & MHT_OPT_INSERT_IF_NOT_EXISTS) ? data : key;
}
const void *
mht_put_new (MHT_TABLE * ht, const void *key, void *data)
{
assert (ht != NULL && key != NULL);
return mht_put_internal (ht, key, data, MHT_OPT_INSERT_ONLY);
}
const void *
mht_put_hls (MHT_HLS_TABLE * ht, const void *key, void *data)
{
assert (ht != NULL && key != NULL);
return mht_put_hls_internal (ht, key, data, MHT_OPT_INSERT_ONLY);
}
/*
* mht_put_if_not_exists - insert only if the same key not exists.
* return: Return existing data if duplicated key found,
* or return new insertion data if insertion successful,
* otherwise return NULL.
* ht(in/out): hash table
* key(in): hashing key
* data(in): data associated with hashing key
*
* Insert an entry into a hash table only same key not exists.
* Note that this function different with other put functions, do not return key.
*/
const void *
mht_put_if_not_exists (MHT_TABLE * ht, const void *key, void *data)
{
assert (ht != NULL && key != NULL);
return mht_put_internal (ht, key, data, MHT_OPT_INSERT_IF_NOT_EXISTS);
}
const void *
mht_put_data (MHT_TABLE * ht, const void *key, void *data)
{
assert (ht != NULL && key != NULL);
return mht_put_internal (ht, key, data, MHT_OPT_KEEP_KEY);
}
/*
* mht_put - insert an entry associating key with data
* return: Returns key if insertion was OK, otherwise, it returns NULL
* ht(in/out): hash table (set as a side effect)
* key(in): hashing key
* data(in): data associated with hashing key
*
* Note: Insert an entry into a hash table, associating the given key
* with the given data. If the entry is duplicated, that is, if
* the key already exist the new entry replaces the old one.
*
* The key and data are NOT COPIED, only its pointers are copied. The
* user must be aware that changes to the key and value are reflected
* into the hash table
*/
const void *
mht_put (MHT_TABLE * ht, const void *key, void *data)
{
assert (ht != NULL && key != NULL);
return mht_put_internal (ht, key, data, MHT_OPT_DEFAULT);
}
/*
* mht_put2_internal - internal function for mht_put2(), mht_put_new2(), and
* mht_put_data2();
* Insert an entry associating key with data;
* Allow mutiple entries with the same key value
* return: Returns key if insertion was OK, otherwise, it returns NULL
* ht(in/out): hash table (set as a side effect)
* key(in): hashing key
* data(in): data associated with hashing key
* opt(in): options;
* MHT_OPT_DEFAULT - change data and the key as given of the hash
* entry; replace the old entry with the new one
* if there is an entry with the same key
* MHT_OPT_KEEP_KEY - change data but the key of the hash entry
* MHT_OPT_INSERT_ONLY - do not replace the existing hash entry
* even if there is an etnry with the same key
*/
static const void *
mht_put2_internal (MHT_TABLE * ht, const void *key, void *data, MHT_PUT_OPT opt)
{
unsigned int hash;
HENTRY_PTR hentry;
assert (ht != NULL && key != NULL);
/*
* Hash the key and make sure that the return value is between 0 and size
* of hash table
*/
hash = (*ht->hash_func) (key, ht->size);
if (hash >= ht->size)
{
hash %= ht->size;
}
if (!(opt & MHT_OPT_INSERT_ONLY))
{
/* now search the linked list */
for (hentry = ht->table[hash]; hentry != NULL; hentry = hentry->next)
{
if ((hentry->key == key || (*ht->cmp_func) (hentry->key, key)) && hentry->data == data)
{
/* We found the existing entry. Replace the old data with the new one. */
if (!(opt & MHT_OPT_KEEP_KEY))
{
hentry->key = key;
}
hentry->data = data;
return key;
}
}
}
/* get new entry */
if (ht->nprealloc_entries > 0)
{
ht->nprealloc_entries--;
hentry = ht->prealloc_entries;
ht->prealloc_entries = ht->prealloc_entries->next;
}
else
{
hentry = (HENTRY_PTR) db_fixed_alloc (ht->heap_id, DB_SIZEOF (HENTRY));
if (hentry == NULL)
{
return NULL;
}
}
if (ht->build_lru_list)
{
/* link new entry to LRU list */
hentry->lru_next = NULL;
hentry->lru_prev = ht->lru_tail;
if (ht->lru_tail)
{
ht->lru_tail->lru_next = hentry;
}
ht->lru_tail = hentry;
if (ht->lru_head == NULL)
{
ht->lru_head = hentry;
}
}
/* link the new entry to the double link list of active entries */
hentry->key = key;
hentry->data = data;
hentry->act_next = NULL;
hentry->act_prev = ht->act_tail;
if (ht->act_tail != NULL)
{
ht->act_tail->act_next = hentry;
}
ht->act_tail = hentry;
if (ht->act_head == NULL)
{
ht->act_head = hentry;
}
/* and link to the hash itself */
if ((hentry->next = ht->table[hash]) != NULL)
{
ht->ncollisions++;
}
ht->table[hash] = hentry;
ht->nentries++;
/* rehash if almost all entries of hash table are used and there are at least 5% of collisions */
if (ht->nentries > ht->rehash_at && ht->ncollisions > (ht->nentries * 0.05))
{
mht_rehash (ht);
}
return key;
}
const void *
mht_put2_new (MHT_TABLE * ht, const void *key, void *data)
{
assert (ht != NULL && key != NULL);
return mht_put2_internal (ht, key, data, MHT_OPT_INSERT_ONLY);
}
#if defined (ENABLE_UNUSED_FUNCTION)
const void *
mht_put2_data (MHT_TABLE * ht, const void *key, void *data)
{
assert (ht != NULL && key != NULL);
return mht_put2_internal (ht, key, data, MHT_OPT_KEEP_KEY);
}
/*
* mht_put2 - Insert an entry associating key with data;
* Allow mutiple entries with the same key value
* return: Returns key if insertion was OK, otherwise, it returns NULL
* ht(in/out): hash table (set as a side effect)
* key(in): hashing key
* data(in): data associated with hashing key
*
* Note: Insert an entry into a hash table, associating the given key
* with the given data. If the entry is duplicated, that is, if
* the key already exist the new entry replaces the old one.
*
* The key and data are NOT COPIED, only its pointers are copied. The
* user must be aware that changes to the key and value are reflected
* into the hash table
*/
const void *
mht_put2 (MHT_TABLE * ht, const void *key, void *data)
{
assert (ht != NULL && key != NULL);
return mht_put2_internal (ht, key, data, MHT_OPT_DEFAULT);
}
#endif
/*
* mht_rem - remove a hash entry
* return: error code
* ht(in): hash table (set as a side effect)
* key(in): hashing key
* rem_func(in): supplied function to delete the data and key
* func_args(in): arguments to be passed to rem_func
*
* Note: For each entry in hash table, call function 'rem_func' on three
* arguments: the key of the entry, the data associated with the key,
* and the given args, in order to delete the data and key
*/
int
mht_rem (MHT_TABLE * ht, const void *key, int (*rem_func) (const void *key, void *data, void *args), void *func_args)
{
unsigned int hash;
HENTRY_PTR prev_hentry;
HENTRY_PTR hentry;
int error_code = NO_ERROR;
assert (ht != NULL && key != NULL);
/*
* Hash the key and make sure that the return value is between 0 and size
* of hash table
*/
hash = (*ht->hash_func) (key, ht->size);
if (hash >= ht->size)
{
hash %= ht->size;
}
/* Now search the linked list.. Is there any entry with the given key ? */
for (hentry = ht->table[hash], prev_hentry = NULL; hentry != NULL; prev_hentry = hentry, hentry = hentry->next)
{
if (hentry->key == key || (*ht->cmp_func) (hentry->key, key))
{
/*
* We found the entry
* Call "rem_func" (if any) to delete the data and key
* Delete the node from the double link list of active entries.
* Then delete the node from the hash table.
*/
if (rem_func)
{
error_code = (*rem_func) (hentry->key, hentry->data, func_args);
if (error_code != NO_ERROR)
{
return error_code;
}
}
if (ht->build_lru_list)
{
/* remove from LRU list */
if (ht->lru_head == ht->lru_tail)
{
ht->lru_head = ht->lru_tail = NULL;
}
else if (ht->lru_head == hentry)
{
ht->lru_head = hentry->lru_next;
hentry->lru_next->lru_prev = NULL;
}
else if (ht->lru_tail == hentry)
{
ht->lru_tail = hentry->lru_prev;
hentry->lru_prev->lru_next = NULL;
}
else
{
hentry->lru_prev->lru_next = hentry->lru_next;
hentry->lru_next->lru_prev = hentry->lru_prev;
}
}
/* Remove from double link list of active entries */
if (ht->act_head == ht->act_tail)
{
/* Single active element */
ht->act_head = ht->act_tail = NULL;
}
else if (ht->act_head == hentry)
{
/* Deleting from the head */
ht->act_head = hentry->act_next;
hentry->act_next->act_prev = NULL;
}
else if (ht->act_tail == hentry)
{
/* Deleting from the tail */
ht->act_tail = hentry->act_prev;
hentry->act_prev->act_next = NULL;
}
else
{
/* Deleting from the middle */
hentry->act_prev->act_next = hentry->act_next;
hentry->act_next->act_prev = hentry->act_prev;
}
/* Remove from the hash */
if (prev_hentry != NULL)
{
prev_hentry->next = hentry->next;
ht->ncollisions--;
}
else if ((ht->table[hash] = hentry->next) != NULL)
{
ht->ncollisions--;
}
ht->nentries--;
/* Save the entry for future insertions */
ht->nprealloc_entries++;
hentry->next = ht->prealloc_entries;
ht->prealloc_entries = hentry;
return NO_ERROR;
}
}
return ER_FAILED;
}
/*
* mht_rem2 - Remove an hash entry having the specified data
* return: error code
* ht(in): hash table (set as a side effect)
* key(in): hashing key
* data(in):
* rem_func(in): supplied function to delete the data and key
* func_args(in): arguments to be passed to rem_func
*
* Note: For each entry in hash table, call function 'rem_func' on three
* arguments: the key of the entry, the data associated with the key,
* and the given args, in order to delete the data and key
*/
int
mht_rem2 (MHT_TABLE * ht, const void *key, const void *data, int (*rem_func) (const void *key, void *data, void *args),
void *func_args)
{
unsigned int hash;
HENTRY_PTR prev_hentry;
HENTRY_PTR hentry;
int error_code = NO_ERROR;
assert (ht != NULL && key != NULL);
/* hash the key and make sure that the return value is between 0 and size of hash table */
hash = (*ht->hash_func) (key, ht->size);
if (hash >= ht->size)
{
hash %= ht->size;
}
/* now search the linked list */
for (hentry = ht->table[hash], prev_hentry = NULL; hentry != NULL; prev_hentry = hentry, hentry = hentry->next)
{
if ((hentry->key == key || (*ht->cmp_func) (hentry->key, key)) && hentry->data == data)
{
/*
* We found the entry.
* Call "fun" (if any) to delete the data and key.
* Delete the node from the double link list of active entries.
* Then delete the node from the hash table.
*/
if (rem_func)
{
error_code = (*rem_func) (hentry->key, hentry->data, func_args);
if (error_code != NO_ERROR)
{
return error_code;
}
}
if (ht->build_lru_list)
{
/* remove from LRU list */
if (ht->lru_head == ht->lru_tail)
{
ht->lru_head = ht->lru_tail = NULL;
}
else if (ht->lru_head == hentry)
{
ht->lru_head = hentry->lru_next;
hentry->lru_next->lru_prev = NULL;
}
else if (ht->lru_tail == hentry)
{
ht->lru_tail = hentry->lru_prev;
hentry->lru_prev->lru_next = NULL;
}
else
{
hentry->lru_prev->lru_next = hentry->lru_next;
hentry->lru_next->lru_prev = hentry->lru_prev;
}
}
/* remove from double link list of active entries */
if (ht->act_head == ht->act_tail)
{
ht->act_head = ht->act_tail = NULL;
}
else if (ht->act_head == hentry)
{
ht->act_head = hentry->act_next;
hentry->act_next->act_prev = NULL;
}
else if (ht->act_tail == hentry)
{
ht->act_tail = hentry->act_prev;
hentry->act_prev->act_next = NULL;
}
else
{
hentry->act_prev->act_next = hentry->act_next;
hentry->act_next->act_prev = hentry->act_prev;
}
/* remove from the hash */
if (prev_hentry != NULL)
{
prev_hentry->next = hentry->next;
ht->ncollisions--;
}
else if ((ht->table[hash] = hentry->next) != NULL)
{
ht->ncollisions--;
}
ht->nentries--;
/* save the entry for future insertions */
ht->nprealloc_entries++;
hentry->next = ht->prealloc_entries;
ht->prealloc_entries = hentry;
return NO_ERROR;
}
}
return ER_FAILED;
}
/*
* mht_map - map over hash entries
* return: NO_ERROR or error code - the result of user supplied "map_func"
* ht(in): hash table
* map_func(in): user supplied mapping function
* func_args(in): arguments to be passed to rem_func
*
* Note: For each entry in hash table, call function "map_func" on three
* arguments: the key of the entry, the data associated with the key,
* and the given args. The function that is called should not remove
* (other than the current entry being processed) nor insert entries on
* the given hash table, otherwise, the behavior of the _map is
* unpredictable (e.g., a newly inserted entry may or may not be
* included as part of the map. If "map_func" returns FALSE,
* the mapping is stopped.
*/
int
mht_map (const MHT_TABLE * ht, int (*map_func) (const void *key, void *data, void *args), void *func_args)
{
HENTRY_PTR hentry;
HENTRY_PTR next;
int error_code = NO_ERROR;
assert (ht != NULL);
for (hentry = ht->act_head; hentry != NULL; hentry = next)
{
/* Just in case the hentry is removed using mht_rem save the next entry */
next = hentry->act_next;
error_code = (*map_func) (hentry->key, hentry->data, func_args);
if (error_code != NO_ERROR)
{
break;
}
}
return (error_code);
}
/*
* mht_map_no_key - map over hash entries;
* Same as mht_map, but "map_func" is called on two arguments:
* data and arguments.
* return: NO_ERROR or error code - the result of user supplied "map_func"
* ht(in): hash table
* map_func(in): user supplied mapping function
* func_args(in): arguments to be passed to rem_func
*/
int
mht_map_no_key (THREAD_ENTRY * thread_p, const MHT_TABLE * ht,
int (*map_func) (THREAD_ENTRY * thread_p, void *data, void *args), void *func_args)
{
HENTRY_PTR hentry;
HENTRY_PTR next;
int error_code = NO_ERROR;
assert (ht != NULL);
for (hentry = ht->act_head; hentry != NULL; hentry = next)
{
/* Just in case the hentry is removed using mht_rem save the next entry */
next = hentry->act_next;
error_code = (*map_func) (thread_p, hentry->data, func_args);
if (error_code != NO_ERROR)
{
break;
}
}
return (error_code);
}
/*
* mht_count - number of hash entries
* return: number of entries
* ht(in): hash table
*/
unsigned int
mht_count (const MHT_TABLE * ht)
{
assert (ht != NULL);
return ht->nentries;
}
/*
* mht_get_hash_number - get linear hash number or string hash number
* return: the hash value of the hash key
* ht_size(out): hash size
* val(in): DB_VALUE to hash
*
* Note:
*/
unsigned int
mht_get_hash_number (const unsigned int ht_size, const DB_VALUE * val)
{
unsigned int hashcode = 0;
int i, len;
const char *ptr;
if (!val || DB_IS_NULL (val) || ht_size <= 1)
{
hashcode = 0;
}
else
{
switch (db_value_type (val))
{
case DB_TYPE_INTEGER:
hashcode = mht_get_shiftmult32 (val->data.i, ht_size);
break;
case DB_TYPE_SMALLINT:
hashcode = mht_get_shiftmult32 (val->data.sh, ht_size);
break;
case DB_TYPE_BIGINT:
{
DB_BIGINT bigint;
unsigned int x, y;
bigint = db_get_bigint (val);
x = bigint >> 32;
y = (unsigned int) bigint;
hashcode = mht_get_shiftmult32 (x ^ y, ht_size);
break;
}
break;
case DB_TYPE_FLOAT:
{
unsigned int *x, y;
x = (unsigned int *) &val->data.f;
y = (*x) & 0xFFFFFFF0;
hashcode = mht_get_shiftmult32 (y, ht_size);
}
break;
case DB_TYPE_DOUBLE:
case DB_TYPE_MONETARY:
{
unsigned int *x, y, z;
x = (unsigned int *) &val->data.d;
y = (x[0]) & 0xFFFFFFF0;
z = (x[1]) & 0xFFFFFFF0;
hashcode = mht_get_shiftmult32 (y ^ z, ht_size);
}
break;
case DB_TYPE_NUMERIC:
{
unsigned int *buf = (unsigned int *) val->data.num.d.buf;
hashcode = mht_get_shiftmult32 (buf[0] ^ buf[1] ^ buf[2] ^ buf[3], ht_size);
}
break;
case DB_TYPE_DATE:
hashcode = mht_get_shiftmult32 (val->data.date, ht_size);
break;
case DB_TYPE_TIME:
hashcode = mht_get_shiftmult32 (val->data.time, ht_size);
break;
case DB_TYPE_TIMESTAMP:
case DB_TYPE_TIMESTAMPLTZ:
hashcode = mht_get_shiftmult32 (val->data.utime, ht_size);
break;
case DB_TYPE_TIMESTAMPTZ:
hashcode = mht_get_shiftmult32 (val->data.timestamptz.timestamp, ht_size);
break;
case DB_TYPE_DATETIME:
case DB_TYPE_DATETIMELTZ:
hashcode = mht_get_shiftmult32 (val->data.datetime.date ^ val->data.datetime.time, ht_size);
break;
case DB_TYPE_DATETIMETZ:
hashcode =
mht_get_shiftmult32 (val->data.datetimetz.datetime.date ^ val->data.datetimetz.datetime.time, ht_size);
break;
case DB_TYPE_OID:
{
unsigned int x = (val->data.oid.volid << 16) | (val->data.oid.slotid);
unsigned int y = val->data.oid.pageid;
hashcode = mht_get_shiftmult32 (x ^ y, ht_size);
}
break;
case DB_TYPE_BIT:
case DB_TYPE_VARBIT:
case DB_TYPE_CHAR:
case DB_TYPE_VARCHAR:
ptr = db_get_string (val);
if (ptr)
{
len = db_get_string_size (val);
if (len < 0)
{
len = (int) strlen (ptr);
}
i = len;
for (i--; 0 <= i && ptr[i]; i--)
{
/* only the trailing ASCII space is ignored; the hashing for other characters depend on collation */
if (ptr[i] != 0x20)
{
break;
}
}
i++;
}
if (!ptr || ptr[0] == 0 || i <= 0)
{
hashcode = 0;
}
else
{
hashcode = MHT2STR_COLL (db_get_string_collation (val), (unsigned char *) ptr, i);
hashcode %= ht_size;
}
break;
case DB_TYPE_SET:
case DB_TYPE_MULTISET:
case DB_TYPE_SEQUENCE:
case DB_TYPE_VOBJ:
{
int size = val->data.set->disk_size / 4;
unsigned int x = 0;
int i;
for (i = 0; i < size; i++)
{
x ^= (unsigned int) (val->data.set->disk_set[i * 4]);
}
hashcode = mht_get_shiftmult32 (x, ht_size);
}
break;
case DB_TYPE_BLOB:
case DB_TYPE_CLOB:
{
DB_ELO *elo = db_get_elo (val);
if (elo == NULL && elo->type != ELO_FBO)
{
hashcode = 0;
break;
}
/* Memory addresses are compared in mr_cmpval_elo,
* so no additional processing is needed. */
hashcode = GET_PTR_FOR_HASH (val);
hashcode %= ht_size;
}
break;
case DB_TYPE_ENUMERATION:
hashcode = mht_get_shiftmult32 (val->data.enumeration.short_val, ht_size);
break;
case DB_TYPE_JSON:
{
char *json_body = NULL;
json_body = db_get_json_raw_body (val);
if (json_body == NULL)
{
hashcode = 0;
}
else
{
len = (int) strlen (json_body);
hashcode = MHT2STR_COLL (LANG_COLL_BINARY, (unsigned char *) json_body, len);
hashcode %= ht_size;
db_private_free (NULL, json_body);
}
}
break;
default: /* impossible */
/*
* TODO this is actually possible. See the QA scenario:
* sql/_01_object/_09_partition/_006_prunning/cases/1093.sql
* select * from hash_test where test_int = round(11.57);
* The value has type DB_TYPE_DOUBLE in this case.
*/
er_log_debug (ARG_FILE_LINE, "mht_get_hash_number: ERROR type = %d" " is Unsupported partition column type.",
db_value_type (val));
#if defined(NDEBUG)
hashcode = 0;
#else /* NDEBUG */
/* debugging purpose */
abort ();
#endif /* NDEBUG */
break;
}
}
return hashcode;
}
#if defined (ENABLE_UNUSED_FUNCTION)
/*
* mht_get32_next_power_of_2 -
* return: the next power of 2 greater than ht_size
* ht_size(out): hash size
*
* Note: find first 1's bit of 32bits integer
*/
static unsigned int
mht_get32_next_power_of_2 (const unsigned int ht_size)
{
unsigned int map = 0xffff0000, mapsave;
int mi;
if (ht_size == 0)
{
return 1;
}
if ((map & ht_size) == 0)
{
map ^= 0xffffffff;
}
for (mi = 3; mi >= 0; mi--)
{
mapsave = map;
map = (map << (1 << mi)) & mapsave;
if ((map & ht_size) == 0)
{
map = (map ^ 0xffffffff) & mapsave;
}
}
if (ht_size == map)
{
return map;
}
else
{
return map << 1;
}
}
#endif /* ENABLE_UNUSED_FUNCTION */
/*
* mht_get_shiftmult32 -
* return: new integer hash value
* key(in): hash key value
* ht_size(in): hash size
*
* Note: Robert Jenkin & Thomas Wang algorithm
*/
static unsigned int
mht_get_shiftmult32 (unsigned int key, const unsigned int ht_size)
{
unsigned int c2 = 0x27d4eb2d; /* a prime or an odd constant */
key = (key ^ 61) ^ (key >> 16);
key += (key << 3);
key ^= (key >> 4);
key *= c2;
key ^= (key >> 15);
return (key % ht_size);
}
#if defined (ENABLE_UNUSED_FUNCTION)
/*
* mht_get_linear_hash32 - find the next power of 2 greater than hashsize
* return: linear hash value
* key: hash key value
* ht_size: hash size
*/
static unsigned int
mht_get_linear_hash32 (const unsigned int key, const unsigned int ht_size)
{
unsigned int np, ret;
np = mht_get32_next_power_of_2 (ht_size);
ret = key & (np - 1);
for (ret = key & (np - 1); ret >= ht_size; ret &= (np - 1))
{
if (np % 2)
{
np = np / 2 + 1;
}
else
{
np = np / 2;
}
}
return ret;
}
#endif /* ENABLE_UNUSED_FUNCTION */
/*
* mht_put_hls_internal
* internal function for mht_put_hls()
* put data in the order.
* eliminates unnecessary logic to improve performance for hash list scan.
*
* return: key
* ht(in/out): hash table (set as a side effect)
* key(in): hashing key
* data(in): data associated with hashing key
* opt(in): options;
*/
static const void *
mht_put_hls_internal (MHT_HLS_TABLE * ht, const void *key, void *data, MHT_PUT_OPT opt)
{
unsigned int hash;
HENTRY_HLS_PTR hentry;
assert (ht != NULL && key != NULL);
/* Hash the key and make sure that the return value is between 0 and size of hash table. */
hash = *((unsigned int *) key);
if (hash >= ht->size)
{
hash %= ht->size;
}
/* This is a new entry */
if (ht->nprealloc_entries > 0)
{
ht->nprealloc_entries--;
hentry = ht->prealloc_entries;
ht->prealloc_entries = ht->prealloc_entries->next;
}
else
{
hentry = (HENTRY_HLS_PTR) db_fixed_alloc (ht->heap_id, DB_SIZEOF (HENTRY_HLS));
if (hentry == NULL)
{
return NULL;
}
}
hentry->data = data;
hentry->key = *((unsigned int *) key);
/* To input in order, use the tail node. */
if (ht->table[hash] == NULL)
{
ht->table[hash] = hentry;
}
else
{
ht->table[hash]->tail->next = hentry;
ht->ncollisions++;
}
hentry->next = NULL;
ht->table[hash]->tail = hentry;
ht->nentries++;
return key;
}