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