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"
43 #define hash_cli_fd(x) (x % CLI_FD_MAX)
45 static rb_dlink_list clientbyfdTable
[U_MAX
];
47 rb_dlink_list
*clientTable
;
48 rb_dlink_list
*channelTable
;
49 rb_dlink_list
*idTable
;
50 rb_dlink_list
*resvTable
;
51 rb_dlink_list
*hostTable
;
54 * look in whowas.c for the missing ...[WW_MAX]; entry
60 * The server uses a chained hash table to provide quick and efficient
61 * hash table maintenance (providing the hash function works evenly over
62 * the input range). The hash table is thus not susceptible to problems
63 * of filling all the buckets or the need to rehash.
64 * It is expected that the hash table would look something like this
66 * +-----+ +-----+ +-----+ +-----+
67 * ---| 224 |----| 225 |----| 226 |---| 227 |---
68 * +-----+ +-----+ +-----+ +-----+
70 * +-----+ +-----+ +-----+
72 * +-----+ +-----+ +-----+
78 * A - GOPbot, B - chang, C - hanuaway, D - *.mu.OZ.AU
80 * The order shown above is just one instant of the server.
83 * The hash functions currently used are based Fowler/Noll/Vo hashes
84 * which work amazingly well and have a extremely low collision rate
85 * For more info see http://www.isthe.com/chongo/tech/comp/fnv/index.html
92 * clears the various hashtables
97 clientTable
= rb_malloc(sizeof(rb_dlink_list
) * U_MAX
);
98 idTable
= rb_malloc(sizeof(rb_dlink_list
) * U_MAX
);
99 channelTable
= rb_malloc(sizeof(rb_dlink_list
) * CH_MAX
);
100 hostTable
= rb_malloc(sizeof(rb_dlink_list
) * HOST_MAX
);
101 resvTable
= rb_malloc(sizeof(rb_dlink_list
) * R_MAX
);
104 #ifndef RICER_HASHING
106 fnv_hash_upper(const unsigned char *s
, int bits
)
108 u_int32_t h
= FNV1_32_INIT
;
113 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
116 h
= ((h
>> bits
) ^ h
) & ((1<<bits
)-1);
121 fnv_hash(const unsigned char *s
, int bits
)
123 u_int32_t h
= FNV1_32_INIT
;
128 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
131 h
= ((h
>> bits
) ^ h
) & ((1<<bits
)-1);
136 fnv_hash_len(const unsigned char *s
, int bits
, int len
)
138 u_int32_t h
= FNV1_32_INIT
;
139 const unsigned char *x
= s
+ len
;
143 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
146 h
= ((h
>> bits
) ^ h
) & ((1<<bits
)-1);
151 fnv_hash_upper_len(const unsigned char *s
, int bits
, int len
)
153 u_int32_t h
= FNV1_32_INIT
;
154 const unsigned char *x
= s
+ len
;
158 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
161 h
= ((h
>> bits
) ^ h
) & ((1<<bits
)-1);
168 * hashes a nickname, first converting to lowercase
171 hash_nick(const char *name
)
173 return fnv_hash_upper((const unsigned char *) name
, U_MAX_BITS
);
178 * hashes an id, case is kept
181 hash_id(const char *name
)
183 return fnv_hash((const unsigned char *) name
, U_MAX_BITS
);
188 * hashes a channel name, based on first 30 chars only for efficiency
191 hash_channel(const char *name
)
193 return fnv_hash_upper_len((const unsigned char *) name
, CH_MAX_BITS
, 30);
198 * hashes a hostname, based on first 30 chars only, as thats likely to
199 * be more dynamic than rest.
202 hash_hostname(const char *name
)
204 return fnv_hash_upper_len((const unsigned char *) name
, HOST_MAX_BITS
, 30);
209 * hashes a resv channel name, based on first 30 chars only
212 hash_resv(const char *name
)
214 return fnv_hash_upper_len((const unsigned char *) name
, R_MAX_BITS
, 30);
219 * adds an entry to the id hash table
222 add_to_id_hash(const char *name
, struct Client
*client_p
)
226 if(EmptyString(name
) || (client_p
== NULL
))
229 hashv
= hash_id(name
);
230 rb_dlinkAddAlloc(client_p
, &idTable
[hashv
]);
233 /* add_to_client_hash()
235 * adds an entry (client/server) to the client hash table
238 add_to_client_hash(const char *name
, struct Client
*client_p
)
242 s_assert(name
!= NULL
);
243 s_assert(client_p
!= NULL
);
244 if(EmptyString(name
) || (client_p
== NULL
))
247 hashv
= hash_nick(name
);
248 rb_dlinkAddAlloc(client_p
, &clientTable
[hashv
]);
251 /* add_to_hostname_hash()
253 * adds a client entry to the hostname hash table
256 add_to_hostname_hash(const char *hostname
, struct Client
*client_p
)
260 s_assert(hostname
!= NULL
);
261 s_assert(client_p
!= NULL
);
262 if(EmptyString(hostname
) || (client_p
== NULL
))
265 hashv
= hash_hostname(hostname
);
266 rb_dlinkAddAlloc(client_p
, &hostTable
[hashv
]);
269 /* add_to_resv_hash()
271 * adds a resv channel entry to the resv hash table
274 add_to_resv_hash(const char *name
, struct ConfItem
*aconf
)
278 s_assert(!EmptyString(name
));
279 s_assert(aconf
!= NULL
);
280 if(EmptyString(name
) || aconf
== NULL
)
283 hashv
= hash_resv(name
);
284 rb_dlinkAddAlloc(aconf
, &resvTable
[hashv
]);
287 /* del_from_id_hash()
289 * removes an id from the id hash table
292 del_from_id_hash(const char *id
, struct Client
*client_p
)
296 s_assert(id
!= NULL
);
297 s_assert(client_p
!= NULL
);
298 if(EmptyString(id
) || client_p
== NULL
)
302 rb_dlinkFindDestroy(client_p
, &idTable
[hashv
]);
305 /* del_from_client_hash()
307 * removes a client/server from the client hash table
310 del_from_client_hash(const char *name
, struct Client
*client_p
)
314 /* no s_asserts, this can happen when removing a client that
317 if(EmptyString(name
) || client_p
== NULL
)
320 hashv
= hash_nick(name
);
321 rb_dlinkFindDestroy(client_p
, &clientTable
[hashv
]);
324 /* del_from_channel_hash()
326 * removes a channel from the channel hash table
329 del_from_channel_hash(const char *name
, struct Channel
*chptr
)
333 s_assert(name
!= NULL
);
334 s_assert(chptr
!= NULL
);
336 if(EmptyString(name
) || chptr
== NULL
)
339 hashv
= hash_channel(name
);
340 rb_dlinkFindDestroy(chptr
, &channelTable
[hashv
]);
343 /* del_from_hostname_hash()
345 * removes a client entry from the hostname hash table
348 del_from_hostname_hash(const char *hostname
, struct Client
*client_p
)
352 if(hostname
== NULL
|| client_p
== NULL
)
355 hashv
= hash_hostname(hostname
);
357 rb_dlinkFindDestroy(client_p
, &hostTable
[hashv
]);
360 /* del_from_resv_hash()
362 * removes a resv entry from the resv hash table
365 del_from_resv_hash(const char *name
, struct ConfItem
*aconf
)
369 s_assert(name
!= NULL
);
370 s_assert(aconf
!= NULL
);
371 if(EmptyString(name
) || aconf
== NULL
)
374 hashv
= hash_resv(name
);
376 rb_dlinkFindDestroy(aconf
, &resvTable
[hashv
]);
381 * finds a client entry from the id hash table
384 find_id(const char *name
)
386 struct Client
*target_p
;
390 if(EmptyString(name
))
393 hashv
= hash_id(name
);
395 RB_DLINK_FOREACH(ptr
, idTable
[hashv
].head
)
397 target_p
= ptr
->data
;
399 if(strcmp(name
, target_p
->id
) == 0)
408 * finds a client/server entry from the client hash table
411 find_client(const char *name
)
413 struct Client
*target_p
;
417 s_assert(name
!= NULL
);
418 if(EmptyString(name
))
421 /* hunting for an id, not a nick */
423 return (find_id(name
));
425 hashv
= hash_nick(name
);
427 RB_DLINK_FOREACH(ptr
, clientTable
[hashv
].head
)
429 target_p
= ptr
->data
;
431 if(irccmp(name
, target_p
->name
) == 0)
438 /* find_named_client()
440 * finds a client/server entry from the client hash table
443 find_named_client(const char *name
)
445 struct Client
*target_p
;
449 s_assert(name
!= NULL
);
450 if(EmptyString(name
))
453 hashv
= hash_nick(name
);
455 RB_DLINK_FOREACH(ptr
, clientTable
[hashv
].head
)
457 target_p
= ptr
->data
;
459 if(irccmp(name
, target_p
->name
) == 0)
468 * finds a server from the client hash table
471 find_server(struct Client
*source_p
, const char *name
)
473 struct Client
*target_p
;
477 if(EmptyString(name
))
480 if((source_p
== NULL
|| !MyClient(source_p
)) &&
481 IsDigit(*name
) && strlen(name
) == 3)
483 target_p
= find_id(name
);
487 hashv
= hash_nick(name
);
489 RB_DLINK_FOREACH(ptr
, clientTable
[hashv
].head
)
491 target_p
= ptr
->data
;
493 if((IsServer(target_p
) || IsMe(target_p
)) &&
494 irccmp(name
, target_p
->name
) == 0)
503 * finds a hostname rb_dlink list from the hostname hash table.
504 * we return the full rb_dlink list, because you can have multiple
505 * entries with the same hostname
508 find_hostname(const char *hostname
)
512 if(EmptyString(hostname
))
515 hashv
= hash_hostname(hostname
);
517 return hostTable
[hashv
].head
;
522 * finds a channel from the channel hash table
525 find_channel(const char *name
)
527 struct Channel
*chptr
;
531 s_assert(name
!= NULL
);
532 if(EmptyString(name
))
535 hashv
= hash_channel(name
);
537 RB_DLINK_FOREACH(ptr
, channelTable
[hashv
].head
)
541 if(irccmp(name
, chptr
->chname
) == 0)
549 * get_or_create_channel
550 * inputs - client pointer
552 * - pointer to int flag whether channel was newly created or not
553 * output - returns channel block or NULL if illegal name
554 * - also modifies *isnew
556 * Get Channel block for chname (and allocate a new channel
557 * block, if it didn't exist before).
560 get_or_create_channel(struct Client
*client_p
, const char *chname
, int *isnew
)
562 struct Channel
*chptr
;
566 const char *s
= chname
;
575 if(IsServer(client_p
))
577 sendto_realops_snomask(SNO_DEBUG
, L_ALL
,
578 "*** Long channel name from %s (%d > %d): %s",
579 client_p
->name
, len
, CHANNELLEN
, s
);
583 *(t
+ CHANNELLEN
) = '\0';
587 hashv
= hash_channel(s
);
589 RB_DLINK_FOREACH(ptr
, channelTable
[hashv
].head
)
593 if(irccmp(s
, chptr
->chname
) == 0)
604 chptr
= allocate_channel(s
);
606 rb_dlinkAdd(chptr
, &chptr
->node
, &global_channel_list
);
608 chptr
->channelts
= rb_current_time(); /* doesn't hurt to set it here */
610 rb_dlinkAddAlloc(chptr
, &channelTable
[hashv
]);
617 * hunts for a resv entry in the resv hash table
620 hash_find_resv(const char *name
)
622 struct ConfItem
*aconf
;
626 s_assert(name
!= NULL
);
627 if(EmptyString(name
))
630 hashv
= hash_resv(name
);
632 RB_DLINK_FOREACH(ptr
, resvTable
[hashv
].head
)
636 if(!irccmp(name
, aconf
->host
))
647 clear_resv_hash(void)
649 struct ConfItem
*aconf
;
651 rb_dlink_node
*next_ptr
;
654 HASH_WALK_SAFE(i
, R_MAX
, ptr
, next_ptr
, resvTable
)
658 /* skip temp resvs */
662 free_conf(ptr
->data
);
663 rb_dlinkDestroy(ptr
, &resvTable
[i
]);
669 add_to_cli_fd_hash(struct Client
*client_p
)
671 rb_dlinkAddAlloc(client_p
, &clientbyfdTable
[hash_cli_fd(rb_get_fd(client_p
->localClient
->F
))]);
676 del_from_cli_fd_hash(struct Client
*client_p
)
679 hashv
= hash_cli_fd(rb_get_fd(client_p
->localClient
->F
));
680 rb_dlinkFindDestroy(client_p
, &clientbyfdTable
[hashv
]);
684 find_cli_fd_hash(int fd
)
686 struct Client
*target_p
;
689 hashv
= hash_cli_fd(fd
);
690 RB_DLINK_FOREACH(ptr
, clientbyfdTable
[hashv
].head
)
692 target_p
= ptr
->data
;
693 if(rb_get_fd(target_p
->localClient
->F
) == fd
)
700 output_hash(struct Client
*source_p
, const char *name
, int length
, int *counts
, unsigned long deepest
)
702 unsigned long total
= 0;
706 sendto_one_numeric(source_p
, RPL_STATSDEBUG
,
707 "B :%s Hash Statistics", name
);
709 snprintf(buf
, sizeof buf
, "%.3f%%",
710 (float) ((counts
[0]*100) / (float) length
));
711 sendto_one_numeric(source_p
, RPL_STATSDEBUG
,
712 "B :Size: %d Empty: %d (%s)",
713 length
, counts
[0], buf
);
715 for(i
= 1; i
< 11; i
++)
717 total
+= (counts
[i
] * i
);
720 /* dont want to divide by 0! --fl */
721 if(counts
[0] != length
)
723 snprintf(buf
, sizeof buf
, "%.3f/%.3f",
724 (float) (total
/ (length
- counts
[0])),
725 (float) (total
/ length
));
726 sendto_one_numeric(source_p
, RPL_STATSDEBUG
,
727 "B :Average depth: %s Highest depth: %lu",
731 for(i
= 0; i
< 11; i
++)
733 sendto_one_numeric(source_p
, RPL_STATSDEBUG
,
734 "B :Nodes with %d entries: %d",
741 count_hash(struct Client
*source_p
, rb_dlink_list
*table
, int length
, const char *name
)
744 unsigned long deepest
= 0;
747 memset(counts
, 0, sizeof(counts
));
749 for(i
= 0; i
< length
; i
++)
751 if(rb_dlink_list_length(&table
[i
]) >= 10)
754 counts
[rb_dlink_list_length(&table
[i
])]++;
756 if(rb_dlink_list_length(&table
[i
]) > deepest
)
757 deepest
= rb_dlink_list_length(&table
[i
]);
760 output_hash(source_p
, name
, length
, counts
, deepest
);
764 hash_stats(struct Client
*source_p
)
766 count_hash(source_p
, channelTable
, CH_MAX
, "Channel");
767 sendto_one_numeric(source_p
, RPL_STATSDEBUG
, "B :--");
768 count_hash(source_p
, clientTable
, U_MAX
, "Client");
769 sendto_one_numeric(source_p
, RPL_STATSDEBUG
, "B :--");
770 count_hash(source_p
, idTable
, U_MAX
, "ID");
771 sendto_one_numeric(source_p
, RPL_STATSDEBUG
, "B :--");
772 count_hash(source_p
, hostTable
, HOST_MAX
, "Hostname");