/* 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 <gray@letters.com>
 *
 * 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 <rse@engelschall.com>
 * 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.  bob_jenkins@compuserve.com.  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)
{
    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,
                 void *(*malloc_f)(void *opt_param, size_t size),
                 void *(*calloc_f)(void *opt_param, size_t number, size_t size),
                 void *(*realloc_f)(void *opt_param, void *ptr, size_t size),
                 void (*free_f)(void *opt_param, void *ptr), void *opt_param)
{
    table_t *table_p = NULL;
    unsigned int buck_n;

    /* allocate a table structure */
    if (malloc_f != NULL)
        table_p = malloc_f(opt_param, sizeof(table_t));
    else
        table_p = malloc(sizeof(table_t));
    if (table_p == NULL) {
        if (error_p != NULL)
            *error_p = TABLE_ERROR_ALLOC;
        return NULL;
    }

    if (bucket_n > 0)
        buck_n = bucket_n;
    else
        buck_n = DEFAULT_SIZE;
    /* allocate the buckets which are NULLed */
    if (calloc_f != NULL)
        table_p->ta_buckets = (table_entry_t **)calloc_f(opt_param, buck_n,
                                                       sizeof(table_entry_t *));
    else
        table_p->ta_buckets = (table_entry_t **)calloc(buck_n, sizeof(table_entry_t *));
    if (table_p->ta_buckets == NULL) {
        if (error_p != NULL)
            *error_p = TABLE_ERROR_ALLOC;
        if (free_f != NULL)
            free_f(opt_param, table_p);
        else
            free(table_p);
        return NULL;
    }

    /* initialize structure */
    table_p->ta_magic = TABLE_MAGIC;
    table_p->ta_flags = 0;
    table_p->ta_bucket_n = buck_n;
    table_p->ta_entry_n = 0;
    table_p->ta_data_align = 0;
    table_p->ta_linear.tl_magic = 0;
    table_p->ta_linear.tl_bucket_c = 0;
    table_p->ta_linear.tl_entry_c = 0;
    table_p->ta_file_size = 0;
    table_p->ta_malloc  = malloc_f  != NULL ? malloc_f  : sys_malloc;
    table_p->ta_calloc  = calloc_f  != NULL ? calloc_f  : sys_calloc;
    table_p->ta_realloc = realloc_f != NULL ? realloc_f : sys_realloc;
    table_p->ta_free    = free_f    != NULL ? free_f    : sys_free;
    table_p->opt_param = opt_param;

    if (error_p != NULL)
        *error_p = TABLE_ERROR_NONE;
    return table_p;
}

/*
 * int table_attr
 *
 * DESCRIPTION:
 *
 * Set the attributes for the table.  The available attributes are
 * specified at the top of table.h.
 *
 * RETURNS:
 *
 * Success - TABLE_ERROR_NONE
 *
 * Failure - Table error code.
 *
 * ARGUMENTS:
 *
 * table_p - Pointer to a table structure which we will be altering.
 *
 * attr - Attribute(s) that we will be applying to the table.
 */
int table_attr(table_t * table_p, const int attr)
{
    if (table_p == NULL)
        return TABLE_ERROR_ARG_NULL;
    if (table_p->ta_magic != TABLE_MAGIC)
        return TABLE_ERROR_PNT;
    table_p->ta_flags = attr;

    return TABLE_ERROR_NONE;
}

/*
 * int table_set_data_alignment
 *
 * DESCRIPTION:
 *
 * Set the alignment for the data in the table.  For data elements
 * sizeof(long) is recommended unless you use smaller data types
 * exclusively.
 *
 * WARNING: This must be done before any data gets put into the table.
 *
 * RETURNS:
 *
 * Success - TABLE_ERROR_NONE
 *
 * Failure - Table error code.
 *
 * ARGUMENTS:
 *
 * table_p - Pointer to a table structure which we will be altering.
 *
 * alignment - Alignment requested for the data.  Must be a power of
 * 2.  Set to 0 for none.
 */
int table_set_data_alignment(table_t * table_p, const int alignment)
{
    int val;

    if (table_p == NULL)
        return TABLE_ERROR_ARG_NULL;
    if (table_p->ta_magic != TABLE_MAGIC)
        return TABLE_ERROR_PNT;
    if (table_p->ta_entry_n > 0)
        return TABLE_ERROR_NOT_EMPTY;
    /* defaults */
    if (alignment < 2)
        table_p->ta_data_align = 0;
    else {
        /* verify we have a base 2 number */
        for (val = 2; val < MAX_ALIGNMENT; val *= 2) {
            if (val == alignment)
                break;
        }
        if (val >= MAX_ALIGNMENT)
            return TABLE_ERROR_ALIGNMENT;
        table_p->ta_data_align = alignment;
    }

    return TABLE_ERROR_NONE;
}

/*
 * int table_clear
 *
 * DESCRIPTION:
 *
 * Clear out and free all elements in a table structure.
 *
 * RETURNS:
 *
 * Success - TABLE_ERROR_NONE
 *
 * Failure - Table error code.
 *
 * ARGUMENTS:
 *
 * table_p - Table structure pointer that we will be clearing.
 */
int table_clear(table_t * table_p)
{
    table_entry_t *entry_p, *next_p;
    table_entry_t **bucket_p, **bounds_p;

    if (table_p == NULL)
        return TABLE_ERROR_ARG_NULL;
    if (table_p->ta_magic != TABLE_MAGIC)
        return TABLE_ERROR_PNT;
    /* free the table allocation and table structure */
    bounds_p = table_p->ta_buckets + table_p->ta_bucket_n;
    for (bucket_p = table_p->ta_buckets; bucket_p < bounds_p; bucket_p++) {
        for (entry_p = *bucket_p; entry_p != NULL; entry_p = next_p) {
            /* record the next pointer before we free */
            next_p = entry_p->te_next_p;
            table_p->ta_free(table_p->opt_param, entry_p);
        }
        /* clear the bucket entry after we free its entries */
        *bucket_p = NULL;
    }

    /* reset table state info */
    table_p->ta_entry_n = 0;
    table_p->ta_linear.tl_magic = 0;
    table_p->ta_linear.tl_bucket_c = 0;
    table_p->ta_linear.tl_entry_c = 0;

    return TABLE_ERROR_NONE;
}

/*
 * int table_free
 *
 * DESCRIPTION:
 *
 * Deallocates a table structure.
 *
 * RETURNS:
 *
 * Success - TABLE_ERROR_NONE
 *
 * Failure - Table error code.
 *
 * ARGUMENTS:
 *
 * table_p - Table structure pointer that we will be freeing.
 */
int table_free(table_t * table_p)
{
    int ret;

    if (table_p == NULL)
        return TABLE_ERROR_ARG_NULL;
    if (table_p->ta_magic != TABLE_MAGIC)
        return TABLE_ERROR_PNT;
    ret = table_clear(table_p);

    if (table_p->ta_buckets != NULL)
        table_p->ta_free(table_p->opt_param, table_p->ta_buckets);
    table_p->ta_magic = 0;
    table_p->ta_free(table_p->opt_param, table_p);

    return ret;
}

