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