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 "dbtype.h"

#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 unsigned int mht_calculate_htsize (unsigned int ht_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_NCHAR:
    case DB_TYPE_VARCHAR:
    case DB_TYPE_VARNCHAR:
      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, 0, 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
};

static 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;
}

/*
 * 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;

  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_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, void *args),
          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,
       "HTABLE NAME = %s, SIZE = %d,\n" "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)
        {
          cont = (*print_func) (thread_p, out_fp, hentry->data, 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 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_get_hls (const MHT_HLS_TABLE * ht, const void *key, void **last)
{
  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 = (*ht->hash_func) (key, ht->size);
  if (hash >= ht->size)
    {
      hash %= ht->size;
    }

  /* In HASH LIST SCAN, key comparison is performed in executor. */
  hentry = ht->table[hash];

  if (hentry != NULL)
    {
      if (last != NULL)
    {
      *((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 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:
    case DB_TYPE_NCHAR:
    case DB_TYPE_VARNCHAR:
      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_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 = (*ht->hash_func) (key, ht->size);
  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;

  /* 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;
}