trunk/src/hash.c

/*
 *  ircd-hybrid: an advanced Internet Relay Chat Daemon(ircd).
 *  hash.c: Maintains hashtables.
 *
 *  Copyright (C) 2002 by the past and present ircd coders, and others.
 *
 *  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 2 of the License, 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307
 *  USA
 *
 *  $Id$
 */

#include "stdinc.h"
#include "list.h"
#include "conf.h"
#include "channel.h"
#include "channel_mode.h"
#include "client.h"
#include "modules.h"
#include "hash.h"
#include "resv.h"
#include "rng_mt.h"
#include "userhost.h"
#include "irc_string.h"
#include "ircd.h"
#include "numeric.h"
#include "send.h"
#include "memory.h"
#include "mempool.h"
#include "dbuf.h"
#include "s_user.h"


static mp_pool_t *userhost_pool = NULL;
static mp_pool_t *namehost_pool = NULL;

static unsigned int hashf_xor_key = 0;

/* The actual hash tables, They MUST be of the same HASHSIZE, variable
 * size tables could be supported but the rehash routine should also
 * rebuild the transformation maps, I kept the tables of equal size 
 * so that I can use one hash function.
 */
static struct Client *idTable[HASHSIZE];
static struct Client *clientTable[HASHSIZE];
static struct Channel *channelTable[HASHSIZE];
static struct UserHost *userhostTable[HASHSIZE];


/* init_hash()
 *
 * inputs       - NONE
 * output       - NONE
 * side effects - Initialize the maps used by hash
 *                functions and clear the tables
 */
void
hash_init(void)
{
  /* Default the userhost/namehost sizes to CLIENT_HEAP_SIZE for now,
   * should be a good close approximation anyway
   * - Dianora
   */
  userhost_pool = mp_pool_new(sizeof(struct UserHost), MP_CHUNK_SIZE_CLIENT);
  namehost_pool = mp_pool_new(sizeof(struct NameHost), MP_CHUNK_SIZE_CLIENT);

  hashf_xor_key = genrand_int32() % 256;  /* better than nothing --adx */
}

/*
 * New hash function based on the Fowler/Noll/Vo (FNV) algorithm from
 * http://www.isthe.com/chongo/tech/comp/fnv/
 *
 * Here, we use the FNV-1 method, which gives slightly better results
 * than FNV-1a.   -Michael
 */
unsigned int
strhash(const char *name)
{
  const unsigned char *p = (const unsigned char *)name;
  unsigned int hval = FNV1_32_INIT;

  if (EmptyString(p))
    return 0;
  for (; *p != '\0'; ++p)
  {
    hval += (hval << 1) + (hval <<  4) + (hval << 7) +
            (hval << 8) + (hval << 24);
    hval ^= (ToLower(*p) ^ hashf_xor_key);
  }

  return (hval >> FNV1_32_BITS) ^ (hval & ((1 << FNV1_32_BITS) - 1));
}

/************************** Externally visible functions ********************/

/* Optimization note: in these functions I supposed that the CSE optimization
 * (Common Subexpression Elimination) does its work decently, this means that
 * I avoided introducing new variables to do the work myself and I did let
 * the optimizer play with more free registers, actual tests proved this
 * solution to be faster than doing things like tmp2=tmp->hnext... and then
 * use tmp2 myself which would have given less freedom to the optimizer.
 */

/* hash_add_client()
 *
 * inputs       - pointer to client
 * output       - NONE
 * side effects - Adds a client's name in the proper hash linked
 *                list, can't fail, client_p must have a non-null
 *                name or expect a coredump, the name is infact
 *                taken from client_p->name
 */
void
hash_add_client(struct Client *client_p)
{
  unsigned int hashv = strhash(client_p->name);

  client_p->hnext = clientTable[hashv];
  clientTable[hashv] = client_p;
}

/* hash_add_channel()
 *
 * inputs       - pointer to channel
 * output       - NONE
 * side effects - Adds a channel's name in the proper hash linked
 *                list, can't fail. chptr must have a non-null name
 *                or expect a coredump. As before the name is taken
 *                from chptr->name, we do hash its entire lenght
 *                since this proved to be statistically faster
 */
void
hash_add_channel(struct Channel *chptr)
{
  unsigned int hashv = strhash(chptr->chname);

  chptr->hnextch = channelTable[hashv];
  channelTable[hashv] = chptr;
}

void
hash_add_userhost(struct UserHost *userhost)
{
  unsigned int hashv = strhash(userhost->host);

  userhost->next = userhostTable[hashv];
  userhostTable[hashv] = userhost;
}

void
hash_add_id(struct Client *client_p)
{
  unsigned int hashv = strhash(client_p->id);

  client_p->idhnext = idTable[hashv];
  idTable[hashv] = client_p;
}

/* hash_del_id()
 *
 * inputs       - pointer to client
 * output       - NONE
 * side effects - Removes an ID from the hash linked list
 */
void
hash_del_id(struct Client *client_p)
{
  unsigned int hashv = strhash(client_p->id);
  struct Client *tmp = idTable[hashv];

  if (tmp != NULL)
  {
    if (tmp == client_p)
    {
      idTable[hashv] = client_p->idhnext;
      client_p->idhnext = client_p;
    }
    else
    {
      while (tmp->idhnext != client_p)
        if ((tmp = tmp->idhnext) == NULL)
          return;

      tmp->idhnext = tmp->idhnext->idhnext;
      client_p->idhnext = client_p;
    }
  }
}

/* hash_del_client()
 *
 * inputs       - pointer to client
 * output       - NONE
 * side effects - Removes a Client's name from the hash linked list
 */
