]>
Commit | Line | Data |
---|---|---|
ae78a571 VY |
1 | /* |
2 | * ircd-ratbox: A slightly useful ircd. | |
3 | * hash.c: Maintains hashtables. | |
4 | * | |
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 | |
8 | * | |
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. | |
13 | * | |
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. | |
18 | * | |
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 | |
22 | * USA | |
23 | * | |
24 | * $Id: hash.c 3177 2007-02-01 00:19:14Z jilles $ | |
25 | */ | |
26 | ||
27 | #include "stdinc.h" | |
28 | #include "ircd_defs.h" | |
29 | #include "s_conf.h" | |
30 | #include "channel.h" | |
31 | #include "client.h" | |
32 | #include "common.h" | |
33 | #include "hash.h" | |
4562c604 | 34 | #include "match.h" |
ae78a571 VY |
35 | #include "ircd.h" |
36 | #include "numeric.h" | |
37 | #include "send.h" | |
38 | #include "msg.h" | |
39 | #include "cache.h" | |
40 | #include "s_newconf.h" | |
77d3d2db | 41 | #include "s_assert.h" |
5c7c7d65 | 42 | #include "irc_dictionary.h" |
46be39fa | 43 | #include "irc_radixtree.h" |
c6d72037 | 44 | |
5c7c7d65 AC |
45 | struct Dictionary *client_connid_tree = NULL; |
46 | struct Dictionary *client_zconnid_tree = NULL; | |
3eeccbe3 | 47 | struct irc_radixtree *client_id_tree = NULL; |
bb4ac314 | 48 | struct irc_radixtree *client_name_tree = NULL; |
5c7c7d65 | 49 | |
9b74b992 | 50 | struct irc_radixtree *channel_tree = NULL; |
46be39fa | 51 | struct irc_radixtree *resv_tree = NULL; |
d38c08c1 | 52 | struct irc_radixtree *hostname_tree = NULL; |
46be39fa | 53 | |
ae78a571 VY |
54 | /* |
55 | * look in whowas.c for the missing ...[WW_MAX]; entry | |
56 | */ | |
57 | ||
ae78a571 VY |
58 | /* init_hash() |
59 | * | |
60 | * clears the various hashtables | |
61 | */ | |
62 | void | |
63 | init_hash(void) | |
64 | { | |
5c7c7d65 AC |
65 | client_connid_tree = irc_dictionary_create("client connid", irc_uint32cmp); |
66 | client_zconnid_tree = irc_dictionary_create("client zconnid", irc_uint32cmp); | |
3eeccbe3 | 67 | client_id_tree = irc_radixtree_create("client id", NULL); |
bb4ac314 | 68 | client_name_tree = irc_radixtree_create("client name", irc_radixtree_irccasecanon); |
46be39fa | 69 | |
9b74b992 | 70 | channel_tree = irc_radixtree_create("channel", irc_radixtree_irccasecanon); |
46be39fa | 71 | resv_tree = irc_radixtree_create("resv", irc_radixtree_irccasecanon); |
d38c08c1 AC |
72 | |
73 | hostname_tree = irc_radixtree_create("hostname", irc_radixtree_irccasecanon); | |
ae78a571 VY |
74 | } |
75 | ||
ae78a571 VY |
76 | u_int32_t |
77 | fnv_hash_upper(const unsigned char *s, int bits) | |
78 | { | |
79 | u_int32_t h = FNV1_32_INIT; | |
80 | ||
81 | while (*s) | |
82 | { | |
83 | h ^= ToUpper(*s++); | |
84 | h += (h<<1) + (h<<4) + (h<<7) + (h << 8) + (h << 24); | |
85 | } | |
86 | if (bits < 32) | |
87 | h = ((h >> bits) ^ h) & ((1<<bits)-1); | |
88 | return h; | |
89 | } | |
90 | ||
91 | u_int32_t | |
92 | fnv_hash(const unsigned char *s, int bits) | |
93 | { | |
94 | u_int32_t h = FNV1_32_INIT; | |
95 | ||
96 | while (*s) | |
97 | { | |
98 | h ^= *s++; | |
99 | h += (h<<1) + (h<<4) + (h<<7) + (h << 8) + (h << 24); | |
100 | } | |
101 | if (bits < 32) | |
102 | h = ((h >> bits) ^ h) & ((1<<bits)-1); | |
103 | return h; | |
104 | } | |
105 | ||
106 | u_int32_t | |
107 | fnv_hash_len(const unsigned char *s, int bits, int len) | |
108 | { | |
109 | u_int32_t h = FNV1_32_INIT; | |
110 | const unsigned char *x = s + len; | |
111 | while (*s && s < x) | |
112 | { | |
113 | h ^= *s++; | |
114 | h += (h<<1) + (h<<4) + (h<<7) + (h << 8) + (h << 24); | |
115 | } | |
116 | if (bits < 32) | |
117 | h = ((h >> bits) ^ h) & ((1<<bits)-1); | |
118 | return h; | |
119 | } | |
120 | ||
121 | u_int32_t | |
122 | fnv_hash_upper_len(const unsigned char *s, int bits, int len) | |
123 | { | |
124 | u_int32_t h = FNV1_32_INIT; | |
125 | const unsigned char *x = s + len; | |
126 | while (*s && s < x) | |
127 | { | |
128 | h ^= ToUpper(*s++); | |
129 | h += (h<<1) + (h<<4) + (h<<7) + (h << 8) + (h << 24); | |
130 | } | |
131 | if (bits < 32) | |
132 | h = ((h >> bits) ^ h) & ((1<<bits)-1); | |
133 | return h; | |
134 | } | |
ae78a571 | 135 | |
ae78a571 VY |
136 | /* add_to_id_hash() |
137 | * | |
138 | * adds an entry to the id hash table | |
139 | */ | |
140 | void | |
141 | add_to_id_hash(const char *name, struct Client *client_p) | |
142 | { | |
ae78a571 VY |
143 | if(EmptyString(name) || (client_p == NULL)) |
144 | return; | |
145 | ||
3eeccbe3 | 146 | irc_radixtree_add(client_id_tree, name, client_p); |
ae78a571 VY |
147 | } |
148 | ||
149 | /* add_to_client_hash() | |
150 | * | |
151 | * adds an entry (client/server) to the client hash table | |
152 | */ | |
153 | void | |
154 | add_to_client_hash(const char *name, struct Client *client_p) | |
155 | { | |
ae78a571 VY |
156 | s_assert(name != NULL); |
157 | s_assert(client_p != NULL); | |
158 | if(EmptyString(name) || (client_p == NULL)) | |
159 | return; | |
160 | ||
bb4ac314 | 161 | irc_radixtree_add(client_name_tree, name, client_p); |
ae78a571 VY |
162 | } |
163 | ||
164 | /* add_to_hostname_hash() | |
165 | * | |
166 | * adds a client entry to the hostname hash table | |
167 | */ | |
168 | void | |
169 | add_to_hostname_hash(const char *hostname, struct Client *client_p) | |
170 | { | |
d38c08c1 | 171 | rb_dlink_list *list; |
ae78a571 VY |
172 | |
173 | s_assert(hostname != NULL); | |
174 | s_assert(client_p != NULL); | |
175 | if(EmptyString(hostname) || (client_p == NULL)) | |
176 | return; | |
177 | ||
d38c08c1 AC |
178 | list = irc_radixtree_retrieve(hostname_tree, hostname); |
179 | if (list != NULL) | |
180 | { | |
181 | rb_dlinkAddAlloc(client_p, list); | |
182 | return; | |
183 | } | |
184 | ||
185 | list = rb_malloc(sizeof(*list)); | |
186 | irc_radixtree_add(hostname_tree, hostname, list); | |
187 | rb_dlinkAddAlloc(client_p, list); | |
ae78a571 VY |
188 | } |
189 | ||
190 | /* add_to_resv_hash() | |
191 | * | |
192 | * adds a resv channel entry to the resv hash table | |
193 | */ | |
194 | void | |
195 | add_to_resv_hash(const char *name, struct ConfItem *aconf) | |
196 | { | |
ae78a571 VY |
197 | s_assert(!EmptyString(name)); |
198 | s_assert(aconf != NULL); | |
199 | if(EmptyString(name) || aconf == NULL) | |
200 | return; | |
201 | ||
46be39fa | 202 | irc_radixtree_add(resv_tree, name, aconf); |
ae78a571 VY |
203 | } |
204 | ||
205 | /* del_from_id_hash() | |
206 | * | |
207 | * removes an id from the id hash table | |
208 | */ | |
209 | void | |
210 | del_from_id_hash(const char *id, struct Client *client_p) | |
211 | { | |
ae78a571 VY |
212 | s_assert(id != NULL); |
213 | s_assert(client_p != NULL); | |
214 | if(EmptyString(id) || client_p == NULL) | |
215 | return; | |
216 | ||
3eeccbe3 | 217 | irc_radixtree_delete(client_id_tree, id); |
ae78a571 VY |
218 | } |
219 | ||
220 | /* del_from_client_hash() | |
221 | * | |
222 | * removes a client/server from the client hash table | |
223 | */ | |
224 | void | |
225 | del_from_client_hash(const char *name, struct Client *client_p) | |
226 | { | |
ae78a571 VY |
227 | /* no s_asserts, this can happen when removing a client that |
228 | * is unregistered. | |
229 | */ | |
230 | if(EmptyString(name) || client_p == NULL) | |
231 | return; | |
232 | ||
bb4ac314 | 233 | irc_radixtree_delete(client_name_tree, name); |
ae78a571 VY |
234 | } |
235 | ||
236 | /* del_from_channel_hash() | |
55abcbb2 | 237 | * |
ae78a571 VY |
238 | * removes a channel from the channel hash table |
239 | */ | |
240 | void | |
241 | del_from_channel_hash(const char *name, struct Channel *chptr) | |
242 | { | |
ae78a571 VY |
243 | s_assert(name != NULL); |
244 | s_assert(chptr != NULL); | |
245 | ||
246 | if(EmptyString(name) || chptr == NULL) | |
247 | return; | |
248 | ||
9b74b992 | 249 | irc_radixtree_delete(channel_tree, name); |
ae78a571 VY |
250 | } |
251 | ||
252 | /* del_from_hostname_hash() | |
253 | * | |
254 | * removes a client entry from the hostname hash table | |
255 | */ | |
256 | void | |
257 | del_from_hostname_hash(const char *hostname, struct Client *client_p) | |
258 | { | |
d38c08c1 | 259 | rb_dlink_list *list; |
ae78a571 VY |
260 | |
261 | if(hostname == NULL || client_p == NULL) | |
262 | return; | |
263 | ||
d38c08c1 AC |
264 | list = irc_radixtree_retrieve(hostname_tree, hostname); |
265 | if (list == NULL) | |
266 | return; | |
267 | ||
268 | rb_dlinkFindDestroy(client_p, list); | |
ae78a571 | 269 | |
d38c08c1 AC |
270 | if (rb_dlink_list_length(list) == 0) |
271 | { | |
272 | irc_radixtree_delete(hostname_tree, hostname); | |
273 | rb_free(list); | |
274 | } | |
ae78a571 VY |
275 | } |
276 | ||
277 | /* del_from_resv_hash() | |
278 | * | |
279 | * removes a resv entry from the resv hash table | |
280 | */ | |
281 | void | |
282 | del_from_resv_hash(const char *name, struct ConfItem *aconf) | |
283 | { | |
ae78a571 VY |
284 | s_assert(name != NULL); |
285 | s_assert(aconf != NULL); | |
286 | if(EmptyString(name) || aconf == NULL) | |
287 | return; | |
288 | ||
46be39fa | 289 | irc_radixtree_delete(resv_tree, name); |
ae78a571 VY |
290 | } |
291 | ||
292 | /* find_id() | |
293 | * | |
294 | * finds a client entry from the id hash table | |
295 | */ | |
296 | struct Client * | |
297 | find_id(const char *name) | |
298 | { | |
ae78a571 VY |
299 | if(EmptyString(name)) |
300 | return NULL; | |
301 | ||
3eeccbe3 | 302 | return irc_radixtree_retrieve(client_id_tree, name); |
ae78a571 VY |
303 | } |
304 | ||
305 | /* find_client() | |
306 | * | |
307 | * finds a client/server entry from the client hash table | |
308 | */ | |
309 | struct Client * | |
310 | find_client(const char *name) | |
311 | { | |
ae78a571 VY |
312 | s_assert(name != NULL); |
313 | if(EmptyString(name)) | |
314 | return NULL; | |
315 | ||
316 | /* hunting for an id, not a nick */ | |
317 | if(IsDigit(*name)) | |
318 | return (find_id(name)); | |
319 | ||
bb4ac314 | 320 | return irc_radixtree_retrieve(client_name_tree, name); |
ae78a571 VY |
321 | } |
322 | ||
323 | /* find_named_client() | |
324 | * | |
325 | * finds a client/server entry from the client hash table | |
326 | */ | |
327 | struct Client * | |
328 | find_named_client(const char *name) | |
329 | { | |
ae78a571 VY |
330 | s_assert(name != NULL); |
331 | if(EmptyString(name)) | |
332 | return NULL; | |
333 | ||
bb4ac314 | 334 | return irc_radixtree_retrieve(client_name_tree, name); |
ae78a571 VY |
335 | } |
336 | ||
337 | /* find_server() | |
338 | * | |
339 | * finds a server from the client hash table | |
340 | */ | |
341 | struct Client * | |
342 | find_server(struct Client *source_p, const char *name) | |
343 | { | |
344 | struct Client *target_p; | |
55abcbb2 | 345 | |
ae78a571 VY |
346 | if(EmptyString(name)) |
347 | return NULL; | |
348 | ||
55abcbb2 | 349 | if((source_p == NULL || !MyClient(source_p)) && |
ae78a571 VY |
350 | IsDigit(*name) && strlen(name) == 3) |
351 | { | |
352 | target_p = find_id(name); | |
353 | return(target_p); | |
354 | } | |
355 | ||
bb4ac314 AC |
356 | target_p = irc_radixtree_retrieve(client_name_tree, name); |
357 | if (target_p != NULL) | |
ae78a571 | 358 | { |
bb4ac314 AC |
359 | if(IsServer(target_p) || IsMe(target_p)) |
360 | return target_p; | |
ae78a571 VY |
361 | } |
362 | ||
363 | return NULL; | |
364 | } | |
365 | ||
366 | /* find_hostname() | |
367 | * | |
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 | |
371 | */ | |
372 | rb_dlink_node * | |
373 | find_hostname(const char *hostname) | |
374 | { | |
d38c08c1 | 375 | rb_dlink_list *hlist; |
ae78a571 VY |
376 | |
377 | if(EmptyString(hostname)) | |
378 | return NULL; | |
379 | ||
d38c08c1 AC |
380 | hlist = irc_radixtree_retrieve(hostname_tree, hostname); |
381 | if (hlist == NULL) | |
382 | return NULL; | |
ae78a571 | 383 | |
d38c08c1 | 384 | return hlist->head; |
ae78a571 VY |
385 | } |
386 | ||
387 | /* find_channel() | |
388 | * | |
389 | * finds a channel from the channel hash table | |
390 | */ | |
391 | struct Channel * | |
392 | find_channel(const char *name) | |
393 | { | |
ae78a571 VY |
394 | s_assert(name != NULL); |
395 | if(EmptyString(name)) | |
396 | return NULL; | |
397 | ||
9b74b992 | 398 | return irc_radixtree_retrieve(channel_tree, name); |
ae78a571 VY |
399 | } |
400 | ||
401 | /* | |
402 | * get_or_create_channel | |
403 | * inputs - client pointer | |
404 | * - channel name | |
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 | |
408 | * | |
409 | * Get Channel block for chname (and allocate a new channel | |
410 | * block, if it didn't exist before). | |
411 | */ | |
412 | struct Channel * | |
413 | get_or_create_channel(struct Client *client_p, const char *chname, int *isnew) | |
414 | { | |
415 | struct Channel *chptr; | |
ae78a571 VY |
416 | int len; |
417 | const char *s = chname; | |
418 | ||
419 | if(EmptyString(s)) | |
420 | return NULL; | |
421 | ||
422 | len = strlen(s); | |
423 | if(len > CHANNELLEN) | |
424 | { | |
425 | char *t; | |
426 | if(IsServer(client_p)) | |
427 | { | |
428 | sendto_realops_snomask(SNO_DEBUG, L_ALL, | |
429 | "*** Long channel name from %s (%d > %d): %s", | |
430 | client_p->name, len, CHANNELLEN, s); | |
431 | } | |
432 | len = CHANNELLEN; | |
433 | t = LOCAL_COPY(s); | |
434 | *(t + CHANNELLEN) = '\0'; | |
435 | s = t; | |
436 | } | |
437 | ||
9b74b992 AC |
438 | chptr = irc_radixtree_retrieve(channel_tree, s); |
439 | if (chptr != NULL) | |
ae78a571 | 440 | { |
9b74b992 AC |
441 | if (isnew != NULL) |
442 | *isnew = 0; | |
443 | return chptr; | |
ae78a571 VY |
444 | } |
445 | ||
446 | if(isnew != NULL) | |
447 | *isnew = 1; | |
448 | ||
449 | chptr = allocate_channel(s); | |
ae78a571 VY |
450 | chptr->channelts = rb_current_time(); /* doesn't hurt to set it here */ |
451 | ||
9b74b992 AC |
452 | rb_dlinkAdd(chptr, &chptr->node, &global_channel_list); |
453 | irc_radixtree_add(channel_tree, chptr->chname, chptr); | |
ae78a571 VY |
454 | |
455 | return chptr; | |
456 | } | |
457 | ||
458 | /* hash_find_resv() | |
459 | * | |
460 | * hunts for a resv entry in the resv hash table | |
461 | */ | |
462 | struct ConfItem * | |
463 | hash_find_resv(const char *name) | |
464 | { | |
465 | struct ConfItem *aconf; | |
ae78a571 VY |
466 | |
467 | s_assert(name != NULL); | |
468 | if(EmptyString(name)) | |
469 | return NULL; | |
470 | ||
46be39fa AC |
471 | aconf = irc_radixtree_retrieve(resv_tree, name); |
472 | if (aconf != NULL) | |
ae78a571 | 473 | { |
46be39fa AC |
474 | aconf->port++; |
475 | return aconf; | |
ae78a571 VY |
476 | } |
477 | ||
478 | return NULL; | |
479 | } | |
480 | ||
481 | void | |
482 | clear_resv_hash(void) | |
483 | { | |
484 | struct ConfItem *aconf; | |
46be39fa | 485 | struct irc_radixtree_iteration_state iter; |
ae78a571 | 486 | |
46be39fa | 487 | IRC_RADIXTREE_FOREACH(aconf, &iter, resv_tree) |
ae78a571 | 488 | { |
ae78a571 VY |
489 | /* skip temp resvs */ |
490 | if(aconf->hold) | |
491 | continue; | |
492 | ||
46be39fa AC |
493 | irc_radixtree_delete(resv_tree, aconf->host); |
494 | free_conf(aconf); | |
ae78a571 | 495 | } |
ae78a571 VY |
496 | } |
497 | ||
8bd5767b | 498 | void |
b5b4a0e7 | 499 | add_to_zconnid_hash(struct Client *client_p) |
8bd5767b | 500 | { |
5c7c7d65 | 501 | irc_dictionary_add(client_zconnid_tree, IRC_UINT_TO_POINTER(client_p->localClient->zconnid), client_p); |
8bd5767b JT |
502 | } |
503 | ||
b5b4a0e7 AC |
504 | void |
505 | del_from_zconnid_hash(struct Client *client_p) | |
506 | { | |
5c7c7d65 | 507 | irc_dictionary_delete(client_zconnid_tree, IRC_UINT_TO_POINTER(client_p->localClient->zconnid)); |
b5b4a0e7 | 508 | } |
8bd5767b JT |
509 | |
510 | void | |
b5b4a0e7 | 511 | add_to_cli_connid_hash(struct Client *client_p) |
8bd5767b | 512 | { |
5c7c7d65 | 513 | irc_dictionary_add(client_connid_tree, IRC_UINT_TO_POINTER(client_p->localClient->connid), client_p); |
b5b4a0e7 AC |
514 | } |
515 | ||
516 | void | |
517 | del_from_cli_connid_hash(struct Client *client_p) | |
518 | { | |
5c7c7d65 | 519 | irc_dictionary_delete(client_connid_tree, IRC_UINT_TO_POINTER(client_p->localClient->connid)); |
8bd5767b JT |
520 | } |
521 | ||
522 | struct Client * | |
5c7c7d65 | 523 | find_cli_connid_hash(uint32_t connid) |
8bd5767b JT |
524 | { |
525 | struct Client *target_p; | |
b5b4a0e7 | 526 | |
5c7c7d65 AC |
527 | target_p = irc_dictionary_retrieve(client_connid_tree, IRC_UINT_TO_POINTER(connid)); |
528 | if (target_p != NULL) | |
529 | return target_p; | |
530 | ||
531 | target_p = irc_dictionary_retrieve(client_zconnid_tree, IRC_UINT_TO_POINTER(connid)); | |
532 | if (target_p != NULL) | |
533 | return target_p; | |
b5b4a0e7 AC |
534 | |
535 | return NULL; | |
c6d72037 | 536 | } |