2 * InspIRCd -- Internet Relay Chat Daemon
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>
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.
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
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/>.
29 /******************************************************
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:
46 * Case insensitivity: The hash_map will be case
49 * Scandanavian Comparisons: The characters [, ], \ will
50 * be considered the lowercase of {, } and |.
52 ******************************************************/
54 /** A mapping of uppercase to lowercase, including scandinavian
55 * 'oddities' as specified by RFC1459, e.g. { -> [, and | -> \
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 */
73 /** Case insensitive map, ASCII rules.
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 */
93 /** Case sensitive map.
94 * Can technically also be used for ASCII case sensitive comparisons, as [ != {, etc.
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
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;
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.
121 void nspace::strlower(char *n)
125 for (char* t = n; *t; t++)
126 *t = national_case_insensitive_map[(unsigned char)*t];
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
133 #ifdef HASHMAP_DEPRECATED
134 size_t CoreExport nspace::insensitive::operator()(const std::string &s) const
136 size_t nspace::hash<std::string>::operator()(const std::string &s) const
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*>
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];
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
156 size_t CoreExport irc::hash::operator()(const irc::string &s) const
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];
165 bool irc::StrHashComp::operator()(const std::string& s1, const std::string& s2) const
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])
172 return (national_case_insensitive_map[*n1] == national_case_insensitive_map[*n2]);
175 /******************************************************
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.
182 * This class depends on the const array 'national_case_insensitive_map'.
184 ******************************************************/
186 bool irc::irc_char_traits::eq(char c1st, char c2nd)
188 return national_case_insensitive_map[(unsigned char)c1st] == national_case_insensitive_map[(unsigned char)c2nd];
191 bool irc::irc_char_traits::ne(char c1st, char c2nd)
193 return national_case_insensitive_map[(unsigned char)c1st] != national_case_insensitive_map[(unsigned char)c2nd];
196 bool irc::irc_char_traits::lt(char c1st, char c2nd)
198 return national_case_insensitive_map[(unsigned char)c1st] < national_case_insensitive_map[(unsigned char)c2nd];
201 int irc::irc_char_traits::compare(const char* str1, const char* str2, size_t n)
203 for(unsigned int i = 0; i < n; i++)
205 if(national_case_insensitive_map[(unsigned char)*str1] > national_case_insensitive_map[(unsigned char)*str2])
208 if(national_case_insensitive_map[(unsigned char)*str1] < national_case_insensitive_map[(unsigned char)*str2])
211 if(*str1 == 0 || *str2 == 0)
220 const char* irc::irc_char_traits::find(const char* s1, int n, char c)
222 while(n-- > 0 && national_case_insensitive_map[(unsigned char)*s1] != national_case_insensitive_map[(unsigned char)c])
224 return (n >= 0) ? s1 : NULL;
227 irc::tokenstream::tokenstream(const std::string &source) : tokens(source), last_pushed(false)
229 /* Record starting position and current position */
230 last_starting_position = tokens.begin();
234 irc::tokenstream::~tokenstream()
238 bool irc::tokenstream::GetToken(std::string &token)
240 std::string::iterator lsp = last_starting_position;
242 while (n != tokens.end())
244 /** Skip multi space, converting " " into " "
246 while ((n+1 != tokens.end()) && (*n == ' ') && (*(n+1) == ' '))
249 if ((last_pushed) && (*n == ':'))
251 /* If we find a token thats not the first and starts with :,
252 * this is the last token on the line
254 std::string::iterator curr = ++n;
256 token = std::string(curr, tokens.end());
262 if ((*n == ' ') || (n+1 == tokens.end()))
264 /* If we find a space, or end of string, this is the end of a token.
266 last_starting_position = n+1;
267 last_pushed = *n == ' ';
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);
274 return !token.empty();
283 bool irc::tokenstream::GetToken(irc::string &token)
285 std::string stdstring;
286 bool returnval = GetToken(stdstring);
287 token = assign(stdstring);
291 bool irc::tokenstream::GetToken(int &token)
294 bool returnval = GetToken(tok);
295 token = ConvToInt(tok);
299 bool irc::tokenstream::GetToken(long &token)
302 bool returnval = GetToken(tok);
303 token = ConvToInt(tok);
307 irc::sepstream::sepstream(const std::string &source, char seperator) : tokens(source), sep(seperator)
309 last_starting_position = tokens.begin();
313 bool irc::sepstream::GetToken(std::string &token)
315 std::string::iterator lsp = last_starting_position;
317 while (n != tokens.end())
319 if ((*n == sep) || (n+1 == tokens.end()))
321 last_starting_position = n+1;
322 token = std::string(lsp, n+1 == tokens.end() ? n+1 : n++);
324 while ((token.length()) && (token.find_last_of(sep) == token.length() - 1))
325 token.erase(token.end() - 1);
330 return n == tokens.end() ? false : true;
340 const std::string irc::sepstream::GetRemaining()
342 return std::string(n, tokens.end());
345 bool irc::sepstream::StreamEnd()
347 return ((n + 1) == tokens.end());
350 irc::sepstream::~sepstream()
354 std::string irc::hex(const unsigned char *raw, size_t rawsz)
359 /* EWW! This used to be using sprintf, which is WAY inefficient. -Special */
361 const char *hex = "0123456789abcdef";
362 static char hexbuf[MAXBUF];
365 for (i = 0, j = 0; j < rawsz; ++j)
367 hexbuf[i++] = hex[raw[j] / 16];
368 hexbuf[i++] = hex[raw[j] % 16];
375 CoreExport const char* irc::Spacify(const char* n)
377 static char x[MAXBUF];
379 for (char* y = x; *y; y++)
386 irc::modestacker::modestacker(bool add) : adding(add)
389 sequence.push_back("");
392 void irc::modestacker::Push(char modeletter, const std::string ¶meter)
394 *(sequence.begin()) += modeletter;
395 sequence.push_back(parameter);
398 void irc::modestacker::Push(char modeletter)
400 this->Push(modeletter,"");
403 void irc::modestacker::PushPlus()
408 void irc::modestacker::PushMinus()
413 int irc::modestacker::GetStackedLine(std::vector<std::string> &result, int max_line_size)
415 if (sequence.empty())
421 int size = 1; /* Account for initial +/- char */
423 int start = result.size();
424 std::string modeline = adding ? "+" : "-";
425 result.push_back(modeline);
427 if (sequence.size() > 1)
428 nextsize = sequence[1].length() + 2;
430 while (!sequence[0].empty() && (sequence.size() > 1) && (n < ServerInstance->Config->Limits.MaxModes) && ((size + nextsize) < max_line_size))
432 modeline += *(sequence[0].begin());
433 if (!sequence[1].empty())
435 result.push_back(sequence[1]);
436 size += nextsize; /* Account for mode character and whitespace */
438 sequence[0].erase(sequence[0].begin());
439 sequence.erase(sequence.begin() + 1);
441 if (sequence.size() > 1)
442 nextsize = sequence[1].length() + 2;
446 result[start] = modeline;
451 irc::stringjoiner::stringjoiner(const std::string &seperator, const std::vector<std::string> &sequence, int begin, int end)
454 throw "stringjoiner logic error, this causes problems.";
456 for (int v = begin; v < end; v++)
457 joined.append(sequence[v]).append(seperator);
458 joined.append(sequence[end]);
461 irc::stringjoiner::stringjoiner(const std::string &seperator, const std::deque<std::string> &sequence, int begin, int end)
464 throw "stringjoiner logic error, this causes problems.";
466 for (int v = begin; v < end; v++)
467 joined.append(sequence[v]).append(seperator);
468 joined.append(sequence[end]);
471 irc::stringjoiner::stringjoiner(const std::string &seperator, const char* const* sequence, int begin, int end)
474 throw "stringjoiner logic error, this causes problems.";
476 for (int v = begin; v < end; v++)
477 joined.append(sequence[v]).append(seperator);
478 joined.append(sequence[end]);
481 std::string& irc::stringjoiner::GetJoined()
486 irc::portparser::portparser(const std::string &source, bool allow_overlapped) : in_range(0), range_begin(0), range_end(0), overlapped(allow_overlapped)
488 sep = new irc::commasepstream(source);
492 irc::portparser::~portparser()
497 bool irc::portparser::Overlaps(long val)
502 if (overlap_set.find(val) == overlap_set.end())
504 overlap_set[val] = true;
511 long irc::portparser::GetToken()
516 if (in_range <= range_end)
518 if (!Overlaps(in_range))
524 while (((Overlaps(in_range)) && (in_range <= range_end)))
527 if (in_range <= range_end)
541 while (Overlaps(atoi(x.c_str())))
543 if (!sep->GetToken(x))
547 std::string::size_type dash = x.rfind('-');
548 if (dash != std::string::npos)
550 std::string sbegin = x.substr(0, dash);
551 std::string send = x.substr(dash+1, x.length());
552 range_begin = atoi(sbegin.c_str());
553 range_end = atoi(send.c_str());
555 if ((range_begin > 0) && (range_end > 0) && (range_begin < 65536) && (range_end < 65536) && (range_begin < range_end))
557 in_range = range_begin;
562 /* Assume its just the one port */
563 return atoi(sbegin.c_str());
568 return atoi(x.c_str());
572 /*const std::basic_string& SearchAndReplace(std::string& text, const std::string& pattern, const std::string& replace)
574 std::string replacement;
575 if ((!pattern.empty()) && (!text.empty()))
577 for (std::string::size_type n = 0; n != text.length(); ++n)
579 if (text.length() >= pattern.length() && text.substr(n, pattern.length()) == pattern)
581 replacement.append(replace);
582 n = n + pattern.length() - 1;
586 replacement += text[n];