| /* _ _ |
| ** _ __ ___ ___ __| | ___ ___| | mod_ssl |
| ** | '_ ` _ \ / _ \ / _` | / __/ __| | Apache Interface to OpenSSL |
| ** | | | | | | (_) | (_| | \__ \__ \ | www.modssl.org |
| ** |_| |_| |_|\___/ \__,_|___|___/___/_| ftp.modssl.org |
| ** |_____| |
| ** ssl_util_table.c |
| ** High Performance Hash Table Functions |
| */ |
| |
| /* ==================================================================== |
| * The Apache Software License, Version 1.1 |
| * |
| * Copyright (c) 2000-2002 The Apache Software Foundation. All rights |
| * reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in |
| * the documentation and/or other materials provided with the |
| * distribution. |
| * |
| * 3. The end-user documentation included with the redistribution, |
| * if any, must include the following acknowledgment: |
| * "This product includes software developed by the |
| * Apache Software Foundation (http://www.apache.org/)." |
| * Alternately, this acknowledgment may appear in the software itself, |
| * if and wherever such third-party acknowledgments normally appear. |
| * |
| * 4. The names "Apache" and "Apache Software Foundation" must |
| * not be used to endorse or promote products derived from this |
| * software without prior written permission. For written |
| * permission, please contact apache@apache.org. |
| * |
| * 5. Products derived from this software may not be called "Apache", |
| * nor may "Apache" appear in their name, without prior written |
| * permission of the Apache Software Foundation. |
| * |
| * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED |
| * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
| * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE |
| * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR |
| * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF |
| * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND |
| * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, |
| * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT |
| * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
| * SUCH DAMAGE. |
| * ==================================================================== |
| */ |
| |
| /* |
| * Generic hash table handler |
| * Table 4.1.0 July-28-1998 |
| * |
| * This library is a generic open hash table with buckets and |
| * linked lists. It is pretty high performance. Each element |
| * has a key and a data. The user indexes on the key to find the |
| * data. |
| * |
| * Copyright 1998 by Gray Watson <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) |
| { |
| #if 0 |
| table_entry_t *entry_p, *next_p; |
| #endif |
| 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++) { |
| #if 0 |
| 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); |
| } |
| #endif |
| /* 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; |
| } |
| |