]>
Commit | Line | Data |
---|---|---|
c86edd1d Q |
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 | } |