]>
jfr.im git - solanum.git/blob - src/hash.c
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"
35 #include "irc_string.h"
42 #include "s_newconf.h"
44 dlink_list
*clientTable
;
45 dlink_list
*channelTable
;
47 dlink_list
*resvTable
;
48 dlink_list
*hostTable
;
49 dlink_list
*helpTable
;
53 * look in whowas.c for the missing ...[WW_MAX]; entry
59 * The server uses a chained hash table to provide quick and efficient
60 * hash table maintenance (providing the hash function works evenly over
61 * the input range). The hash table is thus not susceptible to problems
62 * of filling all the buckets or the need to rehash.
63 * It is expected that the hash table would look something like this
65 * +-----+ +-----+ +-----+ +-----+
66 * ---| 224 |----| 225 |----| 226 |---| 227 |---
67 * +-----+ +-----+ +-----+ +-----+
69 * +-----+ +-----+ +-----+
71 * +-----+ +-----+ +-----+
77 * A - GOPbot, B - chang, C - hanuaway, D - *.mu.OZ.AU
79 * The order shown above is just one instant of the server.
82 * The hash functions currently used are based Fowler/Noll/Vo hashes
83 * which work amazingly well and have a extremely low collision rate
84 * For more info see http://www.isthe.com/chongo/tech/comp/fnv/index.html
91 * clears the various hashtables
96 clientTable
= MyMalloc(sizeof(dlink_list
) * U_MAX
);
97 idTable
= MyMalloc(sizeof(dlink_list
) * U_MAX
);
98 ndTable
= MyMalloc(sizeof(dlink_list
) * U_MAX
);
99 channelTable
= MyMalloc(sizeof(dlink_list
) * CH_MAX
);
100 hostTable
= MyMalloc(sizeof(dlink_list
) * HOST_MAX
);
101 resvTable
= MyMalloc(sizeof(dlink_list
) * R_MAX
);
102 helpTable
= MyMalloc(sizeof(dlink_list
) * HELP_MAX
);
105 #ifndef RICER_HASHING
107 fnv_hash_upper(const unsigned char *s
, int bits
)
109 u_int32_t h
= FNV1_32_INIT
;
114 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
116 h
= (h
>> bits
) ^ (h
& ((2^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);
130 h
= (h
>> bits
) ^ (h
& ((2^bits
)-1));
135 fnv_hash_len(const unsigned char *s
, int bits
, int len
)
137 u_int32_t h
= FNV1_32_INIT
;
138 const unsigned char *x
= s
+ len
;
142 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
144 h
= (h
>> bits
) ^ (h
& ((2^bits
)-1));
149 fnv_hash_upper_len(const unsigned char *s
, int bits
, int len
)
151 u_int32_t h
= FNV1_32_INIT
;
152 const unsigned char *x
= s
+ len
;
156 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
158 h
= (h
>> bits
) ^ (h
& ((2^bits
)-1));
165 * hashes a nickname, first converting to lowercase
168 hash_nick(const char *name
)
170 return fnv_hash_upper((const unsigned char *) name
, U_MAX_BITS
);
175 * hashes an id, case is kept
178 hash_id(const char *name
)
180 return fnv_hash((const unsigned char *) name
, U_MAX_BITS
);
185 * hashes a channel name, based on first 30 chars only for efficiency
188 hash_channel(const char *name
)
190 return fnv_hash_upper_len((const unsigned char *) name
, CH_MAX_BITS
, 30);
195 * hashes a hostname, based on first 30 chars only, as thats likely to
196 * be more dynamic than rest.
199 hash_hostname(const char *name
)
201 return fnv_hash_upper_len((const unsigned char *) name
, HOST_MAX_BITS
, 30);
206 * hashes a resv channel name, based on first 30 chars only
209 hash_resv(const char *name
)
211 return fnv_hash_upper_len((const unsigned char *) name
, R_MAX_BITS
, 30);
215 hash_help(const char *name
)
221 h
+= (unsigned int) (ToLower(*name
++) & 0xDF);
224 return (h
% HELP_MAX
);
229 * adds an entry to the id hash table
232 add_to_id_hash(const char *name
, struct Client
*client_p
)
236 if(EmptyString(name
) || (client_p
== NULL
))
239 hashv
= hash_id(name
);
240 dlinkAddAlloc(client_p
, &idTable
[hashv
]);
243 /* add_to_client_hash()
245 * adds an entry (client/server) to the client hash table
248 add_to_client_hash(const char *name
, struct Client
*client_p
)
252 s_assert(name
!= NULL
);
253 s_assert(client_p
!= NULL
);
254 if(EmptyString(name
) || (client_p
== NULL
))
257 hashv
= hash_nick(name
);
258 dlinkAddAlloc(client_p
, &clientTable
[hashv
]);
261 /* add_to_hostname_hash()
263 * adds a client entry to the hostname hash table
266 add_to_hostname_hash(const char *hostname
, struct Client
*client_p
)
270 s_assert(hostname
!= NULL
);
271 s_assert(client_p
!= NULL
);
272 if(EmptyString(hostname
) || (client_p
== NULL
))
275 hashv
= hash_hostname(hostname
);
276 dlinkAddAlloc(client_p
, &hostTable
[hashv
]);
279 /* add_to_resv_hash()
281 * adds a resv channel entry to the resv hash table
284 add_to_resv_hash(const char *name
, struct ConfItem
*aconf
)
288 s_assert(!EmptyString(name
));
289 s_assert(aconf
!= NULL
);
290 if(EmptyString(name
) || aconf
== NULL
)
293 hashv
= hash_resv(name
);
294 dlinkAddAlloc(aconf
, &resvTable
[hashv
]);
298 add_to_help_hash(const char *name
, struct cachefile
*hptr
)
302 if(EmptyString(name
) || hptr
== NULL
)
305 hashv
= hash_help(name
);
306 dlinkAddAlloc(hptr
, &helpTable
[hashv
]);
310 add_to_nd_hash(const char *name
, struct nd_entry
*nd
)
312 nd
->hashv
= hash_nick(name
);
313 dlinkAdd(nd
, &nd
->hnode
, &ndTable
[nd
->hashv
]);
316 /* del_from_id_hash()
318 * removes an id from the id hash table
321 del_from_id_hash(const char *id
, struct Client
*client_p
)
325 s_assert(id
!= NULL
);
326 s_assert(client_p
!= NULL
);
327 if(EmptyString(id
) || client_p
== NULL
)
331 dlinkFindDestroy(client_p
, &idTable
[hashv
]);
334 /* del_from_client_hash()
336 * removes a client/server from the client hash table
339 del_from_client_hash(const char *name
, struct Client
*client_p
)
343 /* no s_asserts, this can happen when removing a client that
346 if(EmptyString(name
) || client_p
== NULL
)
349 hashv
= hash_nick(name
);
350 dlinkFindDestroy(client_p
, &clientTable
[hashv
]);
353 /* del_from_channel_hash()
355 * removes a channel from the channel hash table
358 del_from_channel_hash(const char *name
, struct Channel
*chptr
)
362 s_assert(name
!= NULL
);
363 s_assert(chptr
!= NULL
);
365 if(EmptyString(name
) || chptr
== NULL
)
368 hashv
= hash_channel(name
);
369 dlinkFindDestroy(chptr
, &channelTable
[hashv
]);
372 /* del_from_hostname_hash()
374 * removes a client entry from the hostname hash table
377 del_from_hostname_hash(const char *hostname
, struct Client
*client_p
)
381 if(hostname
== NULL
|| client_p
== NULL
)
384 hashv
= hash_hostname(hostname
);
386 dlinkFindDestroy(client_p
, &hostTable
[hashv
]);
389 /* del_from_resv_hash()
391 * removes a resv entry from the resv hash table
394 del_from_resv_hash(const char *name
, struct ConfItem
*aconf
)
398 s_assert(name
!= NULL
);
399 s_assert(aconf
!= NULL
);
400 if(EmptyString(name
) || aconf
== NULL
)
403 hashv
= hash_resv(name
);
405 dlinkFindDestroy(aconf
, &resvTable
[hashv
]);
409 clear_help_hash(void)
412 dlink_node
*next_ptr
;
415 HASH_WALK_SAFE(i
, HELP_MAX
, ptr
, next_ptr
, helpTable
)
417 free_cachefile(ptr
->data
);
418 dlinkDestroy(ptr
, &helpTable
[i
]);
425 * finds a client entry from the id hash table
428 find_id(const char *name
)
430 struct Client
*target_p
;
434 if(EmptyString(name
))
437 hashv
= hash_id(name
);
439 DLINK_FOREACH(ptr
, idTable
[hashv
].head
)
441 target_p
= ptr
->data
;
443 if(strcmp(name
, target_p
->id
) == 0)
452 * finds a client/server entry from the client hash table
455 find_client(const char *name
)
457 struct Client
*target_p
;
461 s_assert(name
!= NULL
);
462 if(EmptyString(name
))
465 /* hunting for an id, not a nick */
467 return (find_id(name
));
469 hashv
= hash_nick(name
);
471 DLINK_FOREACH(ptr
, clientTable
[hashv
].head
)
473 target_p
= ptr
->data
;
475 if(irccmp(name
, target_p
->name
) == 0)
482 /* find_named_client()
484 * finds a client/server entry from the client hash table
487 find_named_client(const char *name
)
489 struct Client
*target_p
;
493 s_assert(name
!= NULL
);
494 if(EmptyString(name
))
497 hashv
= hash_nick(name
);
499 DLINK_FOREACH(ptr
, clientTable
[hashv
].head
)
501 target_p
= ptr
->data
;
503 if(irccmp(name
, target_p
->name
) == 0)
512 * finds a server from the client hash table
515 find_server(struct Client
*source_p
, const char *name
)
517 struct Client
*target_p
;
521 if(EmptyString(name
))
524 if((source_p
== NULL
|| !MyClient(source_p
)) &&
525 IsDigit(*name
) && strlen(name
) == 3)
527 target_p
= find_id(name
);
531 hashv
= hash_nick(name
);
533 DLINK_FOREACH(ptr
, clientTable
[hashv
].head
)
535 target_p
= ptr
->data
;
537 if((IsServer(target_p
) || IsMe(target_p
)) &&
538 irccmp(name
, target_p
->name
) == 0)
547 * finds a hostname dlink list from the hostname hash table.
548 * we return the full dlink list, because you can have multiple
549 * entries with the same hostname
552 find_hostname(const char *hostname
)
556 if(EmptyString(hostname
))
559 hashv
= hash_hostname(hostname
);
561 return hostTable
[hashv
].head
;
566 * finds a channel from the channel hash table
569 find_channel(const char *name
)
571 struct Channel
*chptr
;
575 s_assert(name
!= NULL
);
576 if(EmptyString(name
))
579 hashv
= hash_channel(name
);
581 DLINK_FOREACH(ptr
, channelTable
[hashv
].head
)
585 if(irccmp(name
, chptr
->chname
) == 0)
593 * get_or_create_channel
594 * inputs - client pointer
596 * - pointer to int flag whether channel was newly created or not
597 * output - returns channel block or NULL if illegal name
598 * - also modifies *isnew
600 * Get Channel block for chname (and allocate a new channel
601 * block, if it didn't exist before).
604 get_or_create_channel(struct Client
*client_p
, const char *chname
, int *isnew
)
606 struct Channel
*chptr
;
610 const char *s
= chname
;
619 if(IsServer(client_p
))
621 sendto_realops_snomask(SNO_DEBUG
, L_ALL
,
622 "*** Long channel name from %s (%d > %d): %s",
623 client_p
->name
, len
, CHANNELLEN
, s
);
627 *(t
+ CHANNELLEN
) = '\0';
631 hashv
= hash_channel(s
);
633 DLINK_FOREACH(ptr
, channelTable
[hashv
].head
)
637 if(irccmp(s
, chptr
->chname
) == 0)
648 chptr
= allocate_channel(s
);
650 dlinkAdd(chptr
, &chptr
->node
, &global_channel_list
);
652 chptr
->channelts
= CurrentTime
; /* doesn't hurt to set it here */
654 dlinkAddAlloc(chptr
, &channelTable
[hashv
]);
661 * hunts for a resv entry in the resv hash table
664 hash_find_resv(const char *name
)
666 struct ConfItem
*aconf
;
670 s_assert(name
!= NULL
);
671 if(EmptyString(name
))
674 hashv
= hash_resv(name
);
676 DLINK_FOREACH(ptr
, resvTable
[hashv
].head
)
680 if(!irccmp(name
, aconf
->name
))
691 hash_find_help(const char *name
, int flags
)
693 struct cachefile
*hptr
;
697 if(EmptyString(name
))
700 hashv
= hash_help(name
);
702 DLINK_FOREACH(ptr
, helpTable
[hashv
].head
)
706 if((irccmp(name
, hptr
->name
) == 0) &&
707 (hptr
->flags
& flags
))
715 clear_resv_hash(void)
717 struct ConfItem
*aconf
;
719 dlink_node
*next_ptr
;
722 HASH_WALK_SAFE(i
, R_MAX
, ptr
, next_ptr
, resvTable
)
726 /* skip temp resvs */
730 free_conf(ptr
->data
);
731 dlinkDestroy(ptr
, &resvTable
[i
]);
737 hash_find_nd(const char *name
)
743 if(EmptyString(name
))
746 hashv
= hash_nick(name
);
748 DLINK_FOREACH(ptr
, ndTable
[hashv
].head
)
752 if(!irccmp(name
, nd
->name
))
760 output_hash(struct Client
*source_p
, const char *name
, int length
, int *counts
, int deepest
)
762 unsigned long total
= 0;
765 sendto_one_numeric(source_p
, RPL_STATSDEBUG
,
766 "B :%s Hash Statistics", name
);
768 sendto_one_numeric(source_p
, RPL_STATSDEBUG
,
769 "B :Size: %d Empty: %d (%.3f%%)",
771 (float) ((counts
[0]*100) / (float) length
));
773 for(i
= 1; i
< 11; i
++)
775 total
+= (counts
[i
] * i
);
778 /* dont want to divide by 0! --fl */
779 if(counts
[0] != length
)
780 sendto_one_numeric(source_p
, RPL_STATSDEBUG
,
781 "B :Average depth: %.3f/%.3f Highest depth: %d",
782 (float) (total
/ (length
- counts
[0])),
783 (float) (total
/ length
), deepest
);
785 for(i
= 0; i
< 11; i
++)
787 sendto_one_numeric(source_p
, RPL_STATSDEBUG
,
788 "B :Nodes with %d entries: %d",
795 count_hash(struct Client
*source_p
, dlink_list
*table
, int length
, const char *name
)
801 memset(counts
, 0, sizeof(counts
));
803 for(i
= 0; i
< length
; i
++)
805 if(dlink_list_length(&table
[i
]) >= 10)
808 counts
[dlink_list_length(&table
[i
])]++;
810 if(dlink_list_length(&table
[i
]) > deepest
)
811 deepest
= dlink_list_length(&table
[i
]);
814 output_hash(source_p
, name
, length
, counts
, deepest
);
818 hash_stats(struct Client
*source_p
)
820 count_hash(source_p
, channelTable
, CH_MAX
, "Channel");
821 sendto_one_numeric(source_p
, RPL_STATSDEBUG
, "B :--");
822 count_hash(source_p
, clientTable
, U_MAX
, "Client");
823 sendto_one_numeric(source_p
, RPL_STATSDEBUG
, "B :--");
824 count_hash(source_p
, idTable
, U_MAX
, "ID");
825 sendto_one_numeric(source_p
, RPL_STATSDEBUG
, "B :--");
826 count_hash(source_p
, hostTable
, HOST_MAX
, "Hostname");