/************************************************************************
* IRC - Internet Relay Chat, ircd/hash.c
* Copyright (C) 1991 Darren Reed
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 1, or (at your option)
* any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
#ifndef lint
static char rcsid[] = "@(#)$Id: hash.c,v 1.15 2004/02/27 14:05:22 skold Exp $";
#endif
#include "os.h"
#include "s_defines.h"
#define HASH_C
#include "s_externs.h"
#undef HASH_C
static aHashEntry *clientTable = NULL;
static aHashEntry *channelTable = NULL;
static aHashEntry *serverTable = NULL;
static unsigned int *hashtab = NULL;
static int clhits = 0, clmiss = 0, clsize = 0;
static int chhits = 0, chmiss = 0, chsize = 0;
static int svsize = 0;
int _HASHSIZE = 0;
int _CHANNELHASHSIZE = 0;
int _SERVERSIZE = 0;
#ifdef RUSNET_IRCD
static aCollMap *collmap = NULL;
static unsigned int collnum = 0, collsize = 0;
static unsigned long crc_table[256];
static char b64enc_table [64] = {
'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P',
'Q','R','S','T','U','V','W','X','Y','Z','a','b','c','d','e','f',
'g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v',
'w','x','y','z','0','1','2','3','4','5','6','7','8','9','_','-'
/*
* really there must be '+' and '/' latest two
* but they're inacceptable in IRC -erra
*/
};
/*-----------------------------------------------------------*/
/* generate the crc table. Must be called before calculating the crc value */
/*
* I add it here for the soft nick collision handling algorithm -erra
*/
void gen_crc32table(void) /* build the crc table */
{
register unsigned long crc, poly;
register int i, j;
poly = 0xEDB88320L;
for (i = 0; i < 256; i++)
{
crc = i;
for (j = 8; j > 0; j--)
{
if (crc & 1)
crc = (crc >> 1) ^ poly;
else
crc >>= 1;
}
crc_table[i] = crc;
}
}
unsigned long gen_crc(char *c) /* calculate the crc32 value */
{
register unsigned long crc = 0xFFFFFFFF;
char *ch;
for (ch = c; *ch; ch++)
crc = (crc >> 8) ^ crc_table[ (crc ^ *ch) & 0xFF ];
return (crc ^ 0xFFFFFFFF);
}
char * b64enc(unsigned long id)
{
register union {
unsigned long l;
char p[4];
} crc;
int j;
static char b64[6];
crc.l = id;
b64[0] = (crc.p[0] & 0xFC) >> 2;
b64[1] = (crc.p[0] & 0x03) << 4 | (crc.p[1] & 0xF0) >> 4;
b64[2] = (crc.p[1] & 0x0F) << 2 | (crc.p[2] & 0xC0) >> 6;
b64[3] = crc.p[2] & 0x3F;
/* Cut off two bits as non-significant
b64[4] = (crc.p[3] & 0xFC) >> 2;
b64[5] = (crc.p[3] & 0x03) << 4;
*/
b64[4] = crc.p[3] & 0x3F;
for (j = 0; j < 5; j++)
b64[j] = b64enc_table[ b64[j] ];
b64[5] = '\0'; /* null-terminating result string */
return b64;
}
/*
* Collision handling thru maps. This is solely experimental -erra
*/
static void grow_collmap()
{
collmap = (aCollMap *)MyRealloc((char *)collmap, sizeof(aCollMap) *
(collsize + COLLMAPCHUNK));
bzero(collmap + collsize, sizeof(aCollMap) * COLLMAPCHUNK);
Debug((DEBUG_DEBUG, "Collision map from: %d to %d", collsize,
collsize + COLLMAPCHUNK));
sendto_flag(SCH_HASH, "Collision map from %d to %d", collsize,
collsize + COLLMAPCHUNK);
collsize += COLLMAPCHUNK;
}
static void shrink_collmap()
{
if (!collnum)
{
MyFree(collmap);
collmap = NULL;
collsize = 0;
Debug((DEBUG_DEBUG, "Collision map is empty"));
sendto_flag(SCH_HASH, "Collision map is empty");
}
else if (collsize - collnum > COLLMAPCHUNK)
{
collsize -= COLLMAPCHUNK;
collmap = (aCollMap *)MyRealloc((char *)collmap,
sizeof(aCollMap) * collsize);
Debug((DEBUG_DEBUG, "Collision map from: %d to %d, filled %d",
collsize + COLLMAPCHUNK, collsize, collnum));
sendto_flag(SCH_HASH, "Collision map from %d to %d, filled %d",
collsize + COLLMAPCHUNK, collsize, collnum);
}
}
void add_to_collision_map(const char *nick, const char *collnick,
unsigned long id)
{
/*
** In the perfect world we would never need this because adding
** existing should never happen. But running in the "collmap-v1"
** environment can easily cause this.
*/
int i;
for (i = 0; i < collnum; i++)
if (!strcmp(collmap[i].collnick, collnick) &&
!strcmp(collmap[i].nick, nick))
{
sendto_flag(SCH_HASH, "Trying to add existing collision: %s %s %d",
nick, collnick, id);
collmap[i].tstamp = timeofday;
return;
}
if (collnum == collsize)
grow_collmap();
strcpy(collmap[collnum].nick, nick);
strcpy(collmap[collnum].collnick, collnick);
collmap[collnum].id = id;
collmap[collnum].tstamp = timeofday;
collnum++;
#ifdef DEBUGMODE
Debug((DEBUG_DEBUG, "Collision map add: %s %s %d", nick, collnick, id));
#endif
sendto_flag(SCH_HASH, "Collision map add: %s %s %d", nick, collnick, id);
}
void del_from_collision_map(const char *nick, unsigned long id)
{
int i;
if (!nick || !collnum)
return;
for (i = 0; i < collnum; i++)
if (collmap[i].id == id &&
(!strcmp(collmap[i].collnick, nick)))
{ /* Will never allow gaps in the collmap -Ulysses */
collnum--;
if (i < collnum)
memcpy(collmap + i, collmap + collnum,
sizeof(aCollMap));
#ifdef DEBUGMODE
Debug((DEBUG_DEBUG, "Collision map del: %s", nick));
#endif
sendto_flag(SCH_HASH, "Collision map del: %s", nick);
shrink_collmap();
return;
}
}
void expire_collision_map(time_t time)
{
int i;
time -= COLLMAP_HOLDTIME;
for (i = 0; i < collnum; i++)
if (collmap[i].tstamp < time)
{
aClient *acptr;
#ifdef DEBUGMODE
Debug((DEBUG_DEBUG, "Collision map expired: %s -> %s",
collmap[i].nick,collmap[i].collnick));
#endif
if ((acptr = find_client(collmap[i].collnick, NULL)))
{ /* we need to kill him to stop the garbage */
sendto_flag(SCH_HASH, "Collision map expired: %s -> %s!%s@%s %d%s",
collmap[i].nick, acptr->name, acptr->user->username,
acptr->sockhost, collmap[i].id,
acptr->flags & FLAGS_COLLMAP ? "" : " FLAGS_COLLMAP is not set");
sendto_flag(SCH_KILL, "Stalled collision %s -> %s!%s@%s",
collmap[i].nick,
acptr->name, acptr->user->username,
acptr->sockhost);
ircstp->is_kill++;
/**
** Kill mapped nick everywhere. We don't need
** to kill the original nick backwards since
** we've already sent the collided nick there
** so it's path must be changed already. -erra
**/
sendto_serv_butone(NULL, ":%s KILL %s :%s "
"(Stalled collision %s!%s@%s[%s] -> %s)", ME,
collmap[i].collnick, ME,
acptr->name,
acptr->user->username,
acptr->sockhost,
acptr->from->name,
collmap[i].collnick);
acptr->flags |= FLAGS_KILLED|FLAGS_COLLMAP;
(void)exit_client(NULL, acptr, &me,
"Stalled collision");
}
else
{
sendto_flag(SCH_HASH, "Collision map expired: %s -> %s %d",
collmap[i].nick, collmap[i].collnick, collmap[i].id);
collnum--;
if (i < collnum)
memcpy(collmap + i, collmap + collnum,
sizeof(aCollMap));
shrink_collmap();
}
} else
{
sendto_flag(SCH_HASH, "Collision map entry: %s -> %s %d",
collmap[i].nick, collmap[i].collnick, collmap[i].id);
}
}
char * find_collision(const char *nick, unsigned long id)
{
int i;
for (i = 0; i < collnum; i++)
if (collmap[i].id == id &&
!strcmp(collmap[i].nick, nick))
{
sendto_flag(SCH_HASH, "Found collision: %s -> %s %d",
nick, collmap[i].collnick, collmap[i].id);
return collmap[i].collnick;
}
return NULL;
}
#endif
/*
* Hashing.
*
* The server uses a chained hash table to provide quick and efficient
* hash table mantainence (providing the hash function works evenly over
* the input range). The hash table is thus not susceptible to problems
* of filling all the buckets or the need to rehash.
* It is expected that the hash table would look somehting like this
* during use:
* +-----+ +-----+ +-----+ +-----+
* ---| 224 |----| 225 |----| 226 |---| 227 |---
* +-----+ +-----+ +-----+ +-----+
* | | |
* +-----+ +-----+ +-----+
* | A | | C | | D |
* +-----+ +-----+ +-----+
* |
* +-----+
* | B |
* +-----+
*
* A - GOPbot, B - chang, C - hanuaway, D - *.mu.OZ.AU
*
* The order shown above is just one instant of the server.
*/
/*
* hash_nick_name
*
* this function must be *quick*. Thus there should be no multiplication
* or division or modulus in the inner loop. subtraction and other bit
* operations allowed.
*/
static u_int hash_nick_name(nname, store)
char *nname;
int *store;
{
Reg u_char *name = (u_char *)nname;
Reg u_char ch;
Reg u_int hash = 1;
for (; (ch = *name); name++)
{
hash <<= 4;
hash += hashtab[ch];
}
/*
if (hash < 0)
hash = -hash;
*/
if (store)
*store = hash;
hash %= _HASHSIZE;
return (hash);
}
/*
* hash_channel_name
*
* calculate a hash value on at most the first 30 characters of the channel
* name. Most names are short than this or dissimilar in this range. There
* is little or no point hashing on a full channel name which maybe 255 chars
* long.
*/
static u_int hash_channel_name(hname, store, shortname)
char *hname, shortname;
int *store;
{
Reg u_char *name = (u_char *)hname;
Reg u_char ch;
Reg int i = 30;
Reg u_int hash = 5;
if (*name == '!' && shortname == 0)
name += 1 + CHIDLEN;
for (; (ch = *name) && --i; name++)
{
hash <<= 4;
hash += hashtab[ch] + (i << 1);
}
if (store)
*store = hash;
hash %= _CHANNELHASHSIZE;
return (hash);
}
/* bigger prime
*
* given a positive integer, return a prime number that's larger
*
* 13feb94 gbl
*/
static int bigger_prime(size)
int size;
{
int trial, failure, sq;
if (size < 0)
return -1;
if (size < 4)
return size;
if (size % 2 == 0) /* Make sure it's odd because... */
size++;
for ( ; ; size += 2) /* ...no point checking even numbers - Core */
{
failure = 0;
sq = (int)sqrt((double)size);
for (trial = 3; trial <= sq ; trial += 2)
{
if ((size % trial) == 0)
{
failure = 1;
break;
}
}
if (!failure)
return size;
}
/* return -1; */ /* Never reached */
}
/*
* clear_*_hash_table
*
* Nullify the hashtable and its contents so it is completely empty.
*/
static void clear_client_hash_table(size)
int size;
{
_HASHSIZE = bigger_prime(size);
clhits = 0;
clmiss = 0;
clsize = 0;
if (!clientTable)
clientTable = (aHashEntry *)MyMalloc(_HASHSIZE *
sizeof(aHashEntry));
bzero((char *)clientTable, sizeof(aHashEntry) * _HASHSIZE);
Debug((DEBUG_DEBUG, "Client Hash Table Init: %d (%d)",
_HASHSIZE, size));
}
static void clear_channel_hash_table(size)
int size;
{
_CHANNELHASHSIZE = bigger_prime(size);
chmiss = 0;
chhits = 0;
chsize = 0;
if (!channelTable)
channelTable = (aHashEntry *)MyMalloc(_CHANNELHASHSIZE *
sizeof(aHashEntry));
bzero((char *)channelTable, sizeof(aHashEntry) * _CHANNELHASHSIZE);
Debug((DEBUG_DEBUG, "Channel Hash Table Init: %d (%d)",
_CHANNELHASHSIZE, size));
}
static void clear_server_hash_table(size)
int size;
{
_SERVERSIZE = bigger_prime(size);
svsize = 0;
if (!serverTable)
serverTable = (aHashEntry *)MyMalloc(_SERVERSIZE *
sizeof(aHashEntry));
bzero((char *)serverTable, sizeof(aHashEntry) * _SERVERSIZE);
Debug((DEBUG_DEBUG, "Server Hash Table Init: %d (%d)",
_SERVERSIZE, size));
}
void inithashtables()
{
Reg int i;
clear_client_hash_table((_HASHSIZE) ? _HASHSIZE : HASHSIZE);
clear_channel_hash_table((_CHANNELHASHSIZE) ? _CHANNELHASHSIZE
: CHANNELHASHSIZE);
clear_server_hash_table((_SERVERSIZE) ? _SERVERSIZE : SERVERSIZE);
/*
* Moved multiplication out from the hashfunctions and into
* a pre-generated lookup table. Should save some CPU usage
* even on machines with a fast mathprocessor. -- Core
*/
hashtab = (u_int *) MyMalloc(256 * sizeof(u_int));
for (i = 0; i < 256; i++)
hashtab[i] = tolower((u_char)i) * 109;
}
static void bigger_hash_table(size, table, new)
int *size;
aHashEntry *table;
int new;
{
Reg aClient *cptr;
Reg aChannel *chptr;
Reg aServer *sptr;
aHashEntry *otab = table;
int osize = *size;
while (!new || new <= osize)
if (!new)
{
new = osize;
new = bigger_prime(1 + (int)((float)new * 1.30));
}
else
new = bigger_prime(1 + new);
Debug((DEBUG_NOTICE, "bigger_h_table(*%#x = %d,%#x,%d)",
size, osize, table, new));
*size = new;
ircd_writetune(tunefile);
table = (aHashEntry *)MyMalloc(sizeof(*table) * new);
bzero((char *)table, sizeof(*table) * new);
if (otab == channelTable)
{
Debug((DEBUG_ERROR, "Channel Hash Table from %d to %d (%d)",
osize, new, chsize));
sendto_flag(SCH_HASH, "Channel Hash Table from %d to %d (%d)",
osize, new, chsize);
chmiss = 0;
chhits = 0;
chsize = 0;
channelTable = table;
for (chptr = channel; chptr; chptr = chptr->nextch)
(void)add_to_channel_hash_table(chptr->chname, chptr);
MyFree(otab);
}
else if (otab == clientTable)
{
int i;
aClient *next;
Debug((DEBUG_ERROR, "Client Hash Table from %d to %d (%d)",
osize, new, clsize));
sendto_flag(SCH_HASH, "Client Hash Table from %d to %d (%d)",
osize, new, clsize);
clmiss = 0;
clhits = 0;
clsize = 0;
clientTable = table;
for (i = 0; i < osize; i++)
{
for (cptr = (aClient *)otab[i].list; cptr;
cptr = next)
{
next = cptr->hnext;
(void)add_to_client_hash_table(cptr->name,
cptr);
}
}
MyFree(otab);
}
else if (otab == serverTable)
{
Debug((DEBUG_ERROR, "Server Hash Table from %d to %d (%d)",
osize, new, svsize));
sendto_flag(SCH_HASH, "Server Hash Table from %d to %d (%d)",
osize, new, svsize);
svsize = 0;
serverTable = table;
for (sptr = svrtop; sptr; sptr = sptr->nexts)
(void)add_to_server_hash_table(sptr, sptr->bcptr);
MyFree(otab);
}
return;
}
/*
* add_to_client_hash_table
*/
int add_to_client_hash_table(name, cptr)
char *name;
aClient *cptr;
{
Reg u_int hashv;
hashv = hash_nick_name(name, &cptr->hashv);
cptr->hnext = (aClient *)clientTable[hashv].list;
clientTable[hashv].list = (void *)cptr;
clientTable[hashv].links++;
clientTable[hashv].hits++;
clsize++;
if (clsize > _HASHSIZE)
bigger_hash_table(&_HASHSIZE, clientTable, 0);
return 0;
}
/*
* add_to_channel_hash_table
*/
int add_to_channel_hash_table(name, chptr)
char *name;
aChannel *chptr;
{
Reg u_int hashv;
hashv = hash_channel_name(name, &chptr->hashv, 0);
chptr->hnextch = (aChannel *)channelTable[hashv].list;
channelTable[hashv].list = (void *)chptr;
channelTable[hashv].links++;
channelTable[hashv].hits++;
chsize++;
if (chsize > _CHANNELHASHSIZE)
bigger_hash_table(&_CHANNELHASHSIZE, channelTable, 0);
return 0;
}
/*
* add_to_server_hash_table
*/
int add_to_server_hash_table(sptr, cptr)
aServer *sptr;
aClient *cptr;
{
Reg u_int hashv;
Debug((DEBUG_DEBUG, "Add %s token %d/%d/%s cptr %#x to server table",
sptr->bcptr->name, sptr->stok, sptr->ltok, sptr->tok, cptr));
hashv = sptr->stok * 15053;
hashv %= _SERVERSIZE;
sptr->shnext = (aServer *)serverTable[hashv].list;
serverTable[hashv].list = (void *)sptr;
serverTable[hashv].links++;
serverTable[hashv].hits++;
svsize++;
if (svsize > _SERVERSIZE)
bigger_hash_table(&_SERVERSIZE, serverTable, 0);
return 0;
}
/*
* del_from_client_hash_table
*/
int del_from_client_hash_table(name, cptr)
char *name;
aClient *cptr;
{
Reg aClient *tmp, *prev = NULL;
Reg u_int hashv;
hashv = cptr->hashv;
hashv %= _HASHSIZE;
for (tmp = (aClient *)clientTable[hashv].list; tmp; tmp = tmp->hnext)
{
if (tmp == cptr)
{
if (prev)
prev->hnext = tmp->hnext;
else
clientTable[hashv].list = (void *)tmp->hnext;
tmp->hnext = NULL;
if (clientTable[hashv].links > 0)
{
clientTable[hashv].links--;
clsize--;
return 1;
}
else
{
sendto_flag(SCH_ERROR, "cl-hash table failure");
Debug((DEBUG_ERROR, "cl-hash table failure"));
/*
* Should never actually return from here and
* if we do it is an error/inconsistency in the
* hash table.
*/
return -1;
}
}
prev = tmp;
}
return 0;
}
/*
* del_from_channel_hash_table
*/
int del_from_channel_hash_table(name, chptr)
char *name;
aChannel *chptr;
{
Reg aChannel *tmp, *prev = NULL;
Reg u_int hashv;
hashv = chptr->hashv;
hashv %= _CHANNELHASHSIZE;
for (tmp = (aChannel *)channelTable[hashv].list; tmp;
tmp = tmp->hnextch)
{
if (tmp == chptr)
{
if (prev)
prev->hnextch = tmp->hnextch;
else
channelTable[hashv].list=(void *)tmp->hnextch;
tmp->hnextch = NULL;
if (channelTable[hashv].links > 0)
{
channelTable[hashv].links--;
chsize--;
return 1;
}
else
{
sendto_flag(SCH_ERROR, "ch-hash table failure");
return -1;
}
}
prev = tmp;
}
return 0;
}
/*
* del_from_server_hash_table
*/
int del_from_server_hash_table(sptr, cptr)
aServer *sptr;
aClient *cptr;
{
Reg aServer *tmp, *prev = NULL;
Reg u_int hashv;
hashv = sptr->stok * 15053;
hashv %= _SERVERSIZE;
for (tmp = (aServer *)serverTable[hashv].list; tmp; tmp = tmp->shnext)
{
if (tmp == sptr)
{
if (prev)
prev->shnext = tmp->shnext;
else
serverTable[hashv].list = (void *)tmp->shnext;
tmp->shnext = NULL;
if (serverTable[hashv].links > 0)
{
serverTable[hashv].links--;
svsize--;
return 1;
}
else
{
sendto_flag(SCH_ERROR, "se-hash table failure");
return -1;
}
}
prev = tmp;
}
return 0;
}
/*
* hash_find_client
*/
aClient *hash_find_client(name, cptr)
char *name;
aClient *cptr;
{
Reg aClient *tmp;
Reg aClient *prv = NULL;
Reg aHashEntry *tmp3;
u_int hashv, hv;
hashv = hash_nick_name(name, &hv);
tmp3 = &clientTable[hashv];
/*
* Got the bucket, now search the chain.
*/
for (tmp = (aClient *)tmp3->list; tmp; prv = tmp, tmp = tmp->hnext)
if (hv == tmp->hashv && strcasecmp(name, tmp->name) == 0)
{
clhits++;
/*
* If the member of the hashtable we found isnt at
* the top of its chain, put it there. This builds
* a most-frequently used order into the chains of
* the hash table, giving speadier lookups on those
* nicks which are being used currently. This same
* block of code is also used for channels and
* servers for the same performance reasons.
*/
/* I think this is useless concern --Beeth
if (prv)
{
aClient *tmp2;
tmp2 = (aClient *)tmp3->list;
tmp3->list = (void *)tmp;
prv->hnext = tmp->hnext;
tmp->hnext = tmp2;
}
*/
return (tmp);
}
clmiss++;
return (cptr);
}
/*
* hash_find_server
*/
aClient *hash_find_server(server, cptr)
char *server;
aClient *cptr;
{
Reg aClient *tmp, *prv = NULL;
Reg char *t;
Reg char ch;
aHashEntry *tmp3;
u_int hashv, hv;
hashv = hash_nick_name(server, &hv);
tmp3 = &clientTable[hashv];
for (tmp = (aClient *)tmp3->list; tmp; prv = tmp, tmp = tmp->hnext)
{
if (!IsServer(tmp) && !IsMe(tmp))
continue;
if (hv == tmp->hashv && strcasecmp(server, tmp->name) == 0)
{
clhits++;
/*
if (prv)
{
aClient *tmp2;
tmp2 = (aClient *)tmp3->list;
tmp3->list = (void *)tmp;
prv->hnext = tmp->hnext;
tmp->hnext = tmp2;
}
*/
return (tmp);
}
}
t = ((char *)server + strlen(server)) - 1;
/*
* Whats happening in this next loop ? Well, it takes a name like
* foo.bar.edu and proceeds to search for *.edu and then *.bar.edu.
* This is for checking full server names against masks although
* it isn't often done this way in lieu of using match().
*/
for (;;)
{
while (t > server && (*t != '.'))
t--;
if (t == server)
break;
t--;
if (*t == '*')
break;
ch = *t;
*t = '*';
/*
* Don't need to check IsServer() here since nicknames can't
* have *'s in them anyway.
*/
if (((tmp = hash_find_client(t, cptr))) != cptr)
{
*t = ch;
return (tmp);
}
*t = ch;
}
clmiss++;
return (cptr);
}
/*
* hash_find_channel
*/
aChannel *hash_find_channel(name, chptr)
char *name;
aChannel *chptr;
{
Reg aChannel *tmp, *prv = NULL;
Reg aHashEntry *tmp3;
u_int hashv, hv;
hashv = hash_channel_name(name, &hv, 0);
tmp3 = &channelTable[hashv];
for (tmp = (aChannel *)tmp3->list; tmp; prv = tmp, tmp = tmp->hnextch)
if (hv == tmp->hashv && strcasecmp(name, tmp->chname) == 0)
{
chhits++;
/*
if (prv)
{
register aChannel *tmp2;
tmp2 = (aChannel *)tmp3->list;
tmp3->list = (void *)tmp;
prv->hnextch = tmp->hnextch;
tmp->hnextch = tmp2;
}
*/
return (tmp);
}
chmiss++;
return chptr;
}
/*
* hash_find_channels
*
* look up matches for !?????name instead of a real match.
*/
aChannel *hash_find_channels(name, chptr)
char *name;
aChannel *chptr;
{
aChannel *tmp;
u_int hashv, hv;
if (chptr == NULL)
{
aHashEntry *tmp3;
hashv = hash_channel_name(name, &hv, 1);
tmp3 = &channelTable[hashv];
chptr = (aChannel *) tmp3->list;
}
else
{
hv = chptr->hashv;
chptr = chptr->hnextch;
}
if (chptr == NULL)
return NULL;
for (tmp = chptr; tmp; tmp = tmp->hnextch)
if (hv == tmp->hashv && *tmp->chname == '!' &&
strcasecmp(name, tmp->chname + CHIDLEN + 1) == 0)
{
chhits++;
return (tmp);
}
chmiss++;
return NULL;
}
/*
* hash_find_stoken
*/
aServer *hash_find_stoken(tok, cptr, dummy)
int tok;
aClient *cptr;
void *dummy;
{
Reg aServer *tmp, *prv = NULL;
Reg aHashEntry *tmp3;
u_int hashv, hv;
hv = hashv = tok * 15053;
hashv %= _SERVERSIZE;
tmp3 = &serverTable[hashv];
for (tmp = (aServer *)tmp3->list; tmp; prv = tmp, tmp = tmp->shnext)
if (tmp->stok == tok && tmp->bcptr->from == cptr)
{
if (prv)
{
Reg aServer *tmp2;
tmp2 = (aServer *)tmp3->list;
tmp3->list = (void *)tmp;
prv->shnext = tmp->shnext;
tmp->shnext = tmp2;
}
return (tmp);
}
return (aServer *)dummy;
}
/*
* NOTE: this command is not supposed to be an offical part of the ircd
* protocol. It is simply here to help debug and to monitor the
* performance of the hash functions and table, enabling a better
* algorithm to be sought if this one becomes troublesome.
* -avalon
*/
int m_hash(cptr, sptr, parc, parv)
aClient *cptr, *sptr;
int parc;
char *parv[];
{
#ifdef DEBUGMODE
register int l, i;
register aHashEntry *tab;
int deepest = 0, deeplink = 0, showlist = 0, tothits = 0;
int mosthit = 0, mosthits = 0, used = 0, used_now = 0, totlink = 0;
int link_pop[10], size = _HASHSIZE;
char ch;
aHashEntry *table;
if (parc > 1) {
ch = *parv[1];
if (islower(ch))
table = clientTable;
else {
table = channelTable;
size = _CHANNELHASHSIZE;
}
if (ch == 'L' || ch == 'l')
showlist = 1;
} else {
ch = '\0';
table = clientTable;
}
for (i = 0; i < 10; i++)
link_pop[i] = 0;
for (i = 0; i < size; i++) {
tab = &table[i];
l = tab->links;
if (showlist)
sendto_one(sptr,
"NOTICE %s :Hash Entry:%6d Hits:%7d Links:%6d",
parv[0], i, tab->hits, l);
if (l > 0) {
if (l < 10)
link_pop[l]++;
else
link_pop[9]++;
used_now++;
totlink += l;
if (l > deepest) {
deepest = l;
deeplink = i;
}
}
else
link_pop[0]++;
l = tab->hits;
if (l) {
used++;
tothits += l;
if (l > mosthits) {
mosthits = l;
mosthit = i;
}
}
}
switch((int)ch)
{
case 'V' : case 'v' :
{
register aClient *acptr;
int bad = 0, listlength = 0;
for (acptr = client; acptr; acptr = acptr->next) {
if (hash_find_client(acptr->name,acptr) != acptr) {
if (ch == 'V')
sendto_one(sptr, "NOTICE %s :Bad hash for %s",
parv[0], acptr->name);
bad++;
}
listlength++;
}
sendto_one(sptr,"NOTICE %s :List Length: %d Bad Hashes: %d",
parv[0], listlength, bad);
}
case 'P' : case 'p' :
for (i = 0; i < 10; i++)
sendto_one(sptr,"NOTICE %s :Entires with %d links : %d",
parv[0], i, link_pop[i]);
return (2);
case 'r' :
{
Reg aClient *acptr;
sendto_one(sptr,"NOTICE %s :Rehashing Client List.", parv[0]);
clear_client_hash_table(_HASHSIZE);
for (acptr = client; acptr; acptr = acptr->next)
(void)add_to_client_hash_table(acptr->name, acptr);
break;
}
case 'R' :
{
Reg aChannel *acptr;
sendto_one(sptr,"NOTICE %s :Rehashing Channel List.", parv[0]);
clear_channel_hash_table(_CHANNELHASHSIZE);
for (acptr = channel; acptr; acptr = acptr->nextch)
(void)add_to_channel_hash_table(acptr->chname, acptr);
break;
}
case 'H' :
if (parc > 2)
sendto_one(sptr,"NOTICE %s :%s hash to entry %d",
parv[0], parv[2],
hash_channel_name(parv[2], NULL, 0));
return (2);
case 'h' :
if (parc > 2)
sendto_one(sptr,"NOTICE %s :%s hash to entry %d",
parv[0], parv[2],
hash_nick_name(parv[2], NULL));
return (2);
case 'n' :
{
aClient *tmp;
int max;
if (parc <= 2 || !IsAnOper(sptr))
return (1);
l = atoi(parv[2]) % _HASHSIZE;
if (parc > 3)
max = atoi(parv[3]) % _HASHSIZE;
else
max = l;
for (;l <= max; l++)
for (i = 0, tmp = (aClient *)clientTable[l].list; tmp;
i++, tmp = tmp->hnext)
{
if (parv[1][2] == '1' && tmp != tmp->from)
continue;
sendto_one(sptr,"NOTICE %s :Node: %d #%d %s",
parv[0], l, i, tmp->name);
}
return (2);
}
case 'N' :
{
aChannel *tmp;
int max;
if (parc <= 2 || !IsAnOper(sptr))
return (1);
l = atoi(parv[2]) % _CHANNELHASHSIZE;
if (parc > 3)
max = atoi(parv[3]) % _CHANNELHASHSIZE;
else
max = l;
for (;l <= max; l++)
for (i = 0, tmp = (aChannel *)channelTable[l].list; tmp;
i++, tmp = tmp->hnextch)
sendto_one(sptr,"NOTICE %s :Node: %d #%d %s",
parv[0], l, i, tmp->chname);
return (2);
}
case 'S' :
#else
if (parc>1&&!strcmp(parv[1],"sums")){
#endif
sendto_one(sptr, "NOTICE %s :[SBSDC] [SUSER]", parv[0]);
sendto_one(sptr, "NOTICE %s :[SSERV] [IRCDC]", parv[0]);
sendto_one(sptr, "NOTICE %s :[CHANC] [SMISC]", parv[0]);
sendto_one(sptr, "NOTICE %s :[HASHC] [VERSH]", parv[0]);
sendto_one(sptr, "NOTICE %s :[MAKEF] HOSTID", parv[0]);
#ifndef DEBUGMODE
}
#endif
return 2;
#ifdef DEBUGMODE
case 'z' :
{
if (parc <= 2 || !IsAnOper(sptr))
return 1;
l = atoi(parv[2]);
if (l < 256)
return 1;
bigger_hash_table(&_HASHSIZE, clientTable, l);
sendto_one(sptr, "NOTICE %s :HASHSIZE now %d", parv[0], l);
break;
}
case 'Z' :
{
if (parc <= 2 || !IsAnOper(sptr))
return 1;
l = atoi(parv[2]);
if (l < 256)
return 1;
bigger_hash_table(&_CHANNELHASHSIZE, channelTable, l);
sendto_one(sptr, "NOTICE %s :CHANNELHASHSIZE now %d",
parv[0], l);
break;
}
default :
break;
}
sendto_one(sptr,"NOTICE %s :Entries Hashed: %d NonEmpty: %d of %d",
parv[0], totlink, used_now, size);
if (!used_now)
used_now = 1;
sendto_one(sptr,"NOTICE %s :Hash Ratio (av. depth): %f %%Full: %f",
parv[0], (float)((1.0 * totlink) / (1.0 * used_now)),
(float)((1.0 * used_now) / (1.0 * size)));
sendto_one(sptr,"NOTICE %s :Deepest Link: %d Links: %d",
parv[0], deeplink, deepest);
if (!used)
used = 1;
sendto_one(sptr,"NOTICE %s :Total Hits: %d Unhit: %d Av Hits: %f",
parv[0], tothits, size-used,
(float)((1.0 * (float)tothits) / (1.0 * (float)used)));
sendto_one(sptr,"NOTICE %s :Entry Most Hit: %d Hits: %d",
parv[0], mosthit, mosthits);
sendto_one(sptr,"NOTICE %s :Client hits %d miss %d",
parv[0], clhits, clmiss);
sendto_one(sptr,"NOTICE %s :Channel hits %d miss %d",
parv[0], chhits, chmiss);
return 2;
#endif
}
syntax highlighted by Code2HTML, v. 0.9.1