ircd/hash.c

   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_NETWIDE,
 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[len] = '\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 }