ssl_util_table.c

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

 *
 * 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)
{
    const unsigned char *key_p = key;
    unsigned int a, b, c, len;

    /* set up the internal state */
    a = 0x9e3779b9;             /* the golden ratio; an arbitrary value */
    b = 0x9e3779b9;
    c = init_val;               /* the previous hash value */

    /* handle most of the key */
    for (len = length; len >= 12; len -= 12) {
        a += (key_p[0]
              + ((unsigned long) key_p[1] << 8)
              + ((unsigned long) key_p[2] << 16)
              + ((unsigned long) key_p[3] << 24));
        b += (key_p[4]
              + ((unsigned long) key_p[5] << 8)
              + ((unsigned long) key_p[6] << 16)
              + ((unsigned long) key_p[7] << 24));
        c += (key_p[8]
              + ((unsigned long) key_p[9] << 8)
              + ((unsigned long) key_p[10] << 16)
              + ((unsigned long) key_p[11] << 24));
        HASH_MIX(a, b, c);
        key_p += 12;
    }

    c += length;

    /* all the case statements fall through to the next */
    switch (len) {
    case 11:
        c += ((unsigned long) key_p[10] << 24);
    case 10:
        c += ((unsigned long) key_p[9] << 16);
    case 9:
        c += ((unsigned long) key_p[8] << 8);
        /* the first byte of c is reserved for the length */
    case 8:
        b += ((unsigned long) key_p[7] << 24);
    case 7:
        b += ((unsigned long) key_p[6] << 16);
    case 6:
        b += ((unsigned long) key_p[5] << 8);
    case 5:
        b += key_p[4];
    case 4:
        a += ((unsigned long) key_p[3] << 24);
    case 3:
        a += ((unsigned long) key_p[2] << 16);
    case 2:
        a += ((unsigned long) key_p[1] << 8);
    case 1:
        a += key_p[0];
        /* case 0: nothing left to add */
    }
    HASH_MIX(a, b, c);

    return c;
}

/*
 * static int entry_size
 *
 * DESCRIPTION:
 *
 * Calculates the appropriate size of an entry to include the key and
 * data sizes as well as any associated alignment to the data.
 *
 * RETURNS:
 *
 * The associated size of the entry.
 *
 * ARGUMENTS:
 *
 * table_p - Table associated with the entries whose size we are
 * determining.
 *
 * key_size - Size of the entry key.
 *
 * data - Size of the entry data.
 */
static int entry_size(const table_t * table_p, const unsigned int key_size,
                      const unsigned int data_size)
{
    int size, left;

    /* initial size -- key is already aligned if right after struct */
    size = sizeof(struct table_shell_st) + key_size;

    /* if there is no alignment then it is easy */
    if (table_p->ta_data_align == 0)
        return size + data_size;
    /* add in our alignement */
    left = size & (table_p->ta_data_align - 1);
    if (left > 0)
        size += table_p->ta_data_align - left;
    /* we add the data size here after the alignment */
    size += data_size;

    return size;
}

/*
 * static unsigned char *entry_data_buf
 *
 * DESCRIPTION:
 *
 * Companion to the ENTRY_DATA_BUF macro but this handles any
 * associated alignment to the data in the entry.
 *
 * RETURNS:
 *
 * Pointer to the data segment of the entry.
 *
 * ARGUMENTS:
 *
 * table_p - Table associated with the entry.
 *
 * entry_p - Entry whose data pointer we are determining.
 */
static unsigned char *entry_data_buf(const table_t * table_p,
                                     const table_entry_t * entry_p)
{
    const unsigned char *buf_p;
    int size, pad;

    buf_p = entry_p->te_key_buf + entry_p->te_key_size;

    /* if there is no alignment then it is easy */
    if (table_p->ta_data_align == 0)
        return (unsigned char *) buf_p;
    /* we need the size of the space before the data */
    size = sizeof(struct table_shell_st) + entry_p->te_key_size;

    /* add in our alignment */
    pad = size & (table_p->ta_data_align - 1);
    if (pad > 0)
        pad = table_p->ta_data_align - pad;
    return (unsigned char *) buf_p + pad;
}

