]>
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"
34 #include "irc_string.h"
40 #include "s_newconf.h"
42 rb_dlink_list
*clientTable
;
43 rb_dlink_list
*channelTable
;
44 rb_dlink_list
*idTable
;
45 rb_dlink_list
*resvTable
;
46 rb_dlink_list
*hostTable
;
49 * look in whowas.c for the missing ...[WW_MAX]; entry
55 * The server uses a chained hash table to provide quick and efficient
56 * hash table maintenance (providing the hash function works evenly over
57 * the input range). The hash table is thus not susceptible to problems
58 * of filling all the buckets or the need to rehash.
59 * It is expected that the hash table would look something like this
61 * +-----+ +-----+ +-----+ +-----+
62 * ---| 224 |----| 225 |----| 226 |---| 227 |---
63 * +-----+ +-----+ +-----+ +-----+
65 * +-----+ +-----+ +-----+
67 * +-----+ +-----+ +-----+
73 * A - GOPbot, B - chang, C - hanuaway, D - *.mu.OZ.AU
75 * The order shown above is just one instant of the server.
78 * The hash functions currently used are based Fowler/Noll/Vo hashes
79 * which work amazingly well and have a extremely low collision rate
80 * For more info see http://www.isthe.com/chongo/tech/comp/fnv/index.html
87 * clears the various hashtables
92 clientTable
= MyMalloc(sizeof(rb_dlink_list
) * U_MAX
);
93 idTable
= MyMalloc(sizeof(rb_dlink_list
) * U_MAX
);
94 channelTable
= MyMalloc(sizeof(rb_dlink_list
) * CH_MAX
);
95 hostTable
= MyMalloc(sizeof(rb_dlink_list
) * HOST_MAX
);
96 resvTable
= MyMalloc(sizeof(rb_dlink_list
) * R_MAX
);
101 fnv_hash_upper(const unsigned char *s
, int bits
)
103 u_int32_t h
= FNV1_32_INIT
;
108 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
111 h
= ((h
>> bits
) ^ h
) & ((1<<bits
)-1);
116 fnv_hash(const unsigned char *s
, int bits
)
118 u_int32_t h
= FNV1_32_INIT
;
123 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
126 h
= ((h
>> bits
) ^ h
) & ((1<<bits
)-1);
131 fnv_hash_len(const unsigned char *s
, int bits
, int len
)
133 u_int32_t h
= FNV1_32_INIT
;
134 const unsigned char *x
= s
+ len
;
138 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
141 h
= ((h
>> bits
) ^ h
) & ((1<<bits
)-1);
146 fnv_hash_upper_len(const unsigned char *s
, int bits
, int len
)
148 u_int32_t h
= FNV1_32_INIT
;
149 const unsigned char *x
= s
+ len
;
153 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
156 h
= ((h
>> bits
) ^ h
) & ((1<<bits
)-1);
163 * hashes a nickname, first converting to lowercase
166 hash_nick(const char *name
)
168 return fnv_hash_upper((const unsigned char *) name
, U_MAX_BITS
);
173 * hashes an id, case is kept
176 hash_id(const char *name
)
178 return fnv_hash((const unsigned char *) name
, U_MAX_BITS
);
183 * hashes a channel name, based on first 30 chars only for efficiency
186 hash_channel(const char *name
)
188 return fnv_hash_upper_len((const unsigned char *) name
, CH_MAX_BITS
, 30);
193 * hashes a hostname, based on first 30 chars only, as thats likely to
194 * be more dynamic than rest.
197 hash_hostname(const char *name
)
199 return fnv_hash_upper_len((const unsigned char *) name
, HOST_MAX_BITS
, 30);
204 * hashes a resv channel name, based on first 30 chars only
207 hash_resv(const char *name
)
209 return fnv_hash_upper_len((const unsigned char *) name
, R_MAX_BITS
, 30);
214 * adds an entry to the id hash table
217 add_to_id_hash(const char *name
, struct Client
*client_p
)
221 if(EmptyString(name
) || (client_p
== NULL
))
224 hashv
= hash_id(name
);
225 rb_dlinkAddAlloc(client_p
, &idTable
[hashv
]);
228 /* add_to_client_hash()
230 * adds an entry (client/server) to the client hash table
233 add_to_client_hash(const char *name
, struct Client
*client_p
)
237 s_assert(name
!= NULL
);
238 s_assert(client_p
!= NULL
);
239 if(EmptyString(name
) || (client_p
== NULL
))
242 hashv
= hash_nick(name
);
243 rb_dlinkAddAlloc(client_p
, &clientTable
[hashv
]);
246 /* add_to_hostname_hash()
248 * adds a client entry to the hostname hash table
251 add_to_hostname_hash(const char *hostname
, struct Client
*client_p
)
255 s_assert(hostname
!= NULL
);
256 s_assert(client_p
!= NULL
);
257 if(EmptyString(hostname
) || (client_p
== NULL
))
260 hashv
= hash_hostname(hostname
);
261 rb_dlinkAddAlloc(client_p
, &hostTable
[hashv
]);
264 /* add_to_resv_hash()
266 * adds a resv channel entry to the resv hash table
269 add_to_resv_hash(const char *name
, struct ConfItem
*aconf
)
273 s_assert(!EmptyString(name
));
274 s_assert(aconf
!= NULL
);
275 if(EmptyString(name
) || aconf
== NULL
)
278 hashv
= hash_resv(name
);
279 rb_dlinkAddAlloc(aconf
, &resvTable
[hashv
]);
282 /* del_from_id_hash()
284 * removes an id from the id hash table
287 del_from_id_hash(const char *id
, struct Client
*client_p
)
291 s_assert(id
!= NULL
);
292 s_assert(client_p
!= NULL
);
293 if(EmptyString(id
) || client_p
== NULL
)
297 rb_dlinkFindDestroy(client_p
, &idTable
[hashv
]);
300 /* del_from_client_hash()
302 * removes a client/server from the client hash table
305 del_from_client_hash(const char *name
, struct Client
*client_p
)
309 /* no s_asserts, this can happen when removing a client that
312 if(EmptyString(name
) || client_p
== NULL
)
315 hashv
= hash_nick(name
);
316 rb_dlinkFindDestroy(client_p
, &clientTable
[hashv
]);
319 /* del_from_channel_hash()
321 * removes a channel from the channel hash table
324 del_from_channel_hash(const char *name
, struct Channel
*chptr
)
328 s_assert(name
!= NULL
);
329 s_assert(chptr
!= NULL
);
331 if(EmptyString(name
) || chptr
== NULL
)
334 hashv
= hash_channel(name
);
335 rb_dlinkFindDestroy(chptr
, &channelTable
[hashv
]);
338 /* del_from_hostname_hash()
340 * removes a client entry from the hostname hash table
343 del_from_hostname_hash(const char *hostname
, struct Client
*client_p
)
347 if(hostname
== NULL
|| client_p
== NULL
)
350 hashv
= hash_hostname(hostname
);
352 rb_dlinkFindDestroy(client_p
, &hostTable
[hashv
]);
355 /* del_from_resv_hash()
357 * removes a resv entry from the resv hash table
360 del_from_resv_hash(const char *name
, struct ConfItem
*aconf
)
364 s_assert(name
!= NULL
);
365 s_assert(aconf
!= NULL
);
366 if(EmptyString(name
) || aconf
== NULL
)
369 hashv
= hash_resv(name
);
371 rb_dlinkFindDestroy(aconf
, &resvTable
[hashv
]);
376 * finds a client entry from the id hash table
379 find_id(const char *name
)
381 struct Client
*target_p
;
385 if(EmptyString(name
))
388 hashv
= hash_id(name
);
390 RB_DLINK_FOREACH(ptr
, idTable
[hashv
].head
)
392 target_p
= ptr
->data
;
394 if(strcmp(name
, target_p
->id
) == 0)
403 * finds a client/server entry from the client hash table
406 find_client(const char *name
)
408 struct Client
*target_p
;
412 s_assert(name
!= NULL
);
413 if(EmptyString(name
))
416 /* hunting for an id, not a nick */
418 return (find_id(name
));
420 hashv
= hash_nick(name
);
422 RB_DLINK_FOREACH(ptr
, clientTable
[hashv
].head
)
424 target_p
= ptr
->data
;
426 if(irccmp(name
, target_p
->name
) == 0)
433 /* find_named_client()
435 * finds a client/server entry from the client hash table
438 find_named_client(const char *name
)
440 struct Client
*target_p
;
444 s_assert(name
!= NULL
);
445 if(EmptyString(name
))
448 hashv
= hash_nick(name
);
450 RB_DLINK_FOREACH(ptr
, clientTable
[hashv
].head
)
452 target_p
= ptr
->data
;
454 if(irccmp(name
, target_p
->name
) == 0)
463 * finds a server from the client hash table
466 find_server(struct Client
*source_p
, const char *name
)
468 struct Client
*target_p
;
472 if(EmptyString(name
))
475 if((source_p
== NULL
|| !MyClient(source_p
)) &&
476 IsDigit(*name
) && strlen(name
) == 3)
478 target_p
= find_id(name
);
482 hashv
= hash_nick(name
);
484 RB_DLINK_FOREACH(ptr
, clientTable
[hashv
].head
)
486 target_p
= ptr
->data
;
488 if((IsServer(target_p
) || IsMe(target_p
)) &&
489 irccmp(name
, target_p
->name
) == 0)
498 * finds a hostname rb_dlink list from the hostname hash table.
499 * we return the full rb_dlink list, because you can have multiple
500 * entries with the same hostname
503 find_hostname(const char *hostname
)
507 if(EmptyString(hostname
))
510 hashv
= hash_hostname(hostname
);
512 return hostTable
[hashv
].head
;
517 * finds a channel from the channel hash table
520 find_channel(const char *name
)
522 struct Channel
*chptr
;
526 s_assert(name
!= NULL
);
527 if(EmptyString(name
))
530 hashv
= hash_channel(name
);
532 RB_DLINK_FOREACH(ptr
, channelTable
[hashv
].head
)
536 if(irccmp(name
, chptr
->chname
) == 0)
544 * get_or_create_channel
545 * inputs - client pointer
547 * - pointer to int flag whether channel was newly created or not
548 * output - returns channel block or NULL if illegal name
549 * - also modifies *isnew
551 * Get Channel block for chname (and allocate a new channel
552 * block, if it didn't exist before).
555 get_or_create_channel(struct Client
*client_p
, const char *chname
, int *isnew
)
557 struct Channel
*chptr
;
561 const char *s
= chname
;
570 if(IsServer(client_p
))
572 sendto_realops_snomask(SNO_DEBUG
, L_ALL
,
573 "*** Long channel name from %s (%d > %d): %s",
574 client_p
->name
, len
, CHANNELLEN
, s
);
578 *(t
+ CHANNELLEN
) = '\0';
582 hashv
= hash_channel(s
);
584 RB_DLINK_FOREACH(ptr
, channelTable
[hashv
].head
)
588 if(irccmp(s
, chptr
->chname
) == 0)
599 chptr
= allocate_channel(s
);
601 rb_dlinkAdd(chptr
, &chptr
->node
, &global_channel_list
);
603 chptr
->channelts
= CurrentTime
; /* doesn't hurt to set it here */
605 rb_dlinkAddAlloc(chptr
, &channelTable
[hashv
]);
612 * hunts for a resv entry in the resv hash table
615 hash_find_resv(const char *name
)
617 struct ConfItem
*aconf
;
621 s_assert(name
!= NULL
);
622 if(EmptyString(name
))
625 hashv
= hash_resv(name
);
627 RB_DLINK_FOREACH(ptr
, resvTable
[hashv
].head
)
631 if(!irccmp(name
, aconf
->name
))
642 clear_resv_hash(void)
644 struct ConfItem
*aconf
;
646 rb_dlink_node
*next_ptr
;
649 HASH_WALK_SAFE(i
, R_MAX
, ptr
, next_ptr
, resvTable
)
653 /* skip temp resvs */
657 free_conf(ptr
->data
);
658 rb_dlinkDestroy(ptr
, &resvTable
[i
]);
664 output_hash(struct Client
*source_p
, const char *name
, int length
, int *counts
, int deepest
)
666 unsigned long total
= 0;
669 sendto_one_numeric(source_p
, RPL_STATSDEBUG
,
670 "B :%s Hash Statistics", name
);
672 sendto_one_numeric(source_p
, RPL_STATSDEBUG
,
673 "B :Size: %d Empty: %d (%.3f%%)",
675 (float) ((counts
[0]*100) / (float) length
));
677 for(i
= 1; i
< 11; i
++)
679 total
+= (counts
[i
] * i
);
682 /* dont want to divide by 0! --fl */
683 if(counts
[0] != length
)
684 sendto_one_numeric(source_p
, RPL_STATSDEBUG
,
685 "B :Average depth: %.3f/%.3f Highest depth: %d",
686 (float) (total
/ (length
- counts
[0])),
687 (float) (total
/ length
), deepest
);
689 for(i
= 0; i
< 11; i
++)
691 sendto_one_numeric(source_p
, RPL_STATSDEBUG
,
692 "B :Nodes with %d entries: %d",
699 count_hash(struct Client
*source_p
, rb_dlink_list
*table
, int length
, const char *name
)
705 memset(counts
, 0, sizeof(counts
));
707 for(i
= 0; i
< length
; i
++)
709 if(rb_dlink_list_length(&table
[i
]) >= 10)
712 counts
[rb_dlink_list_length(&table
[i
])]++;
714 if(rb_dlink_list_length(&table
[i
]) > deepest
)
715 deepest
= rb_dlink_list_length(&table
[i
]);
718 output_hash(source_p
, name
, length
, counts
, deepest
);
722 hash_stats(struct Client
*source_p
)
724 count_hash(source_p
, channelTable
, CH_MAX
, "Channel");
725 sendto_one_numeric(source_p
, RPL_STATSDEBUG
, "B :--");
726 count_hash(source_p
, clientTable
, U_MAX
, "Client");
727 sendto_one_numeric(source_p
, RPL_STATSDEBUG
, "B :--");
728 count_hash(source_p
, idTable
, U_MAX
, "ID");
729 sendto_one_numeric(source_p
, RPL_STATSDEBUG
, "B :--");
730 count_hash(source_p
, hostTable
, HOST_MAX
, "Hostname");