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