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