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 "hash.h"
#include "id.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 "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];
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)
{
  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_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;

  dlinkFindDelete(&listing_client_list, source_p);

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

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