X-Git-Url: https://jfr.im/git/solanum.git/blobdiff_plain/ff12cc94790de2e87e78ee7aa378f21fa415d73c..573896f6394104e46e8f6f1fccfd9ce0eaac65a8:/ircd/hash.c

diff --git a/ircd/hash.c b/ircd/hash.c
index 74aa5551..7658536d 100644
--- a/ircd/hash.c
+++ b/ircd/hash.c
@@ -39,58 +39,22 @@
 #include "cache.h"
 #include "s_newconf.h"
 #include "s_assert.h"
+#include "irc_dictionary.h"
+#include "irc_radixtree.h"
 
-#define ZCONNID_MAX 64 /* i doubt we'll have this many ziplinks ;) */
+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;
 
-#define hash_cli_connid(x)	(x % CLI_CONNID_MAX)
-#define hash_zconnid(x)		(x % ZCONNID_MAX)
-
-static rb_dlink_list clientbyconnidTable[CLI_CONNID_MAX];
-static rb_dlink_list clientbyzconnidTable[ZCONNID_MAX];
-
-rb_dlink_list *clientTable;
-rb_dlink_list *channelTable;
-rb_dlink_list *idTable;
-rb_dlink_list *resvTable;
-rb_dlink_list *hostTable;
+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
@@ -98,14 +62,17 @@ rb_dlink_list *hostTable;
 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);
-	resvTable = rb_malloc(sizeof(rb_dlink_list) * R_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);
 }
 
-#ifndef RICER_HASHING
 u_int32_t
 fnv_hash_upper(const unsigned char *s, int bits)
 {
@@ -165,58 +132,6 @@ fnv_hash_upper_len(const unsigned char *s, int bits, int len)
 		h = ((h >> bits) ^ h) & ((1<<bits)-1);
 	return h;
 }
-#endif
-
-/* 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);
-}
-
-/* hash_resv()
- *
- * hashes a resv channel name, based on first 30 chars only
- */
-static u_int32_t
-hash_resv(const char *name)
-{
-	return fnv_hash_upper_len((const unsigned char *) name, R_MAX_BITS, 30);
-}
 
 /* add_to_id_hash()
  *
@@ -225,13 +140,10 @@ hash_resv(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()
@@ -241,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()
@@ -259,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()
@@ -277,15 +194,12 @@ add_to_hostname_hash(const char *hostname, struct Client *client_p)
 void
 add_to_resv_hash(const char *name, struct ConfItem *aconf)
 {
-	unsigned int hashv;
-
 	s_assert(!EmptyString(name));
 	s_assert(aconf != NULL);
 	if(EmptyString(name) || aconf == NULL)
 		return;
 
-	hashv = hash_resv(name);
-	rb_dlinkAddAlloc(aconf, &resvTable[hashv]);
+	irc_radixtree_add(resv_tree, name, aconf);
 }
 
 /* del_from_id_hash()
@@ -295,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()
@@ -313,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()
@@ -332,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()
@@ -351,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()
@@ -368,16 +281,12 @@ del_from_hostname_hash(const char *hostname, struct Client *client_p)
 void
 del_from_resv_hash(const char *name, struct ConfItem *aconf)
 {
-	unsigned int hashv;
-
 	s_assert(name != NULL);
 	s_assert(aconf != NULL);
 	if(EmptyString(name) || aconf == NULL)
 		return;
 
-	hashv = hash_resv(name);
-
-	rb_dlinkFindDestroy(aconf, &resvTable[hashv]);
+	irc_radixtree_delete(resv_tree, name);
 }
 
 /* find_id()
@@ -387,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()
@@ -414,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;
@@ -426,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()
@@ -446,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()
@@ -475,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;
@@ -488,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;
@@ -511,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()
@@ -528,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);
 }
 
 /*
@@ -564,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;
 
@@ -588,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;
 }
@@ -624,24 +463,16 @@ struct ConfItem *
 hash_find_resv(const char *name)
 {
 	struct ConfItem *aconf;
-	rb_dlink_node *ptr;
-	unsigned int hashv;
 
 	s_assert(name != NULL);
 	if(EmptyString(name))
 		return NULL;
 
-	hashv = hash_resv(name);
-
-	RB_DLINK_FOREACH(ptr, resvTable[hashv].head)
+	aconf = irc_radixtree_retrieve(resv_tree, name);
+	if (aconf != NULL)
 	{
-		aconf = ptr->data;
-
-		if(!irccmp(name, aconf->host))
-		{
-			aconf->port++;
-			return aconf;
-		}
+		aconf->port++;
+		return aconf;
 	}
 
 	return NULL;
@@ -651,155 +482,55 @@ void
 clear_resv_hash(void)
 {
 	struct ConfItem *aconf;
-	rb_dlink_node *ptr;
-	rb_dlink_node *next_ptr;
-	int i;
+	struct irc_radixtree_iteration_state iter;
 
-	HASH_WALK_SAFE(i, R_MAX, ptr, next_ptr, resvTable)
+	IRC_RADIXTREE_FOREACH(aconf, &iter, resv_tree)
 	{
-		aconf = ptr->data;
-
 		/* skip temp resvs */
 		if(aconf->hold)
 			continue;
 
