trunk/src/hash.c

/*
 *  ircd-hybrid: an advanced, lightweight Internet Relay Chat Daemon (ircd)
 *
 *  Copyright (c) 1997-2018 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 "hash.h"
#include "id.h"
#include "rng_mt.h"
#include "irc_string.h"
#include "ircd.h"
#include "numeric.h"
#include "send.h"
#include "memory.h"
#include "dbuf.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];


/* hash_init()
 *
 * inputs       - NONE
 * output       - NONE
 * side effects - Initialize the maps used by hash
 *                functions and clear the tables
 */
void
hash_init(void)
{
  do
    hashf_xor_key = genrand_int32() % 256;  /* better than nothing --adx */
  while (!hashf_xor_key);
}

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

/* 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;
    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 bool
exceeding_sendq(const struct Client *to)
{
  if (dbuf_length(&to->connection->buf_sendq) > (get_sendq(&to->connection->confs) / 2))
    return true;
  else
    return false;
}

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

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

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

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

  xfree(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 bool
list_allow_channel(const char *name, const struct ListTask *lt)
{
  dlink_node *node;

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

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

  return true;
}

/* 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) == false)
    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, bool only_unmasked_channels)
{
  struct ListTask *const lt = source_p->connection->list_task;
  struct Channel *chptr = NULL;

  if (only_unmasked_channels == false)
  {
    for (unsigned int i = lt->hash_index; i < HASHSIZE; ++i)
    {
      if (exceeding_sendq(source_p) == true)
      {
        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;

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