/*
 * int table_insert_kd
 *
 * DESCRIPTION:
 *
 * Like table_insert except it passes back a pointer to the key and
 * the data buffers after they have been inserted into the table
 * structure.
 *
 * This routine adds a key/data pair both of which are made up of a
 * buffer of bytes and an associated size.  Both the key and the data
 * will be copied into buffers allocated inside the table.  If the key
 * exists already, the associated data will be replaced if the
 * overwrite flag is set, otherwise an error is returned.
 *
 * NOTE: be very careful changing the values since the table library
 * provides the pointers to its memory.  The key can _never_ be
 * changed otherwise you will not find it again.  The data can be
 * changed but its length can never be altered unless you delete and
 * re-insert it into the table.
 *
 * WARNING: The pointers to the key and data are not in any specific
 * alignment.  Accessing the key and/or data as an short, integer, or
 * long pointer directly can cause problems.
 *
 * WARNING: Replacing a data cell (not inserting) will cause the table
 * linked list to be temporarily invalid.  Care must be taken with
 * multiple threaded programs which are relying on the first/next
 * linked list to be always valid.
 *
 * RETURNS:
 *
 * Success - TABLE_ERROR_NONE
 *
 * Failure - Table error code.
 *
 * ARGUMENTS:
 *
 * table_p - Table structure pointer into which we will be inserting a
 * new key/data pair.
 *
 * key_buf - Buffer of bytes of the key that we are inserting.  If you
 * are storing an (int) as the key (for example) then key_buf should
 * be a (int *).
 *
 * key_size - Size of the key_buf buffer.  If set to < 0 then the
 * library will do a strlen of key_buf and add 1 for the '\0'.  If you
 * are storing an (int) as the key (for example) then key_size should
 * be sizeof(int).
 *
 * data_buf - Buffer of bytes of the data that we are inserting.  If
 * it is NULL then the library will allocate space for the data in the
 * table without copying in any information.  If data_buf is NULL and
 * data_size is 0 then the library will associate a NULL data pointer
 * with the key.  If you are storing a (long) as the data (for
 * example) then data_buf should be a (long *).
 *
 * data_size - Size of the data_buf buffer.  If set to < 0 then the
 * library will do a strlen of data_buf and add 1 for the '\0'.  If
 * you are storing an (long) as the key (for example) then key_size
 * should be sizeof(long).
 *
 * key_buf_p - Pointer which, if not NULL, will be set to the address
 * of the key storage that was allocated in the table.  If you are
 * storing an (int) as the key (for example) then key_buf_p should be
 * (int **) i.e. the address of a (int *).
 *
 * data_buf_p - Pointer which, if not NULL, will be set to the address
 * of the data storage that was allocated in the table.  If you are
 * storing an (long) as the data (for example) then data_buf_p should
 * be (long **) i.e. the address of a (long *).
 *
 * overwrite - Flag which, if set to 1, will allow the overwriting of
 * the data in the table with the new data if the key already exists
 * in the table.
 */
int table_insert_kd(table_t * table_p,
                    const void *key_buf, const int key_size,
                    const void *data_buf, const int data_size,
                    void **key_buf_p, void **data_buf_p,
                    const char overwrite_b)
{
    int bucket;
    unsigned int ksize, dsize;
    table_entry_t *entry_p, *last_p;
    void *key_copy_p, *data_copy_p;

    /* check the arguments */
    if (table_p == NULL)
        return TABLE_ERROR_ARG_NULL;
    if (table_p->ta_magic != TABLE_MAGIC)
        return TABLE_ERROR_PNT;
    if (key_buf == NULL)
        return TABLE_ERROR_ARG_NULL;
    /* data_buf can be null but size must be >= 0, if it isn't null size != 0 */
    if ((data_buf == NULL && data_size < 0)
        || (data_buf != NULL && data_size == 0))
        return TABLE_ERROR_SIZE;
    /* determine sizes of key and data */
    if (key_size < 0)
        ksize = strlen((char *) key_buf) + sizeof(char);
    else
        ksize = key_size;
    if (data_size < 0)
        dsize = strlen((char *) data_buf) + sizeof(char);
    else
        dsize = data_size;
    /* get the bucket number via a hash function */
    bucket = hash(key_buf, ksize, 0) % table_p->ta_bucket_n;

    /* look for the entry in this bucket, only check keys of the same size */
    last_p = NULL;
    for (entry_p = table_p->ta_buckets[bucket];
         (entry_p != NULL) && (entry_p->te_next_p != last_p);
         last_p = entry_p, entry_p = entry_p->te_next_p) {
        if (entry_p->te_key_size == ksize
            && memcmp(ENTRY_KEY_BUF(entry_p), key_buf, ksize) == 0)
            break;
    }

    /* did we find it?  then we are in replace mode. */
    if (entry_p != NULL) {

        /* can we not overwrite existing data? */
        if (!overwrite_b) {
            if (key_buf_p != NULL)
                *key_buf_p = ENTRY_KEY_BUF(entry_p);
            if (data_buf_p != NULL) {
                if (entry_p->te_data_size == 0)
                    *data_buf_p = NULL;
                else {
                    if (table_p->ta_data_align == 0)
                        *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
                    else
                        *data_buf_p = entry_data_buf(table_p, entry_p);
                }
            }
            return TABLE_ERROR_OVERWRITE;
        }

        /* re-alloc entry's data if the new size != the old */
        if (dsize != entry_p->te_data_size) {

            /*
             * First we delete it from the list to keep the list whole.
             * This properly preserves the linked list in case we have a
             * thread marching through the linked list while we are
             * inserting.  Maybe this is an unnecessary protection but it
             * should not harm that much.
             */
            if (last_p == NULL)
                table_p->ta_buckets[bucket] = entry_p->te_next_p;
            else
                last_p->te_next_p = entry_p->te_next_p;
            /*
             * Realloc the structure which may change its pointer. NOTE:
             * this may change any previous data_key_p and data_copy_p
             * pointers.
             */
            entry_p = (table_entry_t *)
                       table_p->ta_realloc(table_p->opt_param, entry_p,
			     entry_size(table_p, entry_p->te_key_size, dsize));
            if (entry_p == NULL)
                return TABLE_ERROR_ALLOC;
            /* add it back to the front of the list */
            entry_p->te_data_size = dsize;
            entry_p->te_next_p = table_p->ta_buckets[bucket];
            table_p->ta_buckets[bucket] = entry_p;
        }

        /* copy or replace data in storage */
        if (dsize > 0) {
            if (table_p->ta_data_align == 0)
                data_copy_p = ENTRY_DATA_BUF(table_p, entry_p);
            else
                data_copy_p = entry_data_buf(table_p, entry_p);
            if (data_buf != NULL)
                memcpy(data_copy_p, data_buf, dsize);
        }
        else
            data_copy_p = NULL;
        if (key_buf_p != NULL)
            *key_buf_p = ENTRY_KEY_BUF(entry_p);
        if (data_buf_p != NULL)
            *data_buf_p = data_copy_p;
        /* returning from the section where we were overwriting table data */
        return TABLE_ERROR_NONE;
    }

    /*
     * It is a new entry.
     */

    /* allocate a new entry */
    entry_p = (table_entry_t *)
               table_p->ta_malloc(table_p->opt_param,
                                  entry_size(table_p, ksize, dsize));
    if (entry_p == NULL)
        return TABLE_ERROR_ALLOC;
    /* copy key into storage */
    entry_p->te_key_size = ksize;
    key_copy_p = ENTRY_KEY_BUF(entry_p);
    memcpy(key_copy_p, key_buf, ksize);

    /* copy data in */
    entry_p->te_data_size = dsize;
    if (dsize > 0) {
        if (table_p->ta_data_align == 0)
            data_copy_p = ENTRY_DATA_BUF(table_p, entry_p);
        else
            data_copy_p = entry_data_buf(table_p, entry_p);
        if (data_buf != NULL)
            memcpy(data_copy_p, data_buf, dsize);
    }
    else
        data_copy_p = NULL;
    if (key_buf_p != NULL)
        *key_buf_p = key_copy_p;
    if (data_buf_p != NULL)
        *data_buf_p = data_copy_p;
    /* insert into list, no need to append */
    entry_p->te_next_p = table_p->ta_buckets[bucket];
    table_p->ta_buckets[bucket] = entry_p;

    table_p->ta_entry_n++;

    /* do we need auto-adjust? */
    if (table_p->ta_flags & TABLE_FLAG_AUTO_ADJUST
        && SHOULD_TABLE_GROW(table_p))
        return table_adjust(table_p, table_p->ta_entry_n);
    return TABLE_ERROR_NONE;
}

