channel/chanuserhash.c

   1 /* chanuserhash.c */
   2
   3 #include "channel.h"
   4 #include "../server/server.h"
   5 #include "../nick/nick.h"
   6 #include "../lib/irc_string.h"
   7 #include "../irc/irc_config.h"
   8 #include "../parser/parser.h"
   9 #include "../irc/irc.h"
  10 #include "../lib/base64.h"
  11
  12 /*
  13  * rehashchannel:
  14  *  Make the channel hash a notch larger, to accomodate more users
  15  */
  16
  17 void rehashchannel(channel *cp) {
  18   int i;
  19   chanuserhash *newhash;
  20   int newhashsize;
  21
  22   /* Pick a new hash size.  If we're not making good use of the current hash,
  23    * just increase size slightly, otherwise multiply size by 1.5 */
  24
  25   if (cp->users->totalusers*1.6 < cp->users->hashsize) {
  26     newhashsize=cp->users->hashsize+1;
  27   } else {
  28     newhashsize= ((int)cp->users->hashsize*1.5);
  29     newhashsize |= 1;
  30     if (newhashsize<=cp->users->hashsize) {
  31       newhashsize++;
  32     }
  33   }
  34
  35 rehash:
  36   newhash=newchanuserhash(newhashsize);
  37   for (i=0;i<cp->users->hashsize;i++) {
  38     if (cp->users->content[i]!=nouser) {
  39       if (addnumerictochanuserhash(newhash,cp->users->content[i])) {
  40         /* It didn't fit.  It's clearly not our day :(
  41          * Increase the newhashsize by one and hope for a better fit
  42          * If you whine about the goto I'll just point out that the
  43          * other alternative was exit(1) :) */
  44         newhashsize+=2;
  45         freechanuserhash(newhash);
  46         goto rehash;
  47       }
  48     }
  49   }
  50
  51   /* If we got to here it means we crammed all the old stuff into the new hash */
  52   freechanuserhash(cp->users);
  53   cp->users=newhash;
  54 }
  55
  56 /*
  57  * addnumerictochanuserhash:
  58  *  Try to fit the given numeric into the channel user hash
  59  *
  60  * Returns 0 if the numeric went in, 1 if not.
  61  */
  62
  63 int addnumerictochanuserhash(chanuserhash *cuh, long numeric) {
  64   int i,j,hash,hash2;
  65
  66   /* Double hashing scheme; use the next higher bits of the numeric
  67    * for the second hash (increment)
  68    *
  69    * TODO: discover if there is a better alternative
  70    * to the fixed max search depth value */
  71
  72   hash=(numeric&CU_NUMERICMASK);
  73   hash2=(hash/(cuh->hashsize))%(cuh->hashsize);
  74   hash=hash%(cuh->hashsize);
  75
  76   if (hash2==0) {
  77     hash2=1;
  78   }
  79
  80   for(i=0,j=hash;i<CUHASH_DEPTH && (j!=hash || i==0);i++,j=(j+hash2)%(cuh->hashsize)) {
  81     if (cuh->content[j]==nouser) {
  82       cuh->content[j]=numeric;
  83       cuh->totalusers++;
  84       return 0;
  85     }
  86   }
  87
  88   /* Eeep, we didn't find a space */
  89   return 1;
  90 }
  91
  92 unsigned long *getnumerichandlefromchanhash(chanuserhash *cuh, long numeric) {
  93   int i, j, hash, hash2;
  94
  95   hash=(numeric&CU_NUMERICMASK);
  96   hash2=(hash/(cuh->hashsize))%(cuh->hashsize);
  97   hash=hash%(cuh->hashsize);
  98
  99   if (hash2==0) {
 100     hash2=1;
 101   }
 102
 103   for (i=0,j=hash;i<CUHASH_DEPTH && (j!=hash || i==0);i++,j=(j+hash2)%(cuh->hashsize)) {
 104     if ((cuh->content[j]&CU_NUMERICMASK)==(numeric&CU_NUMERICMASK)) {
 105       return &(cuh->content[j]);
 106     }
 107   }
 108
 109   return NULL;
 110 }