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 ZCONNID_MAX 64 /* i doubt we'll have this many ziplinks ;) */
45 #define hash_cli_connid(x) (x % CLI_CONNID_MAX)
46 #define hash_zconnid(x) (x % ZCONNID_MAX)
48 static rb_dlink_list clientbyconnidTable
[CLI_CONNID_MAX
];
49 static rb_dlink_list clientbyzconnidTable
[ZCONNID_MAX
];
51 rb_dlink_list
*clientTable
;
52 rb_dlink_list
*channelTable
;
53 rb_dlink_list
*idTable
;
54 rb_dlink_list
*resvTable
;
55 rb_dlink_list
*hostTable
;
58 * look in whowas.c for the missing ...[WW_MAX]; entry
64 * The server uses a chained hash table to provide quick and efficient
65 * hash table maintenance (providing the hash function works evenly over
66 * the input range). The hash table is thus not susceptible to problems
67 * of filling all the buckets or the need to rehash.
68 * It is expected that the hash table would look something like this
70 * +-----+ +-----+ +-----+ +-----+
71 * ---| 224 |----| 225 |----| 226 |---| 227 |---
72 * +-----+ +-----+ +-----+ +-----+
74 * +-----+ +-----+ +-----+
76 * +-----+ +-----+ +-----+
82 * A - GOPbot, B - chang, C - hanuaway, D - *.mu.OZ.AU
84 * The order shown above is just one instant of the server.
87 * The hash functions currently used are based Fowler/Noll/Vo hashes
88 * which work amazingly well and have a extremely low collision rate
89 * For more info see http://www.isthe.com/chongo/tech/comp/fnv/index.html
96 * clears the various hashtables
101 clientTable
= rb_malloc(sizeof(rb_dlink_list
) * U_MAX
);
102 idTable
= rb_malloc(sizeof(rb_dlink_list
) * U_MAX
);
103 channelTable
= rb_malloc(sizeof(rb_dlink_list
) * CH_MAX
);
104 hostTable
= rb_malloc(sizeof(rb_dlink_list
) * HOST_MAX
);
105 resvTable
= rb_malloc(sizeof(rb_dlink_list
) * R_MAX
);
108 #ifndef RICER_HASHING
110 fnv_hash_upper(const unsigned char *s
, int bits
)
112 u_int32_t h
= FNV1_32_INIT
;
117 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
120 h
= ((h
>> bits
) ^ h
) & ((1<<bits
)-1);
125 fnv_hash(const unsigned char *s
, int bits
)
127 u_int32_t h
= FNV1_32_INIT
;
132 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
135 h
= ((h
>> bits
) ^ h
) & ((1<<bits
)-1);
140 fnv_hash_len(const unsigned char *s
, int bits
, int len
)
142 u_int32_t h
= FNV1_32_INIT
;
143 const unsigned char *x
= s
+ len
;
147 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
150 h
= ((h
>> bits
) ^ h
) & ((1<<bits
)-1);
155 fnv_hash_upper_len(const unsigned char *s
, int bits
, int len
)
157 u_int32_t h
= FNV1_32_INIT
;
158 const unsigned char *x
= s
+ len
;
162 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
165 h
= ((h
>> bits
) ^ h
) & ((1<<bits
)-1);
172 * hashes a nickname, first converting to lowercase
175 hash_nick(const char *name
)
177 return fnv_hash_upper((const unsigned char *) name
, U_MAX_BITS
);
182 * hashes an id, case is kept
185 hash_id(const char *name
)
187 return fnv_hash((const unsigned char *) name
, U_MAX_BITS
);
192 * hashes a channel name, based on first 30 chars only for efficiency
195 hash_channel(const char *name
)
197 return fnv_hash_upper_len((const unsigned char *) name
, CH_MAX_BITS
, 30);
202 * hashes a hostname, based on first 30 chars only, as thats likely to
203 * be more dynamic than rest.
206 hash_hostname(const char *name
)
208 return fnv_hash_upper_len((const unsigned char *) name
, HOST_MAX_BITS
, 30);
213 * hashes a resv channel name, based on first 30 chars only
216 hash_resv(const char *name
)
218 return fnv_hash_upper_len((const unsigned char *) name
, R_MAX_BITS
, 30);
223 * adds an entry to the id hash table
226 add_to_id_hash(const char *name
, struct Client
*client_p
)
230 if(EmptyString(name
) || (client_p
== NULL
))
233 hashv
= hash_id(name
);
234 rb_dlinkAddAlloc(client_p
, &idTable
[hashv
]);
237 /* add_to_client_hash()
239 * adds an entry (client/server) to the client hash table
242 add_to_client_hash(const char *name
, struct Client
*client_p
)
246 s_assert(name
!= NULL
);
247 s_assert(client_p
!= NULL
);
248 if(EmptyString(name
) || (client_p
== NULL
))
251 hashv
= hash_nick(name
);
252 rb_dlinkAddAlloc(client_p
, &clientTable
[hashv
]);
255 /* add_to_hostname_hash()
257 * adds a client entry to the hostname hash table
260 add_to_hostname_hash(const char *hostname
, struct Client
*client_p
)
264 s_assert(hostname
!= NULL
);
265 s_assert(client_p
!= NULL
);
266 if(EmptyString(hostname
) || (client_p
== NULL
))
269 hashv
= hash_hostname(hostname
);
270 rb_dlinkAddAlloc(client_p
, &hostTable
[hashv
]);
273 /* add_to_resv_hash()
275 * adds a resv channel entry to the resv hash table
278 add_to_resv_hash(const char *name
, struct ConfItem
*aconf
)
282 s_assert(!EmptyString(name
));
283 s_assert(aconf
!= NULL
);
284 if(EmptyString(name
) || aconf
== NULL
)
287 hashv
= hash_resv(name
);
288 rb_dlinkAddAlloc(aconf
, &resvTable
[hashv
]);
291 /* del_from_id_hash()
293 * removes an id from the id hash table
296 del_from_id_hash(const char *id
, struct Client
*client_p
)
300 s_assert(id
!= NULL
);
301 s_assert(client_p
!= NULL
);
302 if(EmptyString(id
) || client_p
== NULL
)
306 rb_dlinkFindDestroy(client_p
, &idTable
[hashv
]);
309 /* del_from_client_hash()
311 * removes a client/server from the client hash table
314 del_from_client_hash(const char *name
, struct Client
*client_p
)
318 /* no s_asserts, this can happen when removing a client that
321 if(EmptyString(name
) || client_p
== NULL
)
324 hashv
= hash_nick(name
);
325 rb_dlinkFindDestroy(client_p
, &clientTable
[hashv
]);
328 /* del_from_channel_hash()
330 * removes a channel from the channel hash table
333 del_from_channel_hash(const char *name
, struct Channel
*chptr
)
337 s_assert(name
!= NULL
);
338 s_assert(chptr
!= NULL
);
340 if(EmptyString(name
) || chptr
== NULL
)
343 hashv
= hash_channel(name
);
344 rb_dlinkFindDestroy(chptr
, &channelTable
[hashv
]);
347 /* del_from_hostname_hash()
349 * removes a client entry from the hostname hash table
352 del_from_hostname_hash(const char *hostname
, struct Client
*client_p
)
356 if(hostname
== NULL
|| client_p
== NULL
)
359 hashv
= hash_hostname(hostname
);
361 rb_dlinkFindDestroy(client_p
, &hostTable
[hashv
]);
364 /* del_from_resv_hash()
366 * removes a resv entry from the resv hash table
369 del_from_resv_hash(const char *name
, struct ConfItem
*aconf
)
373 s_assert(name
!= NULL
);
374 s_assert(aconf
!= NULL
);
375 if(EmptyString(name
) || aconf
== NULL
)
378 hashv
= hash_resv(name
);
380 rb_dlinkFindDestroy(aconf
, &resvTable
[hashv
]);
385 * finds a client entry from the id hash table
388 find_id(const char *name
)
390 struct Client
*target_p
;
394 if(EmptyString(name
))
397 hashv
= hash_id(name
);
399 RB_DLINK_FOREACH(ptr
, idTable
[hashv
].head
)
401 target_p
= ptr
->data
;
403 if(strcmp(name
, target_p
->id
) == 0)
412 * finds a client/server entry from the client hash table
415 find_client(const char *name
)
417 struct Client
*target_p
;
421 s_assert(name
!= NULL
);
422 if(EmptyString(name
))
425 /* hunting for an id, not a nick */
427 return (find_id(name
));
429 hashv
= hash_nick(name
);
431 RB_DLINK_FOREACH(ptr
, clientTable
[hashv
].head
)
433 target_p
= ptr
->data
;
435 if(irccmp(name
, target_p
->name
) == 0)
442 /* find_named_client()
444 * finds a client/server entry from the client hash table
447 find_named_client(const char *name
)
449 struct Client
*target_p
;
453 s_assert(name
!= NULL
);
454 if(EmptyString(name
))
457 hashv
= hash_nick(name
);
459 RB_DLINK_FOREACH(ptr
, clientTable
[hashv
].head
)
461 target_p
= ptr
->data
;
463 if(irccmp(name
, target_p
->name
) == 0)
472 * finds a server from the client hash table
475 find_server(struct Client
*source_p
, const char *name
)
477 struct Client
*target_p
;
481 if(EmptyString(name
))
484 if((source_p
== NULL
|| !MyClient(source_p
)) &&
485 IsDigit(*name
) && strlen(name
) == 3)
487 target_p
= find_id(name
);
491 hashv
= hash_nick(name
);
493 RB_DLINK_FOREACH(ptr
, clientTable
[hashv
].head
)
495 target_p
= ptr
->data
;
497 if((IsServer(target_p
) || IsMe(target_p
)) &&
498 irccmp(name
, target_p
->name
) == 0)
507 * finds a hostname rb_dlink list from the hostname hash table.
508 * we return the full rb_dlink list, because you can have multiple
509 * entries with the same hostname
512 find_hostname(const char *hostname
)
516 if(EmptyString(hostname
))
519 hashv
= hash_hostname(hostname
);
521 return hostTable
[hashv
].head
;
526 * finds a channel from the channel hash table
529 find_channel(const char *name
)
531 struct Channel
*chptr
;
535 s_assert(name
!= NULL
);
536 if(EmptyString(name
))
539 hashv
= hash_channel(name
);
541 RB_DLINK_FOREACH(ptr
, channelTable
[hashv
].head
)
545 if(irccmp(name
, chptr
->chname
) == 0)
553 * get_or_create_channel
554 * inputs - client pointer
556 * - pointer to int flag whether channel was newly created or not
557 * output - returns channel block or NULL if illegal name
558 * - also modifies *isnew
560 * Get Channel block for chname (and allocate a new channel
561 * block, if it didn't exist before).
564 get_or_create_channel(struct Client
*client_p
, const char *chname
, int *isnew
)
566 struct Channel
*chptr
;
570 const char *s
= chname
;
579 if(IsServer(client_p
))
581 sendto_realops_snomask(SNO_DEBUG
, L_ALL
,
582 "*** Long channel name from %s (%d > %d): %s",
583 client_p
->name
, len
, CHANNELLEN
, s
);
587 *(t
+ CHANNELLEN
) = '\0';
591 hashv
= hash_channel(s
);
593 RB_DLINK_FOREACH(ptr
, channelTable
[hashv
].head
)
597 if(irccmp(s
, chptr
->chname
) == 0)
608 chptr
= allocate_channel(s
);
610 rb_dlinkAdd(chptr
, &chptr
->node
, &global_channel_list
);
612 chptr
->channelts
= rb_current_time(); /* doesn't hurt to set it here */
614 rb_dlinkAddAlloc(chptr
, &channelTable
[hashv
]);
621 * hunts for a resv entry in the resv hash table
624 hash_find_resv(const char *name
)
626 struct ConfItem
*aconf
;
630 s_assert(name
!= NULL
);
631 if(EmptyString(name
))
634 hashv
= hash_resv(name
);
636 RB_DLINK_FOREACH(ptr
, resvTable
[hashv
].head
)
640 if(!irccmp(name
, aconf
->host
))
651 clear_resv_hash(void)
653 struct ConfItem
*aconf
;
655 rb_dlink_node
*next_ptr
;
658 HASH_WALK_SAFE(i
, R_MAX
, ptr
, next_ptr
, resvTable
)
662 /* skip temp resvs */
666 free_conf(ptr
->data
);
667 rb_dlinkDestroy(ptr
, &resvTable
[i
]);
673 add_to_zconnid_hash(struct Client
*client_p
)
676 hashv
= hash_zconnid(client_p
->localClient
->zconnid
);
677 rb_dlinkAddAlloc(client_p
, &clientbyzconnidTable
[hashv
]);
681 del_from_zconnid_hash(struct Client
*client_p
)
684 hashv
= hash_zconnid(client_p
->localClient
->zconnid
);
685 rb_dlinkFindDestroy(client_p
, &clientbyzconnidTable
[hashv
]);
689 add_to_cli_connid_hash(struct Client
*client_p
)
692 hashv
= hash_cli_connid(client_p
->localClient
->connid
);
693 rb_dlinkAddAlloc(client_p
, &clientbyconnidTable
[hashv
]);
697 del_from_cli_connid_hash(struct Client
*client_p
)
700 hashv
= hash_cli_connid(client_p
->localClient
->connid
);
701 rb_dlinkFindDestroy(client_p
, &clientbyconnidTable
[hashv
]);
705 find_cli_connid_hash(int connid
)
707 struct Client
*target_p
;
710 hashv
= hash_cli_connid(connid
);
711 RB_DLINK_FOREACH(ptr
, clientbyconnidTable
[hashv
].head
)
713 target_p
= ptr
->data
;
714 if(target_p
->localClient
->connid
== connid
)
718 hashv
= hash_zconnid(connid
);
719 RB_DLINK_FOREACH(ptr
, clientbyzconnidTable
[hashv
].head
)
721 target_p
= ptr
->data
;
722 if(target_p
->localClient
->zconnid
== connid
)
730 output_hash(struct Client
*source_p
, const char *name
, int length
, int *counts
, unsigned long deepest
)
732 unsigned long total
= 0;
736 sendto_one_numeric(source_p
, RPL_STATSDEBUG
,
737 "B :%s Hash Statistics", name
);
739 snprintf(buf
, sizeof buf
, "%.3f%%",
740 (float) ((counts
[0]*100) / (float) length
));
741 sendto_one_numeric(source_p
, RPL_STATSDEBUG
,
742 "B :Size: %d Empty: %d (%s)",
743 length
, counts
[0], buf
);
745 for(i
= 1; i
< 11; i
++)
747 total
+= (counts
[i
] * i
);
750 /* dont want to divide by 0! --fl */
751 if(counts
[0] != length
)
753 snprintf(buf
, sizeof buf
, "%.3f/%.3f",
754 (float) (total
/ (length
- counts
[0])),
755 (float) (total
/ length
));
756 sendto_one_numeric(source_p
, RPL_STATSDEBUG
,
757 "B :Average depth: %s Highest depth: %lu",
761 for(i
= 0; i
< 11; i
++)
763 sendto_one_numeric(source_p
, RPL_STATSDEBUG
,
764 "B :Nodes with %d entries: %d",
771 count_hash(struct Client
*source_p
, rb_dlink_list
*table
, int length
, const char *name
)
774 unsigned long deepest
= 0;
777 memset(counts
, 0, sizeof(counts
));
779 for(i
= 0; i
< length
; i
++)
781 if(rb_dlink_list_length(&table
[i
]) >= 10)
784 counts
[rb_dlink_list_length(&table
[i
])]++;
786 if(rb_dlink_list_length(&table
[i
]) > deepest
)
787 deepest
= rb_dlink_list_length(&table
[i
]);
790 output_hash(source_p
, name
, length
, counts
, deepest
);
794 hash_stats(struct Client
*source_p
)
796 count_hash(source_p
, channelTable
, CH_MAX
, "Channel");
797 sendto_one_numeric(source_p
, RPL_STATSDEBUG
, "B :--");
798 count_hash(source_p
, clientTable
, U_MAX
, "Client");
799 sendto_one_numeric(source_p
, RPL_STATSDEBUG
, "B :--");
800 count_hash(source_p
, idTable
, U_MAX
, "ID");
801 sendto_one_numeric(source_p
, RPL_STATSDEBUG
, "B :--");
802 count_hash(source_p
, hostTable
, HOST_MAX
, "Hostname");
803 sendto_one_numeric(source_p
, RPL_STATSDEBUG
, "B :--");
804 count_hash(source_p
, clientbyconnidTable
, CLI_CONNID_MAX
, "Client by connection id");