ViewVC Help

View File | Revision Log | Show Annotations | View Changeset | Root Listing

root/svn/ircd-hybrid/trunk/src/hash.c

Comparing ircd-hybrid/trunk/src/hash.c (file contents):
Revision 8752 by michael, Tue Jan 1 11:07:01 2019 UTC vs.
Revision 9857 by michael, Fri Jan 1 04:43:22 2021 UTC

#	Line 1 | Line 1
1		/*
2		*  ircd-hybrid: an advanced, lightweight Internet Relay Chat Daemon (ircd)
3		*
4	<	*  Copyright (c) 1997-2019 ircd-hybrid development team
4	>	*  Copyright (c) 1997-2021 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
#	Line 41 | Line 41
41		#include "dbuf.h"
42
43
44	–	static unsigned int hashf_xor_key;
45	–
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
#	Line 53 | Line 51 | static struct Client *clientTable[HASHSI
51		static struct Channel *channelTable[HASHSIZE];
52
53
56	–	/* hash_init()
57	–	*
58	–	* inputs       - NONE
59	–	* output       - NONE
60	–	* side effects - Initialize the maps used by hash
61	–	*                functions and clear the tables
62	–	*/
63	–	void
64	–	hash_init(void)
65	–	{
66	–	do
67	–	hashf_xor_key = genrand_int32() % 256;  /* better than nothing --adx */
68	–	while (!hashf_xor_key);
69	–	}
70	–
54		/*
55		* New hash function based on the Fowler/Noll/Vo (FNV) algorithm from
56		* http://www.isthe.com/chongo/tech/comp/fnv/
#	Line 78 | Line 61 | hash_init(void)
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) +
#	Line 109 | Line 98 | strhash(const char *name)
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_p must have a non-null
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_p->name
103	>	*                taken from client->name
104		*/
105		void
106	<	hash_add_client(struct Client *client_p)
106	>	hash_add_client(struct Client *client)
107		{
108	<	const unsigned int hashv = strhash(client_p->name);
108	>	const unsigned int hashv = strhash(client->name);
109
110	<	client_p->hnext = clientTable[hashv];
111	<	clientTable[hashv] = client_p;
110	>	client->hnext = clientTable[hashv];
111	>	clientTable[hashv] = client;
112		}
113
114		/* hash_add_channel()
#	Line 127 | Line 116 | hash_add_client(struct Client *client_p)
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. chptr must have a non-null name
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 chptr->name, we do hash its entire lenght
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 *chptr)
125	>	hash_add_channel(struct Channel *channel)
126		{
127	<	const unsigned int hashv = strhash(chptr->name);
127	>	const unsigned int hashv = strhash(channel->name);
128
129	<	chptr->hnextch = channelTable[hashv];
130	<	channelTable[hashv] = chptr;
129	>	channel->hnextch = channelTable[hashv];
130	>	channelTable[hashv] = channel;
131		}
132
133		void
134	<	hash_add_id(struct Client *client_p)
134	>	hash_add_id(struct Client *client)
135		{
136	<	const unsigned int hashv = strhash(client_p->id);
136	>	const unsigned int hashv = strhash(client->id);
137
138	<	client_p->idhnext = idTable[hashv];
139	<	idTable[hashv] = client_p;
138	>	client->idhnext = idTable[hashv];
139	>	idTable[hashv] = client;
140		}
141
142		/* hash_del_id()
#	Line 157 | Line 146 | hash_add_id(struct Client *client_p)
146		* side effects - Removes an ID from the hash linked list
147		*/
148		void
149	<	hash_del_id(struct Client *client_p)
149	>	hash_del_id(struct Client *client)
150		{
151	<	const unsigned int hashv = strhash(client_p->id);
151	>	const unsigned int hashv = strhash(client->id);
152		struct Client *tmp = idTable[hashv];
153
154		if (tmp)
155		{
156	<	if (tmp == client_p)
156	>	if (tmp == client)
157		{
158	<	idTable[hashv] = client_p->idhnext;
159	<	client_p->idhnext = client_p;
158	>	idTable[hashv] = client->idhnext;
159	>	client->idhnext = client;
160		}
161		else
162		{
163	<	while (tmp->idhnext != client_p)
163	>	while (tmp->idhnext != client)
164		if ((tmp = tmp->idhnext) == NULL)
165		return;
166
167		tmp->idhnext = tmp->idhnext->idhnext;
168	<	client_p->idhnext = client_p;
168	>	client->idhnext = client;
169		}
170		}
171		}
#	Line 188 | Line 177 | hash_del_id(struct Client *client_p)
177		* side effects - Removes a Client's name from the hash linked list
178		*/
179		void
180	<	hash_del_client(struct Client *client_p)
180	>	hash_del_client(struct Client *client)
181		{
182	<	const unsigned int hashv = strhash(client_p->name);
182	>	const unsigned int hashv = strhash(client->name);
183		struct Client *tmp = clientTable[hashv];
184
185		if (tmp)
186		{
187	<	if (tmp == client_p)
187	>	if (tmp == client)
188		{
189	<	clientTable[hashv] = client_p->hnext;
190	<	client_p->hnext = client_p;
189	>	clientTable[hashv] = client->hnext;
190	>	client->hnext = client;
191		}
192		else
193		{
194	<	while (tmp->hnext != client_p)
194	>	while (tmp->hnext != client)
195		if ((tmp = tmp->hnext) == NULL)
196		return;
197
198		tmp->hnext = tmp->hnext->hnext;
199	<	client_p->hnext = client_p;
199	>	client->hnext = client;
200		}
201		}
202		}
#	Line 220 | Line 209 | hash_del_client(struct Client *client_p)
209		*                hash linked list
210		*/
211		void
212	<	hash_del_channel(struct Channel *chptr)
212	>	hash_del_channel(struct Channel *channel)
213		{
214	<	const unsigned int hashv = strhash(chptr->name);
214	>	const unsigned int hashv = strhash(channel->name);
215		struct Channel *tmp = channelTable[hashv];
216
217		if (tmp)
218		{
219	<	if (tmp == chptr)
219	>	if (tmp == channel)
220		{
221	<	channelTable[hashv] = chptr->hnextch;
222	<	chptr->hnextch = chptr;
221	>	channelTable[hashv] = channel->hnextch;
222	>	channel->hnextch = channel;
223		}
224		else
225		{
226	<	while (tmp->hnextch != chptr)
226	>	while (tmp->hnextch != channel)
227		if ((tmp = tmp->hnextch) == NULL)
228		return;
229
230		tmp->hnextch = tmp->hnextch->hnextch;
231	<	chptr->hnextch = chptr;
231	>	channel->hnextch = channel;
232		}
233		}
234		}
#	Line 256 | Line 245 | struct Client *
245		hash_find_client(const char *name)
246		{
247		const unsigned int hashv = strhash(name);
248	<	struct Client *client_p;
248	>	struct Client *client;
249
250	<	if ((client_p = clientTable[hashv]))
250	>	if ((client = clientTable[hashv]))
251		{
252	<	if (irccmp(name, client_p->name))
252	>	if (irccmp(name, client->name))
253		{
254		struct Client *prev;
255
256	<	while (prev = client_p, (client_p = client_p->hnext))
256	>	while (prev = client, (client = client->hnext))
257		{
258	<	if (!irccmp(name, client_p->name))
258	>	if (irccmp(name, client->name) == 0)
259		{
260	<	prev->hnext = client_p->hnext;
261	<	client_p->hnext = clientTable[hashv];
262	<	clientTable[hashv] = client_p;
260	>	prev->hnext = client->hnext;
261	>	client->hnext = clientTable[hashv];
262	>	clientTable[hashv] = client;
263		break;
264		}
265		}
266		}
267		}
268
269	<	return client_p;
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_p;
276	>	struct Client *client;
277
278	<	if ((client_p = idTable[hashv]))
278	>	if ((client = idTable[hashv]))
279		{
280	<	if (strcmp(name, client_p->id))
280	>	if (strcmp(name, client->id))
281		{
282		struct Client *prev;
283
284	<	while (prev = client_p, (client_p = client_p->idhnext))
284	>	while (prev = client, (client = client->idhnext))
285		{
286	<	if (!strcmp(name, client_p->id))
286	>	if (strcmp(name, client->id) == 0)
287		{
288	<	prev->idhnext = client_p->idhnext;
289	<	client_p->idhnext = idTable[hashv];
290	<	idTable[hashv] = client_p;
288	>	prev->idhnext = client->idhnext;
289	>	client->idhnext = idTable[hashv];
290	>	idTable[hashv] = client;
291		break;
292		}
293		}
294		}
295		}
296
297	<	return client_p;
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_p = NULL;
304	>	struct Client *client;
305
306		if (IsDigit(*name) && strlen(name) == IRC_MAXSID)
307		return hash_find_id(name);
308
309	<	if ((client_p = clientTable[hashv]))
309	>	if ((client = clientTable[hashv]))
310		{
311	<	if ((!IsServer(client_p) && !IsMe(client_p)) ||
312	<	irccmp(name, client_p->name))
311	>	if ((!IsServer(client) && !IsMe(client)) ||
312	>	irccmp(name, client->name))
313		{
314		struct Client *prev;
315
316	<	while (prev = client_p, (client_p = client_p->hnext))
316	>	while (prev = client, (client = client->hnext))
317		{
318	<	if ((IsServer(client_p) || IsMe(client_p)) &&
319	<	!irccmp(name, client_p->name))
318	>	if ((IsServer(client) || IsMe(client)) &&
319	>	irccmp(name, client->name) == 0)
320		{
321	<	prev->hnext = client_p->hnext;
322	<	client_p->hnext = clientTable[hashv];
323	<	clientTable[hashv] = client_p;
321	>	prev->hnext = client->hnext;
322	>	client->hnext = clientTable[hashv];
323	>	clientTable[hashv] = client;
324		break;
325		}
326		}
327		}
328		}
329
330	<	return client_p;
330	>	return client;
331		}
332
333		/* hash_find_channel()
#	Line 353 | Line 342 | struct Channel *
342		hash_find_channel(const char *name)
343		{
344		const unsigned int hashv = strhash(name);
345	<	struct Channel *chptr = NULL;
345	>	struct Channel *channel;
346
347	<	if ((chptr = channelTable[hashv]))
347	>	if ((channel = channelTable[hashv]))
348		{
349	<	if (irccmp(name, chptr->name))
349	>	if (irccmp(name, channel->name))
350		{
351		struct Channel *prev;
352
353	<	while (prev = chptr, (chptr = chptr->hnextch))
353	>	while (prev = channel, (channel = channel->hnextch))
354		{
355	<	if (!irccmp(name, chptr->name))
355	>	if (irccmp(name, channel->name) == 0)
356		{
357	<	prev->hnextch = chptr->hnextch;
358	<	chptr->hnextch = channelTable[hashv];
359	<	channelTable[hashv] = chptr;
357	>	prev->hnextch = channel->hnextch;
358	>	channel->hnextch = channelTable[hashv];
359	>	channelTable[hashv] = channel;
360		break;
361		}
362		}
363		}
364		}
365
366	<	return chptr;
366	>	return channel;
367		}
368
369		/* hash_get_bucket(int type, unsigned int hashv)
#	Line 445 | Line 434 | exceeding_sendq(const struct Client *to)
434		}
435
436		void
437	<	free_list_task(struct Client *source_p)
437	>	free_list_task(struct Client *client)
438		{
439	<	struct ListTask *const lt = source_p->connection->list_task;
439	>	struct ListTask *const lt = client->connection->list_task;
440		dlink_node *node, *node_next;
441
442		dlinkDelete(&lt->node, &listing_client_list);
#	Line 467 | Line 456 | free_list_task(struct Client *source_p)
456		}
457
458		xfree(lt);
459	<	source_p->connection->list_task = NULL;
459	>	client->connection->list_task = NULL;
460		}
461
462		/* list_allow_channel()
#	Line 503 | Line 492 | list_allow_channel(const char *name, con
492		* side effects -
493		*/
494		static void
495	<	list_one_channel(struct Client *source_p, struct Channel *chptr)
495	>	list_one_channel(struct Client *client, struct Channel *channel)
496		{
497	<	const struct ListTask *const lt = source_p->connection->list_task;
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(chptr) &&
504	<	!(HasUMode(source_p, UMODE_ADMIN) || IsMember(source_p, chptr)))
503	>	if (SecretChannel(channel) &&
504	>	!(HasUMode(client, UMODE_ADMIN) || (member = member_find_link(client, channel))))
505		return;
506
507	<	if (dlink_list_length(&chptr->members) < lt->users_min ||
508	<	dlink_list_length(&chptr->members) > lt->users_max ||
509	<	(chptr->creationtime != 0 &&
510	<	((unsigned int)chptr->creationtime < lt->created_min ||
511	<	(unsigned int)chptr->creationtime > lt->created_max)) ||
512	<	(unsigned int)chptr->topic_time < lt->topicts_min ||
513	<	(chptr->topic_time ? (unsigned int)chptr->topic_time : UINT_MAX) >
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, chptr->topic))
517	>	if (lt->topic[0] && match(lt->topic, channel->topic))
518		return;
519
520	<	if (list_allow_channel(chptr->name, lt) == false)
520	>	if (list_allow_channel(channel->name, lt) == false)
521		return;
522
523	<	channel_modes(chptr, source_p, modebuf, parabuf);
523	>	channel_modes(channel, client, member, modebuf, parabuf);
524
525	<	if (chptr->topic[0])
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(source_p, &me, RPL_LIST, chptr->name,
531	<	dlink_list_length(&chptr->members),
532	<	listbuf, chptr->topic);
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 source_p
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.
#	Line 554 | Line 544 | list_one_channel(struct Client *source_p
544		* - Dianora
545		*/
546		void
547	<	safe_list_channels(struct Client *source_p, bool only_unmasked_channels)
547	>	safe_list_channels(struct Client *client, bool only_unmasked_channels)
548		{
549	<	struct ListTask *const lt = source_p->connection->list_task;
550	<	struct Channel *chptr = NULL;
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(source_p) == true)
556	>	if (exceeding_sendq(client) == true)
557		{
558		lt->hash_index = i;
559		return;  /* Still more to do */
560		}
561
562	<	for (chptr = channelTable[i]; chptr; chptr = chptr->hnextch)
563	<	list_one_channel(source_p, chptr);
562	>	for (channel = channelTable[i]; channel; channel = channel->hnextch)
563	>	list_one_channel(client, channel);
564		}
565		}
566		else
#	Line 578 | Line 568 | safe_list_channels(struct Client *source
568		dlink_node *node;
569
570		DLINK_FOREACH(node, lt->show_mask.head)
571	<	if ((chptr = hash_find_channel(node->data)))
572	<	list_one_channel(source_p, chptr);
571	>	if ((channel = hash_find_channel(node->data)))
572	>	list_one_channel(client, channel);
573		}
574
575	<	free_list_task(source_p);
576	<	sendto_one_numeric(source_p, &me, RPL_LISTEND);
575	>	free_list_task(client);
576	>	sendto_one_numeric(client, &me, RPL_LISTEND);
577		}

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines (old)
>	Changed lines (new)