#include "irc_dictionary.h"
#include "irc_radixtree.h"
-rb_dlink_list *clientTable;
-rb_dlink_list *channelTable;
-rb_dlink_list *idTable;
rb_dlink_list *hostTable;
struct Dictionary *client_connid_tree = NULL;
struct Dictionary *client_zconnid_tree = NULL;
+struct irc_radixtree *client_id_tree = NULL;
+struct irc_radixtree *client_name_tree = NULL;
+struct irc_radixtree *channel_tree = NULL;
struct irc_radixtree *resv_tree = NULL;
/*
* look in whowas.c for the missing ...[WW_MAX]; entry
*/
-/*
- * Hashing.
- *
- * The server uses a chained hash table to provide quick and efficient
- * hash table maintenance (providing the hash function works evenly over
- * the input range). The hash table is thus not susceptible to problems
- * of filling all the buckets or the need to rehash.
- * It is expected that the hash table would look something like this
- * during use:
- * +-----+ +-----+ +-----+ +-----+
- * ---| 224 |----| 225 |----| 226 |---| 227 |---
- * +-----+ +-----+ +-----+ +-----+
- * | | |
- * +-----+ +-----+ +-----+
- * | A | | C | | D |
- * +-----+ +-----+ +-----+
- * |
- * +-----+
- * | B |
- * +-----+
- *
- * A - GOPbot, B - chang, C - hanuaway, D - *.mu.OZ.AU
- *
- * The order shown above is just one instant of the server.
- *
- *
- * The hash functions currently used are based Fowler/Noll/Vo hashes
- * which work amazingly well and have a extremely low collision rate
- * For more info see http://www.isthe.com/chongo/tech/comp/fnv/index.html
- *
- *
- */
-
/* init_hash()
*
* clears the various hashtables
void
init_hash(void)
{
- clientTable = rb_malloc(sizeof(rb_dlink_list) * U_MAX);
- idTable = rb_malloc(sizeof(rb_dlink_list) * U_MAX);
- channelTable = rb_malloc(sizeof(rb_dlink_list) * CH_MAX);
hostTable = rb_malloc(sizeof(rb_dlink_list) * HOST_MAX);
client_connid_tree = irc_dictionary_create("client connid", irc_uint32cmp);
client_zconnid_tree = irc_dictionary_create("client zconnid", irc_uint32cmp);
+ client_id_tree = irc_radixtree_create("client id", NULL);
+ client_name_tree = irc_radixtree_create("client name", irc_radixtree_irccasecanon);
+ channel_tree = irc_radixtree_create("channel", irc_radixtree_irccasecanon);
resv_tree = irc_radixtree_create("resv", irc_radixtree_irccasecanon);
}
return h;
}
-/* hash_nick()
- *
- * hashes a nickname, first converting to lowercase
- */
-static u_int32_t
-hash_nick(const char *name)
-{
- return fnv_hash_upper((const unsigned char *) name, U_MAX_BITS);
-}
-
-/* hash_id()
- *
- * hashes an id, case is kept
- */
-static u_int32_t
-hash_id(const char *name)
-{
- return fnv_hash((const unsigned char *) name, U_MAX_BITS);
-}
-
-/* hash_channel()
- *
- * hashes a channel name, based on first 30 chars only for efficiency
- */
-static u_int32_t
-hash_channel(const char *name)
-{
- return fnv_hash_upper_len((const unsigned char *) name, CH_MAX_BITS, 30);
-}
-
/* hash_hostname()
*
* hashes a hostname, based on first 30 chars only, as thats likely to
void
add_to_id_hash(const char *name, struct Client *client_p)
{
- unsigned int hashv;
-
if(EmptyString(name) || (client_p == NULL))
return;
- hashv = hash_id(name);
- rb_dlinkAddAlloc(client_p, &idTable[hashv]);
+ irc_radixtree_add(client_id_tree, name, client_p);
}
/* add_to_client_hash()
void
add_to_client_hash(const char *name, struct Client *client_p)
{
- unsigned int hashv;
-
s_assert(name != NULL);
s_assert(client_p != NULL);
if(EmptyString(name) || (client_p == NULL))
return;
- hashv = hash_nick(name);
- rb_dlinkAddAlloc(client_p, &clientTable[hashv]);
+ irc_radixtree_add(client_name_tree, name, client_p);
}
/* add_to_hostname_hash()
void
del_from_id_hash(const char *id, struct Client *client_p)
{
- unsigned int hashv;
-
s_assert(id != NULL);
s_assert(client_p != NULL);
if(EmptyString(id) || client_p == NULL)
return;
- hashv = hash_id(id);
- rb_dlinkFindDestroy(client_p, &idTable[hashv]);
+ irc_radixtree_delete(client_id_tree, id);
}
/* del_from_client_hash()
void
del_from_client_hash(const char *name, struct Client *client_p)
{
- unsigned int hashv;
-
/* no s_asserts, this can happen when removing a client that
* is unregistered.
*/
if(EmptyString(name) || client_p == NULL)
return;
- hashv = hash_nick(name);
- rb_dlinkFindDestroy(client_p, &clientTable[hashv]);
+ irc_radixtree_delete(client_name_tree, name);
}
/* del_from_channel_hash()
void
del_from_channel_hash(const char *name, struct Channel *chptr)
{
- unsigned int hashv;
-
s_assert(name != NULL);
s_assert(chptr != NULL);
if(EmptyString(name) || chptr == NULL)
return;
- hashv = hash_channel(name);
- rb_dlinkFindDestroy(chptr, &channelTable[hashv]);
+ irc_radixtree_delete(channel_tree, name);
}
/* del_from_hostname_hash()
struct Client *
find_id(const char *name)
{
- struct Client *target_p;
- rb_dlink_node *ptr;
- unsigned int hashv;
-
if(EmptyString(name))
return NULL;
- hashv = hash_id(name);
-
- RB_DLINK_FOREACH(ptr, idTable[hashv].head)
- {
- target_p = ptr->data;
-
- if(strcmp(name, target_p->id) == 0)
- return target_p;
- }
-
- return NULL;
+ return irc_radixtree_retrieve(client_id_tree, name);
}
/* find_client()
struct Client *
find_client(const char *name)
{
- struct Client *target_p;
- rb_dlink_node *ptr;
- unsigned int hashv;
-
s_assert(name != NULL);
if(EmptyString(name))
return NULL;
if(IsDigit(*name))
return (find_id(name));
- hashv = hash_nick(name);
-
- RB_DLINK_FOREACH(ptr, clientTable[hashv].head)
- {
- target_p = ptr->data;
-
- if(irccmp(name, target_p->name) == 0)
- return target_p;
- }
-
- return NULL;
+ return irc_radixtree_retrieve(client_name_tree, name);
}
/* find_named_client()
struct Client *
find_named_client(const char *name)
{
- struct Client *target_p;
- rb_dlink_node *ptr;
- unsigned int hashv;
-
s_assert(name != NULL);
if(EmptyString(name))
return NULL;
- hashv = hash_nick(name);
-
- RB_DLINK_FOREACH(ptr, clientTable[hashv].head)
- {
- target_p = ptr->data;
-
- if(irccmp(name, target_p->name) == 0)
- return target_p;
- }
-
- return NULL;
+ return irc_radixtree_retrieve(client_name_tree, name);
}
/* find_server()
find_server(struct Client *source_p, const char *name)
{
struct Client *target_p;
- rb_dlink_node *ptr;
- unsigned int hashv;
if(EmptyString(name))
return NULL;
return(target_p);
}
- hashv = hash_nick(name);
-
- RB_DLINK_FOREACH(ptr, clientTable[hashv].head)
+ target_p = irc_radixtree_retrieve(client_name_tree, name);
+ if (target_p != NULL)
{
- target_p = ptr->data;
-
- if((IsServer(target_p) || IsMe(target_p)) &&
- irccmp(name, target_p->name) == 0)
- return target_p;
+ if(IsServer(target_p) || IsMe(target_p))
+ return target_p;
}
return NULL;
struct Channel *
find_channel(const char *name)
{
- struct Channel *chptr;
- rb_dlink_node *ptr;
- unsigned int hashv;
-
s_assert(name != NULL);
if(EmptyString(name))
return NULL;
- hashv = hash_channel(name);
-
- RB_DLINK_FOREACH(ptr, channelTable[hashv].head)
- {
- chptr = ptr->data;
-
- if(irccmp(name, chptr->chname) == 0)
- return chptr;
- }
-
- return NULL;
+ return irc_radixtree_retrieve(channel_tree, name);
}
/*
get_or_create_channel(struct Client *client_p, const char *chname, int *isnew)
{
struct Channel *chptr;
- rb_dlink_node *ptr;
- unsigned int hashv;
int len;
const char *s = chname;
s = t;
}
- hashv = hash_channel(s);
-
- RB_DLINK_FOREACH(ptr, channelTable[hashv].head)
+ chptr = irc_radixtree_retrieve(channel_tree, s);
+ if (chptr != NULL)
{
- chptr = ptr->data;
-
- if(irccmp(s, chptr->chname) == 0)
- {
- if(isnew != NULL)
- *isnew = 0;
- return chptr;
- }
+ if (isnew != NULL)
+ *isnew = 0;
+ return chptr;
}
if(isnew != NULL)
*isnew = 1;
chptr = allocate_channel(s);
-
- rb_dlinkAdd(chptr, &chptr->node, &global_channel_list);
-
chptr->channelts = rb_current_time(); /* doesn't hurt to set it here */
- rb_dlinkAddAlloc(chptr, &channelTable[hashv]);
+ rb_dlinkAdd(chptr, &chptr->node, &global_channel_list);
+ irc_radixtree_add(channel_tree, chptr->chname, chptr);
return chptr;
}
"B :Average depth: %s Highest depth: %lu",
buf, deepest);
}
-
- for(i = 0; i < 11; i++)
- {
- sendto_one_numeric(source_p, RPL_STATSDEBUG,
- "B :Nodes with %d entries: %d",
- i, counts[i]);
- }
}
void
hash_stats(struct Client *source_p)
{
- count_hash(source_p, channelTable, CH_MAX, "Channel");
- sendto_one_numeric(source_p, RPL_STATSDEBUG, "B :--");
- count_hash(source_p, clientTable, U_MAX, "Client");
- sendto_one_numeric(source_p, RPL_STATSDEBUG, "B :--");
- count_hash(source_p, idTable, U_MAX, "ID");
- sendto_one_numeric(source_p, RPL_STATSDEBUG, "B :--");
count_hash(source_p, hostTable, HOST_MAX, "Hostname");
}
projects / solanum.git / blobdiff