innodb_utility.c

/*****************************************************************************

Copyright (c) 1994, 2009, Oracle and/or its affiliates. All Rights Reserved.

This program is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free Software
Foundation; version 2 of the License.

This program is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with
this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA

*****************************************************************************/

/**************************************************/
#include <stdlib.h>
#include <string.h>
#include "innodb_utility.h"

#define UT_HASH_RANDOM_MASK     1463735687
#define UT_HASH_RANDOM_MASK2    1653893711
#define UT_RANDOM_1             1.0412321
#define UT_RANDOM_2             1.1131347
#define UT_RANDOM_3             1.0132677

/*************************************************************/
static
ib_ulint_t
ut_fold_ib_ulint_t_pair(
/*====================*/
        ib_ulint_t      n1,     
        ib_ulint_t      n2)     
{
        return(((((n1 ^ n2 ^ UT_HASH_RANDOM_MASK2) << 8) + n1)
                ^ UT_HASH_RANDOM_MASK) + n2);
}

/*************************************************************/
ib_ulint_t
ut_fold_string(
/*===========*/
        const char*     str)    
{
        ib_ulint_t   fold = 0;

        while (*str != '\0') {
                fold = ut_fold_ib_ulint_t_pair(fold, (ib_ulint_t)(*str));
                str++;
        }

        return(fold);
}

/***********************************************************/
static
ib_ulint_t
ut_find_prime(
/*==========*/
        ib_ulint_t      n)      
{
        ib_ulint_t      pow2;
        ib_ulint_t      i;

        n += 100;

        pow2 = 1;
        while (pow2 * 2 < n) {
                pow2 = 2 * pow2;
        }

        if ((double) n < 1.05 * (double) pow2) {
                n = (ib_ulint_t) ((double) n * UT_RANDOM_1);
        }

        pow2 = 2 * pow2;

        if ((double) n > 0.95 * (double) pow2) {
                n = (ib_ulint_t) ((double) n * UT_RANDOM_2);
        }

        if (n > pow2 - 20) {
                n += 30;
        }

        /* Now we have n far enough from powers of 2. To make
        n more random (especially, if it was not near
        a power of 2), we then multiply it by a random number. */

        n = (ib_ulint_t) ((double) n * UT_RANDOM_3);

        for (;; n++) {
                i = 2;
                while (i * i <= n) {
                        if (n % i == 0) {
                                goto next_n;
                        }
                        i++;
                }

                /* Found a prime */
                break;
next_n:         ;
        }

        return(n);
}

/*************************************************************/
hash_table_t*
hash_create(
/*========*/
        ib_ulint_t      n)      
{
        hash_cell_t*    array;
        ib_ulint_t      prime;
        hash_table_t*   table;

        prime = ut_find_prime(n);

        table = (hash_table_t*) malloc(sizeof(hash_table_t));

        array = (hash_cell_t*) malloc(sizeof(hash_cell_t) * prime);

        /* The default type of hash_table is HASH_TABLE_SYNC_NONE i.e.:
        the caller is responsible for access control to the table. */
        table->array = array;
        table->n_cells = prime;

        /* Initialize the cell array */
        memset(table->array, 0x0, table->n_cells * sizeof(*table->array));

        return(table);
}

/*******************************************************/
static
ib_ulint_t
ut_hash_ulint(
/*==========*/
        ib_ulint_t      key,            
        ib_ulint_t      table_size)     
{
        key = key ^ UT_HASH_RANDOM_MASK2;

        return(key % table_size);
}

/**************************************************************/
ib_ulint_t
hash_calc_hash(
/*===========*/
        ib_ulint_t      fold,   
        hash_table_t*   table)  
{
        return(ut_hash_ulint(fold, table->n_cells));
}

/************************************************************/
inline
hash_cell_t*
hash_get_nth_cell(
/*==============*/
        hash_table_t*   table,  
        ib_ulint_t      n)      
{
        return(table->array + n);
}