trunk/src/hash.c

/*
 *  ircd-hybrid: an advanced, lightweight Internet Relay Chat Daemon (ircd)
 *
 *  Copyright (c) 1997-2015 ircd-hybrid development team
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
 *  USA
 */

/*! \file hash.c
 * \brief Hash table management.
 * \version $Id$
 */

#include "stdinc.h"
#include "list.h"
#include "conf.h"
#include "channel.h"
#include "channel_mode.h"
#include "client.h"
#include "modules.h"
#include "hash.h"
#include "id.h"
#include "resv.h"
#include "rng_mt.h"
#include "userhost.h"
#include "irc_string.h"
#include "ircd.h"
#include "numeric.h"
#include "send.h"
#include "memory.h"
#include "mempool.h"
#include "dbuf.h"
#include "user.h"


static unsigned int hashf_xor_key;

/* The actual hash tables, They MUST be of the same HASHSIZE, variable
 * size tables could be supported but the rehash routine should also
 * rebuild the transformation maps, I kept the tables of equal size
 * so that I can use one hash function.
 */
static struct Client *idTable[HASHSIZE];
static struct Client *clientTable[HASHSIZE];
static struct Channel *channelTable[HASHSIZE];
static struct UserHost *userhostTable[HASHSIZE];


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

/*
 * New hash function based on the Fowler/Noll/Vo (FNV) algorithm from
 * http://www.isthe.com/chongo/tech/comp/fnv/
 *
 * Here, we use the FNV-1 method, which gives slightly better results
 * than FNV-1a.   -Michael
 */
unsigned int
strhash(const char *name)
{
  const unsigned char *p = (const unsigned char *)name;
  unsigned int hval = FNV1_32_INIT;

  if (EmptyString(p))
    return 0;

  for (; *p; ++p)
  {
    hval += (hval << 1) + (hval <<  4) + (hval << 7) +
            (hval << 8) + (hval << 24);
    hval ^= (ToLower(*p) ^ hashf_xor_key);
  }

  return (hval >> FNV1_32_BITS) ^ (hval & ((1 << FNV1_32_BITS) - 1));
}

/************************** Externally visible functions ********************/

/* Optimization note: in these functions I supposed that the CSE optimization
 * (Common Subexpression Elimination) does its work decently, this means that
 * I avoided introducing new variables to do the work myself and I did let
 * the optimizer play with more free registers, actual tests proved this
 * solution to be faster than doing things like tmp2=tmp->hnext... and then
 * use tmp2 myself which would have given less freedom to the optimizer.
 */

/* hash_add_client()
 *
 * inputs       - pointer to client
 * output       - NONE
 * side effects - Adds a client's name in the proper hash linked
 *                list, can't fail, client_p must have a non-null
 *                name or expect a coredump, the name is infact
 *                taken from client_p->name
 */
void
hash_add_client(struct Client *client_p)
{
  const unsigned int hashv = strhash(client_p->name);

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

/* hash_add_channel()
 *
 * inputs       - pointer to channel
 * output       - NONE
 * side effects - Adds a channel's name in the proper hash linked
 *                list, can't fail. chptr must have a non-null name
 *                or expect a coredump. As before the name is taken
 *                from chptr->name, we do hash its entire lenght
 *                since this proved to be statistically faster
 */
void
hash_add_channel(struct Channel *chptr)
{
  const unsigned int hashv = strhash(chptr->name);

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

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

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

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

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

/* hash_del_id()
 *
 * inputs       - pointer to client
 * output       - NONE
 * side effects - Removes an ID from the hash linked list
 */
void
hash_del_id(struct Client *client_p)
{
  const unsigned int hashv = strhash(client_p->id);
  struct Client *tmp = idTable[hashv];

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

      tmp->idhnext = tmp->idhnext->idhnext;
      client_p->idhnext = client_p;
    }
  }
}

/* hash_del_client()
 *
 * inputs       - pointer to client
 * output       - NONE
 * side effects - Removes a Client's name from the hash linked list
 */
void
hash_del_client(struct Client *client_p)
{
  const unsigned int hashv = strhash(client_p->name);
  struct Client *tmp = clientTable[hashv];

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

      tmp->hnext = tmp->hnext->hnext;
      client_p->hnext = client_p;
    }
  }
}

/* hash_del_userhost()
 *
 * inputs       - pointer to userhost
 * output       - NONE
 * side effects - Removes a userhost from the hash linked list
 */
void
hash_del_userhost(struct UserHost *userhost)
{
  const unsigned int hashv = strhash(userhost->host);
  struct UserHost *tmp = userhostTable[hashv];

  if (tmp)
  {
    if (tmp == userhost)
    {
      userhostTable[hashv] = userhost->next;
      userhost->next = userhost;
    }
    else
    {
      while (tmp->next != userhost)
        if ((tmp = tmp->next) == NULL)
          return;

      tmp->next = tmp->next->next;
      userhost->next = userhost;
    }
  }
}

/* hash_del_channel()
 *
 * inputs       - pointer to client
 * output       - NONE
 * side effects - Removes the channel's name from the corresponding
 *                hash linked list
 */