-		free_conf(ptr->data);
-		rb_dlinkDestroy(ptr, &resvTable[i]);
+		irc_radixtree_delete(resv_tree, aconf->host);
+		free_conf(aconf);
 	}
-	HASH_WALK_END
 }
 
 void
 add_to_zconnid_hash(struct Client *client_p)
 {
-	unsigned int hashv;
-	hashv = hash_zconnid(client_p->localClient->zconnid);
-	rb_dlinkAddAlloc(client_p, &clientbyzconnidTable[hashv]);       
+	irc_dictionary_add(client_zconnid_tree, IRC_UINT_TO_POINTER(client_p->localClient->zconnid), client_p);
 }
 
 void
 del_from_zconnid_hash(struct Client *client_p)
 {
-	unsigned int hashv;
-	hashv = hash_zconnid(client_p->localClient->zconnid);
-	rb_dlinkFindDestroy(client_p, &clientbyzconnidTable[hashv]); 
+	irc_dictionary_delete(client_zconnid_tree, IRC_UINT_TO_POINTER(client_p->localClient->zconnid));
 }
 
 void
 add_to_cli_connid_hash(struct Client *client_p)
 {
-	unsigned int hashv;
-	hashv = hash_cli_connid(client_p->localClient->connid);
-	rb_dlinkAddAlloc(client_p, &clientbyconnidTable[hashv]);
+	irc_dictionary_add(client_connid_tree, IRC_UINT_TO_POINTER(client_p->localClient->connid), client_p);
 }
 
 void
 del_from_cli_connid_hash(struct Client *client_p)
 {
-	unsigned int hashv;
-	hashv = hash_cli_connid(client_p->localClient->connid);
-	rb_dlinkFindDestroy(client_p, &clientbyconnidTable[hashv]);
+	irc_dictionary_delete(client_connid_tree, IRC_UINT_TO_POINTER(client_p->localClient->connid));
 }
 
 struct Client *
-find_cli_connid_hash(int connid)
+find_cli_connid_hash(uint32_t connid)
 {
 	struct Client *target_p;
-	rb_dlink_node *ptr;
-	unsigned int hashv;
-	hashv = hash_cli_connid(connid);
-	RB_DLINK_FOREACH(ptr, clientbyconnidTable[hashv].head)
-	{
-		target_p = ptr->data;
-		if(target_p->localClient->connid == connid)
-			return target_p;
-	}
-
-	hashv = hash_zconnid(connid);
-	RB_DLINK_FOREACH(ptr, clientbyzconnidTable[hashv].head)
-	{
-		target_p = ptr->data;
-		if(target_p->localClient->zconnid == connid)
-			return target_p;
-	}
-
-	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);
+	target_p = irc_dictionary_retrieve(client_connid_tree, IRC_UINT_TO_POINTER(connid));
+	if (target_p != NULL)
+		return target_p;
 
-	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);
-	}
+	target_p = irc_dictionary_retrieve(client_zconnid_tree, IRC_UINT_TO_POINTER(connid));
+	if (target_p != NULL)
+		return target_p;
 
-	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");
-	sendto_one_numeric(source_p, RPL_STATSDEBUG, "B :--");
-	count_hash(source_p, clientbyconnidTable, CLI_CONNID_MAX, "Client by connection id");
+	return NULL;
 }