X-Git-Url: https://jfr.im/git/solanum.git/blobdiff_plain/46be39faab8f50545821a8030c36b18232c67a26..a393a68a0e1db47faafb71308f9bc93c3704bcb0:/ircd/hash.c diff --git a/ircd/hash.c b/ircd/hash.c index 11831bea..7658536d 100644 --- a/ircd/hash.c +++ b/ircd/hash.c @@ -42,53 +42,19 @@ #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; +struct irc_radixtree *hostname_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 @@ -96,15 +62,15 @@ struct irc_radixtree *resv_tree = NULL; 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); + + hostname_tree = irc_radixtree_create("hostname", irc_radixtree_irccasecanon); } u_int32_t @@ -167,47 +133,6 @@ fnv_hash_upper_len(const unsigned char *s, int bits, int len) 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 - * be more dynamic than rest. - */ -static u_int32_t -hash_hostname(const char *name) -{ - return fnv_hash_upper_len((const unsigned char *) name, HOST_MAX_BITS, 30); -} - /* add_to_id_hash() * * adds an entry to the id hash table @@ -215,13 +140,10 @@ hash_hostname(const char *name) 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() @@ -231,15 +153,12 @@ add_to_id_hash(const char *name, struct Client *client_p) 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() @@ -249,15 +168,23 @@ add_to_client_hash(const char *name, struct Client *client_p) void add_to_hostname_hash(const char *hostname, struct Client *client_p) { - unsigned int hashv; + rb_dlink_list *list; s_assert(hostname != NULL); s_assert(client_p != NULL); if(EmptyString(hostname) || (client_p == NULL)) return; - hashv = hash_hostname(hostname); - rb_dlinkAddAlloc(client_p, &hostTable[hashv]); + list = irc_radixtree_retrieve(hostname_tree, hostname); + if (list != NULL) + { + rb_dlinkAddAlloc(client_p, list); + return; + } + + list = rb_malloc(sizeof(*list)); + irc_radixtree_add(hostname_tree, hostname, list); + rb_dlinkAddAlloc(client_p, list); } /* add_to_resv_hash() @@ -282,15 +209,12 @@ add_to_resv_hash(const char *name, struct ConfItem *aconf) 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() @@ -300,16 +224,13 @@ del_from_id_hash(const char *id, struct Client *client_p) 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() @@ -319,16 +240,13 @@ del_from_client_hash(const char *name, struct Client *client_p) 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() @@ -338,14 +256,22 @@ del_from_channel_hash(const char *name, struct Channel *chptr) void del_from_hostname_hash(const char *hostname, struct Client *client_p) { - unsigned int hashv; + rb_dlink_list *list; if(hostname == NULL || client_p == NULL) return; - hashv = hash_hostname(hostname); + list = irc_radixtree_retrieve(hostname_tree, hostname); + if (list == NULL) + return; - rb_dlinkFindDestroy(client_p, &hostTable[hashv]); + rb_dlinkFindDestroy(client_p, list); + + if (rb_dlink_list_length(list) == 0) + { + irc_radixtree_delete(hostname_tree, hostname); + rb_free(list); + } } /* del_from_resv_hash() @@ -370,24 +296,10 @@ del_from_resv_hash(const char *name, struct ConfItem *aconf) 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() @@ -397,10 +309,6 @@ find_id(const char *name) 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; @@ -409,17 +317,7 @@ find_client(const char *name) 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() @@ -429,25 +327,11 @@ find_client(const char *name) 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() @@ -458,8 +342,6 @@ struct Client * 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; @@ -471,15 +353,11 @@ find_server(struct Client *source_p, const char *name) 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; @@ -494,14 +372,16 @@ find_server(struct Client *source_p, const char *name) rb_dlink_node * find_hostname(const char *hostname) { - unsigned int hashv; + rb_dlink_list *hlist; if(EmptyString(hostname)) return NULL; - hashv = hash_hostname(hostname); + hlist = irc_radixtree_retrieve(hostname_tree, hostname); + if (hlist == NULL) + return NULL; - return hostTable[hashv].head; + return hlist->head; } /* find_channel() @@ -511,25 +391,11 @@ find_hostname(const char *hostname) 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); } /* @@ -547,8 +413,6 @@ struct Channel * 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; @@ -571,30 +435,22 @@ get_or_create_channel(struct Client *client_p, const char *chname, int *isnew) 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; } @@ -678,79 +534,3 @@ find_cli_connid_hash(uint32_t connid) return NULL; } - -static void -output_hash(struct Client *source_p, const char *name, int length, int *counts, unsigned long deepest) -{ - unsigned long total = 0; - int i; - char buf[128]; - - sendto_one_numeric(source_p, RPL_STATSDEBUG, - "B :%s Hash Statistics", name); - - snprintf(buf, sizeof buf, "%.3f%%", - (float) ((counts[0]*100) / (float) length)); - sendto_one_numeric(source_p, RPL_STATSDEBUG, - "B :Size: %d Empty: %d (%s)", - length, counts[0], buf); - - for(i = 1; i < 11; i++) - { - total += (counts[i] * i); - } - - /* dont want to divide by 0! --fl */ - if(counts[0] != length) - { - snprintf(buf, sizeof buf, "%.3f/%.3f", - (float) (total / (length - counts[0])), - (float) (total / length)); - sendto_one_numeric(source_p, RPL_STATSDEBUG, - "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]); - } -} - - -static void -count_hash(struct Client *source_p, rb_dlink_list *table, int length, const char *name) -{ - int counts[11]; - unsigned long deepest = 0; - int i; - - memset(counts, 0, sizeof(counts)); - - for(i = 0; i < length; i++) - { - if(rb_dlink_list_length(&table[i]) >= 10) - counts[10]++; - else - counts[rb_dlink_list_length(&table[i])]++; - - if(rb_dlink_list_length(&table[i]) > deepest) - deepest = rb_dlink_list_length(&table[i]); - } - - output_hash(source_p, name, length, counts, deepest); -} - -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"); -}