void
hash_del_client(struct Client *client_p)
{
  unsigned int hashv = strhash(client_p->name);
  struct Client *tmp = clientTable[hashv];

  if (tmp != NULL)
  {
    if (tmp == client_p)
    {
      clientTable[hashv] = client_p->hnext;
      client_p->hnext = client_p;
    }
    else
    {
      while (tmp->hnext != client_p)
        if ((tmp = tmp->hnext) == NULL)
          return;

      tmp->hnext = tmp->hnext->hnext;
      client_p->hnext = client_p;
    }
  }
}

/* hash_del_userhost()
 *
 * inputs       - pointer to userhost
 * output       - NONE
 * side effects - Removes a userhost from the hash linked list
 */
void
hash_del_userhost(struct UserHost *userhost)
{
  unsigned int hashv = strhash(userhost->host);
  struct UserHost *tmp = userhostTable[hashv];

  if (tmp != NULL)
  {
    if (tmp == userhost)
    {
      userhostTable[hashv] = userhost->next;
      userhost->next = userhost;
    }
    else
    {
      while (tmp->next != userhost)
        if ((tmp = tmp->next) == NULL)
          return;

      tmp->next = tmp->next->next;
      userhost->next = userhost;
    }
  }
}

/* hash_del_channel()
 *
 * inputs       - pointer to client
 * output       - NONE
 * side effects - Removes the channel's name from the corresponding
 *                hash linked list
 */
void
hash_del_channel(struct Channel *chptr)
{
  unsigned int hashv = strhash(chptr->chname);
  struct Channel *tmp = channelTable[hashv];

  if (tmp != NULL)
  {
    if (tmp == chptr)
    {
      channelTable[hashv] = chptr->hnextch;
      chptr->hnextch = chptr;
    }
    else
    {
      while (tmp->hnextch != chptr)
        if ((tmp = tmp->hnextch) == NULL)
          return;

      tmp->hnextch = tmp->hnextch->hnextch;
      chptr->hnextch = chptr;
    }
  }
}

/* hash_find_client()
 *
 * inputs       - pointer to name
 * output       - NONE
 * side effects - New semantics: finds a client whose name is 'name'
 *                if can't find one returns NULL. If it finds one moves
 *                it to the top of the list and returns it.
 */
struct Client *
hash_find_client(const char *name)
{
  unsigned int hashv = strhash(name);
  struct Client *client_p;

  if ((client_p = clientTable[hashv]) != NULL)
  {
    if (irccmp(name, client_p->name))
    {
      struct Client *prev;

      while (prev = client_p, (client_p = client_p->hnext) != NULL)
      {
        if (!irccmp(name, client_p->name))
        {
          prev->hnext = client_p->hnext;
          client_p->hnext = clientTable[hashv];
          clientTable[hashv] = client_p;
          break;
        }
      }
    }
  }

  return client_p;
}

struct Client *
hash_find_id(const char *name)
{
  unsigned int hashv = strhash(name);
  struct Client *client_p;

  if ((client_p = idTable[hashv]) != NULL)
  {
    if (strcmp(name, client_p->id))
    {
      struct Client *prev;

      while (prev = client_p, (client_p = client_p->idhnext) != NULL)
      {
        if (!strcmp(name, client_p->id))
        {
          prev->idhnext = client_p->idhnext;
          client_p->idhnext = idTable[hashv];
          idTable[hashv] = client_p;
          break;
        }
      }
    }
  }

  return client_p;
}

struct Client *
hash_find_server(const char *name)
{
  unsigned int hashv = strhash(name);
  struct Client *client_p = NULL;

  if (IsDigit(*name) && strlen(name) == IRC_MAXSID)
    return hash_find_id(name);

  if ((client_p = clientTable[hashv]) != NULL)
  {
    if ((!IsServer(client_p) && !IsMe(client_p)) ||
        irccmp(name, client_p->name))
    {
      struct Client *prev;

      while (prev = client_p, (client_p = client_p->hnext) != NULL)
      {
        if ((IsServer(client_p) || IsMe(client_p)) &&
            !irccmp(name, client_p->name))
        {
          prev->hnext = client_p->hnext;
          client_p->hnext = clientTable[hashv];
          clientTable[hashv] = client_p;
          break;
        }
      }
    }
  }

  return client_p;
}

/* hash_find_channel()
 *
 * inputs       - pointer to name
 * output       - NONE
 * side effects - New semantics: finds a channel whose name is 'name', 
 *                if can't find one returns NULL, if can find it moves
 *                it to the top of the list and returns it.
 */
struct Channel *
hash_find_channel(const char *name)
{
  unsigned int hashv = strhash(name);
  struct Channel *chptr = NULL;

  if ((chptr = channelTable[hashv]) != NULL)
  {
    if (irccmp(name, chptr->chname))
    {
      struct Channel *prev;

      while (prev = chptr, (chptr = chptr->hnextch) != NULL)
      {
        if (!irccmp(name, chptr->chname))
        {
          prev->hnextch = chptr->hnextch;
          chptr->hnextch = channelTable[hashv];
          channelTable[hashv] = chptr;
          break;
        }
      }
    }
  }

  return chptr;
}

/* hash_get_bucket(int type, unsigned int hashv)
 *
 * inputs       - hash value (must be between 0 and HASHSIZE - 1)
 * output       - NONE
 * returns      - pointer to first channel in channelTable[hashv]
 *                if that exists;
 *                NULL if there is no channel in that place;
 *                NULL if hashv is an invalid number.
 * side effects - NONE
 */
void *
hash_get_bucket(int type, unsigned int hashv)
{
  assert(hashv < HASHSIZE);
  if (hashv >= HASHSIZE)
      return NULL;

  switch (type)
  {
    case HASH_TYPE_ID:
      return idTable[hashv];
      break;
    case HASH_TYPE_CHANNEL:
      return channelTable[hashv];
      break;
    case HASH_TYPE_CLIENT:
      return clientTable[hashv];
      break;
    case HASH_TYPE_USERHOST:
      return userhostTable[hashv];
      break;
    default:
      assert(0);
  }

  return NULL;
}