/******************************* sort routines *******************************/

/*
 * static int our_compare
 *
 * DESCRIPTION:
 *
 * Compare two entries by calling user's compare program or by using
 * memcmp.
 *
 * RETURNS:
 *
 * < 0, == 0, or > 0 depending on whether p1 is > p2, == p2, < p2.
 *
 * ARGUMENTS:
 *
 * p1 - First entry pointer to compare.
 *
 * p2 - Second entry pointer to compare.
 *
 * compare - User comparison function.  Ignored.
 *
 * table_p - Associated table being ordered.  Ignored.
 */
static int local_compare(const void *p1, const void *p2,
                         table_compare_t compare, const table_t * table_p)
{
    const table_entry_t *const *ent1_p = p1, *const *ent2_p = p2;
    int cmp;
    unsigned int size;

    /* compare as many bytes as we can */
    size = (*ent1_p)->te_key_size;
    if ((*ent2_p)->te_key_size < size)
        size = (*ent2_p)->te_key_size;
    cmp = memcmp(ENTRY_KEY_BUF(*ent1_p), ENTRY_KEY_BUF(*ent2_p), size);
    /* if common-size equal, then if next more bytes, it is larger */
    if (cmp == 0)
        cmp = (*ent1_p)->te_key_size - (*ent2_p)->te_key_size;
    return cmp;
}

/*
 * static int external_compare
 *
 * DESCRIPTION:
 *
 * Compare two entries by calling user's compare program or by using
 * memcmp.
 *
 * RETURNS:
 *
 * < 0, == 0, or > 0 depending on whether p1 is > p2, == p2, < p2.
 *
 * ARGUMENTS:
 *
 * p1 - First entry pointer to compare.
 *
 * p2 - Second entry pointer to compare.
 *
 * user_compare - User comparison function.
 *
 * table_p - Associated table being ordered.
 */
static int external_compare(const void *p1, const void *p2,
                            table_compare_t user_compare,
                            const table_t * table_p)
{
    const table_entry_t *const *ent1_p = p1, *const *ent2_p = p2;
    /* since we know we are not aligned we can use the EXTRY_DATA_BUF macro */
    return user_compare(ENTRY_KEY_BUF(*ent1_p), (*ent1_p)->te_key_size,
                        ENTRY_DATA_BUF(table_p, *ent1_p),
                        (*ent1_p)->te_data_size,
                        ENTRY_KEY_BUF(*ent2_p), (*ent2_p)->te_key_size,
                        ENTRY_DATA_BUF(table_p, *ent2_p),
                        (*ent2_p)->te_data_size);
}

/*
 * static int external_compare_align
 *
 * DESCRIPTION:
 *
 * Compare two entries by calling user's compare program or by using
 * memcmp.  Alignment information is necessary.
 *
 * RETURNS:
 *
 * < 0, == 0, or > 0 depending on whether p1 is > p2, == p2, < p2.
 *
 * ARGUMENTS:
 *
 * p1 - First entry pointer to compare.
 *
 * p2 - Second entry pointer to compare.
 *
 * user_compare - User comparison function.
 *
 * table_p - Associated table being ordered.
 */
static int external_compare_align(const void *p1, const void *p2,
                                  table_compare_t user_compare,
                                  const table_t * table_p)
{
    const table_entry_t *const *ent1_p = p1, *const *ent2_p = p2;
    /* since we are aligned we have to use the entry_data_buf function */
    return user_compare(ENTRY_KEY_BUF(*ent1_p), (*ent1_p)->te_key_size,
                        entry_data_buf(table_p, *ent1_p),
                        (*ent1_p)->te_data_size,
                        ENTRY_KEY_BUF(*ent2_p), (*ent2_p)->te_key_size,
                        entry_data_buf(table_p, *ent2_p),
                        (*ent2_p)->te_data_size);
}