/*
 * int table_insert
 *
 * DESCRIPTION:
 *
 * Exactly the same as table_insert_kd except it does not pass back a
 * pointer to the key after they have been inserted into the table
 * structure.  This is still here for backwards compatibility.
 *
 * See table_insert_kd for more information.
 *
 * RETURNS:
 *
 * Success - TABLE_ERROR_NONE
 *
 * Failure - Table error code.
 *
 * ARGUMENTS:
 *
 * table_p - Table structure pointer into which we will be inserting a
 * new key/data pair.
 *
 * key_buf - Buffer of bytes of the key that we are inserting.  If you
 * are storing an (int) as the key (for example) then key_buf should
 * be a (int *).
 *
 * key_size - Size of the key_buf buffer.  If set to < 0 then the
 * library will do a strlen of key_buf and add 1 for the '\0'.  If you
 * are storing an (int) as the key (for example) then key_size should
 * be sizeof(int).
 *
 * data_buf - Buffer of bytes of the data that we are inserting.  If
 * it is NULL then the library will allocate space for the data in the
 * table without copying in any information.  If data_buf is NULL and
 * data_size is 0 then the library will associate a NULL data pointer
 * with the key.  If you are storing a (long) as the data (for
 * example) then data_buf should be a (long *).
 *
 * data_size - Size of the data_buf buffer.  If set to < 0 then the
 * library will do a strlen of data_buf and add 1 for the '\0'.  If
 * you are storing an (long) as the key (for example) then key_size
 * should be sizeof(long).
 *
 * data_buf_p - Pointer which, if not NULL, will be set to the address
 * of the data storage that was allocated in the table.  If you are
 * storing an (long) as the data (for example) then data_buf_p should
 * be (long **) i.e. the address of a (long *).
 *
 * overwrite - Flag which, if set to 1, will allow the overwriting of
 * the data in the table with the new data if the key already exists
 * in the table.
 */
int table_insert(table_t * table_p,
                 const void *key_buf, const int key_size,
                 const void *data_buf, const int data_size,
                 void **data_buf_p, const char overwrite_b)
{
    return table_insert_kd(table_p, key_buf, key_size, data_buf, data_size,
                           NULL, data_buf_p, overwrite_b);
}

/*
 * int table_retrieve
 *
 * DESCRIPTION:
 *
 * This routine looks up a key made up of a buffer of bytes and an
 * associated size in the table.  If found then it returns the
 * associated data information.
 *
 * RETURNS:
 *
 * Success - TABLE_ERROR_NONE
 *
 * Failure - Table error code.
 *
 * ARGUMENTS:
 *
 * table_p - Table structure pointer into which we will be searching
 * for the key.
 *
 * key_buf - Buffer of bytes of the key that we are searching for.  If
 * you are looking for an (int) as the key (for example) then key_buf
 * should be a (int *).
 *
 * key_size - Size of the key_buf buffer.  If set to < 0 then the
 * library will do a strlen of key_buf and add 1 for the '\0'.  If you
 * are looking for an (int) as the key (for example) then key_size
 * should be sizeof(int).
 *
 * data_buf_p - Pointer which, if not NULL, will be set to the address
 * of the data storage that was allocated in the table and that is
 * associated with the key.  If a (long) was stored as the data (for
 * example) then data_buf_p should be (long **) i.e. the address of a
 * (long *).
 *
 * data_size_p - Pointer to an integer which, if not NULL, will be set
 * to the size of the data stored in the table that is associated with
 * the key.
 */
int table_retrieve(table_t * table_p,
                   const void *key_buf, const int key_size,
                   void **data_buf_p, int *data_size_p)
{
    int bucket;
    unsigned int ksize;
    table_entry_t *entry_p, **buckets;

    if (table_p == NULL)
        return TABLE_ERROR_ARG_NULL;
    if (table_p->ta_magic != TABLE_MAGIC)
        return TABLE_ERROR_PNT;
    if (key_buf == NULL)
        return TABLE_ERROR_ARG_NULL;
    /* find key size */
    if (key_size < 0)
        ksize = strlen((char *) key_buf) + sizeof(char);
    else
        ksize = key_size;
    /* get the bucket number via a has function */
    bucket = hash(key_buf, ksize, 0) % table_p->ta_bucket_n;

    /* look for the entry in this bucket, only check keys of the same size */
    buckets = table_p->ta_buckets;
    for (entry_p = buckets[bucket];
         entry_p != NULL;
         entry_p = entry_p->te_next_p) {
        entry_p = TABLE_POINTER(table_p, table_entry_t *, entry_p);
        if (entry_p->te_key_size == ksize
            && memcmp(ENTRY_KEY_BUF(entry_p), key_buf, ksize) == 0)
            break;
    }

    /* not found? */
    if (entry_p == NULL)
        return TABLE_ERROR_NOT_FOUND;
    if (data_buf_p != NULL) {
        if (entry_p->te_data_size == 0)
            *data_buf_p = NULL;
        else {
            if (table_p->ta_data_align == 0)
                *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
            else
                *data_buf_p = entry_data_buf(table_p, entry_p);
        }
    }
    if (data_size_p != NULL)
        *data_size_p = entry_p->te_data_size;
    return TABLE_ERROR_NONE;
}

