]>
jfr.im git - irc/quakenet/snircd.git/blob - ircd/hash.c
2 * IRC - Internet Relay Chat, ircd/hash.c
3 * Copyright (C) 1998 Andrea Cocito, completely rewritten version.
4 * Previous version was Copyright (C) 1991 Darren Reed, the concept
5 * of linked lists for each hash bucket and the move-to-head
6 * optimization has been borrowed from there.
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 1, or (at your option)
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, write to the Free Software
20 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
27 #include "ircd_alloc.h"
28 #include "ircd_chattr.h"
30 #include "ircd_reply.h"
31 #include "ircd_string.h"
41 /* #include <assert.h> -- Now using assert in ircd_log.h */
48 * @brief Hash table management.
49 * @version $Id: hash.c,v 1.18 2005/06/27 13:25:51 entrope Exp $
51 * This file used to use some very complicated hash function. Now it
52 * uses CRC-32, but effectively remaps each input byte according to a
53 * table initialized at startup.
56 /** Hash table for clients. */
57 static struct Client
*clientTable
[HASHSIZE
];
58 /** Hash table for channels. */
59 static struct Channel
*channelTable
[HASHSIZE
];
60 /** CRC-32 update table. */
61 static uint32_t crc32hash
[256];
63 /** Initialize the map used by the hash function. */
66 unsigned int ii
, jj
, rand
, poly
;
68 /* First calculate a normal CRC-32 table. */
69 for (ii
= 0, poly
= 0xedb88320; ii
< 256; ii
++)
72 for (jj
= 0; jj
< 8; jj
++)
73 rand
= (rand
& 1) ? poly
^ (rand
>> 1) : rand
>> 1;
77 /* Now reorder the hash table. */
78 for (ii
= 0, rand
= 0; ii
< 256; ii
++)
82 poly
= ii
+ rand
% (256 - ii
);
84 crc32hash
[ii
] = crc32hash
[poly
];
90 /** Output type of hash function. */
91 typedef unsigned int HASHREGS
;
93 /** Calculate hash value for a string.
94 * @param[in] n String to hash.
95 * @return Hash value for string.
97 static HASHREGS
strhash(const char *n
)
99 HASHREGS hash
= crc32hash
[ToLower(*n
++) & 255];
101 hash
= (hash
>> 8) ^ crc32hash
[(hash
^ ToLower(*n
++)) & 255];
102 return hash
% HASHSIZE
;
105 /************************** Externally visible functions ********************/
107 /* Optimization note: in these functions I supposed that the CSE optimization
108 * (Common Subexpression Elimination) does its work decently, this means that
109 * I avoided introducing new variables to do the work myself and I did let
110 * the optimizer play with more free registers, actual tests proved this
111 * solution to be faster than doing things like tmp2=tmp->hnext... and then
112 * use tmp2 myself which would have given less freedom to the optimizer.
115 /** Prepend a client to the appropriate hash bucket.
116 * @param[in] cptr Client to add to hash table.
119 int hAddClient(struct Client
*cptr
)
121 HASHREGS hashv
= strhash(cli_name(cptr
));
123 cli_hnext(cptr
) = clientTable
[hashv
];
124 clientTable
[hashv
] = cptr
;
129 /** Prepend a channel to the appropriate hash bucket.
130 * @param[in] chptr Channel to add to hash table.
133 int hAddChannel(struct Channel
*chptr
)
135 HASHREGS hashv
= strhash(chptr
->chname
);
137 chptr
->hnext
= channelTable
[hashv
];
138 channelTable
[hashv
] = chptr
;
143 /** Remove a client from its hash bucket.
144 * @param[in] cptr Client to remove from hash table.
145 * @return Zero if the client is found and removed, -1 if not found.
147 int hRemClient(struct Client
*cptr
)
149 HASHREGS hashv
= strhash(cli_name(cptr
));
150 struct Client
*tmp
= clientTable
[hashv
];
153 clientTable
[hashv
] = cli_hnext(cptr
);
154 cli_hnext(cptr
) = cptr
;
159 if (cli_hnext(tmp
) == cptr
) {
160 cli_hnext(tmp
) = cli_hnext(cli_hnext(tmp
));
161 cli_hnext(cptr
) = cptr
;
164 tmp
= cli_hnext(tmp
);
169 /** Rename a client in the hash table.
170 * @param[in] cptr Client whose nickname is changing.
171 * @param[in] newname New nickname for client.
174 int hChangeClient(struct Client
*cptr
, const char *newname
)
176 HASHREGS newhash
= strhash(newname
);
181 cli_hnext(cptr
) = clientTable
[newhash
];
182 clientTable
[newhash
] = cptr
;
186 /** Remove a channel from its hash bucket.
187 * @param[in] chptr Channel to remove from hash table.
188 * @return Zero if the channel is found and removed, -1 if not found.
190 int hRemChannel(struct Channel
*chptr
)
192 HASHREGS hashv
= strhash(chptr
->chname
);
193 struct Channel
*tmp
= channelTable
[hashv
];
196 channelTable
[hashv
] = chptr
->hnext
;
197 chptr
->hnext
= chptr
;
202 if (tmp
->hnext
== chptr
) {
203 tmp
->hnext
= tmp
->hnext
->hnext
;
204 chptr
->hnext
= chptr
;
213 /** Find a client by name, filtered by status mask.
214 * If a client is found, it is moved to the top of its hash bucket.
215 * @param[in] name Client name to search for.
216 * @param[in] TMask Bitmask of status bits, any of which are needed to match.
217 * @return Matching client, or NULL if none.
219 struct Client
* hSeekClient(const char *name
, int TMask
)
221 HASHREGS hashv
= strhash(name
);
222 struct Client
*cptr
= clientTable
[hashv
];
225 if (0 == (cli_status(cptr
) & TMask
) || 0 != ircd_strcmp(name
, cli_name(cptr
))) {
227 while (prev
= cptr
, cptr
= cli_hnext(cptr
)) {
228 if ((cli_status(cptr
) & TMask
) && (0 == ircd_strcmp(name
, cli_name(cptr
)))) {
229 cli_hnext(prev
) = cli_hnext(cptr
);
230 cli_hnext(cptr
) = clientTable
[hashv
];
231 clientTable
[hashv
] = cptr
;
240 /** Find a channel by name.
241 * If a channel is found, it is moved to the top of its hash bucket.
242 * @param[in] name Channel name to search for.
243 * @return Matching channel, or NULL if none.
245 struct Channel
* hSeekChannel(const char *name
)
247 HASHREGS hashv
= strhash(name
);
248 struct Channel
*chptr
= channelTable
[hashv
];
251 if (0 != ircd_strcmp(name
, chptr
->chname
)) {
252 struct Channel
* prev
;
253 while (prev
= chptr
, chptr
= chptr
->hnext
) {
254 if (0 == ircd_strcmp(name
, chptr
->chname
)) {
255 prev
->hnext
= chptr
->hnext
;
256 chptr
->hnext
= channelTable
[hashv
];
257 channelTable
[hashv
] = chptr
;
267 /* I will add some useful(?) statistics here one of these days,
268 but not for DEBUGMODE: just to let the admins play with it,
269 coders are able to SIGCORE the server and look into what goes
272 /** Report hash table statistics to a client.
273 * @param[in] cptr Client that sent us this message.
274 * @param[in] sptr Client that originated the message.
275 * @param[in] parc Number of arguments.
276 * @param[in] parv Argument array.
279 int m_hash(struct Client
*cptr
, struct Client
*sptr
, int parc
, char *parv
[])
288 sendcmdto_one(&me
, CMD_NOTICE
, sptr
, "%C :Hash Table Statistics", sptr
);
290 for (i
= 0; i
< HASHSIZE
; ++i
) {
291 if ((cl
= clientTable
[i
])) {
294 for ( ; cl
; cl
= cli_hnext(cl
))
302 sendcmdto_one(&me
, CMD_NOTICE
, sptr
, "%C :Client: entries: %d buckets: %d "
303 "max chain: %d", sptr
, count
, buckets
, max_chain
);
309 for (i
= 0; i
< HASHSIZE
; ++i
) {
310 if ((ch
= channelTable
[i
])) {
313 for ( ; ch
; ch
= ch
->hnext
)
321 sendcmdto_one(&me
, CMD_NOTICE
, sptr
, "%C :Channel: entries: %d buckets: %d "
322 "max chain: %d", sptr
, count
, buckets
, max_chain
);
326 /* Nick jupe utilities, these are in a static hash table with entry/bucket
327 ratio of one, collision shift up and roll in a circular fashion, the
328 lowest 12 bits of the hash value are used, deletion is not supported,
329 only addition, test for existence and cleanup of the table are.. */
331 /** Number of bits in jupe hash value. */
332 #define JUPEHASHBITS 12 /* 4096 entries, 64 nick jupes allowed */
333 /** Size of jupe hash table. */
334 #define JUPEHASHSIZE (1<<JUPEHASHBITS)
335 /** Bitmask to select into jupe hash table. */
336 #define JUPEHASHMASK (JUPEHASHSIZE-1)
337 /** Maximum number of jupes allowed. */
338 #define JUPEMAX (1<<(JUPEHASHBITS-6))
340 /** Hash table for jupes. */
341 static char jupeTable
[JUPEHASHSIZE
][NICKLEN
+ 1]; /* About 40k */
342 /** Count of jupes. */
343 static int jupesCount
;
345 /** Check whether a nickname is juped.
346 * @param[in] nick Nickname to check.
347 * @return Non-zero of the nickname is juped, zero if not.
349 int isNickJuped(const char *nick
)
354 for (pos
= strhash(nick
); (pos
&= JUPEHASHMASK
), jupeTable
[pos
][0]; pos
++) {
355 if (0 == ircd_strcmp(nick
, jupeTable
[pos
]))
359 return 0; /* A bogus pointer is NOT a juped nick, right ? :) */
362 /** Add a comma-separated list of nick jupes.
363 * @param[in] nicks List of nicks to jupe, separated by commas.
364 * @return Zero on success, non-zero on error.
366 int addNickJupes(const char *nicks
)
368 static char temp
[BUFSIZE
+ 1];
375 ircd_strncpy(temp
, nicks
, BUFSIZE
);
376 temp
[BUFSIZE
] = '\0';
378 for (one
= ircd_strtok(&p
, temp
, ","); one
; one
= ircd_strtok(&p
, NULL
, ","))
385 if (!jupeTable
[pos
][0])
387 if (jupesCount
== JUPEMAX
)
388 return 1; /* Error: Jupe table is full ! */
390 ircd_strncpy(jupeTable
[pos
], one
, NICKLEN
);
391 jupeTable
[pos
][NICKLEN
] = '\000'; /* Better safe than sorry :) */
394 if (0 == ircd_strcmp(one
, jupeTable
[pos
]))
403 /** Empty the table of juped nicknames. */
404 void clearNickJupes(void)
408 for (i
= 0; i
< JUPEHASHSIZE
; i
++)
409 jupeTable
[i
][0] = '\000';
412 /** Report all nick jupes to a user.
413 * @param[in] to Client requesting statistics.
414 * @param[in] sd Stats descriptor for request (ignored).
415 * @param[in] param Extra parameter from user (ignored).
418 stats_nickjupes(struct Client
* to
, const struct StatDesc
* sd
, char* param
)
421 for (i
= 0; i
< JUPEHASHSIZE
; i
++)
423 send_reply(to
, RPL_STATSJLINE
, jupeTable
[i
]);
426 /** Send more channels to a client in mid-LIST.
427 * @param[in] cptr Client to send the list to.
429 void list_next_channels(struct Client
*cptr
)
431 struct ListingArgs
*args
;
432 struct Channel
*chptr
;
434 /* Walk consecutive buckets until we hit the end. */
435 for (args
= cli_listing(cptr
); args
->bucket
< HASHSIZE
; args
->bucket
++)
437 /* Send all the matching channels in the bucket. */
438 for (chptr
= channelTable
[args
->bucket
]; chptr
; chptr
= chptr
->hnext
)
440 if (chptr
->users
> args
->min_users
441 && chptr
->users
< args
->max_users
442 && chptr
->creationtime
> args
->min_time
443 && chptr
->creationtime
< args
->max_time
444 && (!args
->wildcard
[0] || (args
->flags
& LISTARG_NEGATEWILDCARD
) ||
445 (!match(args
->wildcard
, chptr
->chname
)))
446 && (!(args
->flags
& LISTARG_NEGATEWILDCARD
) ||
447 match(args
->wildcard
, chptr
->chname
))
448 && (!(args
->flags
& LISTARG_TOPICLIMITS
)
450 && chptr
->topic_time
> args
->min_topic_time
451 && chptr
->topic_time
< args
->max_topic_time
))
452 && ((args
->flags
& LISTARG_SHOWSECRET
)
453 || ShowChannel(cptr
, chptr
)))
455 send_reply(cptr
, RPL_LIST
, chptr
->chname
, chptr
->users
, chptr
->topic
);
458 /* If, at the end of the bucket, client sendq is more than half
460 if (MsgQLength(&cli_sendQ(cptr
)) > cli_max_sendq(cptr
) / 2)
464 /* If we did all buckets, clean the client and send RPL_LISTEND. */
465 if (args
->bucket
>= HASHSIZE
)
467 MyFree(cli_listing(cptr
));
468 cli_listing(cptr
) = NULL
;
469 send_reply(cptr
, RPL_LISTEND
);