2 * ircd-ratbox: A slightly useful ircd.
3 * hash.c: Maintains hashtables.
5 * Copyright (C) 1990 Jarkko Oikarinen and University of Oulu, Co Center
6 * Copyright (C) 1996-2002 Hybrid Development Team
7 * Copyright (C) 2002-2005 ircd-ratbox development team
9 * This program is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License as published by
11 * the Free Software Foundation; either version 2 of the License, or
12 * (at your option) any later version.
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
19 * You should have received a copy of the GNU General Public License
20 * along with this program; if not, write to the Free Software
21 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
24 * $Id: hash.c 3177 2007-02-01 00:19:14Z jilles $
28 #include "ircd_defs.h"
40 #include "s_newconf.h"
42 #include "irc_dictionary.h"
43 #include "irc_radixtree.h"
45 struct Dictionary
*client_connid_tree
= NULL
;
46 struct Dictionary
*client_zconnid_tree
= NULL
;
47 struct irc_radixtree
*client_id_tree
= NULL
;
48 struct irc_radixtree
*client_name_tree
= NULL
;
50 struct irc_radixtree
*channel_tree
= NULL
;
51 struct irc_radixtree
*resv_tree
= NULL
;
52 struct irc_radixtree
*hostname_tree
= NULL
;
55 * look in whowas.c for the missing ...[WW_MAX]; entry
60 * clears the various hashtables
65 client_connid_tree
= irc_dictionary_create("client connid", irc_uint32cmp
);
66 client_zconnid_tree
= irc_dictionary_create("client zconnid", irc_uint32cmp
);
67 client_id_tree
= irc_radixtree_create("client id", NULL
);
68 client_name_tree
= irc_radixtree_create("client name", irc_radixtree_irccasecanon
);
70 channel_tree
= irc_radixtree_create("channel", irc_radixtree_irccasecanon
);
71 resv_tree
= irc_radixtree_create("resv", irc_radixtree_irccasecanon
);
73 hostname_tree
= irc_radixtree_create("hostname", irc_radixtree_irccasecanon
);
77 fnv_hash_upper(const unsigned char *s
, int bits
)
79 u_int32_t h
= FNV1_32_INIT
;
84 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
87 h
= ((h
>> bits
) ^ h
) & ((1<<bits
)-1);
92 fnv_hash(const unsigned char *s
, int bits
)
94 u_int32_t h
= FNV1_32_INIT
;
99 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
102 h
= ((h
>> bits
) ^ h
) & ((1<<bits
)-1);
107 fnv_hash_len(const unsigned char *s
, int bits
, int len
)
109 u_int32_t h
= FNV1_32_INIT
;
110 const unsigned char *x
= s
+ len
;
114 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
117 h
= ((h
>> bits
) ^ h
) & ((1<<bits
)-1);
122 fnv_hash_upper_len(const unsigned char *s
, int bits
, int len
)
124 u_int32_t h
= FNV1_32_INIT
;
125 const unsigned char *x
= s
+ len
;
129 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
132 h
= ((h
>> bits
) ^ h
) & ((1<<bits
)-1);
138 * adds an entry to the id hash table
141 add_to_id_hash(const char *name
, struct Client
*client_p
)
143 if(EmptyString(name
) || (client_p
== NULL
))
146 irc_radixtree_add(client_id_tree
, name
, client_p
);
149 /* add_to_client_hash()
151 * adds an entry (client/server) to the client hash table
154 add_to_client_hash(const char *name
, struct Client
*client_p
)
156 s_assert(name
!= NULL
);
157 s_assert(client_p
!= NULL
);
158 if(EmptyString(name
) || (client_p
== NULL
))
161 irc_radixtree_add(client_name_tree
, name
, client_p
);
164 /* add_to_hostname_hash()
166 * adds a client entry to the hostname hash table
169 add_to_hostname_hash(const char *hostname
, struct Client
*client_p
)
173 s_assert(hostname
!= NULL
);
174 s_assert(client_p
!= NULL
);
175 if(EmptyString(hostname
) || (client_p
== NULL
))
178 list
= irc_radixtree_retrieve(hostname_tree
, hostname
);
181 rb_dlinkAddAlloc(client_p
, list
);
185 list
= rb_malloc(sizeof(*list
));
186 irc_radixtree_add(hostname_tree
, hostname
, list
);
187 rb_dlinkAddAlloc(client_p
, list
);
190 /* add_to_resv_hash()
192 * adds a resv channel entry to the resv hash table
195 add_to_resv_hash(const char *name
, struct ConfItem
*aconf
)
197 s_assert(!EmptyString(name
));
198 s_assert(aconf
!= NULL
);
199 if(EmptyString(name
) || aconf
== NULL
)
202 irc_radixtree_add(resv_tree
, name
, aconf
);
205 /* del_from_id_hash()
207 * removes an id from the id hash table
210 del_from_id_hash(const char *id
, struct Client
*client_p
)
212 s_assert(id
!= NULL
);
213 s_assert(client_p
!= NULL
);
214 if(EmptyString(id
) || client_p
== NULL
)
217 irc_radixtree_delete(client_id_tree
, id
);
220 /* del_from_client_hash()
222 * removes a client/server from the client hash table
225 del_from_client_hash(const char *name
, struct Client
*client_p
)
227 /* no s_asserts, this can happen when removing a client that
230 if(EmptyString(name
) || client_p
== NULL
)
233 irc_radixtree_delete(client_name_tree
, name
);
236 /* del_from_channel_hash()
238 * removes a channel from the channel hash table
241 del_from_channel_hash(const char *name
, struct Channel
*chptr
)
243 s_assert(name
!= NULL
);
244 s_assert(chptr
!= NULL
);
246 if(EmptyString(name
) || chptr
== NULL
)
249 irc_radixtree_delete(channel_tree
, name
);
252 /* del_from_hostname_hash()
254 * removes a client entry from the hostname hash table
257 del_from_hostname_hash(const char *hostname
, struct Client
*client_p
)
261 if(hostname
== NULL
|| client_p
== NULL
)
264 list
= irc_radixtree_retrieve(hostname_tree
, hostname
);
268 rb_dlinkFindDestroy(client_p
, list
);
270 if (rb_dlink_list_length(list
) == 0)
272 irc_radixtree_delete(hostname_tree
, hostname
);
277 /* del_from_resv_hash()
279 * removes a resv entry from the resv hash table
282 del_from_resv_hash(const char *name
, struct ConfItem
*aconf
)
284 s_assert(name
!= NULL
);
285 s_assert(aconf
!= NULL
);
286 if(EmptyString(name
) || aconf
== NULL
)
289 irc_radixtree_delete(resv_tree
, name
);
294 * finds a client entry from the id hash table
297 find_id(const char *name
)
299 if(EmptyString(name
))
302 return irc_radixtree_retrieve(client_id_tree
, name
);
307 * finds a client/server entry from the client hash table
310 find_client(const char *name
)
312 s_assert(name
!= NULL
);
313 if(EmptyString(name
))
316 /* hunting for an id, not a nick */
318 return (find_id(name
));
320 return irc_radixtree_retrieve(client_name_tree
, name
);
323 /* find_named_client()
325 * finds a client/server entry from the client hash table
328 find_named_client(const char *name
)
330 s_assert(name
!= NULL
);
331 if(EmptyString(name
))
334 return irc_radixtree_retrieve(client_name_tree
, name
);
339 * finds a server from the client hash table
342 find_server(struct Client
*source_p
, const char *name
)
344 struct Client
*target_p
;
346 if(EmptyString(name
))
349 if((source_p
== NULL
|| !MyClient(source_p
)) &&
350 IsDigit(*name
) && strlen(name
) == 3)
352 target_p
= find_id(name
);
356 target_p
= irc_radixtree_retrieve(client_name_tree
, name
);
357 if (target_p
!= NULL
)
359 if(IsServer(target_p
) || IsMe(target_p
))
368 * finds a hostname rb_dlink list from the hostname hash table.
369 * we return the full rb_dlink list, because you can have multiple
370 * entries with the same hostname
373 find_hostname(const char *hostname
)
375 rb_dlink_list
*hlist
;
377 if(EmptyString(hostname
))
380 hlist
= irc_radixtree_retrieve(hostname_tree
, hostname
);
389 * finds a channel from the channel hash table
392 find_channel(const char *name
)
394 s_assert(name
!= NULL
);
395 if(EmptyString(name
))
398 return irc_radixtree_retrieve(channel_tree
, name
);
402 * get_or_create_channel
403 * inputs - client pointer
405 * - pointer to int flag whether channel was newly created or not
406 * output - returns channel block or NULL if illegal name
407 * - also modifies *isnew
409 * Get Channel block for chname (and allocate a new channel
410 * block, if it didn't exist before).
413 get_or_create_channel(struct Client
*client_p
, const char *chname
, int *isnew
)
415 struct Channel
*chptr
;
417 const char *s
= chname
;
426 if(IsServer(client_p
))
428 sendto_realops_snomask(SNO_DEBUG
, L_ALL
,
429 "*** Long channel name from %s (%d > %d): %s",
430 client_p
->name
, len
, CHANNELLEN
, s
);
434 *(t
+ CHANNELLEN
) = '\0';
438 chptr
= irc_radixtree_retrieve(channel_tree
, s
);
449 chptr
= allocate_channel(s
);
450 chptr
->channelts
= rb_current_time(); /* doesn't hurt to set it here */
452 rb_dlinkAdd(chptr
, &chptr
->node
, &global_channel_list
);
453 irc_radixtree_add(channel_tree
, chptr
->chname
, chptr
);
460 * hunts for a resv entry in the resv hash table
463 hash_find_resv(const char *name
)
465 struct ConfItem
*aconf
;
467 s_assert(name
!= NULL
);
468 if(EmptyString(name
))
471 aconf
= irc_radixtree_retrieve(resv_tree
, name
);
482 clear_resv_hash(void)
484 struct ConfItem
*aconf
;
485 struct irc_radixtree_iteration_state iter
;
487 IRC_RADIXTREE_FOREACH(aconf
, &iter
, resv_tree
)
489 /* skip temp resvs */
493 irc_radixtree_delete(resv_tree
, aconf
->host
);
499 add_to_zconnid_hash(struct Client
*client_p
)
501 irc_dictionary_add(client_zconnid_tree
, IRC_UINT_TO_POINTER(client_p
->localClient
->zconnid
), client_p
);
505 del_from_zconnid_hash(struct Client
*client_p
)
507 irc_dictionary_delete(client_zconnid_tree
, IRC_UINT_TO_POINTER(client_p
->localClient
->zconnid
));
511 add_to_cli_connid_hash(struct Client
*client_p
)
513 irc_dictionary_add(client_connid_tree
, IRC_UINT_TO_POINTER(client_p
->localClient
->connid
), client_p
);
517 del_from_cli_connid_hash(struct Client
*client_p
)
519 irc_dictionary_delete(client_connid_tree
, IRC_UINT_TO_POINTER(client_p
->localClient
->connid
));
523 find_cli_connid_hash(uint32_t connid
)
525 struct Client
*target_p
;
527 target_p
= irc_dictionary_retrieve(client_connid_tree
, IRC_UINT_TO_POINTER(connid
));
528 if (target_p
!= NULL
)
531 target_p
= irc_dictionary_retrieve(client_zconnid_tree
, IRC_UINT_TO_POINTER(connid
));
532 if (target_p
!= NULL
)