ssl_util_table.c

mod_ssl-2.8.31-1.3.41.tar.gz 好用的ssl工具

/*                      _             _
**  _ __ ___   ___   __| |    ___ ___| |  mod_ssl
** | '_ ` _ \ / _ \ / _` |   / __/ __| |  Apache Interface to OpenSSL
** | | | | | | (_) | (_| |   \__ \__ \ |  www.modssl.org
** |_| |_| |_|\___/ \__,_|___|___/___/_|  ftp.modssl.org
**                      |_____|
**  ssl_util_table.c
**  High Performance Hash Table Functions
*/

/* ====================================================================
 * Copyright (c) 1999-2004 Ralf S. Engelschall. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following
 *    disclaimer in the documentation and/or other materials
 *    provided with the distribution.
 *
 * 3. All advertising materials mentioning features or use of this
 *    software must display the following acknowledgment:
 *    "This product includes software developed by
 *     Ralf S. Engelschall <[e-mail]> for use in the
 *     mod_ssl project (http://www.modssl.org/)."
 *
 * 4. The names "mod_ssl" must not be used to endorse or promote
 *    products derived from this software without prior written
 *    permission. For written permission, please contact
 *    [e-mail].
 *
 * 5. Products derived from this software may not be called "mod_ssl"
 *    nor may "mod_ssl" appear in their names without prior
 *    written permission of Ralf S. Engelschall.
 *
 * 6. Redistributions of any form whatsoever must retain the following
 *    acknowledgment:
 *    "This product includes software developed by
 *     Ralf S. Engelschall <[e-mail]> for use in the
 *     mod_ssl project (http://www.modssl.org/)."
 *
 * THIS SOFTWARE IS PROVIDED BY RALF S. ENGELSCHALL ``AS IS'' AND ANY
 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL RALF S. ENGELSCHALL OR
 * HIS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 * ====================================================================
 */

/*
 * Generic hash table handler
 * Table 4.1.0 July-28-1998
 *
 * This library is a generic open hash table with buckets and
 * linked lists.  It is pretty high performance.  Each element
 * has a key and a data.  The user indexes on the key to find the
 * data.
 *
 * Copyright 1998 by Gray Watson <[e-mail]>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose and without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies,
 * and that the name of Gray Watson not be used in advertising or
 * publicity pertaining to distribution of the document or software
 * without specific, written prior permission.
 *
 * Gray Watson makes no representations about the suitability of the
 * software described herein for any purpose.  It is provided "as is"
 * without express or implied warranty.
 *
 * Modified in March 1999 by Ralf S. Engelschall <[e-mail]>
 * for use in the mod_ssl project:
 *   o merged table_loc.h header into table.c
 *   o removed fillproto-comments from table.h
 *   o removed mmap() support because it's too unportable
 *   o added support for MM library via ta_{malloc,calloc,realloc,free}
 */

#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifdef WIN32
#include <io.h>
#include <errno.h>
#else
#include <unistd.h>
#endif

/* forward definitions for table.h */
typedef struct table_st table_t;
typedef struct table_entry_st table_entry_t;

#define TABLE_PRIVATE
#include "ssl_util_table.h"

/****************************** local defines ******************************/

#ifndef BITSPERBYTE
#define BITSPERBYTE     8
#endif
#ifndef BITS
#define BITS(type)      (BITSPERBYTE * (int)sizeof(type))
#endif

#define TABLE_MAGIC     0xBADF00D       /* very magic magicness */
#define LINEAR_MAGIC    0xAD00D00       /* magic value for linear struct */
#define DEFAULT_SIZE    1024    /* default table size */
#define MAX_ALIGNMENT   128     /* max alignment value */
#define MAX_SORT_SPLITS 128     /* qsort can handle 2^128 entries */

/* returns 1 when we should grow or shrink the table */
#define SHOULD_TABLE_GROW(tab)  ((tab)->ta_entry_n > (tab)->ta_bucket_n * 2)
#define SHOULD_TABLE_SHRINK(tab) ((tab)->ta_entry_n < (tab)->ta_bucket_n / 2)

/*
 * void HASH_MIX
 *
 * DESCRIPTION:
 *
 * Mix 3 32-bit values reversibly.  For every delta with one or two bits
 * set, and the deltas of all three high bits or all three low bits,
 * whether the original value of a,b,c is almost all zero or is
 * uniformly distributed.
 *
 * If HASH_MIX() is run forward or backward, at least 32 bits in a,b,c
 * have at least 1/4 probability of changing.  If mix() is run
 * forward, every bit of c will change between 1/3 and 2/3 of the
 * time.  (Well, 22/100 and 78/100 for some 2-bit deltas.)
 *
 * HASH_MIX() takes 36 machine instructions, but only 18 cycles on a
 * superscalar machine (like a Pentium or a Sparc).  No faster mixer
 * seems to work, that's the result of my brute-force search.  There
 * were about 2^68 hashes to choose from.  I only tested about a
 * billion of those.
 */
