src/stc/scintilla/src/PropSet.cxx

   1 // SciTE - Scintilla based Text Editor
   2 /** @file PropSet.cxx
   3  ** A Java style properties file module.
   4  **/
   5 // Copyright 1998-2003 by Neil Hodgson <neilh@scintilla.org>
   6 // The License.txt file describes the conditions under which this software may be distributed.
   7
   8 // Maintain a dictionary of properties
   9
  10 #include <stdlib.h>
  11 #include <string.h>
  12 #include <stdio.h>
  13
  14 #include "Platform.h"
  15
  16 #include "PropSet.h"
  17
  18 // The comparison and case changing functions here assume ASCII
  19 // or extended ASCII such as the normal Windows code page.
  20
  21 static inline char MakeUpperCase(char ch) {
  22         if (ch < 'a' || ch > 'z')
  23                 return ch;
  24         else
  25                 return static_cast<char>(ch - 'a' + 'A');
  26 }
  27
  28 static inline bool IsLetter(char ch) {
  29         return ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'));
  30 }
  31
  32 inline bool IsASpace(unsigned int ch) {
  33     return (ch == ' ') || ((ch >= 0x09) && (ch <= 0x0d));
  34 }
  35
  36 int CompareCaseInsensitive(const char *a, const char *b) {
  37         while (*a && *b) {
  38                 if (*a != *b) {
  39                         char upperA = MakeUpperCase(*a);
  40                         char upperB = MakeUpperCase(*b);
  41                         if (upperA != upperB)
  42                                 return upperA - upperB;
  43                 }
  44                 a++;
  45                 b++;
  46         }
  47         // Either *a or *b is nul
  48         return *a - *b;
  49 }
  50
  51 int CompareNCaseInsensitive(const char *a, const char *b, size_t len) {
  52         while (*a && *b && len) {
  53                 if (*a != *b) {
  54                         char upperA = MakeUpperCase(*a);
  55                         char upperB = MakeUpperCase(*b);
  56                         if (upperA != upperB)
  57                                 return upperA - upperB;
  58                 }
  59                 a++;
  60                 b++;
  61                 len--;
  62         }
  63         if (len == 0)
  64                 return 0;
  65         else
  66                 // Either *a or *b is nul
  67                 return *a - *b;
  68 }
  69
  70 bool EqualCaseInsensitive(const char *a, const char *b) {
  71         return 0 == CompareCaseInsensitive(a, b);
  72 }
  73
  74 // Since the CaseInsensitive functions declared in SString
  75 // are implemented here, I will for now put the non-inline
  76 // implementations of the SString members here as well, so
  77 // that I can quickly see what effect this has.
  78
  79 SString::SString(int i) : sizeGrowth(sizeGrowthDefault) {
  80         char number[32];
  81         sprintf(number, "%0d", i);
  82         s = StringAllocate(number);
  83         sSize = sLen = (s) ? strlen(s) : 0;
  84 }
  85
  86 SString::SString(double d, int precision) : sizeGrowth(sizeGrowthDefault) {
  87         char number[32];
  88         sprintf(number, "%.*f", precision, d);
  89         s = StringAllocate(number);
  90         sSize = sLen = (s) ? strlen(s) : 0;
  91 }
  92
  93 bool SString::grow(lenpos_t lenNew) {
  94         while (sizeGrowth * 6 < lenNew) {
  95                 sizeGrowth *= 2;
  96         }
  97         char *sNew = new char[lenNew + sizeGrowth + 1];
  98         if (sNew) {
  99                 if (s) {
 100                         memcpy(sNew, s, sLen);
 101                         delete []s;
 102                 }
 103                 s = sNew;
 104                 s[sLen] = '\0';
 105                 sSize = lenNew + sizeGrowth;
 106         }
 107         return sNew != 0;
 108 }
 109
 110 SString &SString::assign(const char *sOther, lenpos_t sSize_) {
 111         if (!sOther) {
 112                 sSize_ = 0;
 113         } else if (sSize_ == measure_length) {
 114                 sSize_ = strlen(sOther);
 115         }
 116         if (sSize > 0 && sSize_ <= sSize) {     // Does not allocate new buffer if the current is big enough
 117                 if (s && sSize_) {
 118                         memcpy(s, sOther, sSize_);
 119                 }
 120                 s[sSize_] = '\0';
 121                 sLen = sSize_;
 122         } else {
 123                 delete []s;
 124                 s = StringAllocate(sOther, sSize_);
 125                 if (s) {
 126                         sSize = sSize_; // Allow buffer bigger than real string, thus providing space to grow
 127                         sLen = strlen(s);
 128                 } else {
 129                         sSize = sLen = 0;
 130                 }
 131         }
 132         return *this;
 133 }
 134
 135 bool SString::operator==(const SString &sOther) const {
 136         if ((s == 0) && (sOther.s == 0))
 137                 return true;
 138         if ((s == 0) || (sOther.s == 0))
 139                 return false;
 140         return strcmp(s, sOther.s) == 0;
 141 }
 142
 143 bool SString::operator==(const char *sOther) const {
 144         if ((s == 0) && (sOther == 0))
 145                 return true;
 146         if ((s == 0) || (sOther == 0))
 147                 return false;
 148         return strcmp(s, sOther) == 0;
 149 }
 150
 151 SString SString::substr(lenpos_t subPos, lenpos_t subLen) const {
 152         if (subPos >= sLen) {
 153                 return SString();                                       // return a null string if start index is out of bounds
 154         }
 155         if ((subLen == measure_length) || (subPos + subLen > sLen)) {
 156                 subLen = sLen - subPos;         // can't substr past end of source string
 157         }
 158         return SString(s, subPos, subPos + subLen);
 159 }
 160
 161 SString &SString::lowercase(lenpos_t subPos, lenpos_t subLen) {
 162         if ((subLen == measure_length) || (subPos + subLen > sLen)) {
 163                 subLen = sLen - subPos;         // don't apply past end of string
 164         }
 165         for (lenpos_t i = subPos; i < subPos + subLen; i++) {
 166                 if (s[i] < 'A' || s[i] > 'Z')
 167                         continue;
 168                 else
 169                         s[i] = static_cast<char>(s[i] - 'A' + 'a');
 170         }
 171         return *this;
 172 }
 173
 174 SString &SString::uppercase(lenpos_t subPos, lenpos_t subLen) {
 175         if ((subLen == measure_length) || (subPos + subLen > sLen)) {
 176                 subLen = sLen - subPos;         // don't apply past end of string
 177         }
 178         for (lenpos_t i = subPos; i < subPos + subLen; i++) {
 179                 if (s[i] < 'a' || s[i] > 'z')
 180                         continue;
 181                 else
 182                         s[i] = static_cast<char>(s[i] - 'a' + 'A');
 183         }
 184         return *this;
 185 }
 186
 187 SString &SString::append(const char *sOther, lenpos_t sLenOther, char sep) {
 188         if (!sOther) {
 189                 return *this;
 190         }
 191         if (sLenOther == measure_length) {
 192                 sLenOther = strlen(sOther);
 193         }
 194         int lenSep = 0;
 195         if (sLen && sep) {      // Only add a separator if not empty
 196                 lenSep = 1;
 197         }
 198         lenpos_t lenNew = sLen + sLenOther + lenSep;
 199         // Conservative about growing the buffer: don't do it, unless really needed
 200         if ((lenNew < sSize) || (grow(lenNew))) {
 201                 if (lenSep) {
 202                         s[sLen] = sep;
 203                         sLen++;
 204                 }
 205                 memcpy(&s[sLen], sOther, sLenOther);
 206                 sLen += sLenOther;
 207                 s[sLen] = '\0';
 208         }
 209         return *this;
 210 }
 211
 212 SString &SString::insert(lenpos_t pos, const char *sOther, lenpos_t sLenOther) {
 213         if (!sOther || pos > sLen) {
 214                 return *this;
 215         }
 216         if (sLenOther == measure_length) {
 217                 sLenOther = strlen(sOther);
 218         }
 219         lenpos_t lenNew = sLen + sLenOther;
 220         // Conservative about growing the buffer: don't do it, unless really needed
 221         if ((lenNew < sSize) || grow(lenNew)) {
 222                 lenpos_t moveChars = sLen - pos + 1;
 223                 for (lenpos_t i = moveChars; i > 0; i--) {
 224                         s[pos + sLenOther + i - 1] = s[pos + i - 1];
 225                 }
 226                 memcpy(s + pos, sOther, sLenOther);
 227                 sLen = lenNew;
 228         }
 229         return *this;
 230 }
 231
 232 /**
 233  * Remove @a len characters from the @a pos position, included.
 234  * Characters at pos + len and beyond replace characters at pos.
 235  * If @a len is 0, or greater than the length of the string
 236  * starting at @a pos, the string is just truncated at @a pos.
 237  */
 238 void SString::remove(lenpos_t pos, lenpos_t len) {
 239         if (pos >= sLen) {
 240                 return;
 241         }
 242         if (len < 1 || pos + len >= sLen) {
 243                 s[pos] = '\0';
 244                 sLen = pos;
 245         } else {
 246                 for (lenpos_t i = pos; i < sLen - len + 1; i++) {
 247                         s[i] = s[i+len];
 248                 }
 249                 sLen -= len;
 250         }
 251 }
 252
 253 bool SString::startswith(const char *prefix) {
 254         lenpos_t lenPrefix = strlen(prefix);
 255         if (lenPrefix > sLen) {
 256                 return false;
 257         }
 258         return strncmp(s, prefix, lenPrefix) == 0;
 259 }
 260
 261 bool SString::endswith(const char *suffix) {
 262         lenpos_t lenSuffix = strlen(suffix);
 263         if (lenSuffix > sLen) {
 264                 return false;
 265         }
 266         return strncmp(s + sLen - lenSuffix, suffix, lenSuffix) == 0;
 267 }
 268
 269 int SString::search(const char *sFind, lenpos_t start) const {
 270         if (start < sLen) {
 271                 const char *sFound = strstr(s + start, sFind);
 272                 if (sFound) {
 273                         return sFound - s;
 274                 }
 275         }
 276         return -1;
 277 }
 278
 279 int SString::substitute(char chFind, char chReplace) {
 280         int c = 0;
 281         char *t = s;
 282         while (t) {
 283                 t = strchr(t, chFind);
 284                 if (t) {
 285                         *t = chReplace;
 286                         t++;
 287                         c++;
 288                 }
 289         }
 290         return c;
 291 }
 292
 293 int SString::substitute(const char *sFind, const char *sReplace) {
 294         int c = 0;
 295         lenpos_t lenFind = strlen(sFind);
 296         lenpos_t lenReplace = strlen(sReplace);
 297         int posFound = search(sFind);
 298         while (posFound >= 0) {
 299                 remove(posFound, lenFind);
 300                 insert(posFound, sReplace, lenReplace);
 301                 posFound = search(sFind, posFound + lenReplace);
 302                 c++;
 303         }
 304         return c;
 305 }
 306
 307 char *SContainer::StringAllocate(lenpos_t len) {
 308         if (len != measure_length) {
 309                 return new char[len + 1];
 310         } else {
 311                 return 0;
 312         }
 313 }
 314
 315 char *SContainer::StringAllocate(const char *s, lenpos_t len) {
 316         if (s == 0) {
 317                 return 0;
 318         }
 319         if (len == measure_length) {
 320                 len = strlen(s);
 321         }
 322         char *sNew = new char[len + 1];
 323         if (sNew) {
 324                 memcpy(sNew, s, len);
 325                 sNew[len] = '\0';
 326         }
 327         return sNew;
 328 }
 329
 330 // End SString functions
 331
 332 PropSet::PropSet() {
 333         superPS = 0;
 334         for (int root = 0; root < hashRoots; root++)
 335                 props[root] = 0;
 336 }
 337
 338 PropSet::~PropSet() {
 339         superPS = 0;
 340         Clear();
 341 }
 342
 343 void PropSet::Set(const char *key, const char *val, int lenKey, int lenVal) {
 344         if (!*key)      // Empty keys are not supported
 345                 return;
 346         if (lenKey == -1)
 347                 lenKey = static_cast<int>(strlen(key));
 348         if (lenVal == -1)
 349                 lenVal = static_cast<int>(strlen(val));
 350         unsigned int hash = HashString(key, lenKey);
 351         for (Property *p = props[hash % hashRoots]; p; p = p->next) {
 352                 if ((hash == p->hash) &&
 353                         ((strlen(p->key) == static_cast<unsigned int>(lenKey)) &&
 354                                 (0 == strncmp(p->key, key, lenKey)))) {
 355                         // Replace current value
 356                         delete [](p->val);
 357                         p->val = StringDup(val, lenVal);
 358                         return;
 359                 }
 360         }
 361         // Not found
 362         Property *pNew = new Property;
 363         if (pNew) {
 364                 pNew->hash = hash;
 365                 pNew->key = StringDup(key, lenKey);
 366                 pNew->val = StringDup(val, lenVal);
 367                 pNew->next = props[hash % hashRoots];
 368                 props[hash % hashRoots] = pNew;
 369         }
 370 }
 371
 372 void PropSet::Set(const char *keyVal) {
 373         while (IsASpace(*keyVal))
 374                 keyVal++;
 375         const char *endVal = keyVal;
 376         while (*endVal && (*endVal != '\n'))
 377                 endVal++;
 378         const char *eqAt = strchr(keyVal, '=');
 379         if (eqAt) {
 380                 Set(keyVal, eqAt + 1, eqAt-keyVal, endVal - eqAt - 1);
 381         } else if (*keyVal) {   // No '=' so assume '=1'
 382                 Set(keyVal, "1", endVal-keyVal, 1);
 383         }
 384 }
 385
 386 void PropSet::SetMultiple(const char *s) {
 387         const char *eol = strchr(s, '\n');
 388         while (eol) {
 389                 Set(s);
 390                 s = eol + 1;
 391                 eol = strchr(s, '\n');
 392         }
 393         Set(s);
 394 }
 395
 396 SString PropSet::Get(const char *key) {
 397         unsigned int hash = HashString(key, strlen(key));
 398         for (Property *p = props[hash % hashRoots]; p; p = p->next) {
 399                 if ((hash == p->hash) && (0 == strcmp(p->key, key))) {
 400                         return p->val;
 401                 }
 402         }
 403         if (superPS) {
 404                 // Failed here, so try in base property set
 405                 return superPS->Get(key);
 406         } else {
 407                 return "";
 408         }
 409 }
 410
 411 bool PropSet::IncludesVar(const char *value, const char *key) {
 412         const char *var = strstr(value, "$(");
 413         while (var) {
 414                 if (isprefix(var + 2, key) && (var[2 + strlen(key)] == ')')) {
 415                         // Found $(key) which would lead to an infinite loop so exit
 416                         return true;
 417                 }
 418                 var = strstr(var + 2, ")");
 419                 if (var)
 420                         var = strstr(var + 1, "$(");
 421         }
 422         return false;
 423 }
 424
 425 SString PropSet::GetExpanded(const char *key) {
 426         SString val = Get(key);
 427         if (IncludesVar(val.c_str(), key))
 428                 return val;
 429         return Expand(val.c_str());
 430 }
 431
 432 SString PropSet::Expand(const char *withVars, int maxExpands) {
 433         char *base = StringDup(withVars);
 434         char *cpvar = strstr(base, "$(");
 435         while (cpvar && (maxExpands > 0)) {
 436                 char *cpendvar = strchr(cpvar, ')');
 437                 if (!cpendvar)
 438                         break;
 439                 int lenvar = cpendvar - cpvar - 2;      // Subtract the $()
 440                 char *var = StringDup(cpvar + 2, lenvar);
 441                 SString val = Get(var);
 442                 if (IncludesVar(val.c_str(), var))
 443                         break;
 444                 size_t newlenbase = strlen(base) + val.length() - lenvar;
 445                 char *newbase = new char[newlenbase];
 446                 strncpy(newbase, base, cpvar - base);
 447                 strcpy(newbase + (cpvar - base), val.c_str());
 448                 strcpy(newbase + (cpvar - base) + val.length(), cpendvar + 1);
 449                 delete []var;
 450                 delete []base;
 451                 base = newbase;
 452                 cpvar = strstr(base, "$(");
 453                 maxExpands--;
 454         }
 455         SString sret = base;
 456         delete []base;
 457         return sret;
 458 }
 459
 460 int PropSet::GetInt(const char *key, int defaultValue) {
 461         SString val = GetExpanded(key);
 462         if (val.length())
 463                 return val.value();
 464         return defaultValue;
 465 }
 466
 467 bool isprefix(const char *target, const char *prefix) {
 468         while (*target && *prefix) {
 469                 if (*target != *prefix)
 470                         return false;
 471                 target++;
 472                 prefix++;
 473         }
 474         if (*prefix)
 475                 return false;
 476         else
 477                 return true;
 478 }
 479
 480 static bool IsSuffixCaseInsensitive(const char *target, const char *suffix) {
 481         size_t lentarget = strlen(target);
 482         size_t lensuffix = strlen(suffix);
 483         if (lensuffix > lentarget)
 484                 return false;
 485         for (int i = static_cast<int>(lensuffix) - 1; i >= 0; i--) {
 486                 if (MakeUpperCase(target[i + lentarget - lensuffix]) !=
 487                         MakeUpperCase(suffix[i]))
 488                         return false;
 489         }
 490         return true;
 491 }
 492
 493 SString PropSet::GetWild(const char *keybase, const char *filename) {
 494         for (int root = 0; root < hashRoots; root++) {
 495                 for (Property *p = props[root]; p; p = p->next) {
 496                         if (isprefix(p->key, keybase)) {
 497                                 char * orgkeyfile = p->key + strlen(keybase);
 498                                 char *keyfile = NULL;
 499
 500                                 if (strstr(orgkeyfile, "$(") == orgkeyfile) {
 501                                         char *cpendvar = strchr(orgkeyfile, ')');
 502                                         if (cpendvar) {
 503                                                 *cpendvar = '\0';
 504                                                 SString s = GetExpanded(orgkeyfile + 2);
 505                                                 *cpendvar = ')';
 506                                                 keyfile = StringDup(s.c_str());
 507                                         }
 508                                 }
 509                                 char *keyptr = keyfile;
 510
 511                                 if (keyfile == NULL)
 512                                         keyfile = orgkeyfile;
 513
 514                                 for (;;) {
 515                                         char *del = strchr(keyfile, ';');
 516                                         if (del == NULL)
 517                                                 del = keyfile + strlen(keyfile);
 518                                         char delchr = *del;
 519                                         *del = '\0';
 520                                         if (*keyfile == '*') {
 521                                                 if (IsSuffixCaseInsensitive(filename, keyfile + 1)) {
 522                                                         *del = delchr;
 523                                                         delete []keyptr;
 524                                                         return p->val;
 525                                                 }
 526                                         } else if (0 == strcmp(keyfile, filename)) {
 527                                                 *del = delchr;
 528                                                 delete []keyptr;
 529                                                 return p->val;
 530                                         }
 531                                         if (delchr == '\0')
 532                                                 break;
 533                                         *del = delchr;
 534                                         keyfile = del + 1;
 535                                 }
 536                                 delete []keyptr;
 537
 538                                 if (0 == strcmp(p->key, keybase)) {
 539                                         return p->val;
 540                                 }
 541                         }
 542                 }
 543         }
 544         if (superPS) {
 545                 // Failed here, so try in base property set
 546                 return superPS->GetWild(keybase, filename);
 547         } else {
 548                 return "";
 549         }
 550 }
 551
 552 // GetNewExpand does not use Expand as it has to use GetWild with the filename for each
 553 // variable reference found.
 554 SString PropSet::GetNewExpand(const char *keybase, const char *filename) {
 555         char *base = StringDup(GetWild(keybase, filename).c_str());
 556         char *cpvar = strstr(base, "$(");
 557         int maxExpands = 1000;  // Avoid infinite expansion of recursive definitions
 558         while (cpvar && (maxExpands > 0)) {
 559                 char *cpendvar = strchr(cpvar, ')');
 560                 if (cpendvar) {
 561                         int lenvar = cpendvar - cpvar - 2;      // Subtract the $()
 562                         char *var = StringDup(cpvar + 2, lenvar);
 563                         SString val = GetWild(var, filename);
 564                         size_t newlenbase = strlen(base) + val.length() - lenvar;
 565                         char *newbase = new char[newlenbase];
 566                         strncpy(newbase, base, cpvar - base);
 567                         strcpy(newbase + (cpvar - base), val.c_str());
 568                         strcpy(newbase + (cpvar - base) + val.length(), cpendvar + 1);
 569                         delete []var;
 570                         delete []base;
 571                         base = newbase;
 572                 }
 573                 cpvar = strstr(base, "$(");
 574                 maxExpands--;
 575         }
 576         SString sret = base;
 577         delete []base;
 578         return sret;
 579 }
 580
 581 void PropSet::Clear() {
 582         for (int root = 0; root < hashRoots; root++) {
 583                 Property *p = props[root];
 584                 while (p) {
 585                         Property *pNext = p->next;
 586                         p->hash = 0;
 587                         delete []p->key;
 588                         p->key = 0;
 589                         delete []p->val;
 590                         p->val = 0;
 591                         delete p;
 592                         p = pNext;
 593                 }
 594                 props[root] = 0;
 595         }
 596 }
 597
 598 char *PropSet::ToString() {
 599         size_t len=0;
 600         for (int r = 0; r < hashRoots; r++) {
 601                 for (Property *p = props[r]; p; p = p->next) {
 602                         len += strlen(p->key) + 1;
 603                         len += strlen(p->val) + 1;
 604                 }
 605         }
 606         if (len == 0)
 607                 len = 1;        // Return as empty string
 608         char *ret = new char [len];
 609         if (ret) {
 610                 char *w = ret;
 611                 for (int root = 0; root < hashRoots; root++) {
 612                         for (Property *p = props[root]; p; p = p->next) {
 613                                 strcpy(w, p->key);
 614                                 w += strlen(p->key);
 615                                 *w++ = '=';
 616                                 strcpy(w, p->val);
 617                                 w += strlen(p->val);
 618                                 *w++ = '\n';
 619                         }
 620                 }
 621                 ret[len-1] = '\0';
 622         }
 623         return ret;
 624 }
 625
 626 /**
 627  * Initiate enumeration.
 628  */
 629 bool PropSet::GetFirst(char **key, char **val) {
 630         for (int i = 0; i < hashRoots; i++) {
 631                 for (Property *p = props[i]; p; p = p->next) {
 632                         if (p) {
 633                                 *key = p->key;
 634                                 *val = p->val;
 635                                 enumnext = p->next; // GetNext will begin here ...
 636                                 enumhash = i;             // ... in this block
 637                                 return true;
 638                         }
 639                 }
 640         }
 641         return false;
 642 }
 643
 644 /**
 645  * Continue enumeration.
 646  */
 647 bool PropSet::GetNext(char ** key, char ** val) {
 648         bool firstloop = true;
 649
 650         // search begins where we left it : in enumhash block
 651         for (int i = enumhash; i < hashRoots; i++) {
 652                 if (!firstloop)
 653                         enumnext = props[i]; // Begin with first property in block
 654                 // else : begin where we left
 655                 firstloop = false;
 656
 657                 for (Property *p = enumnext; p; p = p->next) {
 658                         if (p) {
 659                                 *key = p->key;
 660                                 *val = p->val;
 661                                 enumnext = p->next; // for GetNext
 662                                 enumhash = i;
 663                                 return true;
 664                         }
 665                 }
 666         }
 667         return false;
 668 }
 669
 670 /**
 671  * Creates an array that points into each word in the string and puts \0 terminators
 672  * after each word.
 673  */
 674 static char **ArrayFromWordList(char *wordlist, int *len, bool onlyLineEnds = false) {
 675         int prev = '\n';
 676         int words = 0;
 677         // For rapid determination of whether a character is a separator, build
 678         // a look up table.
 679         bool wordSeparator[256];
 680         for (int i=0;i<256; i++) {
 681                 wordSeparator[i] = false;
 682         }
 683         wordSeparator['\r'] = true;
 684         wordSeparator['\n'] = true;
 685         if (!onlyLineEnds) {
 686                 wordSeparator[' '] = true;
 687                 wordSeparator['\t'] = true;
 688         }
 689         for (int j = 0; wordlist[j]; j++) {
 690                 int curr = static_cast<unsigned char>(wordlist[j]);
 691                 if (!wordSeparator[curr] && wordSeparator[prev])
 692                         words++;
 693                 prev = curr;
 694         }
 695         char **keywords = new char *[words + 1];
 696         if (keywords) {
 697                 words = 0;
 698                 prev = '\0';
 699                 size_t slen = strlen(wordlist);
 700                 for (size_t k = 0; k < slen; k++) {
 701                         if (!wordSeparator[static_cast<unsigned char>(wordlist[k])]) {
 702                                 if (!prev) {
 703                                         keywords[words] = &wordlist[k];
 704                                         words++;
 705                                 }
 706                         } else {
 707                                 wordlist[k] = '\0';
 708                         }
 709                         prev = wordlist[k];
 710                 }
 711                 keywords[words] = &wordlist[slen];
 712                 *len = words;
 713         } else {
 714                 *len = 0;
 715         }
 716         return keywords;
 717 }
 718
 719 void WordList::Clear() {
 720         if (words) {
 721                 delete []list;
 722                 delete []words;
 723                 delete []wordsNoCase;
 724         }
 725         words = 0;
 726         wordsNoCase = 0;
 727         list = 0;
 728         len = 0;
 729         sorted = false;
 730 }
 731
 732 void WordList::Set(const char *s) {
 733         list = StringDup(s);
 734         sorted = false;
 735         words = ArrayFromWordList(list, &len, onlyLineEnds);
 736         wordsNoCase = new char * [len + 1];
 737         memcpy(wordsNoCase, words, (len + 1) * sizeof (*words));
 738 }
 739
 740 char *WordList::Allocate(int size) {
 741         list = new char[size + 1];
 742         list[size] = '\0';
 743         return list;
 744 }
 745
 746 void WordList::SetFromAllocated() {
 747         sorted = false;
 748         words = ArrayFromWordList(list, &len, onlyLineEnds);
 749         wordsNoCase = new char * [len + 1];
 750         memcpy(wordsNoCase, words, (len + 1) * sizeof (*words));
 751 }
 752
 753 int cmpString(const void *a1, const void *a2) {
 754         // Can't work out the correct incantation to use modern casts here
 755         return strcmp(*(char**)(a1), *(char**)(a2));
 756 }
 757
 758 int cmpStringNoCase(const void *a1, const void *a2) {
 759         // Can't work out the correct incantation to use modern casts here
 760         return CompareCaseInsensitive(*(char**)(a1), *(char**)(a2));
 761 }
 762
 763 static void SortWordList(char **words, char **wordsNoCase, unsigned int len) {
 764         qsort(reinterpret_cast<void*>(words), len, sizeof(*words),
 765               cmpString);
 766         qsort(reinterpret_cast<void*>(wordsNoCase), len, sizeof(*wordsNoCase),
 767               cmpStringNoCase);
 768 }
 769
 770 bool WordList::InList(const char *s) {
 771         if (0 == words)
 772                 return false;
 773         if (!sorted) {
 774                 sorted = true;
 775                 SortWordList(words, wordsNoCase, len);
 776                 for (unsigned int k = 0; k < (sizeof(starts) / sizeof(starts[0])); k++)
 777                         starts[k] = -1;
 778                 for (int l = len - 1; l >= 0; l--) {
 779                         unsigned char indexChar = words[l][0];
 780                         starts[indexChar] = l;
 781                 }
 782         }
 783         unsigned char firstChar = s[0];
 784         int j = starts[firstChar];
 785         if (j >= 0) {
 786                 while (words[j][0] == firstChar) {
 787                         if (s[1] == words[j][1]) {
 788                                 const char *a = words[j] + 1;
 789                                 const char *b = s + 1;
 790                                 while (*a && *a == *b) {
 791                                         a++;
 792                                         b++;
 793                                 }
 794                                 if (!*a && !*b)
 795                                         return true;
 796                         }
 797                         j++;
 798                 }
 799         }
 800         j = starts['^'];
 801         if (j >= 0) {
 802                 while (words[j][0] == '^') {
 803                         const char *a = words[j] + 1;
 804                         const char *b = s;
 805                         while (*a && *a == *b) {
 806                                 a++;
 807                                 b++;
 808                         }
 809                         if (!*a)
 810                                 return true;
 811                         j++;
 812                 }
 813         }
 814         return false;
 815 }
 816
 817 /**
 818  * Returns an element (complete) of the wordlist array which has
 819  * the same beginning as the passed string.
 820  * The length of the word to compare is passed too.
 821  * Letter case can be ignored or preserved (default).
 822  */
 823 const char *WordList::GetNearestWord(const char *wordStart, int searchLen /*= -1*/, bool ignoreCase /*= false*/, SString wordCharacters /*='/0' */, int wordIndex /*= -1 */) {
 824         int start = 0; // lower bound of the api array block to search
 825         int end = len - 1; // upper bound of the api array block to search
 826         int pivot; // index of api array element just being compared
 827         int cond; // comparison result (in the sense of strcmp() result)
 828         const char *word; // api array element just being compared
 829
 830         if (0 == words)
 831                 return NULL;
 832         if (!sorted) {
 833                 sorted = true;
 834                 SortWordList(words, wordsNoCase, len);
 835         }
 836         if (ignoreCase) {
 837                 while (start <= end) { // binary searching loop
 838                         pivot = (start + end) >> 1;
 839                         word = wordsNoCase[pivot];
 840                         cond = CompareNCaseInsensitive(wordStart, word, searchLen);
 841                         if (!cond && (!wordCharacters.contains(word[searchLen]))) {
 842                                 // Found a word in a binary fashion. Now checks if a specific index was requested
 843                                 if (wordIndex < 0)
 844                                         return word; // result must not be freed with free()
 845
 846                                 // Finds first word in a series of equal words
 847                                 int first = pivot;
 848                                 end = pivot - 1;
 849                                 while (start <= end) {
 850                                         pivot = (start + end) >> 1;
 851                                         word = wordsNoCase[pivot];
 852                                         cond = CompareNCaseInsensitive(wordStart, word, searchLen);
 853                                         if (!cond && (!wordCharacters.contains(word[searchLen]))) {
 854                                                 // Found another word
 855                                                 first = pivot;
 856                                                 end = pivot - 1;
 857                                         }
 858                                         else if (cond > 0)
 859                                                 start = pivot + 1;
 860                                         else if (cond <= 0)
 861                                                 break;
 862                                 }
 863
 864                                 // Gets the word at the requested index
 865                                 word = wordsNoCase[first + wordIndex];
 866                                 return word;
 867                         }
 868                         else if (cond > 0)
 869                                 start = pivot + 1;
 870                         else if (cond <= 0)
 871                                 end = pivot - 1;
 872                 }
 873         } else { // preserve the letter case
 874                 while (start <= end) { // binary searching loop
 875                         pivot = (start + end) >> 1;
 876                         word = words[pivot];
 877                         cond = strncmp(wordStart, word, searchLen);
 878                         if (!cond && (!wordCharacters.contains(word[searchLen]))) {
 879                                 // Found a word in a binary fashion. Now checks if a specific index was requested
 880                                 if (wordIndex < 0)
 881                                         return word; // result must not be freed with free()
 882
 883                                 // Finds first word in a series of equal words
 884                                 int first = pivot;
 885                                 end = pivot - 1;
 886                                 while (start <= end) {
 887                                         pivot = (start + end) >> 1;
 888                                         word = words[pivot];
 889                                         cond = strncmp(wordStart, word, searchLen);
 890                                         if (!cond && (!wordCharacters.contains(word[searchLen]))) {
 891                                                 // Found another word
 892                                                 first = pivot;
 893                                                 end = pivot - 1;
 894                                         }
 895                                         else if (cond > 0)
 896                                                 start = pivot + 1;
 897                                         else if (cond <= 0)
 898                                                 break;
 899                                 }
 900
 901                                 // Gets the word at the requested index
 902                                 word = words[first + wordIndex];
 903                                 return word;
 904                         }
 905                         else if (cond > 0)
 906                                 start = pivot + 1;
 907                         else if (cond <= 0)
 908                                 end = pivot - 1;
 909                 }
 910         }
 911         return NULL;
 912 }
 913
 914 /**
 915  * Find the length of a 'word' which is actually an identifier in a string
 916  * which looks like "identifier(..." or "identifier:" or "identifier" and where
 917  * there may be extra spaces after the identifier that should not be
 918  * counted in the length.
 919  */
 920 static unsigned int LengthWord(const char *word, char otherSeparator) {
 921         // Find a '(', or ':'. If that fails go to the end of the string.
 922         const char *endWord = strchr(word, '(');
 923         if (!endWord)
 924                 endWord = strchr(word, ':');
 925         if (!endWord && otherSeparator)
 926                 endWord = strchr(word, otherSeparator);
 927         if (!endWord)
 928                 endWord = word + strlen(word);
 929         // Last case always succeeds so endWord != 0
 930
 931         // Drop any space characters.
 932         if (endWord > word) {
 933                 endWord--;      // Back from the '(', ':', or '\0'
 934                 // Move backwards over any spaces
 935                 while ((endWord > word) && (IsASpace(*endWord))) {
 936                         endWord--;
 937                 }
 938         }
 939         return endWord - word;
 940 }
 941
 942 /**
 943  * Returns elements (first words of them) of the wordlist array which have
 944  * the same beginning as the passed string.
 945  * The length of the word to compare is passed too.
 946  * Letter case can be ignored or preserved (default).
 947  * If there are more words meeting the condition they are returned all of
 948  * them in the ascending order separated with spaces.
 949  *
 950  * NOTE: returned buffer has to be freed with delete[].
 951  */
 952 char *WordList::GetNearestWords(
 953     const char *wordStart,
 954     int searchLen /*= -1*/,
 955     bool ignoreCase /*= false*/,
 956     char otherSeparator /*= '\0'*/,
 957     bool exactLen /*=false*/) {
 958         unsigned int wordlen; // length of the word part (before the '(' brace) of the api array element
 959         SString wordsNear;
 960         wordsNear.setsizegrowth(1000);
 961         int start = 0; // lower bound of the api array block to search
 962         int end = len - 1; // upper bound of the api array block to search
 963         int pivot; // index of api array element just being compared
 964         int cond; // comparison result (in the sense of strcmp() result)
 965
 966         if (0 == words)
 967                 return NULL;
 968         if (!sorted) {
 969                 sorted = true;
 970                 SortWordList(words, wordsNoCase, len);
 971         }
 972         if (ignoreCase) {
 973                 while (start <= end) { // Binary searching loop
 974                         pivot = (start + end) / 2;
 975                         cond = CompareNCaseInsensitive(wordStart, wordsNoCase[pivot], searchLen);
 976                         if (!cond) {
 977                                 // Find first match
 978                                 while ((pivot > start) &&
 979                                         (0 == CompareNCaseInsensitive(wordStart,
 980                                                 wordsNoCase[pivot-1], searchLen))) {
 981                                         --pivot;
 982                                 }
 983                                 // Grab each match
 984                                 while ((pivot <= end) &&
 985                                         (0 == CompareNCaseInsensitive(wordStart,
 986                                                 wordsNoCase[pivot], searchLen))) {
 987                                         wordlen = LengthWord(wordsNoCase[pivot], otherSeparator) + 1;
 988                                         if (exactLen && wordlen != LengthWord(wordStart, otherSeparator) + 1)
 989                                                 break;
 990                                         wordsNear.append(wordsNoCase[pivot], wordlen, ' ');
 991                                         ++pivot;
 992                                 }
 993                                 return wordsNear.detach();
 994                         } else if (cond < 0) {
 995                                 end = pivot - 1;
 996                         } else if (cond > 0) {
 997                                 start = pivot + 1;
 998                         }
 999                 }
1000         } else {        // Preserve the letter case
1001                 while (start <= end) { // Binary searching loop
1002                         pivot = (start + end) / 2;
1003                         cond = strncmp(wordStart, words[pivot], searchLen);
1004                         if (!cond) {
1005                                 // Find first match
1006                                 while ((pivot > start) &&
1007                                         (0 == strncmp(wordStart,
1008                                                 words[pivot-1], searchLen))) {
1009                                         --pivot;
1010                                 }
1011                                 // Grab each match
1012                                 while ((pivot <= end) &&
1013                                         (0 == strncmp(wordStart,
1014                                                 words[pivot], searchLen))) {
1015                                         wordlen = LengthWord(words[pivot], otherSeparator) + 1;
1016                                         if (exactLen && wordlen != LengthWord(wordStart, otherSeparator) + 1)
1017                                                 break;
1018                                         wordsNear.append(words[pivot], wordlen, ' ');
1019                                         ++pivot;
1020                                 }
1021                                 return wordsNear.detach();
1022                         } else if (cond < 0) {
1023                                 end = pivot - 1;
1024                         } else if (cond > 0) {
1025                                 start = pivot + 1;
1026                         }
1027                 }
1028         }
1029         return NULL;
1030 }