struct UserHost *
hash_find_userhost(const char *host)
{
  unsigned int hashv = strhash(host);
  struct UserHost *userhost;

  if ((userhost = userhostTable[hashv]))
  {
    if (irccmp(host, userhost->host))
    {
      struct UserHost *prev;

      while (prev = userhost, (userhost = userhost->next) != NULL)
      {
        if (!irccmp(host, userhost->host))
        {
          prev->next = userhost->next;
          userhost->next = userhostTable[hashv];
          userhostTable[hashv] = userhost;
          break;
        }
      }
    }
  }

  return userhost;
}

/* count_user_host()
 *
 * inputs       - user name
 *              - hostname
 *              - int flag 1 if global, 0 if local
 *              - pointer to where global count should go
 *              - pointer to where local count should go
 *              - pointer to where identd count should go (local clients only)
 * output       - none
 * side effects -
 */
void
count_user_host(const char *user, const char *host, unsigned int *global_p,
                unsigned int *local_p, unsigned int *icount_p)
{
  dlink_node *ptr;
  struct UserHost *found_userhost;
  struct NameHost *nameh;

  if ((found_userhost = hash_find_userhost(host)) == NULL)
    return;

  DLINK_FOREACH(ptr, found_userhost->list.head)
  {
    nameh = ptr->data;

    if (!irccmp(user, nameh->name))
    {
      if (global_p != NULL)
        *global_p = nameh->gcount;
      if (local_p != NULL)
        *local_p  = nameh->lcount;
      if (icount_p != NULL)
        *icount_p = nameh->icount;
      return;
    }
  }
}

/* find_or_add_userhost()
 *
 * inputs       - host name
 * output       - none
 * side effects - find UserHost * for given host name
 */
static struct UserHost *
find_or_add_userhost(const char *host)
{
  struct UserHost *userhost;

  if ((userhost = hash_find_userhost(host)) != NULL)
    return userhost;

  userhost = mp_pool_get(userhost_pool);

  memset(userhost, 0, sizeof(*userhost));
  strlcpy(userhost->host, host, sizeof(userhost->host));
  hash_add_userhost(userhost);

  return userhost;
}

/* add_user_host()
 *
 * inputs       - user name
 *              - hostname
 *              - int flag 1 if global, 0 if local
 * output       - none
 * side effects - add given user@host to hash tables
 */
void
add_user_host(const char *user, const char *host, int global)
{
  dlink_node *ptr;
  struct UserHost *found_userhost;
  struct NameHost *nameh;
  int hasident = 1;

  if (*user == '~')
  {
    hasident = 0;
    ++user;
  }

  if ((found_userhost = find_or_add_userhost(host)) == NULL)
    return;

  DLINK_FOREACH(ptr, found_userhost->list.head)
  {
    nameh = ptr->data;

    if (!irccmp(user, nameh->name))
    {
      nameh->gcount++;

      if (!global)
      {
        if (hasident)
          nameh->icount++;
        nameh->lcount++;
      }

      return;
    }
  }

  nameh = mp_pool_get(namehost_pool);
  memset(nameh, 0, sizeof(*nameh));
  strlcpy(nameh->name, user, sizeof(nameh->name));

  nameh->gcount = 1;

  if (!global)
  {
    if (hasident)
      nameh->icount = 1;
    nameh->lcount = 1;
  }

  dlinkAdd(nameh, &nameh->node, &found_userhost->list);
}

/* delete_user_host()
 *
 * inputs       - user name
 *              - hostname
 *              - int flag 1 if global, 0 if local
 * output       - none
 * side effects - delete given user@host to hash tables
 */
void
delete_user_host(const char *user, const char *host, int global)
{
  dlink_node *ptr = NULL, *next_ptr = NULL;
  struct UserHost *found_userhost;
  struct NameHost *nameh;
  int hasident = 1;

  if (*user == '~')
  {
    hasident = 0;
    ++user;
  }

  if ((found_userhost = hash_find_userhost(host)) == NULL)
    return;

  DLINK_FOREACH_SAFE(ptr, next_ptr, found_userhost->list.head)
  {
    nameh = ptr->data;

    if (!irccmp(user, nameh->name))
    {
      if (nameh->gcount > 0)
        nameh->gcount--;
      if (!global)
      {
        if (nameh->lcount > 0)
          nameh->lcount--;
        if (hasident && nameh->icount > 0)
          nameh->icount--;
      }

      if (nameh->gcount == 0 && nameh->lcount == 0)
      {
        dlinkDelete(&nameh->node, &found_userhost->list);
        mp_pool_release(nameh);
      }

      if (dlink_list_length(&found_userhost->list) == 0)
      {
        hash_del_userhost(found_userhost);
        mp_pool_release(found_userhost);
      }

      return;
    }
  }
}

/*
 * Safe list code.
 *
 * The idea is really quite simple. As the link lists pointed to in
 * each "bucket" of the channel hash table are traversed atomically
 * there is no locking needed. Overall, yes, inconsistent reported
 * state can still happen, but normally this isn't a big deal.
 * I don't like sticking the code into hash.c but oh well. Moreover,
 * if a hash isn't used in future, oops.
 *
 * - Dianora
 */

/* exceeding_sendq()
 *
 * inputs       - pointer to client to check
 * output       - 1 if client is in danger of blowing its sendq
 *                0 if it is not.
 * side effects -
 *
 * Sendq limit is fairly conservative at 1/2 (In original anyway)
 */
static int
exceeding_sendq(struct Client *to)
{
  if (dbuf_length(&to->localClient->buf_sendq) > (get_sendq(&to->localClient->confs) / 2))
    return 1;
  else
    return 0;
}

