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