-/*
- * ircd-ratbox: A slightly useful ircd.
- * hash.h: A header for the ircd hashtable code.
- *
- * Copyright (C) 1990 Jarkko Oikarinen and University of Oulu, Co Center
- * Copyright (C) 1996-2002 Hybrid Development Team
- * Copyright (C) 2002-2004 ircd-ratbox development team
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
- * USA
- *
- * $Id: hash.h 3177 2007-02-01 00:19:14Z jilles $
- */
-
-#ifndef INCLUDED_hash_h
-#define INCLUDED_hash_h
-
-struct Dictionary;
-
-extern rb_dlink_list *clientTable;
-extern rb_dlink_list *channelTable;
-extern rb_dlink_list *idTable;
-extern rb_dlink_list *resvTable;
-extern rb_dlink_list *hostTable;
-extern rb_dlink_list *helpTable;
-
-extern struct Dictionary *nd_dict;
-
-/* Magic value for FNV hash functions */
-#define FNV1_32_INIT 0x811c9dc5UL
-
-/* Client hash table size, used in hash.c/s_debug.c */
-#define U_MAX_BITS 17
-#define U_MAX 131072 /* 2^17 */
-
-/* Channel hash table size, hash.c/s_debug.c */
-#define CH_MAX_BITS 16
-#define CH_MAX 65536 /* 2^16 */
-
-/* hostname hash table size */
-#define HOST_MAX_BITS 17
-#define HOST_MAX 131072 /* 2^17 */
-
-/* RESV/XLINE hash table size, used in hash.c */
-#define R_MAX_BITS 10
-#define R_MAX 1024 /* 2^10 */
-
-
-#define HASH_WALK(i, max, ptr, table) for (i = 0; i < max; i++) { RB_DLINK_FOREACH(ptr, table[i].head)
-#define HASH_WALK_SAFE(i, max, ptr, nptr, table) for (i = 0; i < max; i++) { RB_DLINK_FOREACH_SAFE(ptr, nptr, table[i].head)
-#define HASH_WALK_END }
-
-struct Client;
-struct Channel;
-struct ConfItem;
-struct cachefile;
-struct nd_entry;
-
-extern u_int32_t fnv_hash_upper(const unsigned char *s, int bits);
-extern u_int32_t fnv_hash(const unsigned char *s, int bits);
-extern u_int32_t fnv_hash_len(const unsigned char *s, int bits, int len);
-extern u_int32_t fnv_hash_upper_len(const unsigned char *s, int bits, int len);
-
-extern void init_hash(void);
-
-extern void add_to_client_hash(const char *name, struct Client *client);
-extern void del_from_client_hash(const char *name, struct Client *client);
-extern struct Client *find_client(const char *name);
-extern struct Client *find_named_client(const char *name);
-extern struct Client *find_server(struct Client *source_p, const char *name);
-
-extern void add_to_id_hash(const char *, struct Client *);
-extern void del_from_id_hash(const char *name, struct Client *client);
-extern struct Client *find_id(const char *name);
-
-extern struct Channel *get_or_create_channel(struct Client *client_p, const char *chname, int *isnew);
-extern void del_from_channel_hash(const char *name, struct Channel *chan);
-extern struct Channel *find_channel(const char *name);
-
-extern void add_to_hostname_hash(const char *, struct Client *);
-extern void del_from_hostname_hash(const char *, struct Client *);
-extern rb_dlink_node *find_hostname(const char *);
-
-extern void add_to_resv_hash(const char *name, struct ConfItem *aconf);
-extern void del_from_resv_hash(const char *name, struct ConfItem *aconf);
-extern struct ConfItem *hash_find_resv(const char *name);
-extern void clear_resv_hash(void);
-
-extern void hash_stats(struct Client *);
-
-#endif /* INCLUDED_hash_h */
+/*\r
+ * ircd-ratbox: A slightly useful ircd.\r
+ * hash.h: A header for the ircd hashtable code.\r
+ *\r
+ * Copyright (C) 1990 Jarkko Oikarinen and University of Oulu, Co Center\r
+ * Copyright (C) 1996-2002 Hybrid Development Team\r
+ * Copyright (C) 2002-2005 ircd-ratbox development team\r
+ *\r
+ * This program is free software; you can redistribute it and/or modify\r
+ * it under the terms of the GNU General Public License as published by\r
+ * the Free Software Foundation; either version 2 of the License, or\r
+ * (at your option) any later version.\r
+ *\r
+ * This program is distributed in the hope that it will be useful,\r
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of\r
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\r
+ * GNU General Public License for more details.\r
+ *\r
+ * You should have received a copy of the GNU General Public License\r
+ * along with this program; if not, write to the Free Software\r
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301\r
+ * USA\r
+ *\r
+ * $Id: hash.h 24794 2007-12-28 02:36:59Z androsyn $\r
+ */\r
+\r
+#ifndef INCLUDED_hash_h\r
+#define INCLUDED_hash_h\r
+\r
+extern rb_dlink_list resvTable[];\r
+extern rb_dlink_list ndTable[];\r
+\r
+/* Magic value for FNV hash functions */\r
+#define FNV1_32_INIT 0x811c9dc5UL\r
+\r
+/* Client hash table size, used in hash.c/s_debug.c */\r
+#define U_MAX_BITS 17\r
+#define U_MAX (1<<U_MAX_BITS)\r
+\r
+/* Client fd hash table size, used in hash.c */\r
+#define CLI_FD_MAX 4096\r
+\r
+/* Channel hash table size, hash.c/s_debug.c */\r
+#define CH_MAX_BITS 16\r
+#define CH_MAX (1<<CH_MAX_BITS) /* 2^16 */\r
+\r
+/* hostname hash table size */\r
+#define HOST_MAX_BITS 17\r
+#define HOST_MAX (1<<HOST_MAX_BITS) /* 2^17 */\r
+\r
+/* RESV/XLINE hash table size, used in hash.c */\r
+#define R_MAX_BITS 10\r
+#define R_MAX (1<<R_MAX_BITS) /* 2^10 */\r
+\r
+\r
+#define HASH_WALK(i, max, ptr, table) for (i = 0; i < max; i++) { RB_DLINK_FOREACH(ptr, table[i].head)\r
+#define HASH_WALK_SAFE(i, max, ptr, nptr, table) for (i = 0; i < max; i++) { RB_DLINK_FOREACH_SAFE(ptr, nptr, table[i].head)\r
+#define HASH_WALK_END }\r
+\r
+typedef enum\r
+{\r
+ HASH_CLIENT,\r
+ HASH_ID,\r
+ HASH_CHANNEL,\r
+ HASH_HOSTNAME,\r
+ HASH_RESV\r
+} hash_type;\r
+\r
+struct Client;\r
+struct Channel;\r
+struct ConfItem;\r
+struct cachefile;\r
+struct nd_entry;\r
+\r
+uint32_t fnv_hash_upper(const unsigned char *s, unsigned int bits, unsigned int unused);\r
+uint32_t fnv_hash(const unsigned char *s, unsigned int bits, unsigned int unused);\r
+uint32_t fnv_hash_len(const unsigned char *s, unsigned int bits, unsigned int len);\r
+uint32_t fnv_hash_upper_len(const unsigned char *s, unsigned int bits, unsigned int len);\r
+\r
+void init_hash(void);\r
+\r
+void add_to_hash(hash_type, const char *, void *);\r
+void del_from_hash(hash_type, const char *, void *);\r
+\r
+struct Client *find_any_client(const char *name);\r
+struct Client *find_client(const char *name);\r
+struct Client *find_named_client(const char *name);\r
+struct Client *find_server(struct Client *source_p, const char *name);\r
+\r
+struct Client *find_id(const char *name);\r
+\r
+struct Channel *get_or_create_channel(struct Client *client_p, const char *chname, int *isnew);\r
+struct Channel *find_channel(const char *name);\r
+\r
+rb_dlink_node *find_hostname(const char *);\r
+\r
+struct ConfItem *hash_find_resv(const char *name);\r
+void clear_resv_hash(void);\r
+\r
+void add_to_help_hash(const char *name, struct cachefile *hptr);\r
+void clear_help_hash(void);\r
+struct cachefile *hash_find_help(const char *name, int flags);\r
+\r
+void add_to_nd_hash(const char *name, struct nd_entry *nd);\r
+struct nd_entry *hash_find_nd(const char *name);\r
+\r
+void add_to_cli_fd_hash(struct Client *client_p);\r
+void del_from_cli_fd_hash(struct Client *client_p);\r
+struct Client *find_cli_fd_hash(int fd);\r
+ \r
+void hash_stats(struct Client *);\r
+\r
+#endif /* INCLUDED_hash_h */\r
-/*
- * ircd-ratbox: A slightly useful ircd.
- * hash.c: Maintains hashtables.
- *
- * Copyright (C) 1990 Jarkko Oikarinen and University of Oulu, Co Center
- * Copyright (C) 1996-2002 Hybrid Development Team
- * Copyright (C) 2002-2005 ircd-ratbox development team
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
- * USA
- *
- * $Id: hash.c 3177 2007-02-01 00:19:14Z jilles $
- */
-
-#include "stdinc.h"
-#include "ircd_defs.h"
-#include "s_conf.h"
-#include "channel.h"
-#include "client.h"
-#include "common.h"
-#include "hash.h"
-#include "irc_string.h"
-#include "ircd.h"
-#include "numeric.h"
-#include "send.h"
-#include "msg.h"
-#include "cache.h"
-#include "s_newconf.h"
-
-rb_dlink_list *clientTable;
-rb_dlink_list *channelTable;
-rb_dlink_list *idTable;
-rb_dlink_list *resvTable;
-rb_dlink_list *hostTable;
-
-/*
- * 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);
- resvTable = rb_malloc(sizeof(rb_dlink_list) * R_MAX);
-}
-
-#ifndef RICER_HASHING
-u_int32_t
-fnv_hash_upper(const unsigned char *s, int bits)
-{
- u_int32_t h = FNV1_32_INIT;
-
- while (*s)
- {
- h ^= ToUpper(*s++);
- h += (h<<1) + (h<<4) + (h<<7) + (h << 8) + (h << 24);
- }
- if (bits < 32)
- h = ((h >> bits) ^ h) & ((1<<bits)-1);
- return h;
-}
-
-u_int32_t
-fnv_hash(const unsigned char *s, int bits)
-{
- u_int32_t h = FNV1_32_INIT;
-
- while (*s)
- {
- h ^= *s++;
- h += (h<<1) + (h<<4) + (h<<7) + (h << 8) + (h << 24);
- }
- if (bits < 32)
- h = ((h >> bits) ^ h) & ((1<<bits)-1);
- return h;
-}
-
-u_int32_t
-fnv_hash_len(const unsigned char *s, int bits, int len)
-{
- u_int32_t h = FNV1_32_INIT;
- const unsigned char *x = s + len;
- while (*s && s < x)
- {
- h ^= *s++;
- h += (h<<1) + (h<<4) + (h<<7) + (h << 8) + (h << 24);
- }
- if (bits < 32)
- h = ((h >> bits) ^ h) & ((1<<bits)-1);
- return h;
-}
-
-u_int32_t
-fnv_hash_upper_len(const unsigned char *s, int bits, int len)
-{
- u_int32_t h = FNV1_32_INIT;
- const unsigned char *x = s + len;
- while (*s && s < x)
- {
- h ^= ToUpper(*s++);
- h += (h<<1) + (h<<4) + (h<<7) + (h << 8) + (h << 24);
- }
- if (bits < 32)
- 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()
- *
- * adds an entry to the id hash table
- */
-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]);
-}
-
-/* add_to_client_hash()
- *
- * adds an entry (client/server) to the client hash table
- */
-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]);
-}
-
-/* add_to_hostname_hash()
- *
- * adds a client entry to the hostname hash table
- */
-void
-add_to_hostname_hash(const char *hostname, struct Client *client_p)
-{
- unsigned int hashv;
-
- 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]);
-}
-
-/* add_to_resv_hash()
- *
- * adds a resv channel entry to the resv hash table
- */
-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]);
-}
-
-/* del_from_id_hash()
- *
- * removes an id from the id hash table
- */
-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]);
-}
-
-/* del_from_client_hash()
- *
- * removes a client/server from the client hash table
- */
-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]);
-}
-
-/* del_from_channel_hash()
- *
- * removes a channel from the channel hash table
- */
-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]);
-}
-
-/* del_from_hostname_hash()
- *
- * removes a client entry from the hostname hash table
- */
-void
-del_from_hostname_hash(const char *hostname, struct Client *client_p)
-{
- unsigned int hashv;
-
- if(hostname == NULL || client_p == NULL)
- return;
-
- hashv = hash_hostname(hostname);
-
- rb_dlinkFindDestroy(client_p, &hostTable[hashv]);
-}
-
-/* del_from_resv_hash()
- *
- * removes a resv entry from the resv hash table
- */
-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]);
-}
-
-/* find_id()
- *
- * finds a client entry from the id hash table
- */
-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;
-}
-
-/* find_client()
- *
- * finds a client/server entry from the client hash table
- */
-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;
-
- /* hunting for an id, not a nick */
- 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;
-}
-
-/* find_named_client()
- *
- * finds a client/server entry from the client hash table
- */
-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;
-}
-
-/* find_server()
- *
- * finds a server from the client hash table
- */
-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;
-
- if((source_p == NULL || !MyClient(source_p)) &&
- IsDigit(*name) && strlen(name) == 3)
- {
- target_p = find_id(name);
- return(target_p);
- }
-
- hashv = hash_nick(name);
-
- RB_DLINK_FOREACH(ptr, clientTable[hashv].head)
- {
- target_p = ptr->data;
-
- if((IsServer(target_p) || IsMe(target_p)) &&
- irccmp(name, target_p->name) == 0)
- return target_p;
- }
-
- return NULL;
-}
-
-/* find_hostname()
- *
- * finds a hostname rb_dlink list from the hostname hash table.
- * we return the full rb_dlink list, because you can have multiple
- * entries with the same hostname
- */
-rb_dlink_node *
-find_hostname(const char *hostname)
-{
- unsigned int hashv;
-
- if(EmptyString(hostname))
- return NULL;
-
- hashv = hash_hostname(hostname);
-
- return hostTable[hashv].head;
-}
-
-/* find_channel()
- *
- * finds a channel from the channel hash table
- */
-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;
-}
-
-/*
- * get_or_create_channel
- * inputs - client pointer
- * - channel name
- * - pointer to int flag whether channel was newly created or not
- * output - returns channel block or NULL if illegal name
- * - also modifies *isnew
- *
- * Get Channel block for chname (and allocate a new channel
- * block, if it didn't exist before).
- */
-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;
-
- if(EmptyString(s))
- return NULL;
-
- len = strlen(s);
- if(len > CHANNELLEN)
- {
- char *t;
- if(IsServer(client_p))
- {
- sendto_realops_snomask(SNO_DEBUG, L_ALL,
- "*** Long channel name from %s (%d > %d): %s",
- client_p->name, len, CHANNELLEN, s);
- }
- len = CHANNELLEN;
- t = LOCAL_COPY(s);
- *(t + CHANNELLEN) = '\0';
- s = t;
- }
-
- hashv = hash_channel(s);
-
- RB_DLINK_FOREACH(ptr, channelTable[hashv].head)
- {
- chptr = ptr->data;
-
- if(irccmp(s, chptr->chname) == 0)
- {
- 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]);
-
- return chptr;
-}
-
-/* hash_find_resv()
- *
- * hunts for a resv entry in the resv hash table
- */
-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 = ptr->data;
-
- if(!irccmp(name, aconf->name))
- {
- aconf->port++;
- return aconf;
- }
- }
-
- return NULL;
-}
-
-void
-clear_resv_hash(void)
-{
- struct ConfItem *aconf;
- rb_dlink_node *ptr;
- rb_dlink_node *next_ptr;
- int i;
-
- HASH_WALK_SAFE(i, R_MAX, ptr, next_ptr, resvTable)
- {
- aconf = ptr->data;
-
- /* skip temp resvs */
- if(aconf->hold)
- continue;
-
- free_conf(ptr->data);
- rb_dlinkDestroy(ptr, &resvTable[i]);
- }
- HASH_WALK_END
-}
-
-static void
-output_hash(struct Client *source_p, const char *name, int length, int *counts, int deepest)
-{
- unsigned long total = 0;
- int i;
-
- sendto_one_numeric(source_p, RPL_STATSDEBUG,
- "B :%s Hash Statistics", name);
-
- sendto_one_numeric(source_p, RPL_STATSDEBUG,
- "B :Size: %d Empty: %d (%.3f%%)",
- length, counts[0],
- (float) ((counts[0]*100) / (float) length));
-
- for(i = 1; i < 11; i++)
- {
- total += (counts[i] * i);
- }
-
- /* dont want to divide by 0! --fl */
- if(counts[0] != length)
- sendto_one_numeric(source_p, RPL_STATSDEBUG,
- "B :Average depth: %.3f/%.3f Highest depth: %d",
- (float) (total / (length - counts[0])),
- (float) (total / length), 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];
- int 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");
-}
+/*\r
+ * ircd-ratbox: A slightly useful ircd.\r
+ * hash.c: Maintains hashtables.\r
+ *\r
+ * Copyright (C) 1990 Jarkko Oikarinen and University of Oulu, Co Center\r
+ * Copyright (C) 1996-2002 Hybrid Development Team\r
+ * Copyright (C) 2002-2005 ircd-ratbox development team\r
+ *\r
+ * This program is free software; you can redistribute it and/or modify\r
+ * it under the terms of the GNU General Public License as published by\r
+ * the Free Software Foundation; either version 2 of the License, or\r
+ * (at your option) any later version.\r
+ *\r
+ * This program is distributed in the hope that it will be useful,\r
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of\r
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\r
+ * GNU General Public License for more details.\r
+ *\r
+ * You should have received a copy of the GNU General Public License\r
+ * along with this program; if not, write to the Free Software\r
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301\r
+ * USA\r
+ *\r
+ * $Id: hash.c 25119 2008-03-13 16:57:05Z androsyn $\r
+ */\r
+\r
+#include "stdinc.h"\r
+#include "s_conf.h"\r
+#include "channel.h"\r
+#include "client.h"\r
+#include "hash.h"\r
+#include "ircd.h"\r
+#include "numeric.h"\r
+#include "send.h"\r
+#include "cache.h"\r
+#include "s_newconf.h"\r
+\r
+#define hash_nick(x) (fnv_hash_upper((const unsigned char *)(x), U_MAX_BITS, 0))\r
+#define hash_id(x) (fnv_hash((const unsigned char *)(x), U_MAX_BITS, 0))\r
+#define hash_channel(x) (fnv_hash_upper_len((const unsigned char *)(x), CH_MAX_BITS, 30))\r
+#define hash_hostname(x) (fnv_hash_upper_len((const unsigned char *)(x), HOST_MAX_BITS, 30))\r
+#define hash_resv(x) (fnv_hash_upper_len((const unsigned char *)(x), R_MAX_BITS, 30))\r
+#define hash_cli_fd(x) (x % CLI_FD_MAX)\r
+\r
+\r
+static rb_dlink_list clientbyfdTable[U_MAX];\r
+static rb_dlink_list clientTable[U_MAX];\r
+static rb_dlink_list channelTable[CH_MAX];\r
+static rb_dlink_list idTable[U_MAX];\r
+rb_dlink_list resvTable[R_MAX];\r
+static rb_dlink_list hostTable[HOST_MAX];\r
+static rb_dlink_list helpTable[HELP_MAX];\r
+rb_dlink_list ndTable[U_MAX];\r
+\r
+/*\r
+ * Hashing.\r
+ *\r
+ * The server uses a chained hash table to provide quick and efficient\r
+ * hash table maintenance (providing the hash function works evenly over\r
+ * the input range). The hash table is thus not susceptible to problems\r
+ * of filling all the buckets or the need to rehash.\r
+ * It is expected that the hash table would look something like this\r
+ * during use:\r
+ * +-----+ +-----+ +-----+ +-----+\r
+ * ---| 224 |----| 225 |----| 226 |---| 227 |---\r
+ * +-----+ +-----+ +-----+ +-----+\r
+ * | | |\r
+ * +-----+ +-----+ +-----+\r
+ * | A | | C | | D |\r
+ * +-----+ +-----+ +-----+\r
+ * |\r
+ * +-----+\r
+ * | B |\r
+ * +-----+\r
+ *\r
+ * A - GOPbot, B - chang, C - hanuaway, D - *.mu.OZ.AU\r
+ *\r
+ * The order shown above is just one instant of the server. \r
+ *\r
+ *\r
+ * The hash functions currently used are based Fowler/Noll/Vo hashes\r
+ * which work amazingly well and have a extremely low collision rate\r
+ * For more info see http://www.isthe.com/chongo/tech/comp/fnv/index.html\r
+ *\r
+ * \r
+ */\r
+\r
+/* init_hash()\r
+ *\r
+ * clears the various hashtables\r
+ */\r
+void\r
+init_hash(void)\r
+{\r
+ /* nothing to do here */\r
+}\r
+\r
+\r
+uint32_t\r
+fnv_hash_upper(const unsigned char *s, unsigned int bits, unsigned int unused)\r
+{\r
+ uint32_t h = FNV1_32_INIT;\r
+ bits = 32 - bits;\r
+ while (*s)\r
+ {\r
+ h ^= ToUpper(*s++);\r
+ h += (h<<1) + (h<<4) + (h<<7) + (h << 8) + (h << 24);\r
+ }\r
+ h = (h >> bits) ^ (h & ((2^bits)-1));\r
+ return h;\r
+}\r
+\r
+uint32_t\r
+fnv_hash(const unsigned char *s, unsigned int bits, unsigned int unused)\r
+{\r
+ uint32_t h = FNV1_32_INIT;\r
+ bits = 32 - bits;\r
+ while (*s)\r
+ {\r
+ h ^= *s++;\r
+ h += (h<<1) + (h<<4) + (h<<7) + (h << 8) + (h << 24);\r
+ }\r
+ h = (h >> bits) ^ (h & ((2^bits)-1));\r
+ return h;\r
+}\r
+\r
+uint32_t\r
+fnv_hash_len(const unsigned char *s, unsigned int bits, unsigned int len)\r
+{\r
+ uint32_t h = FNV1_32_INIT;\r
+ bits = 32 - bits;\r
+ const unsigned char *x = s + len;\r
+ while (*s && s < x)\r
+ {\r
+ h ^= *s++;\r
+ h += (h<<1) + (h<<4) + (h<<7) + (h << 8) + (h << 24);\r
+ }\r
+ h = (h >> bits) ^ (h & ((2^bits)-1));\r
+ return h;\r
+}\r
+\r
+uint32_t\r
+fnv_hash_upper_len(const unsigned char *s, unsigned int bits, unsigned int len)\r
+{\r
+ uint32_t h = FNV1_32_INIT;\r
+ bits = 32 - bits;\r
+ const unsigned char *x = s + len;\r
+ while (*s && s < x)\r
+ {\r
+ h ^= ToUpper(*s++);\r
+ h += (h<<1) + (h<<4) + (h<<7) + (h << 8) + (h << 24);\r
+ }\r
+ h = (h >> bits) ^ (h & ((2^bits)-1));\r
+ return h;\r
+}\r
+\r
+static unsigned int\r
+hash_help(const char *name)\r
+{\r
+ unsigned int h = 0;\r
+\r
+ while(*name)\r
+ {\r
+ h += (unsigned int) (ToLower(*name++) & 0xDF);\r
+ }\r
+\r
+ return (h % HELP_MAX);\r
+}\r
+\r
+static struct _hash_function\r
+{\r
+ uint32_t (*func) (unsigned const char *, unsigned int, unsigned int);\r
+ rb_dlink_list *table;\r
+ unsigned int hashbits;\r
+ unsigned int hashlen;\r
+} hash_function[] = {\r
+ { fnv_hash_upper, clientTable, U_MAX_BITS, 0 },\r
+ { fnv_hash, idTable, U_MAX_BITS, 0 },\r
+ { fnv_hash_upper_len, channelTable, CH_MAX_BITS, 30 },\r
+ { fnv_hash_upper_len, hostTable, HOST_MAX_BITS, 30 },\r
+ { fnv_hash_upper_len, resvTable, R_MAX_BITS, 30 }\r
+};\r
+\r
+void\r
+add_to_hash(hash_type type, const char *hashindex, void *pointer)\r
+{\r
+ rb_dlink_list *table = hash_function[type].table;\r
+ unsigned int hashv;\r
+\r
+ if(EmptyString(hashindex) || (pointer == NULL))\r
+ return;\r
+\r
+ hashv = (hash_function[type].func)((const unsigned char *) hashindex, \r
+ hash_function[type].hashbits, \r
+ hash_function[type].hashlen);\r
+// rb_dlinkAddAlloc(pointer, &hash_function[type].table[hashv]);\r
+ rb_dlinkAddAlloc(pointer, &table[hashv]);\r
+}\r
+\r
+void\r
+del_from_hash(hash_type type, const char *hashindex, void *pointer)\r
+{\r
+ rb_dlink_list *table = hash_function[type].table;\r
+ unsigned int hashv;\r
+\r
+ if(EmptyString(hashindex) || (pointer == NULL))\r
+ return;\r
+\r
+ hashv = (hash_function[type].func)((const unsigned char *) hashindex,\r
+ hash_function[type].hashbits,\r
+ hash_function[type].hashlen);\r
+ rb_dlinkFindDestroy(pointer, &table[hashv]);\r
+}\r
+\r
+void\r
+add_to_help_hash(const char *name, struct cachefile *hptr)\r
+{\r
+ unsigned int hashv;\r
+\r
+ if(EmptyString(name) || hptr == NULL)\r
+ return;\r
+\r
+ hashv = hash_help(name);\r
+ rb_dlinkAddAlloc(hptr, &helpTable[hashv]);\r
+}\r
+\r
+void\r
+add_to_nd_hash(const char *name, struct nd_entry *nd)\r
+{\r
+ nd->hashv = hash_nick(name);\r
+ rb_dlinkAdd(nd, &nd->hnode, &ndTable[nd->hashv]);\r
+}\r
+\r
+void\r
+clear_help_hash(void)\r
+{\r
+ rb_dlink_node *ptr;\r
+ rb_dlink_node *next_ptr;\r
+ int i;\r
+\r
+ HASH_WALK_SAFE(i, HELP_MAX, ptr, next_ptr, helpTable)\r
+ {\r
+ free_cachefile(ptr->data);\r
+ rb_dlinkDestroy(ptr, &helpTable[i]);\r
+ }\r
+ HASH_WALK_END\r
+}\r
+\r
+\r
+\r
+\r
+/* find_id()\r
+ *\r
+ * finds a client entry from the id hash table\r
+ */\r
+struct Client *\r
+find_id(const char *name)\r
+{\r
+ struct Client *target_p;\r
+ rb_dlink_node *ptr;\r
+ unsigned int hashv;\r
+\r
+ if(EmptyString(name))\r
+ return NULL;\r
+\r
+ hashv = hash_id(name);\r
+\r
+ RB_DLINK_FOREACH(ptr, idTable[hashv].head)\r
+ {\r
+ target_p = ptr->data;\r
+\r
+ if(strcmp(name, target_p->id) == 0)\r
+ return target_p;\r
+ }\r
+\r
+ return NULL;\r
+}\r
+\r
+/* hash_find_masked_server()\r
+ * \r
+ * Whats happening in this next loop ? Well, it takes a name like\r
+ * foo.bar.edu and proceeds to earch for *.edu and then *.bar.edu.\r
+ * This is for checking full server names against masks although\r
+ * it isnt often done this way in lieu of using matches().\r
+ *\r
+ * Rewrote to do *.bar.edu first, which is the most likely case,\r
+ * also made const correct\r
+ * --Bleep\r
+ */\r
+static struct Client *\r
+hash_find_masked_server(struct Client *source_p, const char *name)\r
+{\r
+ char buf[HOSTLEN + 1];\r
+ char *p = buf;\r
+ char *s;\r
+ struct Client *server;\r
+\r
+ if('*' == *name || '.' == *name)\r
+ return NULL;\r
+\r
+ /* copy it across to give us a buffer to work on */\r
+ rb_strlcpy(buf, name, sizeof(buf));\r
+\r
+ while ((s = strchr(p, '.')) != 0)\r
+ {\r
+ *--s = '*';\r
+ /*\r
+ * Dont need to check IsServer() here since nicknames cant\r
+ * have *'s in them anyway.\r
+ */\r
+ if((server = find_server(source_p, s)))\r
+ return server;\r
+ p = s + 2;\r
+ }\r
+\r
+ return NULL;\r
+}\r
+\r
+/* find_any_client()\r
+ *\r
+ * finds a client/server/masked server entry from the hash\r
+ */\r
+struct Client *\r
+find_any_client(const char *name)\r
+{\r
+ struct Client *target_p;\r
+ rb_dlink_node *ptr;\r
+ unsigned int hashv;\r
+\r
+ s_assert(name != NULL);\r
+ if(EmptyString(name))\r
+ return NULL;\r
+\r
+ /* hunting for an id, not a nick */\r
+ if(IsDigit(*name))\r
+ return (find_id(name));\r
+\r
+ hashv = hash_nick(name);\r
+\r
+ RB_DLINK_FOREACH(ptr, clientTable[hashv].head)\r
+ {\r
+ target_p = ptr->data;\r
+\r
+ if(irccmp(name, target_p->name) == 0)\r
+ return target_p;\r
+ }\r
+\r
+ /* wasnt found, look for a masked server */\r
+ return hash_find_masked_server(NULL, name);\r
+}\r
+\r
+/* find_client()\r
+ *\r
+ * finds a client/server entry from the client hash table\r
+ */\r
+struct Client *\r
+find_client(const char *name)\r
+{\r
+ struct Client *target_p;\r
+ rb_dlink_node *ptr;\r
+ unsigned int hashv;\r
+\r
+ s_assert(name != NULL);\r
+ if(EmptyString(name))\r
+ return NULL;\r
+\r
+ /* hunting for an id, not a nick */\r
+ if(IsDigit(*name))\r
+ return (find_id(name));\r
+\r
+ hashv = hash_nick(name);\r
+\r
+ RB_DLINK_FOREACH(ptr, clientTable[hashv].head)\r
+ {\r
+ target_p = ptr->data;\r
+\r
+ if(irccmp(name, target_p->name) == 0)\r
+ return target_p;\r
+ }\r
+\r
+ return NULL;\r
+}\r
+\r
+/* find_named_client()\r
+ *\r
+ * finds a client/server entry from the client hash table\r
+ */\r
+struct Client *\r
+find_named_client(const char *name)\r
+{\r
+ struct Client *target_p;\r
+ rb_dlink_node *ptr;\r
+ unsigned int hashv;\r
+\r
+ s_assert(name != NULL);\r
+ if(EmptyString(name))\r
+ return NULL;\r
+\r
+ hashv = hash_nick(name);\r
+\r
+ RB_DLINK_FOREACH(ptr, clientTable[hashv].head)\r
+ {\r
+ target_p = ptr->data;\r
+\r
+ if(irccmp(name, target_p->name) == 0)\r
+ return target_p;\r
+ }\r
+\r
+ return NULL;\r
+}\r
+\r
+/* find_server()\r
+ *\r
+ * finds a server from the client hash table\r
+ */\r
+struct Client *\r
+find_server(struct Client *source_p, const char *name)\r
+{\r
+ struct Client *target_p;\r
+ rb_dlink_node *ptr;\r
+ unsigned int hashv;\r
+ \r
+ if(EmptyString(name))\r
+ return NULL;\r
+\r
+ if((source_p == NULL || !MyClient(source_p)) && \r
+ IsDigit(*name) && strlen(name) == 3)\r
+ {\r
+ target_p = find_id(name);\r
+ return(target_p);\r
+ }\r
+\r
+ hashv = hash_nick(name);\r
+\r
+ RB_DLINK_FOREACH(ptr, clientTable[hashv].head)\r
+ {\r
+ target_p = ptr->data;\r
+\r
+ if((IsServer(target_p) || IsMe(target_p)) &&\r
+ irccmp(name, target_p->name) == 0)\r
+ return target_p;\r
+ }\r
+\r
+ /* wasnt found, look for a masked server */\r
+ return hash_find_masked_server(source_p, name);\r
+}\r
+\r
+/* find_hostname()\r
+ *\r
+ * finds a hostname dlink list from the hostname hash table.\r
+ * we return the full dlink list, because you can have multiple\r
+ * entries with the same hostname\r
+ */\r
+rb_dlink_node *\r
+find_hostname(const char *hostname)\r
+{\r
+ unsigned int hashv;\r
+\r
+ if(EmptyString(hostname))\r
+ return NULL;\r
+\r
+ hashv = hash_hostname(hostname);\r
+\r
+ return hostTable[hashv].head;\r
+}\r
+\r
+/* find_channel()\r
+ *\r
+ * finds a channel from the channel hash table\r
+ */\r
+struct Channel *\r
+find_channel(const char *name)\r
+{\r
+ struct Channel *chptr;\r
+ rb_dlink_node *ptr;\r
+ unsigned int hashv;\r
+\r
+ s_assert(name != NULL);\r
+ if(EmptyString(name))\r
+ return NULL;\r
+\r
+ hashv = hash_channel(name);\r
+\r
+ RB_DLINK_FOREACH(ptr, channelTable[hashv].head)\r
+ {\r
+ chptr = ptr->data;\r
+\r
+ if(irccmp(name, chptr->chname) == 0)\r
+ return chptr;\r
+ }\r
+\r
+ return NULL;\r
+}\r
+\r
+/*\r
+ * get_or_create_channel\r
+ * inputs - client pointer\r
+ * - channel name\r
+ * - pointer to int flag whether channel was newly created or not\r
+ * output - returns channel block or NULL if illegal name\r
+ * - also modifies *isnew\r
+ *\r
+ * Get Channel block for chname (and allocate a new channel\r
+ * block, if it didn't exist before).\r
+ */\r
+struct Channel *\r
+get_or_create_channel(struct Client *client_p, const char *chname, int *isnew)\r
+{\r
+ struct Channel *chptr;\r
+ rb_dlink_node *ptr;\r
+ unsigned int hashv;\r
+ int len;\r
+ const char *s = chname;\r
+\r
+ if(EmptyString(s))\r
+ return NULL;\r
+\r
+ len = strlen(s);\r
+ if(len > CHANNELLEN)\r
+ {\r
+ if(IsServer(client_p))\r
+ {\r
+ sendto_realops_flags(UMODE_DEBUG, L_ALL,\r
+ "*** Long channel name from %s (%d > %d): %s",\r
+ client_p->name, len, CHANNELLEN, s);\r
+ }\r
+ len = CHANNELLEN;\r
+ s = LOCAL_COPY_N(s, CHANNELLEN);\r
+ }\r
+\r
+ hashv = hash_channel(s);\r
+\r
+ RB_DLINK_FOREACH(ptr, channelTable[hashv].head)\r
+ {\r
+ chptr = ptr->data;\r
+\r
+ if(irccmp(s, chptr->chname) == 0)\r
+ {\r
+ if(isnew != NULL)\r
+ *isnew = 0;\r
+ return chptr;\r
+ }\r
+ }\r
+\r
+ if(isnew != NULL)\r
+ *isnew = 1;\r
+\r
+ chptr = allocate_channel(s);\r
+\r
+ rb_dlinkAdd(chptr, &chptr->node, &global_channel_list);\r
+\r
+ chptr->channelts = rb_current_time(); /* doesn't hurt to set it here */\r
+\r
+ rb_dlinkAddAlloc(chptr, &channelTable[hashv]);\r
+\r
+ return chptr;\r
+}\r
+\r
+/* hash_find_resv()\r
+ *\r
+ * hunts for a resv entry in the resv hash table\r
+ */\r
+struct ConfItem *\r
+hash_find_resv(const char *name)\r
+{\r
+ struct ConfItem *aconf;\r
+ rb_dlink_node *ptr;\r
+ unsigned int hashv;\r
+\r
+ s_assert(name != NULL);\r
+ if(EmptyString(name))\r
+ return NULL;\r
+\r
+ hashv = hash_resv(name);\r
+\r
+ RB_DLINK_FOREACH(ptr, resvTable[hashv].head)\r
+ {\r
+ aconf = ptr->data;\r
+\r
+ if(!irccmp(name, aconf->host))\r
+ {\r
+ aconf->port++;\r
+ return aconf;\r
+ }\r
+ }\r
+\r
+ return NULL;\r
+}\r
+\r
+struct cachefile *\r
+hash_find_help(const char *name, int flags)\r
+{\r
+ struct cachefile *hptr;\r
+ rb_dlink_node *ptr;\r
+ unsigned int hashv;\r
+\r
+ if(EmptyString(name))\r
+ return NULL;\r
+\r
+ hashv = hash_help(name);\r
+\r
+ RB_DLINK_FOREACH(ptr, helpTable[hashv].head)\r
+ {\r
+ hptr = ptr->data;\r
+\r
+ if((irccmp(name, hptr->name) == 0) &&\r
+ (hptr->flags & flags))\r
+ return hptr;\r
+ }\r
+\r
+ return NULL;\r
+}\r
+\r
+void\r
+clear_resv_hash(void)\r
+{\r
+ struct ConfItem *aconf;\r
+ rb_dlink_node *ptr;\r
+ rb_dlink_node *next_ptr;\r
+ int i;\r
+\r
+ HASH_WALK_SAFE(i, R_MAX, ptr, next_ptr, resvTable)\r
+ {\r
+ aconf = ptr->data;\r
+\r
+ /* skip temp resvs */\r
+ if(aconf->flags & CONF_FLAGS_TEMPORARY)\r
+ continue;\r
+\r
+ free_conf(ptr->data);\r
+ rb_dlinkDestroy(ptr, &resvTable[i]);\r
+ }\r
+ HASH_WALK_END\r
+}\r
+\r
+struct nd_entry *\r
+hash_find_nd(const char *name)\r
+{\r
+ struct nd_entry *nd;\r
+ rb_dlink_node *ptr;\r
+ unsigned int hashv;\r
+\r
+ if(EmptyString(name))\r
+ return NULL;\r
+\r
+ hashv = hash_nick(name);\r
+\r
+ RB_DLINK_FOREACH(ptr, ndTable[hashv].head)\r
+ {\r
+ nd = ptr->data;\r
+\r
+ if(!irccmp(name, nd->name))\r
+ return nd;\r
+ }\r
+\r
+ return NULL;\r
+}\r
+\r
+void\r
+add_to_cli_fd_hash(struct Client *client_p)\r
+{\r
+ rb_dlinkAddAlloc(client_p, &clientbyfdTable[hash_cli_fd(rb_get_fd(client_p->localClient->F))]);\r
+}\r
+\r
+\r
+void\r
+del_from_cli_fd_hash(struct Client *client_p)\r
+{\r
+ unsigned int hashv;\r
+ hashv = hash_cli_fd(rb_get_fd(client_p->localClient->F));\r
+ rb_dlinkFindDestroy(client_p, &clientbyfdTable[hashv]);\r
+}\r
+\r
+struct Client *\r
+find_cli_fd_hash(int fd)\r
+{\r
+ struct Client *target_p;\r
+ rb_dlink_node *ptr;\r
+ unsigned int hashv;\r
+ hashv = hash_cli_fd(fd);\r
+ RB_DLINK_FOREACH(ptr, clientbyfdTable[hashv].head)\r
+ {\r
+ target_p = ptr->data;\r
+ if(rb_get_fd(target_p->localClient->F) == fd)\r
+ return target_p;\r
+ }\r
+ return NULL; \r
+}\r
+\r
+static void\r
+output_hash(struct Client *source_p, const char *name, int length, int *counts, int deepest)\r
+{\r
+ unsigned long total = 0;\r
+ char buf[128];\r
+ int i;\r
+\r
+ sendto_one_numeric(source_p, RPL_STATSDEBUG, "B :%s Hash Statistics", name);\r
+\r
+ /* rb_snprintf which sendto_one_* uses doesn't support float formats */\r
+#ifdef HAVE_SNPRINTF\r
+ snprintf(buf, sizeof(buf), \r
+#else\r
+ sprintf(buf, \r
+#endif\r
+ "%.3f%%", (float) ((counts[0]*100) / (float) length));\r
+ sendto_one_numeric(source_p, RPL_STATSDEBUG, "B :Size: %d Empty: %d (%s)",\r
+ length, counts[0], buf);\r
+\r
+ for(i = 1; i < 11; i++)\r
+ {\r
+ total += (counts[i] * i);\r
+ }\r
+\r
+ /* dont want to divide by 0! --fl */\r
+ if(counts[0] != length) \r
+ {\r
+#ifdef HAVE_SNPRINTF\r
+ snprintf(buf, sizeof(buf),\r
+#else\r
+ sprintf(buf,\r
+#endif\r
+ "%.3f%%/%.3f%%", (float) (total / (length - counts[0])), \r
+ (float) (total / length));\r
+ sendto_one_numeric(source_p, RPL_STATSDEBUG,\r
+ "B :Average depth: %s Highest depth: %d",\r
+ buf, deepest);\r
+ }\r
+ for(i = 0; i < 11; i++)\r
+ {\r
+ sendto_one_numeric(source_p, RPL_STATSDEBUG,\r
+ "B :Nodes with %d entries: %d",\r
+ i, counts[i]);\r
+ }\r
+}\r
+ \r
+\r
+static void\r
+count_hash(struct Client *source_p, rb_dlink_list *table, int length, const char *name)\r
+{\r
+ int counts[11];\r
+ unsigned long deepest = 0;\r
+ int i;\r
+\r
+ memset(counts, 0, sizeof(counts));\r
+ \r
+ for(i = 0; i < length; i++)\r
+ {\r
+ if(rb_dlink_list_length(&table[i]) >= 10)\r
+ counts[10]++;\r
+ else\r
+ counts[rb_dlink_list_length(&table[i])]++;\r
+\r
+ if(rb_dlink_list_length(&table[i]) > deepest)\r
+ deepest = rb_dlink_list_length(&table[i]);\r
+ }\r
+\r
+ output_hash(source_p, name, length, counts, deepest);\r
+}\r
+\r
+void\r
+hash_stats(struct Client *source_p)\r
+{\r
+ count_hash(source_p, channelTable, CH_MAX, "Channel");\r
+ sendto_one_numeric(source_p, RPL_STATSDEBUG, "B :--");\r
+ count_hash(source_p, clientTable, U_MAX, "Client");\r
+ sendto_one_numeric(source_p, RPL_STATSDEBUG, "B :--");\r
+ count_hash(source_p, idTable, U_MAX, "ID");\r
+ sendto_one_numeric(source_p, RPL_STATSDEBUG, "B :--");\r
+ count_hash(source_p, hostTable, HOST_MAX, "Hostname");\r
+ sendto_one_numeric(source_p, RPL_STATSDEBUG, "B :--");\r
+ count_hash(source_p, clientbyfdTable, CLI_FD_MAX, "Client by FD");\r
+} \r