/*
 * int table_delete
 *
 * DESCRIPTION:
 *
 * This routine looks up a key made up of a buffer of bytes and an
 * associated size in the table.  If found then it will be removed
 * from the table.  The associated data can be passed back to the user
 * if requested.
 *
 * RETURNS:
 *
 * Success - TABLE_ERROR_NONE
 *
 * Failure - Table error code.
 *
 * NOTE: this could be an allocation error if the library is to return
 * the data to the user.
 *
 * ARGUMENTS:
 *
 * table_p - Table structure pointer from which we will be deleteing
 * the key.
 *
 * key_buf - Buffer of bytes of the key that we are searching for to
 * delete.  If you are deleting an (int) key (for example) then
 * key_buf should be a (int *).
 *
 * key_size - Size of the key_buf buffer.  If set to < 0 then the
 * library will do a strlen of key_buf and add 1 for the '\0'.  If you
 * are deleting an (int) key (for example) then key_size should be
 * sizeof(int).
 *
 * data_buf_p - Pointer which, if not NULL, will be set to the address
 * of the data storage that was allocated in the table and that was
 * associated with the key.  If a (long) was stored as the data (for
 * example) then data_buf_p should be (long **) i.e. the address of a
 * (long *).  If a pointer is passed in, the caller is responsible for
 * freeing it after use.  If data_buf_p is NULL then the library will
 * free up the data allocation itself.
 *
 * data_size_p - Pointer to an integer which, if not NULL, will be set
 * to the size of the data that was stored in the table and that was
 * associated with the key.
 */
int table_delete(table_t * table_p,
                 const void *key_buf, const int key_size,
                 void **data_buf_p, int *data_size_p)
{
    int bucket;
    unsigned int ksize;
    unsigned char *data_copy_p;
    table_entry_t *entry_p, *last_p;

    if (table_p == NULL)
        return TABLE_ERROR_ARG_NULL;
    if (table_p->ta_magic != TABLE_MAGIC)
        return TABLE_ERROR_PNT;
    if (key_buf == NULL)
        return TABLE_ERROR_ARG_NULL;
    /* get the key size */
    if (key_size < 0)
        ksize = strlen((char *) key_buf) + sizeof(char);
    else
        ksize = key_size;
    /* find our bucket */
    bucket = hash(key_buf, ksize, 0) % table_p->ta_bucket_n;

    /* look for the entry in this bucket, only check keys of the same size */
    for (last_p = NULL, entry_p = table_p->ta_buckets[bucket]; entry_p != NULL;
         last_p = entry_p, entry_p = entry_p->te_next_p) {
        if (entry_p->te_key_size == ksize
            && memcmp(ENTRY_KEY_BUF(entry_p), key_buf, ksize) == 0)
            break;
    }

    /* did we find it? */
    if (entry_p == NULL)
        return TABLE_ERROR_NOT_FOUND;
    /*
     * NOTE: we may want to adjust the linear counters here if the entry
     * we are deleting is the one we are pointing on or is ahead of the
     * one in the bucket list
     */

    /* remove entry from the linked list */
    if (last_p == NULL)
        table_p->ta_buckets[bucket] = entry_p->te_next_p;
    else
        last_p->te_next_p = entry_p->te_next_p;
    /* free entry */
    if (data_buf_p != NULL) {
        if (entry_p->te_data_size == 0)
            *data_buf_p = NULL;
        else {
            /*
             * if we were storing it compacted, we now need to malloc some
             * space if the user wants the value after the delete.
             */
            *data_buf_p = table_p->ta_malloc(table_p->opt_param,
                                             entry_p->te_data_size);
            if (*data_buf_p == NULL)
                return TABLE_ERROR_ALLOC;
            if (table_p->ta_data_align == 0)
                data_copy_p = ENTRY_DATA_BUF(table_p, entry_p);
            else
                data_copy_p = entry_data_buf(table_p, entry_p);
            memcpy(*data_buf_p, data_copy_p, entry_p->te_data_size);
        }
    }
    if (data_size_p != NULL)
        *data_size_p = entry_p->te_data_size;
    table_p->ta_free(table_p->opt_param, entry_p);
    entry_p = NULL;

    table_p->ta_entry_n--;

    /* do we need auto-adjust down? */
    if ((table_p->ta_flags & TABLE_FLAG_AUTO_ADJUST)
        && (table_p->ta_flags & TABLE_FLAG_ADJUST_DOWN)
        && SHOULD_TABLE_SHRINK(table_p))
        return table_adjust(table_p, table_p->ta_entry_n);
    return TABLE_ERROR_NONE;
}

/*
 * int table_delete_first
 *
 * DESCRIPTION:
 *
 * This is like the table_delete routines except it deletes the first
 * key/data pair in the table instead of an entry corresponding to a
 * particular key.  The associated key and data information can be
 * passed back to the user if requested.  This routines is handy to
 * clear out a table.
 *
 * RETURNS:
 *
 * Success - TABLE_ERROR_NONE
 *
 * Failure - Table error code.
 *
 * NOTE: this could be an allocation error if the library is to return
 * the data to the user.
 *
 * ARGUMENTS:
 *
 * table_p - Table structure pointer from which we will be deleteing
 * the first key.
 *
 * key_buf_p - Pointer which, if not NULL, will be set to the address
 * of the storage of the first key that was allocated in the table.
 * If an (int) was stored as the first key (for example) then
 * key_buf_p should be (int **) i.e. the address of a (int *).  If a
 * pointer is passed in, the caller is responsible for freeing it
 * after use.  If key_buf_p is NULL then the library will free up the
 * key allocation itself.
 *
 * key_size_p - Pointer to an integer which, if not NULL, will be set
 * to the size of the key that was stored in the table and that was
 * associated with the key.
 *
 * data_buf_p - Pointer which, if not NULL, will be set to the address
 * of the data storage that was allocated in the table and that was
 * associated with the key.  If a (long) was stored as the data (for
 * example) then data_buf_p should be (long **) i.e. the address of a
 * (long *).  If a pointer is passed in, the caller is responsible for
 * freeing it after use.  If data_buf_p is NULL then the library will
 * free up the data allocation itself.
 *
 * data_size_p - Pointer to an integer which, if not NULL, will be set
 * to the size of the data that was stored in the table and that was
 * associated with the key.
 */
int table_delete_first(table_t * table_p,
                       void **key_buf_p, int *key_size_p,
                       void **data_buf_p, int *data_size_p)
{
    unsigned char *data_copy_p;
    table_entry_t *entry_p;
    table_linear_t linear;

    if (table_p == NULL)
        return TABLE_ERROR_ARG_NULL;
    if (table_p->ta_magic != TABLE_MAGIC)
        return TABLE_ERROR_PNT;
    /* take the first entry */
    entry_p = first_entry(table_p, &linear);
    if (entry_p == NULL)
        return TABLE_ERROR_NOT_FOUND;
    /*
     * NOTE: we may want to adjust the linear counters here if the entry
     * we are deleting is the one we are pointing on or is ahead of the
     * one in the bucket list
     */

    /* remove entry from the linked list */
    table_p->ta_buckets[linear.tl_bucket_c] = entry_p->te_next_p;

    /* free entry */
    if (key_buf_p != NULL) {
        if (entry_p->te_key_size == 0)
            *key_buf_p = NULL;
        else {
            /*
             * if we were storing it compacted, we now need to malloc some
             * space if the user wants the value after the delete.
             */
            *key_buf_p = table_p->ta_malloc(table_p->opt_param,
                                            entry_p->te_key_size);
            if (*key_buf_p == NULL)
                return TABLE_ERROR_ALLOC;
            memcpy(*key_buf_p, ENTRY_KEY_BUF(entry_p), entry_p->te_key_size);
        }
    }
    if (key_size_p != NULL)
        *key_size_p = entry_p->te_key_size;
    if (data_buf_p != NULL) {
        if (entry_p->te_data_size == 0)
            *data_buf_p = NULL;
        else {
            /*
             * if we were storing it compacted, we now need to malloc some
             * space if the user wants the value after the delete.
             */
            *data_buf_p = table_p->ta_malloc(table_p->opt_param,
                                             entry_p->te_data_size);
            if (*data_buf_p == NULL)
                return TABLE_ERROR_ALLOC;
            if (table_p->ta_data_align == 0)
                data_copy_p = ENTRY_DATA_BUF(table_p, entry_p);
            else
                data_copy_p = entry_data_buf(table_p, entry_p);
            memcpy(*data_buf_p, data_copy_p, entry_p->te_data_size);
        }
    }
    if (data_size_p != NULL)
        *data_size_p = entry_p->te_data_size;
    table_p->ta_free(table_p->opt_param, entry_p);

    table_p->ta_entry_n--;

    /* do we need auto-adjust down? */
    if ((table_p->ta_flags & TABLE_FLAG_AUTO_ADJUST)
        && (table_p->ta_flags & TABLE_FLAG_ADJUST_DOWN)
        && SHOULD_TABLE_SHRINK(table_p))
        return table_adjust(table_p, table_p->ta_entry_n);
    return TABLE_ERROR_NONE;
}

