JavaScriptCore:
[WebKit-https.git] / WebCore / platform / DeprecatedString.cpp
1 /*
2  * Copyright (C) 2004, 2005, 2006 Apple Computer, Inc.  All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "config.h"
27 #include "DeprecatedString.h"
28
29 #include "CString.h"
30 #include "Logging.h"
31 #include "PlatformString.h"
32 #include "RegularExpression.h"
33 #include "TextEncoding.h"
34 #include <kjs/dtoa.h>
35 #include <kjs/identifier.h>
36 #include <stdarg.h>
37 #include <stdio.h>
38 #include <wtf/Platform.h>
39 #include <wtf/StringExtras.h>
40
41 #if PLATFORM(WIN_OS)
42 #include <windows.h>
43 #endif
44
45 #if PLATFORM(QT)
46 #include <QString>
47 #endif
48
49 using namespace std;
50 using namespace KJS;
51
52 namespace WebCore {
53
54 COMPILE_ASSERT(sizeof(DeprecatedChar) == 2, deprecated_char_is_2_bytes)
55
56 #define CHECK_FOR_HANDLE_LEAKS 0
57
58 #if PLATFORM(SYMBIAN)
59 #undef CHECK_FOR_HANDLE_LEAKS
60 // symbian:fixme need page aligned allocations as Symbian platform does not have support for valloc
61 #define CHECK_FOR_HANDLE_LEAKS 1
62 #endif
63
64 #define ALLOC_QCHAR_GOOD_SIZE(X) (X)
65 #define ALLOC_CHAR_GOOD_SIZE(X) (X)
66
67 #define ALLOC_CHAR(N) (char*)fastMalloc(N)
68 #define REALLOC_CHAR(P, N) (char *)fastRealloc(P, N)
69 #define DELETE_CHAR(P) fastFree(P)
70
71 #define WEBCORE_ALLOCATE_CHARACTERS(N) (DeprecatedChar*)fastMalloc(sizeof(DeprecatedChar)*(N))
72 #define WEBCORE_REALLOCATE_CHARACTERS(P, N) (DeprecatedChar *)fastRealloc(P, sizeof(DeprecatedChar)*(N))
73 #define DELETE_QCHAR(P) fastFree(P)
74
75 struct HandleNode;
76 struct HandlePageNode;
77
78 static HandleNode *allocateNode(HandlePageNode *pageNode);
79 static HandlePageNode *allocatePageNode();
80
81 static HandlePageNode *usedNodeAllocationPages = 0;
82 static HandlePageNode *freeNodeAllocationPages = 0;
83
84 static inline void initializeHandleNodes()
85 {
86     if (freeNodeAllocationPages == 0)
87         freeNodeAllocationPages = allocatePageNode();
88 }
89
90 static inline DeprecatedStringData **allocateHandle()
91 {
92 #ifdef CHECK_FOR_HANDLE_LEAKS
93     return static_cast<DeprecatedStringData **>(fastMalloc(sizeof(DeprecatedStringData *)));
94 #endif
95
96     initializeHandleNodes();
97     
98     return reinterpret_cast<DeprecatedStringData **>(allocateNode(freeNodeAllocationPages));
99 }
100
101 static void freeHandle(DeprecatedStringData **);
102
103 #define IS_ASCII_QCHAR(c) ((c).unicode() > 0 && (c).unicode() <= 0xff)
104
105 static const int caseDelta = ('a' - 'A');
106
107 const char * const DeprecatedString::null = 0;
108
109 DeprecatedStringData *DeprecatedString::shared_null = 0;
110 DeprecatedStringData **DeprecatedString::shared_null_handle = 0;
111
112 // -------------------------------------------------------------------------
113 // Utility functions
114 // -------------------------------------------------------------------------
115
116 static inline int ucstrcmp( const DeprecatedString &as, const DeprecatedString &bs )
117 {
118     const DeprecatedChar *a = as.unicode();
119     const DeprecatedChar *b = bs.unicode();
120     if ( a == b )
121         return 0;
122     if ( a == 0 )
123         return 1;
124     if ( b == 0 )
125         return -1;
126     int l = min(as.length(), bs.length());
127     while ( l-- && *a == *b )
128         a++,b++;
129     if ( l == -1 )
130         return ( as.length() - bs.length() );
131     return a->unicode() - b->unicode();
132 }
133
134
135 static bool equal(const DeprecatedChar *a, const char *b, int l)
136 {
137     ASSERT(l >= 0);
138     while (l--) {
139         if (*a != *b)
140             return false;
141         a++; b++;
142     }
143     return true;
144 }
145
146 // Not a "true" case insensitive compare; only insensitive for plain ASCII.
147
148 static bool equalCaseInsensitive(const char *a, const char *b, int l)
149 {
150     ASSERT(l >= 0);
151     while (l--) {
152         if (tolower(*a) != tolower(*b))
153             return false;
154         a++; b++;
155     }
156     return true;
157 }
158
159 static bool equalCaseInsensitive(const DeprecatedChar *a, const char *b, int l)
160 {
161     ASSERT(l >= 0);
162     while (l--) {
163         if (tolower(a->unicode()) != tolower(*b))
164             return false;
165         a++; b++;
166     }
167     return true;
168 }
169
170 static bool equalCaseInsensitive(const DeprecatedChar *a, const DeprecatedChar *b, int l)
171 {
172     ASSERT(l >= 0);
173     while (l--) {
174         if (tolower(a->unicode()) != tolower(b->unicode()))
175             return false;
176         a++; b++;
177     }
178     return true;
179 }
180
181 static inline bool equalCaseInsensitive(char c1, char c2)
182 {
183     return tolower(c1) == tolower(c2);
184 }
185
186 static inline bool equalCaseInsensitive(DeprecatedChar c1, char c2)
187 {
188     return tolower(c1.unicode()) == tolower(static_cast<unsigned char>(c2));
189 }
190
191 static bool ok_in_base(DeprecatedChar c, int base)
192 {
193     int uc = c.unicode();
194     if (isdigit(uc))
195         return uc - '0' < base;
196     if (isalpha(uc)) {
197         if (base > 36)
198             base = 36;
199         return (uc >= 'a' && uc < 'a' + base - 10)
200             || (uc >= 'A' && uc < 'A' + base - 10);
201     }
202     return false;
203 }
204
205 // -------------------------------------------------------------------------
206 // DeprecatedStringData
207 // -------------------------------------------------------------------------
208
209 // FIXME, make constructor explicity take a 'copy' flag.
210 // This can be used to hand off ownership of allocated data when detaching and
211 // deleting QStrings.
212
213 DeprecatedStringData::DeprecatedStringData() :
214         refCount(1), _length(0), _unicode(0), _ascii(0), _maxUnicode(WEBCORE_DS_INTERNAL_BUFFER_UCHARS), _isUnicodeValid(0), _isHeapAllocated(0), _maxAscii(WEBCORE_DS_INTERNAL_BUFFER_CHARS), _isAsciiValid(1) 
215
216     _ascii = _internalBuffer;
217     _internalBuffer[0] = 0;
218 }
219
220 void DeprecatedStringData::initialize()
221 {
222     refCount = 1;
223     _length = 0;
224     _unicode = 0;
225     _ascii = _internalBuffer;
226     _maxUnicode = WEBCORE_DS_INTERNAL_BUFFER_UCHARS;
227     _isUnicodeValid = 0;
228     _maxAscii = WEBCORE_DS_INTERNAL_BUFFER_CHARS;
229     _isAsciiValid = 1;
230     _internalBuffer[0] = 0;
231     _isHeapAllocated = 0;
232 }
233
234 // Don't copy data.
235 DeprecatedStringData::DeprecatedStringData(DeprecatedChar *u, unsigned l, unsigned m) :
236         refCount(1), _length(l), _unicode(u), _ascii(0), _maxUnicode(m), _isUnicodeValid(1), _isHeapAllocated(0), _maxAscii(WEBCORE_DS_INTERNAL_BUFFER_CHARS), _isAsciiValid(0)
237 {
238     ASSERT(m >= l);
239 }
240
241 // Don't copy data.
242 void DeprecatedStringData::initialize(DeprecatedChar *u, unsigned l, unsigned m)
243 {
244     ASSERT(m >= l);
245     refCount = 1;
246     _length = l;
247     _unicode = u;
248     _ascii = 0;
249     _maxUnicode = m;
250     _isUnicodeValid = 1;
251     _maxAscii = 0;
252     _isAsciiValid = 0;
253     _isHeapAllocated = 0;
254 }
255
256 // Copy data
257 DeprecatedStringData::DeprecatedStringData(const DeprecatedChar *u, unsigned l)
258 {
259     initialize (u, l);
260 }
261
262 // Copy data
263 void DeprecatedStringData::initialize(const DeprecatedChar *u, unsigned l)
264 {
265     refCount = 1;
266     _length = l;
267     _ascii = 0;
268     _isUnicodeValid = 1;
269     _maxAscii = 0;
270     _isAsciiValid = 0;
271     _isHeapAllocated = 0;
272
273     if (l > WEBCORE_DS_INTERNAL_BUFFER_UCHARS) {
274         _maxUnicode = ALLOC_QCHAR_GOOD_SIZE(l);
275         _unicode = WEBCORE_ALLOCATE_CHARACTERS(_maxUnicode);
276         memcpy(_unicode, u, l*sizeof(DeprecatedChar));
277     } else {
278         _maxUnicode = WEBCORE_DS_INTERNAL_BUFFER_UCHARS;
279         _unicode = (DeprecatedChar *)_internalBuffer;
280         if (l)
281             memcpy(_internalBuffer, u, l*sizeof(DeprecatedChar));
282     }
283 }
284
285
286 // Copy data
287 DeprecatedStringData::DeprecatedStringData(const char *a, unsigned l)
288 {
289     initialize(a, l);
290 }
291
292
293 // Copy data
294 void DeprecatedStringData::initialize(const char *a, unsigned l)
295 {
296     refCount = 1;
297     _length = l;
298     _unicode = 0;
299     _isUnicodeValid = 0;
300     _maxUnicode = 0;
301     _isAsciiValid = 1;
302     _isHeapAllocated = 0;
303
304     if (l > WEBCORE_DS_INTERNAL_BUFFER_CHARS) {
305         _maxAscii = ALLOC_CHAR_GOOD_SIZE(l+1);
306         _ascii = ALLOC_CHAR(_maxAscii);
307         if (a)
308             memcpy(_ascii, a, l);
309         _ascii[l] = 0;
310     } else {
311         _maxAscii = WEBCORE_DS_INTERNAL_BUFFER_CHARS;
312         _ascii = _internalBuffer;
313         if (a)
314             memcpy(_internalBuffer, a, l);
315         _internalBuffer[l] = 0;
316     }
317 }
318
319 DeprecatedStringData::DeprecatedStringData(DeprecatedStringData &o)
320     : refCount(1)
321     , _length(o._length)
322     , _unicode(o._unicode)
323     , _ascii(o._ascii)
324     , _maxUnicode(o._maxUnicode)
325     , _isUnicodeValid(o._isUnicodeValid)
326     , _isHeapAllocated(0)
327     , _maxAscii(o._maxAscii)
328     , _isAsciiValid(o._isAsciiValid)
329 {
330     // Handle the case where either the Unicode or 8-bit pointer was
331     // pointing to the internal buffer. We need to point at the
332     // internal buffer in the new object, and copy the characters.
333     if (_unicode == reinterpret_cast<DeprecatedChar *>(o._internalBuffer)) {
334         if (_isUnicodeValid) {
335             ASSERT(!_isAsciiValid || _ascii != o._internalBuffer);
336             ASSERT(_length <= WEBCORE_DS_INTERNAL_BUFFER_UCHARS);
337             memcpy(_internalBuffer, o._internalBuffer, _length * sizeof(DeprecatedChar));
338             _unicode = reinterpret_cast<DeprecatedChar *>(_internalBuffer);
339         } else {
340             _unicode = 0;
341         }
342     }
343     if (_ascii == o._internalBuffer) {
344         if (_isAsciiValid) {
345             ASSERT(_length <= WEBCORE_DS_INTERNAL_BUFFER_CHARS);
346             memcpy(_internalBuffer, o._internalBuffer, _length);
347             _internalBuffer[_length] = 0;
348             _ascii = _internalBuffer;
349         } else {
350             _ascii = 0;
351         }
352     }
353
354     // Clean up the other DeprecatedStringData just enough so that it can be destroyed
355     // cleanly. It's not in a good enough state to use, but that's OK. It just
356     // needs to be in a state where ~DeprecatedStringData won't do anything harmful,
357     // and setting these to 0 will do that (preventing any double-free problems).
358     o._unicode = 0;
359     o._ascii = 0;
360 }
361
362 DeprecatedStringData *DeprecatedString::makeSharedNull()
363 {
364     if (!shared_null) {
365         shared_null = new DeprecatedStringData;
366         shared_null->ref();
367         shared_null->_maxAscii = 0;
368         shared_null->_maxUnicode = 0;
369         shared_null->_unicode = (DeprecatedChar *)&shared_null->_internalBuffer[0]; 
370         shared_null->_isUnicodeValid = 1;   
371     }
372     return shared_null;
373 }
374
375 DeprecatedStringData **DeprecatedString::makeSharedNullHandle()
376 {
377     if (!shared_null_handle) {
378         shared_null_handle = allocateHandle();
379         *shared_null_handle = makeSharedNull();
380     }
381     return shared_null_handle;
382 }
383
384 DeprecatedStringData::~DeprecatedStringData()
385 {
386     ASSERT(refCount == 0);
387     if (_unicode && !isUnicodeInternal())
388         DELETE_QCHAR(_unicode);
389     if (_ascii && !isAsciiInternal())
390         DELETE_CHAR(_ascii);
391 }
392
393 void DeprecatedStringData::increaseAsciiSize(unsigned size)
394 {
395     ASSERT(this != DeprecatedString::shared_null);
396         
397     unsigned newSize = (unsigned)ALLOC_CHAR_GOOD_SIZE((size * 3 + 1) / 2);
398     
399     if (!_isAsciiValid)
400         makeAscii();
401     ASSERT(_isAsciiValid);
402     
403     if (isAsciiInternal()) {
404         char *newAscii = ALLOC_CHAR(newSize);
405         if (_length)
406             memcpy(newAscii, _ascii, _length);
407         _ascii = newAscii;
408     } else {
409         _ascii = REALLOC_CHAR(_ascii, newSize);
410     }
411     
412     _maxAscii = newSize;
413     _isAsciiValid = 1;
414     _isUnicodeValid = 0;
415 }
416
417
418 void DeprecatedStringData::increaseUnicodeSize(unsigned size)
419 {
420     ASSERT(size > _length);
421     ASSERT(this != DeprecatedString::shared_null);
422         
423     unsigned newSize = (unsigned)ALLOC_QCHAR_GOOD_SIZE((size * 3 + 1) / 2);
424     
425     if (!_isUnicodeValid)
426         makeUnicode();
427     ASSERT(_isUnicodeValid);
428
429     if (isUnicodeInternal()) {
430         DeprecatedChar *newUni = WEBCORE_ALLOCATE_CHARACTERS(newSize);
431         if (_length)
432             memcpy(newUni, _unicode, _length*sizeof(DeprecatedChar));
433         _unicode = newUni;
434     } else {
435         _unicode = WEBCORE_REALLOCATE_CHARACTERS(_unicode, newSize);
436     }
437     
438     _maxUnicode = newSize;
439     _isUnicodeValid = 1;
440     _isAsciiValid = 0;
441 }
442
443
444 char *DeprecatedStringData::makeAscii()
445 {
446     ASSERT(this != DeprecatedString::shared_null);
447         
448     if (_isUnicodeValid){
449         DeprecatedChar copyBuf[WEBCORE_DS_INTERNAL_BUFFER_CHARS];
450         DeprecatedChar *str;
451         
452         if (_ascii && !isAsciiInternal())
453             DELETE_QCHAR(_ascii);
454             
455         if (_length < WEBCORE_DS_INTERNAL_BUFFER_CHARS){
456             if (isUnicodeInternal()) {
457                 unsigned i = _length;
458                 DeprecatedChar *tp = &copyBuf[0], *fp = _unicode;
459                 while (i--)
460                     *tp++ = *fp++;
461                 str = &copyBuf[0];
462                 _isUnicodeValid = 0;
463             }
464             else
465                 str = _unicode;
466             _ascii = _internalBuffer;
467             _maxAscii = WEBCORE_DS_INTERNAL_BUFFER_CHARS;
468         }
469         else {
470             unsigned newSize = ALLOC_CHAR_GOOD_SIZE(_length+1);
471             _ascii = ALLOC_CHAR(newSize);
472             _maxAscii = newSize;
473             str = _unicode;
474         }
475
476         unsigned i = _length;
477         char* cp = _ascii;
478         while (i--)
479             *cp++ = (*str++).latin1();
480         *cp = 0;
481         
482         _isAsciiValid = 1;
483     }
484     else if (!_isAsciiValid)
485         FATAL("ASCII character cache not valid");
486         
487     return _ascii;
488 }
489
490
491 DeprecatedChar *DeprecatedStringData::makeUnicode()
492 {
493     ASSERT(this != DeprecatedString::shared_null);
494         
495     if (_isAsciiValid){
496         char copyBuf[WEBCORE_DS_INTERNAL_BUFFER_CHARS];
497         char *str;
498         
499         if (_unicode && !isUnicodeInternal())
500             DELETE_QCHAR(_unicode);
501             
502         if (_length <= WEBCORE_DS_INTERNAL_BUFFER_UCHARS){
503             if (isAsciiInternal()) {
504                 unsigned i = _length;
505                 char *tp = &copyBuf[0], *fp = _ascii;
506                 while (i--)
507                     *tp++ = *fp++;
508                 str = &copyBuf[0];
509                 _isAsciiValid = 0;
510             }
511             else
512                 str = _ascii;
513             _unicode = (DeprecatedChar *)_internalBuffer;
514             _maxUnicode = WEBCORE_DS_INTERNAL_BUFFER_UCHARS;
515         }
516         else {
517             unsigned newSize = ALLOC_QCHAR_GOOD_SIZE(_length);
518             _unicode = WEBCORE_ALLOCATE_CHARACTERS(newSize);
519             _maxUnicode = newSize;
520             str = _ascii;
521         }
522         unsigned i = _length;
523         DeprecatedChar *cp = _unicode;
524         while ( i-- )
525             *cp++ = *str++;
526         
527         _isUnicodeValid = 1;
528     }
529     else if (!_isUnicodeValid)
530         FATAL("invalid character cache");
531
532     return _unicode;
533 }
534
535
536 // -------------------------------------------------------------------------
537 // DeprecatedString
538 // -------------------------------------------------------------------------
539
540
541 DeprecatedString DeprecatedString::number(int n)
542 {
543     DeprecatedString qs;
544     qs.setNum(n);
545     return qs;
546 }
547
548 DeprecatedString DeprecatedString::number(unsigned n)
549 {
550     DeprecatedString qs;
551     qs.setNum(n);
552     return qs;
553 }
554
555 DeprecatedString DeprecatedString::number(long n)
556 {
557     DeprecatedString qs;
558     qs.setNum(n);
559     return qs;
560 }
561
562 DeprecatedString DeprecatedString::number(unsigned long n)
563 {
564     DeprecatedString qs;
565     qs.setNum(n);
566     return qs;
567 }
568
569 DeprecatedString DeprecatedString::number(double n)
570 {
571     DeprecatedString qs;
572     qs.setNum(n);
573     return qs;
574 }
575
576 inline void DeprecatedString::detachIfInternal()
577 {
578     DeprecatedStringData *oldData = *dataHandle;
579     if (oldData->refCount > 1 && oldData == &internalData) {
580         DeprecatedStringData *newData = new DeprecatedStringData(*oldData);
581         newData->_isHeapAllocated = 1;
582         newData->refCount = oldData->refCount;
583         oldData->refCount = 1;
584         oldData->deref();
585         *dataHandle = newData;    
586     }
587 }
588
589 const DeprecatedChar *DeprecatedString::stableUnicode()
590 {
591     // if we're using the internal data of another string, detach now
592     if (!dataHandle[0]->_isHeapAllocated && *dataHandle != &internalData) {
593         detach();
594     }
595     return unicode();
596 }
597
598
599 DeprecatedString::~DeprecatedString()
600 {
601     ASSERT(dataHandle);
602     ASSERT(dataHandle[0]->refCount != 0);
603
604     // Only free the handle if no other string has a reference to the
605     // data.  The handle will be freed by the string that has the
606     // last reference to data.
607     bool needToFreeHandle = dataHandle[0]->refCount == 1 && *dataHandle != shared_null;
608
609     // Copy our internal data if necessary, other strings still need it.
610     detachIfInternal();
611     
612     // Remove our reference. This should always be the last reference
613     // if *dataHandle points to our internal DeprecatedStringData. If we just detached,
614     // this will remove the extra ref from the new handle.
615     dataHandle[0]->deref();
616
617     ASSERT(*dataHandle != &internalData || dataHandle[0]->refCount == 0);
618     
619     if (needToFreeHandle)
620         freeHandle(dataHandle);
621
622 #ifndef NDEBUG
623     dataHandle = 0;
624 #endif
625 }
626
627
628 DeprecatedString::DeprecatedString()
629 {
630     internalData.deref();
631     dataHandle = makeSharedNullHandle();
632     dataHandle[0]->ref();
633 }
634
635
636 // Careful, just used by DeprecatedConstString
637 DeprecatedString::DeprecatedString(DeprecatedStringData *constData, bool /*dummy*/) 
638 {
639     internalData.deref();
640     dataHandle = allocateHandle();
641     *dataHandle = constData;
642     
643     // The DeprecatedConstString constructor allocated the DeprecatedStringData.
644     constData->_isHeapAllocated = 1;
645 }
646
647
648 DeprecatedString::DeprecatedString(DeprecatedChar qc)
649 {
650     dataHandle = allocateHandle();
651
652     // Copy the DeprecatedChar.
653     if (IS_ASCII_QCHAR(qc)) {
654         char c = qc.unicode(); 
655         *dataHandle = &internalData;
656         internalData.initialize( &c, 1 );
657     }
658     else {
659         *dataHandle = &internalData;
660         internalData.initialize( &qc, 1 );
661     }
662 }
663
664 DeprecatedString::DeprecatedString(const DeprecatedChar *unicode, unsigned length)
665 {
666     if (!unicode && !length) {
667         internalData.deref();
668         dataHandle = makeSharedNullHandle();
669         dataHandle[0]->ref();
670     } else {
671         dataHandle = allocateHandle();
672
673         // Copy the DeprecatedChar *
674         *dataHandle = &internalData;
675         internalData.initialize(unicode, length);
676     }
677 }
678
679 DeprecatedString::DeprecatedString(const char *chs)
680 {
681     if (chs) {
682         internalData.initialize(chs,strlen(chs));
683         dataHandle = allocateHandle();
684         *dataHandle = &internalData;
685     } else {
686         internalData.deref();
687         dataHandle = makeSharedNullHandle();
688         dataHandle[0]->ref();
689     }
690 }
691
692 DeprecatedString::DeprecatedString(const char *chs, int len)
693 {
694     dataHandle = allocateHandle();
695     *dataHandle = &internalData;
696     internalData.initialize(chs,len);
697 }
698
699 DeprecatedString::DeprecatedString(const DeprecatedString &qs) : dataHandle(qs.dataHandle)
700 {
701     internalData.deref();
702     dataHandle[0]->ref();
703 }
704
705 DeprecatedString &DeprecatedString::operator=(const DeprecatedString &qs)
706 {
707     if (this == &qs)
708         return *this;
709
710     // Free our handle if it isn't the shared null handle, and if no-one else is using it.
711     bool needToFreeHandle = dataHandle != shared_null_handle && dataHandle[0]->refCount == 1;
712     
713     qs.dataHandle[0]->ref();
714     deref();
715     
716     if (needToFreeHandle)
717         freeHandle(dataHandle);
718         
719     dataHandle = qs.dataHandle;
720
721     return *this;
722 }
723
724 DeprecatedString &DeprecatedString::operator=(const DeprecatedCString &qcs)
725 {
726     return setLatin1(qcs);
727 }
728
729 DeprecatedString &DeprecatedString::operator=(const char *chs)
730 {
731     return setLatin1(chs);
732 }
733
734 DeprecatedString &DeprecatedString::operator=(DeprecatedChar qc)
735 {
736     return *this = DeprecatedString(qc);
737 }
738
739 DeprecatedString &DeprecatedString::operator=(char ch)
740 {
741     return *this = DeprecatedString(DeprecatedChar(ch));
742 }
743
744 DeprecatedChar DeprecatedString::at(unsigned i) const
745 {
746     DeprecatedStringData *thisData = *dataHandle;
747     
748     if (i >= thisData->_length)
749         return 0;
750         
751     if (thisData->_isAsciiValid) {
752         return thisData->_ascii[i];
753     }
754     
755     ASSERT(thisData->_isUnicodeValid);
756     return thisData->_unicode[i];
757 }
758
759 int DeprecatedString::compare(const DeprecatedString& s) const
760 {
761     if (dataHandle[0]->_isAsciiValid && s.dataHandle[0]->_isAsciiValid)
762         return strcmp(ascii(), s.ascii());
763     return ucstrcmp(*this,s);
764 }
765
766 int DeprecatedString::compare(const char *chs) const
767 {
768     if (!chs)
769         return isEmpty() ? 0 : 1;
770     DeprecatedStringData *d = dataHandle[0];
771     if (d->_isAsciiValid)
772         return strcmp(ascii(), chs);
773     const DeprecatedChar *s = unicode();
774     unsigned len = d->_length;
775     for (unsigned i = 0; i != len; ++i) {
776         char c2 = chs[i];
777         if (!c2)
778             return 1;
779         DeprecatedChar c1 = s[i];
780         if (c1.unicode() < c2)
781             return -1;
782         if (c1.unicode() > c2)
783             return 1;
784     }
785     return chs[len] ? -1 : 0;
786 }
787
788 bool DeprecatedString::startsWith( const DeprecatedString& s ) const
789 {
790     if (dataHandle[0]->_isAsciiValid){
791         const char *asc = ascii();
792         
793         for ( int i =0; i < (int) s.dataHandle[0]->_length; i++ ) {
794             if ( i >= (int) dataHandle[0]->_length || asc[i] != s[i] )
795                 return false;
796         }
797     }
798     else if (dataHandle[0]->_isUnicodeValid){
799         const DeprecatedChar *uni = unicode();
800         
801         for ( int i =0; i < (int) s.dataHandle[0]->_length; i++ ) {
802             if ( i >= (int) dataHandle[0]->_length || uni[i] != s[i] )
803                 return false;
804         }
805     }
806     else
807         FATAL("invalid character cache");
808         
809     return true;
810 }
811
812 bool DeprecatedString::startsWith(const char *prefix) const
813 {
814     DeprecatedStringData *data = *dataHandle;
815
816     unsigned prefixLength = strlen(prefix);
817     if (data->_isAsciiValid) {
818         return strncmp(prefix, data->_ascii, prefixLength) == 0;
819     } else {
820         ASSERT(data->_isUnicodeValid);
821         if (prefixLength > data->_length) {
822             return false;
823         }
824         const DeprecatedChar *uni = data->_unicode;        
825         for (unsigned i = 0; i < prefixLength; ++i) {
826             if (uni[i] != prefix[i]) {
827                 return false;
828             }
829         }
830         return true;
831     }
832 }
833
834 bool DeprecatedString::startsWith(const char *prefix, bool caseSensitive) const
835 {
836     if (caseSensitive) {
837         return startsWith(prefix);
838     }
839
840     DeprecatedStringData *data = *dataHandle;
841
842     unsigned prefixLength = strlen(prefix);
843     if (data->_isAsciiValid) {
844         return strncasecmp(prefix, data->_ascii, prefixLength) == 0;
845     } else {
846         ASSERT(data->_isUnicodeValid);
847         if (prefixLength > data->_length) {
848             return false;
849         }
850         const DeprecatedChar *uni = data->_unicode;        
851         for (unsigned i = 0; i < prefixLength; ++i) {
852             if (!equalCaseInsensitive(uni[i], prefix[i])) {
853                 return false;
854             }
855         }
856         return true;
857     }
858 }
859
860 bool DeprecatedString::endsWith(const DeprecatedString& s) const
861 {
862     const DeprecatedChar *uni = unicode();
863
864     int length = dataHandle[0]->_length;
865     int slength = s.dataHandle[0]->_length;
866     if (length < slength)
867         return false;
868
869     for (int i = length - slength, j = 0; i < length; i++, j++) {
870         if (uni[i] != s[j])
871             return false;
872     }
873
874     return true;
875 }
876
877 bool DeprecatedString::isNull() const
878 {
879     return dataHandle == shared_null_handle;
880 }
881
882 int DeprecatedString::find(DeprecatedChar qc, int index) const
883 {
884     if (dataHandle[0]->_isAsciiValid) {
885         if (!IS_ASCII_QCHAR(qc))
886             return -1;
887         return find(qc.unicode(), index);
888     }
889     return find(DeprecatedString(qc), index, true);
890 }
891
892 int DeprecatedString::find(char ch, int index) const
893 {
894     if (dataHandle[0]->_isAsciiValid){
895         const char *cp = ascii();
896         
897         if ( index < 0 )
898             index += dataHandle[0]->_length;
899         
900         if (index >= (int)dataHandle[0]->_length)
901             return -1;
902             
903         for (int i = index; i < (int)dataHandle[0]->_length; i++)
904             if (cp[i] == ch)
905                 return i;
906     }
907     else if (dataHandle[0]->_isUnicodeValid)
908         return find(DeprecatedChar(ch), index, true);
909     else
910         FATAL("invalid character cache");
911
912     return -1;
913 }
914
915 int DeprecatedString::find(const DeprecatedString &str, int index, bool caseSensitive) const
916 {
917     // FIXME, use the first character algorithm
918     /*
919       We use some weird hashing for efficiency's sake.  Instead of
920       comparing strings, we compare the sum of str with that of
921       a part of this DeprecatedString.  Only if that matches, we call memcmp
922       or ucstrnicmp.
923
924       The hash value of a string is the sum of the cells of its
925       QChars.
926     */
927     if ( index < 0 )
928         index += dataHandle[0]->_length;
929     int lstr = str.dataHandle[0]->_length;
930     int lthis = dataHandle[0]->_length - index;
931     if ( (unsigned)lthis > dataHandle[0]->_length )
932         return -1;
933     int delta = lthis - lstr;
934     if ( delta < 0 )
935         return -1;
936
937     const DeprecatedChar *uthis = unicode() + index;
938     const DeprecatedChar *ustr = str.unicode();
939     unsigned hthis = 0;
940     unsigned hstr = 0;
941     int i;
942     if ( caseSensitive ) {
943         for ( i = 0; i < lstr; i++ ) {
944             hthis += uthis[i].unicode();
945             hstr += ustr[i].unicode();
946         }
947         i = 0;
948         while ( true ) {
949             if ( hthis == hstr && memcmp(uthis + i, ustr, lstr * sizeof(DeprecatedChar)) == 0 )
950                 return index + i;
951             if ( i == delta )
952                 return -1;
953             hthis += uthis[i + lstr].unicode();
954             hthis -= uthis[i].unicode();
955             i++;
956         }
957     } else {
958         for ( i = 0; i < lstr; i++ ) {
959             hthis += tolower(uthis[i].unicode());
960             hstr += tolower(ustr[i].unicode());
961         }
962         i = 0;
963         while ( true ) {
964             if ( hthis == hstr && equalCaseInsensitive(uthis + i, ustr, lstr) )
965                 return index + i;
966             if ( i == delta )
967                 return -1;
968             hthis += tolower(uthis[i + lstr].unicode());
969             hthis -= tolower(uthis[i].unicode());
970             i++;
971         }
972     }
973 }
974
975 // This function should be as fast as possible, every little bit helps.
976 // Our usage patterns are typically small strings.  In time trials
977 // this simplistic algorithm is much faster than Boyer-Moore or hash
978 // based algorithms.
979 int DeprecatedString::find(const char *chs, int index, bool caseSensitive) const
980 {
981     if (!chs || index < 0)
982         return -1;
983
984     DeprecatedStringData *data = *dataHandle;
985
986     int chsLength = strlen(chs);
987     int n = data->_length - index;
988     if (n < 0)
989         return -1;
990     n -= chsLength - 1;
991     if (n <= 0)
992         return -1;
993
994     const char *chsPlusOne = chs + 1;
995     int chsLengthMinusOne = chsLength - 1;
996
997     if (data->_isAsciiValid) {
998         char *ptr = data->_ascii + index - 1;
999         if (caseSensitive) {
1000             char c = *chs;
1001             do {
1002                 if (*++ptr == c && memcmp(ptr + 1, chsPlusOne, chsLengthMinusOne) == 0) {
1003                     return data->_length - chsLength - n + 1;
1004                 }
1005             } while (--n);
1006         } else {
1007             int lc = tolower(*chs);
1008             do {
1009                 if (tolower(*++ptr) == lc && equalCaseInsensitive(ptr + 1, chsPlusOne, chsLengthMinusOne)) {
1010                     return data->_length - chsLength - n + 1;
1011                 }
1012             } while (--n);
1013         }
1014     } else {
1015         ASSERT(data->_isUnicodeValid);
1016
1017         const DeprecatedChar *ptr = data->_unicode + index - 1;
1018         if (caseSensitive) {
1019             DeprecatedChar c = *chs;
1020             do {
1021                 if (*++ptr == c && equal(ptr + 1, chsPlusOne, chsLengthMinusOne)) {
1022                     return data->_length - chsLength - n + 1;
1023                 }
1024             } while (--n);
1025         } else {
1026             int lc = tolower((unsigned char)*chs);
1027             do {
1028                 if (tolower((++ptr)->unicode()) == lc && equalCaseInsensitive(ptr + 1, chsPlusOne, chsLengthMinusOne)) {
1029                     return data->_length - chsLength - n + 1;
1030                 }
1031             } while (--n);
1032         }
1033     }
1034
1035     return -1;
1036 }
1037
1038 int DeprecatedString::find(const RegularExpression &qre, int index) const
1039 {
1040     if ( index < 0 )
1041         index += dataHandle[0]->_length;
1042     return qre.match( *this, index );
1043 }
1044
1045 int DeprecatedString::findRev(char ch, int index) const
1046 {
1047     if (dataHandle[0]->_isAsciiValid){
1048         const char *cp = ascii();
1049         
1050         if (index < 0)
1051             index += dataHandle[0]->_length;
1052         if (index > (int)dataHandle[0]->_length)
1053             return -1;
1054             
1055         for (int i = index; i >= 0; i--) {
1056             if (cp[i] == ch)
1057                 return i;
1058         }
1059     }
1060     else if (dataHandle[0]->_isUnicodeValid)
1061         return findRev(DeprecatedString(DeprecatedChar(ch)), index);
1062     else
1063         FATAL("invalid character cache");
1064
1065     return -1;
1066 }
1067
1068 int DeprecatedString::findRev(const char *chs, int index) const
1069 {
1070     return findRev(DeprecatedString(chs), index);
1071 }
1072
1073 int DeprecatedString::findRev( const DeprecatedString& str, int index, bool cs ) const
1074 {
1075     // FIXME, use the first character algorithm
1076     /*
1077       See DeprecatedString::find() for explanations.
1078     */
1079     int lthis = dataHandle[0]->_length;
1080     if ( index < 0 )
1081         index += lthis;
1082
1083     int lstr = str.dataHandle[0]->_length;
1084     int delta = lthis - lstr;
1085     if ( index < 0 || index > lthis || delta < 0 )
1086         return -1;
1087     if ( index > delta )
1088         index = delta;
1089
1090     const DeprecatedChar *uthis = unicode();
1091     const DeprecatedChar *ustr = str.unicode();
1092     unsigned hthis = 0;
1093     unsigned hstr = 0;
1094     int i;
1095     if ( cs ) {
1096         for ( i = 0; i < lstr; i++ ) {
1097             hthis += uthis[index + i].unicode();
1098             hstr += ustr[i].unicode();
1099         }
1100         i = index;
1101         while ( true ) {
1102             if ( hthis == hstr && memcmp(uthis + i, ustr, lstr * sizeof(DeprecatedChar)) == 0 )
1103                 return i;
1104             if ( i == 0 )
1105                 return -1;
1106             i--;
1107             hthis -= uthis[i + lstr].unicode();
1108             hthis += uthis[i].unicode();
1109         }
1110     } else {
1111         for ( i = 0; i < lstr; i++ ) {
1112             hthis += uthis[index + i].lower().unicode();
1113             hstr += ustr[i].lower().unicode();
1114         }
1115         i = index;
1116         while ( true ) {
1117             if ( hthis == hstr && equalCaseInsensitive(uthis + i, ustr, lstr) )
1118                 return i;
1119             if ( i == 0 )
1120                 return -1;
1121             i--;
1122             hthis -= uthis[i + lstr].lower().unicode();
1123             hthis += uthis[i].lower().unicode();
1124         }
1125     }
1126
1127     // Should never get here.
1128     return -1;
1129 }
1130
1131
1132 int DeprecatedString::contains(DeprecatedChar c, bool cs) const
1133 {
1134     int count = 0;
1135     
1136     DeprecatedStringData *data = *dataHandle;
1137     
1138     if (data->_isAsciiValid) {
1139         if (!IS_ASCII_QCHAR(c))
1140             return 0;
1141         const char *cPtr = data->_ascii;
1142         int n = data->_length;
1143         char ac = c.unicode();
1144         if (cs) {                                       // case sensitive
1145             while (n--)
1146                 count += *cPtr++ == ac;
1147         } else {                                        // case insensitive
1148             int lc = tolower(ac);
1149             while (n--) {
1150                 count += tolower(*cPtr++) == lc;
1151             }
1152         }
1153     } else {
1154         ASSERT(data->_isUnicodeValid);
1155         const DeprecatedChar *uc = data->_unicode;
1156         int n = data->_length;
1157         if (cs) {                                       // case sensitive
1158             while ( n-- )
1159                 count += *uc++ == c;
1160         } else {                                        // case insensitive
1161             int lc = tolower(c.unicode());
1162             while (n--) {
1163                 count += tolower(uc->unicode()) == lc;
1164                 uc++;
1165             }
1166         }
1167     } 
1168
1169     return count;
1170 }
1171
1172 int DeprecatedString::contains(char ch) const
1173 {
1174     return contains(DeprecatedChar(ch), true);
1175 }
1176
1177 int DeprecatedString::contains(const char *str, bool caseSensitive) const
1178 {
1179     if (!str)
1180         return 0;
1181
1182     int len = strlen(str);
1183     char c = *str;
1184
1185     DeprecatedStringData *data = *dataHandle;
1186     int n = data->_length;
1187
1188     n -= len - 1;
1189     if (n <= 0)
1190         return 0;
1191
1192     int count = 0;
1193
1194     if (data->_isAsciiValid) {
1195         const char *p = data->_ascii;
1196         if (caseSensitive) {
1197             do {
1198                 count += *p == c && memcmp(p + 1, str + 1, len - 1) == 0;
1199                 p++;
1200             } while (--n);
1201         } else {
1202             int lc = tolower(c);
1203             do {
1204                 count += tolower(*p) == lc && equalCaseInsensitive(p + 1, str + 1, len - 1);
1205                 p++;
1206             } while (--n);
1207         }
1208     } else {
1209         ASSERT(data->_isUnicodeValid);
1210         const DeprecatedChar *p = data->_unicode;
1211         if (caseSensitive) {
1212             do {
1213                 count += *p == c && equal(p + 1, str + 1, len - 1);
1214                 p++;
1215             } while (--n);
1216         } else {
1217             int lc = tolower(c);
1218             do {
1219                 count += tolower(p->unicode()) == lc && equalCaseInsensitive(p + 1, str + 1, len - 1);
1220                 p++;
1221             } while (--n);
1222         }
1223     }
1224
1225     return count;
1226 }
1227
1228 int DeprecatedString::contains(const DeprecatedString &str, bool caseSensitive) const
1229 {
1230     if (str.isEmpty())
1231         return 0;
1232
1233     const DeprecatedChar *strP = str.unicode();
1234     int len = str.dataHandle[0]->_length;
1235     DeprecatedChar c = *strP;
1236
1237     const DeprecatedChar *p = unicode();
1238     int n = dataHandle[0]->_length;
1239
1240     n -= len - 1;
1241     if (n <= 0)
1242         return 0;
1243
1244     int count = 0;
1245
1246     if (caseSensitive) {
1247         int byteCount = len * sizeof(DeprecatedChar);
1248         do {
1249             count += *p == c && memcmp(p, strP, byteCount) == 0;
1250             ++p;
1251         } while (--n);
1252     } else {
1253         do {
1254             count += p->lower() == c && equalCaseInsensitive(p, strP, len) == 0;
1255             ++p;
1256         } while (--n);
1257     }
1258
1259     return count;
1260 }
1261
1262 bool DeprecatedString::isAllASCII() const
1263 {
1264     DeprecatedStringData *data = *dataHandle;
1265
1266     int n = data->_length;
1267     if (data->_isAsciiValid) {
1268         const char *p = data->_ascii;
1269         while (n--) {
1270             unsigned char c = *p++;
1271             if (c > 0x7F) {
1272                 return false;
1273             }
1274         }
1275     } else {
1276         ASSERT(data->_isUnicodeValid);
1277         const DeprecatedChar *p = data->_unicode;
1278         while (n--) {
1279             if ((*p++).unicode() > 0x7F) {
1280                 return false;
1281             }
1282         }
1283     }
1284
1285     return true;
1286 }
1287
1288 bool DeprecatedString::isAllLatin1() const
1289 {
1290     DeprecatedStringData *data = *dataHandle;
1291
1292     if (data->_isAsciiValid) {
1293         return true;
1294     }
1295
1296     ASSERT(data->_isUnicodeValid);
1297     int n = data->_length;
1298     const DeprecatedChar *p = data->_unicode;
1299     while (n--) {
1300         if ((*p++).unicode() > 0xFF) {
1301             return false;
1302         }
1303     }
1304
1305     return true;
1306 }
1307
1308 bool DeprecatedString::hasFastLatin1() const
1309 {
1310     DeprecatedStringData *data = *dataHandle;
1311     return data->_isAsciiValid;
1312 }
1313
1314 void DeprecatedString::copyLatin1(char *buffer, unsigned position, unsigned maxLength) const
1315 {
1316     DeprecatedStringData *data = *dataHandle;
1317
1318     int length = data->_length;
1319     if (position > static_cast<unsigned>(length))
1320         length = 0;
1321     else
1322         length -= position;
1323     if (static_cast<unsigned>(length) > maxLength)
1324         length = static_cast<int>(maxLength);
1325
1326     buffer[length] = 0;
1327
1328     if (data->_isAsciiValid) {
1329         memcpy(buffer, data->_ascii + position, length);
1330         return;
1331     }
1332
1333     ASSERT(data->_isUnicodeValid);
1334     const DeprecatedChar* uc = data->_unicode + position;
1335     while (length--)
1336         *buffer++ = (*uc++).latin1();
1337 }
1338
1339 short DeprecatedString::toShort(bool *ok, int base) const
1340 {
1341     int v = toInt(ok, base);
1342     short sv = v;
1343     if (sv != v) {
1344         if (ok)
1345             *ok = false;
1346         return 0;
1347     }
1348     return sv;
1349 }
1350
1351 unsigned short DeprecatedString::toUShort(bool *ok, int base) const
1352 {
1353     unsigned v = toUInt(ok, base);
1354     unsigned short sv = v;
1355     if (sv != v) {
1356         if (ok)
1357             *ok = false;
1358         return 0;
1359     }
1360     return sv;
1361 }
1362
1363 int DeprecatedString::toInt(bool *ok, int base) const
1364 {
1365     const DeprecatedChar *p = unicode();
1366     int val=0;
1367     int l = dataHandle[0]->_length;
1368     const int max_mult = INT_MAX / base;
1369     bool is_ok = false;
1370     int neg = 0;
1371     if ( !p )
1372         goto bye;
1373     while ( l && p->isSpace() )                 // skip leading space
1374         l--,p++;
1375     if ( l && *p == '-' ) {
1376         l--;
1377         p++;
1378         neg = 1;
1379     } else if ( *p == '+' ) {
1380         l--;
1381         p++;
1382     }
1383
1384     // NOTE: toUInt() code is similar
1385     if ( !l || !ok_in_base(*p,base) )
1386         goto bye;
1387     while ( l && ok_in_base(*p,base) ) {
1388         l--;
1389         int dv;
1390         int c = p->unicode();
1391         if ( isdigit(c) ) {
1392             dv = c - '0';
1393         } else {
1394             if ( c >= 'a' )
1395                 dv = c - 'a' + 10;
1396             else
1397                 dv = c - 'A' + 10;
1398         }
1399         if ( val > max_mult || (val == max_mult && dv > (INT_MAX % base)+neg) )
1400             goto bye;
1401         val = base*val + dv;
1402         p++;
1403     }
1404     if ( neg )
1405         val = -val;
1406     while ( l && p->isSpace() )                 // skip trailing space
1407         l--,p++;
1408     if ( !l )
1409         is_ok = true;
1410 bye:
1411     if ( ok )
1412         *ok = is_ok;
1413     return is_ok ? val : 0;
1414 }
1415
1416 unsigned DeprecatedString::toUInt(bool *ok, int base) const
1417 {
1418     const DeprecatedChar *p = unicode();
1419     unsigned val=0;
1420     int l = dataHandle[0]->_length;
1421     const unsigned max_mult = UINT_MAX / base;
1422     bool is_ok = false;
1423     if ( !p )
1424         goto bye;
1425     while ( l && p->isSpace() )                 // skip leading space
1426         l--,p++;
1427     if ( *p == '+' )
1428         l--,p++;
1429
1430     // NOTE: toInt() code is similar
1431     if ( !l || !ok_in_base(*p,base) )
1432         goto bye;
1433     while ( l && ok_in_base(*p,base) ) {
1434         l--;
1435         unsigned dv;
1436         int c = p->unicode();
1437         if ( isdigit(c) ) {
1438             dv = c - '0';
1439         } else {
1440             if ( c >= 'a' )
1441                 dv = c - 'a' + 10;
1442             else
1443                 dv = c - 'A' + 10;
1444         }
1445         if ( val > max_mult || (val == max_mult && dv > (UINT_MAX % base)) )
1446             goto bye;
1447         val = base*val + dv;
1448         p++;
1449     }
1450
1451     while ( l && p->isSpace() )                 // skip trailing space
1452         l--,p++;
1453     if ( !l )
1454         is_ok = true;
1455 bye:
1456     if ( ok )
1457         *ok = is_ok;
1458     return is_ok ? val : 0;
1459 }
1460
1461 double DeprecatedString::toDouble(bool *ok) const
1462 {
1463     if (isEmpty()) {
1464         if (ok)
1465             *ok = false;
1466         return 0;
1467     }
1468     const char *s = latin1();
1469     char *end;
1470     double val = kjs_strtod(s, &end);
1471     if (ok)
1472         *ok = end == 0 || *end == '\0';
1473     return val;
1474 }
1475
1476 DeprecatedString DeprecatedString::left(unsigned len) const
1477 {
1478     return mid(0, len);
1479 }
1480
1481 DeprecatedString DeprecatedString::right(unsigned len) const
1482 {
1483     return mid(length() - len, len);
1484 }
1485
1486 DeprecatedString DeprecatedString::mid(unsigned start, unsigned len) const
1487 {
1488     if (dataHandle && *dataHandle) {
1489         DeprecatedStringData &data = **dataHandle;
1490         
1491         // clip length
1492         if (start >= data._length)
1493             return DeprecatedString();
1494         
1495         if (len > data._length - start)
1496             len = data._length - start;
1497
1498         if (len == 0)
1499             return DeprecatedString();
1500         
1501         if (start == 0 && len == data._length)
1502             return *this;
1503
1504         ASSERT(start + len >= start &&       // unsigned overflow
1505                start + len <= data._length); // past the end
1506         
1507         // ascii case
1508         if (data._isAsciiValid && data._ascii)
1509             return DeprecatedString(&data._ascii[start] , len);
1510         
1511         // unicode case
1512         if (data._isUnicodeValid && data._unicode)
1513             return DeprecatedString(&data._unicode[start], len);
1514     }
1515     
1516     // degenerate case
1517     return DeprecatedString();
1518 }
1519
1520 DeprecatedString DeprecatedString::copy() const
1521 {
1522     // does not need to be a deep copy
1523     return DeprecatedString(*this);
1524 }
1525
1526 DeprecatedString DeprecatedString::lower() const
1527 {
1528     DeprecatedString s(*this);
1529     DeprecatedStringData *d = *s.dataHandle;
1530     int l = d->_length;
1531     if (l) {
1532         bool detached = false;
1533         if (d->_isAsciiValid) {
1534             char *p = d->_ascii;
1535             while (l--) {
1536                 char c = *p;
1537                 // FIXME: Doesn't work for 0x80-0xFF.
1538                 if (c >= 'A' && c <= 'Z') {
1539                     if (!detached) {
1540                         s.detach();
1541                         d = *s.dataHandle;
1542                         p = d->_ascii + d->_length - l - 1;
1543                         detached = true;
1544                     }
1545                     *p = c + ('a' - 'A');
1546                 }
1547                 p++;
1548             }
1549         }
1550         else {
1551             ASSERT(d->_isUnicodeValid);
1552             DeprecatedChar *p = d->_unicode;
1553             while (l--) {
1554                 DeprecatedChar c = *p;
1555                 // FIXME: Doesn't work for 0x80-0xFF.
1556                 if (IS_ASCII_QCHAR(c)) {
1557                     if (c.unicode() >= 'A' && c.unicode() <= 'Z') {
1558                         if (!detached) {
1559                             s.detach();
1560                             d = *s.dataHandle;
1561                             p = d->_unicode + d->_length - l - 1;
1562                             detached = true;
1563                         }
1564                         *p = c.unicode() + ('a' - 'A');
1565                     }
1566                 } else {
1567                     DeprecatedChar clower = c.lower();
1568                     if (clower != c) {
1569                         if (!detached) {
1570                             s.detach();
1571                             d = *s.dataHandle;
1572                             p = d->_unicode + d->_length - l - 1;
1573                             detached = true;
1574                         }
1575                         *p = clower;
1576                     }
1577                 }
1578                 p++;
1579             }
1580         }
1581     }
1582     return s;
1583 }
1584
1585 DeprecatedString DeprecatedString::stripWhiteSpace() const
1586 {
1587     if ( isEmpty() )                            // nothing to do
1588         return *this;
1589     if ( !at(0).isSpace() && !at(dataHandle[0]->_length-1).isSpace() )
1590         return *this;
1591
1592     int start = 0;
1593     int end = dataHandle[0]->_length - 1;
1594
1595     DeprecatedString result = fromLatin1("");
1596     while ( start<=end && at(start).isSpace() ) // skip white space from start
1597         start++;
1598     if ( start > end ) {                        // only white space
1599         return result;
1600     }
1601     while ( end && at(end).isSpace() )          // skip white space from end
1602         end--;
1603     int l = end - start + 1;
1604     
1605     if (dataHandle[0]->_isAsciiValid){
1606         result.setLength( l );
1607         if ( l )
1608             memcpy(const_cast<char*>(result.dataHandle[0]->ascii()), &ascii()[start], l );
1609     }
1610     else if (dataHandle[0]->_isUnicodeValid){
1611         result.setLength( l );
1612         if ( l )
1613             memcpy(result.forceUnicode(), &unicode()[start], sizeof(DeprecatedChar)*l );
1614     }
1615     else
1616         FATAL("invalid character cache");
1617     return result;
1618 }
1619
1620 DeprecatedString DeprecatedString::simplifyWhiteSpace() const
1621 {
1622     if ( isEmpty() )                            // nothing to do
1623         return *this;
1624     
1625     DeprecatedString result;
1626
1627     if (dataHandle[0]->_isAsciiValid){
1628         result.setLength( dataHandle[0]->_length );
1629         const char *from = ascii();
1630         const char *fromend = from + dataHandle[0]->_length;
1631         int outc=0;
1632         
1633         char *to = const_cast<char*>(result.ascii());
1634         while ( true ) {
1635             while ( from!=fromend && DeprecatedChar(*from).isSpace() )
1636                 from++;
1637             while ( from!=fromend && !DeprecatedChar(*from).isSpace() )
1638                 to[outc++] = *from++;
1639             if ( from!=fromend )
1640                 to[outc++] = ' ';
1641             else
1642                 break;
1643         }
1644         if ( outc > 0 && to[outc-1] == ' ' )
1645             outc--;
1646         result.truncate( outc );
1647     }
1648     else if (dataHandle[0]->_isUnicodeValid){
1649         result.setLength( dataHandle[0]->_length );
1650         const DeprecatedChar *from = unicode();
1651         const DeprecatedChar *fromend = from + dataHandle[0]->_length;
1652         int outc=0;
1653         
1654         DeprecatedChar *to = result.forceUnicode();
1655         while ( true ) {
1656             while ( from!=fromend && from->isSpace() )
1657                 from++;
1658             while ( from!=fromend && !from->isSpace() )
1659                 to[outc++] = *from++;
1660             if ( from!=fromend )
1661                 to[outc++] = ' ';
1662             else
1663                 break;
1664         }
1665         if ( outc > 0 && to[outc-1] == ' ' )
1666             outc--;
1667         result.truncate( outc );
1668     }
1669     else
1670         FATAL("invalid character cache");
1671     
1672     return result;
1673 }
1674
1675 void DeprecatedString::deref()
1676 {
1677     dataHandle[0]->deref();
1678 }
1679
1680
1681 DeprecatedString &DeprecatedString::setUnicode(const DeprecatedChar *uni, unsigned len)
1682 {
1683     detachAndDiscardCharacters();
1684     
1685     // Free our handle if it isn't the shared null handle, and if no-one else is using it.
1686     bool needToFreeHandle = dataHandle != shared_null_handle && dataHandle[0]->refCount == 1;
1687         
1688     if (len == 0) {
1689         deref();
1690         if (needToFreeHandle)
1691             freeHandle(dataHandle);
1692         dataHandle = makeSharedNullHandle();
1693         dataHandle[0]->ref();
1694     } else if (len > dataHandle[0]->_maxUnicode || dataHandle[0]->refCount != 1 || !dataHandle[0]->_isUnicodeValid) {
1695         deref();
1696         if (needToFreeHandle)
1697             freeHandle(dataHandle);
1698         dataHandle = allocateHandle();
1699         *dataHandle = new DeprecatedStringData(uni, len);
1700         dataHandle[0]->_isHeapAllocated = 1;
1701     } else {
1702         if ( uni )
1703             memcpy( (void *)unicode(), uni, sizeof(DeprecatedChar)*len );
1704         dataHandle[0]->_length = len;
1705         dataHandle[0]->_isAsciiValid = 0;
1706     }
1707     
1708     return *this;
1709 }
1710
1711
1712 DeprecatedString &DeprecatedString::setLatin1(const char *str, int len)
1713 {
1714     if ( str == 0 )
1715         return setUnicode(0,0);
1716     if ( len < 0 )
1717         len = strlen(str);
1718
1719     detachAndDiscardCharacters();
1720     
1721     // Free our handle if it isn't the shared null handle, and if no-one else is using it.
1722     bool needToFreeHandle = dataHandle != shared_null_handle && dataHandle[0]->refCount == 1;
1723    
1724     if (len+1 > (int)dataHandle[0]->_maxAscii || dataHandle[0]->refCount != 1 || !dataHandle[0]->_isAsciiValid) {
1725         deref();
1726         if (needToFreeHandle)
1727             freeHandle(dataHandle);
1728         dataHandle = allocateHandle();
1729         *dataHandle = new DeprecatedStringData(str,len);
1730         dataHandle[0]->_isHeapAllocated = 1;
1731     } else {
1732         strcpy(const_cast<char*>(ascii()), str );
1733         dataHandle[0]->_length = len;
1734         dataHandle[0]->_isUnicodeValid = 0;
1735     }
1736     return *this;
1737 }
1738
1739 DeprecatedString &DeprecatedString::setNum(short n)
1740 {
1741     return format("%d", n);
1742 }
1743
1744 DeprecatedString &DeprecatedString::setNum(unsigned short n)
1745 {
1746     return format("%u", n);
1747 }
1748
1749 DeprecatedString &DeprecatedString::setNum(int n)
1750 {
1751     return format("%d", n);
1752 }
1753
1754 DeprecatedString &DeprecatedString::setNum(unsigned n)
1755 {
1756     return format("%u", n);
1757 }
1758
1759 DeprecatedString &DeprecatedString::setNum(long n)
1760 {
1761     return format("%ld", n);
1762 }
1763
1764 DeprecatedString &DeprecatedString::setNum(unsigned long n)
1765 {
1766     return format("%lu", n);
1767 }
1768
1769 DeprecatedString &DeprecatedString::setNum(double n)
1770 {
1771     return format("%.6lg", n);
1772 }
1773
1774 DeprecatedString &DeprecatedString::format(const char *format, ...)
1775 {
1776     // FIXME: this needs the same windows compat fixes as String::format
1777
1778     va_list args;
1779     va_start(args, format);
1780     
1781     // Do the format once to get the length.
1782 #if PLATFORM(WIN_OS) 
1783     int result = _vscprintf(format, args);
1784 #else
1785     char ch;
1786     int result = vsnprintf(&ch, 1, format, args);
1787 #endif
1788     
1789     // Handle the empty string case to simplify the code below.
1790     if (result <= 0) { // POSIX returns 0 in error; Windows returns a negative number.
1791         setUnicode(0, 0);
1792         return *this;
1793     }
1794     unsigned len = result;
1795     
1796     // Arrange for storage for the resulting string.
1797     detachAndDiscardCharacters();
1798     if (len >= dataHandle[0]->_maxAscii || dataHandle[0]->refCount != 1 || !dataHandle[0]->_isAsciiValid) {
1799         // Free our handle if it isn't the shared null handle, and if no-one else is using it.
1800         bool needToFreeHandle = dataHandle != shared_null_handle && dataHandle[0]->refCount == 1;
1801         deref();
1802         if (needToFreeHandle)
1803             freeHandle(dataHandle);
1804         dataHandle = allocateHandle();
1805         *dataHandle = new DeprecatedStringData((char *)0, len);
1806         dataHandle[0]->_isHeapAllocated = 1;
1807     } else {
1808         dataHandle[0]->_length = len;
1809         dataHandle[0]->_isUnicodeValid = 0;
1810     }
1811
1812     // Now do the formatting again, guaranteed to fit.
1813     vsprintf(const_cast<char*>(ascii()), format, args);
1814
1815     va_end(args);
1816     return *this;
1817 }
1818
1819 DeprecatedString &DeprecatedString::prepend(const DeprecatedString &qs)
1820 {
1821     return insert(0, qs);
1822 }
1823
1824 DeprecatedString &DeprecatedString::prepend(const DeprecatedChar *characters, unsigned length)
1825 {
1826     return insert(0, characters, length);
1827 }
1828
1829 DeprecatedString &DeprecatedString::append(const DeprecatedString &qs)
1830 {
1831     return insert(dataHandle[0]->_length, qs);
1832 }
1833
1834 DeprecatedString &DeprecatedString::append(const char *characters, unsigned length)
1835 {
1836     return insert(dataHandle[0]->_length, characters, length);
1837 }
1838
1839 DeprecatedString &DeprecatedString::append(const DeprecatedChar *characters, unsigned length)
1840 {
1841     return insert(dataHandle[0]->_length, characters, length);
1842 }
1843
1844 DeprecatedString &DeprecatedString::insert(unsigned index, const char *insertChars, unsigned insertLength)
1845 {
1846     if (insertLength == 0)
1847         return *this;
1848         
1849     detach();
1850     
1851     if (dataHandle[0]->_isAsciiValid){
1852         unsigned originalLength = dataHandle[0]->_length;
1853         char *targetChars;
1854         
1855         // Ensure that we have enough space.
1856         setLength (originalLength + insertLength);
1857         targetChars = const_cast<char*>(ascii());
1858         
1859         // Move tail to make space for inserted characters.
1860         memmove (targetChars+index+insertLength, targetChars+index, originalLength-index);
1861         
1862         // Insert characters.
1863         memcpy (targetChars+index, insertChars, insertLength);
1864         
1865         dataHandle[0]->_isUnicodeValid = 0;
1866     }
1867     else if (dataHandle[0]->_isUnicodeValid){
1868         unsigned originalLength = dataHandle[0]->_length;
1869         DeprecatedChar *targetChars;
1870         
1871         // Ensure that we have enough space.
1872         setLength (originalLength + insertLength);
1873         targetChars = (DeprecatedChar *)unicode();
1874         
1875         // Move tail to make space for inserted characters.
1876         memmove (targetChars+(index+insertLength), targetChars+index, (originalLength-index)*sizeof(DeprecatedChar));
1877
1878         // Insert characters.
1879         unsigned i = insertLength;
1880         DeprecatedChar *target = targetChars+index;
1881         
1882         while (i--)
1883             *target++ = *insertChars++;        
1884     }
1885     else
1886         FATAL("invalid character cache");
1887     
1888     return *this;
1889 }
1890
1891
1892 DeprecatedString &DeprecatedString::insert(unsigned index, const DeprecatedString &qs)
1893 {
1894     if (qs.dataHandle[0]->_length == 0)
1895         return *this;
1896         
1897     if (dataHandle[0]->_isAsciiValid && qs.isAllLatin1()) {
1898         insert(index, qs.latin1(), qs.length());
1899     }
1900     else {
1901         unsigned insertLength = qs.dataHandle[0]->_length;
1902         unsigned originalLength = dataHandle[0]->_length;
1903         DeprecatedChar *targetChars;
1904         
1905         // Ensure that we have enough space.
1906         setLength (originalLength + insertLength);
1907         targetChars = forceUnicode();
1908         
1909         // Move tail to make space for inserted characters.
1910         memmove (targetChars+(index+insertLength), targetChars+index, (originalLength-index)*sizeof(DeprecatedChar));
1911
1912         // Insert characters.
1913         if (qs.dataHandle[0]->_isAsciiValid){
1914             unsigned i = insertLength;
1915             DeprecatedChar *target = targetChars+index;
1916             char *a = const_cast<char*>(qs.ascii());
1917             
1918             while (i--)
1919                 *target++ = *a++;
1920         }
1921         else {
1922             DeprecatedChar *insertChars = (DeprecatedChar *)qs.unicode();
1923             memcpy (targetChars+index, insertChars, insertLength*sizeof(DeprecatedChar));
1924         }
1925         
1926         dataHandle[0]->_isAsciiValid = 0;
1927     }
1928     
1929     return *this;
1930 }
1931
1932
1933 DeprecatedString &DeprecatedString::insert(unsigned index, const DeprecatedChar *insertChars, unsigned insertLength)
1934 {
1935     if (insertLength == 0)
1936         return *this;
1937         
1938     forceUnicode();
1939     
1940     unsigned originalLength = dataHandle[0]->_length;
1941     setLength(originalLength + insertLength);
1942
1943     DeprecatedChar *targetChars = const_cast<DeprecatedChar *>(unicode());
1944     if (originalLength > index) {
1945         memmove(targetChars + index + insertLength, targetChars + index, (originalLength - index) * sizeof(DeprecatedChar));
1946     }
1947     memcpy(targetChars + index, insertChars, insertLength * sizeof(DeprecatedChar));
1948     
1949     return *this;
1950 }
1951
1952
1953 DeprecatedString &DeprecatedString::insert(unsigned index, DeprecatedChar qc)
1954 {
1955     detach();
1956     
1957     if (dataHandle[0]->_isAsciiValid && IS_ASCII_QCHAR(qc)){
1958         unsigned originalLength = dataHandle[0]->_length;
1959         char insertChar = qc.unicode();
1960         char *targetChars;
1961         
1962         // Ensure that we have enough space.
1963         setLength (originalLength + 1);
1964         targetChars = const_cast<char*>(ascii());
1965         
1966         // Move tail to make space for inserted character.
1967         memmove (targetChars+index+1, targetChars+index, originalLength-index);
1968         
1969         // Insert character.
1970         targetChars[index] = insertChar;
1971         targetChars[dataHandle[0]->_length] = 0;
1972
1973         dataHandle[0]->_isUnicodeValid = 0;
1974     }
1975     else {
1976         unsigned originalLength = dataHandle[0]->_length;
1977         DeprecatedChar *targetChars;
1978         
1979         // Ensure that we have enough space.
1980         setLength (originalLength + 1);
1981         targetChars = forceUnicode();
1982         
1983         // Move tail to make space for inserted character.
1984         memmove (targetChars+(index+1), targetChars+index, (originalLength-index)*sizeof(DeprecatedChar));
1985
1986         targetChars[index] = qc;
1987     }
1988     
1989     return *this;
1990 }
1991
1992
1993 DeprecatedString &DeprecatedString::insert(unsigned index, char ch)
1994 {
1995     detach();
1996     
1997     if (dataHandle[0]->_isAsciiValid) {
1998         unsigned originalLength = dataHandle[0]->_length;
1999         char *targetChars;
2000         
2001         // Ensure that we have enough space.
2002         setLength (originalLength + 1);
2003         targetChars = const_cast<char*>(ascii());
2004         
2005         // Move tail to make space for inserted character.
2006         memmove (targetChars+index+1, targetChars+index, originalLength-index);
2007         
2008         // Insert character.
2009         targetChars[index] = ch;
2010         targetChars[dataHandle[0]->_length] = 0;
2011
2012         dataHandle[0]->_isUnicodeValid = 0;
2013     }
2014     else if (dataHandle[0]->_isUnicodeValid){
2015         unsigned originalLength = dataHandle[0]->_length;
2016         DeprecatedChar *targetChars;
2017         
2018         // Ensure that we have enough space.
2019         setLength (originalLength + 1);
2020         targetChars = (DeprecatedChar *)unicode();
2021         
2022         // Move tail to make space for inserted character.
2023         memmove (targetChars+(index+1), targetChars+index, (originalLength-index)*sizeof(DeprecatedChar));
2024
2025         targetChars[index] = (DeprecatedChar)ch;
2026     }
2027     else
2028         FATAL("invalid character cache");
2029     
2030     return *this;
2031 }
2032
2033 // Copy DeprecatedStringData if necessary. Must be called before the string data is mutated.
2034 void DeprecatedString::detach()
2035 {
2036     DeprecatedStringData *oldData = *dataHandle;
2037
2038     if (oldData->refCount == 1 && oldData != shared_null)
2039         return;
2040
2041     // Copy data for this string so we can safely mutate it.
2042     DeprecatedStringData *newData;
2043     if (oldData->_isAsciiValid)
2044         newData = new DeprecatedStringData(oldData->ascii(), oldData->_length);
2045     else
2046         newData = new DeprecatedStringData(oldData->unicode(), oldData->_length);
2047     newData->_isHeapAllocated = 1;
2048
2049     // There is now one less client for the old data.
2050     oldData->deref();
2051
2052     // If the old data is our internal data, then we'll keep that.
2053     // This decreases the chance we'll have to do a detachInternal later
2054     // when this object is destroyed.
2055     if (oldData == &internalData) {
2056         newData->refCount = oldData->refCount;
2057         oldData->refCount = 1;
2058         *dataHandle = newData;
2059         newData = oldData;
2060     }
2061
2062     // Create a new handle.
2063     dataHandle = allocateHandle();
2064     *dataHandle = newData;
2065 }
2066
2067 void DeprecatedString::detachAndDiscardCharacters()
2068 {
2069     // Missing optimization: Don't bother copying the old data if we detach.
2070     detach();
2071 }
2072
2073 DeprecatedString &DeprecatedString::remove(unsigned index, unsigned len)
2074 {
2075     unsigned olen = dataHandle[0]->_length;
2076     if ( index >= olen  ) {
2077         // range problems
2078     } else if ( index + len >= olen ) {  // index ok
2079         setLength( index );
2080     } else if ( len != 0 ) {
2081         // Missing optimization: Could avoid copying characters we are going to remove
2082         // by making a special version of detach().
2083
2084         detach();
2085         
2086         if (dataHandle[0]->_isAsciiValid){
2087             memmove( dataHandle[0]->ascii()+index, dataHandle[0]->ascii()+index+len,
2088                     sizeof(char)*(olen-index-len) );
2089             setLength( olen-len );
2090             dataHandle[0]->_isUnicodeValid = 0;
2091         }
2092         else if (dataHandle[0]->_isUnicodeValid){
2093             memmove( dataHandle[0]->unicode()+index, dataHandle[0]->unicode()+index+len,
2094                     sizeof(DeprecatedChar)*(olen-index-len) );
2095             setLength( olen-len );
2096         }
2097         else
2098             FATAL("invalid character cache");
2099     }
2100     return *this;
2101 }
2102
2103 DeprecatedString &DeprecatedString::replace(unsigned index, unsigned len, const DeprecatedString& str)
2104 {
2105     return remove(index, len).insert(index, str);
2106 }
2107
2108 DeprecatedString &DeprecatedString::replace(char pattern, const DeprecatedString &str)
2109 {
2110     int slen = str.dataHandle[0]->_length;
2111     int index = 0;
2112     while ((index = find(pattern, index)) >= 0) {
2113         replace(index, 1, str);
2114         index += slen;
2115     }
2116     return *this;
2117 }
2118
2119 DeprecatedString &DeprecatedString::replace(DeprecatedChar pattern, const DeprecatedString &str)
2120 {
2121     int slen = str.dataHandle[0]->_length;
2122     int index = 0;
2123     while ((index = find(pattern, index)) >= 0) {
2124         replace(index, 1, str);
2125         index += slen;
2126     }
2127     return *this;
2128 }
2129
2130 DeprecatedString &DeprecatedString::replace(const DeprecatedString &pattern, const DeprecatedString &str)
2131 {
2132     if (pattern.isEmpty())
2133         return *this;
2134     int plen = pattern.dataHandle[0]->_length;
2135     int slen = str.dataHandle[0]->_length;
2136     int index = 0;
2137     while ((index = find(pattern, index)) >= 0) {
2138         replace(index, plen, str);
2139         index += slen;
2140     }
2141     return *this;
2142 }
2143
2144
2145 DeprecatedString &DeprecatedString::replace(const RegularExpression &qre, const DeprecatedString &str)
2146 {
2147     if ( isEmpty() )
2148         return *this;
2149     int index = 0;
2150     int slen  = str.dataHandle[0]->_length;
2151     int len;
2152     while ( index < (int)dataHandle[0]->_length ) {
2153         index = qre.match( *this, index, &len);
2154         if ( index >= 0 ) {
2155             replace( index, len, str );
2156             index += slen;
2157             if ( !len )
2158                 break;  // Avoid infinite loop on 0-length matches, e.g. [a-z]*
2159         }
2160         else
2161             break;
2162     }
2163     return *this;
2164 }
2165
2166
2167 DeprecatedString &DeprecatedString::replace(DeprecatedChar oldChar, DeprecatedChar newChar)
2168 {
2169     if (oldChar != newChar && find(oldChar) != -1) {
2170         unsigned length = dataHandle[0]->_length;
2171         
2172         detach();
2173         if (dataHandle[0]->_isAsciiValid && IS_ASCII_QCHAR(newChar)) {
2174             char *p = const_cast<char *>(ascii());
2175             dataHandle[0]->_isUnicodeValid = 0;
2176             char oldC = oldChar.unicode();
2177             char newC = newChar.unicode();
2178             for (unsigned i = 0; i != length; ++i) {
2179                 if (p[i] == oldC) {
2180                     p[i] = newC;
2181                 }
2182             }
2183         } else {
2184             DeprecatedChar *p = const_cast<DeprecatedChar *>(unicode());
2185             dataHandle[0]->_isAsciiValid = 0;
2186             for (unsigned i = 0; i != length; ++i) {
2187                 if (p[i] == oldChar) {
2188                     p[i] = newChar;
2189                 }
2190             }
2191         }
2192     }
2193     
2194     return *this;
2195 }
2196
2197
2198 DeprecatedChar *DeprecatedString::forceUnicode()
2199 {
2200     detach();
2201     DeprecatedChar *result = const_cast<DeprecatedChar *>(unicode());
2202     dataHandle[0]->_isAsciiValid = 0;
2203     return result;
2204 }
2205
2206
2207 // Increase buffer size if necessary.  Newly allocated
2208 // bytes will contain garbage.
2209 void DeprecatedString::setLength(unsigned newLen)
2210 {
2211     if (newLen == 0) {
2212         setUnicode(0, 0);
2213         return;
2214     }
2215
2216     // Missing optimization: Could avoid copying characters we are going to remove
2217     // by making a special version of detach().
2218     detach();
2219
2220     ASSERT(dataHandle != shared_null_handle);
2221     
2222     if (dataHandle[0]->_isAsciiValid){
2223         if (newLen+1 > dataHandle[0]->_maxAscii) {
2224             dataHandle[0]->increaseAsciiSize(newLen+1);
2225         }
2226         // Ensure null termination, although newly allocated
2227         // bytes contain garbage.
2228         dataHandle[0]->_ascii[newLen] = 0;
2229     }
2230     else if (dataHandle[0]->_isUnicodeValid){
2231         if (newLen > dataHandle[0]->_maxUnicode) {
2232             dataHandle[0]->increaseUnicodeSize(newLen);
2233         }
2234     }
2235     else
2236         FATAL("invalid character cache");
2237
2238     dataHandle[0]->_length = newLen;
2239 }
2240
2241
2242 void DeprecatedString::truncate(unsigned newLen)
2243 {
2244     if ( newLen < dataHandle[0]->_length )
2245         setLength( newLen );
2246 }
2247
2248 void DeprecatedString::fill(DeprecatedChar qc, int len)
2249 {
2250     detachAndDiscardCharacters();
2251     
2252     // len == -1 means fill to string length.
2253     if (len < 0) {
2254         len = dataHandle[0]->_length;
2255     }
2256         
2257     if (len == 0) {
2258         if (dataHandle != shared_null_handle) {
2259             ASSERT(dataHandle[0]->refCount == 1);
2260             deref();
2261             freeHandle(dataHandle);
2262             dataHandle = makeSharedNullHandle();
2263             shared_null->ref();
2264         }
2265     } else {
2266         if (dataHandle[0]->_isAsciiValid && IS_ASCII_QCHAR(qc)) {
2267             setLength(len);
2268             char *nd = const_cast<char*>(ascii());
2269             while (len--) 
2270                 *nd++ = qc.unicode();
2271             dataHandle[0]->_isUnicodeValid = 0;
2272         } else {
2273             setLength(len);
2274             DeprecatedChar *nd = forceUnicode();
2275             while (len--) 
2276                 *nd++ = qc;
2277         }
2278     }
2279 }
2280
2281 DeprecatedString &DeprecatedString::append(DeprecatedChar qc)
2282 {
2283     detach();
2284     
2285     DeprecatedStringData *thisData = *dataHandle;
2286     if (thisData->_isUnicodeValid && thisData->_length + 1 < thisData->_maxUnicode){
2287         thisData->_unicode[thisData->_length] = qc;
2288         thisData->_length++;
2289         thisData->_isAsciiValid = 0;
2290         return *this;
2291     }
2292     else if (thisData->_isAsciiValid && IS_ASCII_QCHAR(qc) && thisData->_length + 2 < thisData->_maxAscii){
2293         thisData->_ascii[thisData->_length] = qc.unicode();
2294         thisData->_length++;
2295         thisData->_ascii[thisData->_length] = 0;
2296         thisData->_isUnicodeValid = 0;
2297         return *this;
2298     }
2299     return insert(thisData->_length, qc);
2300 }
2301
2302 DeprecatedString &DeprecatedString::append(char ch)
2303 {
2304     detach();
2305     
2306     DeprecatedStringData *thisData = *dataHandle;
2307     if (thisData->_isUnicodeValid && thisData->_length + 1 < thisData->_maxUnicode){
2308         thisData->_unicode[thisData->_length] = (DeprecatedChar)ch;
2309         thisData->_length++;
2310         thisData->_isAsciiValid = 0;
2311         return *this;
2312     }
2313     else if (thisData->_isAsciiValid && thisData->_length + 2 < thisData->_maxAscii){
2314         thisData->_ascii[thisData->_length] = ch;
2315         thisData->_length++;
2316         thisData->_ascii[thisData->_length] = 0;
2317         thisData->_isUnicodeValid = 0;
2318         return *this;
2319     }
2320     return insert(thisData->_length, ch);
2321 }
2322
2323 void DeprecatedString::reserve(unsigned length)
2324 {
2325     if (length > dataHandle[0]->_maxUnicode) {
2326         detach();
2327         dataHandle[0]->increaseUnicodeSize(length);
2328     }
2329 }
2330
2331 bool operator==(const DeprecatedString &s1, const DeprecatedString &s2)
2332 {
2333     if (s1.dataHandle[0]->_isAsciiValid && s2.dataHandle[0]->_isAsciiValid) {
2334         return strcmp(s1.ascii(), s2.ascii()) == 0;
2335     }
2336     return s1.dataHandle[0]->_length == s2.dataHandle[0]->_length
2337         && memcmp(s1.unicode(), s2.unicode(), s1.dataHandle[0]->_length * sizeof(DeprecatedChar)) == 0;
2338 }
2339
2340 bool operator==(const DeprecatedString &s1, const char *chs)
2341 {
2342     if (!chs)
2343         return s1.isNull();
2344     DeprecatedStringData *d = s1.dataHandle[0];
2345     unsigned len = d->_length;
2346     if (d->_isAsciiValid) {
2347         const char *s = s1.ascii();
2348         for (unsigned i = 0; i != len; ++i) {
2349             char c = chs[i];
2350             if (!c || s[i] != c)
2351                 return false;
2352         }
2353     } else {
2354         const DeprecatedChar *s = s1.unicode();
2355         for (unsigned i = 0; i != len; ++i) {
2356             char c = chs[i];
2357             if (!c || s[i] != c)
2358                 return false;
2359         }
2360     }
2361     return chs[len] == '\0';
2362 }
2363
2364 DeprecatedString operator+(const DeprecatedString &qs1, const DeprecatedString &qs2)
2365 {
2366     return DeprecatedString(qs1) += qs2;
2367 }
2368
2369 DeprecatedString operator+(const DeprecatedString &qs, const char *chs)
2370 {
2371     return DeprecatedString(qs) += chs;
2372 }
2373
2374 DeprecatedString operator+(const DeprecatedString &qs, DeprecatedChar qc)
2375 {
2376     return DeprecatedString(qs) += qc;
2377 }
2378
2379 DeprecatedString operator+(const DeprecatedString &qs, char ch)
2380 {
2381     return DeprecatedString(qs) += ch;
2382 }
2383
2384 DeprecatedString operator+(const char *chs, const DeprecatedString &qs)
2385 {
2386     return DeprecatedString(chs) += qs;
2387 }
2388
2389 DeprecatedString operator+(DeprecatedChar qc, const DeprecatedString &qs)
2390 {
2391     return DeprecatedString(qc) += qs;
2392 }
2393
2394 DeprecatedString operator+(char ch, const DeprecatedString &qs)
2395 {
2396     return DeprecatedString(DeprecatedChar(ch)) += qs;
2397 }
2398
2399 DeprecatedConstString::DeprecatedConstString(const DeprecatedChar* unicode, unsigned length) :
2400     DeprecatedString(new DeprecatedStringData((DeprecatedChar *)unicode, length, length), true)
2401 {
2402 }
2403
2404 DeprecatedConstString::~DeprecatedConstString()
2405 {
2406     DeprecatedStringData *data = *dataHandle;
2407     if (data->refCount > 1) {
2408         DeprecatedChar *tp;
2409         if (data->_length <= WEBCORE_DS_INTERNAL_BUFFER_UCHARS) {
2410             data->_maxUnicode = WEBCORE_DS_INTERNAL_BUFFER_UCHARS;
2411             tp = (DeprecatedChar *)&data->_internalBuffer[0];
2412         } else {
2413             data->_maxUnicode = ALLOC_QCHAR_GOOD_SIZE(data->_length);
2414             tp = WEBCORE_ALLOCATE_CHARACTERS(data->_maxUnicode);
2415         }
2416         memcpy(tp, data->_unicode, data->_length * sizeof(DeprecatedChar));
2417         data->_unicode = tp;
2418         data->_isUnicodeValid = 1;
2419         data->_isAsciiValid = 0;
2420     } else {
2421         data->_unicode = 0;
2422     }
2423 }
2424
2425 struct HandlePageNode
2426 {
2427     HandlePageNode *next;
2428     HandlePageNode *previous;
2429     void *nodes;
2430 };
2431
2432 struct HandleNode {
2433     union {
2434         struct {
2435             unsigned short next;
2436             unsigned short previous;
2437         } internalNode;
2438         
2439         HandleNode *freeNodes;  // Always at block[0] in page.
2440         
2441         HandlePageNode *pageNode;   // Always at block[1] in page
2442         
2443         void *handle;
2444     } type;
2445 };
2446
2447 static const size_t pageSize = 4096;
2448 static const uintptr_t pageMask = ~(pageSize - 1);
2449 static const size_t nodeBlockSize = pageSize / sizeof(HandleNode);
2450
2451 static HandleNode *initializeHandleNodeBlock(HandlePageNode *pageNode)
2452 {
2453     unsigned i;
2454     HandleNode* block;
2455     HandleNode* aNode;
2456
2457 #if PLATFORM(WIN_OS)
2458     block = (HandleNode*)VirtualAlloc(0, pageSize, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
2459 #elif PLATFORM(SYMBIAN)
2460     // symbian::fixme needs to do page aligned allocation as valloc is not supported.
2461     block = NULL;
2462 #else
2463     block = (HandleNode*)valloc(pageSize);
2464 #endif
2465
2466     for (i = 2; i < nodeBlockSize; i++) {
2467         aNode = &block[i];
2468         if (i > 2)
2469             aNode->type.internalNode.previous = i-1;
2470         else
2471             aNode->type.internalNode.previous = 0;
2472         if (i != nodeBlockSize - 1)
2473             aNode->type.internalNode.next = i+1;
2474         else
2475             aNode->type.internalNode.next = 0;
2476     }
2477     block[0].type.freeNodes = &block[nodeBlockSize - 1];
2478     block[1].type.pageNode = pageNode;
2479
2480     return block;
2481 }
2482
2483 static HandlePageNode *allocatePageNode()
2484 {
2485     HandlePageNode *node = (HandlePageNode *)fastMalloc(sizeof(HandlePageNode));
2486     node->next = node->previous = 0;
2487     node->nodes = initializeHandleNodeBlock(node);
2488     return node;
2489 }
2490
2491 static HandleNode *allocateNode(HandlePageNode *pageNode)
2492 {
2493     HandleNode *block = (HandleNode *)pageNode->nodes;
2494     HandleNode *freeNodes = block[0].type.freeNodes;
2495     HandleNode *allocated;
2496     
2497     // Check to see if we're out of nodes.
2498     if (freeNodes == 0) {
2499         FATAL("out of nodes");
2500         return 0;
2501     }
2502     
2503     // Remove node from end of free list 
2504     allocated = freeNodes;
2505     if (allocated->type.internalNode.previous >= 2) {
2506         block[0].type.freeNodes = block + allocated->type.internalNode.previous;
2507         block[0].type.freeNodes->type.internalNode.next = 0;
2508     }
2509     else {
2510         // Used last node on this page.
2511         block[0].type.freeNodes = 0;
2512         
2513         freeNodeAllocationPages = freeNodeAllocationPages->previous;
2514         if (freeNodeAllocationPages)
2515             freeNodeAllocationPages->next = 0;
2516
2517         pageNode->previous = usedNodeAllocationPages;
2518         pageNode->next = 0;
2519         if (usedNodeAllocationPages)
2520             usedNodeAllocationPages->next = pageNode;
2521         usedNodeAllocationPages = pageNode;        
2522     }
2523
2524     return allocated;
2525 }
2526
2527 void freeHandle(DeprecatedStringData **_free)
2528 {
2529 #ifdef CHECK_FOR_HANDLE_LEAKS
2530     fastFree(_free);
2531     return;
2532 #endif
2533
2534     HandleNode *free = (HandleNode *)_free;
2535     HandleNode *base = (HandleNode *)((uintptr_t)free & pageMask);
2536     HandleNode *freeNodes = base[0].type.freeNodes;
2537     HandlePageNode *pageNode = base[1].type.pageNode;
2538     
2539     if (freeNodes == 0){
2540         free->type.internalNode.previous = 0;
2541     }
2542     else {
2543         // Insert at head of free list.
2544         free->type.internalNode.previous = freeNodes - base;
2545         freeNodes->type.internalNode.next = free - base;
2546     }
2547     free->type.internalNode.next = 0;
2548     base[0].type.freeNodes = free;
2549     
2550     // Remove page from used/free list and place on free list
2551     if (freeNodeAllocationPages != pageNode) {
2552         if (pageNode->previous)
2553             pageNode->previous->next = pageNode->next;
2554         if (pageNode->next)
2555             pageNode->next->previous = pageNode->previous;
2556         if (usedNodeAllocationPages == pageNode)
2557             usedNodeAllocationPages = pageNode->previous;
2558     
2559         pageNode->previous = freeNodeAllocationPages;
2560         pageNode->next = 0;
2561         if (freeNodeAllocationPages)
2562             freeNodeAllocationPages->next = pageNode;
2563         freeNodeAllocationPages = pageNode;
2564     }
2565 }
2566
2567 DeprecatedString DeprecatedString::fromUtf8(const char *chs)
2568 {
2569     return UTF8Encoding().decode(chs, strlen(chs)).deprecatedString();
2570 }
2571
2572 DeprecatedString DeprecatedString::fromUtf8(const char *chs, int len)
2573 {
2574     return UTF8Encoding().decode(chs, len).deprecatedString();
2575 }
2576
2577 DeprecatedCString DeprecatedString::utf8(int& length) const
2578 {
2579     DeprecatedCString result = UTF8Encoding().encode((::UChar*)unicode(), this->length()).deprecatedCString();
2580     length = result.length();
2581     return result;
2582 }
2583
2584 DeprecatedString::DeprecatedString(const Identifier& str)
2585 {
2586     if (str.isNull()) {
2587         internalData.deref();
2588         dataHandle = makeSharedNullHandle();
2589         dataHandle[0]->ref();
2590     } else {
2591         dataHandle = allocateHandle();
2592         *dataHandle = &internalData;
2593         internalData.initialize(reinterpret_cast<const DeprecatedChar*>(str.data()), str.size());
2594     }
2595 }
2596
2597 DeprecatedString::DeprecatedString(const UString& str)
2598 {
2599     if (str.isNull()) {
2600         internalData.deref();
2601         dataHandle = makeSharedNullHandle();
2602         dataHandle[0]->ref();
2603     } else {
2604         dataHandle = allocateHandle();
2605         *dataHandle = &internalData;
2606         internalData.initialize(reinterpret_cast<const DeprecatedChar*>(str.data()), str.size());
2607     }
2608 }
2609
2610 #if PLATFORM(QT)
2611 DeprecatedString::DeprecatedString(const QString& str)
2612 {
2613     if (str.isNull()) {
2614         internalData.deref();
2615         dataHandle = makeSharedNullHandle();
2616         dataHandle[0]->ref();
2617     } else {
2618         dataHandle = allocateHandle();
2619         *dataHandle = &internalData;
2620         internalData.initialize(reinterpret_cast<const DeprecatedChar*>(str.data()), str.length());
2621     }
2622 }
2623 #endif
2624
2625 DeprecatedString::operator Identifier() const
2626 {
2627     if (isNull())
2628         return Identifier();
2629     return Identifier(reinterpret_cast<const KJS::UChar*>(unicode()), length());
2630 }
2631
2632 DeprecatedString::operator UString() const
2633 {
2634     if (isNull())
2635         return UString();
2636     return UString(reinterpret_cast<const KJS::UChar*>(unicode()), length());
2637 }
2638
2639 }