2 ** _ __ ___ ___ __| | ___ ___| | mod_ssl
3 ** | '_ ` _ \ / _ \ / _` | / __/ __| | Apache Interface to OpenSSL
4 ** | | | | | | (_) | (_| | \__ \__ \ | www.modssl.org
5 ** |_| |_| |_|\___/ \__,_|___|___/___/_| ftp.modssl.org
8 ** High Performance Hash Table Functions
11 /* ====================================================================
12 * The Apache Software License, Version 1.1
14 * Copyright (c) 2000-2002 The Apache Software Foundation. All rights
17 * Redistribution and use in source and binary forms, with or without
18 * modification, are permitted provided that the following conditions
21 * 1. Redistributions of source code must retain the above copyright
22 * notice, this list of conditions and the following disclaimer.
24 * 2. Redistributions in binary form must reproduce the above copyright
25 * notice, this list of conditions and the following disclaimer in
26 * the documentation and/or other materials provided with the
29 * 3. The end-user documentation included with the redistribution,
30 * if any, must include the following acknowledgment:
31 * "This product includes software developed by the
32 * Apache Software Foundation (http://www.apache.org/)."
33 * Alternately, this acknowledgment may appear in the software itself,
34 * if and wherever such third-party acknowledgments normally appear.
36 * 4. The names "Apache" and "Apache Software Foundation" must
37 * not be used to endorse or promote products derived from this
38 * software without prior written permission. For written
39 * permission, please contact apache@apache.org.
41 * 5. Products derived from this software may not be called "Apache",
42 * nor may "Apache" appear in their name, without prior written
43 * permission of the Apache Software Foundation.
45 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
46 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
47 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
48 * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
49 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
50 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
51 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
52 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
53 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
54 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
55 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
57 * ====================================================================
61 * Generic hash table handler
62 * Table 4.1.0 July-28-1998
64 * This library is a generic open hash table with buckets and
65 * linked lists. It is pretty high performance. Each element
66 * has a key and a data. The user indexes on the key to find the
69 * Copyright 1998 by Gray Watson <gray@letters.com>
71 * Permission to use, copy, modify, and distribute this software for any
72 * purpose and without fee is hereby granted, provided that the above
73 * copyright notice and this permission notice appear in all copies,
74 * and that the name of Gray Watson not be used in advertising or
75 * publicity pertaining to distribution of the document or software
76 * without specific, written prior permission.
78 * Gray Watson makes no representations about the suitability of the
79 * software described herein for any purpose. It is provided "as is"
80 * without express or implied warranty.
82 * Modified in March 1999 by Ralf S. Engelschall <rse@engelschall.com>
83 * for use in the mod_ssl project:
84 * o merged table_loc.h header into table.c
85 * o removed fillproto-comments from table.h
86 * o removed mmap() support because it's too unportable
87 * o added support for MM library via ta_{malloc,calloc,realloc,free}
93 /* forward definitions for table.h */
94 typedef struct table_st table_t;
95 typedef struct table_entry_st table_entry_t;
98 #include "ssl_util_table.h"
101 /****************************** local defines ******************************/
104 #define BITSPERBYTE 8
107 #define BITS(type) (BITSPERBYTE * (int)sizeof(type))
110 #define TABLE_MAGIC 0xBADF00D /* very magic magicness */
111 #define LINEAR_MAGIC 0xAD00D00 /* magic value for linear struct */
112 #define DEFAULT_SIZE 1024 /* default table size */
113 #define MAX_ALIGNMENT 128 /* max alignment value */
114 #define MAX_SORT_SPLITS 128 /* qsort can handle 2^128 entries */
116 /* returns 1 when we should grow or shrink the table */
117 #define SHOULD_TABLE_GROW(tab) ((tab)->ta_entry_n > (tab)->ta_bucket_n * 2)
118 #define SHOULD_TABLE_SHRINK(tab) ((tab)->ta_entry_n < (tab)->ta_bucket_n / 2)
125 * Mix 3 32-bit values reversibly. For every delta with one or two bits
126 * set, and the deltas of all three high bits or all three low bits,
127 * whether the original value of a,b,c is almost all zero or is
128 * uniformly distributed.
130 * If HASH_MIX() is run forward or backward, at least 32 bits in a,b,c
131 * have at least 1/4 probability of changing. If mix() is run
132 * forward, every bit of c will change between 1/3 and 2/3 of the
133 * time. (Well, 22/100 and 78/100 for some 2-bit deltas.)
135 * HASH_MIX() takes 36 machine instructions, but only 18 cycles on a
136 * superscalar machine (like a Pentium or a Sparc). No faster mixer
137 * seems to work, that's the result of my brute-force search. There
138 * were about 2^68 hashes to choose from. I only tested about a
141 #define HASH_MIX(a, b, c) \
143 a -= b; a -= c; a ^= (c >> 13); \
144 b -= c; b -= a; b ^= (a << 8); \
145 c -= a; c -= b; c ^= (b >> 13); \
146 a -= b; a -= c; a ^= (c >> 12); \
147 b -= c; b -= a; b ^= (a << 16); \
148 c -= a; c -= b; c ^= (b >> 5); \
149 a -= b; a -= c; a ^= (c >> 3); \
150 b -= c; b -= a; b ^= (a << 10); \
151 c -= a; c -= b; c ^= (b >> 15); \
154 #define TABLE_POINTER(table, type, pnt) (pnt)
157 * Macros to get at the key and the data pointers
159 #define ENTRY_KEY_BUF(entry_p) ((entry_p)->te_key_buf)
160 #define ENTRY_DATA_BUF(tab_p, entry_p) \
161 (ENTRY_KEY_BUF(entry_p) + (entry_p)->te_key_size)
164 * Table structures...
168 * HACK: this should be equiv as the table_entry_t without the key_buf
169 * char. We use this with the ENTRY_SIZE() macro above which solves
170 * the problem with the lack of the [0] GNU hack. We use the
171 * table_entry_t structure to better map the memory and make things
174 typedef struct table_shell_st {
175 unsigned int te_key_size; /* size of data */
176 unsigned int te_data_size; /* size of data */
177 struct table_shell_st *te_next_p; /* pointer to next in the list */
178 /* NOTE: this does not have the te_key_buf field here */
182 * Elements in the bucket linked-lists. The key[1] is the start of
183 * the key with the rest of the key and all of the data information
184 * packed in memory directly after the end of this structure.
186 * NOTE: if this structure is changed, the table_shell_t must be changed
189 struct table_entry_st {
190 unsigned int te_key_size; /* size of data */
191 unsigned int te_data_size; /* size of data */
192 struct table_entry_st *te_next_p; /* pointer to next in the list */
193 unsigned char te_key_buf[1]; /* 1st byte of key buf */
196 /* external structure for debuggers be able to see void */
197 typedef table_entry_t table_entry_ext_t;
199 /* main table structure */
201 unsigned int ta_magic; /* magic number */
202 unsigned int ta_flags; /* table's flags defined in table.h */
203 unsigned int ta_bucket_n; /* num of buckets, should be 2^X */
204 unsigned int ta_entry_n; /* num of entries in all buckets */
205 unsigned int ta_data_align; /* data alignment value */
206 table_entry_t **ta_buckets; /* array of linked lists */
207 table_linear_t ta_linear; /* linear tracking */
208 unsigned long ta_file_size; /* size of on-disk space */
209 void *(*ta_malloc)(void *opt_param, size_t size);
210 void *(*ta_calloc)(void *opt_param, size_t number, size_t size);
211 void *(*ta_realloc)(void *opt_param, void *ptr, size_t size);
212 void (*ta_free)(void *opt_param, void *ptr);
216 /* external table structure for debuggers */
217 typedef table_t table_ext_t;
219 /* local comparison functions */
220 typedef int (*compare_t) (const void *element1_p, const void *element2_p,
221 table_compare_t user_compare,
222 const table_t * table_p);
225 * to map error to string
228 int es_error; /* error number */
229 char *es_string; /* assocaited string */
232 static error_str_t errors[] =
234 {TABLE_ERROR_NONE, "no error"},
235 {TABLE_ERROR_PNT, "invalid table pointer"},
236 {TABLE_ERROR_ARG_NULL, "buffer argument is null"},
237 {TABLE_ERROR_SIZE, "incorrect size argument"},
238 {TABLE_ERROR_OVERWRITE, "key exists and no overwrite"},
239 {TABLE_ERROR_NOT_FOUND, "key does not exist"},
240 {TABLE_ERROR_ALLOC, "error allocating memory"},
241 {TABLE_ERROR_LINEAR, "linear access not in progress"},
242 {TABLE_ERROR_OPEN, "could not open file"},
243 {TABLE_ERROR_SEEK, "could not seek to position in file"},
244 {TABLE_ERROR_READ, "could not read from file"},
245 {TABLE_ERROR_WRITE, "could not write to file"},
246 {TABLE_ERROR_EMPTY, "table is empty"},
247 {TABLE_ERROR_NOT_EMPTY, "table contains data"},
248 {TABLE_ERROR_ALIGNMENT, "invalid alignment value"},
252 #define INVALID_ERROR "invalid error code"
255 /********************** wrappers for system functions ************************/
256 static void *sys_malloc(void *param, size_t size)
261 static void *sys_calloc(void *param, size_t size1, size_t size2)
263 return calloc(size1, size2);
266 static void *sys_realloc(void *param, void *ptr, size_t size)
268 return realloc(ptr, size);
271 static void sys_free(void *param, void *ptr)
276 /****************************** local functions ******************************/
279 * static table_entry_t *first_entry
283 * Return the first entry in the table. It will set the linear
284 * structure counter to the position of the first entry.
288 * Success: A pointer to the first entry in the table.
290 * Failure: NULL if there is no first entry.
294 * table_p - Table whose next entry we are finding.
296 * linear_p - Pointer to a linear structure which we will advance and
297 * then find the corresponding entry.
299 static table_entry_t *first_entry(table_t * table_p,
300 table_linear_t * linear_p)
302 table_entry_t *entry_p;
303 unsigned int bucket_c = 0;
305 /* look for the first non-empty bucket */
306 for (bucket_c = 0; bucket_c < table_p->ta_bucket_n; bucket_c++) {
307 entry_p = table_p->ta_buckets[bucket_c];
308 if (entry_p != NULL) {
309 if (linear_p != NULL) {
310 linear_p->tl_bucket_c = bucket_c;
311 linear_p->tl_entry_c = 0;
313 return TABLE_POINTER(table_p, table_entry_t *, entry_p);
321 * static table_entry_t *next_entry
325 * Return the next entry in the table which is past the position in
326 * our linear pointer. It will advance the linear structure counters.
330 * Success: A pointer to the next entry in the table.
336 * table_p - Table whose next entry we are finding.
338 * linear_p - Pointer to a linear structure which we will advance and
339 * then find the corresponding entry.
341 * error_p - Pointer to an integer which when the routine returns will
342 * contain a table error code.
344 static table_entry_t *next_entry(table_t * table_p, table_linear_t * linear_p,
347 table_entry_t *entry_p;
350 /* can't next if we haven't first-ed */
351 if (linear_p == NULL) {
353 *error_p = TABLE_ERROR_LINEAR;
357 if (linear_p->tl_bucket_c >= table_p->ta_bucket_n) {
359 * NOTE: this might happen if we delete an item which shortens the
360 * table bucket numbers.
363 *error_p = TABLE_ERROR_NOT_FOUND;
367 linear_p->tl_entry_c++;
369 /* find the entry which is the nth in the list */
370 entry_p = table_p->ta_buckets[linear_p->tl_bucket_c];
371 /* NOTE: we swap the order here to be more efficient */
372 for (entry_c = linear_p->tl_entry_c; entry_c > 0; entry_c--) {
373 /* did we reach the end of the list? */
376 entry_p = TABLE_POINTER(table_p, table_entry_t *, entry_p)->te_next_p;
379 /* did we find an entry in the current bucket? */
380 if (entry_p != NULL) {
382 *error_p = TABLE_ERROR_NONE;
383 return TABLE_POINTER(table_p, table_entry_t *, entry_p);
386 /* find the first entry in the next non-empty bucket */
388 linear_p->tl_entry_c = 0;
389 for (linear_p->tl_bucket_c++; linear_p->tl_bucket_c < table_p->ta_bucket_n;
390 linear_p->tl_bucket_c++) {
391 entry_p = table_p->ta_buckets[linear_p->tl_bucket_c];
392 if (entry_p != NULL) {
394 *error_p = TABLE_ERROR_NONE;
395 return TABLE_POINTER(table_p, table_entry_t *, entry_p);
400 *error_p = TABLE_ERROR_NOT_FOUND;
405 * static unsigned int hash
409 * Hash a variable-length key into a 32-bit value. Every bit of the
410 * key affects every bit of the return value. Every 1-bit and 2-bit
411 * delta achieves avalanche. About (6 * len + 35) instructions. The
412 * best hash table sizes are powers of 2. There is no need to use mod
413 * (sooo slow!). If you need less than 32 bits, use a bitmask. For
414 * example, if you need only 10 bits, do h = (h & hashmask(10)); In
415 * which case, the hash table should have hashsize(10) elements.
417 * By Bob Jenkins, 1996. bob_jenkins@compuserve.com. You may use
418 * this code any way you wish, private, educational, or commercial.
420 * http://ourworld.compuserve.com/homepages/bob_jenkins/evahash.htm
421 * Use for hash table lookup, or anything where one collision in 2^^32
422 * is acceptable. Do NOT use for cryptographic purposes.
426 * Returns a 32-bit hash value.
430 * key - Key (the unaligned variable-length array of bytes) that we
433 * length - Length of the key in bytes.
435 * init_val - Initialization value of the hash if you need to hash a
436 * number of strings together. For instance, if you are hashing N
437 * strings (unsigned char **)keys, do it like this:
439 * for (i=0, h=0; i<N; ++i) h = hash( keys[i], len[i], h);
441 static unsigned int hash(const unsigned char *key,
442 const unsigned int length,
443 const unsigned int init_val)
445 const unsigned char *key_p = key;
446 unsigned int a, b, c, len;
448 /* set up the internal state */
449 a = 0x9e3779b9; /* the golden ratio; an arbitrary value */
451 c = init_val; /* the previous hash value */
453 /* handle most of the key */
454 for (len = length; len >= 12; len -= 12) {
456 + ((unsigned long) key_p[1] << 8)
457 + ((unsigned long) key_p[2] << 16)
458 + ((unsigned long) key_p[3] << 24));
460 + ((unsigned long) key_p[5] << 8)
461 + ((unsigned long) key_p[6] << 16)
462 + ((unsigned long) key_p[7] << 24));
464 + ((unsigned long) key_p[9] << 8)
465 + ((unsigned long) key_p[10] << 16)
466 + ((unsigned long) key_p[11] << 24));
473 /* all the case statements fall through to the next */
476 c += ((unsigned long) key_p[10] << 24);
478 c += ((unsigned long) key_p[9] << 16);
480 c += ((unsigned long) key_p[8] << 8);
481 /* the first byte of c is reserved for the length */
483 b += ((unsigned long) key_p[7] << 24);
485 b += ((unsigned long) key_p[6] << 16);
487 b += ((unsigned long) key_p[5] << 8);
491 a += ((unsigned long) key_p[3] << 24);
493 a += ((unsigned long) key_p[2] << 16);
495 a += ((unsigned long) key_p[1] << 8);
498 /* case 0: nothing left to add */
506 * static int entry_size
510 * Calculates the appropriate size of an entry to include the key and
511 * data sizes as well as any associated alignment to the data.
515 * The associated size of the entry.
519 * table_p - Table associated with the entries whose size we are
522 * key_size - Size of the entry key.
524 * data - Size of the entry data.
526 static int entry_size(const table_t * table_p, const unsigned int key_size,
527 const unsigned int data_size)
531 /* initial size -- key is already aligned if right after struct */
532 size = sizeof(struct table_shell_st) + key_size;
534 /* if there is no alignment then it is easy */
535 if (table_p->ta_data_align == 0)
536 return size + data_size;
537 /* add in our alignement */
538 left = size & (table_p->ta_data_align - 1);
540 size += table_p->ta_data_align - left;
541 /* we add the data size here after the alignment */
548 * static unsigned char *entry_data_buf
552 * Companion to the ENTRY_DATA_BUF macro but this handles any
553 * associated alignment to the data in the entry.
557 * Pointer to the data segment of the entry.
561 * table_p - Table associated with the entry.
563 * entry_p - Entry whose data pointer we are determining.
565 static unsigned char *entry_data_buf(const table_t * table_p,
566 const table_entry_t * entry_p)
568 const unsigned char *buf_p;
571 buf_p = entry_p->te_key_buf + entry_p->te_key_size;
573 /* if there is no alignment then it is easy */
574 if (table_p->ta_data_align == 0)
575 return (unsigned char *) buf_p;
576 /* we need the size of the space before the data */
577 size = sizeof(struct table_shell_st) + entry_p->te_key_size;
579 /* add in our alignment */
580 pad = size & (table_p->ta_data_align - 1);
582 pad = table_p->ta_data_align - pad;
583 return (unsigned char *) buf_p + pad;
586 /******************************* sort routines *******************************/
589 * static int our_compare
593 * Compare two entries by calling user's compare program or by using
598 * < 0, == 0, or > 0 depending on whether p1 is > p2, == p2, < p2.
602 * p1 - First entry pointer to compare.
604 * p2 - Second entry pointer to compare.
606 * compare - User comparison function. Ignored.
608 * table_p - Associated table being ordered. Ignored.
610 static int local_compare(const void *p1, const void *p2,
611 table_compare_t compare, const table_t * table_p)
613 const table_entry_t *const *ent1_p = p1, *const *ent2_p = p2;
617 /* compare as many bytes as we can */
618 size = (*ent1_p)->te_key_size;
619 if ((*ent2_p)->te_key_size < size)
620 size = (*ent2_p)->te_key_size;
621 cmp = memcmp(ENTRY_KEY_BUF(*ent1_p), ENTRY_KEY_BUF(*ent2_p), size);
622 /* if common-size equal, then if next more bytes, it is larger */
624 cmp = (*ent1_p)->te_key_size - (*ent2_p)->te_key_size;
629 * static int external_compare
633 * Compare two entries by calling user's compare program or by using
638 * < 0, == 0, or > 0 depending on whether p1 is > p2, == p2, < p2.
642 * p1 - First entry pointer to compare.
644 * p2 - Second entry pointer to compare.
646 * user_compare - User comparison function.
648 * table_p - Associated table being ordered.
650 static int external_compare(const void *p1, const void *p2,
651 table_compare_t user_compare,
652 const table_t * table_p)
654 const table_entry_t *const *ent1_p = p1, *const *ent2_p = p2;
655 /* since we know we are not aligned we can use the EXTRY_DATA_BUF macro */
656 return user_compare(ENTRY_KEY_BUF(*ent1_p), (*ent1_p)->te_key_size,
657 ENTRY_DATA_BUF(table_p, *ent1_p),
658 (*ent1_p)->te_data_size,
659 ENTRY_KEY_BUF(*ent2_p), (*ent2_p)->te_key_size,
660 ENTRY_DATA_BUF(table_p, *ent2_p),
661 (*ent2_p)->te_data_size);
665 * static int external_compare_align
669 * Compare two entries by calling user's compare program or by using
670 * memcmp. Alignment information is necessary.
674 * < 0, == 0, or > 0 depending on whether p1 is > p2, == p2, < p2.
678 * p1 - First entry pointer to compare.
680 * p2 - Second entry pointer to compare.
682 * user_compare - User comparison function.
684 * table_p - Associated table being ordered.
686 static int external_compare_align(const void *p1, const void *p2,
687 table_compare_t user_compare,
688 const table_t * table_p)
690 const table_entry_t *const *ent1_p = p1, *const *ent2_p = p2;
691 /* since we are aligned we have to use the entry_data_buf function */
692 return user_compare(ENTRY_KEY_BUF(*ent1_p), (*ent1_p)->te_key_size,
693 entry_data_buf(table_p, *ent1_p),
694 (*ent1_p)->te_data_size,
695 ENTRY_KEY_BUF(*ent2_p), (*ent2_p)->te_key_size,
696 entry_data_buf(table_p, *ent2_p),
697 (*ent2_p)->te_data_size);
705 * This sorts an array of longs via the quick sort algorithm (it's
714 * first_p - Start of the list that we are splitting.
716 * last_p - Last entry in the list that we are splitting.
718 * compare - Comparison function which is handling the actual
719 * elements. This is either a local function or a function to setup
720 * the problem element key and data pointers which then hands off to
723 * user_compare - User comparison function. Could be NULL if we are
724 * just using a local comparison function.
726 * table_p - Associated table being sorted.
728 static void split(void *first_p, void *last_p, compare_t compare,
729 table_compare_t user_compare, table_t * table_p)
731 void *pivot_p, *left_p, *right_p, *left_last_p, *right_first_p;
732 void *firsts[MAX_SORT_SPLITS], *lasts[MAX_SORT_SPLITS];
737 /* no need to split the list if it is < 2 elements */
738 while (first_p >= last_p) {
744 first_p = firsts[split_c];
745 last_p = lasts[split_c];
753 /* scan from right hand side */
754 while (right_p > left_p
755 && compare(right_p, pivot_p, user_compare, table_p) > 0)
756 right_p = (char *) right_p - sizeof(table_entry_t *);
757 /* scan from left hand side */
758 while (right_p > left_p
759 && compare(pivot_p, left_p, user_compare, table_p) >= 0)
760 left_p = (char *) left_p + sizeof(table_entry_t *);
761 /* if the pointers haven't met then swap values */
762 if (right_p > left_p) {
763 /* swap_bytes(left_p, right_p) */
766 temp = *(table_entry_t **) left_p;
767 *(table_entry_t **) left_p = *(table_entry_t **) right_p;
768 *(table_entry_t **) right_p = temp;
770 } while (right_p > left_p);
772 /* now we swap the pivot with the right-hand side */
774 /* swap_bytes(pivot_p, right_p); */
777 temp = *(table_entry_t **) pivot_p;
778 *(table_entry_t **) pivot_p = *(table_entry_t **) right_p;
779 *(table_entry_t **) right_p = temp;
783 /* save the section to the right of the pivot in our stack */
784 right_first_p = (char *) pivot_p + sizeof(table_entry_t *);
785 left_last_p = (char *) pivot_p - sizeof(table_entry_t *);
787 /* do we need to save the righthand side? */
788 if (right_first_p < last_p) {
789 if (split_c >= MAX_SORT_SPLITS) {
790 /* sanity check here -- we should never get here */
793 firsts[split_c] = right_first_p;
794 lasts[split_c] = last_p;
798 /* do the left hand side of the pivot */
799 /* first_p = first_p */
800 last_p = left_last_p;
804 /*************************** exported routines *******************************/
807 * table_t *table_alloc
811 * Allocate a new table structure.
815 * A pointer to the new table structure which must be passed to
816 * table_free to be deallocated. On error a NULL is returned.
820 * bucket_n - Number of buckets for the hash table. Our current hash
821 * value works best with base two numbers. Set to 0 to take the
822 * library default of 1024.
824 * error_p - Pointer to an integer which, if not NULL, will contain a
827 * malloc_f, realloc_f, free_f - Pointers to malloc(3)-, realloc(3)-
828 * and free(3)-style functions.
830 table_t *table_alloc(const unsigned int bucket_n, int *error_p,
831 void *(*malloc_f)(void *opt_param, size_t size),
832 void *(*calloc_f)(void *opt_param, size_t number, size_t size),
833 void *(*realloc_f)(void *opt_param, void *ptr, size_t size),
834 void (*free_f)(void *opt_param, void *ptr), void *opt_param)
836 table_t *table_p = NULL;
839 /* allocate a table structure */
840 if (malloc_f != NULL)
841 table_p = malloc_f(opt_param, sizeof(table_t));
843 table_p = malloc(sizeof(table_t));
844 if (table_p == NULL) {
846 *error_p = TABLE_ERROR_ALLOC;
853 buck_n = DEFAULT_SIZE;
854 /* allocate the buckets which are NULLed */
855 if (calloc_f != NULL)
856 table_p->ta_buckets = (table_entry_t **)calloc_f(opt_param, buck_n,
857 sizeof(table_entry_t *));
859 table_p->ta_buckets = (table_entry_t **)calloc(buck_n, sizeof(table_entry_t *));
860 if (table_p->ta_buckets == NULL) {
862 *error_p = TABLE_ERROR_ALLOC;
864 free_f(opt_param, table_p);
870 /* initialize structure */
871 table_p->ta_magic = TABLE_MAGIC;
872 table_p->ta_flags = 0;
873 table_p->ta_bucket_n = buck_n;
874 table_p->ta_entry_n = 0;
875 table_p->ta_data_align = 0;
876 table_p->ta_linear.tl_magic = 0;
877 table_p->ta_linear.tl_bucket_c = 0;
878 table_p->ta_linear.tl_entry_c = 0;
879 table_p->ta_file_size = 0;
880 table_p->ta_malloc = malloc_f != NULL ? malloc_f : sys_malloc;
881 table_p->ta_calloc = calloc_f != NULL ? calloc_f : sys_calloc;
882 table_p->ta_realloc = realloc_f != NULL ? realloc_f : sys_realloc;
883 table_p->ta_free = free_f != NULL ? free_f : sys_free;
884 table_p->opt_param = opt_param;
887 *error_p = TABLE_ERROR_NONE;
896 * Set the attributes for the table. The available attributes are
897 * specified at the top of table.h.
901 * Success - TABLE_ERROR_NONE
903 * Failure - Table error code.
907 * table_p - Pointer to a table structure which we will be altering.
909 * attr - Attribute(s) that we will be applying to the table.
911 int table_attr(table_t * table_p, const int attr)
914 return TABLE_ERROR_ARG_NULL;
915 if (table_p->ta_magic != TABLE_MAGIC)
916 return TABLE_ERROR_PNT;
917 table_p->ta_flags = attr;
919 return TABLE_ERROR_NONE;
923 * int table_set_data_alignment
927 * Set the alignment for the data in the table. For data elements
928 * sizeof(long) is recommended unless you use smaller data types
931 * WARNING: This must be done before any data gets put into the table.
935 * Success - TABLE_ERROR_NONE
937 * Failure - Table error code.
941 * table_p - Pointer to a table structure which we will be altering.
943 * alignment - Alignment requested for the data. Must be a power of
944 * 2. Set to 0 for none.
946 int table_set_data_alignment(table_t * table_p, const int alignment)
951 return TABLE_ERROR_ARG_NULL;
952 if (table_p->ta_magic != TABLE_MAGIC)
953 return TABLE_ERROR_PNT;
954 if (table_p->ta_entry_n > 0)
955 return TABLE_ERROR_NOT_EMPTY;
958 table_p->ta_data_align = 0;
960 /* verify we have a base 2 number */
961 for (val = 2; val < MAX_ALIGNMENT; val *= 2) {
962 if (val == alignment)
965 if (val >= MAX_ALIGNMENT)
966 return TABLE_ERROR_ALIGNMENT;
967 table_p->ta_data_align = alignment;
970 return TABLE_ERROR_NONE;
978 * Clear out and free all elements in a table structure.
982 * Success - TABLE_ERROR_NONE
984 * Failure - Table error code.
988 * table_p - Table structure pointer that we will be clearing.
990 int table_clear(table_t * table_p)
993 table_entry_t *entry_p, *next_p;
995 table_entry_t **bucket_p, **bounds_p;
998 return TABLE_ERROR_ARG_NULL;
999 if (table_p->ta_magic != TABLE_MAGIC)
1000 return TABLE_ERROR_PNT;
1001 /* free the table allocation and table structure */
1002 bounds_p = table_p->ta_buckets + table_p->ta_bucket_n;
1003 for (bucket_p = table_p->ta_buckets; bucket_p <= bounds_p; bucket_p++) {
1005 for (entry_p = *bucket_p; entry_p != NULL; entry_p = next_p) {
1006 /* record the next pointer before we free */
1007 next_p = entry_p->te_next_p;
1008 table_p->ta_free(table_p->opt_param, entry_p);
1011 /* clear the bucket entry after we free its entries */
1015 /* reset table state info */
1016 table_p->ta_entry_n = 0;
1017 table_p->ta_linear.tl_magic = 0;
1018 table_p->ta_linear.tl_bucket_c = 0;
1019 table_p->ta_linear.tl_entry_c = 0;
1021 return TABLE_ERROR_NONE;
1029 * Deallocates a table structure.
1033 * Success - TABLE_ERROR_NONE
1035 * Failure - Table error code.
1039 * table_p - Table structure pointer that we will be freeing.
1041 int table_free(table_t * table_p)
1045 if (table_p == NULL)
1046 return TABLE_ERROR_ARG_NULL;
1047 if (table_p->ta_magic != TABLE_MAGIC)
1048 return TABLE_ERROR_PNT;
1049 ret = table_clear(table_p);
1051 if (table_p->ta_buckets != NULL)
1052 table_p->ta_free(table_p->opt_param, table_p->ta_buckets);
1053 table_p->ta_magic = 0;
1054 table_p->ta_free(table_p->opt_param, table_p);
1060 * int table_insert_kd
1064 * Like table_insert except it passes back a pointer to the key and
1065 * the data buffers after they have been inserted into the table
1068 * This routine adds a key/data pair both of which are made up of a
1069 * buffer of bytes and an associated size. Both the key and the data
1070 * will be copied into buffers allocated inside the table. If the key
1071 * exists already, the associated data will be replaced if the
1072 * overwrite flag is set, otherwise an error is returned.
1074 * NOTE: be very careful changing the values since the table library
1075 * provides the pointers to its memory. The key can _never_ be
1076 * changed otherwise you will not find it again. The data can be
1077 * changed but its length can never be altered unless you delete and
1078 * re-insert it into the table.
1080 * WARNING: The pointers to the key and data are not in any specific
1081 * alignment. Accessing the key and/or data as an short, integer, or
1082 * long pointer directly can cause problems.
1084 * WARNING: Replacing a data cell (not inserting) will cause the table
1085 * linked list to be temporarily invalid. Care must be taken with
1086 * multiple threaded programs which are relying on the first/next
1087 * linked list to be always valid.
1091 * Success - TABLE_ERROR_NONE
1093 * Failure - Table error code.
1097 * table_p - Table structure pointer into which we will be inserting a
1098 * new key/data pair.
1100 * key_buf - Buffer of bytes of the key that we are inserting. If you
1101 * are storing an (int) as the key (for example) then key_buf should
1104 * key_size - Size of the key_buf buffer. If set to < 0 then the
1105 * library will do a strlen of key_buf and add 1 for the '\0'. If you
1106 * are storing an (int) as the key (for example) then key_size should
1109 * data_buf - Buffer of bytes of the data that we are inserting. If
1110 * it is NULL then the library will allocate space for the data in the
1111 * table without copying in any information. If data_buf is NULL and
1112 * data_size is 0 then the library will associate a NULL data pointer
1113 * with the key. If you are storing a (long) as the data (for
1114 * example) then data_buf should be a (long *).
1116 * data_size - Size of the data_buf buffer. If set to < 0 then the
1117 * library will do a strlen of data_buf and add 1 for the '\0'. If
1118 * you are storing an (long) as the key (for example) then key_size
1119 * should be sizeof(long).
1121 * key_buf_p - Pointer which, if not NULL, will be set to the address
1122 * of the key storage that was allocated in the table. If you are
1123 * storing an (int) as the key (for example) then key_buf_p should be
1124 * (int **) i.e. the address of a (int *).
1126 * data_buf_p - Pointer which, if not NULL, will be set to the address
1127 * of the data storage that was allocated in the table. If you are
1128 * storing an (long) as the data (for example) then data_buf_p should
1129 * be (long **) i.e. the address of a (long *).
1131 * overwrite - Flag which, if set to 1, will allow the overwriting of
1132 * the data in the table with the new data if the key already exists
1135 int table_insert_kd(table_t * table_p,
1136 const void *key_buf, const int key_size,
1137 const void *data_buf, const int data_size,
1138 void **key_buf_p, void **data_buf_p,
1139 const char overwrite_b)
1142 unsigned int ksize, dsize;
1143 table_entry_t *entry_p, *last_p;
1144 void *key_copy_p, *data_copy_p;
1146 /* check the arguments */
1147 if (table_p == NULL)
1148 return TABLE_ERROR_ARG_NULL;
1149 if (table_p->ta_magic != TABLE_MAGIC)
1150 return TABLE_ERROR_PNT;
1151 if (key_buf == NULL)
1152 return TABLE_ERROR_ARG_NULL;
1153 /* data_buf can be null but size must be >= 0, if it isn't null size != 0 */
1154 if ((data_buf == NULL && data_size < 0)
1155 || (data_buf != NULL && data_size == 0))
1156 return TABLE_ERROR_SIZE;
1157 /* determine sizes of key and data */
1159 ksize = strlen((char *) key_buf) + sizeof(char);
1163 dsize = strlen((char *) data_buf) + sizeof(char);
1166 /* get the bucket number via a hash function */
1167 bucket = hash(key_buf, ksize, 0) % table_p->ta_bucket_n;
1169 /* look for the entry in this bucket, only check keys of the same size */
1171 for (entry_p = table_p->ta_buckets[bucket];
1172 (entry_p != NULL) && (entry_p->te_next_p != last_p);
1173 last_p = entry_p, entry_p = entry_p->te_next_p) {
1174 if (entry_p->te_key_size == ksize
1175 && memcmp(ENTRY_KEY_BUF(entry_p), key_buf, ksize) == 0)
1179 /* did we find it? then we are in replace mode. */
1180 if (entry_p != NULL) {
1182 /* can we not overwrite existing data? */
1184 if (key_buf_p != NULL)
1185 *key_buf_p = ENTRY_KEY_BUF(entry_p);
1186 if (data_buf_p != NULL) {
1187 if (entry_p->te_data_size == 0)
1190 if (table_p->ta_data_align == 0)
1191 *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
1193 *data_buf_p = entry_data_buf(table_p, entry_p);
1196 return TABLE_ERROR_OVERWRITE;
1199 /* re-alloc entry's data if the new size != the old */
1200 if (dsize != entry_p->te_data_size) {
1203 * First we delete it from the list to keep the list whole.
1204 * This properly preserves the linked list in case we have a
1205 * thread marching through the linked list while we are
1206 * inserting. Maybe this is an unnecessary protection but it
1207 * should not harm that much.
1210 table_p->ta_buckets[bucket] = entry_p->te_next_p;
1212 last_p->te_next_p = entry_p->te_next_p;
1214 * Realloc the structure which may change its pointer. NOTE:
1215 * this may change any previous data_key_p and data_copy_p
1218 entry_p = (table_entry_t *)
1219 table_p->ta_realloc(table_p->opt_param, entry_p,
1220 entry_size(table_p, entry_p->te_key_size, dsize));
1221 if (entry_p == NULL)
1222 return TABLE_ERROR_ALLOC;
1223 /* add it back to the front of the list */
1224 entry_p->te_data_size = dsize;
1225 entry_p->te_next_p = table_p->ta_buckets[bucket];
1226 table_p->ta_buckets[bucket] = entry_p;
1229 /* copy or replace data in storage */
1231 if (table_p->ta_data_align == 0)
1232 data_copy_p = ENTRY_DATA_BUF(table_p, entry_p);
1234 data_copy_p = entry_data_buf(table_p, entry_p);
1235 if (data_buf != NULL)
1236 memcpy(data_copy_p, data_buf, dsize);
1240 if (key_buf_p != NULL)
1241 *key_buf_p = ENTRY_KEY_BUF(entry_p);
1242 if (data_buf_p != NULL)
1243 *data_buf_p = data_copy_p;
1244 /* returning from the section where we were overwriting table data */
1245 return TABLE_ERROR_NONE;
1249 * It is a new entry.
1252 /* allocate a new entry */
1253 entry_p = (table_entry_t *)
1254 table_p->ta_malloc(table_p->opt_param,
1255 entry_size(table_p, ksize, dsize));
1256 if (entry_p == NULL)
1257 return TABLE_ERROR_ALLOC;
1258 /* copy key into storage */
1259 entry_p->te_key_size = ksize;
1260 key_copy_p = ENTRY_KEY_BUF(entry_p);
1261 memcpy(key_copy_p, key_buf, ksize);
1264 entry_p->te_data_size = dsize;
1266 if (table_p->ta_data_align == 0)
1267 data_copy_p = ENTRY_DATA_BUF(table_p, entry_p);
1269 data_copy_p = entry_data_buf(table_p, entry_p);
1270 if (data_buf != NULL)
1271 memcpy(data_copy_p, data_buf, dsize);
1275 if (key_buf_p != NULL)
1276 *key_buf_p = key_copy_p;
1277 if (data_buf_p != NULL)
1278 *data_buf_p = data_copy_p;
1279 /* insert into list, no need to append */
1280 entry_p->te_next_p = table_p->ta_buckets[bucket];
1281 table_p->ta_buckets[bucket] = entry_p;
1283 table_p->ta_entry_n++;
1285 /* do we need auto-adjust? */
1286 if (table_p->ta_flags & TABLE_FLAG_AUTO_ADJUST
1287 && SHOULD_TABLE_GROW(table_p))
1288 return table_adjust(table_p, table_p->ta_entry_n);
1289 return TABLE_ERROR_NONE;
1297 * Exactly the same as table_insert_kd except it does not pass back a
1298 * pointer to the key after they have been inserted into the table
1299 * structure. This is still here for backwards compatibility.
1301 * See table_insert_kd for more information.
1305 * Success - TABLE_ERROR_NONE
1307 * Failure - Table error code.
1311 * table_p - Table structure pointer into which we will be inserting a
1312 * new key/data pair.
1314 * key_buf - Buffer of bytes of the key that we are inserting. If you
1315 * are storing an (int) as the key (for example) then key_buf should
1318 * key_size - Size of the key_buf buffer. If set to < 0 then the
1319 * library will do a strlen of key_buf and add 1 for the '\0'. If you
1320 * are storing an (int) as the key (for example) then key_size should
1323 * data_buf - Buffer of bytes of the data that we are inserting. If
1324 * it is NULL then the library will allocate space for the data in the
1325 * table without copying in any information. If data_buf is NULL and
1326 * data_size is 0 then the library will associate a NULL data pointer
1327 * with the key. If you are storing a (long) as the data (for
1328 * example) then data_buf should be a (long *).
1330 * data_size - Size of the data_buf buffer. If set to < 0 then the
1331 * library will do a strlen of data_buf and add 1 for the '\0'. If
1332 * you are storing an (long) as the key (for example) then key_size
1333 * should be sizeof(long).
1335 * data_buf_p - Pointer which, if not NULL, will be set to the address
1336 * of the data storage that was allocated in the table. If you are
1337 * storing an (long) as the data (for example) then data_buf_p should
1338 * be (long **) i.e. the address of a (long *).
1340 * overwrite - Flag which, if set to 1, will allow the overwriting of
1341 * the data in the table with the new data if the key already exists
1344 int table_insert(table_t * table_p,
1345 const void *key_buf, const int key_size,
1346 const void *data_buf, const int data_size,
1347 void **data_buf_p, const char overwrite_b)
1349 return table_insert_kd(table_p, key_buf, key_size, data_buf, data_size,
1350 NULL, data_buf_p, overwrite_b);
1354 * int table_retrieve
1358 * This routine looks up a key made up of a buffer of bytes and an
1359 * associated size in the table. If found then it returns the
1360 * associated data information.
1364 * Success - TABLE_ERROR_NONE
1366 * Failure - Table error code.
1370 * table_p - Table structure pointer into which we will be searching
1373 * key_buf - Buffer of bytes of the key that we are searching for. If
1374 * you are looking for an (int) as the key (for example) then key_buf
1375 * should be a (int *).
1377 * key_size - Size of the key_buf buffer. If set to < 0 then the
1378 * library will do a strlen of key_buf and add 1 for the '\0'. If you
1379 * are looking for an (int) as the key (for example) then key_size
1380 * should be sizeof(int).
1382 * data_buf_p - Pointer which, if not NULL, will be set to the address
1383 * of the data storage that was allocated in the table and that is
1384 * associated with the key. If a (long) was stored as the data (for
1385 * example) then data_buf_p should be (long **) i.e. the address of a
1388 * data_size_p - Pointer to an integer which, if not NULL, will be set
1389 * to the size of the data stored in the table that is associated with
1392 int table_retrieve(table_t * table_p,
1393 const void *key_buf, const int key_size,
1394 void **data_buf_p, int *data_size_p)
1398 table_entry_t *entry_p, **buckets;
1400 if (table_p == NULL)
1401 return TABLE_ERROR_ARG_NULL;
1402 if (table_p->ta_magic != TABLE_MAGIC)
1403 return TABLE_ERROR_PNT;
1404 if (key_buf == NULL)
1405 return TABLE_ERROR_ARG_NULL;
1408 ksize = strlen((char *) key_buf) + sizeof(char);
1411 /* get the bucket number via a has function */
1412 bucket = hash(key_buf, ksize, 0) % table_p->ta_bucket_n;
1414 /* look for the entry in this bucket, only check keys of the same size */
1415 buckets = table_p->ta_buckets;
1416 for (entry_p = buckets[bucket];
1418 entry_p = entry_p->te_next_p) {
1419 entry_p = TABLE_POINTER(table_p, table_entry_t *, entry_p);
1420 if (entry_p->te_key_size == ksize
1421 && memcmp(ENTRY_KEY_BUF(entry_p), key_buf, ksize) == 0)
1426 if (entry_p == NULL)
1427 return TABLE_ERROR_NOT_FOUND;
1428 if (data_buf_p != NULL) {
1429 if (entry_p->te_data_size == 0)
1432 if (table_p->ta_data_align == 0)
1433 *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
1435 *data_buf_p = entry_data_buf(table_p, entry_p);
1438 if (data_size_p != NULL)
1439 *data_size_p = entry_p->te_data_size;
1440 return TABLE_ERROR_NONE;
1448 * This routine looks up a key made up of a buffer of bytes and an
1449 * associated size in the table. If found then it will be removed
1450 * from the table. The associated data can be passed back to the user
1455 * Success - TABLE_ERROR_NONE
1457 * Failure - Table error code.
1459 * NOTE: this could be an allocation error if the library is to return
1460 * the data to the user.
1464 * table_p - Table structure pointer from which we will be deleteing
1467 * key_buf - Buffer of bytes of the key that we are searching for to
1468 * delete. If you are deleting an (int) key (for example) then
1469 * key_buf should be a (int *).
1471 * key_size - Size of the key_buf buffer. If set to < 0 then the
1472 * library will do a strlen of key_buf and add 1 for the '\0'. If you
1473 * are deleting an (int) key (for example) then key_size should be
1476 * data_buf_p - Pointer which, if not NULL, will be set to the address
1477 * of the data storage that was allocated in the table and that was
1478 * associated with the key. If a (long) was stored as the data (for
1479 * example) then data_buf_p should be (long **) i.e. the address of a
1480 * (long *). If a pointer is passed in, the caller is responsible for
1481 * freeing it after use. If data_buf_p is NULL then the library will
1482 * free up the data allocation itself.
1484 * data_size_p - Pointer to an integer which, if not NULL, will be set
1485 * to the size of the data that was stored in the table and that was
1486 * associated with the key.
1488 int table_delete(table_t * table_p,
1489 const void *key_buf, const int key_size,
1490 void **data_buf_p, int *data_size_p)
1494 unsigned char *data_copy_p;
1495 table_entry_t *entry_p, *last_p;
1497 if (table_p == NULL)
1498 return TABLE_ERROR_ARG_NULL;
1499 if (table_p->ta_magic != TABLE_MAGIC)
1500 return TABLE_ERROR_PNT;
1501 if (key_buf == NULL)
1502 return TABLE_ERROR_ARG_NULL;
1503 /* get the key size */
1505 ksize = strlen((char *) key_buf) + sizeof(char);
1508 /* find our bucket */
1509 bucket = hash(key_buf, ksize, 0) % table_p->ta_bucket_n;
1511 /* look for the entry in this bucket, only check keys of the same size */
1512 for (last_p = NULL, entry_p = table_p->ta_buckets[bucket]; entry_p != NULL;
1513 last_p = entry_p, entry_p = entry_p->te_next_p) {
1514 if (entry_p->te_key_size == ksize
1515 && memcmp(ENTRY_KEY_BUF(entry_p), key_buf, ksize) == 0)
1519 /* did we find it? */
1520 if (entry_p == NULL)
1521 return TABLE_ERROR_NOT_FOUND;
1523 * NOTE: we may want to adjust the linear counters here if the entry
1524 * we are deleting is the one we are pointing on or is ahead of the
1525 * one in the bucket list
1528 /* remove entry from the linked list */
1530 table_p->ta_buckets[bucket] = entry_p->te_next_p;
1532 last_p->te_next_p = entry_p->te_next_p;
1534 if (data_buf_p != NULL) {
1535 if (entry_p->te_data_size == 0)
1539 * if we were storing it compacted, we now need to malloc some
1540 * space if the user wants the value after the delete.
1542 *data_buf_p = table_p->ta_malloc(table_p->opt_param,
1543 entry_p->te_data_size);
1544 if (*data_buf_p == NULL)
1545 return TABLE_ERROR_ALLOC;
1546 if (table_p->ta_data_align == 0)
1547 data_copy_p = ENTRY_DATA_BUF(table_p, entry_p);
1549 data_copy_p = entry_data_buf(table_p, entry_p);
1550 memcpy(*data_buf_p, data_copy_p, entry_p->te_data_size);
1553 if (data_size_p != NULL)
1554 *data_size_p = entry_p->te_data_size;
1555 table_p->ta_free(table_p->opt_param, entry_p);
1558 table_p->ta_entry_n--;
1560 /* do we need auto-adjust down? */
1561 if ((table_p->ta_flags & TABLE_FLAG_AUTO_ADJUST)
1562 && (table_p->ta_flags & TABLE_FLAG_ADJUST_DOWN)
1563 && SHOULD_TABLE_SHRINK(table_p))
1564 return table_adjust(table_p, table_p->ta_entry_n);
1565 return TABLE_ERROR_NONE;
1569 * int table_delete_first
1573 * This is like the table_delete routines except it deletes the first
1574 * key/data pair in the table instead of an entry corresponding to a
1575 * particular key. The associated key and data information can be
1576 * passed back to the user if requested. This routines is handy to
1577 * clear out a table.
1581 * Success - TABLE_ERROR_NONE
1583 * Failure - Table error code.
1585 * NOTE: this could be an allocation error if the library is to return
1586 * the data to the user.
1590 * table_p - Table structure pointer from which we will be deleteing
1593 * key_buf_p - Pointer which, if not NULL, will be set to the address
1594 * of the storage of the first key that was allocated in the table.
1595 * If an (int) was stored as the first key (for example) then
1596 * key_buf_p should be (int **) i.e. the address of a (int *). If a
1597 * pointer is passed in, the caller is responsible for freeing it
1598 * after use. If key_buf_p is NULL then the library will free up the
1599 * key allocation itself.
1601 * key_size_p - Pointer to an integer which, if not NULL, will be set
1602 * to the size of the key that was stored in the table and that was
1603 * associated with the key.
1605 * data_buf_p - Pointer which, if not NULL, will be set to the address
1606 * of the data storage that was allocated in the table and that was
1607 * associated with the key. If a (long) was stored as the data (for
1608 * example) then data_buf_p should be (long **) i.e. the address of a
1609 * (long *). If a pointer is passed in, the caller is responsible for
1610 * freeing it after use. If data_buf_p is NULL then the library will
1611 * free up the data allocation itself.
1613 * data_size_p - Pointer to an integer which, if not NULL, will be set
1614 * to the size of the data that was stored in the table and that was
1615 * associated with the key.
1617 int table_delete_first(table_t * table_p,
1618 void **key_buf_p, int *key_size_p,
1619 void **data_buf_p, int *data_size_p)
1621 unsigned char *data_copy_p;
1622 table_entry_t *entry_p;
1623 table_linear_t linear;
1625 if (table_p == NULL)
1626 return TABLE_ERROR_ARG_NULL;
1627 if (table_p->ta_magic != TABLE_MAGIC)
1628 return TABLE_ERROR_PNT;
1629 /* take the first entry */
1630 entry_p = first_entry(table_p, &linear);
1631 if (entry_p == NULL)
1632 return TABLE_ERROR_NOT_FOUND;
1634 * NOTE: we may want to adjust the linear counters here if the entry
1635 * we are deleting is the one we are pointing on or is ahead of the
1636 * one in the bucket list
1639 /* remove entry from the linked list */
1640 table_p->ta_buckets[linear.tl_bucket_c] = entry_p->te_next_p;
1643 if (key_buf_p != NULL) {
1644 if (entry_p->te_key_size == 0)
1648 * if we were storing it compacted, we now need to malloc some
1649 * space if the user wants the value after the delete.
1651 *key_buf_p = table_p->ta_malloc(table_p->opt_param,
1652 entry_p->te_key_size);
1653 if (*key_buf_p == NULL)
1654 return TABLE_ERROR_ALLOC;
1655 memcpy(*key_buf_p, ENTRY_KEY_BUF(entry_p), entry_p->te_key_size);
1658 if (key_size_p != NULL)
1659 *key_size_p = entry_p->te_key_size;
1660 if (data_buf_p != NULL) {
1661 if (entry_p->te_data_size == 0)
1665 * if we were storing it compacted, we now need to malloc some
1666 * space if the user wants the value after the delete.
1668 *data_buf_p = table_p->ta_malloc(table_p->opt_param,
1669 entry_p->te_data_size);
1670 if (*data_buf_p == NULL)
1671 return TABLE_ERROR_ALLOC;
1672 if (table_p->ta_data_align == 0)
1673 data_copy_p = ENTRY_DATA_BUF(table_p, entry_p);
1675 data_copy_p = entry_data_buf(table_p, entry_p);
1676 memcpy(*data_buf_p, data_copy_p, entry_p->te_data_size);
1679 if (data_size_p != NULL)
1680 *data_size_p = entry_p->te_data_size;
1681 table_p->ta_free(table_p->opt_param, entry_p);
1683 table_p->ta_entry_n--;
1685 /* do we need auto-adjust down? */
1686 if ((table_p->ta_flags & TABLE_FLAG_AUTO_ADJUST)
1687 && (table_p->ta_flags & TABLE_FLAG_ADJUST_DOWN)
1688 && SHOULD_TABLE_SHRINK(table_p))
1689 return table_adjust(table_p, table_p->ta_entry_n);
1690 return TABLE_ERROR_NONE;
1698 * Get some information about a table_p structure.
1702 * Success - TABLE_ERROR_NONE
1704 * Failure - Table error code.
1708 * table_p - Table structure pointer from which we are getting
1711 * num_buckets_p - Pointer to an integer which, if not NULL, will
1712 * contain the number of buckets in the table.
1714 * num_entries_p - Pointer to an integer which, if not NULL, will
1715 * contain the number of entries stored in the table.
1717 int table_info(table_t * table_p, int *num_buckets_p, int *num_entries_p)
1719 if (table_p == NULL)
1720 return TABLE_ERROR_ARG_NULL;
1721 if (table_p->ta_magic != TABLE_MAGIC)
1722 return TABLE_ERROR_PNT;
1723 if (num_buckets_p != NULL)
1724 *num_buckets_p = table_p->ta_bucket_n;
1725 if (num_entries_p != NULL)
1726 *num_entries_p = table_p->ta_entry_n;
1727 return TABLE_ERROR_NONE;
1735 * Set the number of buckets in a table to a certain value.
1739 * Success - TABLE_ERROR_NONE
1741 * Failure - Table error code.
1745 * table_p - Table structure pointer of which we are adjusting.
1747 * bucket_n - Number buckets to adjust the table to. Set to 0 to
1748 * adjust the table to its number of entries.
1750 int table_adjust(table_t * table_p, const int bucket_n)
1752 table_entry_t *entry_p, *next_p;
1753 table_entry_t **buckets, **bucket_p, **bounds_p;
1755 unsigned int buck_n;
1757 if (table_p == NULL)
1758 return TABLE_ERROR_ARG_NULL;
1759 if (table_p->ta_magic != TABLE_MAGIC)
1760 return TABLE_ERROR_PNT;
1762 * NOTE: we walk through the entries and rehash them. If we stored
1763 * the hash value as a full int in the table-entry, all we would
1764 * have to do is remod it.
1767 /* normalize to the number of entries */
1769 buck_n = table_p->ta_entry_n;
1772 /* we must have at least 1 bucket */
1775 /* make sure we have somethign to do */
1776 if (buck_n <= table_p->ta_bucket_n)
1777 return TABLE_ERROR_NONE;
1778 /* allocate a new bucket list */
1779 buckets = (table_entry_t **)
1780 table_p->ta_calloc(table_p->opt_param,
1781 buck_n, sizeof(table_entry_t *));
1782 if (table_p->ta_buckets == NULL)
1783 return TABLE_ERROR_ALLOC;
1785 * run through each of the items in the current table and rehash
1786 * them into the newest bucket sizes
1788 bounds_p = table_p->ta_buckets + table_p->ta_bucket_n;
1789 for (bucket_p = table_p->ta_buckets; bucket_p < bounds_p; bucket_p++) {
1790 for (entry_p = *bucket_p; entry_p != NULL; entry_p = next_p) {
1792 /* hash the old data into the new table size */
1793 bucket = hash(ENTRY_KEY_BUF(entry_p), entry_p->te_key_size, 0) % buck_n;
1795 /* record the next one now since we overwrite next below */
1796 next_p = entry_p->te_next_p;
1798 /* insert into new list, no need to append */
1799 entry_p->te_next_p = buckets[bucket];
1800 buckets[bucket] = entry_p;
1803 * NOTE: we may want to adjust the bucket_c linear entry here to
1807 /* remove the old table pointers as we go by */
1811 /* replace the table buckets with the new ones */
1812 table_p->ta_free(table_p->opt_param, table_p->ta_buckets);
1813 table_p->ta_buckets = buckets;
1814 table_p->ta_bucket_n = buck_n;
1816 return TABLE_ERROR_NONE;
1820 * const char *table_strerror
1824 * Return the corresponding string for the error number.
1828 * Success - String equivalient of the error.
1830 * Failure - String "invalid error code"
1834 * error - Error number that we are converting.
1836 const char *table_strerror(const int error)
1840 for (err_p = errors; err_p->es_error != 0; err_p++) {
1841 if (err_p->es_error == error)
1842 return err_p->es_string;
1845 return INVALID_ERROR;
1849 * int table_type_size
1853 * Return the size of the internal table type.
1857 * The size of the table_t type.
1863 int table_type_size(void)
1865 return sizeof(table_t);
1868 /************************* linear access routines ****************************/
1875 * Find first element in a table and pass back information about the
1876 * key/data pair. If any of the key/data pointers are NULL then they
1879 * NOTE: This function is not reentrant. More than one thread cannot
1880 * be doing a first and next on the same table at the same time. Use
1881 * the table_first_r version below for this.
1885 * Success - TABLE_ERROR_NONE
1887 * Failure - Table error code.
1891 * table_p - Table structure pointer from which we are getting the
1894 * key_buf_p - Pointer which, if not NULL, will be set to the address
1895 * of the storage of the first key that is allocated in the table. If
1896 * an (int) is stored as the first key (for example) then key_buf_p
1897 * should be (int **) i.e. the address of a (int *).
1899 * key_size_p - Pointer to an integer which, if not NULL, will be set
1900 * to the size of the key that is stored in the table and that is
1901 * associated with the first key.
1903 * data_buf_p - Pointer which, if not NULL, will be set to the address
1904 * of the data storage that is allocated in the table and that is
1905 * associated with the first key. If a (long) is stored as the data
1906 * (for example) then data_buf_p should be (long **) i.e. the address
1909 * data_size_p - Pointer to an integer which, if not NULL, will be set
1910 * to the size of the data that is stored in the table and that is
1911 * associated with the first key.
1913 int table_first(table_t * table_p,
1914 void **key_buf_p, int *key_size_p,
1915 void **data_buf_p, int *data_size_p)
1917 table_entry_t *entry_p;
1919 if (table_p == NULL)
1920 return TABLE_ERROR_ARG_NULL;
1921 if (table_p->ta_magic != TABLE_MAGIC)
1922 return TABLE_ERROR_PNT;
1923 /* initialize our linear magic number */
1924 table_p->ta_linear.tl_magic = LINEAR_MAGIC;
1926 entry_p = first_entry(table_p, &table_p->ta_linear);
1927 if (entry_p == NULL)
1928 return TABLE_ERROR_NOT_FOUND;
1929 if (key_buf_p != NULL)
1930 *key_buf_p = ENTRY_KEY_BUF(entry_p);
1931 if (key_size_p != NULL)
1932 *key_size_p = entry_p->te_key_size;
1933 if (data_buf_p != NULL) {
1934 if (entry_p->te_data_size == 0)
1937 if (table_p->ta_data_align == 0)
1938 *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
1940 *data_buf_p = entry_data_buf(table_p, entry_p);
1943 if (data_size_p != NULL)
1944 *data_size_p = entry_p->te_data_size;
1945 return TABLE_ERROR_NONE;
1953 * Find the next element in a table and pass back information about
1954 * the key/data pair. If any of the key/data pointers are NULL then
1957 * NOTE: This function is not reentrant. More than one thread cannot
1958 * be doing a first and next on the same table at the same time. Use
1959 * the table_next_r version below for this.
1963 * Success - TABLE_ERROR_NONE
1965 * Failure - Table error code.
1969 * table_p - Table structure pointer from which we are getting the
1972 * key_buf_p - Pointer which, if not NULL, will be set to the address
1973 * of the storage of the next key that is allocated in the table. If
1974 * an (int) is stored as the next key (for example) then key_buf_p
1975 * should be (int **) i.e. the address of a (int *).
1977 * key_size_p - Pointer to an integer which, if not NULL, will be set
1978 * to the size of the key that is stored in the table and that is
1979 * associated with the next key.
1981 * data_buf_p - Pointer which, if not NULL, will be set to the address
1982 * of the data storage that is allocated in the table and that is
1983 * associated with the next key. If a (long) is stored as the data
1984 * (for example) then data_buf_p should be (long **) i.e. the address
1987 * data_size_p - Pointer to an integer which, if not NULL, will be set
1988 * to the size of the data that is stored in the table and that is
1989 * associated with the next key.
1991 int table_next(table_t * table_p,
1992 void **key_buf_p, int *key_size_p,
1993 void **data_buf_p, int *data_size_p)
1995 table_entry_t *entry_p;
1998 if (table_p == NULL)
1999 return TABLE_ERROR_ARG_NULL;
2000 if (table_p->ta_magic != TABLE_MAGIC)
2001 return TABLE_ERROR_PNT;
2002 if (table_p->ta_linear.tl_magic != LINEAR_MAGIC)
2003 return TABLE_ERROR_LINEAR;
2004 /* move to the next entry */
2005 entry_p = next_entry(table_p, &table_p->ta_linear, &error);
2006 if (entry_p == NULL)
2008 if (key_buf_p != NULL)
2009 *key_buf_p = ENTRY_KEY_BUF(entry_p);
2010 if (key_size_p != NULL)
2011 *key_size_p = entry_p->te_key_size;
2012 if (data_buf_p != NULL) {
2013 if (entry_p->te_data_size == 0)
2016 if (table_p->ta_data_align == 0)
2017 *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
2019 *data_buf_p = entry_data_buf(table_p, entry_p);
2022 if (data_size_p != NULL)
2023 *data_size_p = entry_p->te_data_size;
2024 return TABLE_ERROR_NONE;
2032 * Find the current element in a table and pass back information about
2033 * the key/data pair. If any of the key/data pointers are NULL then
2036 * NOTE: This function is not reentrant. Use the table_current_r
2041 * Success - TABLE_ERROR_NONE
2043 * Failure - Table error code.
2047 * table_p - Table structure pointer from which we are getting the
2050 * key_buf_p - Pointer which, if not NULL, will be set to the address
2051 * of the storage of the current key that is allocated in the table.
2052 * If an (int) is stored as the current key (for example) then
2053 * key_buf_p should be (int **) i.e. the address of a (int *).
2055 * key_size_p - Pointer to an integer which, if not NULL, will be set
2056 * to the size of the key that is stored in the table and that is
2057 * associated with the current key.
2059 * data_buf_p - Pointer which, if not NULL, will be set to the address
2060 * of the data storage that is allocated in the table and that is
2061 * associated with the current key. If a (long) is stored as the data
2062 * (for example) then data_buf_p should be (long **) i.e. the address
2065 * data_size_p - Pointer to an integer which, if not NULL, will be set
2066 * to the size of the data that is stored in the table and that is
2067 * associated with the current key.
2069 int table_this(table_t * table_p,
2070 void **key_buf_p, int *key_size_p,
2071 void **data_buf_p, int *data_size_p)
2073 table_entry_t *entry_p = NULL;
2076 if (table_p == NULL)
2077 return TABLE_ERROR_ARG_NULL;
2078 if (table_p->ta_magic != TABLE_MAGIC)
2079 return TABLE_ERROR_PNT;
2080 if (table_p->ta_linear.tl_magic != LINEAR_MAGIC)
2081 return TABLE_ERROR_LINEAR;
2082 /* if we removed an item that shorted the bucket list, we may get this */
2083 if (table_p->ta_linear.tl_bucket_c >= table_p->ta_bucket_n) {
2085 * NOTE: this might happen if we delete an item which shortens the
2086 * table bucket numbers.
2088 return TABLE_ERROR_NOT_FOUND;
2091 /* find the entry which is the nth in the list */
2092 entry_p = table_p->ta_buckets[table_p->ta_linear.tl_bucket_c];
2093 /* NOTE: we swap the order here to be more efficient */
2094 for (entry_c = table_p->ta_linear.tl_entry_c; entry_c > 0; entry_c--) {
2095 /* did we reach the end of the list? */
2096 if (entry_p == NULL)
2098 entry_p = TABLE_POINTER(table_p, table_entry_t *, entry_p)->te_next_p;
2101 /* is this a NOT_FOUND or a LINEAR error */
2102 if (entry_p == NULL)
2103 return TABLE_ERROR_NOT_FOUND;
2104 if (key_buf_p != NULL)
2105 *key_buf_p = ENTRY_KEY_BUF(entry_p);
2106 if (key_size_p != NULL)
2107 *key_size_p = entry_p->te_key_size;
2108 if (data_buf_p != NULL) {
2109 if (entry_p->te_data_size == 0)
2112 if (table_p->ta_data_align == 0)
2113 *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
2115 *data_buf_p = entry_data_buf(table_p, entry_p);
2118 if (data_size_p != NULL)
2119 *data_size_p = entry_p->te_data_size;
2120 return TABLE_ERROR_NONE;
2128 * Reetrant version of the table_first routine above. Find first
2129 * element in a table and pass back information about the key/data
2130 * pair. If any of the key/data pointers are NULL then they are
2135 * Success - TABLE_ERROR_NONE
2137 * Failure - Table error code.
2141 * table_p - Table structure pointer from which we are getting the
2144 * linear_p - Pointer to a table linear structure which is initialized
2145 * here. The same pointer should then be passed to table_next_r
2148 * key_buf_p - Pointer which, if not NULL, will be set to the address
2149 * of the storage of the first key that is allocated in the table. If
2150 * an (int) is stored as the first key (for example) then key_buf_p
2151 * should be (int **) i.e. the address of a (int *).
2153 * key_size_p - Pointer to an integer which, if not NULL, will be set
2154 * to the size of the key that is stored in the table and that is
2155 * associated with the first key.
2157 * data_buf_p - Pointer which, if not NULL, will be set to the address
2158 * of the data storage that is allocated in the table and that is
2159 * associated with the first key. If a (long) is stored as the data
2160 * (for example) then data_buf_p should be (long **) i.e. the address
2163 * data_size_p - Pointer to an integer which, if not NULL, will be set
2164 * to the size of the data that is stored in the table and that is
2165 * associated with the first key.
2167 int table_first_r(table_t * table_p, table_linear_t * linear_p,
2168 void **key_buf_p, int *key_size_p,
2169 void **data_buf_p, int *data_size_p)
2171 table_entry_t *entry_p;
2173 if (table_p == NULL)
2174 return TABLE_ERROR_ARG_NULL;
2175 if (table_p->ta_magic != TABLE_MAGIC)
2176 return TABLE_ERROR_PNT;
2177 if (linear_p == NULL)
2178 return TABLE_ERROR_ARG_NULL;
2179 /* initialize our linear magic number */
2180 linear_p->tl_magic = LINEAR_MAGIC;
2182 entry_p = first_entry(table_p, linear_p);
2183 if (entry_p == NULL)
2184 return TABLE_ERROR_NOT_FOUND;
2185 if (key_buf_p != NULL)
2186 *key_buf_p = ENTRY_KEY_BUF(entry_p);
2187 if (key_size_p != NULL)
2188 *key_size_p = entry_p->te_key_size;
2189 if (data_buf_p != NULL) {
2190 if (entry_p->te_data_size == 0)
2193 if (table_p->ta_data_align == 0)
2194 *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
2196 *data_buf_p = entry_data_buf(table_p, entry_p);
2199 if (data_size_p != NULL)
2200 *data_size_p = entry_p->te_data_size;
2201 return TABLE_ERROR_NONE;
2209 * Reetrant version of the table_next routine above. Find next
2210 * element in a table and pass back information about the key/data
2211 * pair. If any of the key/data pointers are NULL then they are
2216 * Success - TABLE_ERROR_NONE
2218 * Failure - Table error code.
2222 * table_p - Table structure pointer from which we are getting the
2225 * linear_p - Pointer to a table linear structure which is incremented
2226 * here. The same pointer must have been passed to table_first_r
2227 * first so that it can be initialized.
2229 * key_buf_p - Pointer which, if not NULL, will be set to the address
2230 * of the storage of the next key that is allocated in the table. If
2231 * an (int) is stored as the next key (for example) then key_buf_p
2232 * should be (int **) i.e. the address of a (int *).
2234 * key_size_p - Pointer to an integer which, if not NULL will be set
2235 * to the size of the key that is stored in the table and that is
2236 * associated with the next key.
2238 * data_buf_p - Pointer which, if not NULL, will be set to the address
2239 * of the data storage that is allocated in the table and that is
2240 * associated with the next key. If a (long) is stored as the data
2241 * (for example) then data_buf_p should be (long **) i.e. the address
2244 * data_size_p - Pointer to an integer which, if not NULL, will be set
2245 * to the size of the data that is stored in the table and that is
2246 * associated with the next key.
2248 int table_next_r(table_t * table_p, table_linear_t * linear_p,
2249 void **key_buf_p, int *key_size_p,
2250 void **data_buf_p, int *data_size_p)
2252 table_entry_t *entry_p;
2255 if (table_p == NULL)
2256 return TABLE_ERROR_ARG_NULL;
2257 if (table_p->ta_magic != TABLE_MAGIC)
2258 return TABLE_ERROR_PNT;
2259 if (linear_p == NULL)
2260 return TABLE_ERROR_ARG_NULL;
2261 if (linear_p->tl_magic != LINEAR_MAGIC)
2262 return TABLE_ERROR_LINEAR;
2263 /* move to the next entry */
2264 entry_p = next_entry(table_p, linear_p, &error);
2265 if (entry_p == NULL)
2267 if (key_buf_p != NULL)
2268 *key_buf_p = ENTRY_KEY_BUF(entry_p);
2269 if (key_size_p != NULL)
2270 *key_size_p = entry_p->te_key_size;
2271 if (data_buf_p != NULL) {
2272 if (entry_p->te_data_size == 0)
2275 if (table_p->ta_data_align == 0)
2276 *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
2278 *data_buf_p = entry_data_buf(table_p, entry_p);
2281 if (data_size_p != NULL)
2282 *data_size_p = entry_p->te_data_size;
2283 return TABLE_ERROR_NONE;
2291 * Reetrant version of the table_this routine above. Find current
2292 * element in a table and pass back information about the key/data
2293 * pair. If any of the key/data pointers are NULL then they are
2298 * Success - TABLE_ERROR_NONE
2300 * Failure - Table error code.
2304 * table_p - Table structure pointer from which we are getting the
2307 * linear_p - Pointer to a table linear structure which is accessed
2308 * here. The same pointer must have been passed to table_first_r
2309 * first so that it can be initialized.
2311 * key_buf_p - Pointer which, if not NULL, will be set to the address
2312 * of the storage of the current key that is allocated in the table.
2313 * If an (int) is stored as the current key (for example) then
2314 * key_buf_p should be (int **) i.e. the address of a (int *).
2316 * key_size_p - Pointer to an integer which, if not NULL, will be set
2317 * to the size of the key that is stored in the table and that is
2318 * associated with the current key.
2320 * data_buf_p - Pointer which, if not NULL, will be set to the address
2321 * of the data storage that is allocated in the table and that is
2322 * associated with the current key. If a (long) is stored as the data
2323 * (for example) then data_buf_p should be (long **) i.e. the address
2326 * data_size_p - Pointer to an integer which, if not NULL, will be set
2327 * to the size of the data that is stored in the table and that is
2328 * associated with the current key.
2330 int table_this_r(table_t * table_p, table_linear_t * linear_p,
2331 void **key_buf_p, int *key_size_p,
2332 void **data_buf_p, int *data_size_p)
2334 table_entry_t *entry_p;
2337 if (table_p == NULL)
2338 return TABLE_ERROR_ARG_NULL;
2339 if (table_p->ta_magic != TABLE_MAGIC)
2340 return TABLE_ERROR_PNT;
2341 if (linear_p->tl_magic != LINEAR_MAGIC)
2342 return TABLE_ERROR_LINEAR;
2343 /* if we removed an item that shorted the bucket list, we may get this */
2344 if (linear_p->tl_bucket_c >= table_p->ta_bucket_n) {
2346 * NOTE: this might happen if we delete an item which shortens the
2347 * table bucket numbers.
2349 return TABLE_ERROR_NOT_FOUND;
2352 /* find the entry which is the nth in the list */
2353 for (entry_c = linear_p->tl_entry_c,
2354 entry_p = table_p->ta_buckets[linear_p->tl_bucket_c];
2355 entry_p != NULL && entry_c > 0;
2356 entry_c--, entry_p = TABLE_POINTER(table_p, table_entry_t *,
2357 entry_p)->te_next_p) {
2360 if (entry_p == NULL)
2361 return TABLE_ERROR_NOT_FOUND;
2362 if (key_buf_p != NULL)
2363 *key_buf_p = ENTRY_KEY_BUF(entry_p);
2364 if (key_size_p != NULL)
2365 *key_size_p = entry_p->te_key_size;
2366 if (data_buf_p != NULL) {
2367 if (entry_p->te_data_size == 0)
2370 if (table_p->ta_data_align == 0)
2371 *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
2373 *data_buf_p = entry_data_buf(table_p, entry_p);
2376 if (data_size_p != NULL)
2377 *data_size_p = entry_p->te_data_size;
2378 return TABLE_ERROR_NONE;
2381 /******************************** table order ********************************/
2384 * table_entry_t *table_order
2388 * Order a table by building an array of table entry pointers and then
2389 * sorting this array using the qsort function. To retrieve the
2390 * sorted entries, you can then use the table_entry routine to access
2391 * each entry in order.
2393 * NOTE: This routine is now thread safe in that two table_order calls
2394 * can now happen at the same time, even on the same table.
2398 * An allocated list of entry pointers which must be freed later.
2399 * Returns null on error.
2403 * table_p - Pointer to the table that we are ordering.
2405 * compare - Comparison function defined by the user. Its definition
2406 * is at the top of the table.h file. If this is NULL then it will
2407 * order the table my memcmp-ing the keys.
2409 * num_entries_p - Pointer to an integer which, if not NULL, will
2410 * contain the number of entries in the returned entry pointer array.
2412 * error_p - Pointer to an integer which, if not NULL, will contain a
2415 table_entry_t **table_order(table_t * table_p, table_compare_t compare,
2416 int *num_entries_p, int *error_p)
2418 table_entry_t *entry_p, **entries, **entries_p;
2419 table_linear_t linear;
2420 compare_t comp_func;
2423 if (table_p == NULL) {
2424 if (error_p != NULL)
2425 *error_p = TABLE_ERROR_ARG_NULL;
2428 if (table_p->ta_magic != TABLE_MAGIC) {
2429 if (error_p != NULL)
2430 *error_p = TABLE_ERROR_PNT;
2434 /* there must be at least 1 element in the table for this to work */
2435 if (table_p->ta_entry_n == 0) {
2436 if (error_p != NULL)
2437 *error_p = TABLE_ERROR_EMPTY;
2441 entries = (table_entry_t **)
2442 table_p->ta_malloc(table_p->opt_param,
2443 table_p->ta_entry_n *sizeof(table_entry_t *));
2444 if (entries == NULL) {
2445 if (error_p != NULL)
2446 *error_p = TABLE_ERROR_ALLOC;
2450 /* get a pointer to all entries */
2451 entry_p = first_entry(table_p, &linear);
2452 if (entry_p == NULL) {
2453 if (error_p != NULL)
2454 *error_p = TABLE_ERROR_NOT_FOUND;
2458 /* add all of the entries to the array */
2459 for (entries_p = entries;
2461 entry_p = next_entry(table_p, &linear, &error))
2462 *entries_p++ = entry_p;
2463 if (error != TABLE_ERROR_NOT_FOUND) {
2464 if (error_p != NULL)
2469 if (compare == NULL) {
2470 /* this is regardless of the alignment */
2471 comp_func = local_compare;
2473 else if (table_p->ta_data_align == 0)
2474 comp_func = external_compare;
2476 comp_func = external_compare_align;
2477 /* now qsort the entire entries array from first to last element */
2478 split(entries, entries + table_p->ta_entry_n - 1, comp_func, compare,
2481 if (num_entries_p != NULL)
2482 *num_entries_p = table_p->ta_entry_n;
2483 if (error_p != NULL)
2484 *error_p = TABLE_ERROR_NONE;
2493 * Get information about an element. The element is one from the
2494 * array returned by the table_order function. If any of the key/data
2495 * pointers are NULL then they are ignored.
2499 * Success - TABLE_ERROR_NONE
2501 * Failure - Table error code.
2505 * table_p - Table structure pointer from which we are getting the
2508 * entry_p - Pointer to a table entry from the array returned by the
2509 * table_order function.
2511 * key_buf_p - Pointer which, if not NULL, will be set to the address
2512 * of the storage of this entry that is allocated in the table. If an
2513 * (int) is stored as this entry (for example) then key_buf_p should
2514 * be (int **) i.e. the address of a (int *).
2516 * key_size_p - Pointer to an integer which, if not NULL, will be set
2517 * to the size of the key that is stored in the table.
2519 * data_buf_p - Pointer which, if not NULL, will be set to the address
2520 * of the data storage of this entry that is allocated in the table.
2521 * If a (long) is stored as this entry data (for example) then
2522 * data_buf_p should be (long **) i.e. the address of a (long *).
2524 * data_size_p - Pointer to an integer which, if not NULL, will be set
2525 * to the size of the data that is stored in the table.
2527 int table_entry_info(table_t * table_p, table_entry_t * entry_p,
2528 void **key_buf_p, int *key_size_p,
2529 void **data_buf_p, int *data_size_p)
2531 if (table_p == NULL)
2532 return TABLE_ERROR_ARG_NULL;
2533 if (table_p->ta_magic != TABLE_MAGIC)
2534 return TABLE_ERROR_PNT;
2535 if (entry_p == NULL)
2536 return TABLE_ERROR_ARG_NULL;
2537 if (key_buf_p != NULL)
2538 *key_buf_p = ENTRY_KEY_BUF(entry_p);
2539 if (key_size_p != NULL)
2540 *key_size_p = entry_p->te_key_size;
2541 if (data_buf_p != NULL) {
2542 if (entry_p->te_data_size == 0)
2545 if (table_p->ta_data_align == 0)
2546 *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
2548 *data_buf_p = entry_data_buf(table_p, entry_p);
2551 if (data_size_p != NULL)
2552 *data_size_p = entry_p->te_data_size;
2553 return TABLE_ERROR_NONE;