/*
 * int table_info
 *
 * DESCRIPTION:
 *
 * Get some information about a table_p structure.
 *
 * RETURNS:
 *
 * Success - TABLE_ERROR_NONE
 *
 * Failure - Table error code.
 *
 * ARGUMENTS:
 *
 * table_p - Table structure pointer from which we are getting
 * information.
 *
 * num_buckets_p - Pointer to an integer which, if not NULL, will
 * contain the number of buckets in the table.
 *
 * num_entries_p - Pointer to an integer which, if not NULL, will
 * contain the number of entries stored in the table.
 */
int table_info(table_t * table_p, int *num_buckets_p, int *num_entries_p)
{
    if (table_p == NULL)
        return TABLE_ERROR_ARG_NULL;
    if (table_p->ta_magic != TABLE_MAGIC)
        return TABLE_ERROR_PNT;
    if (num_buckets_p != NULL)
        *num_buckets_p = table_p->ta_bucket_n;
    if (num_entries_p != NULL)
        *num_entries_p = table_p->ta_entry_n;
    return TABLE_ERROR_NONE;
}

/*
 * int table_adjust
 *
 * DESCRIPTION:
 *
 * Set the number of buckets in a table to a certain value.
 *
 * RETURNS:
 *
 * Success - TABLE_ERROR_NONE
 *
 * Failure - Table error code.
 *
 * ARGUMENTS:
 *
 * table_p - Table structure pointer of which we are adjusting.
 *
 * bucket_n - Number buckets to adjust the table to.  Set to 0 to
 * adjust the table to its number of entries.
 */
int table_adjust(table_t * table_p, const int bucket_n)
{
    table_entry_t *entry_p, *next_p;
    table_entry_t **buckets, **bucket_p, **bounds_p;
    int bucket;
    unsigned int buck_n;

    if (table_p == NULL)
        return TABLE_ERROR_ARG_NULL;
    if (table_p->ta_magic != TABLE_MAGIC)
        return TABLE_ERROR_PNT;
    /*
     * NOTE: we walk through the entries and rehash them.  If we stored
     * the hash value as a full int in the table-entry, all we would
     * have to do is remod it.
     */

    /* normalize to the number of entries */
    if (bucket_n == 0)
        buck_n = table_p->ta_entry_n;
    else
        buck_n = bucket_n;
    /* we must have at least 1 bucket */
    if (buck_n == 0)
        buck_n = 1;
    /* make sure we have somethign to do */
    if (buck_n <= table_p->ta_bucket_n)
        return TABLE_ERROR_NONE;
    /* allocate a new bucket list */
    buckets = (table_entry_t **)
               table_p->ta_calloc(table_p->opt_param,
                                  buck_n, sizeof(table_entry_t *));
    if (table_p->ta_buckets == NULL)
        return TABLE_ERROR_ALLOC;
    /*
     * run through each of the items in the current table and rehash
     * them into the newest bucket sizes
     */
    bounds_p = table_p->ta_buckets + table_p->ta_bucket_n;
    for (bucket_p = table_p->ta_buckets; bucket_p < bounds_p; bucket_p++) {
        for (entry_p = *bucket_p; entry_p != NULL; entry_p = next_p) {

            /* hash the old data into the new table size */
            bucket = hash(ENTRY_KEY_BUF(entry_p), entry_p->te_key_size, 0) % buck_n;

            /* record the next one now since we overwrite next below */
            next_p = entry_p->te_next_p;

            /* insert into new list, no need to append */
            entry_p->te_next_p = buckets[bucket];
            buckets[bucket] = entry_p;

            /*
             * NOTE: we may want to adjust the bucket_c linear entry here to
             * keep it current
             */
        }
        /* remove the old table pointers as we go by */
        *bucket_p = NULL;
    }

    /* replace the table buckets with the new ones */
    table_p->ta_free(table_p->opt_param, table_p->ta_buckets);
    table_p->ta_buckets = buckets;
    table_p->ta_bucket_n = buck_n;

    return TABLE_ERROR_NONE;
}

/*
 * const char *table_strerror
 *
 * DESCRIPTION:
 *
 * Return the corresponding string for the error number.
 *
 * RETURNS:
 *
 * Success - String equivalient of the error.
 *
 * Failure - String "invalid error code"
 *
 * ARGUMENTS:
 *
 * error - Error number that we are converting.
 */
const char *table_strerror(const int error)
{
    error_str_t *err_p;

    for (err_p = errors; err_p->es_error != 0; err_p++) {
        if (err_p->es_error == error)
            return err_p->es_string;
    }

    return INVALID_ERROR;
}

/*
 * int table_type_size
 *
 * DESCRIPTION:
 *
 * Return the size of the internal table type.
 *
 * RETURNS:
 *
 * The size of the table_t type.
 *
 * ARGUMENTS:
 *
 * None.
 */
int table_type_size(void)
{
    return sizeof(table_t);
}

/************************* linear access routines ****************************/

/*
 * int table_first
 *
 * DESCRIPTION:
 *
 * Find first element in a table and pass back information about the
 * key/data pair.  If any of the key/data pointers are NULL then they
 * are ignored.
 *
 * NOTE: This function is not reentrant.  More than one thread cannot
 * be doing a first and next on the same table at the same time.  Use
 * the table_first_r version below for this.
 *
 * RETURNS:
 *
 * Success - TABLE_ERROR_NONE
 *
 * Failure - Table error code.
 *
 * ARGUMENTS:
 *
 * table_p - Table structure pointer from which we are getting the
 * first element.
 *
 * key_buf_p - Pointer which, if not NULL, will be set to the address
 * of the storage of the first key that is allocated in the table.  If
 * an (int) is stored as the first key (for example) then key_buf_p
 * should be (int **) i.e. the address of a (int *).
 *
 * key_size_p - Pointer to an integer which, if not NULL, will be set
 * to the size of the key that is stored in the table and that is
 * associated with the first key.
 *
 * data_buf_p - Pointer which, if not NULL, will be set to the address
 * of the data storage that is allocated in the table and that is
 * associated with the first key.  If a (long) is stored as the data
 * (for example) then data_buf_p should be (long **) i.e. the address
 * of a (long *).
 *
 * data_size_p - Pointer to an integer which, if not NULL, will be set
 * to the size of the data that is stored in the table and that is
 * associated with the first key.
 */
