libsablot/src/engine/datastr.h

   1 /*
   2  * The contents of this file are subject to the Mozilla Public
   3  * License Version 1.1 (the "License"); you may not use this file
   4  * except in compliance with the License. You may obtain a copy of
   5  * the License at http://www.mozilla.org/MPL/
   6  *
   7  * Software distributed under the License is distributed on an "AS
   8  * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
   9  * implied. See the License for the specific language governing
  10  * rights and limitations under the License.
  11  *
  12  * The Original Code is the Sablotron XSLT Processor.
  13  *
  14  * The Initial Developer of the Original Code is Ginger Alliance Ltd.
  15  * Portions created by Ginger Alliance are Copyright (C) 2000-2002
  16  * Ginger Alliance Ltd. All Rights Reserved.
  17  *
  18  * Contributor(s):
  19  *
  20  * Alternatively, the contents of this file may be used under the
  21  * terms of the GNU General Public License Version 2 or later (the
  22  * "GPL"), in which case the provisions of the GPL are applicable
  23  * instead of those above.  If you wish to allow use of your
  24  * version of this file only under the terms of the GPL and not to
  25  * allow others to use your version of this file under the MPL,
  26  * indicate your decision by deleting the provisions above and
  27  * replace them with the notice and other provisions required by
  28  * the GPL.  If you do not delete the provisions above, a recipient
  29  * may use your version of this file under either the MPL or the
  30  * GPL.
  31  */
  32
  33 //
  34 // datastr.h
  35 //
  36 // most constants (list sizes etc.) are in base.h
  37
  38 // GP: clean
  39
  40 #ifndef DataStrHIncl
  41 #define DataStrHIncl
  42
  43 // error.h will be included later:
  44 #define BaseH_NoErrorH
  45 #include "base.h"
  46 // #include "situa.h"
  47 #undef BaseH_NoErrorH
  48
  49 typedef unsigned long Phrase;
  50 class HashTable;
  51 class Tree;
  52
  53 #define QSORT_THRESHOLD     10      // insertsort is used for smaller lists
  54
  55 // List is a basic structure for ordered lists.
  56 // If the T's are pointers, you may want to use PList instead, which
  57 // allows you to delete the pointers (in List, they are just taken off the
  58 // list).
  59
  60 template <class T>
  61 class List /* : public SabObj */
  62 {
  63 public:
  64     List(int logBlocksize_ = LIST_SIZE_SMALL);
  65         // append an element to the end of list
  66     void append(T x);
  67         // remove last element from list
  68     void deppend();
  69         // remove all elements (shrink list to size 0)
  70     void deppendall();
  71         // remove element with given index
  72     void rm(int);
  73         // test whether list is empty
  74     Bool isEmpty() const;
  75         // number of elements in list
  76     inline int number() const;
  77         // get element with given index
  78     T& operator[](int ndx) const;
  79         // get last element
  80     inline T& last() const;
  81         // swap two elements with given indices
  82     virtual void swap(int,int);
  83     void insertBefore(T newMember, int refIndex);
  84     virtual ~List(void);
  85 protected:
  86     void grow();
  87     int nItems;
  88     T *block;
  89     int blocksize, origBlocksize;
  90     virtual T* claimMemory( int nbytes ) const { return (T*) malloc(nbytes); }
  91     virtual T* reclaimMemory( T *p, int newbytes, int oldbytes ) const
  92         { return (T*) realloc(p, newbytes); }
  93     virtual void returnMemory( T* &p ) const { if (p) free(p); p = NULL; }
  94 };
  95
  96 // PList is for lists whose members are pointers. It adds the possibility
  97 // to delete pointers when removing them from the list.
  98 // The Bool parameters in its methods say whether delete[] or delete should
  99 // be used (TRUE/FALSE, respectively).
 100 //
 101 template <class T>
 102 class PList : public List<T>
 103 {
 104 public:
 105     PList(int logBlocksize_ = LIST_SIZE_SMALL);
 106         // free and remove the last pointer
 107     void freelast(Bool);
 108         // free and remove all pointers
 109     void freeall(Bool);
 110         // free and remove the given pointer
 111     void freerm(int, Bool);
 112 };
 113
 114
 115 /*****************************************************************
 116 DynBlock
 117
 118   is a class for "dynamic memory blocks", i.e. blocks that can
 119   grow in size.
 120 *****************************************************************/
 121
 122 struct DynBlockItem
 123 {
 124     char *data;
 125     int byteCount;
 126     DynBlockItem *next;
 127 };
 128
 129 class DynBlock
 130 {
 131     friend class DStr;
 132 public:
 133     DynBlock();
 134     ~DynBlock();
 135     void nadd(const char *data, int bytes);
 136     Bool isEmpty() const;
 137     char* getPointer() const;
 138     char* compactToBuffer() const;
 139 protected:
 140     int byteCount;
 141     DynBlockItem *first, *last;
 142     void remove();
 143     void compact() const;
 144     int compactToBuffer_(char* buf, Bool kill_);
 145 };
 146
 147
 148 // block for the dynamic strings
 149 class DynStrBlock : public DynBlock
 150 {
 151 public:
 152         // compact the string into one chunk,
 153         // prepending 'firstPart' and appending 0.
 154     char* compactString_(const char *firstPart, int firstLen);
 155 };
 156
 157
 158 /*****************************************************************
 159
 160     Str
 161     static string
 162
 163 *****************************************************************/
 164
 165 class DStr;
 166
 167 class Str
 168 {
 169 public:
 170     friend class DStr;
 171         // constructors: default, copy, from char, char* and from
 172         // dynamic string
 173     Str();
 174     Str(const Str& string);
 175     Str(int num);
 176     Str(double num);
 177     Str(char c);
 178     Str(const char *chars);
 179     Str(const DStr &dstring);
 180
 181         // assignment: from DStr, Str, char*, char, int, double
 182     Str& operator=(const DStr& string);
 183     Str& operator=(const Str& string);
 184     Str& operator=(const char *chars);
 185     Str& operator=(char c);
 186     Str& operator=(int number);
 187     Str& operator=(double dblnum);
 188
 189         // set self to a string of length 'len' (non-NULL-terminated)
 190     void nset(const char* chars, int len);
 191
 192         // set self to an empty string
 193     virtual void empty();
 194
 195         // test whether the string is void
 196     Bool isEmpty() const;
 197
 198         // get byte with the given index
 199         // NEEDS TO INCLUDE pack_()
 200     char operator[](int index) const;
 201
 202         // convert to const char* (just return the internal pointer)
 203         // NEEDS TO INCLUDE pack_()
 204     virtual operator char*() const;
 205
 206         // test for < / == / > against a Str, char*
 207         // NEEDS TO INCLUDE pack_()
 208     int compare(const Str &other) const;
 209     int compare(const char *otherChars) const;
 210
 211         // test for being lex-smaller than other Str, char*
 212         // NEEDS TO INCLUDE pack_()
 213     Bool operator< (const Str &);
 214     Bool operator< (const char*);
 215
 216         // test for equality: to a Str, char*
 217         // NEEDS TO INCLUDE pack_()
 218     Bool operator== (const Str& other) const;
 219     Bool operator== (const char* otherChars) const;
 220     Bool operator== (char* otherChars) const;
 221
 222         // non-case-sensitive test for equality: to a Str, char*
 223         // NEEDS TO INCLUDE pack_()
 224     Bool eqNoCase(const Str& other) const;
 225     Bool eqNoCase(const char* otherChars) const;
 226
 227         // get the byte length of the string
 228     virtual int length() const;
 229
 230         // addition operator: with char*, Str and int
 231         // NEEDS TO INCLUDE pack_()
 232     DStr operator+ (const Str& other) const;
 233     DStr operator+ (const char *otherChars) const;
 234     DStr operator+ (int otherNum) const;
 235
 236         // convert *this to double, return FALSE if OK
 237     Bool toDouble(double& retval) const;
 238
 239     DStr& appendSelf(DStr& other);
 240
 241
 242     // THE FOLLOWING 3 FUNCTIONS WOULD BE BEST REMOVED
 243         // output *this to another string with whitespace trimmed
 244     void speakTerse(DStr &);
 245
 246     char* cloneData();
 247
 248     virtual ~Str();
 249 protected:
 250         // deallocate all memory used
 251     virtual void remove_() { returnMemory(text_); }
 252
 253         // pack all parts (in derived classes) to form a valid Str
 254     virtual void pack_() const;
 255
 256     // claimMemory and returnMemory are to facilitate allocating the character data in an arena
 257     virtual char* claimMemory( int nbytes ) const { return new char[nbytes]; }
 258
 259     virtual void returnMemory( char *&p ) const { if (p) delete[] p; p = NULL; }
 260
 261     char* text_;
 262     int byteLength_;
 263 };
 264
 265
 266 /*****************************************************************
 267     DStr
 268     dynamic string
 269 *****************************************************************/
 270
 271 class DStr : public Str
 272 {
 273 public:
 274     DStr();
 275     DStr(char c);
 276     DStr(const char *chars);
 277     DStr(const Str& string);
 278     DStr(const DStr& dstring);
 279
 280     DStr& operator=(const DStr& other);
 281
 282         // append a string or whatever
 283     DStr& operator+= (const DStr& other);
 284     DStr& operator+= (const Str& other);
 285     DStr& operator+= (const char* otherChars);
 286     DStr& operator+= (char c);
 287     DStr& operator+= (int num);
 288
 289     virtual DStr& appendSelf(DStr& other);
 290
 291         // nadd adds a non-zero-terminated string
 292     DStr& nadd(const char *,int);
 293
 294     virtual operator char*() const;
 295     virtual int length() const;
 296
 297         // consume is just like += but it steals the char*'s from 'other'.
 298 /*
 299     DStr& operator consume(Str &other);
 300     DStr& operator consume(DStr &other);
 301 */
 302
 303     virtual ~DStr();
 304 private:
 305         // deallocate all memory used
 306     virtual void remove_();
 307         // pack all parts (in derived classes) to form a valid Str
 308     virtual void pack_() const;
 309     DynStrBlock blocks;
 310 };
 311
 312
 313 //
 314 //
 315 //  string constants and functions
 316 //
 317 //
 318
 319 void escapeChars(DStr& result, const Str& what,
 320                  const char* toEscape, const char** substitutes);
 321
 322 /* extern const Str* theEmptyString; */
 323
 324 /*****************************************************************
 325 NamespaceStack
 326 *****************************************************************/
 327
 328 class NamespaceStackObj /* : public SabObj */
 329 {
 330 public:
 331    Str prefix, uri;
 332    Bool hidden;
 333 };
 334
 335 class NamespaceStack : public PList<NamespaceStackObj*>
 336 {
 337 public:
 338         // find the index of the element with the given key
 339     int findNum(const Str &_key) const;
 340         // find the value of the element with the given key
 341     const Str* getUri(const Str &) const;
 342     Bool isHidden(const Str &) const;
 343     void appendConstruct(const Str &prefix, const Str& uri,
 344                          Bool _hidden);
 345 };
 346
 347 /****************************************
 348 Q N a m e
 349 ****************************************/
 350 // container for a QName (e.g. "books:isbn") consisting
 351 // of the "namespace prefix", "namespace URI" and the "local part"
 352
 353 class QName
 354 {
 355     friend class TreeConstructer;
 356 public:
 357     QName();
 358     QName(const QName &other);
 359         // set the QName from the string received from expat (using NS_SEP)
 360     QName& operator =(const QName& other);
 361     Bool isEmpty() const;
 362     void empty();
 363
 364         // set just the prefix
 365     void setPrefix(Phrase);
 366     void setLocal(Phrase);
 367     void setUri(Phrase);
 368
 369         // return the full name
 370     // Str getname(Tree& t) const;
 371         // return the local part
 372     Phrase getLocal() const;
 373         // return the URI
 374     Phrase getUri() const;
 375         // return the prefix
 376     Phrase getPrefix() const;
 377         // return true if a prefix is defined
 378     Bool hasPrefix() const;
 379
 380         // check for equality to another qname
 381     Bool operator==(const QName &) const;
 382
 383         // output to a string
 384     // void speak(DStr&, SpeakMode) const;
 385         // check if our own prefix is bound to the given namespace
 386     // Bool prefixIsNS(const Str &s) const;
 387         // get the associated dictionary
 388 private:
 389     Phrase
 390         prefix,
 391         uri,
 392         local;
 393 };
 394
 395 /*****************************************************************
 396 Q N a m e L i s t
 397 *****************************************************************/
 398
 399 class QNameList : public PList<QName *>
 400 {
 401 public:
 402     // finds item with equal local-part and uri
 403     int findNdx(const QName &what) const;
 404 };
 405
 406 /****************************************
 407 E Q N a m e
 408 ****************************************/
 409
 410 class EQName
 411 {
 412 //    friend class TreeConstructer;
 413 public:
 414     EQName();
 415     EQName(const EQName&);
 416     Bool isEmpty() const;
 417     void empty();
 418
 419     void set(const QName&, const HashTable&);
 420     void setPrefix(const Str&);
 421     void setLocal(const Str&);
 422     void setUri(const Str&);
 423
 424         // return the full name
 425     void getname(Str& fullName) const;
 426         // return the local part
 427     const Str& getLocal() const;
 428         // return the URI
 429     const Str& getUri() const;
 430         // return the prefix
 431     const Str& getPrefix() const;
 432         // return true if a prefix is defined
 433     Bool hasPrefix() const;
 434
 435         // check for equality to another qname
 436     Bool operator==(const EQName &) const;
 437
 438 private:
 439     Str
 440         prefix,
 441         uri,
 442         local;
 443 };
 444
 445
 446
 447 /*****************************************************************
 448     S t r S t r L i s t
 449 *****************************************************************/
 450
 451 class StrStr /* : public SabObj */
 452 {
 453 public:
 454     Str
 455         key,
 456         value;
 457 };
 458
 459 class StrStrList : public PList<StrStr*>
 460 {
 461 public:
 462         // find the index of the element with the given key
 463     int findNum(const Str &_key) const;
 464         // find the value of the element with the given key
 465     Str* find(const Str &) const;
 466     void appendConstruct(const Str &key, const Str& value);
 467 };
 468
 469
 470 /*****************************************************************
 471     E Q N a m e L i s t
 472 *****************************************************************/
 473
 474 class EQNameList : public PList<EQName *>
 475 {
 476 public:
 477     const EQName* find(const EQName &what) const;
 478 };
 479
 480 /*****************************************************************
 481     E Q N a m e S t r L i s t
 482 *****************************************************************/
 483 struct EQNameStr
 484 {
 485     EQNameStr(const EQName& key_, const Str& value_) : key(key_), value(value_)
 486     {
 487     };
 488     EQName key;
 489     Str value;
 490 };
 491
 492 class EQNameStrList : public PList<EQNameStr *>
 493 {
 494 public:
 495     EQNameStrList()
 496     {
 497     };
 498     int findNdx(const EQName &what) const;
 499     const Str* find(const EQName &what) const;
 500     void appendConstruct(const EQName &key, const Str& value);
 501 };
 502
 503 /*****************************************************************
 504
 505     S L i s t
 506
 507 *****************************************************************/
 508
 509 template <class T>
 510 class SList: public PList<T>
 511 {
 512 public:
 513     SList(int logBlocksize_);
 514         // comparison of two elements
 515     virtual int compare(int, int, void *data)
 516     { assert(!"abstract compare"); return 0; }
 517         // insertion of an element
 518     void insert(T, void *data = NULL);
 519     void sort(int from = 0, int to = - 1, void *data = NULL);  // to == -1 means "nItems-1"
 520 private:
 521     void quicksort(int bottom, int top, void *data);
 522     void qsPartition(int& i, int& j, void *data);
 523     void insertsort(int bottom, int top, void *data);
 524 };
 525
 526 /***********
 527
 528   SortDef
 529
 530 ***********/
 531
 532 class Expression;
 533
 534 class SortDef
 535 {
 536 public:
 537     Expression *sortExpr;
 538     Str lang;
 539     Bool asText, ascend, upper1st;
 540     SortDef()
 541       : sortExpr(NULL), asText(TRUE), ascend(TRUE), upper1st(FALSE)
 542         {};
 543     SortDef(Expression *sortExpr_, Str lang_,
 544         Bool asText_, Bool ascend_, Bool upper1st_)
 545         : sortExpr(sortExpr_), lang(lang_),
 546           asText(asText_), ascend(ascend_), upper1st(upper1st_)
 547         {};
 548 };
 549
 550 /***********
 551
 552   SortDefList
 553
 554 ***********/
 555
 556 class SortDefList : public PList<SortDef*>
 557 {
 558     void appendConstruct(Expression *sortExpr_, Str lang_,
 559         Bool asText_, Bool ascend_, Bool upper1st_)
 560     {
 561         append(new SortDef(sortExpr_, lang_,
 562             asText_, ascend_, upper1st_));
 563     };
 564 };
 565
 566 /***************************************
 567 U r i  L i s t
 568 ****************************************/
 569
 570 /****************************************/
 571 /* exclusion prefix list                */
 572
 573 class UriList : public PList<Phrase>
 574 {
 575 public:
 576   //UriList();
 577   void addUri(Phrase);
 578   //void removeUri(Str & uri);
 579   int findNdx(Phrase);
 580 };
 581
 582 /*****************************************************************
 583
 584 t e m p l a t e   m e t h o d s
 585
 586 *****************************************************************/
 587
 588 #include "situa.h"
 589 //#include "error.h"
 590
 591
 592 /*================================================================
 593 List methods
 594 ================================================================*/
 595
 596 template <class T>
 597 List<T>::List(int logBlocksize_)
 598 :
 599 origBlocksize(TWO_TO(logBlocksize_))
 600 {
 601     nItems = 0;
 602     blocksize = 0;
 603     block = NULL;
 604 };
 605
 606
 607 template <class T>
 608 void List<T>::append(T what)
 609 {
 610     if (nItems >= blocksize)
 611     {
 612         if (block)
 613             grow();
 614         else
 615         {
 616             blocksize = origBlocksize;
 617             block = (T*) claimMemory(blocksize * sizeof(T));
 618             // FIXME: asserting memory request ok
 619             assert(block);
 620         }
 621     }
 622     block[nItems++] = what;
 623 };
 624
 625 template <class T>
 626 void List<T>::deppend()
 627 {
 628     assert (nItems > 0);
 629     --nItems;
 630     if (!(nItems & (nItems - 1)) && (nItems >= origBlocksize))   // realloc at powers of 2
 631     {
 632         int oldblocksize = blocksize;
 633         blocksize = nItems;
 634         if (blocksize)
 635         {
 636             block = (T*) reclaimMemory(block, blocksize * sizeof(T),
 637                 oldblocksize * sizeof(T));
 638             // FIXME: asserting memory request ok
 639             assert(block);
 640         }
 641         else
 642             returnMemory(block);
 643     }
 644 };
 645
 646 // double the block size
 647
 648 template <class T>
 649 void List<T>::grow()
 650 {
 651     if (!block) return;
 652     blocksize = blocksize << 1;
 653     int nbytes = blocksize * sizeof(T);
 654     block = (T*) reclaimMemory(block, nbytes, nbytes >> 1);
 655     // FIXME: asserting memory request ok
 656     assert(block);
 657 }
 658
 659 template <class T>
 660 void List<T>::rm(int n)
 661 {
 662     assert((n >= 0) && (n < nItems));
 663     memmove(block + n, block + n + 1, (nItems - n - 1) * sizeof(T));
 664     deppend();
 665 }
 666
 667 template <class T>
 668 void List<T>::swap(int i, int j)
 669 {
 670     assert((i >= 0) && (i < nItems));
 671     assert((j >= 0) && (j < nItems));
 672     T temp = block[i];
 673     block[i] = block[j];
 674     block[j] = temp;
 675 }
 676
 677 template <class T>
 678 void List<T>::deppendall()
 679 {
 680     nItems = 0;
 681     blocksize = 0;
 682     returnMemory(block);
 683 /*    if (block)
 684         free(block);
 685         */
 686 //    block = NULL;
 687 }
 688
 689 template <class T>
 690 inline int List<T>::number() const
 691 {
 692     return nItems;
 693 }
 694
 695 template <class T>
 696 List<T>::~List()
 697 {
 698     deppendall();
 699 };
 700
 701 template <class T>
 702 inline T& List<T>::operator[](int ndx) const
 703 {
 704     assert((ndx < nItems) && (ndx >= 0));
 705     return block[ndx];
 706 };
 707
 708 template <class T>
 709 inline T& List<T>::last() const
 710 {
 711     assert(nItems);
 712     return block[nItems - 1];
 713 }
 714
 715 template <class T>
 716 Bool List<T>::isEmpty() const
 717 {
 718     return (Bool) (!nItems);
 719 }
 720
 721 template <class T>
 722 void List<T>::insertBefore(T newMember, int refIndex)
 723 {
 724     append(newMember);
 725     memmove(block + refIndex + 1, block + refIndex,
 726         (number()-refIndex-1) * sizeof(T));
 727         block[refIndex] = newMember;
 728 }
 729
 730 /*================================================================
 731 PList methods
 732 ================================================================*/
 733
 734 #define deleteScalarOrVector(PTR, VECT) \
 735     {if (VECT) delete[] PTR; else delete PTR;}
 736
 737 template <class T>
 738 PList<T>::PList(int logBlocksize_)
 739 : List<T>(logBlocksize_)
 740 {
 741 }
 742
 743 template <class T>
 744 void PList<T>::freelast(Bool asArray)
 745 {
 746     deleteScalarOrVector(this->last(), asArray);
 747     this->deppend();
 748 }
 749
 750 template <class T>
 751 void PList<T>::freeall(Bool asArray)
 752 {
 753     for (int i = 0; i < this->nItems; i++)
 754         deleteScalarOrVector(this->block[i], asArray);
 755     this->deppendall();
 756 }
 757
 758 template <class T>
 759 void PList<T>::freerm(int n, Bool asArray)
 760 {
 761     assert((n >= 0) && (n < this->nItems));
 762     deleteScalarOrVector(this->block[n], asArray);
 763     this->rm(n);
 764 }
 765
 766 /*================================================================
 767 SList methods
 768 ================================================================*/
 769
 770 template <class T>
 771 SList<T>::SList(int logBlocksize_)
 772     : PList<T>(logBlocksize_)
 773 {
 774 };
 775
 776 template <class T>
 777 void SList<T>::insert(T what, void *data /* = NULL */)
 778 {
 779     this->append(what);
 780     int whatndx = this->number() - 1;
 781     int i, j;
 782     for (i=0; i < whatndx; i++)
 783         if (compare(whatndx, i, data) == -1) break;
 784     if (i < whatndx)
 785     {
 786         for (j = whatndx; j > i; j--)
 787             this->operator[](j) = this->operator[](j-1);
 788         this->operator[](i) = what;
 789     };
 790 };
 791
 792 template <class T>
 793 void SList<T>::insertsort(int bottom, int top, void *data)
 794 {
 795     int ceiling, k;
 796     //T curr;
 797     for (ceiling = bottom + 1; ceiling <= top; ceiling++)
 798     {
 799       //curr = this->block[ceiling];
 800         /* was:
 801         for (k = ceiling - 1; k >= bottom && compare(k, ceiling) > 0; k--)
 802             this->block[k+1] = this->block[k];
 803         this->block[k+1] = curr;
 804          * but need to use swap() to drag extra pointers along
 805          */
 806         for (k = ceiling - 1; k >= bottom && compare(k, k + 1, data) > 0; k--)
 807             this->swap(k, k+1);
 808     }
 809 }
 810
 811 template <class T>
 812 void SList<T>::qsPartition(int& bottom, int& top, void *data)
 813 {
 814     int middle = (bottom + top) >> 1;
 815     if (compare(bottom, top, data) > 0) this->swap(bottom, top);
 816     if (compare(middle, top, data) > 0) this->swap(middle, top);
 817     if (compare(bottom, middle, data) > 0) this->swap(bottom, middle);
 818     // T pivot = this->block[middle];
 819     while (bottom <= top)
 820     {
 821         // boundary conditions fixed by Tim
 822         while ((++bottom <= top) && compare(bottom, middle, data) <= 0);
 823         while ((--top >= bottom) && (compare(top, middle, data) >= 0));
 824
 825         if (bottom < top)
 826         {
 827             if (middle == bottom)
 828                 middle = top;
 829             else if (middle == top)
 830                 middle = bottom;
 831             this->swap(bottom, top);
 832         }
 833     }
 834 }
 835
 836 template <class T>
 837 void SList<T>::quicksort(int bottom, int top, void *data)
 838 {
 839     assert(QSORT_THRESHOLD >= 3);
 840     int i = bottom, j = top;
 841     if (top - bottom < QSORT_THRESHOLD)
 842         insertsort(bottom, top, data);
 843     else
 844     {
 845         qsPartition(i, j, data);
 846         quicksort(bottom, j, data);
 847         quicksort(i, top, data);
 848     }
 849 }
 850
 851 template <class T>
 852 void SList<T>::sort(int from /* = 0 */, int to /* = - 1 */, void *data /* = NULL */)
 853 {
 854     /* cannot initialize 'to' to nItems-1 directly as g++ reports error */
 855     if (to == -1)
 856         to = this->nItems - 1;
 857     if (this->nItems < 2)
 858         return;
 859     quicksort(from, to, data);
 860 }
 861
 862 /******************* expression list moved here ***************/
 863 typedef PList<Expression *> ExprList;
 864
 865 #endif //ifndef DataStrHIncl
 866