summaryrefslogtreecommitdiffstats
path: root/rubbos/app/httpd-2.0.64/modules/ssl/ssl_util_table.c
diff options
context:
space:
mode:
authorhongbotian <hongbo.tianhongbo@huawei.com>2015-11-30 01:45:08 -0500
committerhongbotian <hongbo.tianhongbo@huawei.com>2015-11-30 01:45:08 -0500
commite8ec7aa8e38a93f5b034ac74cebce5de23710317 (patch)
treeaa031937bf856c1f8d6ad7877b8d2cb0224da5ef /rubbos/app/httpd-2.0.64/modules/ssl/ssl_util_table.c
parentcc40af334e619bb549038238507407866f774f8f (diff)
upload http
JIRA: BOTTLENECK-10 Change-Id: I7598427ff904df438ce77c2819ee48ac75ffa8da Signed-off-by: hongbotian <hongbo.tianhongbo@huawei.com>
Diffstat (limited to 'rubbos/app/httpd-2.0.64/modules/ssl/ssl_util_table.c')
-rw-r--r--rubbos/app/httpd-2.0.64/modules/ssl/ssl_util_table.c2518
1 files changed, 2518 insertions, 0 deletions
diff --git a/rubbos/app/httpd-2.0.64/modules/ssl/ssl_util_table.c b/rubbos/app/httpd-2.0.64/modules/ssl/ssl_util_table.c
new file mode 100644
index 00000000..5eb98ec8
--- /dev/null
+++ b/rubbos/app/httpd-2.0.64/modules/ssl/ssl_util_table.c
@@ -0,0 +1,2518 @@
+/* Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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;
+}
+