int table_first(table_t * table_p,
                void **key_buf_p, int *key_size_p,
                void **data_buf_p, int *data_size_p)
{
    table_entry_t *entry_p;

    if (table_p == NULL)
        return TABLE_ERROR_ARG_NULL;
    if (table_p->ta_magic != TABLE_MAGIC)
        return TABLE_ERROR_PNT;
    /* initialize our linear magic number */
    table_p->ta_linear.tl_magic = LINEAR_MAGIC;

    entry_p = first_entry(table_p, &table_p->ta_linear);
    if (entry_p == NULL)
        return TABLE_ERROR_NOT_FOUND;
    if (key_buf_p != NULL)
        *key_buf_p = ENTRY_KEY_BUF(entry_p);
    if (key_size_p != NULL)
        *key_size_p = entry_p->te_key_size;
    if (data_buf_p != NULL) {
        if (entry_p->te_data_size == 0)
            *data_buf_p = NULL;
        else {
            if (table_p->ta_data_align == 0)
                *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
            else
                *data_buf_p = entry_data_buf(table_p, entry_p);
        }
    }
    if (data_size_p != NULL)
        *data_size_p = entry_p->te_data_size;
    return TABLE_ERROR_NONE;
}

/*
 * int table_next
 *
 * DESCRIPTION:
 *
 * Find the next element in a table and pass back information about
 * the key/data pair.  If any of the key/data pointers are NULL then
 * they are ignored.
 *
 * NOTE: This function is not reentrant.  More than one thread cannot
 * be doing a first and next on the same table at the same time.  Use
 * the table_next_r version below for this.
 *
 * RETURNS:
 *
 * Success - TABLE_ERROR_NONE
 *
 * Failure - Table error code.
 *
 * ARGUMENTS:
 *
 * table_p - Table structure pointer from which we are getting the
 * next element.
 *
 * key_buf_p - Pointer which, if not NULL, will be set to the address
 * of the storage of the next key that is allocated in the table.  If
 * an (int) is stored as the next key (for example) then key_buf_p
 * should be (int **) i.e. the address of a (int *).
 *
 * key_size_p - Pointer to an integer which, if not NULL, will be set
 * to the size of the key that is stored in the table and that is
 * associated with the next key.
 *
 * data_buf_p - Pointer which, if not NULL, will be set to the address
 * of the data storage that is allocated in the table and that is
 * associated with the next key.  If a (long) is stored as the data
 * (for example) then data_buf_p should be (long **) i.e. the address
 * of a (long *).
 *
 * data_size_p - Pointer to an integer which, if not NULL, will be set
 * to the size of the data that is stored in the table and that is
 * associated with the next key.
 */
int table_next(table_t * table_p,
               void **key_buf_p, int *key_size_p,
               void **data_buf_p, int *data_size_p)
{
    table_entry_t *entry_p;
    int error;

    if (table_p == NULL)
        return TABLE_ERROR_ARG_NULL;
    if (table_p->ta_magic != TABLE_MAGIC)
        return TABLE_ERROR_PNT;
    if (table_p->ta_linear.tl_magic != LINEAR_MAGIC)
        return TABLE_ERROR_LINEAR;
    /* move to the next entry */
    entry_p = next_entry(table_p, &table_p->ta_linear, &error);
    if (entry_p == NULL)
        return error;
    if (key_buf_p != NULL)
        *key_buf_p = ENTRY_KEY_BUF(entry_p);
    if (key_size_p != NULL)
        *key_size_p = entry_p->te_key_size;
    if (data_buf_p != NULL) {
        if (entry_p->te_data_size == 0)
            *data_buf_p = NULL;
        else {
            if (table_p->ta_data_align == 0)
                *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
            else
                *data_buf_p = entry_data_buf(table_p, entry_p);
        }
    }
    if (data_size_p != NULL)
        *data_size_p = entry_p->te_data_size;
    return TABLE_ERROR_NONE;
}

/*
 * int table_this
 *
 * DESCRIPTION:
 *
 * Find the current element in a table and pass back information about
 * the key/data pair.  If any of the key/data pointers are NULL then
 * they are ignored.
 *
 * NOTE: This function is not reentrant.  Use the table_current_r
 * version below.
 *
 * RETURNS:
 *
 * Success - TABLE_ERROR_NONE
 *
 * Failure - Table error code.
 *
 * ARGUMENTS:
 *
 * table_p - Table structure pointer from which we are getting the
 * current element.
 *
 * key_buf_p - Pointer which, if not NULL, will be set to the address
 * of the storage of the current key that is allocated in the table.
 * If an (int) is stored as the current key (for example) then
 * key_buf_p should be (int **) i.e. the address of a (int *).
 *
 * key_size_p - Pointer to an integer which, if not NULL, will be set
 * to the size of the key that is stored in the table and that is
 * associated with the current key.
 *
 * data_buf_p - Pointer which, if not NULL, will be set to the address
 * of the data storage that is allocated in the table and that is
 * associated with the current key.  If a (long) is stored as the data
 * (for example) then data_buf_p should be (long **) i.e. the address
 * of a (long *).
 *
 * data_size_p - Pointer to an integer which, if not NULL, will be set
 * to the size of the data that is stored in the table and that is
 * associated with the current key.
 */
int table_this(table_t * table_p,
               void **key_buf_p, int *key_size_p,
               void **data_buf_p, int *data_size_p)
{
    table_entry_t *entry_p = NULL;
    int entry_c;

    if (table_p == NULL)
        return TABLE_ERROR_ARG_NULL;
    if (table_p->ta_magic != TABLE_MAGIC)
        return TABLE_ERROR_PNT;
    if (table_p->ta_linear.tl_magic != LINEAR_MAGIC)
        return TABLE_ERROR_LINEAR;
    /* if we removed an item that shorted the bucket list, we may get this */
    if (table_p->ta_linear.tl_bucket_c >= table_p->ta_bucket_n) {
        /*
         * NOTE: this might happen if we delete an item which shortens the
         * table bucket numbers.
         */
        return TABLE_ERROR_NOT_FOUND;
    }

    /* find the entry which is the nth in the list */
    entry_p = table_p->ta_buckets[table_p->ta_linear.tl_bucket_c];
    /* NOTE: we swap the order here to be more efficient */
    for (entry_c = table_p->ta_linear.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;
    }

    /* is this a NOT_FOUND or a LINEAR error */
    if (entry_p == NULL)
        return TABLE_ERROR_NOT_FOUND;
    if (key_buf_p != NULL)
        *key_buf_p = ENTRY_KEY_BUF(entry_p);
    if (key_size_p != NULL)
        *key_size_p = entry_p->te_key_size;
    if (data_buf_p != NULL) {
        if (entry_p->te_data_size == 0)
            *data_buf_p = NULL;
        else {
            if (table_p->ta_data_align == 0)
                *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
            else
                *data_buf_p = entry_data_buf(table_p, entry_p);
        }
    }
    if (data_size_p != NULL)
        *data_size_p = entry_p->te_data_size;
    return TABLE_ERROR_NONE;
}