void
free_list_task(struct ListTask *lt, struct Client *source_p)
{
  dlink_node *dl = NULL, *dln = NULL;

  if ((dl = dlinkFindDelete(&listing_client_list, source_p)) != NULL)
    free_dlink_node(dl);

  DLINK_FOREACH_SAFE(dl, dln, lt->show_mask.head)
  {
    MyFree(dl->data);
    free_dlink_node(dl);
  }

  DLINK_FOREACH_SAFE(dl, dln, lt->hide_mask.head)
  {
    MyFree(dl->data);
    free_dlink_node(dl);
  }

  MyFree(lt);

  if (MyConnect(source_p))
    source_p->localClient->list_task = NULL;
}

/* list_allow_channel()
 *
 * inputs       - channel name
 *              - pointer to a list task
 * output       - 1 if the channel is to be displayed
 *                0 otherwise
 * side effects -
 */
static int
list_allow_channel(const char *chname, const struct ListTask *lt)
{
  const dlink_node *dl = NULL;

  DLINK_FOREACH(dl, lt->show_mask.head)
    if (match(dl->data, chname) != 0)
      return 0;

  DLINK_FOREACH(dl, lt->hide_mask.head)
    if (match(dl->data, chname) == 0)
      return 0;

  return 1;
}

/* list_one_channel()
 *
 * inputs       - client pointer to return result to
 *              - pointer to channel to list
 *              - pointer to ListTask structure
 * output       - none
 * side effects -
 */
static void
list_one_channel(struct Client *source_p, struct Channel *chptr,
                 struct ListTask *list_task)
{
  if (SecretChannel(chptr) && !IsMember(source_p, chptr))
    return;
  if (dlink_list_length(&chptr->members) < list_task->users_min ||
      dlink_list_length(&chptr->members) > list_task->users_max ||
      (chptr->channelts != 0 &&
       ((unsigned int)chptr->channelts < list_task->created_min ||
        (unsigned int)chptr->channelts > list_task->created_max)) ||
      (unsigned int)chptr->topic_time < list_task->topicts_min ||
      (chptr->topic_time ? (unsigned int)chptr->topic_time : UINT_MAX) >
      list_task->topicts_max)
    return;

  if (!list_allow_channel(chptr->chname, list_task))
    return;
  sendto_one(source_p, form_str(RPL_LIST), me.name, source_p->name,
             chptr->chname, dlink_list_length(&chptr->members),
             chptr->topic);
}

/* safe_list_channels()
 *
 * inputs       - pointer to client requesting list
 * output       - 0/1
 * side effects - safely list all channels to source_p
 *
 * Walk the channel buckets, ensure all pointers in a bucket are
 * traversed before blocking on a sendq. This means, no locking is needed.
 *
 * N.B. This code is "remote" safe, but is not currently used for
 * remote clients.
 *
 * - Dianora
 */
