src/hashcomp.cpp

   1 /*       +------------------------------------+
   2  *       | Inspire Internet Relay Chat Daemon |
   3  *       +------------------------------------+
   4  *
   5  *  InspIRCd: (C) 2002-2007 InspIRCd Development Team
   6  * See: http://www.inspircd.org/wiki/index.php/Credits
   7  *
   8  * This program is free but copyrighted software; see
   9  *            the file COPYING for details.
  10  *
  11  * ---------------------------------------------------
  12  */
  13
  14 #include "inspircd.h"
  15 #include "hashcomp.h"
  16 #include <ext/hash_map>
  17 #define nspace __gnu_cxx
  18
  19 /******************************************************
  20  *
  21  * The hash functions of InspIRCd are the centrepoint
  22  * of the entire system. If these functions are
  23  * inefficient or wasteful, the whole program suffers
  24  * as a result. A lot of C programmers in the ircd
  25  * scene spend a lot of time debating (arguing) about
  26  * the best way to write hash functions to hash irc
  27  * nicknames, channels etc.
  28  * We are lucky as C++ developers as hash_map does
  29  * a lot of this for us. It does intellegent memory
  30  * requests, bucketing, search functions, insertion
  31  * and deletion etc. All we have to do is write some
  32  * overloaded comparison and hash value operators which
  33  * cause it to act in an irc-like way. The features we
  34  * add to the standard hash_map are:
  35  *
  36  * Case insensitivity: The hash_map will be case
  37  * insensitive.
  38  *
  39  * Scandanavian Comparisons: The characters [, ], \ will
  40  * be considered the lowercase of {, } and |.
  41  *
  42  ******************************************************/
  43
  44 using namespace irc::sockets;
  45
  46 /* convert a string to lowercase. Note following special circumstances
  47  * taken from RFC 1459. Many "official" server branches still hold to this
  48  * rule so i will too;
  49  *
  50  *  Because of IRC's scandanavian origin, the characters {}| are
  51  *  considered to be the lower case equivalents of the characters []\,
  52  *  respectively. This is a critical issue when determining the
  53  *  equivalence of two nicknames.
  54  */
  55 void nspace::strlower(char *n)
  56 {
  57         if (n)
  58         {
  59                 for (char* t = n; *t; t++)
  60                         *t = lowermap[(unsigned char)*t];
  61         }
  62 }
  63
  64 size_t nspace::hash<string>::operator()(const string &s) const
  65 {
  66         /* XXX: NO DATA COPIES! :)
  67          * The hash function here is practically
  68          * a copy of the one in STL's hash_fun.h,
  69          * only with *x replaced with lowermap[*x].
  70          * This avoids a copy to use hash<const char*>
  71          */
  72         register size_t t = 0;
  73         for (std::string::const_iterator x = s.begin(); x != s.end(); ++x) /* ++x not x++, as its faster */
  74                 t = 5 * t + lowermap[(unsigned char)*x];
  75         return t;
  76 }
  77
  78 size_t nspace::hash<irc::string>::operator()(const irc::string &s) const
  79 {
  80         register size_t t = 0;
  81         for (irc::string::const_iterator x = s.begin(); x != s.end(); ++x) /* ++x not x++, as its faster */
  82                 t = 5 * t + lowermap[(unsigned char)*x];
  83         return t;
  84 }
  85
  86 bool irc::StrHashComp::operator()(const std::string& s1, const std::string& s2) const
  87 {
  88         unsigned char* n1 = (unsigned char*)s1.c_str();
  89         unsigned char* n2 = (unsigned char*)s2.c_str();
  90         for (; *n1 && *n2; n1++, n2++)
  91                 if (lowermap[*n1] != lowermap[*n2])
  92                         return false;
  93         return (lowermap[*n1] == lowermap[*n2]);
  94 }
  95
  96 /******************************************************
  97  *
  98  * This is the implementation of our special irc::string
  99  * class which is a case-insensitive equivalent to
 100  * std::string which is not only case-insensitive but
 101  * can also do scandanavian comparisons, e.g. { = [, etc.
 102  *
 103  * This class depends on the const array 'lowermap'.
 104  *
 105  ******************************************************/
 106
 107 bool irc::irc_char_traits::eq(char c1st, char c2nd)
 108 {
 109         return lowermap[(unsigned char)c1st] == lowermap[(unsigned char)c2nd];
 110 }
 111
 112 bool irc::irc_char_traits::ne(char c1st, char c2nd)
 113 {
 114         return lowermap[(unsigned char)c1st] != lowermap[(unsigned char)c2nd];
 115 }
 116
 117 bool irc::irc_char_traits::lt(char c1st, char c2nd)
 118 {
 119         return lowermap[(unsigned char)c1st] < lowermap[(unsigned char)c2nd];
 120 }
 121
 122 int irc::irc_char_traits::compare(const char* str1, const char* str2, size_t n)
 123 {
 124         for(unsigned int i = 0; i < n; i++)
 125         {
 126                 if(lowermap[(unsigned char)*str1] > lowermap[(unsigned char)*str2])
 127                         return 1;
 128
 129                 if(lowermap[(unsigned char)*str1] < lowermap[(unsigned char)*str2])
 130                         return -1;
 131
 132                 if(*str1 == 0 || *str2 == 0)
 133                         return 0;
 134
 135                 str1++;
 136                 str2++;
 137         }
 138         return 0;
 139 }
 140
 141 std::string operator+ (std::string& leftval, irc::string& rightval)
 142 {
 143         return leftval + std::string(rightval.c_str());
 144 }
 145
 146 irc::string operator+ (irc::string& leftval, std::string& rightval)
 147 {
 148         return leftval + irc::string(rightval.c_str());
 149 }
 150
 151 bool operator== (std::string& leftval, irc::string& rightval)
 152 {
 153         return (leftval.c_str() == rightval);
 154 }
 155
 156 bool operator== (irc::string& leftval, std::string& rightval)
 157 {
 158         return (leftval == rightval.c_str());
 159 }
 160
 161 const char* irc::irc_char_traits::find(const char* s1, int  n, char c)
 162 {
 163         while(n-- > 0 && lowermap[(unsigned char)*s1] != lowermap[(unsigned char)c])
 164                 s1++;
 165         return s1;
 166 }
 167
 168 /* See hashcomp.h if you care about these... */
 169 std::ostream& operator<<(std::ostream &os, const irc::string &str)
 170 {
 171         return os << str.c_str();
 172 }
 173
 174 std::istream& operator>>(std::istream &is, irc::string &str)
 175 {
 176         std::string tmp;
 177         is >> tmp;
 178         str = tmp.c_str();
 179         return is;
 180 }
 181
 182 irc::tokenstream::tokenstream(const std::string &source) : tokens(source), last_pushed(false)
 183 {
 184         /* Record starting position and current position */
 185         last_starting_position = tokens.begin();
 186         n = tokens.begin();
 187 }
 188
 189 irc::tokenstream::~tokenstream()
 190 {
 191 }
 192
 193 const std::string irc::tokenstream::GetToken()
 194 {
 195         std::string::iterator lsp = last_starting_position;
 196
 197         while (n != tokens.end())
 198         {
 199                 /** Skip multi space, converting "  " into " "
 200                  */
 201                 while ((n+1 != tokens.end()) && (*n == ' ') && (*(n+1) == ' '))
 202                         n++;
 203
 204                 if ((last_pushed) && (*n == ':'))
 205                 {
 206                         /* If we find a token thats not the first and starts with :,
 207                          * this is the last token on the line
 208                          */
 209                         std::string::iterator curr = ++n;
 210                         n = tokens.end();
 211                         return std::string(curr, tokens.end());
 212                 }
 213
 214                 last_pushed = false;
 215
 216                 if ((*n == ' ') || (n+1 == tokens.end()))
 217                 {
 218                         /* If we find a space, or end of string, this is the end of a token.
 219                          */
 220                         last_starting_position = n+1;
 221                         last_pushed = true;
 222
 223                         std::string strip(lsp, n+1 == tokens.end() ? n+1  : n++);
 224                         while ((strip.length()) && (strip.find_last_of(' ') == strip.length() - 1))
 225                                 strip.erase(strip.end() - 1);
 226
 227                         return strip;
 228                 }
 229
 230                 n++;
 231         }
 232         return "";
 233 }
 234
 235 irc::sepstream::sepstream(const std::string &source, char seperator) : tokens(source), sep(seperator)
 236 {
 237         last_starting_position = tokens.begin();
 238         n = tokens.begin();
 239 }
 240
 241 const std::string irc::sepstream::GetToken()
 242 {
 243         std::string::iterator lsp = last_starting_position;
 244
 245         while (n != tokens.end())
 246         {
 247                 if ((*n == sep) || (n+1 == tokens.end()))
 248                 {
 249                         last_starting_position = n+1;
 250                         std::string strip = std::string(lsp, n+1 == tokens.end() ? n+1  : n++);
 251
 252                         while ((strip.length()) && (strip.find_last_of(sep) == strip.length() - 1))
 253                                 strip.erase(strip.end() - 1);
 254
 255                         return strip;
 256                 }
 257
 258                 n++;
 259         }
 260
 261         return "";
 262 }
 263
 264 bool irc::sepstream::StreamEnd()
 265 {
 266         return ((n + 1) == tokens.end());
 267 }
 268
 269 irc::sepstream::~sepstream()
 270 {
 271 }
 272
 273 std::string irc::hex(const unsigned char *raw, size_t rawsz)
 274 {
 275         if (!rawsz)
 276                 return "";
 277
 278         /* EWW! This used to be using sprintf, which is WAY inefficient. -Special */
 279
 280         const char *hex = "0123456789abcdef";
 281
 282         char buf[rawsz*2+1];
 283
 284         size_t i, j;
 285         for (i = 0, j = 0; j < rawsz; ++j)
 286         {
 287                 buf[i++] = hex[raw[j] / 16];
 288                 buf[i++] = hex[raw[j] % 16];
 289         }
 290         buf[i] = '\0';
 291
 292         return buf;
 293 }
 294
 295 const char* irc::Spacify(const char* n)
 296 {
 297         static char x[MAXBUF];
 298         strlcpy(x,n,MAXBUF);
 299         for (char* y = x; *y; y++)
 300                 if (*y == '_')
 301                         *y = ' ';
 302         return x;
 303 }
 304
 305
 306 irc::modestacker::modestacker(bool add) : adding(add)
 307 {
 308         sequence.clear();
 309         sequence.push_back("");
 310 }
 311
 312 void irc::modestacker::Push(char modeletter, const std::string &parameter)
 313 {
 314         *(sequence.begin()) += modeletter;
 315         sequence.push_back(parameter);
 316 }
 317
 318 void irc::modestacker::Push(char modeletter)
 319 {
 320         this->Push(modeletter,"");
 321 }
 322
 323 void irc::modestacker::PushPlus()
 324 {
 325         this->Push('+',"");
 326 }
 327
 328 void irc::modestacker::PushMinus()
 329 {
 330         this->Push('-',"");
 331 }
 332
 333 int irc::modestacker::GetStackedLine(std::deque<std::string> &result)
 334 {
 335         int n = 0;
 336         result.clear();
 337         result.push_back(adding ? "+" : "-");
 338
 339         while (!sequence[0].empty() && (sequence.size() > 1) && (result.size() < MAXMODES+1))
 340         {
 341                 result[0] += *(sequence[0].begin());
 342                 if (!sequence[1].empty())
 343                         result.push_back(sequence[1]);
 344                 sequence[0].erase(sequence[0].begin());
 345                 sequence.erase(sequence.begin() + 1);
 346                 n++;
 347         }
 348
 349         return n;
 350 }
 351
 352 irc::stringjoiner::stringjoiner(const std::string &seperator, const std::vector<std::string> &sequence, int begin, int end)
 353 {
 354         for (int v = begin; v < end; v++)
 355                 joined.append(sequence[v]).append(seperator);
 356         joined.append(sequence[end]);
 357 }
 358
 359 irc::stringjoiner::stringjoiner(const std::string &seperator, const std::deque<std::string> &sequence, int begin, int end)
 360 {
 361         for (int v = begin; v < end; v++)
 362                 joined.append(sequence[v]).append(seperator);
 363         joined.append(sequence[end]);
 364 }
 365
 366 irc::stringjoiner::stringjoiner(const std::string &seperator, const char** sequence, int begin, int end)
 367 {
 368         for (int v = begin; v < end; v++)
 369                 joined.append(sequence[v]).append(seperator);
 370         joined.append(sequence[end]);
 371 }
 372
 373 std::string& irc::stringjoiner::GetJoined()
 374 {
 375         return joined;
 376 }
 377
 378 irc::portparser::portparser(const std::string &source, bool allow_overlapped) : in_range(0), range_begin(0), range_end(0), overlapped(allow_overlapped)
 379 {
 380         sep = new irc::commasepstream(source);
 381         overlap_set.clear();
 382 }
 383
 384 irc::portparser::~portparser()
 385 {
 386         delete sep;
 387 }
 388
 389 bool irc::portparser::Overlaps(long val)
 390 {
 391         if (!overlapped)
 392                 return false;
 393
 394         if (overlap_set.find(val) == overlap_set.end())
 395         {
 396                 overlap_set[val] = true;
 397                 return false;
 398         }
 399         else
 400                 return true;
 401 }
 402
 403 long irc::portparser::GetToken()
 404 {
 405         if (in_range > 0)
 406         {
 407                 in_range++;
 408                 if (in_range <= range_end)
 409                 {
 410                         if (!Overlaps(in_range))
 411                         {
 412                                 return in_range;
 413                         }
 414                         else
 415                         {
 416                                 while (((Overlaps(in_range)) && (in_range <= range_end)))
 417                                         in_range++;
 418
 419                                 if (in_range <= range_end)
 420                                         return in_range;
 421                         }
 422                 }
 423                 else
 424                         in_range = 0;
 425         }
 426
 427         std::string x = sep->GetToken();
 428
 429         if (x == "")
 430                 return 0;
 431
 432         while (Overlaps(atoi(x.c_str())))
 433         {
 434                 x = sep->GetToken();
 435
 436                 if (x == "")
 437                         return 0;
 438         }
 439
 440         std::string::size_type dash = x.rfind('-');
 441         if (dash != std::string::npos)
 442         {
 443                 std::string sbegin = x.substr(0, dash);
 444                 std::string send = x.substr(dash+1, x.length());
 445                 range_begin = atoi(sbegin.c_str());
 446                 range_end = atoi(send.c_str());
 447
 448                 if ((range_begin > 0) && (range_end > 0) && (range_begin < 65536) && (range_end < 65536) && (range_begin < range_end))
 449                 {
 450                         in_range = range_begin;
 451                         return in_range;
 452                 }
 453                 else
 454                 {
 455                         /* Assume its just the one port */
 456                         return atoi(sbegin.c_str());
 457                 }
 458         }
 459         else
 460         {
 461                 return atoi(x.c_str());
 462         }
 463 }
 464
 465 irc::dynamicbitmask::dynamicbitmask() : bits_size(4)
 466 {
 467         /* We start with 4 bytes allocated which is room
 468          * for 4 items. Something makes me doubt its worth
 469          * allocating less than 4 bytes.
 470          */
 471         bits = new unsigned char[bits_size];
 472         memset(bits, 0, bits_size);
 473 }
 474
 475 irc::dynamicbitmask::~dynamicbitmask()
 476 {
 477         /* Tidy up the entire used memory on delete */
 478         delete[] bits;
 479 }
 480
 481 irc::bitfield irc::dynamicbitmask::Allocate()
 482 {
 483         /* Yeah, this isnt too efficient, however a module or the core
 484          * should only be allocating bitfields on load, the Toggle and
 485          * Get methods are O(1) as these are called much more often.
 486          */
 487         unsigned char* freebits = this->GetFreeBits();
 488         for (unsigned char i = 0; i < bits_size; i++)
 489         {
 490                 /* Yes, this is right. You'll notice we terminate the  loop when !current_pos,
 491                  * this is because we logic shift our bit off the end of unsigned char, and its
 492                  * lost, making the loop counter 0 when we're done.
 493                  */
 494                 for (unsigned char current_pos = 1; current_pos; current_pos = current_pos << 1)
 495                 {
 496                         if (!(freebits[i] & current_pos))
 497                         {
 498                                 freebits[i] |= current_pos;
 499                                 return std::make_pair(i, current_pos);
 500                         }
 501                 }
 502         }
 503         /* We dont have any free space left, increase by one */
 504
 505         if (bits_size == 255)
 506                 /* Oh dear, cant grow it any further */
 507                 throw std::bad_alloc();
 508
 509         unsigned char old_bits_size = bits_size;
 510         bits_size++;
 511         /* Allocate new bitfield space */
 512         unsigned char* temp_bits = new unsigned char[bits_size];
 513         unsigned char* temp_freebits = new unsigned char[bits_size];
 514         /* Copy the old data in */
 515         memcpy(temp_bits, bits, old_bits_size);
 516         memcpy(temp_freebits, freebits, old_bits_size);
 517         /* Delete the old data pointers */
 518         delete[] bits;
 519         delete[] freebits;
 520         /* Swap the pointers over so now the new
 521          * pointers point to our member values
 522          */
 523         bits = temp_bits;
 524         freebits = temp_freebits;
 525         this->SetFreeBits(freebits);
 526         /* Initialize the new byte on the end of
 527          * the bitfields, pre-allocate the one bit
 528          * for this allocation
 529          */
 530         bits[old_bits_size] = 0;
 531         freebits[old_bits_size] = 1;
 532         /* We already know where we just allocated
 533          * the bitfield, so no loop needed
 534          */
 535         return std::make_pair(old_bits_size, 1);
 536 }
 537
 538 bool irc::dynamicbitmask::Deallocate(irc::bitfield &pos)
 539 {
 540         /* We dont bother to shrink the bitfield
 541          * on deallocation, the most we could do
 542          * is save one byte (!) and this would cost
 543          * us a loop (ugly O(n) stuff) so we just
 544          * clear the bit and leave the memory
 545          * claimed -- nobody will care about one
 546          * byte.
 547          */
 548         if (pos.first < bits_size)
 549         {
 550                 this->GetFreeBits()[pos.first] &= ~pos.second;
 551                 return true;
 552         }
 553         /* They gave a bitfield outside of the
 554          * length of our array. BAD programmer.
 555          */
 556         return false;
 557 }
 558
 559 void irc::dynamicbitmask::Toggle(irc::bitfield &pos, bool state)
 560 {
 561         /* Range check the value */
 562         if (pos.first < bits_size)
 563         {
 564                 if (state)
 565                         /* Set state, OR the state in */
 566                         bits[pos.first] |= pos.second;
 567                 else
 568                         /* Clear state, AND the !state out */
 569                         bits[pos.first] &= ~pos.second;
 570         }
 571 }
 572
 573 bool irc::dynamicbitmask::Get(irc::bitfield &pos)
 574 {
 575         /* Range check the value */
 576         if (pos.first < bits_size)
 577                 return (bits[pos.first] & pos.second);
 578         else
 579                 /* We can't return false, otherwise we can't
 580                  * distinguish between failure and a cleared bit!
 581                  * Our only sensible choice is to throw (ew).
 582                  */
 583                 throw ModuleException("irc::dynamicbitmask::Get(): Invalid bitfield, out of range");
 584 }
 585
 586 unsigned char irc::dynamicbitmask::GetSize()
 587 {
 588         return bits_size;
 589 }
 590
 591 std::string assign(const irc::string &other)
 592 {
 593         return other.c_str();
 594 }
 595
 596 irc::string assign(const std::string &other)
 597 {
 598         return other.c_str();
 599 }
 600