trunk/src/hash.c

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


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


/*
 * 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)
{
  static unsigned int hashf_xor_key = 0;
  const unsigned char *p = (const unsigned char *)name;
  unsigned int hval = FNV1_32_INIT;

  if (EmptyString(p))
    return 0;

  if (hashf_xor_key == 0)
    do
      hashf_xor_key = genrand_int32() % 256;  /* better than nothing --adx */
    while (hashf_xor_key == 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 must have a non-null
 *                name or expect a coredump, the name is infact
 *                taken from client->name
 */
void
hash_add_client(struct Client *client)
{
  const unsigned int hashv = strhash(client->name);

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

/* 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. channel must have a non-null name
 *                or expect a coredump. As before the name is taken
 *                from channel->name, we do hash its entire lenght
 *                since this proved to be statistically faster
 */
void
hash_add_channel(struct Channel *channel)
{
  const unsigned int hashv = strhash(channel->name);

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

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

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

/* 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)
{
  const unsigned int hashv = strhash(client->id);
  struct Client *tmp = idTable[hashv];

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

      tmp->idhnext = tmp->idhnext->idhnext;
      client->idhnext = client;
    }
  }
}

/* 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)
{
  const unsigned int hashv = strhash(client->name);
  struct Client *tmp = clientTable[hashv];

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

      tmp->hnext = tmp->hnext->hnext;
      client->hnext = client;
    }
  }
}

/* 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 *channel)
{
  const unsigned int hashv = strhash(channel->name);
  struct Channel *tmp = channelTable[hashv];

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

      tmp->hnextch = tmp->hnextch->hnextch;
      channel->hnextch = channel;
    }
  }
}

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

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

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

  return client;
}

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

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

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

  return client;
}

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

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

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

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

  return client;
}

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

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

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

  return channel;
}

/* 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 *client)
{
  struct ListTask *const lt = client->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);
  client->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 *client, struct Channel *channel)
{
  const struct ListTask *const lt = client->connection->list_task;
  const struct ChannelMember *member = NULL;
  char listbuf[MODEBUFLEN] = "";
  char modebuf[MODEBUFLEN] = "";
  char parabuf[MODEBUFLEN] = "";

  if (SecretChannel(channel) &&
      !(HasUMode(client, UMODE_ADMIN) || (member = member_find_link(client, channel))))
    return;

  if (dlink_list_length(&channel->members) < lt->users_min ||
      dlink_list_length(&channel->members) > lt->users_max ||
      (channel->creation_time != 0 &&
       ((unsigned int)channel->creation_time < lt->created_min ||
        (unsigned int)channel->creation_time > lt->created_max)) ||
      (unsigned int)channel->topic_time < lt->topicts_min ||
      (channel->topic_time ? (unsigned int)channel->topic_time : UINT_MAX) >
      lt->topicts_max)
    return;

  if (lt->topic[0] && match(lt->topic, channel->topic))
    return;

  if (list_allow_channel(channel->name, lt) == false)
    return;

  channel_modes(channel, client, member, modebuf, parabuf);

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

  sendto_one_numeric(client, &me, RPL_LIST, channel->name,
                     dlink_list_length(&channel->members),
                     listbuf, channel->topic);
}

/* safe_list_channels()
 *
 * inputs       - pointer to client requesting list
 * output       - 0/1
 * side effects - safely list all channels to client
 *
 * 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 *client, bool only_unmasked_channels)
{
  struct ListTask *const lt = client->connection->list_task;
  struct Channel *channel;

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

      for (channel = channelTable[i]; channel; channel = channel->hnextch)
        list_one_channel(client, channel);
    }
  }
  else
  {
    dlink_node *node;

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

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