home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 35 Internet / 35-Internet.zip / ircd4652.zip / ircd-df-4.6.5-os2 / src / hash.c < prev    next >
C/C++ Source or Header  |  1997-12-28  |  28KB  |  1,169 lines
  1. /************************************************************************
  2.  *   IRC - Internet Relay Chat, ircd/hash.c
  3.  *   Copyright (C) 1991 Darren Reed
  4.  *
  5.  *   This program is free software; you can redistribute it and/or modify
  6.  *   it under the terms of the GNU General Public License as published by
  7.  *   the Free Software Foundation; either version 1, or (at your option)
  8.  *   any later version.
  9.  *
  10.  *   This program is distributed in the hope that it will be useful,
  11.  *   but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.  *   GNU General Public License for more details.
  14.  *
  15.  *   You should have received a copy of the GNU General Public License
  16.  *   along with this program; if not, write to the Free Software
  17.  *   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18.  */
  19. #ifndef lint
  20. static char sccsid[] = "@(#)hash.c    2.10 7/3/93 (C) 1991 Darren Reed";
  21. #endif
  22.  
  23. #include <limits.h>
  24. #include "numeric.h"
  25. #include "struct.h"
  26. #include "common.h"
  27. #include "sys.h"
  28. #include "hash.h"
  29. #include "h.h"
  30.  
  31. /* Quick & dirty inline version of mycmp for hash-tables -Donwulff */
  32. #define thecmp(str1, str2, where) { \
  33.                                     register char *st1=str1, *st2=str2; \
  34.                                     while (tolower(*st1)==tolower(*st2)) \
  35.                                     { \
  36.                                       if (!*st1) goto where; \
  37.                                       st1++; st2++; \
  38.                                     } \
  39.                                   }
  40.  
  41. #ifdef    DEBUGMODE
  42. static    aHashEntry    *clientTable = NULL;
  43. static    aHashEntry    *channelTable = NULL;
  44. static    int    clhits, clmiss;
  45. static    int    chhits, chmiss;
  46. int    HASHSIZE = 32003;
  47. int    CHANNELHASHSIZE = 10007;
  48. #else /* DEBUGMODE */
  49. static    aHashEntry    clientTable[HASHSIZE];
  50. static    aHashEntry    channelTable[CHANNELHASHSIZE];
  51. #endif /* DEBUGMODE */
  52.  
  53. static    aNotify    *notifyTable[NOTIFYHASHSIZE];
  54.  
  55. /*
  56.  * Hashing.
  57.  *
  58.  *   The server uses a chained hash table to provide quick and efficient
  59.  * hash table mantainence (providing the hash function works evenly over
  60.  * the input range).  The hash table is thus not susceptible to problems
  61.  * of filling all the buckets or the need to rehash.
  62.  *    It is expected that the hash table would look somehting like this
  63.  * during use:
  64.  *                   +-----+    +-----+    +-----+   +-----+
  65.  *                ---| 224 |----| 225 |----| 226 |---| 227 |---
  66.  *                   +-----+    +-----+    +-----+   +-----+
  67.  *                      |          |          |
  68.  *                   +-----+    +-----+    +-----+
  69.  *                   |  A  |    |  C  |    |  D  |
  70.  *                   +-----+    +-----+    +-----+
  71.  *                      |
  72.  *                   +-----+
  73.  *                   |  B  |
  74.  *                   +-----+
  75.  *
  76.  * A - GOPbot, B - chang, C - hanuaway, D - *.mu.OZ.AU
  77.  *
  78.  * The order shown above is just one instant of the server.  Each time a
  79.  * lookup is made on an entry in the hash table and it is found, the entry
  80.  * is moved to the top of the chain.
  81.  */
  82.  
  83. #ifndef ELFHASH
  84. /*
  85.  * hash_nn_name
  86.  *
  87.  * Well, extensive profiling seems to indicate that the hash-function
  88.  * is a major provider to ircd's CPU-usage after all, so we're using
  89.  * _really_ minimalistic hash-function and make up for it with huge
  90.  * hash-tables. -Donwulff
  91.  */
  92. unsigned int hash_nn_name (hname)
  93. const char *hname;
  94. {
  95.     unsigned int hash_value;
  96.  
  97.     for ( hash_value = 0; *hname; ++hname)
  98.         hash_value = ( hash_value << 2 ) ^ tolower(*hname);
  99.  
  100.     return ( hash_value );
  101. }
  102. #else
  103. /* Take equal propotions from the size of int on all arcitechtures */
  104. #define BITS_IN_int             ( sizeof(int) * CHAR_BIT )
  105. #define THREE_QUARTERS            ((int) ((BITS_IN_int * 3) / 4))
  106. #define ONE_EIGHTH        ((int) (BITS_IN_int / 8))
  107. #define HIGH_BITS        ( ~((unsigned int)(~0) >> ONE_EIGHTH ))
  108.  
  109. unsigned int hash_nn_name (hname)
  110. const char *hname;
  111. {
  112.     unsigned int hash_value, i;
  113.  
  114.     for ( hash_value = 0; *hname; ++hname )
  115.     {
  116.         /* Shift hash-value by one eights of int for adding every letter */
  117.         hash_value = ( hash_value << ONE_EIGHTH ) + tolower(*hname);
  118.         /* If the next shift would cause an overflow... */
  119.         if (( i = hash_value & HIGH_BITS ) != 0 )
  120.             /* Then wrap the upper quarter of bits back to the value */
  121.         hash_value = ( hash_value ^ 
  122.                        ( i >> THREE_QUARTERS )) & ~HIGH_BITS;
  123.     }
  124.  
  125.     return ( hash_value );
  126. }
  127. #endif
  128.  
  129. /*
  130.  * clear_*_hash_table
  131.  *
  132.  * Nullify the hashtable and its contents so it is completely empty.
  133.  */
  134. void    clear_client_hash_table()
  135. {
  136. #ifdef    DEBUGMODE
  137.     clhits = 0;
  138.     clmiss = 0;
  139.     if (!clientTable)
  140.         clientTable = (aHashEntry *)MyMalloc(HASHSIZE *
  141.                              sizeof(aHashEntry));
  142. #endif /* DEBUGMODE */
  143.  
  144.     bzero((char *)clientTable, sizeof(aHashEntry) * HASHSIZE);
  145. }
  146.  
  147. void    clear_channel_hash_table()
  148. {
  149. #ifdef    DEBUGMODE
  150.     chmiss = 0;
  151.     chhits = 0;
  152.     if (!channelTable)
  153.         channelTable = (aHashEntry *)MyMalloc(CHANNELHASHSIZE *
  154.                              sizeof(aHashEntry));
  155. #endif /* DEBUGMODE */
  156.     bzero((char *)channelTable, sizeof(aHashEntry) * CHANNELHASHSIZE);
  157. }
  158.  
  159. void    clear_notify_hash_table(void)
  160. {
  161.     bzero((char *)notifyTable, sizeof(notifyTable));
  162. }
  163.  
  164. /*
  165.  * add_to_client_hash_table
  166.  */
  167. int    add_to_client_hash_table(name, cptr)
  168. char    *name;
  169. aClient    *cptr;
  170. {
  171.     int    hashv;
  172.     aClient    *acptr;
  173.  
  174.     hashv = hash_nn_name(name)%HASHSIZE;
  175.  
  176. #ifdef DEBUGMODE
  177.     if(acptr=(aClient *)clientTable[hashv].list) {
  178.         while(acptr&&mycmp(acptr->name,name)) acptr=acptr->hnext;
  179.         if(acptr) dumpcore("add_to_client_hash_table %s",name);
  180.     }
  181.     cptr->hnext = (aClient *)clientTable[hashv].list;
  182.     clientTable[hashv].list = (void *)cptr;
  183.     clientTable[hashv].links++;
  184.     clientTable[hashv].hits++;
  185. #else /* DEBUGMODE */
  186. #ifdef INSERTCHECK
  187.     if(acptr=(aClient *)clientTable[hashv]) {
  188.         while(acptr&&mycmp(acptr->name,name)) acptr=acptr->hnext;
  189.         if(acptr) dumpcore("add_to_client_hash_table %s",name);
  190.     }
  191. #endif /* INSERTCHECK */
  192.     cptr->hnext = (aClient *)clientTable[hashv];
  193.     clientTable[hashv] = (void *)cptr;
  194. #endif /* DEBUGMODE */
  195.     return 0;
  196. }
  197.  
  198. /*
  199.  * add_to_channel_hash_table
  200.  */
  201. int    add_to_channel_hash_table(name, chptr)
  202. char    *name;
  203. aChannel    *chptr;
  204. {
  205.     int    hashv;
  206.     aChannel    *chan;
  207.  
  208.     hashv = hash_nn_name(name)%CHANNELHASHSIZE;
  209.  
  210. #ifdef DEBUGMODE
  211.     if(chan=(aChannel *)channelTable[hashv].list) {
  212.         while(chan&&mycmp(chan->chname,name)) chan=chan->hnextch;
  213.         if(chan) dumpcore("add_to_channel_hash_table %s",name);
  214.     }
  215.     chptr->hnextch = (aChannel *)channelTable[hashv].list;
  216.     channelTable[hashv].list = (void *)chptr;
  217.     channelTable[hashv].links++;
  218.     channelTable[hashv].hits++;
  219. #else /* DEBUGMODE */
  220. #ifdef INSERTCHECK
  221.     if(chan=(aChannel *)channelTable[hashv]) {
  222.         while(chan&&mycmp(chan->chname,name)) chan=chan->hnextch;
  223.         if(chan) dumpcore("add_to_channel_hash_table %s",name);
  224.     }
  225. #endif /* INSERTCHECK */
  226.     chptr->hnextch = (aChannel *)channelTable[hashv];
  227.     channelTable[hashv] = (void *)chptr;
  228. #endif /* DEBUGMODE */
  229.     return 0;
  230. }
  231.  
  232. /*
  233.  * Rough figure of the datastructures for notify:
  234.  *
  235.  * NOTIFY HASH      cptr1
  236.  *   |                |- nick1
  237.  * nick1-|- cptr1     |- nick2
  238.  *   |   |- cptr2                cptr3
  239.  *   |   |- cptr3   cptr2          |- nick1
  240.  *   |                |- nick1
  241.  * nick2-|- cptr2     |- nick2
  242.  *       |- cptr1
  243.  *
  244.  * add-to-notify-hash-table:
  245.  * del-from-notify-hash-table:
  246.  * hash-del-notify-list:
  247.  * hash-check-notify:
  248.  * hash-get-notify:
  249.  */
  250.  
  251. /*
  252.  * count_watch_memory
  253.  */
  254. void    count_watch_memory(count, memory)
  255. int    *count;
  256. u_long    *memory;
  257. {
  258.     int    i = NOTIFYHASHSIZE;
  259.     aNotify    *anptr;
  260.  
  261.  
  262.     while (i--) {
  263.         anptr = notifyTable[i];
  264.         while (anptr) {
  265.             (*count)++;
  266.             (*memory) += sizeof(aNotify)+strlen(anptr->nick);
  267.             anptr = anptr->hnext;
  268.         }
  269.     }
  270. }
  271.  
  272. /*
  273.  * add_to_notify_hash_table
  274.  */
  275. int    add_to_notify_hash_table(nick, cptr)
  276. char    *nick;
  277. aClient    *cptr;
  278. {
  279.     int    hashv;
  280.     aNotify    *anptr;
  281.     Link    *lp;
  282.  
  283.  
  284.     /* Get the right bucket... */
  285.     hashv = hash_nn_name(nick)%NOTIFYHASHSIZE;
  286.  
  287.     /* Find the right nick (header) in the bucket, or NULL... */
  288.     if ((anptr = (aNotify *)notifyTable[hashv]))
  289.         while (anptr && mycmp(anptr->nick, nick))
  290.             anptr = anptr->hnext;
  291.  
  292.     /* If found NULL (no header for this nick), make one... */
  293.     if (!anptr) {
  294.         anptr = (aNotify *)MyMalloc(sizeof(aNotify)+strlen(nick));
  295.         anptr->lasttime = 0;
  296.         strcpy(anptr->nick, nick);
  297.  
  298.         anptr->notify = NULL;
  299.  
  300.         anptr->hnext = notifyTable[hashv];
  301.         notifyTable[hashv] = anptr;
  302.     }
  303.  
  304.     /* Is this client already on the notify-list? */
  305.     if ((lp = anptr->notify))
  306.         while (lp && (lp->value.cptr != cptr))
  307.             lp = lp->next;
  308.  
  309.     /* No it isn't, so add it in the bucket and client addint it */
  310.     if (!lp) {
  311.         lp = anptr->notify;
  312.         anptr->notify = make_link();
  313.         anptr->notify->value.cptr = cptr;
  314.         anptr->notify->next = lp;
  315.  
  316.         lp = make_link();
  317.         lp->next = cptr->notify;
  318.         lp->value.nptr = anptr;
  319.         cptr->notify = lp;
  320.         cptr->notifies++;
  321.     }
  322.  
  323.     return 0;
  324. }
  325.  
  326. /*
  327.  * hash_check_notify
  328.  */
  329. int    hash_check_notify(cptr, reply)
  330. aClient    *cptr;
  331. int    reply;
  332. {
  333.     int    hashv;
  334.     aNotify    *anptr;
  335.     Link    *lp;
  336.  
  337.  
  338.     /* Get us the right bucket */
  339.     hashv = hash_nn_name(cptr->name)%NOTIFYHASHSIZE;
  340.  
  341.     /* Find the right header in this bucket */
  342.     if ((anptr = (aNotify *)notifyTable[hashv]))
  343.         while (anptr && mycmp(anptr->nick, cptr->name))
  344.             anptr = anptr->hnext;
  345.     if (!anptr)
  346.         return 0;    /* This nick isn't on notify */
  347.  
  348.     /* Update the time of last change to item */
  349.     anptr->lasttime = time(NULL);
  350.  
  351.     /* Send notifies out to everybody on the list in header */
  352.     for (lp = anptr->notify; lp; lp = lp->next)
  353.         sendto_one(lp->value.cptr, rpl_str(reply), me.name,
  354.             lp->value.cptr->name, cptr->name,
  355.             (IsPerson(cptr)?cptr->user->username:"<N/A>"),
  356.             (IsPerson(cptr)?cptr->user->host:"<N/A>"),
  357.             anptr->lasttime, cptr->info);
  358.  
  359.     return 0;
  360. }
  361.  
  362. /*
  363.  * hash_get_notify
  364.  */
  365. aNotify    *hash_get_notify(name)
  366. char    *name;
  367. {
  368.     int    hashv;
  369.     aNotify    *anptr;
  370.  
  371.  
  372.     hashv = hash_nn_name(name)%NOTIFYHASHSIZE;
  373.  
  374.     if ((anptr = (aNotify *)notifyTable[hashv]))
  375.         while (anptr && mycmp(anptr->nick, name))
  376.             anptr = anptr->hnext;
  377.  
  378.     return anptr;
  379. }
  380.  
  381. /*
  382.  * del_from_notify_hash_table
  383.  */
  384. int    del_from_notify_hash_table(nick, cptr)
  385. char    *nick;
  386. aClient    *cptr;
  387. {
  388.     int    hashv;
  389.     aNotify    *anptr, *nlast = NULL;
  390.     Link    *lp, *last = NULL;
  391.  
  392.  
  393.     /* Get the bucket for this nick... */
  394.     hashv = hash_nn_name(nick)%NOTIFYHASHSIZE;
  395.  
  396.     /* Find the right header, maintaining last-link pointer... */
  397.     if ((anptr = (aNotify *)notifyTable[hashv]))
  398.         while (anptr && mycmp(anptr->nick, nick)) {
  399.             nlast = anptr;
  400.             anptr = anptr->hnext;
  401.         }
  402.     if (!anptr)
  403.         return 0;    /* No such notify */
  404.  
  405.     /* Find this client from the list of notifies... with last-ptr. */
  406.     if ((lp = anptr->notify))
  407.         while (lp && (lp->value.cptr != cptr)) {
  408.             last = lp;
  409.             lp = lp->next;
  410.         }
  411.     if (!lp)
  412.         return 0;    /* No such client to notify */
  413.  
  414.     /* Fix the linked list under header, then remove the notify entry */
  415.     if (!last)
  416.         anptr->notify = lp->next;
  417.     else
  418.         last->next = lp->next;
  419.     free_link(lp);
  420.  
  421.     /* Do the same regarding the links in client-record... */
  422.     last = NULL;
  423.     if ((lp = cptr->notify))
  424.         while (lp && (lp->value.nptr != anptr)) {
  425.             last = lp;
  426.             lp = lp->next;
  427.         }
  428.  
  429.     /*
  430.      * Give error on the odd case... probobly not even neccessary
  431.      *
  432.      * No error checking in ircd is unneccessary ;) -Cabal95
  433.      */
  434.     if (!lp)
  435.         sendto_ops("WATCH debug error: del_from_notify_hash_table "
  436.                "found a watch entry with no client "
  437.                "counterpoint processing nick %s on client %s!",
  438.                nick, cptr->user);
  439.     else {
  440.         if (!last) /* First one matched */
  441.             cptr->notify = lp->next;
  442.         else
  443.             last->next = lp->next;
  444.         free_link(lp);
  445.     }
  446.  
  447.     /* In case this header is now empty of notices, remove it */
  448.     if (!anptr->notify) {
  449.         if (!nlast)
  450.             notifyTable[hashv] = anptr->hnext;
  451.         else
  452.             nlast->hnext = anptr->hnext;
  453.         MyFree(anptr);
  454.     }
  455.  
  456.     /* Update count of notifies on nick */
  457.     cptr->notifies--;
  458.  
  459.     return 0;
  460. }
  461.  
  462. /*
  463.  * hash_del_notify_list
  464.  */
  465. int    hash_del_notify_list(cptr)
  466. aClient    *cptr;
  467. {
  468.     int    hashv;
  469.     aNotify    *anptr;
  470.     Link    *np, *lp, *last;
  471.  
  472.  
  473.     if (!(np = cptr->notify))
  474.         return 0;    /* Nothing to do */
  475.  
  476.     cptr->notify = NULL;    /* Break the notify-list for client */
  477.     while (np) {
  478.         /* Find the notify-record from hash-table... */
  479.         anptr = np->value.nptr;
  480.         last = NULL;
  481.         for (lp = anptr->notify; lp && (lp->value.cptr != cptr);
  482.              lp = lp->next)
  483.             last = lp;
  484.  
  485.         /* Not found, another "worst case" debug error */
  486.         if (!lp)
  487.             sendto_ops("WATCH Debug error: hash_del_notify_list "
  488.                    "found a WATCH entry with no table "
  489.                    "counterpoint processing client %s!",
  490.                    cptr->name);
  491.         else {
  492.             /* Fix the notify-list and remove entry */
  493.             if (!last)
  494.                 anptr->notify = lp->next;
  495.             else
  496.                 last->next = lp->next;
  497.             free_link(lp);
  498.  
  499.             /*
  500.              * If this leaves a header without notifies,
  501.              * remove it. Need to find the last-pointer!
  502.              */
  503.             if (!anptr->notify) {
  504.                 aNotify    *np2, *nl;
  505.  
  506.                 hashv = hash_nn_name(anptr->nick)%NOTIFYHASHSIZE;
  507.  
  508.                 nl = NULL;
  509.                 np2 = notifyTable[hashv];
  510.                 while (np2 != anptr) {
  511.                     nl = np2;
  512.                     np2 = np2->hnext;
  513.                 }
  514.  
  515.                 if (nl)
  516.                     nl->hnext = anptr->hnext;
  517.                 else
  518.                     notifyTable[hashv] = anptr->hnext;
  519.                 MyFree(anptr);
  520.             }
  521.         }
  522.  
  523.         lp = np;    /* Save last pointer processed */
  524.         np = np->next;    /* Jump to the next pointer */
  525.         free_link(lp);    /* Free the previous */
  526.     }
  527.  
  528.     cptr->notifies = 0;
  529.  
  530.     return 0;
  531. }
  532.  
  533.  
  534. /*
  535.  * del_from_client_hash_table
  536.  */
  537. int    del_from_client_hash_table(name, cptr)
  538. char    *name;
  539. aClient    *cptr;
  540. {
  541.     Reg1    aClient    *tmp, *prev = NULL;
  542.     Reg2    int    hashv;
  543.  
  544.     hashv = hash_nn_name(name)%HASHSIZE;
  545. #ifdef DEBUGMODE
  546.     for (tmp = (aClient *)clientTable[hashv].list; tmp; tmp = tmp->hnext)
  547.         {
  548.         if (tmp == cptr)
  549.             {
  550.             if (prev)
  551.                 prev->hnext = tmp->hnext;
  552.             else
  553.                 clientTable[hashv].list = (void *)tmp->hnext;
  554.             tmp->hnext = NULL;
  555.             if (clientTable[hashv].links > 0)
  556.                 {
  557.                 clientTable[hashv].links--;
  558.                 return 1;
  559.                 } 
  560.             else
  561.                 /*
  562.                  * Should never actually return from here and
  563.                  * if we do it is an error/inconsistency in the
  564.                  * hash table.
  565.                  */
  566.                 return -1;
  567.             return 0; /* Found, we can return -Donwulff */
  568.         }
  569.         prev = tmp;
  570.     }
  571. #else /* DEBUGMODE */
  572.     for (tmp = (aClient *)clientTable[hashv]; tmp; tmp = tmp->hnext) {
  573.         if (tmp == cptr) {
  574.             if (prev)
  575.                 prev->hnext = tmp->hnext;
  576.             else
  577.                 clientTable[hashv] = (void *)tmp->hnext;
  578.             tmp->hnext = NULL;
  579.             return 0; /* Found, we can return -Donwulff */
  580.         }
  581.         prev = tmp;
  582.         }
  583. #endif /* DEBUGMODE */
  584.     return 0;
  585. }
  586.  
  587. /*
  588.  * del_from_channel_hash_table
  589.  */
  590. int    del_from_channel_hash_table(name, chptr)
  591. char    *name;
  592. aChannel    *chptr;
  593. {
  594.     Reg1    aChannel    *tmp, *prev = NULL;
  595.     Reg2    int    hashv;
  596.  
  597.     hashv = hash_nn_name(name)%CHANNELHASHSIZE;
  598. #ifdef DEBUGMODE
  599.     for (tmp = (aChannel *)channelTable[hashv].list; tmp;
  600.          tmp = tmp->hnextch)
  601.         {
  602.         if (tmp == chptr)
  603.             {
  604.             if (prev)
  605.                 prev->hnextch = tmp->hnextch;
  606.             else
  607.                 channelTable[hashv].list=(void *)tmp->hnextch;
  608.             tmp->hnextch = NULL;
  609.             if (channelTable[hashv].links > 0)
  610.                 {
  611.                 channelTable[hashv].links--;
  612.                 return 1;
  613.                 }
  614.             else
  615.                 return -1;
  616.             return 0; /* Found, we can return -Donwulff */
  617.             }
  618.         prev = tmp;
  619.         }
  620. #else /* DEBUGMODE */
  621.     for (tmp = (aChannel *)channelTable[hashv]; tmp; tmp = tmp->hnextch) {
  622.         if (tmp == chptr) {
  623.             if (prev)
  624.                 prev->hnextch = tmp->hnextch;
  625.             else
  626.                 channelTable[hashv]=(void *)tmp->hnextch;
  627.             tmp->hnextch = NULL;
  628.             return 0; /* Found, we can return -Donwulff */
  629.         }
  630.         prev = tmp;
  631.     }
  632. #endif /* DEBUGMODE */
  633.     return 0;
  634. }
  635.  
  636.  
  637. /*
  638.  * hash_get_chan_bucket
  639.  */
  640. aChannel    *hash_get_chan_bucket(hashv)
  641. int    hashv;
  642. {
  643.     if (hashv > CHANNELHASHSIZE)
  644.         return NULL;
  645. #ifdef DEBUGMODE
  646.     return (aChannel *)channelTable[hashv].list;
  647. #else
  648.     return (aChannel *)channelTable[hashv];
  649. #endif
  650. }
  651.  
  652.  
  653. /*
  654.  * hash_find_client
  655.  */
  656. aClient    *hash_find_client(name, cptr)
  657. char    *name;
  658. aClient    *cptr;
  659. {
  660.     Reg1    aClient    *tmp;
  661.     Reg2    aClient    *prv = NULL;
  662. #ifdef DEBUGMODE
  663.     Reg3    aHashEntry    *tmp3;
  664. #endif /* DEBUGMODE */
  665.     int    hashv;
  666.  
  667.     hashv = hash_nn_name(name)%HASHSIZE;
  668.  
  669.     /*
  670.      * Got the bucket, now search the chain.
  671.      */
  672. #ifdef  DEBUGMODE
  673. tmp3 = &clientTable[hashv];
  674.  
  675.     for (tmp = (aClient *)tmp3->list; tmp; prv = tmp, tmp = tmp->hnext)
  676.         thecmp(name, tmp->name, c_move_to_top);
  677.     clmiss++;
  678.     return (cptr);
  679. c_move_to_top:
  680.     clhits++;
  681.     /*
  682.      * If the member of the hashtable we found isnt at the top of its
  683.      * chain, put it there.  This builds a most-frequently used order into
  684.      * the chains of the hash table, giving speadier lookups on those nicks
  685.      * which are being used currently.  This same block of code is also
  686.      * used for channels and servers for the same performance reasons.
  687.      */
  688.     if (prv)
  689.         {
  690.         aClient *tmp2;
  691.  
  692.         tmp2 = (aClient *)tmp3->list;
  693.         tmp3->list = (void *)tmp;
  694.         prv->hnext = tmp->hnext;
  695.         tmp->hnext = tmp2;
  696.         }
  697. #else /* DEBUGMODE */
  698.     for (tmp = (aClient *)clientTable[hashv]; tmp; prv = tmp, tmp = tmp->hnext)
  699.         thecmp(name, tmp->name, c_move_to_top);
  700.     return (cptr);
  701. c_move_to_top:
  702.     if (prv) {
  703.         aClient *tmp2;
  704.  
  705.         tmp2 = (aClient *)clientTable[hashv];
  706.         clientTable[hashv] = (void *)tmp;
  707.         prv->hnext = tmp->hnext;
  708.         tmp->hnext = tmp2;
  709.     }
  710. #endif /* DEBUGMODE */
  711.     return (tmp);
  712. }
  713.  
  714. /*
  715.  * hash_find_nickserver
  716.  */
  717. aClient    *hash_find_nickserver(name, cptr)
  718. char    *name;
  719. aClient *cptr;
  720. {
  721.     Reg1    aClient    *tmp;
  722.     Reg2    aClient    *prv = NULL;
  723. #ifdef DEBUGMODE
  724.     Reg3    aHashEntry    *tmp3;
  725. #endif /* DEBUGMODE */
  726.     int    hashv;
  727.     char    *serv;
  728.  
  729.     serv = index(name, '@');
  730.     *serv++ = '\0';
  731.     hashv = hash_nn_name(name)%HASHSIZE;
  732.  
  733.     /*
  734.      * Got the bucket, now search the chain.
  735.      */
  736. #ifdef  DEBUGMODE
  737. tmp3 = &clientTable[hashv];
  738.     for (tmp = (aClient *)tmp3->list; tmp; prv = tmp, tmp = tmp->hnext)
  739.         if (tmp->user &&
  740.                     mycmp(name, tmp->name) == 0 &&
  741.             mycmp(serv, tmp->user->server) == 0)
  742.             goto c_move_to_top;
  743.  
  744.     clmiss++;
  745. /*    *--serv = '\0'; */ /* This code has no function, perhaps meant @? */
  746.     return (cptr);     /* For now, just remarking it out... -Donwulff */
  747.  
  748. c_move_to_top:
  749.     clhits++;
  750.     if (prv)
  751.         {
  752.         aClient *tmp2;
  753.  
  754.         tmp2 = (aClient *)tmp3->list;
  755.         tmp3->list = (void *)tmp;
  756.         prv->hnext = tmp->hnext;
  757.         tmp->hnext = tmp2;
  758.         }
  759. #else /* DEBUGMODE */
  760.     for (tmp = (aClient *)clientTable[hashv]; tmp; prv = tmp, tmp = tmp->hnext)
  761.         if (tmp->user &&
  762.             mycmp(name, tmp->name) == 0 &&
  763.             mycmp(serv, tmp->user->server) == 0)
  764.             goto c_move_to_top;
  765. /*    *--serv = '\0'; */ /* This code has no function, perhaps meant @? */
  766.     return (cptr);     /* For now, just remarking it out... -Donwulff */
  767.  
  768. c_move_to_top:
  769.     if (prv) {
  770.         aClient *tmp2;
  771.  
  772.         tmp2 = (aClient *)clientTable[hashv];
  773.         clientTable[hashv] = (void *)tmp;
  774.         prv->hnext = tmp->hnext;
  775.         tmp->hnext = tmp2;
  776.     }
  777. #endif /* DEBUGMODE */
  778. /*    *--serv = '\0'; */ /* This code has no function, perhaps meant @? */
  779.     return (tmp);      /* For now, just remarking it out... -Donwulff */
  780. }
  781.  
  782. /*
  783.  * hash_find_server
  784.  */
  785. aClient    *hash_find_server(server, cptr)
  786. char    *server;
  787. aClient *cptr;
  788. {
  789.     Reg1    aClient    *tmp, *prv = NULL;
  790.     Reg2    char    *t;
  791.     Reg3    char    ch;
  792. #ifdef DEBUGMODE
  793.     aHashEntry    *tmp3;
  794. #endif /* DEBUGMODE */
  795.  
  796.     int hashv;
  797.  
  798.     hashv = hash_nn_name(server)%HASHSIZE;
  799.  
  800. #ifdef  DEBUGMODE
  801.     tmp3 = &clientTable[hashv];
  802.  
  803.     for (tmp = (aClient *)tmp3->list; tmp; prv = tmp, tmp = tmp->hnext)
  804.         {
  805.         if (!IsServer(tmp) && !IsMe(tmp))
  806.             continue;
  807.         thecmp(server, tmp->name, s_move_to_top);
  808.         }
  809. #else /* DEBUGMODE */
  810.     for (tmp = (aClient *)clientTable[hashv]; tmp; prv = tmp, tmp = tmp->hnext) {
  811.         if (!IsServer(tmp) && !IsMe(tmp))
  812.             continue;
  813.         thecmp(server, tmp->name, s_move_to_top);
  814.     }
  815. #endif /* DEBUGMODE */
  816.     t = ((char *)server + strlen(server));
  817.     /*
  818.      * Whats happening in this next loop ? Well, it takes a name like
  819.      * foo.bar.edu and proceeds to search for *.edu and then *.bar.edu.
  820.      * This is for checking full server names against masks although
  821.      * it isnt often done this way in lieu of using match().
  822.      */
  823.     for (;;)
  824.         {
  825.         t--;
  826.         for (; t > server; t--)
  827.             if (*(t+1) == '.')
  828.                 break;
  829.         if (t <= server || *t == '*')
  830.             break;
  831.         ch = *t;
  832.         *t = '*';
  833.         /*
  834.           * Dont need to check IsServer() here since nicknames cant
  835.          *have *'s in them anyway.
  836.          */
  837.         if (((tmp = hash_find_client(t, cptr))) != cptr)
  838.             {
  839.             *t = ch;
  840.             return (tmp);
  841.             }
  842.         *t = ch;
  843.         }
  844. #ifdef    DEBUGMODE
  845.     clmiss++;
  846.     return (cptr);
  847. s_move_to_top:
  848.     clhits++;
  849.  
  850.     if (prv)
  851.         {
  852.         aClient *tmp2;
  853.  
  854.         tmp2 = (aClient *)tmp3->list;
  855.         tmp3->list = (void *)tmp;
  856.         prv->hnext = tmp->hnext;
  857.         tmp->hnext = tmp2;
  858.         }
  859. #else /* DEBUGMODE */
  860.     return (cptr);
  861. s_move_to_top:
  862.     if (prv) {
  863.             aClient *tmp2;
  864.  
  865.         tmp2 = (aClient *)clientTable[hashv];
  866.             clientTable[hashv] = (void *)tmp;
  867.             prv->hnext = tmp->hnext;
  868.             tmp->hnext = tmp2;
  869.     }
  870. #endif /* DEBUGMODE */
  871.     return (tmp);
  872. }
  873.  
  874. /*
  875.  * hash_find_channel
  876.  */
  877. aChannel    *hash_find_channel(name, chptr)
  878. char    *name;
  879. aChannel *chptr;
  880. {
  881.     int    hashv;
  882.     Reg1    aChannel    *tmp;
  883.     Reg2    aChannel    *prv = NULL;
  884. #ifdef DEBUGMODE
  885.     aHashEntry    *tmp3;
  886. #endif /* DEBUGMODE */
  887.     hashv = hash_nn_name(name)%CHANNELHASHSIZE;
  888.  
  889. #ifdef  DEBUGMODE
  890.     tmp3 = &channelTable[hashv];
  891.  
  892.     for (tmp = (aChannel *)tmp3->list; tmp; prv = tmp, tmp = tmp->hnextch)
  893.         thecmp(name, tmp->chname, c_move_to_top);
  894.     chmiss++;
  895.     return chptr;
  896. c_move_to_top:
  897.     chhits++;
  898.     if (prv)
  899.         {
  900.         register aChannel *tmp2;
  901.  
  902.         tmp2 = (aChannel *)tmp3->list;
  903.         tmp3->list = (void *)tmp;
  904.         prv->hnextch = tmp->hnextch;
  905.         tmp->hnextch = tmp2;
  906.         }
  907. #else /* DEBUGMODE */
  908.     for (tmp = (aChannel *)channelTable[hashv]; tmp; prv = tmp, tmp = tmp->hnextch)
  909.         thecmp(name, tmp->chname, c_move_to_top);
  910.     return chptr;
  911. c_move_to_top:
  912.     if(prv) {
  913.         register    aChannel    *tmp2;
  914.  
  915.         tmp2 = (aChannel *)channelTable[hashv];
  916.         channelTable[hashv] = (void *)tmp;
  917.         prv->hnextch = tmp->hnextch;
  918.         tmp->hnextch = tmp2;
  919.     }
  920. #endif /* DEBUGMODE */
  921.     return (tmp);
  922. }
  923.  
  924. /*
  925.  * NOTE: this command is not supposed to be an offical part of the ircd
  926.  *       protocol.  It is simply here to help debug and to monitor the
  927.  *       performance of the hash functions and table, enabling a better
  928.  *       algorithm to be sought if this one becomes troublesome.
  929.  *       -avalon
  930.  */
  931.  
  932. int    m_hash(cptr, sptr, parc, parv)
  933. aClient    *cptr, *sptr;
  934. int    parc;
  935. char    *parv[];
  936. {
  937. #ifndef DEBUGMODE
  938.     return 0;
  939. #else
  940.     register    int    l, i;
  941.     register    aHashEntry    *tab;
  942.     int    deepest = 0, deeplink = 0, showlist = 0, tothits = 0;
  943.     int    mosthit = 0, mosthits = 0, used = 0, used_now = 0, totlink = 0;
  944.     int    link_pop[10], size = HASHSIZE;
  945.     char    ch;
  946.     aHashEntry    *table;
  947.  
  948.     if(!IsPrivileged(sptr)) return 0;
  949.  
  950.     if (parc > 1) {
  951.         ch = *parv[1];
  952.         if (islower(ch))
  953.             table = clientTable;
  954.         else {
  955.             table = channelTable;
  956.             size = CHANNELHASHSIZE;
  957.         }
  958.         if (ch == 'L' || ch == 'l')
  959.             showlist = 1;
  960.     } else {
  961.         ch = '\0';
  962.         table = clientTable;
  963.     }
  964.  
  965.     for (i = 0; i < 10; i++)
  966.         link_pop[i] = 0;
  967.     for (i = 0; i < size; i++) {
  968.         tab = &table[i];
  969.         l = tab->links;
  970.         if (showlist)
  971.             sendto_one(sptr,
  972.                "NOTICE %s :Hash Entry:%6d Hits:%7d Links:%6d",
  973.                parv[0], i, tab->hits, l);
  974.         if (l > 0) {
  975.             if (l < 10)
  976.                 link_pop[l]++;
  977.             else
  978.                 link_pop[9]++;
  979.             used_now++;
  980.             totlink += l;
  981.             if (l > deepest) {
  982.                 deepest = l;
  983.                 deeplink = i;
  984.             }
  985.         }
  986.         else
  987.             link_pop[0]++;
  988.         l = tab->hits;
  989.         if (l) {
  990.             used++;
  991.             tothits += l;
  992.             if (l > mosthits) {
  993.                 mosthits = l;
  994.                 mosthit = i;
  995.             }
  996.         }
  997.     }
  998.     switch((int)ch)
  999.     {
  1000.     case 'V' : case 'v' :
  1001.         {
  1002.         register    aClient    *acptr;
  1003.         int    bad = 0, listlength = 0;
  1004.  
  1005.         for (acptr = client; acptr; acptr = acptr->next) {
  1006.             if (hash_find_client(acptr->name,acptr) != acptr) {
  1007.                 if (ch == 'V')
  1008.                 sendto_one(sptr, "NOTICE %s :Bad hash for %s",
  1009.                        parv[0], acptr->name);
  1010.                 bad++;
  1011.             }
  1012.             listlength++;
  1013.         }
  1014.         sendto_one(sptr,"NOTICE %s :List Length: %d Bad Hashes: %d",
  1015.                parv[0], listlength, bad);
  1016.         }
  1017.     case 'P' : case 'p' :
  1018.         for (i = 0; i < 10; i++)
  1019.             sendto_one(sptr,"NOTICE %s :Entires with %d links : %d",
  1020.             parv[0], i, link_pop[i]);
  1021.         return (0);
  1022.     case 'r' :
  1023.         {
  1024.         Reg1    aClient    *acptr;
  1025.  
  1026.         sendto_one(sptr,"NOTICE %s :Rehashing Client List.", parv[0]);
  1027.         clear_client_hash_table();
  1028.         for (acptr = client; acptr; acptr = acptr->next)
  1029.             (void)add_to_client_hash_table(acptr->name, acptr);
  1030.         break;
  1031.         }
  1032.     case 'R' :
  1033.         {
  1034.         Reg1    aChannel    *acptr;
  1035.  
  1036.         sendto_one(sptr,"NOTICE %s :Rehashing Channel List.", parv[0]);
  1037.         clear_channel_hash_table();
  1038.         for (acptr = channel; acptr; acptr = acptr->nextch)
  1039.             (void)add_to_channel_hash_table(acptr->chname, acptr);
  1040.         break;
  1041.         }
  1042.     case 'H' :
  1043.         if (parc > 2)
  1044.             sendto_one(sptr,"NOTICE %s :%s hash to entry %d",
  1045.                    parv[0], parv[2],
  1046.                        hash_nn_name(parv[2])%CHANNELHASHSIZE);
  1047.         return (0);
  1048.     case 'h' :
  1049.         if (parc > 2)
  1050.             sendto_one(sptr,"NOTICE %s :%s hash to entry %d",
  1051.                    parv[0], parv[2],
  1052.                        hash_nn_name(parv[2])%HASHSIZE);
  1053.         return (0);
  1054. /* Quick hack for getting memory statistics from list.c -Donwulff */
  1055.     case 'm' :
  1056.         send_listinfo(sptr, parv[0]);
  1057.         return(0);
  1058.     case 'n' :
  1059.         {
  1060.         aClient    *tmp;
  1061.         int    max;
  1062.  
  1063.         if (parc <= 2)
  1064.             return (0);
  1065.         l = atoi(parv[2]) % HASHSIZE;
  1066.         if (parc > 3)
  1067.             max = atoi(parv[3]) % HASHSIZE;
  1068.         else
  1069.             max = l;
  1070.         for (;l <= max; l++)
  1071.             for (i = 0, tmp = (aClient *)clientTable[l].list; tmp;
  1072.                  i++, tmp = tmp->hnext)
  1073.                 {
  1074.                 if (parv[1][2] == '1' && tmp != tmp->from)
  1075.                     continue;
  1076.                 sendto_one(sptr,"NOTICE %s :Node: %d #%d %s",
  1077.                        parv[0], l, i, tmp->name);
  1078.                 }
  1079.         return (0);
  1080.         }
  1081.     case 'N' :
  1082.         {
  1083.         aChannel *tmp;
  1084.         int    max;
  1085.  
  1086.         if (parc <= 2)
  1087.             return (0);
  1088.         l = atoi(parv[2]) % CHANNELHASHSIZE;
  1089.         if (parc > 3)
  1090.             max = atoi(parv[3]) % CHANNELHASHSIZE;
  1091.         else
  1092.             max = l;
  1093.         for (;l <= max; l++)
  1094.             for (i = 0, tmp = (aChannel *)channelTable[l].list; tmp;
  1095.                  i++, tmp = tmp->hnextch)
  1096.                 sendto_one(sptr,"NOTICE %s :Node: %d #%d %s",
  1097.                        parv[0], l, i, tmp->chname);
  1098.         return (0);
  1099.         }
  1100.     case 'z' :
  1101.         {
  1102.         Reg1    aClient    *acptr;
  1103.  
  1104.         if (parc <= 2)
  1105.             return 0;
  1106.         l = atoi(parv[2]);
  1107.         if (l < 256)
  1108.             return 0;
  1109.         (void)MyFree((char *)clientTable);
  1110.         clientTable = (aHashEntry *)MyMalloc(sizeof(aHashEntry) * l);
  1111.         HASHSIZE = l;
  1112.         clear_client_hash_table();
  1113.         for (acptr = client; acptr; acptr = acptr->next)
  1114.             {
  1115.             acptr->hnext = NULL;
  1116.             (void)add_to_client_hash_table(acptr->name, acptr);
  1117.             }
  1118.         sendto_one(sptr, "NOTICE %s :HASHSIZE now %d", parv[0], l);
  1119.         break;
  1120.         }
  1121.     case 'Z' :
  1122.         {
  1123.         Reg1    aChannel    *acptr;
  1124.  
  1125.         if (parc <= 2)
  1126.             return 0;
  1127.         l = atoi(parv[2]);
  1128.         if (l < 256)
  1129.             return 0;
  1130.         (void)MyFree((char *)channelTable);
  1131.         channelTable = (aHashEntry *)MyMalloc(sizeof(aHashEntry) * l);
  1132.         CHANNELHASHSIZE = l;
  1133.         clear_channel_hash_table();
  1134.         for (acptr = channel; acptr; acptr = acptr->nextch)
  1135.             {
  1136.             acptr->hnextch = NULL;
  1137.             (void)add_to_channel_hash_table(acptr->chname, acptr);
  1138.             }
  1139.         sendto_one(sptr, "NOTICE %s :CHANNELHASHSIZE now %d",
  1140.                parv[0], l);
  1141.         break;
  1142.         }
  1143.     default :
  1144.         break;
  1145.     }
  1146.     sendto_one(sptr,"NOTICE %s :Entries Hashed: %d NonEmpty: %d of %d",
  1147.            parv[0], totlink, used_now, size);
  1148.     if (!used_now)
  1149.         used_now = 1;
  1150.     sendto_one(sptr,"NOTICE %s :Hash Ratio (av. depth): %f %%Full: %f",
  1151.           parv[0], (float)((1.0 * totlink) / (1.0 * used_now)),
  1152.           (float)((1.0 * used_now) / (1.0 * size)));
  1153.     sendto_one(sptr,"NOTICE %s :Deepest Link: %d Links: %d",
  1154.            parv[0], deeplink, deepest);
  1155.     if (!used)
  1156.         used = 1;
  1157.     sendto_one(sptr,"NOTICE %s :Total Hits: %d Unhit: %d Av Hits: %f",
  1158.            parv[0], tothits, size-used,
  1159.            (float)((1.0 * tothits) / (1.0 * used)));
  1160.     sendto_one(sptr,"NOTICE %s :Entry Most Hit: %d Hits: %d",
  1161.            parv[0], mosthit, mosthits);
  1162.     sendto_one(sptr,"NOTICE %s :Client hits %d miss %d",
  1163.            parv[0], clhits, clmiss);
  1164.     sendto_one(sptr,"NOTICE %s :Channel hits %d miss %d",
  1165.            parv[0], chhits, chmiss);
  1166.     return 0;
  1167. #endif /* DEBUGMODE */
  1168. }
  1169.