1 /* Licensed to the Apache Software Foundation (ASF) under one or more
2 * contributor license agreements. See the NOTICE file distributed with
3 * this work for additional information regarding copyright ownership.
4 * The ASF licenses this file to You under the Apache License, Version 2.0
5 * (the "License"); you may not use this file except in compliance with
6 * the License. You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
18 * _ __ ___ ___ __| | ___ ___| | mod_ssl
19 * | '_ ` _ \ / _ \ / _` | / __/ __| | Apache Interface to OpenSSL
20 * | | | | | | (_) | (_| | \__ \__ \ |
21 * |_| |_| |_|\___/ \__,_|___|___/___/_|
24 * High Performance Hash Table Functions
28 * Generic hash table handler
29 * Table 4.1.0 July-28-1998
31 * This library is a generic open hash table with buckets and
32 * linked lists. It is pretty high performance. Each element
33 * has a key and a data. The user indexes on the key to find the
36 * Copyright 1998 by Gray Watson <gray@letters.com>
38 * Permission to use, copy, modify, and distribute this software for any
39 * purpose and without fee is hereby granted, provided that the above
40 * copyright notice and this permission notice appear in all copies,
41 * and that the name of Gray Watson not be used in advertising or
42 * publicity pertaining to distribution of the document or software
43 * without specific, written prior permission.
45 * Gray Watson makes no representations about the suitability of the
46 * software described herein for any purpose. It is provided "as is"
47 * without express or implied warranty.
49 * Modified in March 1999 by Ralf S. Engelschall <rse@engelschall.com>
50 * for use in the mod_ssl project:
51 * o merged table_loc.h header into table.c
52 * o removed fillproto-comments from table.h
53 * o removed mmap() support because it's too unportable
54 * o added support for MM library via ta_{malloc,calloc,realloc,free}
60 /* forward definitions for table.h */
61 typedef struct table_st table_t;
62 typedef struct table_entry_st table_entry_t;
65 #include "ssl_util_table.h"
68 /****************************** local defines ******************************/
74 #define BITS(type) (BITSPERBYTE * (int)sizeof(type))
77 #define TABLE_MAGIC 0xBADF00D /* very magic magicness */
78 #define LINEAR_MAGIC 0xAD00D00 /* magic value for linear struct */
79 #define DEFAULT_SIZE 1024 /* default table size */
80 #define MAX_ALIGNMENT 128 /* max alignment value */
81 #define MAX_SORT_SPLITS 128 /* qsort can handle 2^128 entries */
83 /* returns 1 when we should grow or shrink the table */
84 #define SHOULD_TABLE_GROW(tab) ((tab)->ta_entry_n > (tab)->ta_bucket_n * 2)
85 #define SHOULD_TABLE_SHRINK(tab) ((tab)->ta_entry_n < (tab)->ta_bucket_n / 2)
92 * Mix 3 32-bit values reversibly. For every delta with one or two bits
93 * set, and the deltas of all three high bits or all three low bits,
94 * whether the original value of a,b,c is almost all zero or is
95 * uniformly distributed.
97 * If HASH_MIX() is run forward or backward, at least 32 bits in a,b,c
98 * have at least 1/4 probability of changing. If mix() is run
99 * forward, every bit of c will change between 1/3 and 2/3 of the
100 * time. (Well, 22/100 and 78/100 for some 2-bit deltas.)
102 * HASH_MIX() takes 36 machine instructions, but only 18 cycles on a
103 * superscalar machine (like a Pentium or a Sparc). No faster mixer
104 * seems to work, that's the result of my brute-force search. There
105 * were about 2^68 hashes to choose from. I only tested about a
108 #define HASH_MIX(a, b, c) \
110 a -= b; a -= c; a ^= (c >> 13); \
111 b -= c; b -= a; b ^= (a << 8); \
112 c -= a; c -= b; c ^= (b >> 13); \
113 a -= b; a -= c; a ^= (c >> 12); \
114 b -= c; b -= a; b ^= (a << 16); \
115 c -= a; c -= b; c ^= (b >> 5); \
116 a -= b; a -= c; a ^= (c >> 3); \
117 b -= c; b -= a; b ^= (a << 10); \
118 c -= a; c -= b; c ^= (b >> 15); \
121 #define TABLE_POINTER(table, type, pnt) (pnt)
124 * Macros to get at the key and the data pointers
126 #define ENTRY_KEY_BUF(entry_p) ((entry_p)->te_key_buf)
127 #define ENTRY_DATA_BUF(tab_p, entry_p) \
128 (ENTRY_KEY_BUF(entry_p) + (entry_p)->te_key_size)
131 * Table structures...
135 * HACK: this should be equiv as the table_entry_t without the key_buf
136 * char. We use this with the ENTRY_SIZE() macro above which solves
137 * the problem with the lack of the [0] GNU hack. We use the
138 * table_entry_t structure to better map the memory and make things
141 typedef struct table_shell_st {
142 unsigned int te_key_size; /* size of data */
143 unsigned int te_data_size; /* size of data */
144 struct table_shell_st *te_next_p; /* pointer to next in the list */
145 /* NOTE: this does not have the te_key_buf field here */
149 * Elements in the bucket linked-lists. The key[1] is the start of
150 * the key with the rest of the key and all of the data information
151 * packed in memory directly after the end of this structure.
153 * NOTE: if this structure is changed, the table_shell_t must be changed
156 struct table_entry_st {
157 unsigned int te_key_size; /* size of data */
158 unsigned int te_data_size; /* size of data */
159 struct table_entry_st *te_next_p; /* pointer to next in the list */
160 unsigned char te_key_buf[1]; /* 1st byte of key buf */
163 /* external structure for debuggers be able to see void */
164 typedef table_entry_t table_entry_ext_t;
166 /* main table structure */
168 unsigned int ta_magic; /* magic number */
169 unsigned int ta_flags; /* table's flags defined in table.h */
170 unsigned int ta_bucket_n; /* num of buckets, should be 2^X */
171 unsigned int ta_entry_n; /* num of entries in all buckets */
172 unsigned int ta_data_align; /* data alignment value */
173 table_entry_t **ta_buckets; /* array of linked lists */
174 table_linear_t ta_linear; /* linear tracking */
175 unsigned long ta_file_size; /* size of on-disk space */
176 void *(*ta_malloc)(void *opt_param, size_t size);
177 void *(*ta_calloc)(void *opt_param, size_t number, size_t size);
178 void *(*ta_realloc)(void *opt_param, void *ptr, size_t size);
179 void (*ta_free)(void *opt_param, void *ptr);
183 /* external table structure for debuggers */
184 typedef table_t table_ext_t;
186 /* local comparison functions */
187 typedef int (*compare_t) (const void *element1_p, const void *element2_p,
188 table_compare_t user_compare,
189 const table_t * table_p);
192 * to map error to string
195 int es_error; /* error number */
196 char *es_string; /* assocaited string */
199 static error_str_t errors[] =
201 {TABLE_ERROR_NONE, "no error"},
202 {TABLE_ERROR_PNT, "invalid table pointer"},
203 {TABLE_ERROR_ARG_NULL, "buffer argument is null"},
204 {TABLE_ERROR_SIZE, "incorrect size argument"},
205 {TABLE_ERROR_OVERWRITE, "key exists and no overwrite"},
206 {TABLE_ERROR_NOT_FOUND, "key does not exist"},
207 {TABLE_ERROR_ALLOC, "error allocating memory"},
208 {TABLE_ERROR_LINEAR, "linear access not in progress"},
209 {TABLE_ERROR_OPEN, "could not open file"},
210 {TABLE_ERROR_SEEK, "could not seek to position in file"},
211 {TABLE_ERROR_READ, "could not read from file"},
212 {TABLE_ERROR_WRITE, "could not write to file"},
213 {TABLE_ERROR_EMPTY, "table is empty"},
214 {TABLE_ERROR_NOT_EMPTY, "table contains data"},
215 {TABLE_ERROR_ALIGNMENT, "invalid alignment value"},
219 #define INVALID_ERROR "invalid error code"
222 /********************** wrappers for system functions ************************/
223 static void *sys_malloc(void *param, size_t size)
228 static void *sys_calloc(void *param, size_t size1, size_t size2)
230 return calloc(size1, size2);
233 static void *sys_realloc(void *param, void *ptr, size_t size)
235 return realloc(ptr, size);
238 static void sys_free(void *param, void *ptr)
243 /****************************** local functions ******************************/
246 * static table_entry_t *first_entry
250 * Return the first entry in the table. It will set the linear
251 * structure counter to the position of the first entry.
255 * Success: A pointer to the first entry in the table.
257 * Failure: NULL if there is no first entry.
261 * table_p - Table whose next entry we are finding.
263 * linear_p - Pointer to a linear structure which we will advance and
264 * then find the corresponding entry.
266 static table_entry_t *first_entry(table_t * table_p,
267 table_linear_t * linear_p)
269 table_entry_t *entry_p;
270 unsigned int bucket_c = 0;
272 /* look for the first non-empty bucket */
273 for (bucket_c = 0; bucket_c < table_p->ta_bucket_n; bucket_c++) {
274 entry_p = table_p->ta_buckets[bucket_c];
275 if (entry_p != NULL) {
276 if (linear_p != NULL) {
277 linear_p->tl_bucket_c = bucket_c;
278 linear_p->tl_entry_c = 0;
280 return TABLE_POINTER(table_p, table_entry_t *, entry_p);
288 * static table_entry_t *next_entry
292 * Return the next entry in the table which is past the position in
293 * our linear pointer. It will advance the linear structure counters.
297 * Success: A pointer to the next entry in the table.
303 * table_p - Table whose next entry we are finding.
305 * linear_p - Pointer to a linear structure which we will advance and
306 * then find the corresponding entry.
308 * error_p - Pointer to an integer which when the routine returns will
309 * contain a table error code.
311 static table_entry_t *next_entry(table_t * table_p, table_linear_t * linear_p,
314 table_entry_t *entry_p;
317 /* can't next if we haven't first-ed */
318 if (linear_p == NULL) {
320 *error_p = TABLE_ERROR_LINEAR;
324 if (linear_p->tl_bucket_c >= table_p->ta_bucket_n) {
326 * NOTE: this might happen if we delete an item which shortens the
327 * table bucket numbers.
330 *error_p = TABLE_ERROR_NOT_FOUND;
334 linear_p->tl_entry_c++;
336 /* find the entry which is the nth in the list */
337 entry_p = table_p->ta_buckets[linear_p->tl_bucket_c];
338 /* NOTE: we swap the order here to be more efficient */
339 for (entry_c = linear_p->tl_entry_c; entry_c > 0; entry_c--) {
340 /* did we reach the end of the list? */
343 entry_p = TABLE_POINTER(table_p, table_entry_t *, entry_p)->te_next_p;
346 /* did we find an entry in the current bucket? */
347 if (entry_p != NULL) {
349 *error_p = TABLE_ERROR_NONE;
350 return TABLE_POINTER(table_p, table_entry_t *, entry_p);
353 /* find the first entry in the next non-empty bucket */
355 linear_p->tl_entry_c = 0;
356 for (linear_p->tl_bucket_c++; linear_p->tl_bucket_c < table_p->ta_bucket_n;
357 linear_p->tl_bucket_c++) {
358 entry_p = table_p->ta_buckets[linear_p->tl_bucket_c];
359 if (entry_p != NULL) {
361 *error_p = TABLE_ERROR_NONE;
362 return TABLE_POINTER(table_p, table_entry_t *, entry_p);
367 *error_p = TABLE_ERROR_NOT_FOUND;
372 * static unsigned int hash
376 * Hash a variable-length key into a 32-bit value. Every bit of the
377 * key affects every bit of the return value. Every 1-bit and 2-bit
378 * delta achieves avalanche. About (6 * len + 35) instructions. The
379 * best hash table sizes are powers of 2. There is no need to use mod
380 * (sooo slow!). If you need less than 32 bits, use a bitmask. For
381 * example, if you need only 10 bits, do h = (h & hashmask(10)); In
382 * which case, the hash table should have hashsize(10) elements.
384 * By Bob Jenkins, 1996. bob_jenkins@compuserve.com. You may use
385 * this code any way you wish, private, educational, or commercial.
387 * http://ourworld.compuserve.com/homepages/bob_jenkins/evahash.htm
388 * Use for hash table lookup, or anything where one collision in 2^^32
389 * is acceptable. Do NOT use for cryptographic purposes.
393 * Returns a 32-bit hash value.
397 * key - Key (the unaligned variable-length array of bytes) that we
400 * length - Length of the key in bytes.
402 * init_val - Initialization value of the hash if you need to hash a
403 * number of strings together. For instance, if you are hashing N
404 * strings (unsigned char **)keys, do it like this:
406 * for (i=0, h=0; i<N; ++i) h = hash( keys[i], len[i], h);
408 static unsigned int hash(const unsigned char *key,
409 const unsigned int length,
410 const unsigned int init_val)
412 const unsigned char *key_p = key;
413 unsigned int a, b, c, len;
415 /* set up the internal state */
416 a = 0x9e3779b9; /* the golden ratio; an arbitrary value */
418 c = init_val; /* the previous hash value */
420 /* handle most of the key */
421 for (len = length; len >= 12; len -= 12) {
423 + ((unsigned long) key_p[1] << 8)
424 + ((unsigned long) key_p[2] << 16)
425 + ((unsigned long) key_p[3] << 24));
427 + ((unsigned long) key_p[5] << 8)
428 + ((unsigned long) key_p[6] << 16)
429 + ((unsigned long) key_p[7] << 24));
431 + ((unsigned long) key_p[9] << 8)
432 + ((unsigned long) key_p[10] << 16)
433 + ((unsigned long) key_p[11] << 24));
440 /* all the case statements fall through to the next */
443 c += ((unsigned long) key_p[10] << 24);
445 c += ((unsigned long) key_p[9] << 16);
447 c += ((unsigned long) key_p[8] << 8);
448 /* the first byte of c is reserved for the length */
450 b += ((unsigned long) key_p[7] << 24);
452 b += ((unsigned long) key_p[6] << 16);
454 b += ((unsigned long) key_p[5] << 8);
458 a += ((unsigned long) key_p[3] << 24);
460 a += ((unsigned long) key_p[2] << 16);
462 a += ((unsigned long) key_p[1] << 8);
465 /* case 0: nothing left to add */
473 * static int entry_size
477 * Calculates the appropriate size of an entry to include the key and
478 * data sizes as well as any associated alignment to the data.
482 * The associated size of the entry.
486 * table_p - Table associated with the entries whose size we are
489 * key_size - Size of the entry key.
491 * data - Size of the entry data.
493 static int entry_size(const table_t * table_p, const unsigned int key_size,
494 const unsigned int data_size)
498 /* initial size -- key is already aligned if right after struct */
499 size = sizeof(struct table_shell_st) + key_size;
501 /* if there is no alignment then it is easy */
502 if (table_p->ta_data_align == 0)
503 return size + data_size;
504 /* add in our alignement */
505 left = size & (table_p->ta_data_align - 1);
507 size += table_p->ta_data_align - left;
508 /* we add the data size here after the alignment */
515 * static unsigned char *entry_data_buf
519 * Companion to the ENTRY_DATA_BUF macro but this handles any
520 * associated alignment to the data in the entry.
524 * Pointer to the data segment of the entry.
528 * table_p - Table associated with the entry.
530 * entry_p - Entry whose data pointer we are determining.
532 static unsigned char *entry_data_buf(const table_t * table_p,
533 const table_entry_t * entry_p)
535 const unsigned char *buf_p;
538 buf_p = entry_p->te_key_buf + entry_p->te_key_size;
540 /* if there is no alignment then it is easy */
541 if (table_p->ta_data_align == 0)
542 return (unsigned char *) buf_p;
543 /* we need the size of the space before the data */
544 size = sizeof(struct table_shell_st) + entry_p->te_key_size;
546 /* add in our alignment */
547 pad = size & (table_p->ta_data_align - 1);
549 pad = table_p->ta_data_align - pad;
550 return (unsigned char *) buf_p + pad;
553 /******************************* sort routines *******************************/
556 * static int our_compare
560 * Compare two entries by calling user's compare program or by using
565 * < 0, == 0, or > 0 depending on whether p1 is > p2, == p2, < p2.
569 * p1 - First entry pointer to compare.
571 * p2 - Second entry pointer to compare.
573 * compare - User comparison function. Ignored.
575 * table_p - Associated table being ordered. Ignored.
577 static int local_compare(const void *p1, const void *p2,
578 table_compare_t compare, const table_t * table_p)
580 const table_entry_t *const *ent1_p = p1, *const *ent2_p = p2;
584 /* compare as many bytes as we can */
585 size = (*ent1_p)->te_key_size;
586 if ((*ent2_p)->te_key_size < size)
587 size = (*ent2_p)->te_key_size;
588 cmp = memcmp(ENTRY_KEY_BUF(*ent1_p), ENTRY_KEY_BUF(*ent2_p), size);
589 /* if common-size equal, then if next more bytes, it is larger */
591 cmp = (*ent1_p)->te_key_size - (*ent2_p)->te_key_size;
596 * static int external_compare
600 * Compare two entries by calling user's compare program or by using
605 * < 0, == 0, or > 0 depending on whether p1 is > p2, == p2, < p2.
609 * p1 - First entry pointer to compare.
611 * p2 - Second entry pointer to compare.
613 * user_compare - User comparison function.
615 * table_p - Associated table being ordered.
617 static int external_compare(const void *p1, const void *p2,
618 table_compare_t user_compare,
619 const table_t * table_p)
621 const table_entry_t *const *ent1_p = p1, *const *ent2_p = p2;
622 /* since we know we are not aligned we can use the EXTRY_DATA_BUF macro */
623 return user_compare(ENTRY_KEY_BUF(*ent1_p), (*ent1_p)->te_key_size,
624 ENTRY_DATA_BUF(table_p, *ent1_p),
625 (*ent1_p)->te_data_size,
626 ENTRY_KEY_BUF(*ent2_p), (*ent2_p)->te_key_size,
627 ENTRY_DATA_BUF(table_p, *ent2_p),
628 (*ent2_p)->te_data_size);
632 * static int external_compare_align
636 * Compare two entries by calling user's compare program or by using
637 * memcmp. Alignment information is necessary.
641 * < 0, == 0, or > 0 depending on whether p1 is > p2, == p2, < p2.
645 * p1 - First entry pointer to compare.
647 * p2 - Second entry pointer to compare.
649 * user_compare - User comparison function.
651 * table_p - Associated table being ordered.
653 static int external_compare_align(const void *p1, const void *p2,
654 table_compare_t user_compare,
655 const table_t * table_p)
657 const table_entry_t *const *ent1_p = p1, *const *ent2_p = p2;
658 /* since we are aligned we have to use the entry_data_buf function */
659 return user_compare(ENTRY_KEY_BUF(*ent1_p), (*ent1_p)->te_key_size,
660 entry_data_buf(table_p, *ent1_p),
661 (*ent1_p)->te_data_size,
662 ENTRY_KEY_BUF(*ent2_p), (*ent2_p)->te_key_size,
663 entry_data_buf(table_p, *ent2_p),
664 (*ent2_p)->te_data_size);
672 * This sorts an array of longs via the quick sort algorithm (it's
681 * first_p - Start of the list that we are splitting.
683 * last_p - Last entry in the list that we are splitting.
685 * compare - Comparison function which is handling the actual
686 * elements. This is either a local function or a function to setup
687 * the problem element key and data pointers which then hands off to
690 * user_compare - User comparison function. Could be NULL if we are
691 * just using a local comparison function.
693 * table_p - Associated table being sorted.
695 static void split(void *first_p, void *last_p, compare_t compare,
696 table_compare_t user_compare, table_t * table_p)
698 void *pivot_p, *left_p, *right_p, *left_last_p, *right_first_p;
699 void *firsts[MAX_SORT_SPLITS], *lasts[MAX_SORT_SPLITS];
704 /* no need to split the list if it is < 2 elements */
705 while (first_p >= last_p) {
711 first_p = firsts[split_c];
712 last_p = lasts[split_c];
720 /* scan from right hand side */
721 while (right_p > left_p
722 && compare(right_p, pivot_p, user_compare, table_p) > 0)
723 right_p = (char *) right_p - sizeof(table_entry_t *);
724 /* scan from left hand side */
725 while (right_p > left_p
726 && compare(pivot_p, left_p, user_compare, table_p) >= 0)
727 left_p = (char *) left_p + sizeof(table_entry_t *);
728 /* if the pointers haven't met then swap values */
729 if (right_p > left_p) {
730 /* swap_bytes(left_p, right_p) */
733 temp = *(table_entry_t **) left_p;
734 *(table_entry_t **) left_p = *(table_entry_t **) right_p;
735 *(table_entry_t **) right_p = temp;
737 } while (right_p > left_p);
739 /* now we swap the pivot with the right-hand side */
741 /* swap_bytes(pivot_p, right_p); */
744 temp = *(table_entry_t **) pivot_p;
745 *(table_entry_t **) pivot_p = *(table_entry_t **) right_p;
746 *(table_entry_t **) right_p = temp;
750 /* save the section to the right of the pivot in our stack */
751 right_first_p = (char *) pivot_p + sizeof(table_entry_t *);
752 left_last_p = (char *) pivot_p - sizeof(table_entry_t *);
754 /* do we need to save the righthand side? */
755 if (right_first_p < last_p) {
756 if (split_c >= MAX_SORT_SPLITS) {
757 /* sanity check here -- we should never get here */
760 firsts[split_c] = right_first_p;
761 lasts[split_c] = last_p;
765 /* do the left hand side of the pivot */
766 /* first_p = first_p */
767 last_p = left_last_p;
771 /*************************** exported routines *******************************/
774 * table_t *table_alloc
778 * Allocate a new table structure.
782 * A pointer to the new table structure which must be passed to
783 * table_free to be deallocated. On error a NULL is returned.
787 * bucket_n - Number of buckets for the hash table. Our current hash
788 * value works best with base two numbers. Set to 0 to take the
789 * library default of 1024.
791 * error_p - Pointer to an integer which, if not NULL, will contain a
794 * malloc_f, realloc_f, free_f - Pointers to malloc(3)-, realloc(3)-
795 * and free(3)-style functions.
797 table_t *table_alloc(const unsigned int bucket_n, int *error_p,
798 void *(*malloc_f)(void *opt_param, size_t size),
799 void *(*calloc_f)(void *opt_param, size_t number, size_t size),
800 void *(*realloc_f)(void *opt_param, void *ptr, size_t size),
801 void (*free_f)(void *opt_param, void *ptr), void *opt_param)
803 table_t *table_p = NULL;
806 /* allocate a table structure */
807 if (malloc_f != NULL)
808 table_p = malloc_f(opt_param, sizeof(table_t));
810 table_p = malloc(sizeof(table_t));
811 if (table_p == NULL) {
813 *error_p = TABLE_ERROR_ALLOC;
820 buck_n = DEFAULT_SIZE;
821 /* allocate the buckets which are NULLed */
822 if (calloc_f != NULL)
823 table_p->ta_buckets = (table_entry_t **)calloc_f(opt_param, buck_n,
824 sizeof(table_entry_t *));
826 table_p->ta_buckets = (table_entry_t **)calloc(buck_n, sizeof(table_entry_t *));
827 if (table_p->ta_buckets == NULL) {
829 *error_p = TABLE_ERROR_ALLOC;
831 free_f(opt_param, table_p);
837 /* initialize structure */
838 table_p->ta_magic = TABLE_MAGIC;
839 table_p->ta_flags = 0;
840 table_p->ta_bucket_n = buck_n;
841 table_p->ta_entry_n = 0;
842 table_p->ta_data_align = 0;
843 table_p->ta_linear.tl_magic = 0;
844 table_p->ta_linear.tl_bucket_c = 0;
845 table_p->ta_linear.tl_entry_c = 0;
846 table_p->ta_file_size = 0;
847 table_p->ta_malloc = malloc_f != NULL ? malloc_f : sys_malloc;
848 table_p->ta_calloc = calloc_f != NULL ? calloc_f : sys_calloc;
849 table_p->ta_realloc = realloc_f != NULL ? realloc_f : sys_realloc;
850 table_p->ta_free = free_f != NULL ? free_f : sys_free;
851 table_p->opt_param = opt_param;
854 *error_p = TABLE_ERROR_NONE;
863 * Set the attributes for the table. The available attributes are
864 * specified at the top of table.h.
868 * Success - TABLE_ERROR_NONE
870 * Failure - Table error code.
874 * table_p - Pointer to a table structure which we will be altering.
876 * attr - Attribute(s) that we will be applying to the table.
878 int table_attr(table_t * table_p, const int attr)
881 return TABLE_ERROR_ARG_NULL;
882 if (table_p->ta_magic != TABLE_MAGIC)
883 return TABLE_ERROR_PNT;
884 table_p->ta_flags = attr;
886 return TABLE_ERROR_NONE;
890 * int table_set_data_alignment
894 * Set the alignment for the data in the table. For data elements
895 * sizeof(long) is recommended unless you use smaller data types
898 * WARNING: This must be done before any data gets put into the table.
902 * Success - TABLE_ERROR_NONE
904 * Failure - Table error code.
908 * table_p - Pointer to a table structure which we will be altering.
910 * alignment - Alignment requested for the data. Must be a power of
911 * 2. Set to 0 for none.
913 int table_set_data_alignment(table_t * table_p, const int alignment)
918 return TABLE_ERROR_ARG_NULL;
919 if (table_p->ta_magic != TABLE_MAGIC)
920 return TABLE_ERROR_PNT;
921 if (table_p->ta_entry_n > 0)
922 return TABLE_ERROR_NOT_EMPTY;
925 table_p->ta_data_align = 0;
927 /* verify we have a base 2 number */
928 for (val = 2; val < MAX_ALIGNMENT; val *= 2) {
929 if (val == alignment)
932 if (val >= MAX_ALIGNMENT)
933 return TABLE_ERROR_ALIGNMENT;
934 table_p->ta_data_align = alignment;
937 return TABLE_ERROR_NONE;
945 * Clear out and free all elements in a table structure.
949 * Success - TABLE_ERROR_NONE
951 * Failure - Table error code.
955 * table_p - Table structure pointer that we will be clearing.
957 int table_clear(table_t * table_p)
959 table_entry_t *entry_p, *next_p;
960 table_entry_t **bucket_p, **bounds_p;
963 return TABLE_ERROR_ARG_NULL;
964 if (table_p->ta_magic != TABLE_MAGIC)
965 return TABLE_ERROR_PNT;
966 /* free the table allocation and table structure */
967 bounds_p = table_p->ta_buckets + table_p->ta_bucket_n;
968 for (bucket_p = table_p->ta_buckets; bucket_p < bounds_p; bucket_p++) {
969 for (entry_p = *bucket_p; entry_p != NULL; entry_p = next_p) {
970 /* record the next pointer before we free */
971 next_p = entry_p->te_next_p;
972 table_p->ta_free(table_p->opt_param, entry_p);
974 /* clear the bucket entry after we free its entries */
978 /* reset table state info */
979 table_p->ta_entry_n = 0;
980 table_p->ta_linear.tl_magic = 0;
981 table_p->ta_linear.tl_bucket_c = 0;
982 table_p->ta_linear.tl_entry_c = 0;
984 return TABLE_ERROR_NONE;
992 * Deallocates a table structure.
996 * Success - TABLE_ERROR_NONE
998 * Failure - Table error code.
1002 * table_p - Table structure pointer that we will be freeing.
1004 int table_free(table_t * table_p)
1008 if (table_p == NULL)
1009 return TABLE_ERROR_ARG_NULL;
1010 if (table_p->ta_magic != TABLE_MAGIC)
1011 return TABLE_ERROR_PNT;
1012 ret = table_clear(table_p);
1014 if (table_p->ta_buckets != NULL)
1015 table_p->ta_free(table_p->opt_param, table_p->ta_buckets);
1016 table_p->ta_magic = 0;
1017 table_p->ta_free(table_p->opt_param, table_p);
1023 * int table_insert_kd
1027 * Like table_insert except it passes back a pointer to the key and
1028 * the data buffers after they have been inserted into the table
1031 * This routine adds a key/data pair both of which are made up of a
1032 * buffer of bytes and an associated size. Both the key and the data
1033 * will be copied into buffers allocated inside the table. If the key
1034 * exists already, the associated data will be replaced if the
1035 * overwrite flag is set, otherwise an error is returned.
1037 * NOTE: be very careful changing the values since the table library
1038 * provides the pointers to its memory. The key can _never_ be
1039 * changed otherwise you will not find it again. The data can be
1040 * changed but its length can never be altered unless you delete and
1041 * re-insert it into the table.
1043 * WARNING: The pointers to the key and data are not in any specific
1044 * alignment. Accessing the key and/or data as an short, integer, or
1045 * long pointer directly can cause problems.
1047 * WARNING: Replacing a data cell (not inserting) will cause the table
1048 * linked list to be temporarily invalid. Care must be taken with
1049 * multiple threaded programs which are relying on the first/next
1050 * linked list to be always valid.
1054 * Success - TABLE_ERROR_NONE
1056 * Failure - Table error code.
1060 * table_p - Table structure pointer into which we will be inserting a
1061 * new key/data pair.
1063 * key_buf - Buffer of bytes of the key that we are inserting. If you
1064 * are storing an (int) as the key (for example) then key_buf should
1067 * key_size - Size of the key_buf buffer. If set to < 0 then the
1068 * library will do a strlen of key_buf and add 1 for the '\0'. If you
1069 * are storing an (int) as the key (for example) then key_size should
1072 * data_buf - Buffer of bytes of the data that we are inserting. If
1073 * it is NULL then the library will allocate space for the data in the
1074 * table without copying in any information. If data_buf is NULL and
1075 * data_size is 0 then the library will associate a NULL data pointer
1076 * with the key. If you are storing a (long) as the data (for
1077 * example) then data_buf should be a (long *).
1079 * data_size - Size of the data_buf buffer. If set to < 0 then the
1080 * library will do a strlen of data_buf and add 1 for the '\0'. If
1081 * you are storing an (long) as the key (for example) then key_size
1082 * should be sizeof(long).
1084 * key_buf_p - Pointer which, if not NULL, will be set to the address
1085 * of the key storage that was allocated in the table. If you are
1086 * storing an (int) as the key (for example) then key_buf_p should be
1087 * (int **) i.e. the address of a (int *).
1089 * data_buf_p - Pointer which, if not NULL, will be set to the address
1090 * of the data storage that was allocated in the table. If you are
1091 * storing an (long) as the data (for example) then data_buf_p should
1092 * be (long **) i.e. the address of a (long *).
1094 * overwrite - Flag which, if set to 1, will allow the overwriting of
1095 * the data in the table with the new data if the key already exists
1098 int table_insert_kd(table_t * table_p,
1099 const void *key_buf, const int key_size,
1100 const void *data_buf, const int data_size,
1101 void **key_buf_p, void **data_buf_p,
1102 const char overwrite_b)
1105 unsigned int ksize, dsize;
1106 table_entry_t *entry_p, *last_p;
1107 void *key_copy_p, *data_copy_p;
1109 /* check the arguments */
1110 if (table_p == NULL)
1111 return TABLE_ERROR_ARG_NULL;
1112 if (table_p->ta_magic != TABLE_MAGIC)
1113 return TABLE_ERROR_PNT;
1114 if (key_buf == NULL)
1115 return TABLE_ERROR_ARG_NULL;
1116 /* data_buf can be null but size must be >= 0, if it isn't null size != 0 */
1117 if ((data_buf == NULL && data_size < 0)
1118 || (data_buf != NULL && data_size == 0))
1119 return TABLE_ERROR_SIZE;
1120 /* determine sizes of key and data */
1122 ksize = strlen((char *) key_buf) + sizeof(char);
1126 dsize = strlen((char *) data_buf) + sizeof(char);
1129 /* get the bucket number via a hash function */
1130 bucket = hash(key_buf, ksize, 0) % table_p->ta_bucket_n;
1132 /* look for the entry in this bucket, only check keys of the same size */
1134 for (entry_p = table_p->ta_buckets[bucket];
1135 (entry_p != NULL) && (entry_p->te_next_p != last_p);
1136 last_p = entry_p, entry_p = entry_p->te_next_p) {
1137 if (entry_p->te_key_size == ksize
1138 && memcmp(ENTRY_KEY_BUF(entry_p), key_buf, ksize) == 0)
1142 /* did we find it? then we are in replace mode. */
1143 if (entry_p != NULL) {
1145 /* can we not overwrite existing data? */
1147 if (key_buf_p != NULL)
1148 *key_buf_p = ENTRY_KEY_BUF(entry_p);
1149 if (data_buf_p != NULL) {
1150 if (entry_p->te_data_size == 0)
1153 if (table_p->ta_data_align == 0)
1154 *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
1156 *data_buf_p = entry_data_buf(table_p, entry_p);
1159 return TABLE_ERROR_OVERWRITE;
1162 /* re-alloc entry's data if the new size != the old */
1163 if (dsize != entry_p->te_data_size) {
1166 * First we delete it from the list to keep the list whole.
1167 * This properly preserves the linked list in case we have a
1168 * thread marching through the linked list while we are
1169 * inserting. Maybe this is an unnecessary protection but it
1170 * should not harm that much.
1173 table_p->ta_buckets[bucket] = entry_p->te_next_p;
1175 last_p->te_next_p = entry_p->te_next_p;
1177 * Realloc the structure which may change its pointer. NOTE:
1178 * this may change any previous data_key_p and data_copy_p
1181 entry_p = (table_entry_t *)
1182 table_p->ta_realloc(table_p->opt_param, entry_p,
1183 entry_size(table_p, entry_p->te_key_size, dsize));
1184 if (entry_p == NULL)
1185 return TABLE_ERROR_ALLOC;
1186 /* add it back to the front of the list */
1187 entry_p->te_data_size = dsize;
1188 entry_p->te_next_p = table_p->ta_buckets[bucket];
1189 table_p->ta_buckets[bucket] = entry_p;
1192 /* copy or replace data in storage */
1194 if (table_p->ta_data_align == 0)
1195 data_copy_p = ENTRY_DATA_BUF(table_p, entry_p);
1197 data_copy_p = entry_data_buf(table_p, entry_p);
1198 if (data_buf != NULL)
1199 memcpy(data_copy_p, data_buf, dsize);
1203 if (key_buf_p != NULL)
1204 *key_buf_p = ENTRY_KEY_BUF(entry_p);
1205 if (data_buf_p != NULL)
1206 *data_buf_p = data_copy_p;
1207 /* returning from the section where we were overwriting table data */
1208 return TABLE_ERROR_NONE;
1212 * It is a new entry.
1215 /* allocate a new entry */
1216 entry_p = (table_entry_t *)
1217 table_p->ta_malloc(table_p->opt_param,
1218 entry_size(table_p, ksize, dsize));
1219 if (entry_p == NULL)
1220 return TABLE_ERROR_ALLOC;
1221 /* copy key into storage */
1222 entry_p->te_key_size = ksize;
1223 key_copy_p = ENTRY_KEY_BUF(entry_p);
1224 memcpy(key_copy_p, key_buf, ksize);
1227 entry_p->te_data_size = dsize;
1229 if (table_p->ta_data_align == 0)
1230 data_copy_p = ENTRY_DATA_BUF(table_p, entry_p);
1232 data_copy_p = entry_data_buf(table_p, entry_p);
1233 if (data_buf != NULL)
1234 memcpy(data_copy_p, data_buf, dsize);
1238 if (key_buf_p != NULL)
1239 *key_buf_p = key_copy_p;
1240 if (data_buf_p != NULL)
1241 *data_buf_p = data_copy_p;
1242 /* insert into list, no need to append */
1243 entry_p->te_next_p = table_p->ta_buckets[bucket];
1244 table_p->ta_buckets[bucket] = entry_p;
1246 table_p->ta_entry_n++;
1248 /* do we need auto-adjust? */
1249 if (table_p->ta_flags & TABLE_FLAG_AUTO_ADJUST
1250 && SHOULD_TABLE_GROW(table_p))
1251 return table_adjust(table_p, table_p->ta_entry_n);
1252 return TABLE_ERROR_NONE;
1260 * Exactly the same as table_insert_kd except it does not pass back a
1261 * pointer to the key after they have been inserted into the table
1262 * structure. This is still here for backwards compatibility.
1264 * See table_insert_kd for more information.
1268 * Success - TABLE_ERROR_NONE
1270 * Failure - Table error code.
1274 * table_p - Table structure pointer into which we will be inserting a
1275 * new key/data pair.
1277 * key_buf - Buffer of bytes of the key that we are inserting. If you
1278 * are storing an (int) as the key (for example) then key_buf should
1281 * key_size - Size of the key_buf buffer. If set to < 0 then the
1282 * library will do a strlen of key_buf and add 1 for the '\0'. If you
1283 * are storing an (int) as the key (for example) then key_size should
1286 * data_buf - Buffer of bytes of the data that we are inserting. If
1287 * it is NULL then the library will allocate space for the data in the
1288 * table without copying in any information. If data_buf is NULL and
1289 * data_size is 0 then the library will associate a NULL data pointer
1290 * with the key. If you are storing a (long) as the data (for
1291 * example) then data_buf should be a (long *).
1293 * data_size - Size of the data_buf buffer. If set to < 0 then the
1294 * library will do a strlen of data_buf and add 1 for the '\0'. If
1295 * you are storing an (long) as the key (for example) then key_size
1296 * should be sizeof(long).
1298 * data_buf_p - Pointer which, if not NULL, will be set to the address
1299 * of the data storage that was allocated in the table. If you are
1300 * storing an (long) as the data (for example) then data_buf_p should
1301 * be (long **) i.e. the address of a (long *).
1303 * overwrite - Flag which, if set to 1, will allow the overwriting of
1304 * the data in the table with the new data if the key already exists
1307 int table_insert(table_t * table_p,
1308 const void *key_buf, const int key_size,
1309 const void *data_buf, const int data_size,
1310 void **data_buf_p, const char overwrite_b)
1312 return table_insert_kd(table_p, key_buf, key_size, data_buf, data_size,
1313 NULL, data_buf_p, overwrite_b);
1317 * int table_retrieve
1321 * This routine looks up a key made up of a buffer of bytes and an
1322 * associated size in the table. If found then it returns the
1323 * associated data information.
1327 * Success - TABLE_ERROR_NONE
1329 * Failure - Table error code.
1333 * table_p - Table structure pointer into which we will be searching
1336 * key_buf - Buffer of bytes of the key that we are searching for. If
1337 * you are looking for an (int) as the key (for example) then key_buf
1338 * should be a (int *).
1340 * key_size - Size of the key_buf buffer. If set to < 0 then the
1341 * library will do a strlen of key_buf and add 1 for the '\0'. If you
1342 * are looking for an (int) as the key (for example) then key_size
1343 * should be sizeof(int).
1345 * data_buf_p - Pointer which, if not NULL, will be set to the address
1346 * of the data storage that was allocated in the table and that is
1347 * associated with the key. If a (long) was stored as the data (for
1348 * example) then data_buf_p should be (long **) i.e. the address of a
1351 * data_size_p - Pointer to an integer which, if not NULL, will be set
1352 * to the size of the data stored in the table that is associated with
1355 int table_retrieve(table_t * table_p,
1356 const void *key_buf, const int key_size,
1357 void **data_buf_p, int *data_size_p)
1361 table_entry_t *entry_p, **buckets;
1363 if (table_p == NULL)
1364 return TABLE_ERROR_ARG_NULL;
1365 if (table_p->ta_magic != TABLE_MAGIC)
1366 return TABLE_ERROR_PNT;
1367 if (key_buf == NULL)
1368 return TABLE_ERROR_ARG_NULL;
1371 ksize = strlen((char *) key_buf) + sizeof(char);
1374 /* get the bucket number via a has function */
1375 bucket = hash(key_buf, ksize, 0) % table_p->ta_bucket_n;
1377 /* look for the entry in this bucket, only check keys of the same size */
1378 buckets = table_p->ta_buckets;
1379 for (entry_p = buckets[bucket];
1381 entry_p = entry_p->te_next_p) {
1382 entry_p = TABLE_POINTER(table_p, table_entry_t *, entry_p);
1383 if (entry_p->te_key_size == ksize
1384 && memcmp(ENTRY_KEY_BUF(entry_p), key_buf, ksize) == 0)
1389 if (entry_p == NULL)
1390 return TABLE_ERROR_NOT_FOUND;
1391 if (data_buf_p != NULL) {
1392 if (entry_p->te_data_size == 0)
1395 if (table_p->ta_data_align == 0)
1396 *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
1398 *data_buf_p = entry_data_buf(table_p, entry_p);
1401 if (data_size_p != NULL)
1402 *data_size_p = entry_p->te_data_size;
1403 return TABLE_ERROR_NONE;
1411 * This routine looks up a key made up of a buffer of bytes and an
1412 * associated size in the table. If found then it will be removed
1413 * from the table. The associated data can be passed back to the user
1418 * Success - TABLE_ERROR_NONE
1420 * Failure - Table error code.
1422 * NOTE: this could be an allocation error if the library is to return
1423 * the data to the user.
1427 * table_p - Table structure pointer from which we will be deleteing
1430 * key_buf - Buffer of bytes of the key that we are searching for to
1431 * delete. If you are deleting an (int) key (for example) then
1432 * key_buf should be a (int *).
1434 * key_size - Size of the key_buf buffer. If set to < 0 then the
1435 * library will do a strlen of key_buf and add 1 for the '\0'. If you
1436 * are deleting an (int) key (for example) then key_size should be
1439 * data_buf_p - Pointer which, if not NULL, will be set to the address
1440 * of the data storage that was allocated in the table and that was
1441 * associated with the key. If a (long) was stored as the data (for
1442 * example) then data_buf_p should be (long **) i.e. the address of a
1443 * (long *). If a pointer is passed in, the caller is responsible for
1444 * freeing it after use. If data_buf_p is NULL then the library will
1445 * free up the data allocation itself.
1447 * data_size_p - Pointer to an integer which, if not NULL, will be set
1448 * to the size of the data that was stored in the table and that was
1449 * associated with the key.
1451 int table_delete(table_t * table_p,
1452 const void *key_buf, const int key_size,
1453 void **data_buf_p, int *data_size_p)
1457 unsigned char *data_copy_p;
1458 table_entry_t *entry_p, *last_p;
1460 if (table_p == NULL)
1461 return TABLE_ERROR_ARG_NULL;
1462 if (table_p->ta_magic != TABLE_MAGIC)
1463 return TABLE_ERROR_PNT;
1464 if (key_buf == NULL)
1465 return TABLE_ERROR_ARG_NULL;
1466 /* get the key size */
1468 ksize = strlen((char *) key_buf) + sizeof(char);
1471 /* find our bucket */
1472 bucket = hash(key_buf, ksize, 0) % table_p->ta_bucket_n;
1474 /* look for the entry in this bucket, only check keys of the same size */
1475 for (last_p = NULL, entry_p = table_p->ta_buckets[bucket]; entry_p != NULL;
1476 last_p = entry_p, entry_p = entry_p->te_next_p) {
1477 if (entry_p->te_key_size == ksize
1478 && memcmp(ENTRY_KEY_BUF(entry_p), key_buf, ksize) == 0)
1482 /* did we find it? */
1483 if (entry_p == NULL)
1484 return TABLE_ERROR_NOT_FOUND;
1486 * NOTE: we may want to adjust the linear counters here if the entry
1487 * we are deleting is the one we are pointing on or is ahead of the
1488 * one in the bucket list
1491 /* remove entry from the linked list */
1493 table_p->ta_buckets[bucket] = entry_p->te_next_p;
1495 last_p->te_next_p = entry_p->te_next_p;
1497 if (data_buf_p != NULL) {
1498 if (entry_p->te_data_size == 0)
1502 * if we were storing it compacted, we now need to malloc some
1503 * space if the user wants the value after the delete.
1505 *data_buf_p = table_p->ta_malloc(table_p->opt_param,
1506 entry_p->te_data_size);
1507 if (*data_buf_p == NULL)
1508 return TABLE_ERROR_ALLOC;
1509 if (table_p->ta_data_align == 0)
1510 data_copy_p = ENTRY_DATA_BUF(table_p, entry_p);
1512 data_copy_p = entry_data_buf(table_p, entry_p);
1513 memcpy(*data_buf_p, data_copy_p, entry_p->te_data_size);
1516 if (data_size_p != NULL)
1517 *data_size_p = entry_p->te_data_size;
1518 table_p->ta_free(table_p->opt_param, entry_p);
1521 table_p->ta_entry_n--;
1523 /* do we need auto-adjust down? */
1524 if ((table_p->ta_flags & TABLE_FLAG_AUTO_ADJUST)
1525 && (table_p->ta_flags & TABLE_FLAG_ADJUST_DOWN)
1526 && SHOULD_TABLE_SHRINK(table_p))
1527 return table_adjust(table_p, table_p->ta_entry_n);
1528 return TABLE_ERROR_NONE;
1532 * int table_delete_first
1536 * This is like the table_delete routines except it deletes the first
1537 * key/data pair in the table instead of an entry corresponding to a
1538 * particular key. The associated key and data information can be
1539 * passed back to the user if requested. This routines is handy to
1540 * clear out a table.
1544 * Success - TABLE_ERROR_NONE
1546 * Failure - Table error code.
1548 * NOTE: this could be an allocation error if the library is to return
1549 * the data to the user.
1553 * table_p - Table structure pointer from which we will be deleteing
1556 * key_buf_p - Pointer which, if not NULL, will be set to the address
1557 * of the storage of the first key that was allocated in the table.
1558 * If an (int) was stored as the first key (for example) then
1559 * key_buf_p should be (int **) i.e. the address of a (int *). If a
1560 * pointer is passed in, the caller is responsible for freeing it
1561 * after use. If key_buf_p is NULL then the library will free up the
1562 * key allocation itself.
1564 * key_size_p - Pointer to an integer which, if not NULL, will be set
1565 * to the size of the key that was stored in the table and that was
1566 * associated with the key.
1568 * data_buf_p - Pointer which, if not NULL, will be set to the address
1569 * of the data storage that was allocated in the table and that was
1570 * associated with the key. If a (long) was stored as the data (for
1571 * example) then data_buf_p should be (long **) i.e. the address of a
1572 * (long *). If a pointer is passed in, the caller is responsible for
1573 * freeing it after use. If data_buf_p is NULL then the library will
1574 * free up the data allocation itself.
1576 * data_size_p - Pointer to an integer which, if not NULL, will be set
1577 * to the size of the data that was stored in the table and that was
1578 * associated with the key.
1580 int table_delete_first(table_t * table_p,
1581 void **key_buf_p, int *key_size_p,
1582 void **data_buf_p, int *data_size_p)
1584 unsigned char *data_copy_p;
1585 table_entry_t *entry_p;
1586 table_linear_t linear;
1588 if (table_p == NULL)
1589 return TABLE_ERROR_ARG_NULL;
1590 if (table_p->ta_magic != TABLE_MAGIC)
1591 return TABLE_ERROR_PNT;
1592 /* take the first entry */
1593 entry_p = first_entry(table_p, &linear);
1594 if (entry_p == NULL)
1595 return TABLE_ERROR_NOT_FOUND;
1597 * NOTE: we may want to adjust the linear counters here if the entry
1598 * we are deleting is the one we are pointing on or is ahead of the
1599 * one in the bucket list
1602 /* remove entry from the linked list */
1603 table_p->ta_buckets[linear.tl_bucket_c] = entry_p->te_next_p;
1606 if (key_buf_p != NULL) {
1607 if (entry_p->te_key_size == 0)
1611 * if we were storing it compacted, we now need to malloc some
1612 * space if the user wants the value after the delete.
1614 *key_buf_p = table_p->ta_malloc(table_p->opt_param,
1615 entry_p->te_key_size);
1616 if (*key_buf_p == NULL)
1617 return TABLE_ERROR_ALLOC;
1618 memcpy(*key_buf_p, ENTRY_KEY_BUF(entry_p), entry_p->te_key_size);
1621 if (key_size_p != NULL)
1622 *key_size_p = entry_p->te_key_size;
1623 if (data_buf_p != NULL) {
1624 if (entry_p->te_data_size == 0)
1628 * if we were storing it compacted, we now need to malloc some
1629 * space if the user wants the value after the delete.
1631 *data_buf_p = table_p->ta_malloc(table_p->opt_param,
1632 entry_p->te_data_size);
1633 if (*data_buf_p == NULL)
1634 return TABLE_ERROR_ALLOC;
1635 if (table_p->ta_data_align == 0)
1636 data_copy_p = ENTRY_DATA_BUF(table_p, entry_p);
1638 data_copy_p = entry_data_buf(table_p, entry_p);
1639 memcpy(*data_buf_p, data_copy_p, entry_p->te_data_size);
1642 if (data_size_p != NULL)
1643 *data_size_p = entry_p->te_data_size;
1644 table_p->ta_free(table_p->opt_param, entry_p);
1646 table_p->ta_entry_n--;
1648 /* do we need auto-adjust down? */
1649 if ((table_p->ta_flags & TABLE_FLAG_AUTO_ADJUST)
1650 && (table_p->ta_flags & TABLE_FLAG_ADJUST_DOWN)
1651 && SHOULD_TABLE_SHRINK(table_p))
1652 return table_adjust(table_p, table_p->ta_entry_n);
1653 return TABLE_ERROR_NONE;
1661 * Get some information about a table_p structure.
1665 * Success - TABLE_ERROR_NONE
1667 * Failure - Table error code.
1671 * table_p - Table structure pointer from which we are getting
1674 * num_buckets_p - Pointer to an integer which, if not NULL, will
1675 * contain the number of buckets in the table.
1677 * num_entries_p - Pointer to an integer which, if not NULL, will
1678 * contain the number of entries stored in the table.
1680 int table_info(table_t * table_p, int *num_buckets_p, int *num_entries_p)
1682 if (table_p == NULL)
1683 return TABLE_ERROR_ARG_NULL;
1684 if (table_p->ta_magic != TABLE_MAGIC)
1685 return TABLE_ERROR_PNT;
1686 if (num_buckets_p != NULL)
1687 *num_buckets_p = table_p->ta_bucket_n;
1688 if (num_entries_p != NULL)
1689 *num_entries_p = table_p->ta_entry_n;
1690 return TABLE_ERROR_NONE;
1698 * Set the number of buckets in a table to a certain value.
1702 * Success - TABLE_ERROR_NONE
1704 * Failure - Table error code.
1708 * table_p - Table structure pointer of which we are adjusting.
1710 * bucket_n - Number buckets to adjust the table to. Set to 0 to
1711 * adjust the table to its number of entries.
1713 int table_adjust(table_t * table_p, const int bucket_n)
1715 table_entry_t *entry_p, *next_p;
1716 table_entry_t **buckets, **bucket_p, **bounds_p;
1718 unsigned int buck_n;
1720 if (table_p == NULL)
1721 return TABLE_ERROR_ARG_NULL;
1722 if (table_p->ta_magic != TABLE_MAGIC)
1723 return TABLE_ERROR_PNT;
1725 * NOTE: we walk through the entries and rehash them. If we stored
1726 * the hash value as a full int in the table-entry, all we would
1727 * have to do is remod it.
1730 /* normalize to the number of entries */
1732 buck_n = table_p->ta_entry_n;
1735 /* we must have at least 1 bucket */
1738 /* make sure we have somethign to do */
1739 if (buck_n <= table_p->ta_bucket_n)
1740 return TABLE_ERROR_NONE;
1741 /* allocate a new bucket list */
1742 buckets = (table_entry_t **)
1743 table_p->ta_calloc(table_p->opt_param,
1744 buck_n, sizeof(table_entry_t *));
1745 if (table_p->ta_buckets == NULL)
1746 return TABLE_ERROR_ALLOC;
1748 * run through each of the items in the current table and rehash
1749 * them into the newest bucket sizes
1751 bounds_p = table_p->ta_buckets + table_p->ta_bucket_n;
1752 for (bucket_p = table_p->ta_buckets; bucket_p < bounds_p; bucket_p++) {
1753 for (entry_p = *bucket_p; entry_p != NULL; entry_p = next_p) {
1755 /* hash the old data into the new table size */
1756 bucket = hash(ENTRY_KEY_BUF(entry_p), entry_p->te_key_size, 0) % buck_n;
1758 /* record the next one now since we overwrite next below */
1759 next_p = entry_p->te_next_p;
1761 /* insert into new list, no need to append */
1762 entry_p->te_next_p = buckets[bucket];
1763 buckets[bucket] = entry_p;
1766 * NOTE: we may want to adjust the bucket_c linear entry here to
1770 /* remove the old table pointers as we go by */
1774 /* replace the table buckets with the new ones */
1775 table_p->ta_free(table_p->opt_param, table_p->ta_buckets);
1776 table_p->ta_buckets = buckets;
1777 table_p->ta_bucket_n = buck_n;
1779 return TABLE_ERROR_NONE;
1783 * const char *table_strerror
1787 * Return the corresponding string for the error number.
1791 * Success - String equivalient of the error.
1793 * Failure - String "invalid error code"
1797 * error - Error number that we are converting.
1799 const char *table_strerror(const int error)
1803 for (err_p = errors; err_p->es_error != 0; err_p++) {
1804 if (err_p->es_error == error)
1805 return err_p->es_string;
1808 return INVALID_ERROR;
1812 * int table_type_size
1816 * Return the size of the internal table type.
1820 * The size of the table_t type.
1826 int table_type_size(void)
1828 return sizeof(table_t);
1831 /************************* linear access routines ****************************/
1838 * Find first element in a table and pass back information about the
1839 * key/data pair. If any of the key/data pointers are NULL then they
1842 * NOTE: This function is not reentrant. More than one thread cannot
1843 * be doing a first and next on the same table at the same time. Use
1844 * the table_first_r version below for this.
1848 * Success - TABLE_ERROR_NONE
1850 * Failure - Table error code.
1854 * table_p - Table structure pointer from which we are getting the
1857 * key_buf_p - Pointer which, if not NULL, will be set to the address
1858 * of the storage of the first key that is allocated in the table. If
1859 * an (int) is stored as the first key (for example) then key_buf_p
1860 * should be (int **) i.e. the address of a (int *).
1862 * key_size_p - Pointer to an integer which, if not NULL, will be set
1863 * to the size of the key that is stored in the table and that is
1864 * associated with the first key.
1866 * data_buf_p - Pointer which, if not NULL, will be set to the address
1867 * of the data storage that is allocated in the table and that is
1868 * associated with the first key. If a (long) is stored as the data
1869 * (for example) then data_buf_p should be (long **) i.e. the address
1872 * data_size_p - Pointer to an integer which, if not NULL, will be set
1873 * to the size of the data that is stored in the table and that is
1874 * associated with the first key.
1876 int table_first(table_t * table_p,
1877 void **key_buf_p, int *key_size_p,
1878 void **data_buf_p, int *data_size_p)
1880 table_entry_t *entry_p;
1882 if (table_p == NULL)
1883 return TABLE_ERROR_ARG_NULL;
1884 if (table_p->ta_magic != TABLE_MAGIC)
1885 return TABLE_ERROR_PNT;
1886 /* initialize our linear magic number */
1887 table_p->ta_linear.tl_magic = LINEAR_MAGIC;
1889 entry_p = first_entry(table_p, &table_p->ta_linear);
1890 if (entry_p == NULL)
1891 return TABLE_ERROR_NOT_FOUND;
1892 if (key_buf_p != NULL)
1893 *key_buf_p = ENTRY_KEY_BUF(entry_p);
1894 if (key_size_p != NULL)
1895 *key_size_p = entry_p->te_key_size;
1896 if (data_buf_p != NULL) {
1897 if (entry_p->te_data_size == 0)
1900 if (table_p->ta_data_align == 0)
1901 *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
1903 *data_buf_p = entry_data_buf(table_p, entry_p);
1906 if (data_size_p != NULL)
1907 *data_size_p = entry_p->te_data_size;
1908 return TABLE_ERROR_NONE;
1916 * Find the next element in a table and pass back information about
1917 * the key/data pair. If any of the key/data pointers are NULL then
1920 * NOTE: This function is not reentrant. More than one thread cannot
1921 * be doing a first and next on the same table at the same time. Use
1922 * the table_next_r version below for this.
1926 * Success - TABLE_ERROR_NONE
1928 * Failure - Table error code.
1932 * table_p - Table structure pointer from which we are getting the
1935 * key_buf_p - Pointer which, if not NULL, will be set to the address
1936 * of the storage of the next key that is allocated in the table. If
1937 * an (int) is stored as the next key (for example) then key_buf_p
1938 * should be (int **) i.e. the address of a (int *).
1940 * key_size_p - Pointer to an integer which, if not NULL, will be set
1941 * to the size of the key that is stored in the table and that is
1942 * associated with the next key.
1944 * data_buf_p - Pointer which, if not NULL, will be set to the address
1945 * of the data storage that is allocated in the table and that is
1946 * associated with the next key. If a (long) is stored as the data
1947 * (for example) then data_buf_p should be (long **) i.e. the address
1950 * data_size_p - Pointer to an integer which, if not NULL, will be set
1951 * to the size of the data that is stored in the table and that is
1952 * associated with the next key.
1954 int table_next(table_t * table_p,
1955 void **key_buf_p, int *key_size_p,
1956 void **data_buf_p, int *data_size_p)
1958 table_entry_t *entry_p;
1961 if (table_p == NULL)
1962 return TABLE_ERROR_ARG_NULL;
1963 if (table_p->ta_magic != TABLE_MAGIC)
1964 return TABLE_ERROR_PNT;
1965 if (table_p->ta_linear.tl_magic != LINEAR_MAGIC)
1966 return TABLE_ERROR_LINEAR;
1967 /* move to the next entry */
1968 entry_p = next_entry(table_p, &table_p->ta_linear, &error);
1969 if (entry_p == NULL)
1971 if (key_buf_p != NULL)
1972 *key_buf_p = ENTRY_KEY_BUF(entry_p);
1973 if (key_size_p != NULL)
1974 *key_size_p = entry_p->te_key_size;
1975 if (data_buf_p != NULL) {
1976 if (entry_p->te_data_size == 0)
1979 if (table_p->ta_data_align == 0)
1980 *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
1982 *data_buf_p = entry_data_buf(table_p, entry_p);
1985 if (data_size_p != NULL)
1986 *data_size_p = entry_p->te_data_size;
1987 return TABLE_ERROR_NONE;
1995 * Find the current element in a table and pass back information about
1996 * the key/data pair. If any of the key/data pointers are NULL then
1999 * NOTE: This function is not reentrant. Use the table_current_r
2004 * Success - TABLE_ERROR_NONE
2006 * Failure - Table error code.
2010 * table_p - Table structure pointer from which we are getting the
2013 * key_buf_p - Pointer which, if not NULL, will be set to the address
2014 * of the storage of the current key that is allocated in the table.
2015 * If an (int) is stored as the current key (for example) then
2016 * key_buf_p should be (int **) i.e. the address of a (int *).
2018 * key_size_p - Pointer to an integer which, if not NULL, will be set
2019 * to the size of the key that is stored in the table and that is
2020 * associated with the current key.
2022 * data_buf_p - Pointer which, if not NULL, will be set to the address
2023 * of the data storage that is allocated in the table and that is
2024 * associated with the current key. If a (long) is stored as the data
2025 * (for example) then data_buf_p should be (long **) i.e. the address
2028 * data_size_p - Pointer to an integer which, if not NULL, will be set
2029 * to the size of the data that is stored in the table and that is
2030 * associated with the current key.
2032 int table_this(table_t * table_p,
2033 void **key_buf_p, int *key_size_p,
2034 void **data_buf_p, int *data_size_p)
2036 table_entry_t *entry_p = NULL;
2039 if (table_p == NULL)
2040 return TABLE_ERROR_ARG_NULL;
2041 if (table_p->ta_magic != TABLE_MAGIC)
2042 return TABLE_ERROR_PNT;
2043 if (table_p->ta_linear.tl_magic != LINEAR_MAGIC)
2044 return TABLE_ERROR_LINEAR;
2045 /* if we removed an item that shorted the bucket list, we may get this */
2046 if (table_p->ta_linear.tl_bucket_c >= table_p->ta_bucket_n) {
2048 * NOTE: this might happen if we delete an item which shortens the
2049 * table bucket numbers.
2051 return TABLE_ERROR_NOT_FOUND;
2054 /* find the entry which is the nth in the list */
2055 entry_p = table_p->ta_buckets[table_p->ta_linear.tl_bucket_c];
2056 /* NOTE: we swap the order here to be more efficient */
2057 for (entry_c = table_p->ta_linear.tl_entry_c; entry_c > 0; entry_c--) {
2058 /* did we reach the end of the list? */
2059 if (entry_p == NULL)
2061 entry_p = TABLE_POINTER(table_p, table_entry_t *, entry_p)->te_next_p;
2064 /* is this a NOT_FOUND or a LINEAR error */
2065 if (entry_p == NULL)
2066 return TABLE_ERROR_NOT_FOUND;
2067 if (key_buf_p != NULL)
2068 *key_buf_p = ENTRY_KEY_BUF(entry_p);
2069 if (key_size_p != NULL)
2070 *key_size_p = entry_p->te_key_size;
2071 if (data_buf_p != NULL) {
2072 if (entry_p->te_data_size == 0)
2075 if (table_p->ta_data_align == 0)
2076 *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
2078 *data_buf_p = entry_data_buf(table_p, entry_p);
2081 if (data_size_p != NULL)
2082 *data_size_p = entry_p->te_data_size;
2083 return TABLE_ERROR_NONE;
2091 * Reetrant version of the table_first routine above. Find first
2092 * element in a table and pass back information about the key/data
2093 * pair. If any of the key/data pointers are NULL then they are
2098 * Success - TABLE_ERROR_NONE
2100 * Failure - Table error code.
2104 * table_p - Table structure pointer from which we are getting the
2107 * linear_p - Pointer to a table linear structure which is initialized
2108 * here. The same pointer should then be passed to table_next_r
2111 * key_buf_p - Pointer which, if not NULL, will be set to the address
2112 * of the storage of the first key that is allocated in the table. If
2113 * an (int) is stored as the first key (for example) then key_buf_p
2114 * should be (int **) i.e. the address of a (int *).
2116 * key_size_p - Pointer to an integer which, if not NULL, will be set
2117 * to the size of the key that is stored in the table and that is
2118 * associated with the first key.
2120 * data_buf_p - Pointer which, if not NULL, will be set to the address
2121 * of the data storage that is allocated in the table and that is
2122 * associated with the first key. If a (long) is stored as the data
2123 * (for example) then data_buf_p should be (long **) i.e. the address
2126 * data_size_p - Pointer to an integer which, if not NULL, will be set
2127 * to the size of the data that is stored in the table and that is
2128 * associated with the first key.
2130 int table_first_r(table_t * table_p, table_linear_t * linear_p,
2131 void **key_buf_p, int *key_size_p,
2132 void **data_buf_p, int *data_size_p)
2134 table_entry_t *entry_p;
2136 if (table_p == NULL)
2137 return TABLE_ERROR_ARG_NULL;
2138 if (table_p->ta_magic != TABLE_MAGIC)
2139 return TABLE_ERROR_PNT;
2140 if (linear_p == NULL)
2141 return TABLE_ERROR_ARG_NULL;
2142 /* initialize our linear magic number */
2143 linear_p->tl_magic = LINEAR_MAGIC;
2145 entry_p = first_entry(table_p, linear_p);
2146 if (entry_p == NULL)
2147 return TABLE_ERROR_NOT_FOUND;
2148 if (key_buf_p != NULL)
2149 *key_buf_p = ENTRY_KEY_BUF(entry_p);
2150 if (key_size_p != NULL)
2151 *key_size_p = entry_p->te_key_size;
2152 if (data_buf_p != NULL) {
2153 if (entry_p->te_data_size == 0)
2156 if (table_p->ta_data_align == 0)
2157 *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
2159 *data_buf_p = entry_data_buf(table_p, entry_p);
2162 if (data_size_p != NULL)
2163 *data_size_p = entry_p->te_data_size;
2164 return TABLE_ERROR_NONE;
2172 * Reetrant version of the table_next routine above. Find next
2173 * element in a table and pass back information about the key/data
2174 * pair. If any of the key/data pointers are NULL then they are
2179 * Success - TABLE_ERROR_NONE
2181 * Failure - Table error code.
2185 * table_p - Table structure pointer from which we are getting the
2188 * linear_p - Pointer to a table linear structure which is incremented
2189 * here. The same pointer must have been passed to table_first_r
2190 * first so that it can be initialized.
2192 * key_buf_p - Pointer which, if not NULL, will be set to the address
2193 * of the storage of the next key that is allocated in the table. If
2194 * an (int) is stored as the next key (for example) then key_buf_p
2195 * should be (int **) i.e. the address of a (int *).
2197 * key_size_p - Pointer to an integer which, if not NULL will be set
2198 * to the size of the key that is stored in the table and that is
2199 * associated with the next key.
2201 * data_buf_p - Pointer which, if not NULL, will be set to the address
2202 * of the data storage that is allocated in the table and that is
2203 * associated with the next key. If a (long) is stored as the data
2204 * (for example) then data_buf_p should be (long **) i.e. the address
2207 * data_size_p - Pointer to an integer which, if not NULL, will be set
2208 * to the size of the data that is stored in the table and that is
2209 * associated with the next key.
2211 int table_next_r(table_t * table_p, table_linear_t * linear_p,
2212 void **key_buf_p, int *key_size_p,
2213 void **data_buf_p, int *data_size_p)
2215 table_entry_t *entry_p;
2218 if (table_p == NULL)
2219 return TABLE_ERROR_ARG_NULL;
2220 if (table_p->ta_magic != TABLE_MAGIC)
2221 return TABLE_ERROR_PNT;
2222 if (linear_p == NULL)
2223 return TABLE_ERROR_ARG_NULL;
2224 if (linear_p->tl_magic != LINEAR_MAGIC)
2225 return TABLE_ERROR_LINEAR;
2226 /* move to the next entry */
2227 entry_p = next_entry(table_p, linear_p, &error);
2228 if (entry_p == NULL)
2230 if (key_buf_p != NULL)
2231 *key_buf_p = ENTRY_KEY_BUF(entry_p);
2232 if (key_size_p != NULL)
2233 *key_size_p = entry_p->te_key_size;
2234 if (data_buf_p != NULL) {
2235 if (entry_p->te_data_size == 0)
2238 if (table_p->ta_data_align == 0)
2239 *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
2241 *data_buf_p = entry_data_buf(table_p, entry_p);
2244 if (data_size_p != NULL)
2245 *data_size_p = entry_p->te_data_size;
2246 return TABLE_ERROR_NONE;
2254 * Reetrant version of the table_this routine above. Find current
2255 * element in a table and pass back information about the key/data
2256 * pair. If any of the key/data pointers are NULL then they are
2261 * Success - TABLE_ERROR_NONE
2263 * Failure - Table error code.
2267 * table_p - Table structure pointer from which we are getting the
2270 * linear_p - Pointer to a table linear structure which is accessed
2271 * here. The same pointer must have been passed to table_first_r
2272 * first so that it can be initialized.
2274 * key_buf_p - Pointer which, if not NULL, will be set to the address
2275 * of the storage of the current key that is allocated in the table.
2276 * If an (int) is stored as the current key (for example) then
2277 * key_buf_p should be (int **) i.e. the address of a (int *).
2279 * key_size_p - Pointer to an integer which, if not NULL, will be set
2280 * to the size of the key that is stored in the table and that is
2281 * associated with the current key.
2283 * data_buf_p - Pointer which, if not NULL, will be set to the address
2284 * of the data storage that is allocated in the table and that is
2285 * associated with the current key. If a (long) is stored as the data
2286 * (for example) then data_buf_p should be (long **) i.e. the address
2289 * data_size_p - Pointer to an integer which, if not NULL, will be set
2290 * to the size of the data that is stored in the table and that is
2291 * associated with the current key.
2293 int table_this_r(table_t * table_p, table_linear_t * linear_p,
2294 void **key_buf_p, int *key_size_p,
2295 void **data_buf_p, int *data_size_p)
2297 table_entry_t *entry_p;
2300 if (table_p == NULL)
2301 return TABLE_ERROR_ARG_NULL;
2302 if (table_p->ta_magic != TABLE_MAGIC)
2303 return TABLE_ERROR_PNT;
2304 if (linear_p->tl_magic != LINEAR_MAGIC)
2305 return TABLE_ERROR_LINEAR;
2306 /* if we removed an item that shorted the bucket list, we may get this */
2307 if (linear_p->tl_bucket_c >= table_p->ta_bucket_n) {
2309 * NOTE: this might happen if we delete an item which shortens the
2310 * table bucket numbers.
2312 return TABLE_ERROR_NOT_FOUND;
2315 /* find the entry which is the nth in the list */
2316 for (entry_c = linear_p->tl_entry_c,
2317 entry_p = table_p->ta_buckets[linear_p->tl_bucket_c];
2318 entry_p != NULL && entry_c > 0;
2319 entry_c--, entry_p = TABLE_POINTER(table_p, table_entry_t *,
2320 entry_p)->te_next_p) {
2323 if (entry_p == NULL)
2324 return TABLE_ERROR_NOT_FOUND;
2325 if (key_buf_p != NULL)
2326 *key_buf_p = ENTRY_KEY_BUF(entry_p);
2327 if (key_size_p != NULL)
2328 *key_size_p = entry_p->te_key_size;
2329 if (data_buf_p != NULL) {
2330 if (entry_p->te_data_size == 0)
2333 if (table_p->ta_data_align == 0)
2334 *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
2336 *data_buf_p = entry_data_buf(table_p, entry_p);
2339 if (data_size_p != NULL)
2340 *data_size_p = entry_p->te_data_size;
2341 return TABLE_ERROR_NONE;
2344 /******************************** table order ********************************/
2347 * table_entry_t *table_order
2351 * Order a table by building an array of table entry pointers and then
2352 * sorting this array using the qsort function. To retrieve the
2353 * sorted entries, you can then use the table_entry routine to access
2354 * each entry in order.
2356 * NOTE: This routine is now thread safe in that two table_order calls
2357 * can now happen at the same time, even on the same table.
2361 * An allocated list of entry pointers which must be freed later.
2362 * Returns null on error.
2366 * table_p - Pointer to the table that we are ordering.
2368 * compare - Comparison function defined by the user. Its definition
2369 * is at the top of the table.h file. If this is NULL then it will
2370 * order the table my memcmp-ing the keys.
2372 * num_entries_p - Pointer to an integer which, if not NULL, will
2373 * contain the number of entries in the returned entry pointer array.
2375 * error_p - Pointer to an integer which, if not NULL, will contain a
2378 table_entry_t **table_order(table_t * table_p, table_compare_t compare,
2379 int *num_entries_p, int *error_p)
2381 table_entry_t *entry_p, **entries, **entries_p;
2382 table_linear_t linear;
2383 compare_t comp_func;
2386 if (table_p == NULL) {
2387 if (error_p != NULL)
2388 *error_p = TABLE_ERROR_ARG_NULL;
2391 if (table_p->ta_magic != TABLE_MAGIC) {
2392 if (error_p != NULL)
2393 *error_p = TABLE_ERROR_PNT;
2397 /* there must be at least 1 element in the table for this to work */
2398 if (table_p->ta_entry_n == 0) {
2399 if (error_p != NULL)
2400 *error_p = TABLE_ERROR_EMPTY;
2404 entries = (table_entry_t **)
2405 table_p->ta_malloc(table_p->opt_param,
2406 table_p->ta_entry_n *sizeof(table_entry_t *));
2407 if (entries == NULL) {
2408 if (error_p != NULL)
2409 *error_p = TABLE_ERROR_ALLOC;
2413 /* get a pointer to all entries */
2414 entry_p = first_entry(table_p, &linear);
2415 if (entry_p == NULL) {
2416 if (error_p != NULL)
2417 *error_p = TABLE_ERROR_NOT_FOUND;
2421 /* add all of the entries to the array */
2422 for (entries_p = entries;
2424 entry_p = next_entry(table_p, &linear, &error))
2425 *entries_p++ = entry_p;
2426 if (error != TABLE_ERROR_NOT_FOUND) {
2427 if (error_p != NULL)
2432 if (compare == NULL) {
2433 /* this is regardless of the alignment */
2434 comp_func = local_compare;
2436 else if (table_p->ta_data_align == 0)
2437 comp_func = external_compare;
2439 comp_func = external_compare_align;
2440 /* now qsort the entire entries array from first to last element */
2441 split(entries, entries + table_p->ta_entry_n - 1, comp_func, compare,
2444 if (num_entries_p != NULL)
2445 *num_entries_p = table_p->ta_entry_n;
2446 if (error_p != NULL)
2447 *error_p = TABLE_ERROR_NONE;
2456 * Get information about an element. The element is one from the
2457 * array returned by the table_order function. If any of the key/data
2458 * pointers are NULL then they are ignored.
2462 * Success - TABLE_ERROR_NONE
2464 * Failure - Table error code.
2468 * table_p - Table structure pointer from which we are getting the
2471 * entry_p - Pointer to a table entry from the array returned by the
2472 * table_order function.
2474 * key_buf_p - Pointer which, if not NULL, will be set to the address
2475 * of the storage of this entry that is allocated in the table. If an
2476 * (int) is stored as this entry (for example) then key_buf_p should
2477 * be (int **) i.e. the address of a (int *).
2479 * key_size_p - Pointer to an integer which, if not NULL, will be set
2480 * to the size of the key that is stored in the table.
2482 * data_buf_p - Pointer which, if not NULL, will be set to the address
2483 * of the data storage of this entry that is allocated in the table.
2484 * If a (long) is stored as this entry data (for example) then
2485 * data_buf_p should be (long **) i.e. the address of a (long *).
2487 * data_size_p - Pointer to an integer which, if not NULL, will be set
2488 * to the size of the data that is stored in the table.
2490 int table_entry_info(table_t * table_p, table_entry_t * entry_p,
2491 void **key_buf_p, int *key_size_p,
2492 void **data_buf_p, int *data_size_p)
2494 if (table_p == NULL)
2495 return TABLE_ERROR_ARG_NULL;
2496 if (table_p->ta_magic != TABLE_MAGIC)
2497 return TABLE_ERROR_PNT;
2498 if (entry_p == NULL)
2499 return TABLE_ERROR_ARG_NULL;
2500 if (key_buf_p != NULL)
2501 *key_buf_p = ENTRY_KEY_BUF(entry_p);
2502 if (key_size_p != NULL)
2503 *key_size_p = entry_p->te_key_size;
2504 if (data_buf_p != NULL) {
2505 if (entry_p->te_data_size == 0)
2508 if (table_p->ta_data_align == 0)
2509 *data_buf_p = ENTRY_DATA_BUF(table_p, entry_p);
2511 *data_buf_p = entry_data_buf(table_p, entry_p);
2514 if (data_size_p != NULL)
2515 *data_size_p = entry_p->te_data_size;
2516 return TABLE_ERROR_NONE;