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
26 #include "ircd_defs.h"
37 #include "s_newconf.h"
39 #include "rb_dictionary.h"
40 #include "rb_radixtree.h"
42 rb_dictionary
*client_connid_tree
= NULL
;
43 rb_radixtree
*client_id_tree
= NULL
;
44 rb_radixtree
*client_name_tree
= NULL
;
46 rb_radixtree
*channel_tree
= NULL
;
47 rb_radixtree
*resv_tree
= NULL
;
48 rb_radixtree
*hostname_tree
= NULL
;
51 * look in whowas.c for the missing ...[WW_MAX]; entry
56 * clears the various hashtables
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
);
65 channel_tree
= rb_radixtree_create("channel", irccasecanon
);
66 resv_tree
= rb_radixtree_create("resv", irccasecanon
);
68 hostname_tree
= rb_radixtree_create("hostname", irccasecanon
);
72 fnv_hash_upper(const unsigned char *s
, int bits
)
74 uint32_t h
= FNV1_32_INIT
;
78 h
^= irctoupper(*s
++);
79 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
82 h
= ((h
>> bits
) ^ h
) & ((1<<bits
)-1);
87 fnv_hash(const unsigned char *s
, int bits
)
89 uint32_t h
= FNV1_32_INIT
;
94 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
97 h
= ((h
>> bits
) ^ h
) & ((1<<bits
)-1);
102 fnv_hash_len(const unsigned char *s
, int bits
, int len
)
104 uint32_t h
= FNV1_32_INIT
;
105 const unsigned char *x
= s
+ len
;
109 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
112 h
= ((h
>> bits
) ^ h
) & ((1<<bits
)-1);
117 fnv_hash_upper_len(const unsigned char *s
, int bits
, int len
)
119 uint32_t h
= FNV1_32_INIT
;
120 const unsigned char *x
= s
+ len
;
123 h
^= irctoupper(*s
++);
124 h
+= (h
<<1) + (h
<<4) + (h
<<7) + (h
<< 8) + (h
<< 24);
127 h
= ((h
>> bits
) ^ h
) & ((1<<bits
)-1);
133 * adds an entry to the id hash table
136 add_to_id_hash(const char *name
, struct Client
*client_p
)
138 if(EmptyString(name
) || (client_p
== NULL
))
141 rb_radixtree_add(client_id_tree
, name
, client_p
);
144 /* add_to_client_hash()
146 * adds an entry (client/server) to the client hash table
149 add_to_client_hash(const char *name
, struct Client
*client_p
)
151 s_assert(name
!= NULL
);
152 s_assert(client_p
!= NULL
);
153 if(EmptyString(name
) || (client_p
== NULL
))
156 rb_radixtree_add(client_name_tree
, name
, client_p
);
159 /* add_to_hostname_hash()
161 * adds a client entry to the hostname hash table
164 add_to_hostname_hash(const char *hostname
, struct Client
*client_p
)
168 s_assert(hostname
!= NULL
);
169 s_assert(client_p
!= NULL
);
170 if(EmptyString(hostname
) || (client_p
== NULL
))
173 list
= rb_radixtree_retrieve(hostname_tree
, hostname
);
176 rb_dlinkAddAlloc(client_p
, list
);
180 list
= rb_malloc(sizeof(*list
));
181 rb_radixtree_add(hostname_tree
, hostname
, list
);
182 rb_dlinkAddAlloc(client_p
, list
);
185 /* add_to_resv_hash()
187 * adds a resv channel entry to the resv hash table
190 add_to_resv_hash(const char *name
, struct ConfItem
*aconf
)
192 s_assert(!EmptyString(name
));
193 s_assert(aconf
!= NULL
);
194 if(EmptyString(name
) || aconf
== NULL
)
197 rb_radixtree_add(resv_tree
, name
, aconf
);
200 /* del_from_id_hash()
202 * removes an id from the id hash table
205 del_from_id_hash(const char *id
, struct Client
*client_p
)
207 s_assert(id
!= NULL
);
208 s_assert(client_p
!= NULL
);
209 if(EmptyString(id
) || client_p
== NULL
)
212 rb_radixtree_delete(client_id_tree
, id
);
215 /* del_from_client_hash()
217 * removes a client/server from the client hash table
220 del_from_client_hash(const char *name
, struct Client
*client_p
)
222 /* no s_asserts, this can happen when removing a client that
225 if(EmptyString(name
) || client_p
== NULL
)
228 rb_radixtree_delete(client_name_tree
, name
);
231 /* del_from_channel_hash()
233 * removes a channel from the channel hash table
236 del_from_channel_hash(const char *name
, struct Channel
*chptr
)
238 s_assert(name
!= NULL
);
239 s_assert(chptr
!= NULL
);
241 if(EmptyString(name
) || chptr
== NULL
)
244 rb_radixtree_delete(channel_tree
, name
);
247 /* del_from_hostname_hash()
249 * removes a client entry from the hostname hash table
252 del_from_hostname_hash(const char *hostname
, struct Client
*client_p
)
256 if(hostname
== NULL
|| client_p
== NULL
)
259 list
= rb_radixtree_retrieve(hostname_tree
, hostname
);
263 rb_dlinkFindDestroy(client_p
, list
);
265 if (rb_dlink_list_length(list
) == 0)
267 rb_radixtree_delete(hostname_tree
, hostname
);
272 /* del_from_resv_hash()
274 * removes a resv entry from the resv hash table
277 del_from_resv_hash(const char *name
, struct ConfItem
*aconf
)
279 s_assert(name
!= NULL
);
280 s_assert(aconf
!= NULL
);
281 if(EmptyString(name
) || aconf
== NULL
)
284 rb_radixtree_delete(resv_tree
, name
);
289 * finds a client entry from the id hash table
292 find_id(const char *name
)
294 if(EmptyString(name
))
297 return rb_radixtree_retrieve(client_id_tree
, name
);
302 * finds a client/server entry from the client hash table
305 find_client(const char *name
)
307 s_assert(name
!= NULL
);
308 if(EmptyString(name
))
311 /* hunting for an id, not a nick */
313 return (find_id(name
));
315 return rb_radixtree_retrieve(client_name_tree
, name
);
318 /* find_named_client()
320 * finds a client/server entry from the client hash table
323 find_named_client(const char *name
)
325 s_assert(name
!= NULL
);
326 if(EmptyString(name
))
329 return rb_radixtree_retrieve(client_name_tree
, name
);
334 * finds a server from the client hash table
337 find_server(struct Client
*source_p
, const char *name
)
339 struct Client
*target_p
;
341 if(EmptyString(name
))
344 if((source_p
== NULL
|| !MyClient(source_p
)) &&
345 IsDigit(*name
) && strlen(name
) == 3)
347 target_p
= find_id(name
);
351 target_p
= rb_radixtree_retrieve(client_name_tree
, name
);
352 if (target_p
!= NULL
)
354 if(IsServer(target_p
) || IsMe(target_p
))
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
368 find_hostname(const char *hostname
)
370 rb_dlink_list
*hlist
;
372 if(EmptyString(hostname
))
375 hlist
= rb_radixtree_retrieve(hostname_tree
, hostname
);
384 * finds a channel from the channel hash table
387 find_channel(const char *name
)
389 s_assert(name
!= NULL
);
390 if(EmptyString(name
))
393 return rb_radixtree_retrieve(channel_tree
, name
);
397 * get_or_create_channel
398 * inputs - client pointer
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
404 * Get Channel block for chname (and allocate a new channel
405 * block, if it didn't exist before).
408 get_or_create_channel(struct Client
*client_p
, const char *chname
, int *isnew
)
410 struct Channel
*chptr
;
412 const char *s
= chname
;
421 if(IsServer(client_p
))
423 sendto_realops_snomask(SNO_DEBUG
, L_ALL
,
424 "*** Long channel name from %s (%d > %d): %s",
425 client_p
->name
, len
, CHANNELLEN
, s
);
429 *(t
+ CHANNELLEN
) = '\0';
433 chptr
= rb_radixtree_retrieve(channel_tree
, s
);
444 chptr
= allocate_channel(s
);
445 chptr
->channelts
= rb_current_time(); /* doesn't hurt to set it here */
447 rb_dlinkAdd(chptr
, &chptr
->node
, &global_channel_list
);
448 rb_radixtree_add(channel_tree
, chptr
->chname
, chptr
);
455 * hunts for a resv entry in the resv hash table
458 hash_find_resv(const char *name
)
460 struct ConfItem
*aconf
;
462 s_assert(name
!= NULL
);
463 if(EmptyString(name
))
466 aconf
= rb_radixtree_retrieve(resv_tree
, name
);
477 clear_resv_hash(void)
479 struct ConfItem
*aconf
;
480 rb_radixtree_iteration_state iter
;
482 RB_RADIXTREE_FOREACH(aconf
, &iter
, resv_tree
)
484 /* skip temp resvs */
488 rb_radixtree_delete(resv_tree
, aconf
->host
);
494 add_to_cli_connid_hash(struct Client
*client_p
, uint32_t id
)
496 rb_dictionary_add(client_connid_tree
, RB_UINT_TO_POINTER(id
), client_p
);
500 del_from_cli_connid_hash(uint32_t id
)
502 rb_dictionary_delete(client_connid_tree
, RB_UINT_TO_POINTER(id
));
506 find_cli_connid_hash(uint32_t connid
)
508 return rb_dictionary_retrieve(client_connid_tree
, RB_UINT_TO_POINTER(connid
));