#define HASH_MIX(a, b, c) \
 do { \
   a -= b; a -= c; a ^= (c >> 13); \
   b -= c; b -= a; b ^= (a << 8); \
   c -= a; c -= b; c ^= (b >> 13); \
   a -= b; a -= c; a ^= (c >> 12); \
   b -= c; b -= a; b ^= (a << 16); \
   c -= a; c -= b; c ^= (b >> 5); \
   a -= b; a -= c; a ^= (c >> 3); \
   b -= c; b -= a; b ^= (a << 10); \
   c -= a; c -= b; c ^= (b >> 15); \
 } while(0)

#define TABLE_POINTER(table, type, pnt)         (pnt)

/*
 * Macros to get at the key and the data pointers
 */
#define ENTRY_KEY_BUF(entry_p)          ((entry_p)->te_key_buf)
#define ENTRY_DATA_BUF(tab_p, entry_p)  \
     (ENTRY_KEY_BUF(entry_p) + (entry_p)->te_key_size)

/*
 * Table structures...
 */

/*
 * HACK: this should be equiv as the table_entry_t without the key_buf
 * char.  We use this with the ENTRY_SIZE() macro above which solves
 * the problem with the lack of the [0] GNU hack.  We use the
 * table_entry_t structure to better map the memory and make things
 * faster.
 */
typedef struct table_shell_st {
    unsigned int te_key_size;   /* size of data */
    unsigned int te_data_size;  /* size of data */
    struct table_shell_st *te_next_p;   /* pointer to next in the list */
    /* NOTE: this does not have the te_key_buf field here */
} table_shell_t;

/*
 * Elements in the bucket linked-lists.  The key[1] is the start of
 * the key with the rest of the key and all of the data information
 * packed in memory directly after the end of this structure.
 *
 * NOTE: if this structure is changed, the table_shell_t must be changed
 * to match.
 */
struct table_entry_st {
    unsigned int te_key_size;   /* size of data */
    unsigned int te_data_size;  /* size of data */
    struct table_entry_st *te_next_p;   /* pointer to next in the list */
    unsigned char te_key_buf[1];        /* 1st byte of key buf */
};

/* external structure for debuggers be able to see void */
typedef table_entry_t table_entry_ext_t;

/* main table structure */
struct table_st {
    unsigned int ta_magic;      /* magic number */
    unsigned int ta_flags;      /* table's flags defined in table.h */
    unsigned int ta_bucket_n;   /* num of buckets, should be 2^X */
    unsigned int ta_entry_n;    /* num of entries in all buckets */
    unsigned int ta_data_align; /* data alignment value */
    table_entry_t **ta_buckets; /* array of linked lists */
    table_linear_t ta_linear;   /* linear tracking */
    unsigned long ta_file_size; /* size of on-disk space */
    void *(*ta_malloc)(size_t size);
    void *(*ta_calloc)(size_t number, size_t size);
    void *(*ta_realloc)(void *ptr, size_t size);
    void (*ta_free)(void *ptr);
};

/* external table structure for debuggers */
typedef table_t table_ext_t;

/* local comparison functions */
typedef int (*compare_t) (const void *element1_p, const void *element2_p,
                          table_compare_t user_compare,
                          const table_t * table_p);

/*
 * to map error to string
 */
typedef struct {
    int es_error;               /* error number */
    char *es_string;            /* assocaited string */
} error_str_t;

static error_str_t errors[] =
{
    {TABLE_ERROR_NONE, "no error"},
    {TABLE_ERROR_PNT, "invalid table pointer"},
    {TABLE_ERROR_ARG_NULL, "buffer argument is null"},
    {TABLE_ERROR_SIZE, "incorrect size argument"},
    {TABLE_ERROR_OVERWRITE, "key exists and no overwrite"},
    {TABLE_ERROR_NOT_FOUND, "key does not exist"},
    {TABLE_ERROR_ALLOC, "error allocating memory"},
    {TABLE_ERROR_LINEAR, "linear access not in progress"},
    {TABLE_ERROR_OPEN, "could not open file"},
    {TABLE_ERROR_SEEK, "could not seek to position in file"},
    {TABLE_ERROR_READ, "could not read from file"},
    {TABLE_ERROR_WRITE, "could not write to file"},
    {TABLE_ERROR_EMPTY, "table is empty"},
    {TABLE_ERROR_NOT_EMPTY, "table contains data"},
    {TABLE_ERROR_ALIGNMENT, "invalid alignment value"},
    {0}
};

#define INVALID_ERROR   "invalid error code"

/****************************** local functions ******************************/

