]> jfr.im git - irc/rqf/shadowircd.git/blob - src/hash.c
projects / irc / rqf / shadowircd.git / blob
? search:


5386856b70221466daf2ef7284aaa5ec730df933
[irc/rqf/shadowircd.git] / src / hash.c
1 /*
2 * ircd-ratbox: A slightly useful ircd.
3 * hash.c: Maintains hashtables.
4 *
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
8 *
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.
13 *
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.
18 *
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
22 * USA
23 *
24 * $Id: hash.c 3177 2007-02-01 00:19:14Z jilles $
25 */
26
27 #include "stdinc.h"
28 #include "ircd_defs.h"
29 #include "s_conf.h"
30 #include "channel.h"
31 #include "client.h"
32 #include "common.h"
33 #include "hash.h"
34 #include "match.h"
35 #include "ircd.h"
36 #include "numeric.h"
37 #include "send.h"
38 #include "msg.h"
39 #include "cache.h"
40 #include "s_newconf.h"
41
42 #define hash_cli_fd(x) (x % CLI_FD_MAX)
43
44 static rb_dlink_list clientbyfdTable[U_MAX];
45
46 rb_dlink_list *clientTable;
47 rb_dlink_list *channelTable;
48 rb_dlink_list *idTable;
49 rb_dlink_list *resvTable;
50 rb_dlink_list *hostTable;
51
52 /*
53 * look in whowas.c for the missing ...[WW_MAX]; entry
54 */
55
56 /*
57 * Hashing.
58 *
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
64 * during use:
65 * +-----+ +-----+ +-----+ +-----+
66 * ---| 224 |----| 225 |----| 226 |---| 227 |---
67 * +-----+ +-----+ +-----+ +-----+
68 * | | |
69 * +-----+ +-----+ +-----+
70 * | A | | C | | D |
71 * +-----+ +-----+ +-----+
72 * |
73 * +-----+
74 * | B |
75 * +-----+
76 *
77 * A - GOPbot, B - chang, C - hanuaway, D - *.mu.OZ.AU
78 *
79 * The order shown above is just one instant of the server.
80 *
81 *
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
85 *
86 *
87 */
88
89 /* init_hash()
90 *
91 * clears the various hashtables
92 */
93 void
94 init_hash(void)
95 {
96 clientTable = rb_malloc(sizeof(rb_dlink_list) * U_MAX);
97 idTable = rb_malloc(sizeof(rb_dlink_list) * U_MAX);
98 channelTable = rb_malloc(sizeof(rb_dlink_list) * CH_MAX);
99 hostTable = rb_malloc(sizeof(rb_dlink_list) * HOST_MAX);
100 resvTable = rb_malloc(sizeof(rb_dlink_list) * R_MAX);
101 }
102
103 #ifndef RICER_HASHING
104 u_int32_t
105 fnv_hash_upper(const unsigned char *s, int bits)
106 {
107 u_int32_t h = FNV1_32_INIT;
108
109 while (*s)
110 {
111 h ^= ToUpper(*s++);
112 h += (h<<1) + (h<<4) + (h<<7) + (h << 8) + (h << 24);
113 }
114 if (bits < 32)
115 h = ((h >> bits) ^ h) & ((1<<bits)-1);
116 return h;
117 }
118
119 u_int32_t
120 fnv_hash(const unsigned char *s, int bits)
121 {
122 u_int32_t h = FNV1_32_INIT;
123
124 while (*s)
125 {
126 h ^= *s++;
127 h += (h<<1) + (h<<4) + (h<<7) + (h << 8) + (h << 24);
128 }
129 if (bits < 32)
130 h = ((h >> bits) ^ h) & ((1<<bits)-1);
131 return h;
132 }
133
134 u_int32_t
135 fnv_hash_len(const unsigned char *s, int bits, int len)
136 {
137 u_int32_t h = FNV1_32_INIT;
138 const unsigned char *x = s + len;
139 while (*s && s < x)
140 {
141 h ^= *s++;
142 h += (h<<1) + (h<<4) + (h<<7) + (h << 8) + (h << 24);
143 }
144 if (bits < 32)
145 h = ((h >> bits) ^ h) & ((1<<bits)-1);
146 return h;
147 }
148
149 u_int32_t
150 fnv_hash_upper_len(const unsigned char *s, int bits, int len)
151 {
152 u_int32_t h = FNV1_32_INIT;
153 const unsigned char *x = s + len;
154 while (*s && s < x)
155 {
156 h ^= ToUpper(*s++);
157 h += (h<<1) + (h<<4) + (h<<7) + (h << 8) + (h << 24);
158 }
159 if (bits < 32)
160 h = ((h >> bits) ^ h) & ((1<<bits)-1);
161 return h;
162 }
163 #endif
164
165 /* hash_nick()
166 *
167 * hashes a nickname, first converting to lowercase
168 */
169 static u_int32_t
170 hash_nick(const char *name)
171 {
172 return fnv_hash_upper((const unsigned char *) name, U_MAX_BITS);
173 }
174
175 /* hash_id()
176 *
177 * hashes an id, case is kept
178 */
179 static u_int32_t
180 hash_id(const char *name)
181 {
182 return fnv_hash((const unsigned char *) name, U_MAX_BITS);
183 }
184
185 /* hash_channel()
186 *
187 * hashes a channel name, based on first 30 chars only for efficiency
188 */
189 static u_int32_t
190 hash_channel(const char *name)
191 {
192 return fnv_hash_upper_len((const unsigned char *) name, CH_MAX_BITS, 30);
193 }
194
195 /* hash_hostname()
196 *
197 * hashes a hostname, based on first 30 chars only, as thats likely to
198 * be more dynamic than rest.
199 */
200 static u_int32_t
201 hash_hostname(const char *name)
202 {
203 return fnv_hash_upper_len((const unsigned char *) name, HOST_MAX_BITS, 30);
204 }
205
206 /* hash_resv()
207 *
208 * hashes a resv channel name, based on first 30 chars only
209 */
210 static u_int32_t
211 hash_resv(const char *name)
212 {
213 return fnv_hash_upper_len((const unsigned char *) name, R_MAX_BITS, 30);
214 }
215
216 /* add_to_id_hash()
217 *
218 * adds an entry to the id hash table
219 */
220 void
221 add_to_id_hash(const char *name, struct Client *client_p)
222 {
223 unsigned int hashv;
224
225 if(EmptyString(name) || (client_p == NULL))
226 return;
227
228 hashv = hash_id(name);
229 rb_dlinkAddAlloc(client_p, &idTable[hashv]);
230 }
231
232 /* add_to_client_hash()
233 *
234 * adds an entry (client/server) to the client hash table
235 */
236 void
237 add_to_client_hash(const char *name, struct Client *client_p)
238 {
239 unsigned int hashv;
240
241 s_assert(name != NULL);
242 s_assert(client_p != NULL);
243 if(EmptyString(name) || (client_p == NULL))
244 return;
245
246 hashv = hash_nick(name);
247 rb_dlinkAddAlloc(client_p, &clientTable[hashv]);
248 }
249
250 /* add_to_hostname_hash()
251 *
252 * adds a client entry to the hostname hash table
253 */
254 void
255 add_to_hostname_hash(const char *hostname, struct Client *client_p)
256 {
257 unsigned int hashv;
258
259 s_assert(hostname != NULL);
260 s_assert(client_p != NULL);
261 if(EmptyString(hostname) || (client_p == NULL))
262 return;
263
264 hashv = hash_hostname(hostname);
265 rb_dlinkAddAlloc(client_p, &hostTable[hashv]);
266 }
267
268 /* add_to_resv_hash()
269 *
270 * adds a resv channel entry to the resv hash table
271 */
272 void
273 add_to_resv_hash(const char *name, struct ConfItem *aconf)
274 {
275 unsigned int hashv;
276
277 s_assert(!EmptyString(name));
278 s_assert(aconf != NULL);
279 if(EmptyString(name) || aconf == NULL)
280 return;
281
282 hashv = hash_resv(name);
283 rb_dlinkAddAlloc(aconf, &resvTable[hashv]);
284 }
285
286 /* del_from_id_hash()
287 *
288 * removes an id from the id hash table
289 */
290 void
291 del_from_id_hash(const char *id, struct Client *client_p)
292 {
293 unsigned int hashv;
294
295 s_assert(id != NULL);
296 s_assert(client_p != NULL);
297 if(EmptyString(id) || client_p == NULL)
298 return;
299
300 hashv = hash_id(id);
301 rb_dlinkFindDestroy(client_p, &idTable[hashv]);
302 }
303
304 /* del_from_client_hash()
305 *
306 * removes a client/server from the client hash table
307 */
308 void
309 del_from_client_hash(const char *name, struct Client *client_p)
310 {
311 unsigned int hashv;
312
313 /* no s_asserts, this can happen when removing a client that
314 * is unregistered.
315 */
316 if(EmptyString(name) || client_p == NULL)
317 return;
318
319 hashv = hash_nick(name);
320 rb_dlinkFindDestroy(client_p, &clientTable[hashv]);
321 }
322
323 /* del_from_channel_hash()
324 *
325 * removes a channel from the channel hash table
326 */
327 void
328 del_from_channel_hash(const char *name, struct Channel *chptr)
329 {
330 unsigned int hashv;
331
332 s_assert(name != NULL);
333 s_assert(chptr != NULL);
334
335 if(EmptyString(name) || chptr == NULL)
336 return;
337
338 hashv = hash_channel(name);
339 rb_dlinkFindDestroy(chptr, &channelTable[hashv]);
340 }
341
342 /* del_from_hostname_hash()
343 *
344 * removes a client entry from the hostname hash table
345 */
346 void
347 del_from_hostname_hash(const char *hostname, struct Client *client_p)
348 {
349 unsigned int hashv;
350
351 if(hostname == NULL || client_p == NULL)
352 return;
353
354 hashv = hash_hostname(hostname);
355
356 rb_dlinkFindDestroy(client_p, &hostTable[hashv]);
357 }
358
359 /* del_from_resv_hash()
360 *
361 * removes a resv entry from the resv hash table
362 */
363 void
364 del_from_resv_hash(const char *name, struct ConfItem *aconf)
365 {
366 unsigned int hashv;
367
368 s_assert(name != NULL);
369 s_assert(aconf != NULL);
370 if(EmptyString(name) || aconf == NULL)
371 return;
372
373 hashv = hash_resv(name);
374
375 rb_dlinkFindDestroy(aconf, &resvTable[hashv]);
376 }
377
378 /* find_id()
379 *
380 * finds a client entry from the id hash table
381 */
382 struct Client *
383 find_id(const char *name)
384 {
385 struct Client *target_p;
386 rb_dlink_node *ptr;
387 unsigned int hashv;
388
389 if(EmptyString(name))
390 return NULL;
391
392 hashv = hash_id(name);
393
394 RB_DLINK_FOREACH(ptr, idTable[hashv].head)
395 {
396 target_p = ptr->data;
397
398 if(strcmp(name, target_p->id) == 0)
399 return target_p;
400 }
401
402 return NULL;
403 }
404
405 /* find_client()
406 *
407 * finds a client/server entry from the client hash table
408 */
409 struct Client *
410 find_client(const char *name)
411 {
412 struct Client *target_p;
413 rb_dlink_node *ptr;
414 unsigned int hashv;
415
416 s_assert(name != NULL);
417 if(EmptyString(name))
418 return NULL;
419
420 /* hunting for an id, not a nick */
421 if(IsDigit(*name))
422 return (find_id(name));
423
424 hashv = hash_nick(name);
425
426 RB_DLINK_FOREACH(ptr, clientTable[hashv].head)
427 {
428 target_p = ptr->data;
429
430 if(irccmp(name, target_p->name) == 0)
431 return target_p;
432 }
433
434 return NULL;
435 }
436
437 /* find_named_client()
438 *
439 * finds a client/server entry from the client hash table
440 */
441 struct Client *
442 find_named_client(const char *name)
443 {
444 struct Client *target_p;
445 rb_dlink_node *ptr;
446 unsigned int hashv;
447
448 s_assert(name != NULL);
449 if(EmptyString(name))
450 return NULL;
451
452 hashv = hash_nick(name);
453
454 RB_DLINK_FOREACH(ptr, clientTable[hashv].head)
455 {
456 target_p = ptr->data;
457
458 if(irccmp(name, target_p->name) == 0)
459 return target_p;
460 }
461
462 return NULL;
463 }
464
465 /* find_server()
466 *
467 * finds a server from the client hash table
468 */
469 struct Client *
470 find_server(struct Client *source_p, const char *name)
471 {
472 struct Client *target_p;
473 rb_dlink_node *ptr;
474 unsigned int hashv;
475
476 if(EmptyString(name))
477 return NULL;
478
479 if((source_p == NULL || !MyClient(source_p)) &&
480 IsDigit(*name) && strlen(name) == 3)
481 {
482 target_p = find_id(name);
483 return(target_p);
484 }
485
486 hashv = hash_nick(name);
487
488 RB_DLINK_FOREACH(ptr, clientTable[hashv].head)
489 {
490 target_p = ptr->data;
491
492 if((IsServer(target_p) || IsMe(target_p)) &&
493 irccmp(name, target_p->name) == 0)
494 return target_p;
495 }
496
497 return NULL;
498 }
499
500 /* find_hostname()
501 *
502 * finds a hostname rb_dlink list from the hostname hash table.
503 * we return the full rb_dlink list, because you can have multiple
504 * entries with the same hostname
505 */
506 rb_dlink_node *
507 find_hostname(const char *hostname)
508 {
509 unsigned int hashv;
510
511 if(EmptyString(hostname))
512 return NULL;
513
514 hashv = hash_hostname(hostname);
515
516 return hostTable[hashv].head;
517 }
518
519 /* find_channel()
520 *
521 * finds a channel from the channel hash table
522 */
523 struct Channel *
524 find_channel(const char *name)
525 {
526 struct Channel *chptr;
527 rb_dlink_node *ptr;
528 unsigned int hashv;
529
530 s_assert(name != NULL);
531 if(EmptyString(name))
532 return NULL;
533
534 hashv = hash_channel(name);
535
536 RB_DLINK_FOREACH(ptr, channelTable[hashv].head)
537 {
538 chptr = ptr->data;
539
540 if(irccmp(name, chptr->chname) == 0)
541 return chptr;
542 }
543
544 return NULL;
545 }
546
547 /*
548 * get_or_create_channel
549 * inputs - client pointer
550 * - channel name
551 * - pointer to int flag whether channel was newly created or not
552 * output - returns channel block or NULL if illegal name
553 * - also modifies *isnew
554 *
555 * Get Channel block for chname (and allocate a new channel
556 * block, if it didn't exist before).
557 */
558 struct Channel *
559 get_or_create_channel(struct Client *client_p, const char *chname, int *isnew)
560 {
561 struct Channel *chptr;
562 rb_dlink_node *ptr;
563 unsigned int hashv;
564 int len;
565 const char *s = chname;
566
567 if(EmptyString(s))
568 return NULL;
569
570 len = strlen(s);
571 if(len > CHANNELLEN)
572 {
573 char *t;
574 if(IsServer(client_p))
575 {
576 sendto_realops_snomask(SNO_DEBUG, L_ALL,
577 "*** Long channel name from %s (%d > %d): %s",
578 client_p->name, len, CHANNELLEN, s);
579 }
580 len = CHANNELLEN;
581 t = LOCAL_COPY(s);
582 *(t + CHANNELLEN) = '\0';
583 s = t;
584 }
585
586 hashv = hash_channel(s);
587
588 RB_DLINK_FOREACH(ptr, channelTable[hashv].head)
589 {
590 chptr = ptr->data;
591
592 if(irccmp(s, chptr->chname) == 0)
593 {
594 if(isnew != NULL)
595 *isnew = 0;
596 return chptr;
597 }
598 }
599
600 if(isnew != NULL)
601 *isnew = 1;
602
603 chptr = allocate_channel(s);
604
605 rb_dlinkAdd(chptr, &chptr->node, &global_channel_list);
606
607 chptr->channelts = rb_current_time(); /* doesn't hurt to set it here */
608
609 rb_dlinkAddAlloc(chptr, &channelTable[hashv]);
610
611 return chptr;
612 }
613
614 /* hash_find_resv()
615 *
616 * hunts for a resv entry in the resv hash table
617 */
618 struct ConfItem *
619 hash_find_resv(const char *name)
620 {
621 struct ConfItem *aconf;
622 rb_dlink_node *ptr;
623 unsigned int hashv;
624
625 s_assert(name != NULL);
626 if(EmptyString(name))
627 return NULL;
628
629 hashv = hash_resv(name);
630
631 RB_DLINK_FOREACH(ptr, resvTable[hashv].head)
632 {
633 aconf = ptr->data;
634
635 if(!irccmp(name, aconf->host))
636 {
637 aconf->port++;
638 return aconf;
639 }
640 }
641
642 return NULL;
643 }
644
645 void
646 clear_resv_hash(void)
647 {
648 struct ConfItem *aconf;
649 rb_dlink_node *ptr;
650 rb_dlink_node *next_ptr;
651 int i;
652
653 HASH_WALK_SAFE(i, R_MAX, ptr, next_ptr, resvTable)
654 {
655 aconf = ptr->data;
656
657 /* skip temp resvs */
658 if(aconf->hold)
659 continue;
660
661 free_conf(ptr->data);
662 rb_dlinkDestroy(ptr, &resvTable[i]);
663 }
664 HASH_WALK_END
665 }
666
667 void
668 add_to_cli_fd_hash(struct Client *client_p)
669 {
670 rb_dlinkAddAlloc(client_p, &clientbyfdTable[hash_cli_fd(rb_get_fd(client_p->localClient->F))]);
671 }
672
673
674 void
675 del_from_cli_fd_hash(struct Client *client_p)
676 {
677 unsigned int hashv;
678 hashv = hash_cli_fd(rb_get_fd(client_p->localClient->F));
679 rb_dlinkFindDestroy(client_p, &clientbyfdTable[hashv]);
680 }
681
682 struct Client *
683 find_cli_fd_hash(int fd)
684 {
685 struct Client *target_p;
686 rb_dlink_node *ptr;
687 unsigned int hashv;
688 hashv = hash_cli_fd(fd);
689 RB_DLINK_FOREACH(ptr, clientbyfdTable[hashv].head)
690 {
691 target_p = ptr->data;
692 if(rb_get_fd(target_p->localClient->F) == fd)
693 return target_p;
694 }
695 return NULL;
696 }
697
698 static void
699 output_hash(struct Client *source_p, const char *name, int length, int *counts, int deepest)
700 {
701 unsigned long total = 0;
702 int i;
703 char buf[128];
704
705 sendto_one_numeric(source_p, RPL_STATSDEBUG,
706 "B :%s Hash Statistics", name);
707
708 snprintf(buf, sizeof buf, "%.3f%%",
709 (float) ((counts[0]*100) / (float) length));
710 sendto_one_numeric(source_p, RPL_STATSDEBUG,
711 "B :Size: %d Empty: %d (%s)",
712 length, counts[0], buf);
713
714 for(i = 1; i < 11; i++)
715 {
716 total += (counts[i] * i);
717 }
718
719 /* dont want to divide by 0! --fl */
720 if(counts[0] != length)
721 {
722 snprintf(buf, sizeof buf, "%.3f/%.3f",
723 (float) (total / (length - counts[0])),
724 (float) (total / length));
725 sendto_one_numeric(source_p, RPL_STATSDEBUG,
726 "B :Average depth: %s Highest depth: %d",
727 buf, deepest);
728 }
729
730 for(i = 0; i < 11; i++)
731 {
732 sendto_one_numeric(source_p, RPL_STATSDEBUG,
733 "B :Nodes with %d entries: %d",
734 i, counts[i]);
735 }
736 }
737
738
739 static void
740 count_hash(struct Client *source_p, rb_dlink_list *table, int length, const char *name)
741 {
742 int counts[11];
743 int deepest = 0;
744 int i;
745
746 memset(counts, 0, sizeof(counts));
747
748 for(i = 0; i < length; i++)
749 {
750 if(rb_dlink_list_length(&table[i]) >= 10)
751 counts[10]++;
752 else
753 counts[rb_dlink_list_length(&table[i])]++;
754
755 if(rb_dlink_list_length(&table[i]) > deepest)
756 deepest = rb_dlink_list_length(&table[i]);
757 }
758
759 output_hash(source_p, name, length, counts, deepest);
760 }
761
762 void
763 hash_stats(struct Client *source_p)
764 {
765 count_hash(source_p, channelTable, CH_MAX, "Channel");
766 sendto_one_numeric(source_p, RPL_STATSDEBUG, "B :--");
767 count_hash(source_p, clientTable, U_MAX, "Client");
768 sendto_one_numeric(source_p, RPL_STATSDEBUG, "B :--");
769 count_hash(source_p, idTable, U_MAX, "ID");
770 sendto_one_numeric(source_p, RPL_STATSDEBUG, "B :--");
771 count_hash(source_p, hostTable, HOST_MAX, "Hostname");
772 }
Unnamed repository; edit this file 'description' to name the repository.