/* * Copyright (C) 2008 Search Solution Corporation. All rights reserved by Search Solution. * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; version 2 of the License. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA * */ /* * 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 #include #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 "intl_support.h" /* this must be the last header file included! */ #include "dbval.h" /* constants for rehash */ static const float MHT_REHASH_TRESHOLD = 0.7; static const float MHT_REHASH_FACTOR = 1.3; /* options for mht_put() */ typedef enum mht_put_opt MHT_PUT_OPT; enum mht_put_opt { MHT_OPT_DEFAULT, MHT_OPT_KEEP_KEY, MHT_OPT_INSERT_ONLY }; /* * 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_2str_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_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 unsigned int mht_get_shiftmult32 (const 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. */ static 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_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 */ 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. */ 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_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 (const unsigned int) 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_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), -1); 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: hash = (unsigned int) *(db_get_time (val)); break; case DB_TYPE_TIMESTAMP: hash = (unsigned int) *(db_get_timestamp (val)); break; case DB_TYPE_DATE: hash = (unsigned int) *(db_get_date (val)); break; case DB_TYPE_MONETARY: hash = (unsigned int) db_get_monetary (val)->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 = (unsigned int) 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 (set_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 && set_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 = (unsigned int) db_get_pointer (val); break; case DB_TYPE_ELO: 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 = (unsigned int) val; break; } } return hash % ht_size; } /* * Compare functions for datatypes */ /* * mht_numcmpeq - compare two integer keys * return: 0 or 1 (key1 == key2) * key1(in): pointer to integer key1 * key2(in): pointer to integer key2 */ int mht_numcmpeq (const void *key1, const void *key2) { if (*(const int *) key1 == *(const int *) key2) { return TRUE; } return FALSE; } /* * mht_strcasecmpeq - compare two string keys (ignoring case) * return: 0 or 1 (key1 == key2) * key1(in): pointer to string key1 * key2(in): pointer to string key2 */ int mht_strcasecmpeq (const void *key1, const void *key2) { if ((intl_mbs_casecmp ((const char *) key1, (const char *) key2)) == 0) { return TRUE; } return FALSE; } /* * mht_strcmpeq - 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_strcmpeq (const void *key1, const void *key2) { if ((strcmp ((const char *) key1, (const char *) key2)) == 0) { return TRUE; } return FALSE; } /* * mht_ptrcmpeq - compare two pointer keys * return: 0 or 1 (key1 == key2) * key1(in): pointer key1 * key2(in): pointer key2 */ int mht_ptrcmpeq (const void *key1, const void *key2) { if (key1 == key2) { return TRUE; } return FALSE; } /* * mht_valcmpeq - 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_valcmpeq (const void *key1, const void *key2) { int result; if (key1 == key2) { result = TRUE; } else { result = (tp_value_compare ((DB_VALUE *) key1, (DB_VALUE *) key2, 0, 1) == DB_EQ); } return result; } /* * 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; unsigned int 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) { 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) { 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) { 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->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; /* 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; unsigned int size; unsigned int i; /* Find an estimated size for hash table entries */ rehash_factor = 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) { return ER_OUT_OF_VIRTUAL_MEMORY; } /* Initialize all entries */ for (hvector = new_hvector, i = 0; i < est_size; i++) { *hvector++ = NULL; } /* 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_clear - remove all entries of hash table * return: error code * ht(in/out): hash table */ int mht_clear (MHT_TABLE * ht) { 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; 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) { 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->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 (FILE * out_fp, const MHT_TABLE * ht, const int print_id_opt, int (*print_func) (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) { /* 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) (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) (out_fp, hentry->key, hentry->data, func_args); } } 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 (const MHT_TABLE * ht, const void *key) { 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)) { return hentry->data; } } return NULL; } /* * 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): */ 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_put_internal - internal function for mht_put(), mht_put_new(), and * mht_put_data(); * 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 * 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_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)) { /* 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; } } /* * 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 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_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; } } /* 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); } 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); } /* * 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; } } /* 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 * 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; } } /* 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; 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_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: hashcode = mht_get_shiftmult32 (val->data.utime, ht_size); break; 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 = strlen (ptr); } i = db_value_precision (val); if (i <= 0 || len < i) { i = len; } for (i--; i && ptr[i]; i--) { if (!char_isspace (ptr[i])) { break; } } i++; } if (!ptr || ptr[0] == 0 || i <= 0) { hashcode = 0; } else { hashcode = mht_2str_pseudo_key (ptr, i) % ht_size; } break; default: /* impossible */ 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 */