/*
* Copyright (c) 2002-2005 Sendmail, Inc. and its suppliers.
* All rights reserved.
*
* By using this file, you agree to the terms and conditions set
* forth in the LICENSE file which can be found at the top level of
* the sendmail distribution.
*/
#include "sm/generic.h"
SM_RCSID("@(#)$Id: bhtable.c,v 1.49 2006/05/02 17:13:40 ca Exp $")
#include "sm/assert.h"
#include "sm/error.h"
#include "sm/memops.h"
#include "sm/heap.h"
#include "bhtable.h"
#if SM_BHT_PERF
# include <stdio.h> /* snprintf */
#endif
/*
** Notes:
** - locking must be provided by caller.
*/
/* Check whether two keys x and y of length l are equal */
#define BHT_KEY_EQ(x, y, l) ((x)[0] == (y)[0] && sm_memeq((x), (y), (l)))
/*
** BHT_HASH -- hash a key
**
** Parameters:
** key -- key to hash
** len -- len of key
** htsize -- size of hash table
**
** Returns:
** hash value
**
** Note: it might be useful to make the hash function a pointer in
** the hash table context such that different hash functions
** can be used.
**
** Last code review: 2005-04-08 21:41:17
** Last code change:
*/
static uint
bht_hash(const char *key, uint len, uint htsize)
{
ulong h;
#if IPV4_HASH
int c, d;
#else
ulong g;
#endif
SM_REQUIRE(key != NULL);
/* From the "Dragon" book by Aho, Sethi and Ullman. */
#if IPV4_HASH
h = 0xABC3D20F;
#else
h = 0;
#endif
while (len-- > 0)
{
#if IPV4_HASH
d = *key++;
c = d;
c ^= c<<6;
h += (c<<11) ^ (c>>1);
h ^= (d<<14) + (d<<7) + (d<<4) + d;
#else /* IPV4_HASH */
h = (h << 4) + *key++;
g = h & 0xf0000000;
if (g != 0)
{
h ^= (g >> 24);
h ^= g;
}
#endif /* IPV4_HASH */
}
return h % htsize;
}
/*
** BHT_LINK -- insert element into table (prepend it)
**
** Parameters:
** table -- hash table
** elem -- element
**
** Returns:
** It's a macro...
**
** Last code review: 2005-04-08 22:23:11
** Last code change:
*/
#define BHT_LINK(table, elem) do \
{ \
sm_bht_entry_P *he = table->bht_data + \
bht_hash(elem->bhe_key, \
elem->bhe_len, table->bht_size);\
elem->bhe_prev = NULL; \
if ((elem->bhe_next = *he) != NULL) \
{ \
(*he)->bhe_prev = elem; \
bhtincracol(table); \
BHTCHAINLEN(table, elem); \
} \
*he = elem; \
table->bht_used++; \
} while (0)
#if SM_TWO_KEYS
/*
** BHT2_LINK -- insert element into table (prepend it)
**
** Parameters:
** table -- hash table
** elem -- element
**
** Returns:
** It's a macro...
**
** Last code review: 2005-04-08 22:23:46
** Last code change:
*/
#define BHT2_LINK(table, elem) do \
{ \
sm_bht_entry_P *h = table->bht_data2 + \
bht_hash(elem->bhe_key2, \
elem->bhe_len2, table->bht_size);\
elem->bhe_prev2 = NULL; \
if ((elem->bhe_next2 = *h) != NULL) \
(*h)->bhe_prev2 = elem; \
*h = elem; \
} while (0)
#endif /* SM_TWO_KEYS */
/*
** BHT_INIT -- allocate and initialize hash table
**
** Parameters:
** table -- pointer to table
** htsize -- size of hash table
**
** Returns:
** usual sm_error code; ENOMEM
**
** Last code review: 2005-04-08 22:24:36
** Last code change:
*/
sm_ret_T
bht_init(sm_bht_P table, uint htsize)
{
sm_bht_entry_P *h;
htsize |= 1; /* odd, isn't it? */
table->bht_data = h = (sm_bht_entry_P *) sm_zalloc(htsize *
sizeof(sm_bht_entry_P));
if (h == NULL)
return sm_error_temp(SM_EM_HT, ENOMEM);
#if SM_TWO_KEYS
table->bht_data2 = h = (sm_bht_entry_P *) sm_zalloc(htsize *
sizeof(sm_bht_entry_P));
if (h == NULL)
{
sm_free(table->bht_data);
return sm_error_temp(SM_EM_HT, ENOMEM);
}
#endif /* SM_TWO_KEYS */
table->bht_size = htsize;
table->bht_used = 0;
return SM_SUCCESS;
}
/*
** BHT_NEW -- create initial hash table
**
** Parameters:
** htsize -- size of hash table
** limit -- maximum number of entries
**
** Returns:
** pointer to table; NULL on error (ENOMEM)
**
** Last code review: 2005-04-08 22:26:00
** Last code change:
*/
sm_bht_P
sm_bht_new(uint htsize, uint limit)
{
sm_bht_P table;
sm_ret_T ret;
table = (sm_bht_P) sm_zalloc(sizeof(*table));
if (table == NULL)
return NULL;
ret = bht_init(table, htsize < BHT_MIN_SIZE ? BHT_MIN_SIZE : htsize);
if (!sm_is_success(ret))
{
sm_free_size(table, sizeof(*table));
return NULL;
}
table->bht_limit = limit;
return table;
}
/*
** BHT_GROW -- extend existing table (double its size)
**
** Parameters:
** table -- (return) pointer to table
**
** Returns:
** usual sm_error code; ENOMEM
**
** Last code review: 2005-04-08 22:35:56
** Last code change:
*/
static sm_ret_T
sm_bht_grow(sm_bht_P table)
{
uint old_size, i;
sm_bht_entry_P hte, hte_next, *h, *old_entries;
#if SM_TWO_KEYS
sm_bht_entry_P *old_entries2;
#endif
sm_ret_T ret;
old_size = table->bht_size;
h = table->bht_data;
old_entries = h;
#if SM_TWO_KEYS
old_entries2 = table->bht_data2;
#endif
ret = bht_init(table, 2 * old_size);
if (sm_is_err(ret))
return ret;
/* copy old entries into new table */
for (i = old_size; i > 0; i--)
{
for (hte = *h++; hte != NULL; hte = hte_next)
{
hte_next = hte->bhe_next;
BHT_LINK(table, hte);
}
}
#if SM_TWO_KEYS
h = old_entries2;
for (i = old_size; i > 0; i--)
{
for (hte = *h++; hte != NULL; hte = hte_next)
{
hte_next = hte->bhe_next2;
BHT2_LINK(table, hte);
}
}
#endif /* SM_TWO_KEYS */
sm_free((void *) old_entries);
#if SM_TWO_KEYS
sm_free((void *) old_entries2);
#endif
bhtincrgrows(table);
return SM_SUCCESS;
}
/*
** BHT_ADD -- add (key, value) pair
** Note: this does not check whether key exists! It will simply add
** the new pair.
**
** Parameters:
** table -- table
** key -- key to hash
** len -- len of key
** value -- value to add
** entry -- pointer to entry (output)
**
** Returns:
** usual sm_error code; ENOMEM, SM_E_FULL
**
** Side Effects: may grow table.
**
** Last code review: 2005-04-08 22:45:07
** Last code change:
*/
sm_ret_T
sm_bht_add(sm_bht_P table, char *key, uint len,
#if SM_TWO_KEYS
char *key2, uint len2,
#endif
void *value,
sm_bht_entry_P *entry)
{
sm_ret_T ret;
sm_bht_entry_P hte;
SM_REQUIRE(table != NULL);
SM_REQUIRE(entry != NULL);
if (table->bht_limit > 0 && table->bht_used >= table->bht_limit)
return sm_error_temp(SM_EM_HT, SM_E_FULL);
if (table->bht_used >= table->bht_size)
{
ret = sm_bht_grow(table);
if (sm_is_err(ret))
return ret;
}
hte = (sm_bht_entry_P) sm_malloc(sizeof(*hte));
if (hte == NULL)
return sm_error_temp(SM_EM_HT, ENOMEM);
bhtincradd(table);
#if SM_TWO_KEYS
hte->bhe_key2 = NULL;
#endif
hte->bhe_key = key;
hte->bhe_len = len;
#if SM_TWO_KEYS
hte->bhe_key2 = key2;
hte->bhe_len2 = len2;
BHT2_LINK(table, hte);
#endif /* SM_TWO_KEYS */
hte->bhe_value = value;
BHT_LINK(table, hte);
*entry = hte;
return SM_SUCCESS;
}
/* common code for next two routines, only return type is different */
#define BHT_LOOKUP(ret) \
if (table == NULL) \
return NULL; \
bhtincrlu(table); \
bhtinitchain(table); \
for (hte = table->bht_data[bht_hash(key, len, table->bht_size)]; \
hte != NULL; hte = hte->bhe_next) \
{ \
if (len == hte->bhe_len && \
BHT_KEY_EQ(key, hte->bhe_key, len)) \
return (ret); \
bhtincrlcol(table); \
BHTINCRCHAIN(table); \
} \
return NULL
#if SM_TWO_KEYS
/* common code for next two routines, only return type is different */
#define BHT2_LOOKUP(ret) \
if (table == NULL) \
return NULL; \
bhtincrlu(table); \
bhtinitchain(table); \
for (hte = table->bht_data2[bht_hash(key2, len2, table->bht_size)]; \
hte != NULL; hte = hte->bhe_next2) \
{ \
if (len2 == hte->bhe_len2 && \
BHT_KEY_EQ(key2, hte->bhe_key2, len2)) \
return (ret); \
bhtincrlcol(table); \
BHTINCRCHAIN(table); \
} \
return NULL
#endif /* SM_TWO_KEYS */
/*
** BHT_FIND -- lookup value
**
** Parameters:
** table -- pointer to table
** key -- key to hash
** len -- len of key
**
** Returns:
** pointer to value
**
** Last code review: 2005-03-20 02:00:42
** Last code change:
*/
void *
sm_bht_find(sm_bht_P table, const char *key, uint len)
{
sm_bht_entry_P hte;
BHT_LOOKUP(hte->bhe_value);
}
/*
** BHT_LOCATE -- lookup entry
**
** Parameters:
** table -- pointer to table
** key -- key to hash
** len -- len of key
**
** Returns:
** pointer to entry.
**
** Last code review: 2005-03-20 02:00:42
** Last code change:
*/
sm_bht_entry_P
sm_bht_locate(sm_bht_P table, const char *key, uint len)
{
sm_bht_entry_P hte;
BHT_LOOKUP(hte);
}
#if SM_TWO_KEYS
/*
** BHT2_FIND_FIRST -- lookup value
**
** Parameters:
** table -- pointer to table
** key2 -- key to hash
** len2 -- len of key
**
** Returns:
** pointer to value
**
** Last code review: 2005-04-08 22:46:00
** Last code change:
*/
void *
bht2_find_first(sm_bht_P table, const char *key2, uint len2)
{
sm_bht_entry_P hte;
BHT2_LOOKUP(hte->bhe_value);
}
/*
** BHT2_LOCATE_FIRST -- lookup entry
**
** Parameters:
** table -- pointer to table
** key2 -- key to hash
** len2 -- len of key
**
** Returns:
** pointer to entry.
**
** Last code review: 2005-04-08 22:46:07
** Last code change:
*/
sm_bht_entry_P
bht2_locate_first(sm_bht_P table, const char *key2, uint len2)
{
sm_bht_entry_P hte;
BHT2_LOOKUP(hte);
}
/*
** BHT2_LOCATE_NEXT -- get next entry
**
** Parameters:
** table -- pointer to table
** prev -- previous entry
**
** Returns:
** pointer to entry.
**
** Last code review: 2005-04-08 22:46:19
** Last code change:
*/
sm_bht_entry_P
bht2_locate_next(sm_bht_P table, sm_bht_entry_P prev)
{
SM_REQUIRE(table != NULL);
SM_REQUIRE(prev != NULL);
return prev->bhe_next2;
}
#endif /* SM_TWO_KEYS */
#if SM_TWO_KEYS
# define BHT_RM_2 \
if (hte->bhe_next2 != NULL) \
hte->bhe_next2->bhe_prev2 = hte->bhe_prev2; \
if (hte->bhe_prev2 != NULL) \
hte->bhe_prev2->bhe_next2 = hte->bhe_next2; \
else \
{ \
h = table->bht_data2 + \
bht_hash(hte->bhe_key2, \
hte->bhe_len2, \
table->bht_size); \
*h = hte->bhe_next2; \
}
#else /* SM_TWO_KEYS */
# define BHT_RM_2
#endif /* SM_TWO_KEYS */
/*
** Notice: we can't have a simple bht_rm_entry() function
** since this removal requires the pointer in bht->data,
** not just the pointer to the entry itself.
*/
#define BH_RM_FCT(one) \
{ \
sm_bht_entry_P hte, *h, hte_next; \
\
SM_REQUIRE(table != NULL); \
h = table->bht_data + bht_hash(key, len, table->bht_size); \
bhtincrdel(table); \
\
for (hte = *h; hte != NULL; hte = hte_next) \
{ \
hte_next = hte->bhe_next; \
if (len == hte->bhe_len && \
BHT_KEY_EQ(key, hte->bhe_key, len)) \
{ \
BHTINCRDCOL(table, hte); \
/* remove element from list */ \
if (hte->bhe_next != NULL) \
hte->bhe_next->bhe_prev = hte->bhe_prev; \
if (hte->bhe_prev != NULL) \
hte->bhe_prev->bhe_next = hte->bhe_next; \
else \
*h = hte->bhe_next; \
BHT_RM_2 \
SM_ASSERT(table->bht_used > 0); \
table->bht_used--; \
if (free_fn != NULL) \
(*free_fn)(hte->bhe_value, hte->bhe_key, ctx); \
sm_free_size(hte, sizeof(*hte)); \
one; \
} \
} \
}
/*
** BHT_RM_ALL -- remove all entries that match key/len
**
** Parameters:
** table -- pointer to table
** key -- key to look up
** len -- len of key
** free_fn -- function to free individual entries
** ctx -- context for free function.
**
** Returns:
** Nothing. (should it return number of removed entries?)
**
** Last code review: 2005-04-08 22:49:20
** Last code change: 2005-03-20 02:15:08
*/
void
sm_bht_rm_all(sm_bht_P table, const char *key, uint len, sm_bhfree_F free_fn, void *ctx)
BH_RM_FCT(SM_NOOP)
/*
** BHT_RM -- remove first entry that matches key/len
**
** Parameters:
** table -- pointer to table
** key -- key to look up
** len -- len of key
** free_fn -- function to free individual entries
** ctx -- context for free function.
**
** Returns:
** Nothing. (should it return whether an entry has been removed?)
**
** Last code review: 2005-03-30 23:00:44
** Last code change: 2005-03-20 02:15:08
*/
void
sm_bht_rm(sm_bht_P table, const char *key, uint len, sm_bhfree_F free_fn, void *ctx)
BH_RM_FCT(return)
/*
** BHT_DESTROY -- destroy hash table
**
** Parameters:
** table -- pointer to table
** free_fn -- function to free individual entries
** ctx -- context for free function.
**
** Returns:
** Nothing.
**
** Last code review: 2005-04-08 22:50:40
** Last code change:
*/
void
sm_bht_destroy(sm_bht_P table, sm_bhfree_F free_fn, void *ctx)
{
uint i;
sm_bht_entry_P hte, hte_next, *h;
if (table == NULL)
return;
i = table->bht_size;
h = table->bht_data;
while (i-- > 0)
{
for (hte = *h++; hte != NULL; hte = hte_next)
{
hte_next = hte->bhe_next;
if (free_fn != NULL)
(*free_fn)(hte->bhe_value, hte->bhe_key, ctx);
sm_free_size(hte, sizeof(*hte));
}
}
sm_free((void *) table->bht_data);
table->bht_data = NULL;
#if SM_TWO_KEYS
sm_free((void *) table->bht_data2);
#endif
sm_free_size(table, sizeof(*table));
}
/*
** BHT_WALK -- iterate over hash table, apply a function to each element
**
** Parameters:
** table -- pointer to table
** action -- function to apply
** ctx -- context for function.
**
** Returns:
** return value from action if not SM_SUCCESS
**
** Last code review: 2005-03-31 04:51:42
** Last code change:
*/
sm_ret_T
sm_bht_walk(sm_bht_P table, sm_bhwalk_F action, void *ctx)
{
uint i;
sm_bht_entry_P *h, hte, htn;
sm_ret_T ret;
SM_REQUIRE(table != NULL);
i = table->bht_size;
h = table->bht_data;
while (i-- > 0)
{
for (hte = *h++; hte != NULL; hte = htn)
{
htn = hte->bhe_next;
ret = (*action)(hte, ctx);
if (ret != SM_SUCCESS)
return ret;
}
}
return SM_SUCCESS;
}
#if 0
///*
//** BHT_LIST - list all table members
//**
//** Parameters:
//** table -- pointer to table
//**
//** Returns:
//** array of entries (NULL on error).
//*/
//
//sm_bht_entry_P *
//sm_bht_list(sm_bht_P table)
//{
// uint count, i;
// sm_bht_entry_P *list, member;
//
// count = 0;
// if (table != NULL)
// {
// list = (sm_bht_entry_P *) sm_malloc(sizeof(*list) *
// (table->bht_used + 1));
// if (list == NULL)
// return NULL;
// for (i = 0; i < table->bht_size; i++)
// {
// for (member = table->bht_data[i]; member != NULL;
// member = member->bhe_next)
// list[count++] = member;
// }
// }
// else
// {
// list = (sm_bht_entry_P *) sm_malloc(sizeof(*list));
// if (list == NULL)
// return NULL;
// }
// list[count] = NULL;
// return list;
//}
#endif /* 0 */
/*
** BHT_STATS -- print statistics about table (if available)
**
** Parameters:
** table -- table
** out -- pointer to output data
** len -- maximum length of output data
**
** Returns:
** Nothing.
**
** Last code review: 2005-04-08 22:51:19
** Last code change:
*/
void
sm_bht_stats(sm_bht_P table, char *out, uint len)
{
SM_REQUIRE(table != NULL);
SM_REQUIRE(out != NULL);
SM_REQUIRE(len > 0);
#if SM_BHT_PERF
snprintf(out, len, "adds %9lu\n"
"lookups %9lu\n"
"deletes %9lu\n"
"add collisions %9lu\n"
"lookup collisions %9lu\n"
"delete collisions %9lu\n"
"max chain len %9u\n"
"grows %9u\n"
, table->bht_adds, table->bht_lookups, table->bht_deletes
, table->bht_acollisions
, table->bht_lcollisions, table->bht_dcollisions
, table->bht_chainmax, table->bht_grows);
#else /* SM_BHT_PERF */
*out = '\0';
#endif /* SM_BHT_PERF */
}
syntax highlighted by Code2HTML, v. 0.9.1