/*
 * static void split
 *
 * DESCRIPTION:
 *
 * This sorts an array of longs via the quick sort algorithm (it's
 * pretty quick)
 *
 * RETURNS:
 *
 * None.
 *
 * ARGUMENTS:
 *
 * first_p - Start of the list that we are splitting.
 *
 * last_p - Last entry in the list that we are splitting.
 *
 * compare - Comparison function which is handling the actual
 * elements.  This is either a local function or a function to setup
 * the problem element key and data pointers which then hands off to
 * the user function.
 *
 * user_compare - User comparison function.  Could be NULL if we are
 * just using a local comparison function.
 *
 * table_p - Associated table being sorted.
 */
static void split(void *first_p, void *last_p, compare_t compare,
                  table_compare_t user_compare, table_t * table_p)
{
    void *pivot_p, *left_p, *right_p, *left_last_p, *right_first_p;
    void *firsts[MAX_SORT_SPLITS], *lasts[MAX_SORT_SPLITS];
    int split_c = 0;

    for (;;) {

        /* no need to split the list if it is < 2 elements */
        while (first_p >= last_p) {
            if (split_c == 0) {
                /* we are done */
                return;
            }
            split_c--;
            first_p = firsts[split_c];
            last_p = lasts[split_c];
        }

        left_p = first_p;
        right_p = last_p;
        pivot_p = first_p;

        do {
            /* scan from right hand side */
            while (right_p > left_p
                   && compare(right_p, pivot_p, user_compare, table_p) > 0)
                right_p = (char *) right_p - sizeof(table_entry_t *);
            /* scan from left hand side */
            while (right_p > left_p
                   && compare(pivot_p, left_p, user_compare, table_p) >= 0)
                left_p = (char *) left_p + sizeof(table_entry_t *);
            /* if the pointers haven't met then swap values */
            if (right_p > left_p) {
                /* swap_bytes(left_p, right_p) */
                table_entry_t *temp;

                temp = *(table_entry_t **) left_p;
                *(table_entry_t **) left_p = *(table_entry_t **) right_p;
                *(table_entry_t **) right_p = temp;
            }
        } while (right_p > left_p);

        /* now we swap the pivot with the right-hand side */
        {
            /* swap_bytes(pivot_p, right_p); */
            table_entry_t *temp;

            temp = *(table_entry_t **) pivot_p;
            *(table_entry_t **) pivot_p = *(table_entry_t **) right_p;
            *(table_entry_t **) right_p = temp;
        }
        pivot_p = right_p;

        /* save the section to the right of the pivot in our stack */
        right_first_p = (char *) pivot_p + sizeof(table_entry_t *);
        left_last_p = (char *) pivot_p - sizeof(table_entry_t *);

        /* do we need to save the righthand side? */
        if (right_first_p < last_p) {
            if (split_c >= MAX_SORT_SPLITS) {
                /* sanity check here -- we should never get here */
                abort();
            }
            firsts[split_c] = right_first_p;
            lasts[split_c] = last_p;
            split_c++;
        }

        /* do the left hand side of the pivot */
        /* first_p = first_p */
        last_p = left_last_p;
    }
}

/*************************** exported routines *******************************/

/*
 * table_t *table_alloc
 *
 * DESCRIPTION:
 *
 * Allocate a new table structure.
 *
 * RETURNS:
 *
 * A pointer to the new table structure which must be passed to
 * table_free to be deallocated.  On error a NULL is returned.
 *
 * ARGUMENTS:
 *
 * bucket_n - Number of buckets for the hash table.  Our current hash
 * value works best with base two numbers.  Set to 0 to take the
 * library default of 1024.
 *
 * error_p - Pointer to an integer which, if not NULL, will contain a
 * table error code.
 *
 * malloc_f, realloc_f, free_f - Pointers to malloc(3)-, realloc(3)-
 * and free(3)-style functions.
 */
table_t *table_alloc(const unsigned int bucket_n, int *error_p,