2 * ircd-ratbox: A slightly useful ircd.
3 * hash.c: Maintains hashtables.
5 * Copyright (C) 1990 Jarkko Oikarinen and University of Oulu, Co Center
6 * Copyright (C) 1996-2002 Hybrid Development Team
7 * Copyright (C) 2002-2005 ircd-ratbox development team
9 * This program is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License as published by
11 * the Free Software Foundation; either version 2 of the License, or
12 * (at your option) any later version.
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
19 * You should have received a copy of the GNU General Public License
20 * along with this program; if not, write to the Free Software
21 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
24 * $Id: hash.c 3177 2007-02-01 00:19:14Z jilles $
28 #include "ircd_defs.h"
40 #include "s_newconf.h"
42 #include "irc_dictionary.h"
43 #include "irc_radixtree.h"
45 rb_dlink_list
*channelTable
;
46 rb_dlink_list
*hostTable
;
48 struct Dictionary
*client_connid_tree
= NULL
;
49 struct Dictionary
*client_zconnid_tree
= NULL
;
50 struct irc_radixtree
*client_id_tree
= NULL
;
51 struct irc_radixtree
*client_name_tree
= NULL
;
53 struct irc_radixtree
*resv_tree
= NULL
;
56 * look in whowas.c for the missing ...[WW_MAX]; entry
62 * The server uses a chained hash table to provide quick and efficient
63 * hash table maintenance (providing the hash function works evenly over
64 * the input range). The hash table is thus not susceptible to problems
65 * of filling all the buckets or the need to rehash.
66 * It is expected that the hash table would look something like this
68 * +-----+ +-----+ +-----+ +-----+
69 * ---| 224 |----| 225 |----| 226 |---| 227 |---
70 * +-----+ +-----+ +-----+ +-----+
72 * +-----+ +-----+ +-----+
74 * +-----+ +-----+ +-----+
80 * A - GOPbot, B - chang, C - hanuaway, D - *.mu.OZ.AU
82 * The order shown above is just one instant of the server.
85 * The hash functions currently used are based Fowler/Noll/Vo hashes
86 * which work amazingly well and have a extremely low collision rate
87 * For more info see http://www.isthe.com/chongo/tech/comp/fnv/index.html
94 * clears the various hashtables
99 channelTable
= rb_malloc(sizeof(rb_dlink_list
) * CH_MAX
);
100 hostTable
= rb_malloc(sizeof(rb_dlink_list
) * HOST_MAX
);
102 client_connid_tree
= irc_dictionary_create("client connid", irc_uint32cmp
);
103 client_zconnid_tree
= irc_dictionary_create("client zconnid", irc_uint32cmp
);
104 client_id_tree
= irc_radixtree_create("client id", NULL
);
105 client_name_tree
= irc_radixtree_create("client name", irc_radixtree_irccasecanon
);
107 resv_tree
= irc_radixtree_create("resv", irc_radixtree_irccasecanon
);
111 fnv_hash_upper(const unsigned char *s
, int bits
)
113 u_int32_t h
= FNV1_32_INIT
;
118 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
121 h
= ((h
>> bits
) ^ h
) & ((1<<bits
)-1);
126 fnv_hash(const unsigned char *s
, int bits
)
128 u_int32_t h
= FNV1_32_INIT
;
133 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
136 h
= ((h
>> bits
) ^ h
) & ((1<<bits
)-1);
141 fnv_hash_len(const unsigned char *s
, int bits
, int len
)
143 u_int32_t h
= FNV1_32_INIT
;
144 const unsigned char *x
= s
+ len
;
148 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
151 h
= ((h
>> bits
) ^ h
) & ((1<<bits
)-1);
156 fnv_hash_upper_len(const unsigned char *s
, int bits
, int len
)
158 u_int32_t h
= FNV1_32_INIT
;
159 const unsigned char *x
= s
+ len
;
163 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
166 h
= ((h
>> bits
) ^ h
) & ((1<<bits
)-1);
172 * hashes a channel name, based on first 30 chars only for efficiency
175 hash_channel(const char *name
)
177 return fnv_hash_upper_len((const unsigned char *) name
, CH_MAX_BITS
, 30);
182 * hashes a hostname, based on first 30 chars only, as thats likely to
183 * be more dynamic than rest.
186 hash_hostname(const char *name
)
188 return fnv_hash_upper_len((const unsigned char *) name
, HOST_MAX_BITS
, 30);
193 * adds an entry to the id hash table
196 add_to_id_hash(const char *name
, struct Client
*client_p
)
198 if(EmptyString(name
) || (client_p
== NULL
))
201 irc_radixtree_add(client_id_tree
, name
, client_p
);
204 /* add_to_client_hash()
206 * adds an entry (client/server) to the client hash table
209 add_to_client_hash(const char *name
, struct Client
*client_p
)
211 s_assert(name
!= NULL
);
212 s_assert(client_p
!= NULL
);
213 if(EmptyString(name
) || (client_p
== NULL
))
216 irc_radixtree_add(client_name_tree
, name
, client_p
);
219 /* add_to_hostname_hash()
221 * adds a client entry to the hostname hash table
224 add_to_hostname_hash(const char *hostname
, struct Client
*client_p
)
228 s_assert(hostname
!= NULL
);
229 s_assert(client_p
!= NULL
);
230 if(EmptyString(hostname
) || (client_p
== NULL
))
233 hashv
= hash_hostname(hostname
);
234 rb_dlinkAddAlloc(client_p
, &hostTable
[hashv
]);
237 /* add_to_resv_hash()
239 * adds a resv channel entry to the resv hash table
242 add_to_resv_hash(const char *name
, struct ConfItem
*aconf
)
244 s_assert(!EmptyString(name
));
245 s_assert(aconf
!= NULL
);
246 if(EmptyString(name
) || aconf
== NULL
)
249 irc_radixtree_add(resv_tree
, name
, aconf
);
252 /* del_from_id_hash()
254 * removes an id from the id hash table
257 del_from_id_hash(const char *id
, struct Client
*client_p
)
259 s_assert(id
!= NULL
);
260 s_assert(client_p
!= NULL
);
261 if(EmptyString(id
) || client_p
== NULL
)
264 irc_radixtree_delete(client_id_tree
, id
);
267 /* del_from_client_hash()
269 * removes a client/server from the client hash table
272 del_from_client_hash(const char *name
, struct Client
*client_p
)
274 /* no s_asserts, this can happen when removing a client that
277 if(EmptyString(name
) || client_p
== NULL
)
280 irc_radixtree_delete(client_name_tree
, name
);
283 /* del_from_channel_hash()
285 * removes a channel from the channel hash table
288 del_from_channel_hash(const char *name
, struct Channel
*chptr
)
292 s_assert(name
!= NULL
);
293 s_assert(chptr
!= NULL
);
295 if(EmptyString(name
) || chptr
== NULL
)
298 hashv
= hash_channel(name
);
299 rb_dlinkFindDestroy(chptr
, &channelTable
[hashv
]);
302 /* del_from_hostname_hash()
304 * removes a client entry from the hostname hash table
307 del_from_hostname_hash(const char *hostname
, struct Client
*client_p
)
311 if(hostname
== NULL
|| client_p
== NULL
)
314 hashv
= hash_hostname(hostname
);
316 rb_dlinkFindDestroy(client_p
, &hostTable
[hashv
]);
319 /* del_from_resv_hash()
321 * removes a resv entry from the resv hash table
324 del_from_resv_hash(const char *name
, struct ConfItem
*aconf
)
326 s_assert(name
!= NULL
);
327 s_assert(aconf
!= NULL
);
328 if(EmptyString(name
) || aconf
== NULL
)
331 irc_radixtree_delete(resv_tree
, name
);
336 * finds a client entry from the id hash table
339 find_id(const char *name
)
341 if(EmptyString(name
))
344 return irc_radixtree_retrieve(client_id_tree
, name
);
349 * finds a client/server entry from the client hash table
352 find_client(const char *name
)
354 s_assert(name
!= NULL
);
355 if(EmptyString(name
))
358 /* hunting for an id, not a nick */
360 return (find_id(name
));
362 return irc_radixtree_retrieve(client_name_tree
, name
);
365 /* find_named_client()
367 * finds a client/server entry from the client hash table
370 find_named_client(const char *name
)
372 s_assert(name
!= NULL
);
373 if(EmptyString(name
))
376 return irc_radixtree_retrieve(client_name_tree
, name
);
381 * finds a server from the client hash table
384 find_server(struct Client
*source_p
, const char *name
)
386 struct Client
*target_p
;
388 if(EmptyString(name
))
391 if((source_p
== NULL
|| !MyClient(source_p
)) &&
392 IsDigit(*name
) && strlen(name
) == 3)
394 target_p
= find_id(name
);
398 target_p
= irc_radixtree_retrieve(client_name_tree
, name
);
399 if (target_p
!= NULL
)
401 if(IsServer(target_p
) || IsMe(target_p
))
410 * finds a hostname rb_dlink list from the hostname hash table.
411 * we return the full rb_dlink list, because you can have multiple
412 * entries with the same hostname
415 find_hostname(const char *hostname
)
419 if(EmptyString(hostname
))
422 hashv
= hash_hostname(hostname
);
424 return hostTable
[hashv
].head
;
429 * finds a channel from the channel hash table
432 find_channel(const char *name
)
434 struct Channel
*chptr
;
438 s_assert(name
!= NULL
);
439 if(EmptyString(name
))
442 hashv
= hash_channel(name
);
444 RB_DLINK_FOREACH(ptr
, channelTable
[hashv
].head
)
448 if(irccmp(name
, chptr
->chname
) == 0)
456 * get_or_create_channel
457 * inputs - client pointer
459 * - pointer to int flag whether channel was newly created or not
460 * output - returns channel block or NULL if illegal name
461 * - also modifies *isnew
463 * Get Channel block for chname (and allocate a new channel
464 * block, if it didn't exist before).
467 get_or_create_channel(struct Client
*client_p
, const char *chname
, int *isnew
)
469 struct Channel
*chptr
;
473 const char *s
= chname
;
482 if(IsServer(client_p
))
484 sendto_realops_snomask(SNO_DEBUG
, L_ALL
,
485 "*** Long channel name from %s (%d > %d): %s",
486 client_p
->name
, len
, CHANNELLEN
, s
);
490 *(t
+ CHANNELLEN
) = '\0';
494 hashv
= hash_channel(s
);
496 RB_DLINK_FOREACH(ptr
, channelTable
[hashv
].head
)
500 if(irccmp(s
, chptr
->chname
) == 0)
511 chptr
= allocate_channel(s
);
513 rb_dlinkAdd(chptr
, &chptr
->node
, &global_channel_list
);
515 chptr
->channelts
= rb_current_time(); /* doesn't hurt to set it here */
517 rb_dlinkAddAlloc(chptr
, &channelTable
[hashv
]);
524 * hunts for a resv entry in the resv hash table
527 hash_find_resv(const char *name
)
529 struct ConfItem
*aconf
;
531 s_assert(name
!= NULL
);
532 if(EmptyString(name
))
535 aconf
= irc_radixtree_retrieve(resv_tree
, name
);
546 clear_resv_hash(void)
548 struct ConfItem
*aconf
;
549 struct irc_radixtree_iteration_state iter
;
551 IRC_RADIXTREE_FOREACH(aconf
, &iter
, resv_tree
)
553 /* skip temp resvs */
557 irc_radixtree_delete(resv_tree
, aconf
->host
);
563 add_to_zconnid_hash(struct Client
*client_p
)
565 irc_dictionary_add(client_zconnid_tree
, IRC_UINT_TO_POINTER(client_p
->localClient
->zconnid
), client_p
);
569 del_from_zconnid_hash(struct Client
*client_p
)
571 irc_dictionary_delete(client_zconnid_tree
, IRC_UINT_TO_POINTER(client_p
->localClient
->zconnid
));
575 add_to_cli_connid_hash(struct Client
*client_p
)
577 irc_dictionary_add(client_connid_tree
, IRC_UINT_TO_POINTER(client_p
->localClient
->connid
), client_p
);
581 del_from_cli_connid_hash(struct Client
*client_p
)
583 irc_dictionary_delete(client_connid_tree
, IRC_UINT_TO_POINTER(client_p
->localClient
->connid
));
587 find_cli_connid_hash(uint32_t connid
)
589 struct Client
*target_p
;
591 target_p
= irc_dictionary_retrieve(client_connid_tree
, IRC_UINT_TO_POINTER(connid
));
592 if (target_p
!= NULL
)
595 target_p
= irc_dictionary_retrieve(client_zconnid_tree
, IRC_UINT_TO_POINTER(connid
));
596 if (target_p
!= NULL
)
603 output_hash(struct Client
*source_p
, const char *name
, int length
, int *counts
, unsigned long deepest
)
605 unsigned long total
= 0;
609 sendto_one_numeric(source_p
, RPL_STATSDEBUG
,
610 "B :%s Hash Statistics", name
);
612 snprintf(buf
, sizeof buf
, "%.3f%%",
613 (float) ((counts
[0]*100) / (float) length
));
614 sendto_one_numeric(source_p
, RPL_STATSDEBUG
,
615 "B :Size: %d Empty: %d (%s)",
616 length
, counts
[0], buf
);
618 for(i
= 1; i
< 11; i
++)
620 total
+= (counts
[i
] * i
);
623 /* dont want to divide by 0! --fl */
624 if(counts
[0] != length
)
626 snprintf(buf
, sizeof buf
, "%.3f/%.3f",
627 (float) (total
/ (length
- counts
[0])),
628 (float) (total
/ length
));
629 sendto_one_numeric(source_p
, RPL_STATSDEBUG
,
630 "B :Average depth: %s Highest depth: %lu",
634 for(i
= 0; i
< 11; i
++)
636 sendto_one_numeric(source_p
, RPL_STATSDEBUG
,
637 "B :Nodes with %d entries: %d",
644 count_hash(struct Client
*source_p
, rb_dlink_list
*table
, int length
, const char *name
)
647 unsigned long deepest
= 0;
650 memset(counts
, 0, sizeof(counts
));
652 for(i
= 0; i
< length
; i
++)
654 if(rb_dlink_list_length(&table
[i
]) >= 10)
657 counts
[rb_dlink_list_length(&table
[i
])]++;
659 if(rb_dlink_list_length(&table
[i
]) > deepest
)
660 deepest
= rb_dlink_list_length(&table
[i
]);
663 output_hash(source_p
, name
, length
, counts
, deepest
);
667 hash_stats(struct Client
*source_p
)
669 count_hash(source_p
, channelTable
, CH_MAX
, "Channel");
670 sendto_one_numeric(source_p
, RPL_STATSDEBUG
, "B :--");
671 count_hash(source_p
, hostTable
, HOST_MAX
, "Hostname");