/*
 * int table_first_r
 *
 * DESCRIPTION:
 *
 * Reetrant version of the table_first routine above.  Find first
 * element in a table and pass back information about the key/data
 * pair.  If any of the key/data pointers are NULL then they are
 * ignored.
 *
 * RETURNS:
 *
 * Success - TABLE_ERROR_NONE
 *
 * Failure - Table error code.
 *
 * ARGUMENTS:
 *
 * table_p - Table structure pointer from which we are getting the
 * first element.
 *
 * linear_p - Pointer to a table linear structure which is initialized
 * here.  The same pointer should then be passed to table_next_r
 * below.
 *
 * key_buf_p - Pointer which, if not NULL, will be set to the address
 * of the storage of the first key that is allocated in the table.  If
 * an (int) is stored as the first key (for example) then key_buf_p
 * should be (int **) i.e. the address of a (int *).
 *
 * key_size_p - Pointer to an integer which, if not NULL, will be set
 * to the size of the key that is stored in the table and that is
 * associated with the first key.
 *
 * data_buf_p - Pointer which, if not NULL, will be set to the address
 * of the data storage that is allocated in the table and that is
 * associated with the first key.  If a (long) is stored as the data
 * (for example) then data_buf_p should be (long **) i.e. the address
 * of a (long *).
 *
 * data_size_p - Pointer to an integer which, if not NULL, will be set
 * to the size of the data that is stored in the table and that is
 * associated with the first key.
 */
int table_first_r(table_t * table_p, table_linear_t * linear_p,
                  void **key_buf_p, int *key_size_p,
                  void **data_buf_p, int *data_size_p)
{
    table_entry_t *entry_p;

    if (table_p == NULL)
        return TABLE_ERROR_ARG_NULL;
    if (table_p->ta_magic != TABLE_MAGIC)
        return TABLE_ERROR_PNT;
    if (linear_p == NULL)
        return TABLE_ERROR_ARG_NULL;
    /* initialize our linear magic number */
    linear_p->tl_magic = LINEAR_MAGIC;

    entry_p = first_entry(table_p, linear_p);
    if (entry_p == NULL)
        return TABLE_ERROR_NOT_FOUND;
    if (key_buf_p != NULL)
        *key_buf_p = ENTRY_KEY_BUF(entry_p);
    if (key_size_p != NULL)
        *key_size_p = entry_p->te_key_size;
    if (data_buf_p != NULL) {
        if (entry_p->te_data_size == 0)
            *data_buf_p = NULL;
        else {
            if (table_p->ta_data_align == 0)
                *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
            else
                *data_buf_p = entry_data_buf(table_p, entry_p);
        }
    }
    if (data_size_p != NULL)
        *data_size_p = entry_p->te_data_size;
    return TABLE_ERROR_NONE;
}

/*
 * int table_next_r
 *
 * DESCRIPTION:
 *
 * Reetrant version of the table_next routine above.  Find next
 * element in a table and pass back information about the key/data
 * pair.  If any of the key/data pointers are NULL then they are
 * ignored.
 *
 * RETURNS:
 *
 * Success - TABLE_ERROR_NONE
 *
 * Failure - Table error code.
 *
 * ARGUMENTS:
 *
 * table_p - Table structure pointer from which we are getting the
 * next element.
 *
 * linear_p - Pointer to a table linear structure which is incremented
 * here.  The same pointer must have been passed to table_first_r
 * first so that it can be initialized.
 *
 * key_buf_p - Pointer which, if not NULL, will be set to the address
 * of the storage of the next key that is allocated in the table.  If
 * an (int) is stored as the next key (for example) then key_buf_p
 * should be (int **) i.e. the address of a (int *).
 *
 * key_size_p - Pointer to an integer which, if not NULL will be set
 * to the size of the key that is stored in the table and that is
 * associated with the next key.
 *
 * data_buf_p - Pointer which, if not NULL, will be set to the address
 * of the data storage that is allocated in the table and that is
 * associated with the next key.  If a (long) is stored as the data
 * (for example) then data_buf_p should be (long **) i.e. the address
 * of a (long *).
 *
 * data_size_p - Pointer to an integer which, if not NULL, will be set
 * to the size of the data that is stored in the table and that is
 * associated with the next key.
 */
int table_next_r(table_t * table_p, table_linear_t * linear_p,
                 void **key_buf_p, int *key_size_p,
                 void **data_buf_p, int *data_size_p)
{
    table_entry_t *entry_p;
    int error;

    if (table_p == NULL)
        return TABLE_ERROR_ARG_NULL;
    if (table_p->ta_magic != TABLE_MAGIC)
        return TABLE_ERROR_PNT;
    if (linear_p == NULL)
        return TABLE_ERROR_ARG_NULL;
    if (linear_p->tl_magic != LINEAR_MAGIC)
        return TABLE_ERROR_LINEAR;
    /* move to the next entry */
    entry_p = next_entry(table_p, linear_p, &error);
    if (entry_p == NULL)
        return error;
    if (key_buf_p != NULL)
        *key_buf_p = ENTRY_KEY_BUF(entry_p);
    if (key_size_p != NULL)
        *key_size_p = entry_p->te_key_size;
    if (data_buf_p != NULL) {
        if (entry_p->te_data_size == 0)
            *data_buf_p = NULL;
        else {
            if (table_p->ta_data_align == 0)
                *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
            else
                *data_buf_p = entry_data_buf(table_p, entry_p);
        }
    }
    if (data_size_p != NULL)
        *data_size_p = entry_p->te_data_size;
    return TABLE_ERROR_NONE;
}

/*
 * int table_this_r
 *
 * DESCRIPTION:
 *
 * Reetrant version of the table_this routine above.  Find current
 * element in a table and pass back information about the key/data
 * pair.  If any of the key/data pointers are NULL then they are
 * ignored.
 *
 * RETURNS:
 *
 * Success - TABLE_ERROR_NONE
 *
 * Failure - Table error code.
 *
 * ARGUMENTS:
 *
 * table_p - Table structure pointer from which we are getting the
 * current element.
 *
 * linear_p - Pointer to a table linear structure which is accessed
 * here.  The same pointer must have been passed to table_first_r
 * first so that it can be initialized.
 *
 * key_buf_p - Pointer which, if not NULL, will be set to the address
 * of the storage of the current key that is allocated in the table.
 * If an (int) is stored as the current key (for example) then
 * key_buf_p should be (int **) i.e. the address of a (int *).
 *
 * key_size_p - Pointer to an integer which, if not NULL, will be set
 * to the size of the key that is stored in the table and that is
 * associated with the current key.
 *
 * data_buf_p - Pointer which, if not NULL, will be set to the address
 * of the data storage that is allocated in the table and that is
 * associated with the current key.  If a (long) is stored as the data
 * (for example) then data_buf_p should be (long **) i.e. the address
 * of a (long *).
 *
 * data_size_p - Pointer to an integer which, if not NULL, will be set
 * to the size of the data that is stored in the table and that is
 * associated with the current key.
 */
