src/hashcomp.cpp

   1 /*
   2  * InspIRCd -- Internet Relay Chat Daemon
   3  *
   4  *   Copyright (C) 2009 Daniel De Graaf <danieldg@inspircd.org>
   5  *   Copyright (C) 2005-2009 Craig Edwards <craigedwards@brainbox.cc>
   6  *   Copyright (C) 2007-2008 Robin Burchell <robin+git@viroteck.net>
   7  *   Copyright (C) 2007 Dennis Friis <peavey@inspircd.org>
   8  *
   9  * This file is part of InspIRCd.  InspIRCd is free software: you can
  10  * redistribute it and/or modify it under the terms of the GNU General Public
  11  * License as published by the Free Software Foundation, version 2.
  12  *
  13  * This program is distributed in the hope that it will be useful, but WITHOUT
  14  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  15  * FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU General Public License
  19  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  20  */
  21
  22
  23 /* $Core */
  24
  25 #include "inspircd.h"
  26 #include "hashcomp.h"
  27 #include "hash_map.h"
  28
  29 /******************************************************
  30  *
  31  * The hash functions of InspIRCd are the centrepoint
  32  * of the entire system. If these functions are
  33  * inefficient or wasteful, the whole program suffers
  34  * as a result. A lot of C programmers in the ircd
  35  * scene spend a lot of time debating (arguing) about
  36  * the best way to write hash functions to hash irc
  37  * nicknames, channels etc.
  38  * We are lucky as C++ developers as hash_map does
  39  * a lot of this for us. It does intellegent memory
  40  * requests, bucketing, search functions, insertion
  41  * and deletion etc. All we have to do is write some
  42  * overloaded comparison and hash value operators which
  43  * cause it to act in an irc-like way. The features we
  44  * add to the standard hash_map are:
  45  *
  46  * Case insensitivity: The hash_map will be case
  47  * insensitive.
  48  *
  49  * Scandanavian Comparisons: The characters [, ], \ will
  50  * be considered the lowercase of {, } and |.
  51  *
  52  ******************************************************/
  53
  54 /** A mapping of uppercase to lowercase, including scandinavian
  55  * 'oddities' as specified by RFC1459, e.g. { -> [, and | -> \
  56  */
  57 unsigned const char rfc_case_insensitive_map[256] = {
  58         0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,                                   /* 0-19 */
  59         20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39,                         /* 20-39 */
  60         40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59,                         /* 40-59 */
  61         60, 61, 62, 63, 64, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111,             /* 60-79 */
  62         112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 94, 95, 96, 97, 98, 99,           /* 80-99 */
  63         100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119,     /* 100-119 */
  64         120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139,     /* 120-139 */
  65         140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159,     /* 140-159 */
  66         160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179,     /* 160-179 */
  67         180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199,     /* 180-199 */
  68         200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219,     /* 200-219 */
  69         220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239,     /* 220-239 */
  70         240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255                          /* 240-255 */
  71 };
  72
  73 /** Case insensitive map, ASCII rules.
  74  * That is;
  75  * [ != {, but A == a.
  76  */
  77 unsigned const char ascii_case_insensitive_map[256] = {
  78         0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,                                   /* 0-19 */
  79         20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39,                         /* 20-39 */
  80         40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59,                         /* 40-59 */
  81         60, 61, 62, 63, 64, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111,             /* 60-79 */
  82         112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 91, 92, 93, 94, 95, 96, 97, 98, 99,              /* 80-99 */
  83         100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119,     /* 100-119 */
  84         120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139,     /* 120-139 */
  85         140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159,     /* 140-159 */
  86         160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179,     /* 160-179 */
  87         180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199,     /* 180-199 */
  88         200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219,     /* 200-219 */
  89         220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239,     /* 220-239 */
  90         240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255                          /* 240-255 */
  91 };
  92
  93 /** Case sensitive map.
  94  * Can technically also be used for ASCII case sensitive comparisons, as [ != {, etc.
  95  */
  96 unsigned const char rfc_case_sensitive_map[256] = {
  97         0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
  98         21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
  99         41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60,
 100         61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80,
 101         81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100,
 102         101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120,
 103         121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140,
 104         141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160,
 105         161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180,
 106         181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200,
 107         201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220,
 108         221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240,
 109         241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255
 110 };
 111
 112 /* convert a string to lowercase. Note following special circumstances
 113  * taken from RFC 1459. Many "official" server branches still hold to this
 114  * rule so i will too;
 115  *
 116  *  Because of IRC's scandanavian origin, the characters {}| are
 117  *  considered to be the lower case equivalents of the characters []\,
 118  *  respectively. This is a critical issue when determining the
 119  *  equivalence of two nicknames.
 120  */
 121 void nspace::strlower(char *n)
 122 {
 123         if (n)
 124         {
 125                 for (char* t = n; *t; t++)
 126                         *t = national_case_insensitive_map[(unsigned char)*t];
 127         }
 128 }
 129
 130 #if defined(WINDOWS) && !defined(HASHMAP_DEPRECATED)
 131         size_t nspace::hash_compare<std::string, std::less<std::string> >::operator()(const std::string &s) const
 132 #else
 133         #ifdef HASHMAP_DEPRECATED
 134                 size_t CoreExport nspace::insensitive::operator()(const std::string &s) const
 135         #else
 136                 size_t nspace::hash<std::string>::operator()(const std::string &s) const
 137         #endif
 138 #endif
 139 {
 140         /* XXX: NO DATA COPIES! :)
 141          * The hash function here is practically
 142          * a copy of the one in STL's hash_fun.h,
 143          * only with *x replaced with national_case_insensitive_map[*x].
 144          * This avoids a copy to use hash<const char*>
 145          */
 146         register size_t t = 0;
 147         for (std::string::const_iterator x = s.begin(); x != s.end(); ++x) /* ++x not x++, as its faster */
 148                 t = 5 * t + national_case_insensitive_map[(unsigned char)*x];
 149         return t;
 150 }
 151
 152
 153 #if defined(WINDOWS) && !defined(HASHMAP_DEPRECATED)
 154         size_t nspace::hash_compare<irc::string, std::less<irc::string> >::operator()(const irc::string &s) const
 155 #else
 156         size_t CoreExport irc::hash::operator()(const irc::string &s) const
 157 #endif
 158 {
 159         register size_t t = 0;
 160         for (irc::string::const_iterator x = s.begin(); x != s.end(); ++x) /* ++x not x++, as its faster */
 161                 t = 5 * t + national_case_insensitive_map[(unsigned char)*x];
 162         return t;
 163 }
 164
 165 bool irc::StrHashComp::operator()(const std::string& s1, const std::string& s2) const
 166 {
 167         const unsigned char* n1 = (const unsigned char*)s1.c_str();
 168         const unsigned char* n2 = (const unsigned char*)s2.c_str();
 169         for (; *n1 && *n2; n1++, n2++)
 170                 if (national_case_insensitive_map[*n1] != national_case_insensitive_map[*n2])
 171                         return false;
 172         return (national_case_insensitive_map[*n1] == national_case_insensitive_map[*n2]);
 173 }
 174
 175 /******************************************************
 176  *
 177  * This is the implementation of our special irc::string
 178  * class which is a case-insensitive equivalent to
 179  * std::string which is not only case-insensitive but
 180  * can also do scandanavian comparisons, e.g. { = [, etc.
 181  *
 182  * This class depends on the const array 'national_case_insensitive_map'.
 183  *
 184  ******************************************************/
 185
 186 bool irc::irc_char_traits::eq(char c1st, char c2nd)
 187 {
 188         return national_case_insensitive_map[(unsigned char)c1st] == national_case_insensitive_map[(unsigned char)c2nd];
 189 }
 190
 191 bool irc::irc_char_traits::ne(char c1st, char c2nd)
 192 {
 193         return national_case_insensitive_map[(unsigned char)c1st] != national_case_insensitive_map[(unsigned char)c2nd];
 194 }
 195
 196 bool irc::irc_char_traits::lt(char c1st, char c2nd)
 197 {
 198         return national_case_insensitive_map[(unsigned char)c1st] < national_case_insensitive_map[(unsigned char)c2nd];
 199 }
 200
 201 int irc::irc_char_traits::compare(const char* str1, const char* str2, size_t n)
 202 {
 203         for(unsigned int i = 0; i < n; i++)
 204         {
 205                 if(national_case_insensitive_map[(unsigned char)*str1] > national_case_insensitive_map[(unsigned char)*str2])
 206                         return 1;
 207
 208                 if(national_case_insensitive_map[(unsigned char)*str1] < national_case_insensitive_map[(unsigned char)*str2])
 209                         return -1;
 210
 211                 if(*str1 == 0 || *str2 == 0)
 212                         return 0;
 213
 214                 str1++;
 215                 str2++;
 216         }
 217         return 0;
 218 }
 219
 220 const char* irc::irc_char_traits::find(const char* s1, int  n, char c)
 221 {
 222         while(n-- > 0 && national_case_insensitive_map[(unsigned char)*s1] != national_case_insensitive_map[(unsigned char)c])
 223                 s1++;
 224         return (n >= 0) ? s1 : NULL;
 225 }
 226
 227 irc::tokenstream::tokenstream(const std::string &source) : tokens(source), last_pushed(false)
 228 {
 229         /* Record starting position and current position */
 230         last_starting_position = tokens.begin();
 231         n = tokens.begin();
 232 }
 233
 234 irc::tokenstream::~tokenstream()
 235 {
 236 }
 237
 238 bool irc::tokenstream::GetToken(std::string &token)
 239 {
 240         std::string::iterator lsp = last_starting_position;
 241
 242         while (n != tokens.end())
 243         {
 244                 /** Skip multi space, converting "  " into " "
 245                  */
 246                 while ((n+1 != tokens.end()) && (*n == ' ') && (*(n+1) == ' '))
 247                         n++;
 248
 249                 if ((last_pushed) && (*n == ':'))
 250                 {
 251                         /* If we find a token thats not the first and starts with :,
 252                          * this is the last token on the line
 253                          */
 254                         std::string::iterator curr = ++n;
 255                         n = tokens.end();
 256                         token = std::string(curr, tokens.end());
 257                         return true;
 258                 }
 259
 260                 last_pushed = false;
 261
 262                 if ((*n == ' ') || (n+1 == tokens.end()))
 263                 {
 264                         /* If we find a space, or end of string, this is the end of a token.
 265                          */
 266                         last_starting_position = n+1;
 267                         last_pushed = *n == ' ';
 268
 269                         std::string strip(lsp, n+1 == tokens.end() ? n+1  : n++);
 270                         while ((strip.length()) && (strip.find_last_of(' ') == strip.length() - 1))
 271                                 strip.erase(strip.end() - 1);
 272
 273                         token = strip;
 274                         return !token.empty();
 275                 }
 276
 277                 n++;
 278         }
 279         token.clear();
 280         return false;
 281 }
 282
 283 bool irc::tokenstream::GetToken(irc::string &token)
 284 {
 285         std::string stdstring;
 286         bool returnval = GetToken(stdstring);
 287         token = assign(stdstring);
 288         return returnval;
 289 }
 290
 291 bool irc::tokenstream::GetToken(int &token)
 292 {
 293         std::string tok;
 294         bool returnval = GetToken(tok);
 295         token = ConvToInt(tok);
 296         return returnval;
 297 }
 298
 299 bool irc::tokenstream::GetToken(long &token)
 300 {
 301         std::string tok;
 302         bool returnval = GetToken(tok);
 303         token = ConvToInt(tok);
 304         return returnval;
 305 }
 306
 307 irc::sepstream::sepstream(const std::string &source, char seperator) : tokens(source), sep(seperator)
 308 {
 309         last_starting_position = tokens.begin();
 310         n = tokens.begin();
 311 }
 312
 313 bool irc::sepstream::GetToken(std::string &token)
 314 {
 315         std::string::iterator lsp = last_starting_position;
 316
 317         while (n != tokens.end())
 318         {
 319                 if ((*n == sep) || (n+1 == tokens.end()))
 320                 {
 321                         last_starting_position = n+1;
 322                         token = std::string(lsp, n+1 == tokens.end() ? n+1  : n++);
 323
 324                         while ((token.length()) && (token.find_last_of(sep) == token.length() - 1))
 325                                 token.erase(token.end() - 1);
 326
 327                         if (token.empty())
 328                                 n++;
 329
 330                         return n == tokens.end() ? false : true;
 331                 }
 332
 333                 n++;
 334         }
 335
 336         token = "";
 337         return false;
 338 }
 339
 340 const std::string irc::sepstream::GetRemaining()
 341 {
 342         return std::string(n, tokens.end());
 343 }
 344
 345 bool irc::sepstream::StreamEnd()
 346 {
 347         return ((n + 1) == tokens.end());
 348 }
 349
 350 irc::sepstream::~sepstream()
 351 {
 352 }
 353
 354 std::string irc::hex(const unsigned char *raw, size_t rawsz)
 355 {
 356         if (!rawsz)
 357                 return "";
 358
 359         /* EWW! This used to be using sprintf, which is WAY inefficient. -Special */
 360
 361         const char *hex = "0123456789abcdef";
 362         static char hexbuf[MAXBUF];
 363
 364         size_t i, j;
 365         for (i = 0, j = 0; j < rawsz; ++j)
 366         {
 367                 hexbuf[i++] = hex[raw[j] / 16];
 368                 hexbuf[i++] = hex[raw[j] % 16];
 369         }
 370         hexbuf[i] = 0;
 371
 372         return hexbuf;
 373 }
 374
 375 CoreExport const char* irc::Spacify(const char* n)
 376 {
 377         static char x[MAXBUF];
 378         strlcpy(x,n,MAXBUF);
 379         for (char* y = x; *y; y++)
 380                 if (*y == '_')
 381                         *y = ' ';
 382         return x;
 383 }
 384
 385
 386 irc::modestacker::modestacker(bool add) : adding(add)
 387 {
 388         sequence.clear();
 389         sequence.push_back("");
 390 }
 391
 392 void irc::modestacker::Push(char modeletter, const std::string &parameter)
 393 {
 394         *(sequence.begin()) += modeletter;
 395         sequence.push_back(parameter);
 396 }
 397
 398 void irc::modestacker::Push(char modeletter)
 399 {
 400         this->Push(modeletter,"");
 401 }
 402
 403 void irc::modestacker::PushPlus()
 404 {
 405         this->Push('+',"");
 406 }
 407
 408 void irc::modestacker::PushMinus()
 409 {
 410         this->Push('-',"");
 411 }
 412
 413 int irc::modestacker::GetStackedLine(std::vector<std::string> &result, int max_line_size)
 414 {
 415         if (sequence.empty())
 416         {
 417                 return 0;
 418         }
 419
 420         unsigned int n = 0;
 421         int size = 1; /* Account for initial +/- char */
 422         int nextsize = 0;
 423         int start = result.size();
 424         std::string modeline = adding ? "+" : "-";
 425         result.push_back(modeline);
 426
 427         if (sequence.size() > 1)
 428                 nextsize = sequence[1].length() + 2;
 429
 430         while (!sequence[0].empty() && (sequence.size() > 1) && (n < ServerInstance->Config->Limits.MaxModes) && ((size + nextsize) < max_line_size))
 431         {
 432                 modeline += *(sequence[0].begin());
 433                 if (!sequence[1].empty())
 434                 {
 435                         result.push_back(sequence[1]);
 436                         size += nextsize; /* Account for mode character and whitespace */
 437                 }
 438                 sequence[0].erase(sequence[0].begin());
 439                 sequence.erase(sequence.begin() + 1);
 440
 441                 if (sequence.size() > 1)
 442                         nextsize = sequence[1].length() + 2;
 443
 444                 n++;
 445         }
 446         result[start] = modeline;
 447
 448         return n;
 449 }
 450
 451 irc::stringjoiner::stringjoiner(const std::string &seperator, const std::vector<std::string> &sequence, int begin, int end)
 452 {
 453         if (end < begin)
 454                 return; // nothing to do here
 455
 456         for (int v = begin; v < end; v++)
 457                 joined.append(sequence[v]).append(seperator);
 458         joined.append(sequence[end]);
 459 }
 460
 461 irc::stringjoiner::stringjoiner(const std::string &seperator, const std::deque<std::string> &sequence, int begin, int end)
 462 {
 463         if (end < begin)
 464                 return; // nothing to do here
 465
 466         for (int v = begin; v < end; v++)
 467                 joined.append(sequence[v]).append(seperator);
 468         joined.append(sequence[end]);
 469 }
 470
 471 irc::stringjoiner::stringjoiner(const std::string &seperator, const char* const* sequence, int begin, int end)
 472 {
 473         if (end < begin)
 474                 return; // nothing to do here
 475
 476         for (int v = begin; v < end; v++)
 477                 joined.append(sequence[v]).append(seperator);
 478         joined.append(sequence[end]);
 479 }
 480
 481 std::string& irc::stringjoiner::GetJoined()
 482 {
 483         return joined;
 484 }
 485
 486 irc::portparser::portparser(const std::string &source, bool allow_overlapped)
 487         : sep(source), in_range(0), range_begin(0), range_end(0), overlapped(allow_overlapped)
 488 {
 489 }
 490
 491 bool irc::portparser::Overlaps(long val)
 492 {
 493         if (overlapped)
 494                 return false;
 495
 496         return (!overlap_set.insert(val).second);
 497 }
 498
 499 long irc::portparser::GetToken()
 500 {
 501         if (in_range > 0)
 502         {
 503                 in_range++;
 504                 if (in_range <= range_end)
 505                 {
 506                         if (!Overlaps(in_range))
 507                         {
 508                                 return in_range;
 509                         }
 510                         else
 511                         {
 512                                 while (((Overlaps(in_range)) && (in_range <= range_end)))
 513                                         in_range++;
 514
 515                                 if (in_range <= range_end)
 516                                         return in_range;
 517                         }
 518                 }
 519                 else
 520                         in_range = 0;
 521         }
 522
 523         std::string x;
 524         sep.GetToken(x);
 525
 526         if (x.empty())
 527                 return 0;
 528
 529         while (Overlaps(atoi(x.c_str())))
 530         {
 531                 if (!sep.GetToken(x))
 532                         return 0;
 533         }
 534
 535         std::string::size_type dash = x.rfind('-');
 536         if (dash != std::string::npos)
 537         {
 538                 std::string sbegin = x.substr(0, dash);
 539                 std::string send = x.substr(dash+1, x.length());
 540                 range_begin = atoi(sbegin.c_str());
 541                 range_end = atoi(send.c_str());
 542
 543                 if ((range_begin > 0) && (range_end > 0) && (range_begin < 65536) && (range_end < 65536) && (range_begin < range_end))
 544                 {
 545                         in_range = range_begin;
 546                         return in_range;
 547                 }
 548                 else
 549                 {
 550                         /* Assume its just the one port */
 551                         return atoi(sbegin.c_str());
 552                 }
 553         }
 554         else
 555         {
 556                 return atoi(x.c_str());
 557         }
 558 }
 559
 560 /*const std::basic_string& SearchAndReplace(std::string& text, const std::string& pattern, const std::string& replace)
 561 {
 562         std::string replacement;
 563         if ((!pattern.empty()) && (!text.empty()))
 564         {
 565                 for (std::string::size_type n = 0; n != text.length(); ++n)
 566                 {
 567                         if (text.length() >= pattern.length() && text.substr(n, pattern.length()) == pattern)
 568                         {
 569                                 replacement.append(replace);
 570                                 n = n + pattern.length() - 1;
 571                         }
 572                         else
 573                         {
 574                                 replacement += text[n];
 575                         }
 576                 }
 577         }
 578         text = replacement;
 579         return text;
 580 }*/