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 108 2006-10-14 18:12:28Z spb $
  25  */
  26
  27 #include "stdinc.h"
  28 #include "ircd_defs.h"
  29 #include "tools.h"
  30 #include "s_conf.h"
  31 #include "channel.h"
  32 #include "client.h"
  33 #include "common.h"
  34 #include "hash.h"
  35 #include "irc_string.h"
  36 #include "ircd.h"
  37 #include "numeric.h"
  38 #include "send.h"
  39 #include "memory.h"
  40 #include "msg.h"
  41 #include "cache.h"
  42 #include "s_newconf.h"
  43
  44 dlink_list *clientTable;
  45 dlink_list *channelTable;
  46 dlink_list *idTable;
  47 dlink_list *resvTable;
  48 dlink_list *hostTable;
  49 dlink_list *helpTable;
  50 dlink_list *ndTable;
  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 = 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);
 103 }
 104
 105 #ifndef RICER_HASHING
 106 u_int32_t
 107 fnv_hash_upper(const unsigned char *s, int bits)
 108 {
 109         u_int32_t h = FNV1_32_INIT;
 110
 111         while (*s)
 112         {
 113                 h ^= ToUpper(*s++);
 114                 h += (h<<1) + (h<<4) + (h<<7) + (h << 8) + (h << 24);
 115         }
 116         h = (h >> bits) ^ (h & ((2^bits)-1));
 117         return h;
 118 }
 119
 120 u_int32_t
 121 fnv_hash(const unsigned char *s, int bits)
 122 {
 123         u_int32_t h = FNV1_32_INIT;
 124
 125         while (*s)
 126         {
 127                 h ^= *s++;
 128                 h += (h<<1) + (h<<4) + (h<<7) + (h << 8) + (h << 24);
 129         }
 130         h = (h >> bits) ^ (h & ((2^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         h = (h >> bits) ^ (h & ((2^bits)-1));
 145         return h;
 146 }
 147
 148 u_int32_t
 149 fnv_hash_upper_len(const unsigned char *s, int bits, int len)
 150 {
 151         u_int32_t h = FNV1_32_INIT;
 152         const unsigned char *x = s + len;
 153         while (*s && s < x)
 154         {
 155                 h ^= ToUpper(*s++);
 156                 h += (h<<1) + (h<<4) + (h<<7) + (h << 8) + (h << 24);
 157         }
 158         h = (h >> bits) ^ (h & ((2^bits)-1));
 159         return h;
 160 }
 161 #endif
 162
 163 /* hash_nick()
 164  *
 165  * hashes a nickname, first converting to lowercase
 166  */
 167 static u_int32_t
 168 hash_nick(const char *name)
 169 {
 170         return fnv_hash_upper((const unsigned char *) name, U_MAX_BITS);
 171 }
 172
 173 /* hash_id()
 174  *
 175  * hashes an id, case is kept
 176  */
 177 static u_int32_t
 178 hash_id(const char *name)
 179 {
 180         return fnv_hash((const unsigned char *) name, U_MAX_BITS);
 181 }
 182
 183 /* hash_channel()
 184  *
 185  * hashes a channel name, based on first 30 chars only for efficiency
 186  */
 187 static u_int32_t
 188 hash_channel(const char *name)
 189 {
 190         return fnv_hash_upper_len((const unsigned char *) name, CH_MAX_BITS, 30);
 191 }
 192
 193 /* hash_hostname()
 194  *
 195  * hashes a hostname, based on first 30 chars only, as thats likely to
 196  * be more dynamic than rest.
 197  */
 198 static u_int32_t
 199 hash_hostname(const char *name)
 200 {
 201         return fnv_hash_upper_len((const unsigned char *) name, HOST_MAX_BITS, 30);
 202 }
 203
 204 /* hash_resv()
 205  *
 206  * hashes a resv channel name, based on first 30 chars only
 207  */
 208 static u_int32_t
 209 hash_resv(const char *name)
 210 {
 211         return fnv_hash_upper_len((const unsigned char *) name, R_MAX_BITS, 30);
 212 }
 213
 214 static unsigned int
 215 hash_help(const char *name)
 216 {
 217         unsigned int h = 0;
 218
 219         while(*name)
 220         {
 221                 h += (unsigned int) (ToLower(*name++) & 0xDF);
 222         }
 223
 224         return (h % HELP_MAX);
 225 }
 226
 227 /* add_to_id_hash()
 228  *
 229  * adds an entry to the id hash table
 230  */
 231 void
 232 add_to_id_hash(const char *name, struct Client *client_p)
 233 {
 234         unsigned int hashv;
 235
 236         if(EmptyString(name) || (client_p == NULL))
 237                 return;
 238
 239         hashv = hash_id(name);
 240         dlinkAddAlloc(client_p, &idTable[hashv]);
 241 }
 242
 243 /* add_to_client_hash()
 244  *
 245  * adds an entry (client/server) to the client hash table
 246  */
 247 void
 248 add_to_client_hash(const char *name, struct Client *client_p)
 249 {
 250         unsigned int hashv;
 251
 252         s_assert(name != NULL);
 253         s_assert(client_p != NULL);
 254         if(EmptyString(name) || (client_p == NULL))
 255                 return;
 256
 257         hashv = hash_nick(name);
 258         dlinkAddAlloc(client_p, &clientTable[hashv]);
 259 }
 260
 261 /* add_to_hostname_hash()
 262  *
 263  * adds a client entry to the hostname hash table
 264  */
 265 void
 266 add_to_hostname_hash(const char *hostname, struct Client *client_p)
 267 {
 268         unsigned int hashv;
 269
 270         s_assert(hostname != NULL);
 271         s_assert(client_p != NULL);
 272         if(EmptyString(hostname) || (client_p == NULL))
 273                 return;
 274
 275         hashv = hash_hostname(hostname);
 276         dlinkAddAlloc(client_p, &hostTable[hashv]);
 277 }
 278
 279 /* add_to_resv_hash()
 280  *
 281  * adds a resv channel entry to the resv hash table
 282  */
 283 void
 284 add_to_resv_hash(const char *name, struct ConfItem *aconf)
 285 {
 286         unsigned int hashv;
 287
 288         s_assert(!EmptyString(name));
 289         s_assert(aconf != NULL);
 290         if(EmptyString(name) || aconf == NULL)
 291                 return;
 292
 293         hashv = hash_resv(name);
 294         dlinkAddAlloc(aconf, &resvTable[hashv]);
 295 }
 296
 297 void
 298 add_to_help_hash(const char *name, struct cachefile *hptr)
 299 {
 300         unsigned int hashv;
 301
 302         if(EmptyString(name) || hptr == NULL)
 303                 return;
 304
 305         hashv = hash_help(name);
 306         dlinkAddAlloc(hptr, &helpTable[hashv]);
 307 }
 308
 309 void
 310 add_to_nd_hash(const char *name, struct nd_entry *nd)
 311 {
 312         nd->hashv = hash_nick(name);
 313         dlinkAdd(nd, &nd->hnode, &ndTable[nd->hashv]);
 314 }
 315
 316 /* del_from_id_hash()
 317  *
 318  * removes an id from the id hash table
 319  */
 320 void
 321 del_from_id_hash(const char *id, struct Client *client_p)
 322 {
 323         unsigned int hashv;
 324
 325         s_assert(id != NULL);
 326         s_assert(client_p != NULL);
 327         if(EmptyString(id) || client_p == NULL)
 328                 return;
 329
 330         hashv = hash_id(id);
 331         dlinkFindDestroy(client_p, &idTable[hashv]);
 332 }
 333
 334 /* del_from_client_hash()
 335  *
 336  * removes a client/server from the client hash table
 337  */
 338 void
 339 del_from_client_hash(const char *name, struct Client *client_p)
 340 {
 341         unsigned int hashv;
 342
 343         /* no s_asserts, this can happen when removing a client that
 344          * is unregistered.
 345          */
 346         if(EmptyString(name) || client_p == NULL)
 347                 return;
 348
 349         hashv = hash_nick(name);
 350         dlinkFindDestroy(client_p, &clientTable[hashv]);
 351 }
 352
 353 /* del_from_channel_hash()
 354  *
 355  * removes a channel from the channel hash table
 356  */
 357 void
 358 del_from_channel_hash(const char *name, struct Channel *chptr)
 359 {
 360         unsigned int hashv;
 361
 362         s_assert(name != NULL);
 363         s_assert(chptr != NULL);
 364
 365         if(EmptyString(name) || chptr == NULL)
 366                 return;
 367
 368         hashv = hash_channel(name);
 369         dlinkFindDestroy(chptr, &channelTable[hashv]);
 370 }
 371
 372 /* del_from_hostname_hash()
 373  *
 374  * removes a client entry from the hostname hash table
 375  */
 376 void
 377 del_from_hostname_hash(const char *hostname, struct Client *client_p)
 378 {
 379         unsigned int hashv;
 380
 381         if(hostname == NULL || client_p == NULL)
 382                 return;
 383
 384         hashv = hash_hostname(hostname);
 385
 386         dlinkFindDestroy(client_p, &hostTable[hashv]);
 387 }
 388
 389 /* del_from_resv_hash()
 390  *
 391  * removes a resv entry from the resv hash table
 392  */
 393 void
 394 del_from_resv_hash(const char *name, struct ConfItem *aconf)
 395 {
 396         unsigned int hashv;
 397
 398         s_assert(name != NULL);
 399         s_assert(aconf != NULL);
 400         if(EmptyString(name) || aconf == NULL)
 401                 return;
 402
 403         hashv = hash_resv(name);
 404
 405         dlinkFindDestroy(aconf, &resvTable[hashv]);
 406 }
 407
 408 void
 409 clear_help_hash(void)
 410 {
 411         dlink_node *ptr;
 412         dlink_node *next_ptr;
 413         int i;
 414
 415         HASH_WALK_SAFE(i, HELP_MAX, ptr, next_ptr, helpTable)
 416         {
 417                 free_cachefile(ptr->data);
 418                 dlinkDestroy(ptr, &helpTable[i]);
 419         }
 420         HASH_WALK_END
 421 }
 422
 423 /* find_id()
 424  *
 425  * finds a client entry from the id hash table
 426  */
 427 struct Client *
 428 find_id(const char *name)
 429 {
 430         struct Client *target_p;
 431         dlink_node *ptr;
 432         unsigned int hashv;
 433
 434         if(EmptyString(name))
 435                 return NULL;
 436
 437         hashv = hash_id(name);
 438
 439         DLINK_FOREACH(ptr, idTable[hashv].head)
 440         {
 441                 target_p = ptr->data;
 442
 443                 if(strcmp(name, target_p->id) == 0)
 444                         return target_p;
 445         }
 446
 447         return NULL;
 448 }
 449
 450 /* hash_find_masked_server()
 451  *
 452  * Whats happening in this next loop ? Well, it takes a name like
 453  * foo.bar.edu and proceeds to earch for *.edu and then *.bar.edu.
 454  * This is for checking full server names against masks although
 455  * it isnt often done this way in lieu of using matches().
 456  *
 457  * Rewrote to do *.bar.edu first, which is the most likely case,
 458  * also made const correct
 459  * --Bleep
 460  */
 461 static struct Client *
 462 hash_find_masked_server(struct Client *source_p, const char *name)
 463 {
 464         char buf[HOSTLEN + 1];
 465         char *p = buf;
 466         char *s;
 467         struct Client *server;
 468
 469         if('*' == *name || '.' == *name)
 470                 return NULL;
 471
 472         /* copy it across to give us a buffer to work on */
 473         strlcpy(buf, name, sizeof(buf));
 474
 475         while ((s = strchr(p, '.')) != 0)
 476         {
 477                 *--s = '*';
 478                 /*
 479                  * Dont need to check IsServer() here since nicknames cant
 480                  * have *'s in them anyway.
 481                  */
 482                 if((server = find_server(source_p, s)))
 483                         return server;
 484                 p = s + 2;
 485         }
 486
 487         return NULL;
 488 }
 489
 490 /* find_any_client()
 491  *
 492  * finds a client/server/masked server entry from the hash
 493  */
 494 struct Client *
 495 find_any_client(const char *name)
 496 {
 497         struct Client *target_p;
 498         dlink_node *ptr;
 499         unsigned int hashv;
 500
 501         s_assert(name != NULL);
 502         if(EmptyString(name))
 503                 return NULL;
 504
 505         /* hunting for an id, not a nick */
 506         if(IsDigit(*name))
 507                 return (find_id(name));
 508
 509         hashv = hash_nick(name);
 510
 511         DLINK_FOREACH(ptr, clientTable[hashv].head)
 512         {
 513                 target_p = ptr->data;
 514
 515                 if(irccmp(name, target_p->name) == 0)
 516                         return target_p;
 517         }
 518
 519         /* wasnt found, look for a masked server */
 520         return hash_find_masked_server(NULL, name);
 521 }
 522
 523 /* find_client()
 524  *
 525  * finds a client/server entry from the client hash table
 526  */
 527 struct Client *
 528 find_client(const char *name)
 529 {
 530         struct Client *target_p;
 531         dlink_node *ptr;
 532         unsigned int hashv;
 533
 534         s_assert(name != NULL);
 535         if(EmptyString(name))
 536                 return NULL;
 537
 538         /* hunting for an id, not a nick */
 539         if(IsDigit(*name))
 540                 return (find_id(name));
 541
 542         hashv = hash_nick(name);
 543
 544         DLINK_FOREACH(ptr, clientTable[hashv].head)
 545         {
 546                 target_p = ptr->data;
 547
 548                 if(irccmp(name, target_p->name) == 0)
 549                         return target_p;
 550         }
 551
 552         return NULL;
 553 }
 554
 555 /* find_named_client()
 556  *
 557  * finds a client/server entry from the client hash table
 558  */
 559 struct Client *
 560 find_named_client(const char *name)
 561 {
 562         struct Client *target_p;
 563         dlink_node *ptr;
 564         unsigned int hashv;
 565
 566         s_assert(name != NULL);
 567         if(EmptyString(name))
 568                 return NULL;
 569
 570         hashv = hash_nick(name);
 571
 572         DLINK_FOREACH(ptr, clientTable[hashv].head)
 573         {
 574                 target_p = ptr->data;
 575
 576                 if(irccmp(name, target_p->name) == 0)
 577                         return target_p;
 578         }
 579
 580         return NULL;
 581 }
 582
 583 /* find_server()
 584  *
 585  * finds a server from the client hash table
 586  */
 587 struct Client *
 588 find_server(struct Client *source_p, const char *name)
 589 {
 590         struct Client *target_p;
 591         dlink_node *ptr;
 592         unsigned int hashv;
 593
 594         if(EmptyString(name))
 595                 return NULL;
 596
 597         if((source_p == NULL || !MyClient(source_p)) &&
 598            IsDigit(*name) && strlen(name) == 3)
 599         {
 600                 target_p = find_id(name);
 601                 return(target_p);
 602         }
 603
 604         hashv = hash_nick(name);
 605
 606         DLINK_FOREACH(ptr, clientTable[hashv].head)
 607         {
 608                 target_p = ptr->data;
 609
 610                 if((IsServer(target_p) || IsMe(target_p)) &&
 611                    irccmp(name, target_p->name) == 0)
 612                                 return target_p;
 613         }
 614
 615         /* wasnt found, look for a masked server */
 616         return hash_find_masked_server(source_p, name);
 617 }
 618
 619 /* find_hostname()
 620  *
 621  * finds a hostname dlink list from the hostname hash table.
 622  * we return the full dlink list, because you can have multiple
 623  * entries with the same hostname
 624  */
 625 dlink_node *
 626 find_hostname(const char *hostname)
 627 {
 628         unsigned int hashv;
 629
 630         if(EmptyString(hostname))
 631                 return NULL;
 632
 633         hashv = hash_hostname(hostname);
 634
 635         return hostTable[hashv].head;
 636 }
 637
 638 /* find_channel()
 639  *
 640  * finds a channel from the channel hash table
 641  */
 642 struct Channel *
 643 find_channel(const char *name)
 644 {
 645         struct Channel *chptr;
 646         dlink_node *ptr;
 647         unsigned int hashv;
 648
 649         s_assert(name != NULL);
 650         if(EmptyString(name))
 651                 return NULL;
 652
 653         hashv = hash_channel(name);
 654
 655         DLINK_FOREACH(ptr, channelTable[hashv].head)
 656         {
 657                 chptr = ptr->data;
 658
 659                 if(irccmp(name, chptr->chname) == 0)
 660                         return chptr;
 661         }
 662
 663         return NULL;
 664 }
 665
 666 /*
 667  * get_or_create_channel
 668  * inputs       - client pointer
 669  *              - channel name
 670  *              - pointer to int flag whether channel was newly created or not
 671  * output       - returns channel block or NULL if illegal name
 672  *              - also modifies *isnew
 673  *
 674  *  Get Channel block for chname (and allocate a new channel
 675  *  block, if it didn't exist before).
 676  */
 677 struct Channel *
 678 get_or_create_channel(struct Client *client_p, const char *chname, int *isnew)
 679 {
 680         struct Channel *chptr;
 681         dlink_node *ptr;
 682         unsigned int hashv;
 683         int len;
 684         const char *s = chname;
 685
 686         if(EmptyString(s))
 687                 return NULL;
 688
 689         len = strlen(s);
 690         if(len > CHANNELLEN)
 691         {
 692                 char *t;
 693                 if(IsServer(client_p))
 694                 {
 695                         sendto_realops_snomask(SNO_DEBUG, L_NETWIDE,
 696                                              "*** Long channel name from %s (%d > %d): %s",
 697                                              client_p->name, len, CHANNELLEN, s);
 698                 }
 699                 len = CHANNELLEN;
 700                 t = LOCAL_COPY(s);
 701                 *(t + CHANNELLEN) = '\0';
 702                 s = t;
 703         }
 704
 705         hashv = hash_channel(s);
 706
 707         DLINK_FOREACH(ptr, channelTable[hashv].head)
 708         {
 709                 chptr = ptr->data;
 710
 711                 if(irccmp(s, chptr->chname) == 0)
 712                 {
 713                         if(isnew != NULL)
 714                                 *isnew = 0;
 715                         return chptr;
 716                 }
 717         }
 718
 719         if(isnew != NULL)
 720                 *isnew = 1;
 721
 722         chptr = allocate_channel(s);
 723
 724         dlinkAdd(chptr, &chptr->node, &global_channel_list);
 725
 726         chptr->channelts = CurrentTime; /* doesn't hurt to set it here */
 727
 728         dlinkAddAlloc(chptr, &channelTable[hashv]);
 729
 730         return chptr;
 731 }
 732
 733 /* hash_find_resv()
 734  *
 735  * hunts for a resv entry in the resv hash table
 736  */
 737 struct ConfItem *
 738 hash_find_resv(const char *name)
 739 {
 740         struct ConfItem *aconf;
 741         dlink_node *ptr;
 742         unsigned int hashv;
 743
 744         s_assert(name != NULL);
 745         if(EmptyString(name))
 746                 return NULL;
 747
 748         hashv = hash_resv(name);
 749
 750         DLINK_FOREACH(ptr, resvTable[hashv].head)
 751         {
 752                 aconf = ptr->data;
 753
 754                 if(!irccmp(name, aconf->name))
 755                 {
 756                         aconf->port++;
 757                         return aconf;
 758                 }
 759         }
 760
 761         return NULL;
 762 }
 763
 764 struct cachefile *
 765 hash_find_help(const char *name, int flags)
 766 {
 767         struct cachefile *hptr;
 768         dlink_node *ptr;
 769         unsigned int hashv;
 770
 771         if(EmptyString(name))
 772                 return NULL;
 773
 774         hashv = hash_help(name);
 775
 776         DLINK_FOREACH(ptr, helpTable[hashv].head)
 777         {
 778                 hptr = ptr->data;
 779
 780                 if((irccmp(name, hptr->name) == 0) &&
 781                    (hptr->flags & flags))
 782                         return hptr;
 783         }
 784
 785         return NULL;
 786 }
 787
 788 void
 789 clear_resv_hash(void)
 790 {
 791         struct ConfItem *aconf;
 792         dlink_node *ptr;
 793         dlink_node *next_ptr;
 794         int i;
 795
 796         HASH_WALK_SAFE(i, R_MAX, ptr, next_ptr, resvTable)
 797         {
 798                 aconf = ptr->data;
 799
 800                 /* skip temp resvs */
 801                 if(aconf->hold)
 802                         continue;
 803
 804                 free_conf(ptr->data);
 805                 dlinkDestroy(ptr, &resvTable[i]);
 806         }
 807         HASH_WALK_END
 808 }
 809
 810 struct nd_entry *
 811 hash_find_nd(const char *name)
 812 {
 813         struct nd_entry *nd;
 814         dlink_node *ptr;
 815         unsigned int hashv;
 816
 817         if(EmptyString(name))
 818                 return NULL;
 819
 820         hashv = hash_nick(name);
 821
 822         DLINK_FOREACH(ptr, ndTable[hashv].head)
 823         {
 824                 nd = ptr->data;
 825
 826                 if(!irccmp(name, nd->name))
 827                         return nd;
 828         }
 829
 830         return NULL;
 831 }
 832
 833 static void
 834 output_hash(struct Client *source_p, const char *name, int length, int *counts, int deepest)
 835 {
 836         unsigned long total = 0;
 837         int i;
 838
 839         sendto_one_numeric(source_p, RPL_STATSDEBUG,
 840                         "B :%s Hash Statistics", name);
 841
 842         sendto_one_numeric(source_p, RPL_STATSDEBUG,
 843                         "B :Size: %d Empty: %d (%.3f%%)",
 844                         length, counts[0],
 845                         (float) ((counts[0]*100) / (float) length));
 846
 847         for(i = 1; i < 11; i++)
 848         {
 849                 total += (counts[i] * i);
 850         }
 851
 852         /* dont want to divide by 0! --fl */
 853         if(counts[0] != length)
 854                 sendto_one_numeric(source_p, RPL_STATSDEBUG,
 855                                 "B :Average depth: %.3f/%.3f Highest depth: %d",
 856                                 (float) (total / (length - counts[0])),
 857                                 (float) (total / length), deepest);
 858
 859         for(i = 0; i < 11; i++)
 860         {
 861                 sendto_one_numeric(source_p, RPL_STATSDEBUG,
 862                                 "B :Nodes with %d entries: %d",
 863                                 i, counts[i]);
 864         }
 865 }
 866
 867
 868 static void
 869 count_hash(struct Client *source_p, dlink_list *table, int length, const char *name)
 870 {
 871         int counts[11];
 872         int deepest = 0;
 873         int i;
 874
 875         memset(counts, 0, sizeof(counts));
 876
 877         for(i = 0; i < length; i++)
 878         {
 879                 if(dlink_list_length(&table[i]) >= 10)
 880                         counts[10]++;
 881                 else
 882                         counts[dlink_list_length(&table[i])]++;
 883
 884                 if(dlink_list_length(&table[i]) > deepest)
 885                         deepest = dlink_list_length(&table[i]);
 886         }
 887
 888         output_hash(source_p, name, length, counts, deepest);
 889 }
 890
 891 void
 892 hash_stats(struct Client *source_p)
 893 {
 894         count_hash(source_p, channelTable, CH_MAX, "Channel");
 895         sendto_one_numeric(source_p, RPL_STATSDEBUG, "B :--");
 896         count_hash(source_p, clientTable, U_MAX, "Client");
 897         sendto_one_numeric(source_p, RPL_STATSDEBUG, "B :--");
 898         count_hash(source_p, idTable, U_MAX, "ID");
 899         sendto_one_numeric(source_p, RPL_STATSDEBUG, "B :--");
 900         count_hash(source_p, hostTable, HOST_MAX, "Hostname");
 901 }