int table_this_r(table_t * table_p, table_linear_t * linear_p,
                 void **key_buf_p, int *key_size_p,
                 void **data_buf_p, int *data_size_p)
{
    table_entry_t *entry_p;
    int entry_c;

    if (table_p == NULL)
        return TABLE_ERROR_ARG_NULL;
    if (table_p->ta_magic != TABLE_MAGIC)
        return TABLE_ERROR_PNT;
    if (linear_p->tl_magic != LINEAR_MAGIC)
        return TABLE_ERROR_LINEAR;
    /* if we removed an item that shorted the bucket list, we may get this */
    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.
         */
        return TABLE_ERROR_NOT_FOUND;
    }

    /* find the entry which is the nth in the list */
    for (entry_c = linear_p->tl_entry_c,
         entry_p = table_p->ta_buckets[linear_p->tl_bucket_c];
         entry_p != NULL && entry_c > 0;
         entry_c--, entry_p = TABLE_POINTER(table_p, table_entry_t *,
                                            entry_p)->te_next_p) {
    }

    if (entry_p == NULL)
        return TABLE_ERROR_NOT_FOUND;
    if (key_buf_p != NULL)
        *key_buf_p = ENTRY_KEY_BUF(entry_p);
    if (key_size_p != NULL)
        *key_size_p = entry_p->te_key_size;
    if (data_buf_p != NULL) {
        if (entry_p->te_data_size == 0)
            *data_buf_p = NULL;
        else {
            if (table_p->ta_data_align == 0)
                *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
            else
                *data_buf_p = entry_data_buf(table_p, entry_p);
        }
    }
    if (data_size_p != NULL)
        *data_size_p = entry_p->te_data_size;
    return TABLE_ERROR_NONE;
}

/******************************** table order ********************************/

/*
 * table_entry_t *table_order
 *
 * DESCRIPTION:
 *
 * Order a table by building an array of table entry pointers and then
 * sorting this array using the qsort function.  To retrieve the
 * sorted entries, you can then use the table_entry routine to access
 * each entry in order.
 *
 * NOTE: This routine is now thread safe in that two table_order calls
 * can now happen at the same time, even on the same table.
 *
 * RETURNS:
 *
 * An allocated list of entry pointers which must be freed later.
 * Returns null on error.
 *
 * ARGUMENTS:
 *
 * table_p - Pointer to the table that we are ordering.
 *
 * compare - Comparison function defined by the user.  Its definition
 * is at the top of the table.h file.  If this is NULL then it will
 * order the table my memcmp-ing the keys.
 *
 * num_entries_p - Pointer to an integer which, if not NULL, will
 * contain the number of entries in the returned entry pointer array.
 *
 * error_p - Pointer to an integer which, if not NULL, will contain a
 * table error code.
 */
table_entry_t **table_order(table_t * table_p, table_compare_t compare,
                            int *num_entries_p, int *error_p)
{
    table_entry_t *entry_p, **entries, **entries_p;
    table_linear_t linear;
    compare_t comp_func;
    int error;

    if (table_p == NULL) {
        if (error_p != NULL)
            *error_p = TABLE_ERROR_ARG_NULL;
        return NULL;
    }
    if (table_p->ta_magic != TABLE_MAGIC) {
        if (error_p != NULL)
            *error_p = TABLE_ERROR_PNT;
        return NULL;
    }

    /* there must be at least 1 element in the table for this to work */
    if (table_p->ta_entry_n == 0) {
        if (error_p != NULL)
            *error_p = TABLE_ERROR_EMPTY;
        return NULL;
    }

    entries = (table_entry_t **)
               table_p->ta_malloc(table_p->opt_param,
                                  table_p->ta_entry_n *sizeof(table_entry_t *));
    if (entries == NULL) {
        if (error_p != NULL)
            *error_p = TABLE_ERROR_ALLOC;
        return NULL;
    }

    /* get a pointer to all entries */
    entry_p = first_entry(table_p, &linear);
    if (entry_p == NULL) {
        if (error_p != NULL)
            *error_p = TABLE_ERROR_NOT_FOUND;
        return NULL;
    }

    /* add all of the entries to the array */
    for (entries_p = entries;
         entry_p != NULL;
         entry_p = next_entry(table_p, &linear, &error))
        *entries_p++ = entry_p;
    if (error != TABLE_ERROR_NOT_FOUND) {
        if (error_p != NULL)
            *error_p = error;
        return NULL;
    }

    if (compare == NULL) {
        /* this is regardless of the alignment */
        comp_func = local_compare;
    }
    else if (table_p->ta_data_align == 0)
        comp_func = external_compare;
    else
        comp_func = external_compare_align;
    /* now qsort the entire entries array from first to last element */
    split(entries, entries + table_p->ta_entry_n - 1, comp_func, compare,
          table_p);

    if (num_entries_p != NULL)
        *num_entries_p = table_p->ta_entry_n;
    if (error_p != NULL)
        *error_p = TABLE_ERROR_NONE;
    return entries;
}

/*
 * int table_entry
 *
 * DESCRIPTION:
 *
 * Get information about an element.  The element is one from the
 * array returned by the table_order function.  If any of the key/data
 * pointers are NULL then they are ignored.
 *
 * RETURNS:
 *
 * Success - TABLE_ERROR_NONE
 *
 * Failure - Table error code.
 *
 * ARGUMENTS:
 *
 * table_p - Table structure pointer from which we are getting the
 * element.
 *
 * entry_p - Pointer to a table entry from the array returned by the
 * table_order function.
 *
 * key_buf_p - Pointer which, if not NULL, will be set to the address
 * of the storage of this entry that is allocated in the table.  If an
 * (int) is stored as this entry (for example) then key_buf_p should
 * be (int **) i.e. the address of a (int *).
 *
 * key_size_p - Pointer to an integer which, if not NULL, will be set
 * to the size of the key that is stored in the table.
 *
 * data_buf_p - Pointer which, if not NULL, will be set to the address
 * of the data storage of this entry that is allocated in the table.
 * If a (long) is stored as this entry data (for example) then
 * data_buf_p should be (long **) i.e. the address of a (long *).
 *
 * data_size_p - Pointer to an integer which, if not NULL, will be set
 * to the size of the data that is stored in the table.
 */
int table_entry_info(table_t * table_p, table_entry_t * entry_p,
                void **key_buf_p, int *key_size_p,
                void **data_buf_p, int *data_size_p)
{
    if (table_p == NULL)
        return TABLE_ERROR_ARG_NULL;
    if (table_p->ta_magic != TABLE_MAGIC)
        return TABLE_ERROR_PNT;
    if (entry_p == NULL)
        return TABLE_ERROR_ARG_NULL;
    if (key_buf_p != NULL)
        *key_buf_p = ENTRY_KEY_BUF(entry_p);
    if (key_size_p != NULL)
        *key_size_p = entry_p->te_key_size;
    if (data_buf_p != NULL) {
        if (entry_p->te_data_size == 0)
            *data_buf_p = NULL;
        else {
            if (table_p->ta_data_align == 0)
                *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
            else
                *data_buf_p = entry_data_buf(table_p, entry_p);
        }
    }
    if (data_size_p != NULL)
        *data_size_p = entry_p->te_data_size;
    return TABLE_ERROR_NONE;
}