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;
claimMemory(int nbytes)90 virtual T* claimMemory( int nbytes ) const { return (T*) malloc(nbytes); }
reclaimMemory(T * p,int newbytes,int oldbytes)91 virtual T* reclaimMemory( T *p, int newbytes, int oldbytes ) const
92 { return (T*) realloc(p, newbytes); }
returnMemory(T * & p)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
remove_()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
claimMemory(int nbytes)257 virtual char* claimMemory( int nbytes ) const { return new char[nbytes]; }
258
returnMemory(char * & p)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 {
EQNameStrEQNameStr485 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:
EQNameStrList()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
compare(int,int,void * data)515 virtual int compare(int, int, void *data)
516 { sabassert(!"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;
SortDef()540 SortDef()
541 : sortExpr(NULL), asText(TRUE), ascend(TRUE), upper1st(FALSE)
542 {};
SortDef(Expression * sortExpr_,Str lang_,Bool asText_,Bool ascend_,Bool upper1st_)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 {
appendConstruct(Expression * sortExpr_,Str lang_,Bool asText_,Bool ascend_,Bool upper1st_)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>
List(int logBlocksize_)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>
append(T what)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 sabassert(block);
620 }
621 }
622 block[nItems++] = what;
623 };
624
625 template <class T>
deppend()626 void List<T>::deppend()
627 {
628 sabassert (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 sabassert(block);
640 }
641 else
642 returnMemory(block);
643 }
644 };
645
646 // double the block size
647
648 template <class T>
grow()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 sabassert(block);
657 }
658
659 template <class T>
rm(int n)660 void List<T>::rm(int n)
661 {
662 sabassert((n >= 0) && (n < nItems));
663 memmove(block + n, block + n + 1, (nItems - n - 1) * sizeof(T));
664 deppend();
665 }
666
667 template <class T>
swap(int i,int j)668 void List<T>::swap(int i, int j)
669 {
670 sabassert((i >= 0) && (i < nItems));
671 sabassert((j >= 0) && (j < nItems));
672 T temp = block[i];
673 block[i] = block[j];
674 block[j] = temp;
675 }
676
677 template <class T>
deppendall()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>
number()690 inline int List<T>::number() const
691 {
692 return nItems;
693 }
694
695 template <class T>
~List()696 List<T>::~List()
697 {
698 deppendall();
699 };
700
701 template <class T>
702 inline T& List<T>::operator[](int ndx) const
703 {
704 sabassert((ndx < nItems) && (ndx >= 0));
705 return block[ndx];
706 };
707
708 template <class T>
last()709 inline T& List<T>::last() const
710 {
711 sabassert(nItems);
712 return block[nItems - 1];
713 }
714
715 template <class T>
isEmpty()716 Bool List<T>::isEmpty() const
717 {
718 return (Bool) (!nItems);
719 }
720
721 template <class T>
insertBefore(T newMember,int refIndex)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>
PList(int logBlocksize_)738 PList<T>::PList(int logBlocksize_)
739 : List<T>(logBlocksize_)
740 {
741 }
742
743 template <class T>
freelast(Bool asArray)744 void PList<T>::freelast(Bool asArray)
745 {
746 deleteScalarOrVector(this->last(), asArray);
747 this->deppend();
748 }
749
750 template <class T>
freeall(Bool asArray)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>
freerm(int n,Bool asArray)759 void PList<T>::freerm(int n, Bool asArray)
760 {
761 sabassert((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>
SList(int logBlocksize_)771 SList<T>::SList(int logBlocksize_)
772 : PList<T>(logBlocksize_)
773 {
774 };
775
776 template <class T>
insert(T what,void * data)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>
insertsort(int bottom,int top,void * data)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>
qsPartition(int & bottom,int & top,void * data)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>
quicksort(int bottom,int top,void * data)837 void SList<T>::quicksort(int bottom, int top, void *data)
838 {
839 sabassert(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>
sort(int from,int to,void * data)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 /******************* sorted string list ***********************/
866 class SortedStringList: public SList<Str*> {
867 public:
SortedStringList()868 SortedStringList() : SList<Str*>(LIST_SIZE_MEDIUM) {};
869 virtual int compare(int, int, void* data);
870 int findIdx(Str & val);
871 };
872
873 #endif //ifndef DataStrHIncl
874
875