ssl_util_table.c

Apache HTTP Server 是一个功能强大的灵活的与HTTP/1.1相兼容的web服务器.这里给出的是Apache HTTP服务器的源码。

/* Copyright 2001-2005 The Apache Software Foundation or its licensors, as
 * applicable.
 *
 * 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.
 */

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

/*
 * 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 <stdlib.h>
#include <string.h>

/* 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"
#include "mod_ssl.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)(void *opt_param, size_t size);
    void *(*ta_calloc)(void *opt_param, size_t number, size_t size);
    void *(*ta_realloc)(void *opt_param, void *ptr, size_t size);
    void (*ta_free)(void *opt_param, void *ptr);
    void *opt_param;
};

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


/********************** wrappers for system functions ************************/
static void *sys_malloc(void *param, size_t size)
{
    return malloc(size);
}

static void *sys_calloc(void *param, size_t size1, size_t size2)
{
    return calloc(size1, size2);
}

static void *sys_realloc(void *param, void *ptr, size_t size)
{
    return realloc(ptr, size);
}

static void sys_free(void *param, void *ptr)
{
    free(ptr);
}

/****************************** 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.
 *
 * RETURNS:
 *
 * Returns a 32-bit hash value.
 *
 * ARGUMENTS:
 *
 * key - Key (the unaligned variable-length array of bytes) that we
 * are hashing.
 *
 * length - Length of the key in bytes.
 *
 * init_val - Initialization value of the hash if you need to hash a
 * number of strings together.  For instance, if you are hashing N
 * strings (unsigned char **)keys, do it like this:
 *
 * for (i=0, h=0; i<N; ++i) h = hash( keys[i], len[i], h);
 */
static unsigned int hash(const unsigned char *key,
                         const unsigned int length,
                         const unsigned int init_val)
{