void
safe_list_channels(struct Client *source_p, struct ListTask *list_task,
                   int only_unmasked_channels)
{
  struct Channel *chptr = NULL;

  if (!only_unmasked_channels)
  {
    unsigned int i;

    for (i = list_task->hash_index; i < HASHSIZE; ++i)
    {
      if (exceeding_sendq(source_p->from))
      {
        list_task->hash_index = i;
        return;    /* still more to do */
      }

      for (chptr = channelTable[i]; chptr; chptr = chptr->hnextch)
        list_one_channel(source_p, chptr, list_task);
    }
  }
  else
  {
    dlink_node *dl;

    DLINK_FOREACH(dl, list_task->show_mask.head)
      if ((chptr = hash_find_channel(dl->data)) != NULL)
        list_one_channel(source_p, chptr, list_task);
  }

  free_list_task(list_task, source_p);
  sendto_one(source_p, form_str(RPL_LISTEND),
             me.name, source_p->name);
}
Revision:	1826
Committed:	Mon Apr 15 09:09:09 2013 UTC (12 years, 4 months ago) by michael
Content type:	text/x-csrc
File size:	19975 byte(s)
Log Message:	- Minor cleanups to hash.c; removed now unused functions, style cleanups
#	User	Rev	Content
1	adx	30	/*
2			* ircd-hybrid: an advanced Internet Relay Chat Daemon(ircd).
3			* hash.c: Maintains hashtables.
4			*
5			* Copyright (C) 2002 by the past and present ircd coders, and others.
6			*
7			* This program is free software; you can redistribute it and/or modify
8			* it under the terms of the GNU General Public License as published by
9			* the Free Software Foundation; either version 2 of the License, or
10			* (at your option) any later version.
11			*
12			* This program is distributed in the hope that it will be useful,
13			* but WITHOUT ANY WARRANTY; without even the implied warranty of
14			* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15			* GNU General Public License for more details.
16			*
17			* You should have received a copy of the GNU General Public License
18			* along with this program; if not, write to the Free Software
19			* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
20			* USA
21			*
22	knight	31	* $Id$
23	adx	30	*/
24
25			#include "stdinc.h"
26	michael	1011	#include "list.h"
27	michael	1309	#include "conf.h"
28	adx	30	#include "channel.h"
29			#include "channel_mode.h"
30			#include "client.h"
31			#include "modules.h"
32			#include "hash.h"
33			#include "resv.h"
34	michael	982	#include "rng_mt.h"
35	adx	30	#include "userhost.h"
36			#include "irc_string.h"
37			#include "ircd.h"
38			#include "numeric.h"
39			#include "send.h"
40			#include "memory.h"
41	michael	1654	#include "mempool.h"
42	adx	30	#include "dbuf.h"
43			#include "s_user.h"
44
45
46	michael	1654	static mp_pool_t *userhost_pool = NULL;
47			static mp_pool_t *namehost_pool = NULL;
48	adx	30
49	michael	982	static unsigned int hashf_xor_key = 0;
50	adx	30
51			/* The actual hash tables, They MUST be of the same HASHSIZE, variable
52			* size tables could be supported but the rehash routine should also
53			* rebuild the transformation maps, I kept the tables of equal size
54			* so that I can use one hash function.
55			*/
56			static struct Client *idTable[HASHSIZE];
57			static struct Client *clientTable[HASHSIZE];
58			static struct Channel *channelTable[HASHSIZE];
59			static struct UserHost *userhostTable[HASHSIZE];
60
61
62			/* init_hash()
63			*
64			* inputs - NONE
65			* output - NONE
66			* side effects - Initialize the maps used by hash
67			* functions and clear the tables
68			*/
69			void
70	michael	1798	hash_init(void)
71	adx	30	{
72			/* Default the userhost/namehost sizes to CLIENT_HEAP_SIZE for now,
73			* should be a good close approximation anyway
74			* - Dianora
75			*/
76	michael	1654	userhost_pool = mp_pool_new(sizeof(struct UserHost), MP_CHUNK_SIZE_CLIENT);
77			namehost_pool = mp_pool_new(sizeof(struct NameHost), MP_CHUNK_SIZE_CLIENT);
78	adx	30
79	michael	982	hashf_xor_key = genrand_int32() % 256; /* better than nothing --adx */
80	adx	30	}
81
82			/*
83			* New hash function based on the Fowler/Noll/Vo (FNV) algorithm from
84			* http://www.isthe.com/chongo/tech/comp/fnv/
85			*
86			* Here, we use the FNV-1 method, which gives slightly better results
87			* than FNV-1a. -Michael
88			*/
89			unsigned int
90			strhash(const char *name)
91			{
92			const unsigned char p = (const unsigned char )name;
93			unsigned int hval = FNV1_32_INIT;
94
95	michael	1826	if (EmptyString(p))
96	adx	30	return 0;
97			for (; *p != '\0'; ++p)
98			{
99			hval += (hval << 1) + (hval << 4) + (hval << 7) +
100			(hval << 8) + (hval << 24);
101	michael	982	hval ^= (ToLower(*p) ^ hashf_xor_key);
102	adx	30	}
103
104	michael	982	return (hval >> FNV1_32_BITS) ^ (hval & ((1 << FNV1_32_BITS) - 1));
105	adx	30	}
106
107			/************************ Externally visible functions ******************/
108
109			/* Optimization note: in these functions I supposed that the CSE optimization
110			* (Common Subexpression Elimination) does its work decently, this means that
111			* I avoided introducing new variables to do the work myself and I did let
112			* the optimizer play with more free registers, actual tests proved this
113			* solution to be faster than doing things like tmp2=tmp->hnext... and then
114			* use tmp2 myself which would have given less freedom to the optimizer.
115			*/
116
117			/* hash_add_client()
118			*
119			* inputs - pointer to client
120			* output - NONE
121			* side effects - Adds a client's name in the proper hash linked
122			* list, can't fail, client_p must have a non-null
123			* name or expect a coredump, the name is infact
124			* taken from client_p->name
125			*/
126			void
127			hash_add_client(struct Client *client_p)
128			{
129			unsigned int hashv = strhash(client_p->name);
130
131			client_p->hnext = clientTable[hashv];
132			clientTable[hashv] = client_p;
133			}
134
135			/* hash_add_channel()
136			*
137			* inputs - pointer to channel
138			* output - NONE
139			* side effects - Adds a channel's name in the proper hash linked
140			* list, can't fail. chptr must have a non-null name
141			* or expect a coredump. As before the name is taken
142			* from chptr->name, we do hash its entire lenght
143			* since this proved to be statistically faster
144			*/
145			void
146			hash_add_channel(struct Channel *chptr)
147			{
148			unsigned int hashv = strhash(chptr->chname);
149
150			chptr->hnextch = channelTable[hashv];
151			channelTable[hashv] = chptr;
152			}
153
154			void
155			hash_add_userhost(struct UserHost *userhost)
156			{
157			unsigned int hashv = strhash(userhost->host);
158
159			userhost->next = userhostTable[hashv];
160			userhostTable[hashv] = userhost;
161			}
162
163			void
164			hash_add_id(struct Client *client_p)
165			{
166			unsigned int hashv = strhash(client_p->id);
167
168			client_p->idhnext = idTable[hashv];
169			idTable[hashv] = client_p;
170			}
171
172			/* hash_del_id()
173			*
174			* inputs - pointer to client
175			* output - NONE
176			* side effects - Removes an ID from the hash linked list
177			*/
178			void
179			hash_del_id(struct Client *client_p)
180			{
181			unsigned int hashv = strhash(client_p->id);
182			struct Client *tmp = idTable[hashv];
183
184			if (tmp != NULL)
185			{
186			if (tmp == client_p)
187			{
188			idTable[hashv] = client_p->idhnext;
189			client_p->idhnext = client_p;
190			}
191			else
192			{
193			while (tmp->idhnext != client_p)
194			if ((tmp = tmp->idhnext) == NULL)
195			return;
196
197			tmp->idhnext = tmp->idhnext->idhnext;
198			client_p->idhnext = client_p;
199			}
200			}
201			}
202
203			/* hash_del_client()
204			*
205			* inputs - pointer to client
206			* output - NONE
207			* side effects - Removes a Client's name from the hash linked list
208			*/
209			void
210			hash_del_client(struct Client *client_p)
211			{
212			unsigned int hashv = strhash(client_p->name);
213			struct Client *tmp = clientTable[hashv];
214
215			if (tmp != NULL)
216			{
217			if (tmp == client_p)
218			{
219			clientTable[hashv] = client_p->hnext;
220			client_p->hnext = client_p;
221			}
222			else
223			{
224			while (tmp->hnext != client_p)
225			if ((tmp = tmp->hnext) == NULL)
226			return;
227
228			tmp->hnext = tmp->hnext->hnext;
229			client_p->hnext = client_p;
230			}
231			}
232			}
233
234			/* hash_del_userhost()
235			*
236			* inputs - pointer to userhost
237			* output - NONE
238			* side effects - Removes a userhost from the hash linked list
239			*/
240			void
241			hash_del_userhost(struct UserHost *userhost)
242			{
243			unsigned int hashv = strhash(userhost->host);
244			struct UserHost *tmp = userhostTable[hashv];
245
246			if (tmp != NULL)
247			{
248			if (tmp == userhost)
249			{
250			userhostTable[hashv] = userhost->next;
251			userhost->next = userhost;
252			}
253			else
254			{
255			while (tmp->next != userhost)
256			if ((tmp = tmp->next) == NULL)
257			return;
258
259			tmp->next = tmp->next->next;
260			userhost->next = userhost;
261			}
262			}
263			}
264
265			/* hash_del_channel()
266			*
267			* inputs - pointer to client
268			* output - NONE
269			* side effects - Removes the channel's name from the corresponding
270			* hash linked list
271			*/
272			void
273			hash_del_channel(struct Channel *chptr)
274			{
275			unsigned int hashv = strhash(chptr->chname);
276			struct Channel *tmp = channelTable[hashv];
277
278			if (tmp != NULL)
279			{
280			if (tmp == chptr)
281			{
282			channelTable[hashv] = chptr->hnextch;
283			chptr->hnextch = chptr;
284			}
285			else
286			{
287			while (tmp->hnextch != chptr)
288			if ((tmp = tmp->hnextch) == NULL)
289			return;
290
291			tmp->hnextch = tmp->hnextch->hnextch;
292			chptr->hnextch = chptr;
293			}
294			}
295			}
296
297	michael	1169	/* hash_find_client()
298	adx	30	*
299			* inputs - pointer to name
300			* output - NONE
301			* side effects - New semantics: finds a client whose name is 'name'
302			* if can't find one returns NULL. If it finds one moves
303			* it to the top of the list and returns it.
304			*/
305			struct Client *
306	michael	1169	hash_find_client(const char *name)
307	adx	30	{
308			unsigned int hashv = strhash(name);
309			struct Client *client_p;
310
311			if ((client_p = clientTable[hashv]) != NULL)
312			{
313			if (irccmp(name, client_p->name))
314			{
315			struct Client *prev;
316
317			while (prev = client_p, (client_p = client_p->hnext) != NULL)
318			{
319			if (!irccmp(name, client_p->name))
320			{
321			prev->hnext = client_p->hnext;
322			client_p->hnext = clientTable[hashv];
323			clientTable[hashv] = client_p;
324			break;
325			}
326			}
327			}
328			}
329
330			return client_p;
331			}
332
333			struct Client *
334			hash_find_id(const char *name)
335			{
336			unsigned int hashv = strhash(name);
337			struct Client *client_p;
338
339			if ((client_p = idTable[hashv]) != NULL)
340			{
341	michael	880	if (strcmp(name, client_p->id))
342	adx	30	{
343			struct Client *prev;
344
345			while (prev = client_p, (client_p = client_p->idhnext) != NULL)
346			{
347	michael	880	if (!strcmp(name, client_p->id))
348	adx	30	{
349			prev->idhnext = client_p->idhnext;
350			client_p->idhnext = idTable[hashv];
351			idTable[hashv] = client_p;
352			break;
353			}
354			}
355			}
356			}
357
358			return client_p;
359			}
360
361			struct Client *
362	michael	1169	hash_find_server(const char *name)
363	adx	30	{
364			unsigned int hashv = strhash(name);
365			struct Client *client_p = NULL;
366
367			if (IsDigit(*name) && strlen(name) == IRC_MAXSID)
368	michael	1397	return hash_find_id(name);
369	adx	30
370	michael	1397	if ((client_p = clientTable[hashv]) != NULL)
371	adx	30	{
372			if ((!IsServer(client_p) && !IsMe(client_p)) \|\|
373			irccmp(name, client_p->name))
374			{
375			struct Client *prev;
376
377			while (prev = client_p, (client_p = client_p->hnext) != NULL)
378			{
379			if ((IsServer(client_p) \|\| IsMe(client_p)) &&
380			!irccmp(name, client_p->name))
381			{
382			prev->hnext = client_p->hnext;
383			client_p->hnext = clientTable[hashv];
384			clientTable[hashv] = client_p;
385			break;
386			}
387			}
388			}
389			}
390
391	michael	1118	return client_p;
392	adx	30	}
393
394			/* hash_find_channel()
395			*
396			* inputs - pointer to name
397			* output - NONE
398			* side effects - New semantics: finds a channel whose name is 'name',
399			* if can't find one returns NULL, if can find it moves
400			* it to the top of the list and returns it.
401			*/
402			struct Channel *
403			hash_find_channel(const char *name)
404			{
405			unsigned int hashv = strhash(name);
406			struct Channel *chptr = NULL;
407
408			if ((chptr = channelTable[hashv]) != NULL)
409			{
410			if (irccmp(name, chptr->chname))
411			{
412			struct Channel *prev;
413
414			while (prev = chptr, (chptr = chptr->hnextch) != NULL)
415			{
416			if (!irccmp(name, chptr->chname))
417			{
418			prev->hnextch = chptr->hnextch;
419			chptr->hnextch = channelTable[hashv];
420			channelTable[hashv] = chptr;
421			break;
422			}
423			}
424			}
425			}
426
427			return chptr;
428			}
429
430			/* hash_get_bucket(int type, unsigned int hashv)
431			*
432			* inputs - hash value (must be between 0 and HASHSIZE - 1)
433			* output - NONE
434			* returns - pointer to first channel in channelTable[hashv]
435			* if that exists;
436			* NULL if there is no channel in that place;
437			* NULL if hashv is an invalid number.
438			* side effects - NONE
439			*/
440			void *
441			hash_get_bucket(int type, unsigned int hashv)
442			{
443			assert(hashv < HASHSIZE);
444			if (hashv >= HASHSIZE)
445			return NULL;
446
447			switch (type)
448			{
449			case HASH_TYPE_ID:
450			return idTable[hashv];
451			break;
452			case HASH_TYPE_CHANNEL:
453			return channelTable[hashv];
454			break;
455			case HASH_TYPE_CLIENT:
456			return clientTable[hashv];
457			break;
458			case HASH_TYPE_USERHOST:
459			return userhostTable[hashv];
460			break;
461			default:
462			assert(0);
463			}
464
465			return NULL;
466			}
467
468			struct UserHost *
469			hash_find_userhost(const char *host)
470			{
471			unsigned int hashv = strhash(host);
472			struct UserHost *userhost;
473
474			if ((userhost = userhostTable[hashv]))
475			{
476			if (irccmp(host, userhost->host))
477			{
478			struct UserHost *prev;
479
480			while (prev = userhost, (userhost = userhost->next) != NULL)
481			{
482			if (!irccmp(host, userhost->host))
483			{
484			prev->next = userhost->next;
485			userhost->next = userhostTable[hashv];
486			userhostTable[hashv] = userhost;
487			break;
488			}
489			}
490			}
491			}
492
493			return userhost;
494			}
495
496			/* count_user_host()
497			*
498			* inputs - user name
499			* - hostname
500			* - int flag 1 if global, 0 if local
501			* - pointer to where global count should go
502			* - pointer to where local count should go
503			* - pointer to where identd count should go (local clients only)
504			* output - none
505			* side effects -
506			*/
507			void
508	michael	1644	count_user_host(const char user, const char host, unsigned int *global_p,
509			unsigned int local_p, unsigned int icount_p)
510	adx	30	{
511			dlink_node *ptr;
512			struct UserHost *found_userhost;
513			struct NameHost *nameh;
514
515			if ((found_userhost = hash_find_userhost(host)) == NULL)
516			return;
517
518			DLINK_FOREACH(ptr, found_userhost->list.head)
519			{
520			nameh = ptr->data;
521
522			if (!irccmp(user, nameh->name))
523			{
524			if (global_p != NULL)
525			*global_p = nameh->gcount;
526			if (local_p != NULL)
527			*local_p = nameh->lcount;
528			if (icount_p != NULL)
529			*icount_p = nameh->icount;
530			return;
531			}
532			}
533			}
534
535	michael	1396	/* find_or_add_userhost()
536			*
537			* inputs - host name
538			* output - none
539			* side effects - find UserHost * for given host name
540			*/
541			static struct UserHost *
542			find_or_add_userhost(const char *host)
543			{
544			struct UserHost *userhost;
545
546			if ((userhost = hash_find_userhost(host)) != NULL)
547			return userhost;
548
549	michael	1654	userhost = mp_pool_get(userhost_pool);
550
551			memset(userhost, 0, sizeof(*userhost));
552	michael	1396	strlcpy(userhost->host, host, sizeof(userhost->host));
553			hash_add_userhost(userhost);
554
555			return userhost;
556			}
557
558	adx	30	/* add_user_host()
559			*
560			* inputs - user name
561			* - hostname
562			* - int flag 1 if global, 0 if local
563			* output - none
564			* side effects - add given user@host to hash tables
565			*/
566			void
567			add_user_host(const char user, const char host, int global)
568			{
569			dlink_node *ptr;
570			struct UserHost *found_userhost;
571			struct NameHost *nameh;
572			int hasident = 1;
573
574			if (*user == '~')
575			{
576			hasident = 0;
577			++user;
578			}
579
580			if ((found_userhost = find_or_add_userhost(host)) == NULL)
581			return;
582
583			DLINK_FOREACH(ptr, found_userhost->list.head)
584			{
585			nameh = ptr->data;
586
587			if (!irccmp(user, nameh->name))
588			{
589			nameh->gcount++;
590	michael	1396
591	adx	30	if (!global)
592			{
593	michael	1396	if (hasident)
594			nameh->icount++;
595			nameh->lcount++;
596	adx	30	}
597	michael	1396
598	adx	30	return;
599			}
600			}
601
602	michael	1654	nameh = mp_pool_get(namehost_pool);
603			memset(nameh, 0, sizeof(*nameh));
604	adx	30	strlcpy(nameh->name, user, sizeof(nameh->name));
605
606			nameh->gcount = 1;
607	michael	1396
608	adx	30	if (!global)
609			{
610			if (hasident)
611			nameh->icount = 1;
612			nameh->lcount = 1;
613			}
614
615			dlinkAdd(nameh, &nameh->node, &found_userhost->list);
616			}
617
618			/* delete_user_host()
619			*
620			* inputs - user name
621			* - hostname
622			* - int flag 1 if global, 0 if local
623			* output - none
624			* side effects - delete given user@host to hash tables
625			*/
626			void
627			delete_user_host(const char user, const char host, int global)
628			{
629			dlink_node ptr = NULL, next_ptr = NULL;
630			struct UserHost *found_userhost;
631			struct NameHost *nameh;
632			int hasident = 1;
633
634			if (*user == '~')
635			{
636			hasident = 0;
637			++user;
638			}
639
640			if ((found_userhost = hash_find_userhost(host)) == NULL)
641			return;
642
643			DLINK_FOREACH_SAFE(ptr, next_ptr, found_userhost->list.head)
644			{
645			nameh = ptr->data;
646
647			if (!irccmp(user, nameh->name))
648			{
649			if (nameh->gcount > 0)
650			nameh->gcount--;
651			if (!global)
652			{
653	michael	1396	if (nameh->lcount > 0)
654			nameh->lcount--;
655			if (hasident && nameh->icount > 0)
656			nameh->icount--;
657	adx	30	}
658
659			if (nameh->gcount == 0 && nameh->lcount == 0)
660			{
661	michael	1396	dlinkDelete(&nameh->node, &found_userhost->list);
662	michael	1654	mp_pool_release(nameh);
663	adx	30	}
664
665			if (dlink_list_length(&found_userhost->list) == 0)
666			{
667	michael	1396	hash_del_userhost(found_userhost);
668	michael	1654	mp_pool_release(found_userhost);
669	adx	30	}
670
671			return;
672			}
673			}
674			}
675
676			/*
677			* Safe list code.
678			*
679			* The idea is really quite simple. As the link lists pointed to in
680			* each "bucket" of the channel hash table are traversed atomically
681			* there is no locking needed. Overall, yes, inconsistent reported
682			* state can still happen, but normally this isn't a big deal.
683			* I don't like sticking the code into hash.c but oh well. Moreover,
684			* if a hash isn't used in future, oops.
685			*
686			* - Dianora
687			*/
688
689			/* exceeding_sendq()
690			*
691			* inputs - pointer to client to check
692			* output - 1 if client is in danger of blowing its sendq
693			* 0 if it is not.
694			* side effects -
695			*
696			* Sendq limit is fairly conservative at 1/2 (In original anyway)
697			*/
698			static int
699			exceeding_sendq(struct Client *to)
700			{
701	michael	1632	if (dbuf_length(&to->localClient->buf_sendq) > (get_sendq(&to->localClient->confs) / 2))
702	adx	30	return 1;
703			else
704			return 0;
705			}
706
707			void
708			free_list_task(struct ListTask lt, struct Client source_p)
709			{
710	michael	1826	dlink_node dl = NULL, dln = NULL;
711	adx	30
712			if ((dl = dlinkFindDelete(&listing_client_list, source_p)) != NULL)
713			free_dlink_node(dl);
714
715			DLINK_FOREACH_SAFE(dl, dln, lt->show_mask.head)
716			{
717			MyFree(dl->data);
718			free_dlink_node(dl);
719			}
720
721			DLINK_FOREACH_SAFE(dl, dln, lt->hide_mask.head)
722			{
723			MyFree(dl->data);
724			free_dlink_node(dl);
725			}
726
727			MyFree(lt);
728
729			if (MyConnect(source_p))
730			source_p->localClient->list_task = NULL;
731			}
732
733			/* list_allow_channel()
734			*
735			* inputs - channel name
736			* - pointer to a list task
737			* output - 1 if the channel is to be displayed
738			* 0 otherwise
739			* side effects -
740			*/
741			static int
742	michael	1826	list_allow_channel(const char chname, const struct ListTask lt)
743	adx	30	{
744	michael	1826	const dlink_node *dl = NULL;
745	adx	30
746			DLINK_FOREACH(dl, lt->show_mask.head)
747	michael	1653	if (match(dl->data, chname) != 0)
748	adx	30	return 0;
749
750			DLINK_FOREACH(dl, lt->hide_mask.head)
751	michael	1653	if (match(dl->data, chname) == 0)
752	adx	30	return 0;
753
754			return 1;
755			}
756
757			/* list_one_channel()
758			*
759			* inputs - client pointer to return result to
760			* - pointer to channel to list
761			* - pointer to ListTask structure
762			* output - none
763			* side effects -
764			*/
765			static void
766			list_one_channel(struct Client source_p, struct Channel chptr,
767	michael	896	struct ListTask *list_task)
768	adx	30	{
769	michael	896	if (SecretChannel(chptr) && !IsMember(source_p, chptr))
770	adx	30	return;
771	michael	1013	if (dlink_list_length(&chptr->members) < list_task->users_min \|\|
772			dlink_list_length(&chptr->members) > list_task->users_max \|\|
773	adx	30	(chptr->channelts != 0 &&
774			((unsigned int)chptr->channelts < list_task->created_min \|\|
775			(unsigned int)chptr->channelts > list_task->created_max)) \|\|
776			(unsigned int)chptr->topic_time < list_task->topicts_min \|\|
777			(chptr->topic_time ? (unsigned int)chptr->topic_time : UINT_MAX) >
778			list_task->topicts_max)
779			return;
780
781			if (!list_allow_channel(chptr->chname, list_task))
782			return;
783			sendto_one(source_p, form_str(RPL_LIST), me.name, source_p->name,
784			chptr->chname, dlink_list_length(&chptr->members),
785	michael	1203	chptr->topic);
786	adx	30	}
787
788			/* safe_list_channels()
789			*
790			* inputs - pointer to client requesting list
791			* output - 0/1
792			* side effects - safely list all channels to source_p
793			*
794			* Walk the channel buckets, ensure all pointers in a bucket are
795			* traversed before blocking on a sendq. This means, no locking is needed.
796			*
797			* N.B. This code is "remote" safe, but is not currently used for
798			* remote clients.
799			*
800			* - Dianora
801			*/
802			void
803			safe_list_channels(struct Client source_p, struct ListTask list_task,
804	michael	896	int only_unmasked_channels)
805	adx	30	{
806			struct Channel *chptr = NULL;
807
808			if (!only_unmasked_channels)
809			{
810	michael	1013	unsigned int i;
811	adx	30
812	michael	896	for (i = list_task->hash_index; i < HASHSIZE; ++i)
813	adx	30	{
814			if (exceeding_sendq(source_p->from))
815			{
816			list_task->hash_index = i;
817	michael	880	return; /* still more to do */
818	adx	30	}
819
820			for (chptr = channelTable[i]; chptr; chptr = chptr->hnextch)
821	michael	896	list_one_channel(source_p, chptr, list_task);
822	adx	30	}
823			}
824			else
825			{
826			dlink_node *dl;
827
828			DLINK_FOREACH(dl, list_task->show_mask.head)
829			if ((chptr = hash_find_channel(dl->data)) != NULL)
830	michael	896	list_one_channel(source_p, chptr, list_task);
831	adx	30	}
832
833			free_list_task(list_task, source_p);
834			sendto_one(source_p, form_str(RPL_LISTEND),
835			me.name, source_p->name);
836			}