trunk/src/hash.c

/*
 *  ircd-hybrid: an advanced, lightweight Internet Relay Chat Daemon (ircd)
 *
 *  Copyright (c) 1997-2014 ircd-hybrid development team
 *
 *  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
 */

/*! \file hash.c
 * \brief Hash table management.
 * \version $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)
{
  userhost_pool = mp_pool_new(sizeof(struct UserHost), MP_CHUNK_SIZE_USERHOST);
  namehost_pool = mp_pool_new(sizeof(struct NameHost), MP_CHUNK_SIZE_NAMEHOST);

  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)
  {
    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)
  {
    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)
  {
    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)
  {
    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]))
  {
    if (irccmp(name, client_p->name))
    {
      struct Client *prev;

      while (prev = client_p, (client_p = client_p->hnext))
      {
        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]))
  {
    if (strcmp(name, client_p->id))
    {
      struct Client *prev;

      while (prev = client_p, (client_p = client_p->idhnext))
      {
        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]))
  {
    if ((!IsServer(client_p) && !IsMe(client_p)) ||
        irccmp(name, client_p->name))
    {
      struct Client *prev;

      while (prev = client_p, (client_p = client_p->hnext))
      {
        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]))
  {
    if (irccmp(name, chptr->chname))
    {
      struct Channel *prev;

      while (prev = chptr, (chptr = chptr->hnextch))
      {
        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))
      {
        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)
        *global_p = nameh->gcount;
      if (local_p)
        *local_p  = nameh->lcount;
      if (icount_p)
        *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 = NULL;

  if ((userhost = hash_find_userhost(host)))
    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;
  struct UserHost *found_userhost = NULL;
  unsigned int hasident = 1;

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

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

  DLINK_FOREACH(ptr, found_userhost->list.head)
  {
    struct NameHost *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(const 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 Client *source_p)
{
  struct ListTask *lt = source_p->localClient->list_task;
  dlink_node *ptr = NULL, *ptr_next = NULL;

  if ((ptr = dlinkFindDelete(&listing_client_list, source_p)))
    free_dlink_node(ptr);

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

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

  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 *ptr = NULL;

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

  DLINK_FOREACH(ptr, lt->hide_mask.head)
    if (match(ptr->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 *lt = source_p->localClient->list_task;
  char listbuf[MODEBUFLEN] = "";
  char modebuf[MODEBUFLEN] = "";
  char parabuf[MODEBUFLEN] = "";

  if (SecretChannel(chptr) &&
      !(IsMember(source_p, chptr) || HasUMode(source_p, UMODE_ADMIN)))
    return;
  if (dlink_list_length(&chptr->members) < lt->users_min ||
      dlink_list_length(&chptr->members) > lt->users_max ||
      (chptr->channelts != 0 &&
       ((unsigned int)chptr->channelts < lt->created_min ||
        (unsigned int)chptr->channelts > lt->created_max)) ||
      (unsigned int)chptr->topic_time < lt->topicts_min ||
      (chptr->topic_time ? (unsigned int)chptr->topic_time : UINT_MAX) >
      lt->topicts_max)
    return;

  if (!list_allow_channel(chptr->chname, lt))
    return;

  if (HasUMode(source_p, UMODE_ADMIN))
  {
    channel_modes(chptr, source_p, modebuf, parabuf);

    if (chptr->topic[0])
      snprintf(listbuf, sizeof(listbuf), "[%s] ", modebuf);
    else
      snprintf(listbuf, sizeof(listbuf), "[%s]",  modebuf);
  }

  sendto_one_numeric(source_p, &me, RPL_LIST, chptr->chname,
                     dlink_list_length(&chptr->members),
                     listbuf, 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, int only_unmasked_channels)
{
  struct ListTask *lt = source_p->localClient->list_task;
  struct Channel *chptr = NULL;

  if (!only_unmasked_channels)
  {
    for (unsigned int i = lt->hash_index; i < HASHSIZE; ++i)
    {
      if (exceeding_sendq(source_p))
      {
        lt->hash_index = i;
        return;  /* Still more to do */
      }

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

    DLINK_FOREACH(ptr, lt->show_mask.head)
      if ((chptr = hash_find_channel(ptr->data)))
        list_one_channel(source_p, chptr);
  }

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