/*
 * static table_entry_t *first_entry
 *
 * DESCRIPTION:
 *
 * Return the first entry in the table.  It will set the linear
 * structure counter to the position of the first entry.
 *
 * RETURNS:
 *
 * Success: A pointer to the first entry in the table.
 *
 * Failure: NULL if there is no first entry.
 *
 * ARGUMENTS:
 *
 * table_p - Table whose next entry we are finding.
 *
 * linear_p - Pointer to a linear structure which we will advance and
 * then find the corresponding entry.
 */
static table_entry_t *first_entry(table_t * table_p,
                                  table_linear_t * linear_p)
{
    table_entry_t *entry_p;
    unsigned int bucket_c = 0;

    /* look for the first non-empty bucket */
    for (bucket_c = 0; bucket_c < table_p->ta_bucket_n; bucket_c++) {
        entry_p = table_p->ta_buckets[bucket_c];
        if (entry_p != NULL) {
            if (linear_p != NULL) {
                linear_p->tl_bucket_c = bucket_c;
                linear_p->tl_entry_c = 0;
            }
            return TABLE_POINTER(table_p, table_entry_t *, entry_p);
        }
    }

    return NULL;
}

/*
 * static table_entry_t *next_entry
 *
 * DESCRIPTION:
 *
 * Return the next entry in the table which is past the position in
 * our linear pointer.  It will advance the linear structure counters.
 *
 * RETURNS:
 *
 * Success: A pointer to the next entry in the table.
 *
 * Failure: NULL.
 *
 * ARGUMENTS:
 *
 * table_p - Table whose next entry we are finding.
 *
 * linear_p - Pointer to a linear structure which we will advance and
 * then find the corresponding entry.
 *
 * error_p - Pointer to an integer which when the routine returns will
 * contain a table error code.
 */
static table_entry_t *next_entry(table_t * table_p, table_linear_t * linear_p,
                                 int *error_p)
{
    table_entry_t *entry_p;
    int entry_c;

    /* can't next if we haven't first-ed */
    if (linear_p == NULL) {
        if (error_p != NULL)
            *error_p = TABLE_ERROR_LINEAR;
        return NULL;
    }

    if (linear_p->tl_bucket_c >= table_p->ta_bucket_n) {
        /*
         * NOTE: this might happen if we delete an item which shortens the
         * table bucket numbers.
         */
        if (error_p != NULL)
            *error_p = TABLE_ERROR_NOT_FOUND;
        return NULL;
    }

    linear_p->tl_entry_c++;

    /* find the entry which is the nth in the list */
    entry_p = table_p->ta_buckets[linear_p->tl_bucket_c];
    /* NOTE: we swap the order here to be more efficient */
    for (entry_c = linear_p->tl_entry_c; entry_c > 0; entry_c--) {
        /* did we reach the end of the list? */
        if (entry_p == NULL)
            break;
        entry_p = TABLE_POINTER(table_p, table_entry_t *, entry_p)->te_next_p;
    }

    /* did we find an entry in the current bucket? */
    if (entry_p != NULL) {
        if (error_p != NULL)
            *error_p = TABLE_ERROR_NONE;
        return TABLE_POINTER(table_p, table_entry_t *, entry_p);
    }

    /* find the first entry in the next non-empty bucket */

    linear_p->tl_entry_c = 0;
    for (linear_p->tl_bucket_c++; linear_p->tl_bucket_c < table_p->ta_bucket_n;
         linear_p->tl_bucket_c++) {
        entry_p = table_p->ta_buckets[linear_p->tl_bucket_c];
        if (entry_p != NULL) {
            if (error_p != NULL)
                *error_p = TABLE_ERROR_NONE;
            return TABLE_POINTER(table_p, table_entry_t *, entry_p);
        }
    }

    if (error_p != NULL)
        *error_p = TABLE_ERROR_NOT_FOUND;
    return NULL;
}

/*
 * static unsigned int hash
 *
 * DESCRIPTION:
 *
 * Hash a variable-length key into a 32-bit value.  Every bit of the
 * key affects every bit of the return value.  Every 1-bit and 2-bit
 * delta achieves avalanche.  About (6 * len + 35) instructions.  The
 * best hash table sizes are powers of 2.  There is no need to use mod
 * (sooo slow!).  If you need less than 32 bits, use a bitmask.  For
 * example, if you need only 10 bits, do h = (h & hashmask(10)); In
 * which case, the hash table should have hashsize(10) elements.
 *
 * By Bob Jenkins, 1996.  [e-mail].  You may use
 * this code any way you wish, private, educational, or commercial.
 * It's free.  See
 * http://ourworld.compuserve.com/homepages/bob_jenkins/evahash.htm
 * Use for hash table lookup, or anything where one collision in 2^^32
 * is acceptable.  Do NOT use for cryptographic purposes.