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 #include "inspircd.h"
  24 #include "hashcomp.h"
  25
  26 /******************************************************
  27  *
  28  * The hash functions of InspIRCd are the centrepoint
  29  * of the entire system. If these functions are
  30  * inefficient or wasteful, the whole program suffers
  31  * as a result. A lot of C programmers in the ircd
  32  * scene spend a lot of time debating (arguing) about
  33  * the best way to write hash functions to hash irc
  34  * nicknames, channels etc.
  35  * We are lucky as C++ developers as unordered_map does
  36  * a lot of this for us. It does intellegent memory
  37  * requests, bucketing, search functions, insertion
  38  * and deletion etc. All we have to do is write some
  39  * overloaded comparison and hash value operators which
  40  * cause it to act in an irc-like way. The features we
  41  * add to the standard hash_map are:
  42  *
  43  * Case insensitivity: The hash_map will be case
  44  * insensitive.
  45  *
  46  * Scandanavian Comparisons: The characters [, ], \ will
  47  * be considered the lowercase of {, } and |.
  48  *
  49  ******************************************************/
  50
  51
  52 /**
  53  * A case insensitive mapping of characters from upper case to lower case for
  54  * the ASCII character set.
  55  */
  56 unsigned const char ascii_case_insensitive_map[256] = {
  57         0,   1,   2,   3,   4,   5,   6,   7,   8,   9,   // 0-9
  58         10,  11,  12,  13,  14,  15,  16,  17,  18,  19,  // 10-19
  59         20,  21,  22,  23,  24,  25,  26,  27,  28,  29,  // 20-29
  60         30,  31,  32,  33,  34,  35,  36,  37,  38,  39,  // 30-39
  61         40,  41,  42,  43,  44,  45,  46,  47,  48,  49,  // 40-49
  62         50,  51,  52,  53,  54,  55,  56,  57,  58,  59,  // 50-59
  63         60,  61,  62,  63,  64,  97,  98,  99,  100, 101, // 60-69
  64         102, 103, 104, 105, 106, 107, 108, 109, 110, 111, // 70-79
  65         112, 113, 114, 115, 116, 117, 118, 119, 120, 121, // 80-89
  66         122, 91,  92,  93,  94,  95,  96,  97,  98,  99,  // 90-99
  67         100, 101, 102, 103, 104, 105, 106, 107, 108, 109, // 100-109
  68         110, 111, 112, 113, 114, 115, 116, 117, 118, 119, // 110-119
  69         120, 121, 122, 123, 124, 125, 126, 127, 128, 129, // 120-129
  70         130, 131, 132, 133, 134, 135, 136, 137, 138, 139, // 130-139
  71         140, 141, 142, 143, 144, 145, 146, 147, 148, 149, // 140-149
  72         150, 151, 152, 153, 154, 155, 156, 157, 158, 159, // 150-159
  73         160, 161, 162, 163, 164, 165, 166, 167, 168, 169, // 160-169
  74         170, 171, 172, 173, 174, 175, 176, 177, 178, 179, // 170-179
  75         180, 181, 182, 183, 184, 185, 186, 187, 188, 189, // 180-189
  76         190, 191, 192, 193, 194, 195, 196, 197, 198, 199, // 190-199
  77         200, 201, 202, 203, 204, 205, 206, 207, 208, 209, // 200-209
  78         210, 211, 212, 213, 214, 215, 216, 217, 218, 219, // 210-219
  79         220, 221, 222, 223, 224, 225, 226, 227, 228, 229, // 220-229
  80         230, 231, 232, 233, 234, 235, 236, 237, 238, 239, // 230-249
  81         240, 241, 242, 243, 244, 245, 246, 247, 248, 249, // 240-249
  82         250, 251, 252, 253, 254, 255,                     // 250-255
  83 };
  84
  85
  86
  87 /**
  88  * A case insensitive mapping of characters from upper case to lower case for
  89  * the character set of RFC 1459. This is identical to ASCII with the small
  90  * exception of {}| being considered to be the lower case equivalents of the
  91  * characters []\ respectively.
  92  */
  93 unsigned const char rfc_case_insensitive_map[256] = {
  94         0,   1,   2,   3,   4,   5,   6,   7,   8,   9,   // 0-9
  95         10,  11,  12,  13,  14,  15,  16,  17,  18,  19,  // 10-19
  96         20,  21,  22,  23,  24,  25,  26,  27,  28,  29,  // 20-29
  97         30,  31,  32,  33,  34,  35,  36,  37,  38,  39,  // 30-39
  98         40,  41,  42,  43,  44,  45,  46,  47,  48,  49,  // 40-49
  99         50,  51,  52,  53,  54,  55,  56,  57,  58,  59,  // 50-59
 100         60,  61,  62,  63,  64,  97,  98,  99,  100, 101, // 60-69
 101         102, 103, 104, 105, 106, 107, 108, 109, 110, 111, // 70-79
 102         112, 113, 114, 115, 116, 117, 118, 119, 120, 121, // 80-89
 103         122, 123, 124, 125, 94,  95,  96,  97,  98,  99,  // 90-99
 104         100, 101, 102, 103, 104, 105, 106, 107, 108, 109, // 100-109
 105         110, 111, 112, 113, 114, 115, 116, 117, 118, 119, // 110-119
 106         120, 121, 122, 123, 124, 125, 126, 127, 128, 129, // 120-129
 107         130, 131, 132, 133, 134, 135, 136, 137, 138, 139, // 130-139
 108         140, 141, 142, 143, 144, 145, 146, 147, 148, 149, // 140-149
 109         150, 151, 152, 153, 154, 155, 156, 157, 158, 159, // 150-159
 110         160, 161, 162, 163, 164, 165, 166, 167, 168, 169, // 160-169
 111         170, 171, 172, 173, 174, 175, 176, 177, 178, 179, // 170-179
 112         180, 181, 182, 183, 184, 185, 186, 187, 188, 189, // 180-189
 113         190, 191, 192, 193, 194, 195, 196, 197, 198, 199, // 190-199
 114         200, 201, 202, 203, 204, 205, 206, 207, 208, 209, // 200-209
 115         210, 211, 212, 213, 214, 215, 216, 217, 218, 219, // 210-219
 116         220, 221, 222, 223, 224, 225, 226, 227, 228, 229, // 220-229
 117         230, 231, 232, 233, 234, 235, 236, 237, 238, 239, // 230-239
 118         240, 241, 242, 243, 244, 245, 246, 247, 248, 249, // 240-249
 119         250, 251, 252, 253, 254, 255,                     // 250-255
 120 };
 121
 122 /**
 123  * A case sensitive mapping of characters from upper case to lower case for the
 124  * character set of RFC 1459. This is identical to ASCII.
 125  */
 126 unsigned const char rfc_case_sensitive_map[256] = {
 127         0,   1,   2,   3,   4,   5,   6,   7,   8,   9,   // 0-9
 128         10,  11,  12,  13,  14,  15,  16,  17,  18,  19,  // 10-19
 129         20,  21,  22,  23,  24,  25,  26,  27,  28,  29,  // 20-29
 130         30,  31,  32,  33,  34,  35,  36,  37,  38,  39,  // 30-39
 131         40,  41,  42,  43,  44,  45,  46,  47,  48,  49,  // 40-49
 132         50,  51,  52,  53,  54,  55,  56,  57,  58,  59,  // 50-59
 133         60,  61,  62,  63,  64,  65,  66,  67,  68,  69,  // 60-69
 134         70,  71,  72,  73,  74,  75,  76,  77,  78,  79,  // 70-79
 135         80,  81,  82,  83,  84,  85,  86,  87,  88,  89,  // 80-89
 136         90,  91,  92,  93,  94,  95,  96,  97,  98,  99,  // 90-99
 137         100, 101, 102, 103, 104, 105, 106, 107, 108, 109, // 100-109
 138         110, 111, 112, 113, 114, 115, 116, 117, 118, 119, // 110-119
 139         120, 121, 122, 123, 124, 125, 126, 127, 128, 129, // 120-129
 140         130, 131, 132, 133, 134, 135, 136, 137, 138, 139, // 130-139
 141         140, 141, 142, 143, 144, 145, 146, 147, 148, 149, // 140-149
 142         150, 151, 152, 153, 154, 155, 156, 157, 158, 159, // 150-159
 143         160, 161, 162, 163, 164, 165, 166, 167, 168, 169, // 160-169
 144         170, 171, 172, 173, 174, 175, 176, 177, 178, 179, // 170-179
 145         180, 181, 182, 183, 184, 185, 186, 187, 188, 189, // 180-189
 146         190, 191, 192, 193, 194, 195, 196, 197, 198, 199, // 190-199
 147         200, 201, 202, 203, 204, 205, 206, 207, 208, 209, // 200-209
 148         210, 211, 212, 213, 214, 215, 216, 217, 218, 219, // 210-219
 149         220, 221, 222, 223, 224, 225, 226, 227, 228, 229, // 220-229
 150         230, 231, 232, 233, 234, 235, 236, 237, 238, 239, // 230-239
 151         240, 241, 242, 243, 244, 245, 246, 247, 248, 249, // 240-249
 152         250, 251, 252, 253, 254, 255,                     // 250-255
 153 };
 154
 155 size_t CoreExport irc::hash::operator()(const irc::string &s) const
 156 {
 157         register size_t t = 0;
 158         for (irc::string::const_iterator x = s.begin(); x != s.end(); ++x) /* ++x not x++, as its faster */
 159                 t = 5 * t + national_case_insensitive_map[(unsigned char)*x];
 160         return t;
 161 }
 162
 163 bool irc::StrHashComp::operator()(const std::string& s1, const std::string& s2) const
 164 {
 165         const unsigned char* n1 = (const unsigned char*)s1.c_str();
 166         const unsigned char* n2 = (const unsigned char*)s2.c_str();
 167         for (; *n1 && *n2; n1++, n2++)
 168                 if (national_case_insensitive_map[*n1] != national_case_insensitive_map[*n2])
 169                         return false;
 170         return (national_case_insensitive_map[*n1] == national_case_insensitive_map[*n2]);
 171 }
 172
 173 bool irc::insensitive_swo::operator()(const std::string& a, const std::string& b) const
 174 {
 175         const unsigned char* charmap = national_case_insensitive_map;
 176         std::string::size_type asize = a.size();
 177         std::string::size_type bsize = b.size();
 178         std::string::size_type maxsize = std::min(asize, bsize);
 179
 180         for (std::string::size_type i = 0; i < maxsize; i++)
 181         {
 182                 unsigned char A = charmap[(unsigned char)a[i]];
 183                 unsigned char B = charmap[(unsigned char)b[i]];
 184                 if (A > B)
 185                         return false;
 186                 else if (A < B)
 187                         return true;
 188         }
 189         return (asize < bsize);
 190 }
 191
 192 size_t irc::insensitive::operator()(const std::string &s) const
 193 {
 194         /* XXX: NO DATA COPIES! :)
 195          * The hash function here is practically
 196          * a copy of the one in STL's hash_fun.h,
 197          * only with *x replaced with national_case_insensitive_map[*x].
 198          * This avoids a copy to use hash<const char*>
 199          */
 200         register size_t t = 0;
 201         for (std::string::const_iterator x = s.begin(); x != s.end(); ++x) /* ++x not x++, as its faster */
 202                 t = 5 * t + national_case_insensitive_map[(unsigned char)*x];
 203         return t;
 204 }
 205
 206 /******************************************************
 207  *
 208  * This is the implementation of our special irc::string
 209  * class which is a case-insensitive equivalent to
 210  * std::string which is not only case-insensitive but
 211  * can also do scandanavian comparisons, e.g. { = [, etc.
 212  *
 213  * This class depends on the const array 'national_case_insensitive_map'.
 214  *
 215  ******************************************************/
 216
 217 bool irc::irc_char_traits::eq(char c1st, char c2nd)
 218 {
 219         return national_case_insensitive_map[(unsigned char)c1st] == national_case_insensitive_map[(unsigned char)c2nd];
 220 }
 221
 222 bool irc::irc_char_traits::ne(char c1st, char c2nd)
 223 {
 224         return national_case_insensitive_map[(unsigned char)c1st] != national_case_insensitive_map[(unsigned char)c2nd];
 225 }
 226
 227 bool irc::irc_char_traits::lt(char c1st, char c2nd)
 228 {
 229         return national_case_insensitive_map[(unsigned char)c1st] < national_case_insensitive_map[(unsigned char)c2nd];
 230 }
 231
 232 int irc::irc_char_traits::compare(const char* str1, const char* str2, size_t n)
 233 {
 234         for(unsigned int i = 0; i < n; i++)
 235         {
 236                 if(national_case_insensitive_map[(unsigned char)*str1] > national_case_insensitive_map[(unsigned char)*str2])
 237                         return 1;
 238
 239                 if(national_case_insensitive_map[(unsigned char)*str1] < national_case_insensitive_map[(unsigned char)*str2])
 240                         return -1;
 241
 242                 if(*str1 == 0 || *str2 == 0)
 243                         return 0;
 244
 245                 str1++;
 246                 str2++;
 247         }
 248         return 0;
 249 }
 250
 251 const char* irc::irc_char_traits::find(const char* s1, int  n, char c)
 252 {
 253         while(n-- > 0 && national_case_insensitive_map[(unsigned char)*s1] != national_case_insensitive_map[(unsigned char)c])
 254                 s1++;
 255         return (n >= 0) ? s1 : NULL;
 256 }
 257
 258 irc::tokenstream::tokenstream(const std::string &source) : spacesepstream(source)
 259 {
 260 }
 261
 262 bool irc::tokenstream::GetToken(std::string &token)
 263 {
 264         bool first = !pos;
 265
 266         if (!spacesepstream::GetToken(token))
 267                 return false;
 268
 269         /* This is the last parameter */
 270         if (token[0] == ':' && !first)
 271         {
 272                 token = token.substr(1);
 273                 if (!StreamEnd())
 274                 {
 275                         token += ' ';
 276                         token += GetRemaining();
 277                 }
 278                 pos = tokens.length() + 1;
 279         }
 280
 281         return true;
 282 }
 283
 284 bool irc::tokenstream::GetToken(irc::string &token)
 285 {
 286         std::string stdstring;
 287         bool returnval = GetToken(stdstring);
 288         token = assign(stdstring);
 289         return returnval;
 290 }
 291
 292 bool irc::tokenstream::GetToken(int &token)
 293 {
 294         std::string tok;
 295         bool returnval = GetToken(tok);
 296         token = ConvToInt(tok);
 297         return returnval;
 298 }
 299
 300 bool irc::tokenstream::GetToken(long &token)
 301 {
 302         std::string tok;
 303         bool returnval = GetToken(tok);
 304         token = ConvToInt(tok);
 305         return returnval;
 306 }
 307
 308 irc::sepstream::sepstream(const std::string& source, char separator, bool allowempty)
 309         : tokens(source), sep(separator), pos(0), allow_empty(allowempty)
 310 {
 311 }
 312
 313 bool irc::sepstream::GetToken(std::string &token)
 314 {
 315         if (this->StreamEnd())
 316         {
 317                 token.clear();
 318                 return false;
 319         }
 320
 321         if (!this->allow_empty)
 322         {
 323                 this->pos = this->tokens.find_first_not_of(this->sep, this->pos);
 324                 if (this->pos == std::string::npos)
 325                 {
 326                         this->pos = this->tokens.length() + 1;
 327                         token.clear();
 328                         return false;
 329                 }
 330         }
 331
 332         size_t p = this->tokens.find(this->sep, this->pos);
 333         if (p == std::string::npos)
 334                 p = this->tokens.length();
 335
 336         token = this->tokens.substr(this->pos, p - this->pos);
 337         this->pos = p + 1;
 338
 339         return true;
 340 }
 341
 342 const std::string irc::sepstream::GetRemaining()
 343 {
 344         return !this->StreamEnd() ? this->tokens.substr(this->pos) : "";
 345 }
 346
 347 bool irc::sepstream::StreamEnd()
 348 {
 349         return this->pos > this->tokens.length();
 350 }
 351
 352 irc::modestacker::modestacker(bool add) : adding(add)
 353 {
 354         sequence.clear();
 355         sequence.push_back("");
 356 }
 357
 358 void irc::modestacker::Push(char modeletter, const std::string &parameter)
 359 {
 360         *(sequence.begin()) += modeletter;
 361         sequence.push_back(parameter);
 362 }
 363
 364 void irc::modestacker::Push(char modeletter)
 365 {
 366         this->Push(modeletter,"");
 367 }
 368
 369 void irc::modestacker::PushPlus()
 370 {
 371         this->Push('+',"");
 372 }
 373
 374 void irc::modestacker::PushMinus()
 375 {
 376         this->Push('-',"");
 377 }
 378
 379 int irc::modestacker::GetStackedLine(std::vector<std::string> &result, int max_line_size)
 380 {
 381         if (sequence.empty())
 382         {
 383                 return 0;
 384         }
 385
 386         unsigned int n = 0;
 387         int size = 1; /* Account for initial +/- char */
 388         int nextsize = 0;
 389         int start = result.size();
 390         std::string modeline = adding ? "+" : "-";
 391         result.push_back(modeline);
 392
 393         if (sequence.size() > 1)
 394                 nextsize = sequence[1].length() + 2;
 395
 396         while (!sequence[0].empty() && (sequence.size() > 1) && (n < ServerInstance->Config->Limits.MaxModes) && ((size + nextsize) < max_line_size))
 397         {
 398                 modeline += *(sequence[0].begin());
 399                 if (!sequence[1].empty())
 400                 {
 401                         result.push_back(sequence[1]);
 402                         size += nextsize; /* Account for mode character and whitespace */
 403                 }
 404                 sequence[0].erase(sequence[0].begin());
 405                 sequence.erase(sequence.begin() + 1);
 406
 407                 if (sequence.size() > 1)
 408                         nextsize = sequence[1].length() + 2;
 409
 410                 n++;
 411         }
 412         result[start] = modeline;
 413
 414         return n;
 415 }
 416
 417 irc::stringjoiner::stringjoiner(const std::vector<std::string>& sequence)
 418 {
 419         if (sequence.empty())
 420                 return; // nothing to do here
 421
 422         for (std::vector<std::string>::const_iterator i = sequence.begin(); i != sequence.end(); ++i)
 423                 joined.append(*i).push_back(' ');
 424         joined.erase(joined.end()-1);
 425 }
 426
 427 irc::portparser::portparser(const std::string &source, bool allow_overlapped)
 428         : sep(source), in_range(0), range_begin(0), range_end(0), overlapped(allow_overlapped)
 429 {
 430 }
 431
 432 bool irc::portparser::Overlaps(long val)
 433 {
 434         if (overlapped)
 435                 return false;
 436
 437         return (!overlap_set.insert(val).second);
 438 }
 439
 440 long irc::portparser::GetToken()
 441 {
 442         if (in_range > 0)
 443         {
 444                 in_range++;
 445                 if (in_range <= range_end)
 446                 {
 447                         if (!Overlaps(in_range))
 448                         {
 449                                 return in_range;
 450                         }
 451                         else
 452                         {
 453                                 while (((Overlaps(in_range)) && (in_range <= range_end)))
 454                                         in_range++;
 455
 456                                 if (in_range <= range_end)
 457                                         return in_range;
 458                         }
 459                 }
 460                 else
 461                         in_range = 0;
 462         }
 463
 464         std::string x;
 465         sep.GetToken(x);
 466
 467         if (x.empty())
 468                 return 0;
 469
 470         while (Overlaps(atoi(x.c_str())))
 471         {
 472                 if (!sep.GetToken(x))
 473                         return 0;
 474         }
 475
 476         std::string::size_type dash = x.rfind('-');
 477         if (dash != std::string::npos)
 478         {
 479                 std::string sbegin = x.substr(0, dash);
 480                 std::string send = x.substr(dash+1, x.length());
 481                 range_begin = atoi(sbegin.c_str());
 482                 range_end = atoi(send.c_str());
 483
 484                 if ((range_begin > 0) && (range_end > 0) && (range_begin < 65536) && (range_end < 65536) && (range_begin < range_end))
 485                 {
 486                         in_range = range_begin;
 487                         return in_range;
 488                 }
 489                 else
 490                 {
 491                         /* Assume its just the one port */
 492                         return atoi(sbegin.c_str());
 493                 }
 494         }
 495         else
 496         {
 497                 return atoi(x.c_str());
 498         }
 499 }