void
hash_del_channel(struct Channel *chptr)
{
  const unsigned int hashv = strhash(chptr->name);
  struct Channel *tmp = channelTable[hashv];

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

      tmp->hnextch = tmp->hnextch->hnextch;
      chptr->hnextch = chptr;
    }
  }
}

/* hash_find_client()
 *
 * inputs       - pointer to name
 * output       - NONE
 * side effects - New semantics: finds a client whose name is 'name'
 *                if can't find one returns NULL. If it finds one moves
 *                it to the top of the list and returns it.
 */
struct Client *
hash_find_client(const char *name)
{
  const unsigned int hashv = strhash(name);
  struct Client *client_p;

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

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

  return client_p;
}

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

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

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

  return client_p;
}

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

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

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

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

  return client_p;
}

/* hash_find_channel()
 *
 * inputs       - pointer to name
 * output       - NONE
 * side effects - New semantics: finds a channel whose name is 'name',
 *                if can't find one returns NULL, if can find it moves
 *                it to the top of the list and returns it.
 */
struct Channel *
hash_find_channel(const char *name)
{
  const unsigned int hashv = strhash(name);
  struct Channel *chptr = NULL;

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

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

  return chptr;
}

struct UserHost *
hash_find_userhost(const char *host)
{
  const unsigned int hashv = strhash(host);
  struct UserHost *userhost;

  if ((userhost = userhostTable[hashv]))
  {
    if (irccmp(host, userhost->host))
    {
      struct UserHost *prev;

      while (prev = userhost, (userhost = userhost->next))
      {
        if (!irccmp(host, userhost->host))
        {
          prev->next = userhost->next;
          userhost->next = userhostTable[hashv];
          userhostTable[hashv] = userhost;
          break;
        }
      }
    }
  }

  return userhost;
}

/* hash_get_bucket(int type, unsigned int hashv)
 *
 * inputs       - hash value (must be between 0 and HASHSIZE - 1)
 * output       - NONE
 * returns      - pointer to first channel in channelTable[hashv]
 *                if that exists;
 *                NULL if there is no channel in that place;
 *                NULL if hashv is an invalid number.
 * side effects - NONE
 */
void *
hash_get_bucket(int type, unsigned int hashv)
{
  assert(hashv < HASHSIZE);

  if (hashv >= HASHSIZE)
    return NULL;

  switch (type)
  {
    case HASH_TYPE_ID:
      return idTable[hashv];
      break;
    case HASH_TYPE_CHANNEL:
      return channelTable[hashv];
      break;
    case HASH_TYPE_CLIENT:
      return clientTable[hashv];
      break;
    case HASH_TYPE_USERHOST:
      return userhostTable[hashv];
      break;
    default:
      assert(0);
  }

  return NULL;
}

/*
 * Safe list code.
 *
 * The idea is really quite simple. As the link lists pointed to in
 * each "bucket" of the channel hash table are traversed atomically
 * there is no locking needed. Overall, yes, inconsistent reported
 * state can still happen, but normally this isn't a big deal.
 * I don't like sticking the code into hash.c but oh well. Moreover,
 * if a hash isn't used in future, oops.
 *
 * - Dianora
 */

/* exceeding_sendq()
 *
 * inputs       - pointer to client to check
 * output       - 1 if client is in danger of blowing its sendq
 *                0 if it is not.
 * side effects -
 *
 * Sendq limit is fairly conservative at 1/2 (In original anyway)
 */
static int
exceeding_sendq(const struct Client *to)
{
  if (dbuf_length(&to->connection->buf_sendq) > (get_sendq(&to->connection->confs) / 2))
    return 1;
  else
    return 0;
}

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

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

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

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

  MyFree(lt);
  source_p->connection->list_task = NULL;
}

/* list_allow_channel()
 *
 * inputs       - channel name
 *              - pointer to a list task
 * output       - 1 if the channel is to be displayed
 *                0 otherwise
 * side effects -
 */
static int
list_allow_channel(const char *name, const struct ListTask *lt)
{
  const dlink_node *node = NULL;

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

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

  return 1;
}

/* list_one_channel()
 *
 * inputs       - client pointer to return result to
 *              - pointer to channel to list
 *              - pointer to ListTask structure
 * output       - none
 * side effects -
 */
static void
list_one_channel(struct Client *source_p, struct Channel *chptr)
{
  const struct ListTask *const lt = source_p->connection->list_task;
  char listbuf[MODEBUFLEN] = "";
  char modebuf[MODEBUFLEN] = "";
  char parabuf[MODEBUFLEN] = "";

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

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

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

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

  channel_modes(chptr, source_p, modebuf, parabuf);

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

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

/* safe_list_channels()
 *
 * inputs       - pointer to client requesting list
 * output       - 0/1
 * side effects - safely list all channels to source_p
 *
 * Walk the channel buckets, ensure all pointers in a bucket are
 * traversed before blocking on a sendq. This means, no locking is needed.
 *
 * - Dianora
 */
void
safe_list_channels(struct Client *source_p, int only_unmasked_channels)
{
  struct ListTask *const lt = source_p->connection->list_task;
  struct Channel *chptr = NULL;

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

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

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

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