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"
42 /* #include <assert.h> -- Now using assert in ircd_log.h */
49 * @brief Hash table management.
50 * @version $Id: hash.c 1841 2007-11-05 03:01:34Z entrope $
52 * This file used to use some very complicated hash function. Now it
53 * uses CRC-32, but effectively remaps each input byte according to a
54 * table initialized at startup.
57 /** Hash table for clients. */
58 static struct Client *clientTable[HASHSIZE];
59 /** Hash table for channels. */
60 static struct Channel *channelTable[HASHSIZE];
61 /** CRC-32 update table. */
62 static uint32_t crc32hash[256];
64 /** Initialize the map used by the hash function. */
67 unsigned int ii, jj, rand, poly;
69 /* First calculate a normal CRC-32 table. */
70 for (ii = 0, poly = 0xedb88320; ii < 256; ii++)
73 for (jj = 0; jj < 8; jj++)
74 rand = (rand & 1) ? poly ^ (rand >> 1) : rand >> 1;
78 /* Now reorder the hash table. */
79 for (ii = 0, rand = 0; ii < 256; ii++)
83 poly = ii + rand % (256 - ii);
85 crc32hash[ii] = crc32hash[poly];
91 /** Output type of hash function. */
92 typedef unsigned int HASHREGS;
94 /** Calculate hash value for a string.
95 * @param[in] n String to hash.
96 * @return Hash value for string.
98 static HASHREGS strhash(const char *n)
100 HASHREGS hash = crc32hash[ToLower(*n++) & 255];
102 hash = (hash >> 8) ^ crc32hash[(hash ^ ToLower(*n++)) & 255];
103 return hash % HASHSIZE;
106 /************************** Externally visible functions ********************/
108 /* Optimization note: in these functions I supposed that the CSE optimization
109 * (Common Subexpression Elimination) does its work decently, this means that
110 * I avoided introducing new variables to do the work myself and I did let
111 * the optimizer play with more free registers, actual tests proved this
112 * solution to be faster than doing things like tmp2=tmp->hnext... and then
113 * use tmp2 myself which would have given less freedom to the optimizer.
116 /** Prepend a client to the appropriate hash bucket.
117 * @param[in] cptr Client to add to hash table.
120 int hAddClient(struct Client *cptr)
122 HASHREGS hashv = strhash(cli_name(cptr));
124 cli_hnext(cptr) = clientTable[hashv];
125 clientTable[hashv] = cptr;
130 /** Prepend a channel to the appropriate hash bucket.
131 * @param[in] chptr Channel to add to hash table.
134 int hAddChannel(struct Channel *chptr)
136 HASHREGS hashv = strhash(chptr->chname);
138 chptr->hnext = channelTable[hashv];
139 channelTable[hashv] = chptr;
144 /** Remove a client from its hash bucket.
145 * @param[in] cptr Client to remove from hash table.
146 * @return Zero if the client is found and removed, -1 if not found.
148 int hRemClient(struct Client *cptr)
150 HASHREGS hashv = strhash(cli_name(cptr));
151 struct Client *tmp = clientTable[hashv];
154 clientTable[hashv] = cli_hnext(cptr);
155 cli_hnext(cptr) = cptr;
160 if (cli_hnext(tmp) == cptr) {
161 cli_hnext(tmp) = cli_hnext(cli_hnext(tmp));
162 cli_hnext(cptr) = cptr;
165 tmp = cli_hnext(tmp);
170 /** Rename a client in the hash table.
171 * @param[in] cptr Client whose nickname is changing.
172 * @param[in] newname New nickname for client.
175 int hChangeClient(struct Client *cptr, const char *newname)
177 HASHREGS newhash = strhash(newname);
182 cli_hnext(cptr) = clientTable[newhash];
183 clientTable[newhash] = cptr;
187 /** Remove a channel from its hash bucket.
188 * @param[in] chptr Channel to remove from hash table.
189 * @return Zero if the channel is found and removed, -1 if not found.
191 int hRemChannel(struct Channel *chptr)
193 HASHREGS hashv = strhash(chptr->chname);
194 struct Channel *tmp = channelTable[hashv];
197 channelTable[hashv] = chptr->hnext;
198 chptr->hnext = chptr;
203 if (tmp->hnext == chptr) {
204 tmp->hnext = tmp->hnext->hnext;
205 chptr->hnext = chptr;
214 /** Find a client by name, filtered by status mask.
215 * If a client is found, it is moved to the top of its hash bucket.
216 * @param[in] name Client name to search for.
217 * @param[in] TMask Bitmask of status bits, any of which are needed to match.
218 * @return Matching client, or NULL if none.
220 struct Client* hSeekClient(const char *name, int TMask)
222 HASHREGS hashv = strhash(name);
223 struct Client *cptr = clientTable[hashv];
226 if (0 == (cli_status(cptr) & TMask) || 0 != ircd_strcmp(name, cli_name(cptr))) {
228 while (prev = cptr, cptr = cli_hnext(cptr)) {
229 if ((cli_status(cptr) & TMask) && (0 == ircd_strcmp(name, cli_name(cptr)))) {
230 cli_hnext(prev) = cli_hnext(cptr);
231 cli_hnext(cptr) = clientTable[hashv];
232 clientTable[hashv] = cptr;
241 /** Find a channel by name.
242 * If a channel is found, it is moved to the top of its hash bucket.
243 * @param[in] name Channel name to search for.
244 * @return Matching channel, or NULL if none.
246 struct Channel* hSeekChannel(const char *name)
248 HASHREGS hashv = strhash(name);
249 struct Channel *chptr = channelTable[hashv];
252 if (0 != ircd_strcmp(name, chptr->chname)) {
253 struct Channel* prev;
254 while (prev = chptr, chptr = chptr->hnext) {
255 if (0 == ircd_strcmp(name, chptr->chname)) {
256 prev->hnext = chptr->hnext;
257 chptr->hnext = channelTable[hashv];
258 channelTable[hashv] = chptr;
268 /* I will add some useful(?) statistics here one of these days,
269 but not for DEBUGMODE: just to let the admins play with it,
270 coders are able to SIGCORE the server and look into what goes
273 /** Report hash table statistics to a client.
274 * @param[in] cptr Client that sent us this message.
275 * @param[in] sptr Client that originated the message.
276 * @param[in] parc Number of arguments.
277 * @param[in] parv Argument array.
280 int m_hash(struct Client *cptr, struct Client *sptr, int parc, char *parv[])
289 sendcmdto_one(&me, CMD_NOTICE, sptr, "%C :Hash Table Statistics", sptr);
291 for (i = 0; i < HASHSIZE; ++i) {
292 if ((cl = clientTable[i])) {
295 for ( ; cl; cl = cli_hnext(cl))
303 sendcmdto_one(&me, CMD_NOTICE, sptr, "%C :Client: entries: %d buckets: %d "
304 "max chain: %d", sptr, count, buckets, max_chain);
310 for (i = 0; i < HASHSIZE; ++i) {
311 if ((ch = channelTable[i])) {
314 for ( ; ch; ch = ch->hnext)
322 sendcmdto_one(&me, CMD_NOTICE, sptr, "%C :Channel: entries: %d buckets: %d "
323 "max chain: %d", sptr, count, buckets, max_chain);
327 /* Nick jupe utilities, these are in a static hash table with entry/bucket
328 ratio of one, collision shift up and roll in a circular fashion, the
329 lowest 12 bits of the hash value are used, deletion is not supported,
330 only addition, test for existence and cleanup of the table are.. */
332 /** Number of bits in jupe hash value. */
333 #define JUPEHASHBITS 12 /* 4096 entries, 64 nick jupes allowed */
334 /** Size of jupe hash table. */
335 #define JUPEHASHSIZE (1<<JUPEHASHBITS)
336 /** Bitmask to select into jupe hash table. */
337 #define JUPEHASHMASK (JUPEHASHSIZE-1)
338 /** Maximum number of jupes allowed. */
339 #define JUPEMAX (1<<(JUPEHASHBITS-6))
341 /** Hash table for jupes. */
342 static char jupeTable[JUPEHASHSIZE][NICKLEN + 1]; /* About 40k */
343 /** Count of jupes. */
344 static int jupesCount;
346 /** Check whether a nickname is juped.
347 * @param[in] nick Nickname to check.
348 * @return Non-zero of the nickname is juped, zero if not.
350 int isNickJuped(const char *nick)
355 //for (pos = strhash(nick); (pos &= JUPEHASHMASK), jupeTable[pos][0]; pos++) {
356 for (pos = 0; pos < JUPEHASHSIZE; pos++) {
357 //if (0 == ircd_strcmp(nick, jupeTable[pos]))
358 //Debug((DEBUG_DEBUG, "NickJupe match: %s %s %i",jupeTable[pos], nick, match(jupeTable[pos], nick)));
359 if (0 == match(jupeTable[pos], nick))
363 return 0; /* A bogus pointer is NOT a juped nick, right ? :) */
366 /** Add a comma-separated list of nick jupes.
367 * @param[in] nicks List of nicks to jupe, separated by commas.
368 * @return Zero on success, non-zero on error.
370 int addNickJupes(const char *nicks)
372 static char temp[BUFSIZE + 1];
379 ircd_strncpy(temp, nicks, BUFSIZE);
380 temp[BUFSIZE] = '\0';
382 for (one = ircd_strtok(&p, temp, ","); one; one = ircd_strtok(&p, NULL, ","))
389 if (!jupeTable[pos][0])
391 if (jupesCount == JUPEMAX)
392 return 1; /* Error: Jupe table is full ! */
394 ircd_strncpy(jupeTable[pos], one, NICKLEN);
395 jupeTable[pos][NICKLEN] = '\000'; /* Better safe than sorry :) */
398 if (0 == ircd_strcmp(one, jupeTable[pos]))
407 /** Empty the table of juped nicknames. */
408 void clearNickJupes(void)
412 for (i = 0; i < JUPEHASHSIZE; i++)
413 jupeTable[i][0] = '\000';
416 /** Report all nick jupes to a user.
417 * @param[in] to Client requesting statistics.
418 * @param[in] sd Stats descriptor for request (ignored).
419 * @param[in] param Extra parameter from user (ignored).
422 stats_nickjupes(struct Client* to, const struct StatDesc* sd, char* param)
425 for (i = 0; i < JUPEHASHSIZE; i++)
427 send_reply(to, RPL_STATSJLINE, jupeTable[i]);
430 /** Send more channels to a client in mid-LIST.
431 * @param[in] cptr Client to send the list to.
433 void list_next_channels(struct Client *cptr)
435 struct ListingArgs *args;
436 struct Channel *chptr;
438 /* Walk consecutive buckets until we hit the end. */
439 for (args = cli_listing(cptr); args->bucket < HASHSIZE; args->bucket++)
441 /* Send all the matching channels in the bucket. */
442 for (chptr = channelTable[args->bucket]; chptr; chptr = chptr->hnext)
444 if (chptr->users > args->min_users
445 && chptr->users < args->max_users
446 && chptr->creationtime > args->min_time
447 && chptr->creationtime < args->max_time
448 && (!args->wildcard[0] || (args->flags & LISTARG_NEGATEWILDCARD) ||
449 (!match(args->wildcard, chptr->chname)))
450 && (!(args->flags & LISTARG_NEGATEWILDCARD) ||
451 match(args->wildcard, chptr->chname))
452 && (!(args->flags & LISTARG_TOPICLIMITS)
454 && chptr->topic_time > args->min_topic_time
455 && chptr->topic_time < args->max_topic_time))
456 && ((args->flags & LISTARG_SHOWSECRET)
457 || ShowChannel(cptr, chptr)))
459 if (args->flags & LISTARG_SHOWMODES) {
460 char modebuf[MODEBUFLEN];
461 char parabuf[MODEBUFLEN];
463 modebuf[0] = modebuf[1] = parabuf[0] = '\0';
464 channel_modes(cptr, modebuf, parabuf, sizeof(parabuf), chptr, NULL);
465 send_reply(cptr, RPL_LIST | SND_EXPLICIT, "%s %u %s %s :%s",
466 chptr->chname, chptr->users, modebuf, parabuf, chptr->topic);
468 send_reply(cptr, RPL_LIST, chptr->chname, chptr->users, chptr->topic);
472 /* If, at the end of the bucket, client sendq is more than half
474 if (MsgQLength(&cli_sendQ(cptr)) > cli_max_sendq(cptr) / 2)
478 /* If we did all buckets, clean the client and send RPL_LISTEND. */
479 if (args->bucket >= HASHSIZE)
481 MyFree(cli_listing(cptr));
482 cli_listing(cptr) = NULL;
483 send_reply(cptr, RPL_LISTEND);