/************************************************************************
* IRC - Internet Relay Chat, src/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.
*/
/* $Id: hash.c,v 1.3 2005/07/05 03:17:53 sheik Exp $ */
#include "struct.h"
#include "common.h"
#include "sys.h"
#include "hash.h"
#include "h.h"
#include "memcount.h"
static aHashEntry clientTable[U_MAX];
static aHashEntry channelTable[CH_MAX];
/*
* look in whowas.c for the missing ...[WW_MAX]; entry - Dianora
*
* 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. Each time a
* lookup is made on an entry in the hash table and it is found, the
* entry is moved to the top of the chain.
*
* ^^^^^^^^^^^^^^^^ **** Not anymore - Dianora
*
*/
unsigned hash_nick_name(char *nname)
{
unsigned hash = 0;
int hash2 = 0;
int ret;
char lower;
while (*nname)
{
lower = ToLower(*nname);
hash = (hash << 1) + lower;
hash2 = (hash2 >> 1) + lower;
nname++;
}
ret = ((hash & U_MAX_INITIAL_MASK) << BITS_PER_COL) +
(hash2 & BITS_PER_COL_MASK);
return ret;
}
/*
* 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.
*/
int hash_channel_name(char *name)
{
unsigned char *hname = (unsigned char *) name;
unsigned int hash = 0;
int hash2 = 0;
char lower;
int i = 30;
while (*hname && --i)
{
lower = ToLower(*hname);
hash = (hash << 1) + lower;
hash2 = (hash2 >> 1) + lower;
hname++;
}
return ((hash & CH_MAX_INITIAL_MASK) << BITS_PER_COL) +
(hash2 & BITS_PER_COL_MASK);
}
unsigned int hash_whowas_name(char *name)
{
unsigned char *nname = (unsigned char *) name;
unsigned int hash = 0;
int hash2 = 0;
int ret;
char lower;
while (*nname)
{
lower = ToLower(*nname);
hash = (hash << 1) + lower;
hash2 = (hash2 >> 1) + lower;
nname++;
}
ret = ((hash & WW_MAX_INITIAL_MASK) << BITS_PER_COL) +
(hash2 & BITS_PER_COL_MASK);
return ret;
}
/*
* clear_*_hash_table
*
* Nullify the hashtable and its contents so it is completely empty.
*/
void clear_client_hash_table()
{
memset((char *) clientTable, '\0', sizeof(aHashEntry) * U_MAX);
}
void clear_channel_hash_table()
{
memset((char *) channelTable, '\0', sizeof(aHashEntry) * CH_MAX);
}
/* add_to_client_hash_table */
int add_to_client_hash_table(char *name, aClient *cptr)
{
int hashv;
hashv = hash_nick_name(name);
cptr->hnext = (aClient *) clientTable[hashv].list;
clientTable[hashv].list = (void *) cptr;
clientTable[hashv].links++;
clientTable[hashv].hits++;
return 0;
}
/* add_to_channel_hash_table */
int add_to_channel_hash_table(char *name, aChannel *chptr)
{
int hashv;
hashv = hash_channel_name(name);
chptr->hnextch = (aChannel *) channelTable[hashv].list;
channelTable[hashv].list = (void *) chptr;
channelTable[hashv].links++;
channelTable[hashv].hits++;
return 0;
}
/* del_from_client_hash_table */
int
del_from_client_hash_table(char *name, aClient *cptr)
{
aClient *tmp, *prev = NULL;
int hashv;
hashv = hash_nick_name(name);
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--;
return 1;
}
else
/*
* 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(char *name, aChannel *chptr)
{
aChannel *tmp, *prev = NULL;
int hashv;
hashv = hash_channel_name(name);
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--;
return 1;
}
else
return -1;
}
prev = tmp;
}
return 0;
}
/* hash_find_client */
aClient *hash_find_client(char *name, aClient *cptr)
{
aClient *tmp;
aHashEntry *tmp3;
int hashv;
hashv = hash_nick_name(name);
tmp3 = &clientTable[hashv];
/* Got the bucket, now search the chain. */
for (tmp = (aClient *) tmp3->list; tmp; tmp = tmp->hnext)
if (mycmp(name, tmp->name) == 0)
{
return (tmp);
}
return (cptr);
/*
* 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 speedier 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 don't believe it does.. it only wastes CPU, lets try it and
* see....
*
* - Dianora
*/
}
/*
* hash_find_nickserver
*/
aClient *hash_find_nickserver(char *name, aClient *cptr)
{
aClient *tmp;
aHashEntry *tmp3;
int hashv;
char *serv;
serv = strchr(name, '@');
*serv++ = '\0';
hashv = hash_nick_name(name);
tmp3 = &clientTable[hashv];
/* Got the bucket, now search the chain. */
for (tmp = (aClient *) tmp3->list; tmp; tmp = tmp->hnext)
if (mycmp(name, tmp->name) == 0 && tmp->user &&
mycmp(serv, tmp->user->server) == 0)
{
*--serv = '\0';
return (tmp);
}
*--serv = '\0';
return (cptr);
}
/* hash_find_server*/
aClient *hash_find_server(char *server, aClient *cptr)
{
aClient *tmp;
aHashEntry *tmp3;
int hashv;
hashv = hash_nick_name(server);
tmp3 = &clientTable[hashv];
for (tmp = (aClient *) tmp3->list; tmp; tmp = tmp->hnext)
{
if (!IsServer(tmp) && !IsMe(tmp))
continue;
if (mycmp(server, tmp->name) == 0)
{
return (tmp);
}
}
/*
* Whats happening in this next loop ? Well, it takes a name like
* foo.bar.edu and proceeds to earch for *.edu and then *.bar.edu.
* This is for checking full server names against masks although it
* isnt often done this way in lieu of using matches().
*/
return (cptr);
}
/* hash_find_channel */
aChannel *hash_find_channel(char *name, aChannel *chptr)
{
int hashv;
aChannel *tmp;
aHashEntry *tmp3;
hashv = hash_channel_name(name);
tmp3 = &channelTable[hashv];
for (tmp = (aChannel *) tmp3->list; tmp; tmp = tmp->hnextch)
if (mycmp(name, tmp->chname) == 0)
{
return (tmp);
}
return chptr;
}
/*
* 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
*
* Needs rewriting for DOUGH_HASH, consider this a place holder until
* thats done. Hopefully for hybrid-5, if not. tough. - Dianora
*
*/
int m_hash(aClient *cptr, aClient *sptr, int parc, char *parv[])
{
return 0;
}
/*
* Rough figure of the datastructures for notify:
*
* NOTIFY HASH cptr1
* | |- nick1
* nick1-|- cptr1 |- nick2
* | |- cptr2 cptr3
* | |- cptr3 cptr2 |- nick1
* | |- nick1
* nick2-|- cptr2 |- nick2
* |- cptr1
*
* add-to-notify-hash-table:
* del-from-notify-hash-table:
* hash-del-notify-list:
* hash-check-notify:
* hash-get-notify:
*/
static aWatch *watchTable[WATCHHASHSIZE];
void clear_watch_hash_table(void)
{
memset((char *)watchTable, '\0', sizeof(watchTable));
}
/* add_to_watch_hash_table */
int add_to_watch_hash_table(char *nick, aClient *cptr)
{
int hashv;
aWatch *anptr;
Link *lp;
/* Get the right bucket... */
hashv = hash_nick_name(nick)%WATCHHASHSIZE;
/* Find the right nick (header) in the bucket, or NULL... */
if ((anptr = (aWatch *)watchTable[hashv]))
while (anptr && mycmp(anptr->nick, nick))
anptr = anptr->hnext;
/* If found NULL (no header for this nick), make one... */
if (!anptr)
{
anptr = (aWatch *)MyMalloc(sizeof(aWatch)+strlen(nick));
anptr->lasttime = timeofday;
strcpy(anptr->nick, nick);
anptr->watch = NULL;
anptr->hnext = watchTable[hashv];
watchTable[hashv] = anptr;
}
/* Is this client already on the watch-list? */
if ((lp = anptr->watch))
while (lp && (lp->value.cptr != cptr))
lp = lp->next;
/* No it isn't, so add it in the bucket and client addint it */
if (!lp)
{
lp = anptr->watch;
anptr->watch = make_link();
anptr->watch->value.cptr = cptr;
anptr->watch->next = lp;
lp = make_link();
lp->next = cptr->watch;
lp->value.wptr = anptr;
cptr->watch = lp;
cptr->watches++;
}
return 0;
}
/* hash_check_watch */
int hash_check_watch(aClient *cptr, int reply)
{
int hashv;
aWatch *anptr;
Link *lp;
/* Get us the right bucket */
hashv = hash_nick_name(cptr->name)%WATCHHASHSIZE;
/* Find the right header in this bucket */
if ((anptr = (aWatch *)watchTable[hashv]))
while (anptr && mycmp(anptr->nick, cptr->name))
anptr = anptr->hnext;
if (!anptr)
return 0; /* This nick isn't on watch */
/* Update the time of last change to item */
anptr->lasttime = NOW;
/* Send notifies out to everybody on the list in header */
for (lp = anptr->watch; lp; lp = lp->next)
sendto_one(lp->value.cptr, rpl_str(reply), me.name,
lp->value.cptr->name, cptr->name,
(IsPerson(cptr)?cptr->user->username:"<N/A>"),
(IsPerson(cptr)?cptr->user->host:"<N/A>"),
anptr->lasttime, cptr->info);
return 0;
}
/* hash_get_watch */
aWatch *hash_get_watch(char *name)
{
int hashv;
aWatch *anptr;
hashv = hash_nick_name(name)%WATCHHASHSIZE;
if ((anptr = (aWatch *)watchTable[hashv]))
while (anptr && mycmp(anptr->nick, name))
anptr = anptr->hnext;
return anptr;
}
/* del_from_watch_hash_table */
int del_from_watch_hash_table(char *nick, aClient *cptr)
{
int hashv;
aWatch *anptr, *nlast = NULL;
Link *lp, *last = NULL;
/* Get the bucket for this nick... */
hashv = hash_nick_name(nick)%WATCHHASHSIZE;
/* Find the right header, maintaining last-link pointer... */
if ((anptr = (aWatch *)watchTable[hashv]))
while (anptr && mycmp(anptr->nick, nick))
{
nlast = anptr;
anptr = anptr->hnext;
}
if (!anptr)
return 0; /* No such watch */
/* Find this client from the list of notifies... with last-ptr. */
if ((lp = anptr->watch))
while (lp && (lp->value.cptr != cptr))
{
last = lp;
lp = lp->next;
}
if (!lp)
return 0; /* No such client to watch */
/* Fix the linked list under header, then remove the watch entry */
if (!last)
anptr->watch = lp->next;
else
last->next = lp->next;
free_link(lp);
/* Do the same regarding the links in client-record... */
last = NULL;
if ((lp = cptr->watch))
while (lp && (lp->value.wptr != anptr))
{
last = lp;
lp = lp->next;
}
/*
* Give error on the odd case... probobly not even neccessary
* No error checking in ircd is unneccessary ;) -Cabal95
*/
if (!lp)
sendto_ops("WATCH debug error: del_from_watch_hash_table "
"found a watch entry with no client "
"counterpoint processing nick %s on client %s!",
nick, cptr->user);
else
{
if (!last) /* First one matched */
cptr->watch = lp->next;
else
last->next = lp->next;
free_link(lp);
}
/* In case this header is now empty of notices, remove it */
if (!anptr->watch)
{
if (!nlast)
watchTable[hashv] = anptr->hnext;
else
nlast->hnext = anptr->hnext;
MyFree(anptr);
}
/* Update count of notifies on nick */
cptr->watches--;
return 0;
}
/* hash_del_watch_list */
int hash_del_watch_list(aClient *cptr)
{
int hashv;
aWatch *anptr;
Link *np, *lp, *last;
if (!(np = cptr->watch))
return 0; /* Nothing to do */
cptr->watch = NULL; /* Break the watch-list for client */
while (np)
{
/* Find the watch-record from hash-table... */
anptr = np->value.wptr;
last = NULL;
for (lp = anptr->watch; lp && (lp->value.cptr != cptr);
lp = lp->next)
last = lp;
/* Not found, another "worst case" debug error */
if (!lp)
sendto_ops("WATCH Debug error: hash_del_watch_list "
"found a WATCH entry with no table "
"counterpoint processing client %s!",
cptr->name);
else
{
/* Fix the watch-list and remove entry */
if (!last)
anptr->watch = lp->next;
else
last->next = lp->next;
free_link(lp);
/*
* If this leaves a header without notifies,
* remove it. Need to find the last-pointer!
*/
if (!anptr->watch)
{
aWatch *np2, *nl;
hashv = hash_nick_name(anptr->nick)%WATCHHASHSIZE;
nl = NULL;
np2 = watchTable[hashv];
while (np2 != anptr)
{
nl = np2;
np2 = np2->hnext;
}
if (nl)
nl->hnext = anptr->hnext;
else
watchTable[hashv] = anptr->hnext;
MyFree(anptr);
}
}
lp = np; /* Save last pointer processed */
np = np->next; /* Jump to the next pointer */
free_link(lp); /* Free the previous */
}
cptr->watches = 0;
return 0;
}
aChannel *hash_get_chan_bucket(int hashv)
{
if (hashv > CH_MAX)
return NULL;
return (aChannel *)channelTable[hashv].list;
}
u_long
memcount_hash(MChash *mc)
{
aWatch *wptr;
Link *lp;
int i;
mc->file = __FILE__;
for (i = 0; i < WATCHHASHSIZE; i++)
{
for (wptr = watchTable[i]; wptr; wptr = wptr->hnext)
{
mc->watches.c++;
mc->watches.m += sizeof(*wptr) + strlen(wptr->nick);
for (lp = wptr->watch; lp; lp = lp->next)
mc->e_links++;
}
}
mc->total.c += mc->watches.c;
mc->total.m += mc->watches.m;
mc->s_clienthash.c = sizeof(clientTable)/sizeof(clientTable[0]);
mc->s_clienthash.m = sizeof(clientTable);
mc->s_channelhash.c = sizeof(channelTable)/sizeof(channelTable[0]);
mc->s_channelhash.m = sizeof(channelTable);
mc->s_watchhash.c = sizeof(watchTable)/sizeof(watchTable[0]);
mc->s_watchhash.m = sizeof(watchTable);
return mc->total.m;
}
syntax highlighted by Code2HTML, v. 0.9.1