scintilla/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 = sSize_;
 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::Unset(const char *key, int lenKey) {
 387         if (!*key)      // Empty keys are not supported
 388                 return;
 389         if (lenKey == -1)
 390                 lenKey = static_cast<int>(strlen(key));
 391         unsigned int hash = HashString(key, lenKey);
 392         Property *pPrev = NULL;
 393         for (Property *p = props[hash % hashRoots]; p; p = p->next) {
 394                 if ((hash == p->hash) &&
 395                         ((strlen(p->key) == static_cast<unsigned int>(lenKey)) &&
 396                                 (0 == strncmp(p->key, key, lenKey)))) {
 397                         if (pPrev)
 398                                 pPrev->next = p->next;
 399                         else
 400                                 props[hash % hashRoots] = p->next;
 401                         if (p == enumnext)
 402                                 enumnext = p->next; // Not that anyone should mix enum and Set / Unset.
 403                         delete [](p->key);
 404                         delete [](p->val);
 405                         delete p;
 406                         return;
 407                 } else {
 408                         pPrev = p;
 409                 }
 410         }
 411 }
 412
 413 void PropSet::SetMultiple(const char *s) {
 414         const char *eol = strchr(s, '\n');
 415         while (eol) {
 416                 Set(s);
 417                 s = eol + 1;
 418                 eol = strchr(s, '\n');
 419         }
 420         Set(s);
 421 }
 422
 423 SString PropSet::Get(const char *key) {
 424         unsigned int hash = HashString(key, strlen(key));
 425         for (Property *p = props[hash % hashRoots]; p; p = p->next) {
 426                 if ((hash == p->hash) && (0 == strcmp(p->key, key))) {
 427                         return p->val;
 428                 }
 429         }
 430         if (superPS) {
 431                 // Failed here, so try in base property set
 432                 return superPS->Get(key);
 433         } else {
 434                 return "";
 435         }
 436 }
 437
 438 bool PropSet::IncludesVar(const char *value, const char *key) {
 439         const char *var = strstr(value, "$(");
 440         while (var) {
 441                 if (isprefix(var + 2, key) && (var[2 + strlen(key)] == ')')) {
 442                         // Found $(key) which would lead to an infinite loop so exit
 443                         return true;
 444                 }
 445                 var = strstr(var + 2, ")");
 446                 if (var)
 447                         var = strstr(var + 1, "$(");
 448         }
 449         return false;
 450 }
 451
 452
 453 // There is some inconsistency between GetExpanded("foo") and Expand("$(foo)").
 454 // A solution is to keep a stack of variables that have been expanded, so that
 455 // recursive expansions can be skipped.  For now I'll just use the C++ stack
 456 // for that, through a recursive function and a simple chain of pointers.
 457
 458 struct VarChain {
 459         VarChain(const char*var_=NULL, const VarChain *link_=NULL): var(var_), link(link_) {}
 460
 461         bool contains(const char *testVar) const {
 462                 return (var && (0 == strcmp(var, testVar)))
 463                         || (link && link->contains(testVar));
 464         }
 465
 466         const char *var;
 467         const VarChain *link;
 468 };
 469
 470 static int ExpandAllInPlace(PropSet &props, SString &withVars, int maxExpands, const VarChain &blankVars = VarChain()) {
 471         int varStart = withVars.search("$(");
 472         while ((varStart >= 0) && (maxExpands > 0)) {
 473                 int varEnd = withVars.search(")", varStart+2);
 474                 if (varEnd < 0) {
 475                         break;
 476                 }
 477
 478                 // For consistency, when we see '$(ab$(cde))', expand the inner variable first,
 479                 // regardless whether there is actually a degenerate variable named 'ab$(cde'.
 480                 int innerVarStart = withVars.search("$(", varStart+2);
 481                 while ((innerVarStart > varStart) && (innerVarStart < varEnd)) {
 482                         varStart = innerVarStart;
 483                         innerVarStart = withVars.search("$(", varStart+2);
 484                 }
 485
 486                 SString var(withVars.c_str(), varStart + 2, varEnd);
 487                 SString val = props.Get(var.c_str());
 488
 489                 if (blankVars.contains(var.c_str())) {
 490                         val.clear(); // treat blankVar as an empty string (e.g. to block self-reference)
 491                 }
 492
 493                 if (--maxExpands >= 0) {
 494                         maxExpands = ExpandAllInPlace(props, val, maxExpands, VarChain(var.c_str(), &blankVars));
 495                 }
 496
 497                 withVars.remove(varStart, varEnd-varStart+1);
 498                 withVars.insert(varStart, val.c_str(), val.length());
 499
 500                 varStart = withVars.search("$(");
 501         }
 502
 503         return maxExpands;
 504 }
 505
 506
 507 SString PropSet::GetExpanded(const char *key) {
 508         SString val = Get(key);
 509         ExpandAllInPlace(*this, val, 100, VarChain(key));
 510         return val;
 511 }
 512
 513 SString PropSet::Expand(const char *withVars, int maxExpands) {
 514         SString val = withVars;
 515         ExpandAllInPlace(*this, val, maxExpands);
 516         return val;
 517 }
 518
 519 int PropSet::GetInt(const char *key, int defaultValue) {
 520         SString val = GetExpanded(key);
 521         if (val.length())
 522                 return val.value();
 523         return defaultValue;
 524 }
 525
 526 bool isprefix(const char *target, const char *prefix) {
 527         while (*target && *prefix) {
 528                 if (*target != *prefix)
 529                         return false;
 530                 target++;
 531                 prefix++;
 532         }
 533         if (*prefix)
 534                 return false;
 535         else
 536                 return true;
 537 }
 538
 539 static bool IsSuffixCaseInsensitive(const char *target, const char *suffix) {
 540         size_t lentarget = strlen(target);
 541         size_t lensuffix = strlen(suffix);
 542         if (lensuffix > lentarget)
 543                 return false;
 544         for (int i = static_cast<int>(lensuffix) - 1; i >= 0; i--) {
 545                 if (MakeUpperCase(target[i + lentarget - lensuffix]) !=
 546                         MakeUpperCase(suffix[i]))
 547                         return false;
 548         }
 549         return true;
 550 }
 551
 552 SString PropSet::GetWild(const char *keybase, const char *filename) {
 553         for (int root = 0; root < hashRoots; root++) {
 554                 for (Property *p = props[root]; p; p = p->next) {
 555                         if (isprefix(p->key, keybase)) {
 556                                 char * orgkeyfile = p->key + strlen(keybase);
 557                                 char *keyfile = NULL;
 558
 559                                 if (strstr(orgkeyfile, "$(") == orgkeyfile) {
 560                                         char *cpendvar = strchr(orgkeyfile, ')');
 561                                         if (cpendvar) {
 562                                                 *cpendvar = '\0';
 563                                                 SString s = GetExpanded(orgkeyfile + 2);
 564                                                 *cpendvar = ')';
 565                                                 keyfile = StringDup(s.c_str());
 566                                         }
 567                                 }
 568                                 char *keyptr = keyfile;
 569
 570                                 if (keyfile == NULL)
 571                                         keyfile = orgkeyfile;
 572
 573                                 for (;;) {
 574                                         char *del = strchr(keyfile, ';');
 575                                         if (del == NULL)
 576                                                 del = keyfile + strlen(keyfile);
 577                                         char delchr = *del;
 578                                         *del = '\0';
 579                                         if (*keyfile == '*') {
 580                                                 if (IsSuffixCaseInsensitive(filename, keyfile + 1)) {
 581                                                         *del = delchr;
 582                                                         delete []keyptr;
 583                                                         return p->val;
 584                                                 }
 585                                         } else if (0 == strcmp(keyfile, filename)) {
 586                                                 *del = delchr;
 587                                                 delete []keyptr;
 588                                                 return p->val;
 589                                         }
 590                                         if (delchr == '\0')
 591                                                 break;
 592                                         *del = delchr;
 593                                         keyfile = del + 1;
 594                                 }
 595                                 delete []keyptr;
 596
 597                                 if (0 == strcmp(p->key, keybase)) {
 598                                         return p->val;
 599                                 }
 600                         }
 601                 }
 602         }
 603         if (superPS) {
 604                 // Failed here, so try in base property set
 605                 return superPS->GetWild(keybase, filename);
 606         } else {
 607                 return "";
 608         }
 609 }
 610
 611
 612
 613 // GetNewExpand does not use Expand as it has to use GetWild with the filename for each
 614 // variable reference found.
 615 SString PropSet::GetNewExpand(const char *keybase, const char *filename) {
 616         char *base = StringDup(GetWild(keybase, filename).c_str());
 617         char *cpvar = strstr(base, "$(");
 618         int maxExpands = 1000;  // Avoid infinite expansion of recursive definitions
 619         while (cpvar && (maxExpands > 0)) {
 620                 char *cpendvar = strchr(cpvar, ')');
 621                 if (cpendvar) {
 622                         int lenvar = cpendvar - cpvar - 2;      // Subtract the $()
 623                         char *var = StringDup(cpvar + 2, lenvar);
 624                         SString val = GetWild(var, filename);
 625                         if (0 == strcmp(var, keybase))
 626                                 val.clear(); // Self-references evaluate to empty string
 627                         size_t newlenbase = strlen(base) + val.length() - lenvar;
 628                         char *newbase = new char[newlenbase];
 629                         strncpy(newbase, base, cpvar - base);
 630                         strcpy(newbase + (cpvar - base), val.c_str());
 631                         strcpy(newbase + (cpvar - base) + val.length(), cpendvar + 1);
 632                         delete []var;
 633                         delete []base;
 634                         base = newbase;
 635                 }
 636                 cpvar = strstr(base, "$(");
 637                 maxExpands--;
 638         }
 639         SString sret = base;
 640         delete []base;
 641         return sret;
 642 }
 643
 644 void PropSet::Clear() {
 645         for (int root = 0; root < hashRoots; root++) {
 646                 Property *p = props[root];
 647                 while (p) {
 648                         Property *pNext = p->next;
 649                         p->hash = 0;
 650                         delete []p->key;
 651                         p->key = 0;
 652                         delete []p->val;
 653                         p->val = 0;
 654                         delete p;
 655                         p = pNext;
 656                 }
 657                 props[root] = 0;
 658         }
 659 }
 660
 661 char *PropSet::ToString() {
 662         size_t len=0;
 663         for (int r = 0; r < hashRoots; r++) {
 664                 for (Property *p = props[r]; p; p = p->next) {
 665                         len += strlen(p->key) + 1;
 666                         len += strlen(p->val) + 1;
 667                 }
 668         }
 669         if (len == 0)
 670                 len = 1;        // Return as empty string
 671         char *ret = new char [len];
 672         if (ret) {
 673                 char *w = ret;
 674                 for (int root = 0; root < hashRoots; root++) {
 675                         for (Property *p = props[root]; p; p = p->next) {
 676                                 strcpy(w, p->key);
 677                                 w += strlen(p->key);
 678                                 *w++ = '=';
 679                                 strcpy(w, p->val);
 680                                 w += strlen(p->val);
 681                                 *w++ = '\n';
 682                         }
 683                 }
 684                 ret[len-1] = '\0';
 685         }
 686         return ret;
 687 }
 688
 689 /**
 690  * Initiate enumeration.
 691  */
 692 bool PropSet::GetFirst(char **key, char **val) {
 693         for (int i = 0; i < hashRoots; i++) {
 694                 for (Property *p = props[i]; p; p = p->next) {
 695                         if (p) {
 696                                 *key = p->key;
 697                                 *val = p->val;
 698                                 enumnext = p->next; // GetNext will begin here ...
 699                                 enumhash = i;             // ... in this block
 700                                 return true;
 701                         }
 702                 }
 703         }
 704         return false;
 705 }
 706
 707 /**
 708  * Continue enumeration.
 709  */
 710 bool PropSet::GetNext(char ** key, char ** val) {
 711         bool firstloop = true;
 712
 713         // search begins where we left it : in enumhash block
 714         for (int i = enumhash; i < hashRoots; i++) {
 715                 if (!firstloop)
 716                         enumnext = props[i]; // Begin with first property in block
 717                 // else : begin where we left
 718                 firstloop = false;
 719
 720                 for (Property *p = enumnext; p; p = p->next) {
 721                         if (p) {
 722                                 *key = p->key;
 723                                 *val = p->val;
 724                                 enumnext = p->next; // for GetNext
 725                                 enumhash = i;
 726                                 return true;
 727                         }
 728                 }
 729         }
 730         return false;
 731 }
 732
 733 /**
 734  * Creates an array that points into each word in the string and puts \0 terminators
 735  * after each word.
 736  */
 737 static char **ArrayFromWordList(char *wordlist, int *len, bool onlyLineEnds = false) {
 738         int prev = '\n';
 739         int words = 0;
 740         // For rapid determination of whether a character is a separator, build
 741         // a look up table.
 742         bool wordSeparator[256];
 743         for (int i=0;i<256; i++) {
 744                 wordSeparator[i] = false;
 745         }
 746         wordSeparator['\r'] = true;
 747         wordSeparator['\n'] = true;
 748         if (!onlyLineEnds) {
 749                 wordSeparator[' '] = true;
 750                 wordSeparator['\t'] = true;
 751         }
 752         for (int j = 0; wordlist[j]; j++) {
 753                 int curr = static_cast<unsigned char>(wordlist[j]);
 754                 if (!wordSeparator[curr] && wordSeparator[prev])
 755                         words++;
 756                 prev = curr;
 757         }
 758         char **keywords = new char *[words + 1];
 759         if (keywords) {
 760                 words = 0;
 761                 prev = '\0';
 762                 size_t slen = strlen(wordlist);
 763                 for (size_t k = 0; k < slen; k++) {
 764                         if (!wordSeparator[static_cast<unsigned char>(wordlist[k])]) {
 765                                 if (!prev) {
 766                                         keywords[words] = &wordlist[k];
 767                                         words++;
 768                                 }
 769                         } else {
 770                                 wordlist[k] = '\0';
 771                         }
 772                         prev = wordlist[k];
 773                 }
 774                 keywords[words] = &wordlist[slen];
 775                 *len = words;
 776         } else {
 777                 *len = 0;
 778         }
 779         return keywords;
 780 }
 781
 782 void WordList::Clear() {
 783         if (words) {
 784                 delete []list;
 785                 delete []words;
 786                 delete []wordsNoCase;
 787         }
 788         words = 0;
 789         wordsNoCase = 0;
 790         list = 0;
 791         len = 0;
 792         sorted = false;
 793 }
 794
 795 void WordList::Set(const char *s) {
 796         list = StringDup(s);
 797         sorted = false;
 798         words = ArrayFromWordList(list, &len, onlyLineEnds);
 799         wordsNoCase = new char * [len + 1];
 800         memcpy(wordsNoCase, words, (len + 1) * sizeof (*words));
 801 }
 802
 803 char *WordList::Allocate(int size) {
 804         list = new char[size + 1];
 805         list[size] = '\0';
 806         return list;
 807 }
 808
 809 void WordList::SetFromAllocated() {
 810         sorted = false;
 811         words = ArrayFromWordList(list, &len, onlyLineEnds);
 812         wordsNoCase = new char * [len + 1];
 813         memcpy(wordsNoCase, words, (len + 1) * sizeof (*words));
 814 }
 815
 816 int cmpString(const void *a1, const void *a2) {
 817         // Can't work out the correct incantation to use modern casts here
 818         return strcmp(*(char**)(a1), *(char**)(a2));
 819 }
 820
 821 int cmpStringNoCase(const void *a1, const void *a2) {
 822         // Can't work out the correct incantation to use modern casts here
 823         return CompareCaseInsensitive(*(char**)(a1), *(char**)(a2));
 824 }
 825
 826 static void SortWordList(char **words, char **wordsNoCase, unsigned int len) {
 827         qsort(reinterpret_cast<void*>(words), len, sizeof(*words),
 828               cmpString);
 829         qsort(reinterpret_cast<void*>(wordsNoCase), len, sizeof(*wordsNoCase),
 830               cmpStringNoCase);
 831 }
 832
 833 bool WordList::InList(const char *s) {
 834         if (0 == words)
 835                 return false;
 836         if (!sorted) {
 837                 sorted = true;
 838                 SortWordList(words, wordsNoCase, len);
 839                 for (unsigned int k = 0; k < (sizeof(starts) / sizeof(starts[0])); k++)
 840                         starts[k] = -1;
 841                 for (int l = len - 1; l >= 0; l--) {
 842                         unsigned char indexChar = words[l][0];
 843                         starts[indexChar] = l;
 844                 }
 845         }
 846         unsigned char firstChar = s[0];
 847         int j = starts[firstChar];
 848         if (j >= 0) {
 849                 while (words[j][0] == firstChar) {
 850                         if (s[1] == words[j][1]) {
 851                                 const char *a = words[j] + 1;
 852                                 const char *b = s + 1;
 853                                 while (*a && *a == *b) {
 854                                         a++;
 855                                         b++;
 856                                 }
 857                                 if (!*a && !*b)
 858                                         return true;
 859                         }
 860                         j++;
 861                 }
 862         }
 863         j = starts['^'];
 864         if (j >= 0) {
 865                 while (words[j][0] == '^') {
 866                         const char *a = words[j] + 1;
 867                         const char *b = s;
 868                         while (*a && *a == *b) {
 869                                 a++;
 870                                 b++;
 871                         }
 872                         if (!*a)
 873                                 return true;
 874                         j++;
 875                 }
 876         }
 877         return false;
 878 }
 879
 880 /**
 881  * Returns an element (complete) of the wordlist array which has
 882  * the same beginning as the passed string.
 883  * The length of the word to compare is passed too.
 884  * Letter case can be ignored or preserved (default).
 885  */
 886 const char *WordList::GetNearestWord(const char *wordStart, int searchLen, bool ignoreCase /*= false*/, SString wordCharacters /*='/0' */, int wordIndex /*= -1 */) {
 887         int start = 0; // lower bound of the api array block to search
 888         int end = len - 1; // upper bound of the api array block to search
 889         int pivot; // index of api array element just being compared
 890         int cond; // comparison result (in the sense of strcmp() result)
 891         const char *word; // api array element just being compared
 892
 893         if (0 == words)
 894                 return NULL;
 895         if (!sorted) {
 896                 sorted = true;
 897                 SortWordList(words, wordsNoCase, len);
 898         }
 899         if (ignoreCase) {
 900                 while (start <= end) { // binary searching loop
 901                         pivot = (start + end) >> 1;
 902                         word = wordsNoCase[pivot];
 903                         cond = CompareNCaseInsensitive(wordStart, word, searchLen);
 904                         if (!cond) {
 905                                 // find first word
 906                                 start = pivot;
 907                                 while (start > 0 && !CompareNCaseInsensitive(wordStart, wordsNoCase[start-1], searchLen)) {
 908                                         start--;
 909                                 }
 910                                 // find last word
 911                                 end = pivot;
 912                                 while (end < len-1 && !CompareNCaseInsensitive(wordStart, wordsNoCase[end+1], searchLen)) {
 913                                         end++;
 914                                 }
 915
 916                                 // Finds first word in a series of equal words
 917                                 for (pivot = start; pivot <= end; pivot++) {
 918                                         word = wordsNoCase[pivot];
 919                                         if (!wordCharacters.contains(word[searchLen])) {
 920                                                 if (wordIndex <= 0) // Checks if a specific index was requested
 921                                                         return word; // result must not be freed with free()
 922                                                 wordIndex--;
 923                                         }
 924                                 }
 925                                 return NULL;
 926                         }
 927                         else if (cond > 0)
 928                                 start = pivot + 1;
 929                         else if (cond < 0)
 930                                 end = pivot - 1;
 931                 }
 932         } else { // preserve the letter case
 933                 while (start <= end) { // binary searching loop
 934                         pivot = (start + end) >> 1;
 935                         word = words[pivot];
 936                         cond = strncmp(wordStart, word, searchLen);
 937                         if (!cond) {
 938                                 // find first word
 939                                 start = pivot;
 940                                 while (start > 0 && !strncmp(wordStart, words[start-1], searchLen)) {
 941                                         start--;
 942                                 }
 943                                 // find last word
 944                                 end = pivot;
 945                                 while (end < len-1 && !strncmp(wordStart, words[end+1], searchLen)) {
 946                                         end++;
 947                                 }
 948
 949                                 // Finds first word in a series of equal words
 950                                 pivot = start;
 951                                 while (pivot <= end) {
 952                                         word = words[pivot];
 953                                         if (!wordCharacters.contains(word[searchLen])) {
 954                                                 if (wordIndex <= 0) // Checks if a specific index was requested
 955                                                         return word; // result must not be freed with free()
 956                                                 wordIndex--;
 957                                         }
 958                                         pivot++;
 959                                 }
 960                                 return NULL;
 961                         }
 962                         else if (cond > 0)
 963                                 start = pivot + 1;
 964                         else if (cond < 0)
 965                                 end = pivot - 1;
 966                 }
 967         }
 968         return NULL;
 969 }
 970
 971 /**
 972  * Find the length of a 'word' which is actually an identifier in a string
 973  * which looks like "identifier(..." or "identifier" and where
 974  * there may be extra spaces after the identifier that should not be
 975  * counted in the length.
 976  */
 977 static unsigned int LengthWord(const char *word, char otherSeparator) {
 978         // Find a '('. If that fails go to the end of the string.
 979         const char *endWord = strchr(word, '(');
 980         if (!endWord && otherSeparator)
 981                 endWord = strchr(word, otherSeparator);
 982         if (!endWord)
 983                 endWord = word + strlen(word);
 984         // Last case always succeeds so endWord != 0
 985
 986         // Drop any space characters.
 987         if (endWord > word) {
 988                 endWord--;      // Back from the '(', otherSeparator, or '\0'
 989                 // Move backwards over any spaces
 990                 while ((endWord > word) && (IsASpace(*endWord))) {
 991                         endWord--;
 992                 }
 993         }
 994         return endWord - word;
 995 }
 996
 997 /**
 998  * Returns elements (first words of them) of the wordlist array which have
 999  * the same beginning as the passed string.
1000  * The length of the word to compare is passed too.
1001  * Letter case can be ignored or preserved (default).
1002  * If there are more words meeting the condition they are returned all of
1003  * them in the ascending order separated with spaces.
1004  *
1005  * NOTE: returned buffer has to be freed with delete[].
1006  */
1007 char *WordList::GetNearestWords(
1008     const char *wordStart,
1009     int searchLen,
1010     bool ignoreCase /*= false*/,
1011     char otherSeparator /*= '\0'*/,
1012     bool exactLen /*=false*/) {
1013         unsigned int wordlen; // length of the word part (before the '(' brace) of the api array element
1014         SString wordsNear;
1015         wordsNear.setsizegrowth(1000);
1016         int start = 0; // lower bound of the api array block to search
1017         int end = len - 1; // upper bound of the api array block to search
1018         int pivot; // index of api array element just being compared
1019         int cond; // comparison result (in the sense of strcmp() result)
1020
1021         if (0 == words)
1022                 return NULL;
1023         if (!sorted) {
1024                 sorted = true;
1025                 SortWordList(words, wordsNoCase, len);
1026         }
1027         if (ignoreCase) {
1028                 while (start <= end) { // Binary searching loop
1029                         pivot = (start + end) / 2;
1030                         cond = CompareNCaseInsensitive(wordStart, wordsNoCase[pivot], searchLen);
1031                         if (!cond) {
1032                                 // Find first match
1033                                 while ((pivot > start) &&
1034                                         (0 == CompareNCaseInsensitive(wordStart,
1035                                                 wordsNoCase[pivot-1], searchLen))) {
1036                                         --pivot;
1037                                 }
1038                                 // Grab each match
1039                                 while ((pivot <= end) &&
1040                                         (0 == CompareNCaseInsensitive(wordStart,
1041                                                 wordsNoCase[pivot], searchLen))) {
1042                                         wordlen = LengthWord(wordsNoCase[pivot], otherSeparator) + 1;
1043                                         ++pivot;
1044                                         if (exactLen && wordlen != LengthWord(wordStart, otherSeparator) + 1)
1045                                                 continue;
1046                                         wordsNear.append(wordsNoCase[pivot-1], wordlen, ' ');
1047                                 }
1048                                 return wordsNear.detach();
1049                         } else if (cond < 0) {
1050                                 end = pivot - 1;
1051                         } else if (cond > 0) {
1052                                 start = pivot + 1;
1053                         }
1054                 }
1055         } else {        // Preserve the letter case
1056                 while (start <= end) { // Binary searching loop
1057                         pivot = (start + end) / 2;
1058                         cond = strncmp(wordStart, words[pivot], searchLen);
1059                         if (!cond) {
1060                                 // Find first match
1061                                 while ((pivot > start) &&
1062                                         (0 == strncmp(wordStart,
1063                                                 words[pivot-1], searchLen))) {
1064                                         --pivot;
1065                                 }
1066                                 // Grab each match
1067                                 while ((pivot <= end) &&
1068                                         (0 == strncmp(wordStart,
1069                                                 words[pivot], searchLen))) {
1070                                         wordlen = LengthWord(words[pivot], otherSeparator) + 1;
1071                                         ++pivot;
1072                                         if (exactLen && wordlen != LengthWord(wordStart, otherSeparator) + 1)
1073                                                 continue;
1074                                         wordsNear.append(words[pivot-1], wordlen, ' ');
1075                                 }
1076                                 return wordsNear.detach();
1077                         } else if (cond < 0) {
1078                                 end = pivot - 1;
1079                         } else if (cond > 0) {
1080                                 start = pivot + 1;
1081                         }
1082                 }
1083         }
1084         return NULL;
1085 }