trunk/src/hash.c

/*
 *  ircd-hybrid: an advanced, lightweight Internet Relay Chat Daemon (ircd)
 *
 *  Copyright (c) 1997-2016 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
 *  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 "id.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 "user.h"


static unsigned int hashf_xor_key;

/* 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];


/* hash_init()
 *
 * inputs       - NONE
 * output       - NONE
 * side effects - Initialize the maps used by hash
 *                functions and clear the tables
 */
void
hash_init(void)
{
  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; ++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)
{
  const 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)
{
  const unsigned int hashv = strhash(chptr->name);

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

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

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

void
hash_add_id(struct Client *client_p)
{
  const 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)
{
  const 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)
{
  const 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)
{
  const 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)
{
  const unsigned int hashv = strhash(chptr->name);
  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)
{
  const 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)
{
  const 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)
{
  const 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)
{
  const unsigned int hashv = strhash(name);
  struct Channel *chptr = NULL;

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

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

  return chptr;
}

struct UserHost *
hash_find_userhost(const char *host)
{
  const 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;
}

/* 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;
}

/*
 * 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->connection->buf_sendq) > (get_sendq(&to->connection->confs) / 2))
    return 1;
  else
    return 0;
}

void
free_list_task(struct Client *source_p)
{
  struct ListTask *const lt = source_p->connection->list_task;
  dlink_node *node = NULL, *node_next = NULL;

  dlinkDelete(&lt->node, &listing_client_list);

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

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

  MyFree(lt);
  source_p->connection->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 *name, const struct ListTask *lt)
{
  const dlink_node *node = NULL;

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

  DLINK_FOREACH(node, lt->hide_mask.head)
    if (match(node->data, name) == 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)
{
  const struct ListTask *const lt = source_p->connection->list_task;
  char listbuf[MODEBUFLEN] = "";
  char modebuf[MODEBUFLEN] = "";
  char parabuf[MODEBUFLEN] = "";

  if (SecretChannel(chptr) &&
      !(HasUMode(source_p, UMODE_ADMIN) || IsMember(source_p, chptr)))
    return;

  if (dlink_list_length(&chptr->members) < lt->users_min ||
      dlink_list_length(&chptr->members) > lt->users_max ||
      (chptr->creationtime != 0 &&
       ((unsigned int)chptr->creationtime < lt->created_min ||
        (unsigned int)chptr->creationtime > 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 (lt->topic[0] && match(lt->topic, chptr->topic))
    return;

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

  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->name,
                     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.
 *
 * - Dianora
 */
void
safe_list_channels(struct Client *source_p, int only_unmasked_channels)
{
  struct ListTask *const lt = source_p->connection->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 *node = NULL;

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

  free_list_task(source_p);
  sendto_one_numeric(source_p, &me, RPL_LISTEND);
}
Revision:	7006
Committed:	Fri Jan 1 00:07:54 2016 UTC (9 years, 7 months ago) by michael
Content type:	text/x-csrc
File size:	16133 byte(s)
Log Message:	- Update copyright years
#	User	Rev	Content
1	adx	30	/*
2	michael	2916	* ircd-hybrid: an advanced, lightweight Internet Relay Chat Daemon (ircd)
3	adx	30	*
4	michael	7006	* Copyright (c) 1997-2016 ircd-hybrid development team
5	adx	30	*
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	michael	4565	* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
19	adx	30	* USA
20			*/
21
22	michael	2916	/*! \file hash.c
23			* \brief Hash table management.
24			* \version $Id$
25			*/
26
27	adx	30	#include "stdinc.h"
28	michael	1011	#include "list.h"
29	michael	1309	#include "conf.h"
30	adx	30	#include "channel.h"
31			#include "channel_mode.h"
32			#include "client.h"
33			#include "modules.h"
34			#include "hash.h"
35	michael	6161	#include "id.h"
36	adx	30	#include "resv.h"
37	michael	982	#include "rng_mt.h"
38	adx	30	#include "userhost.h"
39			#include "irc_string.h"
40			#include "ircd.h"
41			#include "numeric.h"
42			#include "send.h"
43			#include "memory.h"
44	michael	1654	#include "mempool.h"
45	adx	30	#include "dbuf.h"
46	michael	3347	#include "user.h"
47	adx	30
48
49	michael	5460	static unsigned int hashf_xor_key;
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	michael	2916	* rebuild the transformation maps, I kept the tables of equal size
54	adx	30	* 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	michael	6393	/* hash_init()
63	adx	30	*
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	michael	982	hashf_xor_key = genrand_int32() % 256; /* better than nothing --adx */
73	adx	30	}
74
75			/*
76			* New hash function based on the Fowler/Noll/Vo (FNV) algorithm from
77			* http://www.isthe.com/chongo/tech/comp/fnv/
78			*
79			* Here, we use the FNV-1 method, which gives slightly better results
80			* than FNV-1a. -Michael
81			*/
82			unsigned int
83			strhash(const char *name)
84			{
85			const unsigned char p = (const unsigned char )name;
86			unsigned int hval = FNV1_32_INIT;
87
88	michael	1826	if (EmptyString(p))
89	adx	30	return 0;
90	michael	4890
91			for (; *p; ++p)
92	adx	30	{
93			hval += (hval << 1) + (hval << 4) + (hval << 7) +
94			(hval << 8) + (hval << 24);
95	michael	982	hval ^= (ToLower(*p) ^ hashf_xor_key);
96	adx	30	}
97
98	michael	982	return (hval >> FNV1_32_BITS) ^ (hval & ((1 << FNV1_32_BITS) - 1));
99	adx	30	}
100
101			/************************ Externally visible functions ******************/
102
103			/* Optimization note: in these functions I supposed that the CSE optimization
104			* (Common Subexpression Elimination) does its work decently, this means that
105			* I avoided introducing new variables to do the work myself and I did let
106			* the optimizer play with more free registers, actual tests proved this
107			* solution to be faster than doing things like tmp2=tmp->hnext... and then
108			* use tmp2 myself which would have given less freedom to the optimizer.
109			*/
110
111			/* hash_add_client()
112			*
113			* inputs - pointer to client
114			* output - NONE
115			* side effects - Adds a client's name in the proper hash linked
116			* list, can't fail, client_p must have a non-null
117			* name or expect a coredump, the name is infact
118			* taken from client_p->name
119			*/
120			void
121			hash_add_client(struct Client *client_p)
122			{
123	michael	4977	const unsigned int hashv = strhash(client_p->name);
124	adx	30
125			client_p->hnext = clientTable[hashv];
126			clientTable[hashv] = client_p;
127			}
128
129			/* hash_add_channel()
130			*
131			* inputs - pointer to channel
132			* output - NONE
133			* side effects - Adds a channel's name in the proper hash linked
134			* list, can't fail. chptr must have a non-null name
135			* or expect a coredump. As before the name is taken
136			* from chptr->name, we do hash its entire lenght
137			* since this proved to be statistically faster
138			*/
139			void
140			hash_add_channel(struct Channel *chptr)
141			{
142	michael	4977	const unsigned int hashv = strhash(chptr->name);
143	adx	30
144			chptr->hnextch = channelTable[hashv];
145			channelTable[hashv] = chptr;
146			}
147
148			void
149			hash_add_userhost(struct UserHost *userhost)
150			{
151	michael	4977	const unsigned int hashv = strhash(userhost->host);
152	adx	30
153			userhost->next = userhostTable[hashv];
154			userhostTable[hashv] = userhost;
155			}
156
157			void
158			hash_add_id(struct Client *client_p)
159			{
160	michael	4977	const unsigned int hashv = strhash(client_p->id);
161	adx	30
162			client_p->idhnext = idTable[hashv];
163			idTable[hashv] = client_p;
164			}
165
166			/* hash_del_id()
167			*
168			* inputs - pointer to client
169			* output - NONE
170			* side effects - Removes an ID from the hash linked list
171			*/
172			void
173			hash_del_id(struct Client *client_p)
174			{
175	michael	4977	const unsigned int hashv = strhash(client_p->id);
176	adx	30	struct Client *tmp = idTable[hashv];
177
178	michael	3241	if (tmp)
179	adx	30	{
180			if (tmp == client_p)
181			{
182			idTable[hashv] = client_p->idhnext;
183			client_p->idhnext = client_p;
184			}
185			else
186			{
187			while (tmp->idhnext != client_p)
188			if ((tmp = tmp->idhnext) == NULL)
189			return;
190
191			tmp->idhnext = tmp->idhnext->idhnext;
192			client_p->idhnext = client_p;
193			}
194			}
195			}
196
197			/* hash_del_client()
198			*
199			* inputs - pointer to client
200			* output - NONE
201			* side effects - Removes a Client's name from the hash linked list
202			*/
203			void
204			hash_del_client(struct Client *client_p)
205			{
206	michael	4977	const unsigned int hashv = strhash(client_p->name);
207	adx	30	struct Client *tmp = clientTable[hashv];
208
209	michael	3241	if (tmp)
210	adx	30	{
211			if (tmp == client_p)
212			{
213			clientTable[hashv] = client_p->hnext;
214			client_p->hnext = client_p;
215			}
216			else
217			{
218			while (tmp->hnext != client_p)
219			if ((tmp = tmp->hnext) == NULL)
220			return;
221
222			tmp->hnext = tmp->hnext->hnext;
223			client_p->hnext = client_p;
224			}
225			}
226			}
227
228			/* hash_del_userhost()
229			*
230			* inputs - pointer to userhost
231			* output - NONE
232			* side effects - Removes a userhost from the hash linked list
233			*/
234			void
235			hash_del_userhost(struct UserHost *userhost)
236			{
237	michael	4977	const unsigned int hashv = strhash(userhost->host);
238	adx	30	struct UserHost *tmp = userhostTable[hashv];
239
240	michael	3241	if (tmp)
241	adx	30	{
242			if (tmp == userhost)
243			{
244			userhostTable[hashv] = userhost->next;
245			userhost->next = userhost;
246			}
247			else
248			{
249			while (tmp->next != userhost)
250			if ((tmp = tmp->next) == NULL)
251			return;
252
253			tmp->next = tmp->next->next;
254			userhost->next = userhost;
255			}
256			}
257			}
258
259			/* hash_del_channel()
260			*
261			* inputs - pointer to client
262			* output - NONE
263			* side effects - Removes the channel's name from the corresponding
264			* hash linked list
265			*/
266			void
267			hash_del_channel(struct Channel *chptr)
268			{
269	michael	4977	const unsigned int hashv = strhash(chptr->name);
270	adx	30	struct Channel *tmp = channelTable[hashv];
271
272	michael	3241	if (tmp)
273	adx	30	{
274			if (tmp == chptr)
275			{
276			channelTable[hashv] = chptr->hnextch;
277			chptr->hnextch = chptr;
278			}
279			else
280			{
281			while (tmp->hnextch != chptr)
282			if ((tmp = tmp->hnextch) == NULL)
283			return;
284
285			tmp->hnextch = tmp->hnextch->hnextch;
286			chptr->hnextch = chptr;
287			}
288			}
289			}
290
291	michael	1169	/* hash_find_client()
292	adx	30	*
293			* inputs - pointer to name
294			* output - NONE
295			* side effects - New semantics: finds a client whose name is 'name'
296			* if can't find one returns NULL. If it finds one moves
297			* it to the top of the list and returns it.
298			*/
299			struct Client *
300	michael	1169	hash_find_client(const char *name)
301	adx	30	{
302	michael	4977	const unsigned int hashv = strhash(name);
303	adx	30	struct Client *client_p;
304
305	michael	3241	if ((client_p = clientTable[hashv]))
306	adx	30	{
307			if (irccmp(name, client_p->name))
308			{
309			struct Client *prev;
310
311	michael	3241	while (prev = client_p, (client_p = client_p->hnext))
312	adx	30	{
313			if (!irccmp(name, client_p->name))
314			{
315			prev->hnext = client_p->hnext;
316			client_p->hnext = clientTable[hashv];
317			clientTable[hashv] = client_p;
318			break;
319			}
320			}
321			}
322			}
323
324			return client_p;
325			}
326
327			struct Client *
328			hash_find_id(const char *name)
329			{
330	michael	4977	const unsigned int hashv = strhash(name);
331	adx	30	struct Client *client_p;
332
333	michael	3242	if ((client_p = idTable[hashv]))
334	adx	30	{
335	michael	880	if (strcmp(name, client_p->id))
336	adx	30	{
337			struct Client *prev;
338
339	michael	3242	while (prev = client_p, (client_p = client_p->idhnext))
340	adx	30	{
341	michael	880	if (!strcmp(name, client_p->id))
342	adx	30	{
343			prev->idhnext = client_p->idhnext;
344			client_p->idhnext = idTable[hashv];
345			idTable[hashv] = client_p;
346			break;
347			}
348			}
349			}
350			}
351
352			return client_p;
353			}
354
355			struct Client *
356	michael	1169	hash_find_server(const char *name)
357	adx	30	{
358	michael	4977	const unsigned int hashv = strhash(name);
359	adx	30	struct Client *client_p = NULL;
360
361			if (IsDigit(*name) && strlen(name) == IRC_MAXSID)
362	michael	1397	return hash_find_id(name);
363	adx	30
364	michael	3242	if ((client_p = clientTable[hashv]))
365	adx	30	{
366			if ((!IsServer(client_p) && !IsMe(client_p)) \|\|
367			irccmp(name, client_p->name))
368			{
369			struct Client *prev;
370
371	michael	3242	while (prev = client_p, (client_p = client_p->hnext))
372	adx	30	{
373			if ((IsServer(client_p) \|\| IsMe(client_p)) &&
374			!irccmp(name, client_p->name))
375			{
376			prev->hnext = client_p->hnext;
377			client_p->hnext = clientTable[hashv];
378			clientTable[hashv] = client_p;
379			break;
380			}
381			}
382			}
383			}
384
385	michael	1118	return client_p;
386	adx	30	}
387
388			/* hash_find_channel()
389			*
390			* inputs - pointer to name
391			* output - NONE
392	michael	2916	* side effects - New semantics: finds a channel whose name is 'name',
393	adx	30	* if can't find one returns NULL, if can find it moves
394			* it to the top of the list and returns it.
395			*/
396			struct Channel *
397			hash_find_channel(const char *name)
398			{
399	michael	4977	const unsigned int hashv = strhash(name);
400	adx	30	struct Channel *chptr = NULL;
401
402	michael	3242	if ((chptr = channelTable[hashv]))
403	adx	30	{
404	michael	4618	if (irccmp(name, chptr->name))
405	adx	30	{
406			struct Channel *prev;
407
408	michael	3242	while (prev = chptr, (chptr = chptr->hnextch))
409	adx	30	{
410	michael	4618	if (!irccmp(name, chptr->name))
411	adx	30	{
412			prev->hnextch = chptr->hnextch;
413			chptr->hnextch = channelTable[hashv];
414			channelTable[hashv] = chptr;
415			break;
416			}
417			}
418			}
419			}
420
421			return chptr;
422			}
423
424	michael	6393	struct UserHost *
425			hash_find_userhost(const char *host)
426			{
427			const unsigned int hashv = strhash(host);
428			struct UserHost *userhost;
429
430			if ((userhost = userhostTable[hashv]))
431			{
432			if (irccmp(host, userhost->host))
433			{
434			struct UserHost *prev;
435
436			while (prev = userhost, (userhost = userhost->next))
437			{
438			if (!irccmp(host, userhost->host))
439			{
440			prev->next = userhost->next;
441			userhost->next = userhostTable[hashv];
442			userhostTable[hashv] = userhost;
443			break;
444			}
445			}
446			}
447			}
448
449			return userhost;
450			}
451
452	adx	30	/* hash_get_bucket(int type, unsigned int hashv)
453			*
454			* inputs - hash value (must be between 0 and HASHSIZE - 1)
455			* output - NONE
456			* returns - pointer to first channel in channelTable[hashv]
457			* if that exists;
458			* NULL if there is no channel in that place;
459			* NULL if hashv is an invalid number.
460			* side effects - NONE
461			*/
462			void *
463			hash_get_bucket(int type, unsigned int hashv)
464			{
465			assert(hashv < HASHSIZE);
466	michael	4977
467	adx	30	if (hashv >= HASHSIZE)
468	michael	6393	return NULL;
469	adx	30
470			switch (type)
471			{
472			case HASH_TYPE_ID:
473			return idTable[hashv];
474			break;
475			case HASH_TYPE_CHANNEL:
476			return channelTable[hashv];
477			break;
478			case HASH_TYPE_CLIENT:
479			return clientTable[hashv];
480			break;
481			case HASH_TYPE_USERHOST:
482			return userhostTable[hashv];
483			break;
484			default:
485			assert(0);
486			}
487
488			return NULL;
489			}
490
491			/*
492			* Safe list code.
493			*
494			* The idea is really quite simple. As the link lists pointed to in
495			* each "bucket" of the channel hash table are traversed atomically
496			* there is no locking needed. Overall, yes, inconsistent reported
497			* state can still happen, but normally this isn't a big deal.
498			* I don't like sticking the code into hash.c but oh well. Moreover,
499			* if a hash isn't used in future, oops.
500			*
501			* - Dianora
502			*/
503
504			/* exceeding_sendq()
505			*
506			* inputs - pointer to client to check
507			* output - 1 if client is in danger of blowing its sendq
508			* 0 if it is not.
509			* side effects -
510			*
511			* Sendq limit is fairly conservative at 1/2 (In original anyway)
512			*/
513			static int
514	michael	2757	exceeding_sendq(const struct Client *to)
515	adx	30	{
516	michael	4588	if (dbuf_length(&to->connection->buf_sendq) > (get_sendq(&to->connection->confs) / 2))
517	adx	30	return 1;
518			else
519			return 0;
520			}
521
522			void
523	michael	3289	free_list_task(struct Client *source_p)
524	adx	30	{
525	michael	4870	struct ListTask *const lt = source_p->connection->list_task;
526	michael	4815	dlink_node node = NULL, node_next = NULL;
527	adx	30
528	michael	6385	dlinkDelete(&lt->node, &listing_client_list);
529	adx	30
530	michael	4815	DLINK_FOREACH_SAFE(node, node_next, lt->show_mask.head)
531	adx	30	{
532	michael	4815	MyFree(node->data);
533			free_dlink_node(node);
534	adx	30	}
535
536	michael	4815	DLINK_FOREACH_SAFE(node, node_next, lt->hide_mask.head)
537	adx	30	{
538	michael	4815	MyFree(node->data);
539			free_dlink_node(node);
540	adx	30	}
541
542			MyFree(lt);
543	michael	4868	source_p->connection->list_task = NULL;
544	adx	30	}
545
546			/* list_allow_channel()
547			*
548			* inputs - channel name
549			* - pointer to a list task
550			* output - 1 if the channel is to be displayed
551			* 0 otherwise
552			* side effects -
553			*/
554			static int
555	michael	4618	list_allow_channel(const char name, const struct ListTask lt)
556	adx	30	{
557	michael	4815	const dlink_node *node = NULL;
558	adx	30
559	michael	4815	DLINK_FOREACH(node, lt->show_mask.head)
560			if (match(node->data, name) != 0)
561	adx	30	return 0;
562
563	michael	4815	DLINK_FOREACH(node, lt->hide_mask.head)
564			if (match(node->data, name) == 0)
565	adx	30	return 0;
566
567			return 1;
568			}
569
570			/* list_one_channel()
571			*
572			* inputs - client pointer to return result to
573			* - pointer to channel to list
574			* - pointer to ListTask structure
575			* output - none
576			* side effects -
577			*/
578			static void
579	michael	3288	list_one_channel(struct Client source_p, struct Channel chptr)
580	adx	30	{
581	michael	4870	const struct ListTask *const lt = source_p->connection->list_task;
582	michael	2616	char listbuf[MODEBUFLEN] = "";
583			char modebuf[MODEBUFLEN] = "";
584			char parabuf[MODEBUFLEN] = "";
585
586	michael	2495	if (SecretChannel(chptr) &&
587	michael	3428	!(HasUMode(source_p, UMODE_ADMIN) \|\| IsMember(source_p, chptr)))
588	adx	30	return;
589	michael	4890
590	michael	3288	if (dlink_list_length(&chptr->members) < lt->users_min \|\|
591			dlink_list_length(&chptr->members) > lt->users_max \|\|
592	michael	4818	(chptr->creationtime != 0 &&
593			((unsigned int)chptr->creationtime < lt->created_min \|\|
594			(unsigned int)chptr->creationtime > lt->created_max)) \|\|
595	michael	3288	(unsigned int)chptr->topic_time < lt->topicts_min \|\|
596	adx	30	(chptr->topic_time ? (unsigned int)chptr->topic_time : UINT_MAX) >
597	michael	3288	lt->topicts_max)
598	adx	30	return;
599
600	michael	4489	if (lt->topic[0] && match(lt->topic, chptr->topic))
601			return;
602
603	michael	4618	if (!list_allow_channel(chptr->name, lt))
604	adx	30	return;
605	michael	2616
606	michael	4486	channel_modes(chptr, source_p, modebuf, parabuf);
607	michael	2616
608	michael	4486	if (chptr->topic[0])
609			snprintf(listbuf, sizeof(listbuf), "[%s] ", modebuf);
610			else
611			snprintf(listbuf, sizeof(listbuf), "[%s]", modebuf);
612	michael	2616
613	michael	4618	sendto_one_numeric(source_p, &me, RPL_LIST, chptr->name,
614	michael	3109	dlink_list_length(&chptr->members),
615			listbuf, chptr->topic);
616	adx	30	}
617
618			/* safe_list_channels()
619			*
620			* inputs - pointer to client requesting list
621			* output - 0/1
622			* side effects - safely list all channels to source_p
623			*
624			* Walk the channel buckets, ensure all pointers in a bucket are
625			* traversed before blocking on a sendq. This means, no locking is needed.
626			*
627			* - Dianora
628			*/
629			void
630	michael	3288	safe_list_channels(struct Client *source_p, int only_unmasked_channels)
631	adx	30	{
632	michael	4870	struct ListTask *const lt = source_p->connection->list_task;
633	adx	30	struct Channel *chptr = NULL;
634
635			if (!only_unmasked_channels)
636			{
637	michael	3288	for (unsigned int i = lt->hash_index; i < HASHSIZE; ++i)
638	adx	30	{
639	michael	3291	if (exceeding_sendq(source_p))
640	adx	30	{
641	michael	3288	lt->hash_index = i;
642			return; /* Still more to do */
643	adx	30	}
644
645			for (chptr = channelTable[i]; chptr; chptr = chptr->hnextch)
646	michael	3288	list_one_channel(source_p, chptr);
647	adx	30	}
648			}
649			else
650			{
651	michael	4815	dlink_node *node = NULL;
652	adx	30
653	michael	4815	DLINK_FOREACH(node, lt->show_mask.head)
654			if ((chptr = hash_find_channel(node->data)))
655	michael	3288	list_one_channel(source_p, chptr);
656	adx	30	}
657
658	michael	3289	free_list_task(source_p);
659	michael	3109	sendto_one_numeric(source_p, &me, RPL_LISTEND);
660	adx	30	}