source: icXML/icXML-devel/src/xercesc/util/regx/RangeToken.cpp @ 2722

Last change on this file since 2722 was 2722, checked in by cameron, 6 years ago

Original Xerces files with import mods for icxercesc

File size: 24.8 KB
Line 
1/*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements.  See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License.  You may obtain a copy of the License at
8 *
9 *      http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18/*
19 * $Id: RangeToken.cpp 901107 2010-01-20 08:45:02Z borisk $
20 */
21
22// ---------------------------------------------------------------------------
23//  Includes
24// ---------------------------------------------------------------------------
25#if HAVE_CONFIG_H
26#    include <config.h>
27#endif
28
29#include <assert.h>
30
31#include <xercesc/util/regx/RangeToken.hpp>
32#include <xercesc/util/regx/TokenFactory.hpp>
33#include <xercesc/util/IllegalArgumentException.hpp>
34#include <xercesc/util/XMLUniDefs.hpp>
35
36#if XERCES_USE_TRANSCODER_ICU
37  #include <unicode/uchar.h>
38
39#if (U_ICU_VERSION_MAJOR_NUM > 2) || (U_ICU_VERSION_MAJOR_NUM == 2 && U_ICU_VERSION_MINOR_NUM >=4)
40  #include <unicode/uset.h>
41  #include <icxercesc/util/XMLString.hpp>
42  #include <xercesc/util/Janitor.hpp>
43#endif
44#endif
45
46XERCES_CPP_NAMESPACE_BEGIN
47
48// ---------------------------------------------------------------------------
49//  Static member data initialization
50// ---------------------------------------------------------------------------
51const int RangeToken::MAPSIZE = 256;
52const unsigned int RangeToken::INITIALSIZE = 16;
53
54// ---------------------------------------------------------------------------
55//  RangeToken: Constructors and Destructors
56// ---------------------------------------------------------------------------
57RangeToken::RangeToken(const Token::tokType tkType,
58                       MemoryManager* const manager)
59    : Token(tkType, manager)
60    , fSorted(false)
61    , fCompacted(false)
62    , fNonMapIndex(0)
63    , fElemCount(0)
64    , fMaxCount(INITIALSIZE)
65    , fMap(0)
66    , fRanges(0)
67    , fCaseIToken(0)
68    , fMemoryManager(manager)
69{
70
71}
72
73RangeToken::~RangeToken() {
74
75    // TODO(dbertoni) This is a temporary hack until we can change the ABI.
76    // See Jira issue XERCESC-1866 for more details.
77    if (fCaseIToken && fCaseIToken->fCaseIToken == this)
78    {
79        fCaseIToken->fCaseIToken = 0;
80    }
81    fMemoryManager->deallocate(fMap);//delete [] fMap;
82    fMemoryManager->deallocate(fRanges);//delete[] fRanges;
83}
84
85
86// This is a struct that defines a mapping for
87// case-insensitive matching.  The first character
88// is the character we try to match in the range.
89// The second is the character we add to the range,
90// because it maps to the first when we're folding
91// case.
92struct ExceptionCharsStruct
93{
94    XMLInt32    baseChar;
95
96    XMLInt32    matchingChar;
97};
98
99
100// This is an array of character mappings that we will
101// add to ranges for case-insensitive matching.
102static const ExceptionCharsStruct   s_exceptions[] =
103{
104    { 0x49, 0x130 },
105    { 0x49, 0x131 },
106    { 0x4b, 0x212a },
107    { 0x53, 0x17f },
108    { 0x69, 0x130 },
109    { 0x69, 0x131 },
110    { 0x6b, 0x212a },
111    { 0x73, 0x17f },
112    { 0xc5, 0x212b },
113    { 0xe5, 0x212b },
114    { 0x1c4, 0x1c5 },
115    { 0x1c6, 0x1c5 },
116    { 0x1c7, 0x1c8 },
117    { 0x1c9, 0x1c8 },
118    { 0x1ca, 0x1cb },
119    { 0x1cc, 0x1cb },
120    { 0x1f1, 0x1f2 },
121    { 0x1f3, 0x1f2 },
122    { 0x392, 0x3d0 },
123    { 0x395, 0x3f5 },
124    { 0x398, 0x3d1 },
125    { 0x398, 0x3f4 },
126    { 0x399, 0x345 },
127    { 0x399, 0x1fbe },
128    { 0x39a, 0x3f0 },
129    { 0x39c, 0xb5 },
130    { 0x3a0, 0x3d6 },
131    { 0x3a1, 0x3f1 },
132    { 0x3a3, 0x3c2 },
133    { 0x3a6, 0x3d5 },
134    { 0x3a9, 0x2126 },
135    { 0x3b2, 0x3d0 },
136    { 0x3b5, 0x3f5 },
137    { 0x3b8, 0x3d1 },
138    { 0x3b8, 0x3f4 },
139    { 0x3b9, 0x345 },
140    { 0x3b9, 0x1fbe },
141    { 0x3ba, 0x3f0 },
142    { 0x3bc, 0xb5 },
143    { 0x3c0, 0x3d6 },
144    { 0x3c1, 0x3f1 },
145    { 0x3c3, 0x3c2 },
146    { 0x3c6, 0x3d5 },
147    { 0x3c9, 0x2126 },
148    { 0x1e60, 0x1e9b },
149    { 0x1e61, 0x1e9b }
150};
151
152// ---------------------------------------------------------------------------
153//  RangeToken: Getter methods
154// ---------------------------------------------------------------------------
155RangeToken* RangeToken::getCaseInsensitiveToken(TokenFactory* const tokFactory) {
156
157    if (fCaseIToken == 0 && tokFactory && fRanges) {
158
159        bool isNRange = (getTokenType() == T_NRANGE) ? true : false;
160        RangeToken* lwrToken = tokFactory->createRange(isNRange);
161
162#if XERCES_USE_TRANSCODER_ICU && ((U_ICU_VERSION_MAJOR_NUM > 2) || (U_ICU_VERSION_MAJOR_NUM == 2 && U_ICU_VERSION_MINOR_NUM >=4))
163        UChar* rangeStr=(UChar*)fMemoryManager->allocate(40*fElemCount*sizeof(UChar));
164        ArrayJanitor<UChar> janRange(rangeStr, fMemoryManager);
165        int c=0;
166        rangeStr[c++] = chOpenSquare;
167        for (unsigned int i = 0;  i < fElemCount - 1;  i += 2) {
168            XMLCh buffer[10];
169            XMLSize_t len, j;
170
171            rangeStr[c++] = chBackSlash;
172            rangeStr[c++] = chLatin_U;
173            XMLString::binToText(fRanges[i], buffer, 10, 16, fMemoryManager);
174            len = XMLString::stringLen(buffer);
175            for(j=0;j<(8-len);j++)
176                rangeStr[c++] = chDigit_0;
177            XMLCh* p=buffer;
178            while(*p)
179                rangeStr[c++] = *p++;
180            if(fRanges[i+1]!=fRanges[i])
181            {
182                rangeStr[c++] = chDash;
183                rangeStr[c++] = chBackSlash;
184                rangeStr[c++] = chLatin_U;
185                XMLString::binToText(fRanges[i+1], buffer, 10, 16, fMemoryManager);
186                len = XMLString::stringLen(buffer);
187                for(j=0;j<(8-len);j++)
188                    rangeStr[c++] = chDigit_0;
189                p=buffer;
190                while(*p)
191                    rangeStr[c++] = *p++;
192            }
193        }
194        rangeStr[c++] = chCloseSquare;
195        rangeStr[c++] = chNull;
196        UErrorCode ec=U_ZERO_ERROR;
197        USet* range=uset_openPatternOptions(rangeStr, -1, USET_CASE_INSENSITIVE, &ec);
198        if(range)
199        {
200            ec = U_ZERO_ERROR;
201            uint32_t cbCount=uset_serialize(range, NULL, 0, &ec);
202            uint16_t* buffer=(uint16_t*)fMemoryManager->allocate(cbCount*sizeof(uint16_t));
203            ArrayJanitor<uint16_t> janSet(buffer, fMemoryManager);
204            ec = U_ZERO_ERROR;
205            uset_serialize(range, buffer, cbCount, &ec);
206            USerializedSet serializedSet;
207            uset_getSerializedSet(&serializedSet, buffer, cbCount);
208            int32_t nSets=uset_getSerializedRangeCount(&serializedSet);
209            for(int32_t i=0; i<nSets; i++)
210            {
211                UChar32 start, end;
212                uset_getSerializedRange(&serializedSet, i, &start, &end);
213                lwrToken->addRange(start, end);
214            }
215            // does this release the memory allocated by the set?
216            uset_setSerializedToOne(&serializedSet, 32);
217            uset_close(range);
218        }
219#else
220        unsigned int exceptIndex = 0;
221
222        for (unsigned int i = 0;  i < fElemCount - 1;  i += 2) {
223            for (XMLInt32 ch = fRanges[i];  ch <= fRanges[i + 1];  ++ch) {
224#if XERCES_USE_TRANSCODER_ICU
225                const XMLInt32  upperCh = u_toupper(ch);
226
227                if (upperCh != ch)
228                {
229                    lwrToken->addRange(upperCh, upperCh);
230                }
231
232                const XMLInt32  lowerCh = u_tolower(ch);
233
234                if (lowerCh != ch)
235                {
236                    lwrToken->addRange(lowerCh, lowerCh);
237                }
238
239                const XMLInt32  titleCh = u_totitle(ch);
240
241                if (titleCh != ch && titleCh != upperCh)
242                {
243                    lwrToken->addRange(titleCh, titleCh);
244                }
245#else
246                if (ch >= chLatin_A && ch <= chLatin_Z)
247                {
248                    ch += chLatin_a - chLatin_A;
249
250                    lwrToken->addRange(ch, ch);
251                }
252                else if (ch >= chLatin_a && ch <= chLatin_z)
253                {
254                    ch -= chLatin_a - chLatin_A;
255
256                    lwrToken->addRange(ch, ch);
257                }
258#endif
259
260                const unsigned int  exceptionsSize =
261                    sizeof(s_exceptions) / sizeof(s_exceptions[0]);
262
263                // Add any exception chars.  These are characters where the the
264                // case mapping is not symmetric.  (Unicode case mappings are not isomorphic...)
265                while (exceptIndex < exceptionsSize)
266                {
267                    if (s_exceptions[exceptIndex].baseChar < ch)
268                    {
269                        ++exceptIndex;
270                    }
271                    else if (s_exceptions[exceptIndex].baseChar == ch)
272                    {
273                        const XMLInt32  matchingChar =
274                            s_exceptions[exceptIndex].matchingChar;
275
276                        lwrToken->addRange(
277                            matchingChar,
278                            matchingChar);
279
280                        ++exceptIndex;
281                    }
282                    else
283                    {
284                        break;
285                    }
286                }
287            }
288        }
289
290        lwrToken->mergeRanges(this);
291#endif
292        lwrToken->compactRanges();
293        lwrToken->createMap();
294
295        fCaseIToken = lwrToken;
296        // TODO(dbertoni) This is a temporary hack until we can change the ABI.
297        // See Jira issue XERCESC-1866 for more details.
298        // Overload the fCaseIToken data member to be the case-insensitive token
299        // that's caching the case-insensitive one.  We need this because tokens
300        // have varying lifetimes.
301        fCaseIToken->setCaseInsensitiveToken(this);
302    }
303
304    return fCaseIToken;
305}
306
307// ---------------------------------------------------------------------------
308//  RangeToken: Setter methods
309// ---------------------------------------------------------------------------
310void RangeToken::setRangeValues(XMLInt32* const rangeValues, const unsigned int count)
311{
312    if (fRanges) {
313
314        if (fMap) {
315            fMemoryManager->deallocate(fMap);//delete [] fMap;
316            fMap = 0;
317        }
318
319        fElemCount = 0;
320        fMemoryManager->deallocate(fRanges);//delete [] fRanges;
321        fRanges = 0;
322    }
323
324    fElemCount = fMaxCount = count;
325    fRanges = rangeValues;
326}
327
328// ---------------------------------------------------------------------------
329//  RangeToken: Range manipulation methods
330// ---------------------------------------------------------------------------
331void RangeToken::addRange(const XMLInt32 start, const XMLInt32 end) {
332
333    XMLInt32 val1, val2;
334
335    fCaseIToken = 0;
336
337    if (start <= end) {
338
339        val1 = start;
340        val2 = end;
341    }
342    else {
343
344        val1 = end;
345        val2 = start;
346    }
347
348    if (fRanges == 0) {
349
350        fRanges = (XMLInt32*) fMemoryManager->allocate
351        (
352            fMaxCount * sizeof(XMLInt32)
353        );//new XMLInt32[fMaxCount];
354        fRanges[0] = val1;
355        fRanges[1] = val2;
356        fElemCount = 2;
357        fSorted = true;
358    }
359    else {
360
361        if (fRanges[fElemCount-1] + 1 == val1) {
362
363            fRanges[fElemCount-1] = val2;
364            return;
365        }
366
367        if (fElemCount + 2 >= fMaxCount) {
368            expand(2);
369        }
370
371        if(fSorted && fRanges[fElemCount-1] >= val1)
372        {
373            for (int i = 0; i < (int)fElemCount; i +=2)
374            {
375                // check if this range is already part of this one
376                if (fRanges[i] <= val1 && fRanges[i+1] >= val2)
377                    break;
378                // or if the new one extends the old one
379                else if(fRanges[i]==val1 && fRanges[i+1] < val2)
380                {
381                    fRanges[i+1]=val2;
382                    break;
383                }
384                else if (fRanges[i] > val1 ||
385                          (fRanges[i]==val1 && fRanges[i+1] > val2))
386                {
387                    for(int j=fElemCount-1;j>=i;j--)
388                        fRanges[j+2]=fRanges[j];
389                    fRanges[i]   = val1;
390                    fRanges[i+1] = val2;
391                    fElemCount  += 2;
392                    break;
393                }
394            }
395        }
396        else
397        {
398            if (fRanges[fElemCount-1] >= val1)
399                fSorted = false;
400
401            fRanges[fElemCount++] = val1;
402            fRanges[fElemCount++] = val2;
403
404            if (!fSorted) {
405                sortRanges();
406            }
407        }
408    }
409}
410
411void RangeToken::sortRanges() {
412
413    if (fSorted || fRanges == 0)
414        return;
415
416    for (int i = fElemCount - 4; i >= 0; i -= 2) {
417
418        for (int j = 0; j <= i; j +=2) {
419
420            if (fRanges[j] > fRanges[j + 2]
421                || (fRanges[j]==fRanges[j+2] && fRanges[j+1] > fRanges[j+3])) {
422
423                XMLInt32 tmpVal = fRanges[j+2];
424                fRanges[j+2] = fRanges[j];
425                fRanges[j] = tmpVal;
426                tmpVal = fRanges[j+3];
427                fRanges[j+3] = fRanges[j+1];
428                fRanges[j+1] = tmpVal;
429            }
430        }
431    }
432
433    fSorted = true;
434}
435
436void RangeToken::compactRanges() {
437
438    if (fCompacted || fRanges == 0 || fElemCount <= 2)
439        return;
440
441    unsigned int base = 0;
442    unsigned int target = 0;
443
444    while (target < fElemCount) {
445
446        if (base != target) {
447
448            fRanges[base] = fRanges[target++];
449            fRanges[base+1] = fRanges[target++];
450        }
451        else
452            target += 2;
453
454        XMLInt32 baseEnd = fRanges[base + 1];
455
456        while (target < fElemCount) {
457
458            XMLInt32 startRange = fRanges[target];
459
460            if (baseEnd + 1 < startRange)
461                break;
462
463            XMLInt32 endRange = fRanges[target + 1];
464
465            if (baseEnd + 1 == startRange || baseEnd < endRange) {
466
467                baseEnd = endRange;
468                fRanges[base+1] = baseEnd;
469                target += 2;
470            }
471            else if (baseEnd >= endRange) {
472                target += 2;
473            }
474            else {
475                ThrowXMLwithMemMgr(RuntimeException, XMLExcepts::Regex_CompactRangesError, fMemoryManager);
476            }
477        } // inner while
478
479        base += 2;
480    }
481
482    fElemCount = base;
483    fCompacted = true;
484}
485
486void RangeToken::mergeRanges(const Token *const tok) {
487
488
489    if (tok->getTokenType() != this->getTokenType())
490        ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::Regex_MergeRangesTypeMismatch, fMemoryManager);
491
492    RangeToken* rangeTok = (RangeToken *) tok;
493
494    if (rangeTok->fRanges == 0)
495        return;
496
497    fCaseIToken = 0;
498    sortRanges();
499    rangeTok->sortRanges();
500
501    if (fRanges == 0) {
502
503        fMaxCount = rangeTok->fMaxCount;
504        fRanges = (XMLInt32*) fMemoryManager->allocate
505        (
506            fMaxCount * sizeof(XMLInt32)
507        );//new XMLInt32[fMaxCount];
508        for (unsigned int index = 0; index < rangeTok->fElemCount; index++) {
509            fRanges[index] = rangeTok->fRanges[index];
510        }
511
512        fElemCount = rangeTok->fElemCount;
513        fSorted = true;
514        return;
515    }
516
517    unsigned int newMaxCount = (fElemCount + rangeTok->fElemCount >= fMaxCount)
518                                 ? fMaxCount + rangeTok->fMaxCount : fMaxCount;
519    XMLInt32* result = (XMLInt32*) fMemoryManager->allocate
520    (
521        newMaxCount * sizeof(XMLInt32)
522    );//new XMLInt32[newMaxCount];
523
524    for (unsigned int i=0, j=0, k=0; i < fElemCount || j < rangeTok->fElemCount;) {
525
526        if (i >= fElemCount) {
527
528            for (int count = 0; count < 2; count++) {
529                result[k++] = rangeTok->fRanges[j++];
530            }
531        }
532        else if (j >= rangeTok->fElemCount) {
533
534            for (int count = 0; count < 2; count++) {
535                result[k++] = fRanges[i++];
536            }
537        }
538        else if (rangeTok->fRanges[j] < fRanges[i]
539                 || (rangeTok->fRanges[j] == fRanges[i]
540                     && rangeTok->fRanges[j+1] < fRanges[i+1])) {
541
542            for (int count = 0; count < 2; count++) {
543                result[k++] = rangeTok->fRanges[j++];
544            }
545        }
546        else {
547
548            for (int count = 0; count < 2; count++) {
549
550                result[k++] = fRanges[i++];
551            }
552        }
553    }
554
555    fMemoryManager->deallocate(fRanges);//delete [] fRanges;
556    fElemCount += rangeTok->fElemCount;
557    fRanges = result;
558    fMaxCount = newMaxCount;
559}
560
561void RangeToken::subtractRanges(RangeToken* const tok) {
562
563    if (fRanges == 0 || tok->fRanges == 0)
564        return;
565
566    if (tok->getTokenType() == T_NRANGE) {
567
568        intersectRanges(tok);
569        return;
570    }
571
572    fCaseIToken = 0;
573    sortRanges();
574    compactRanges();
575    tok->sortRanges();
576    tok->compactRanges();
577
578    unsigned int newMax = (fElemCount + tok->fElemCount >= fMaxCount)
579                             ? fMaxCount + tok->fMaxCount : fMaxCount;
580    XMLInt32* result = (XMLInt32*) fMemoryManager->allocate
581    (
582        newMax * sizeof(XMLInt32)
583    );//new XMLInt32[newMax];
584    unsigned int newElemCount = 0;
585    unsigned int srcCount = 0;
586    unsigned int subCount = 0;
587
588    while (srcCount < fElemCount && subCount < tok->fElemCount) {
589
590        XMLInt32 srcBegin = fRanges[srcCount];
591        XMLInt32 srcEnd = fRanges[srcCount + 1];
592        XMLInt32 subBegin = tok->fRanges[subCount];
593        XMLInt32 subEnd = tok->fRanges[subCount + 1];
594
595        if (srcEnd < subBegin) { // no overlap
596
597            result[newElemCount++] = fRanges[srcCount++];
598            result[newElemCount++] = fRanges[srcCount++];
599        }
600        else if (srcEnd >= subBegin && srcBegin <= subEnd) {
601
602            if (subBegin <= srcBegin && srcEnd <= subEnd) {
603                srcCount += 2;
604            }
605            else if (subBegin <= srcBegin) {
606
607                fRanges[srcCount] = subEnd + 1;
608                subCount += 2;
609            }
610            else if (srcEnd <= subEnd) {
611
612                result[newElemCount++] = srcBegin;
613                result[newElemCount++] = subBegin - 1;
614                srcCount += 2;
615            }
616            else {
617
618                result[newElemCount++] = srcBegin;
619                result[newElemCount++] = subBegin - 1;
620                fRanges[srcCount] = subEnd + 1;
621                subCount += 2;
622            }
623        }
624        else if (subEnd < srcBegin) {
625            subCount += 2;
626        }
627        else {
628            fMemoryManager->deallocate(result);//delete [] result;
629            ThrowXMLwithMemMgr(RuntimeException, XMLExcepts::Regex_SubtractRangesError, fMemoryManager);
630        }
631    } //end while
632
633    while (srcCount < fElemCount) {
634
635        result[newElemCount++] = fRanges[srcCount++];
636        result[newElemCount++] = fRanges[srcCount++];
637    }
638
639    fMemoryManager->deallocate(fRanges);//delete [] fRanges;
640    fRanges = result;
641    fElemCount = newElemCount;
642    fMaxCount = newMax;
643}
644
645/**
646  * Ignore whether 'tok' is NRANGE or not.
647  */
648void RangeToken::intersectRanges(RangeToken* const tok) {
649
650    if (fRanges == 0 || tok->fRanges == 0)
651        return;
652
653    fCaseIToken = 0;
654    sortRanges();
655    compactRanges();
656    tok->sortRanges();
657    tok->compactRanges();
658
659    unsigned int newMax = (fElemCount + tok->fElemCount >= fMaxCount)
660                             ? fMaxCount + tok->fMaxCount : fMaxCount;
661    XMLInt32* result = (XMLInt32*) fMemoryManager->allocate
662    (
663        newMax * sizeof(XMLInt32)
664    );//new XMLInt32[newMax];
665    unsigned int newElemCount = 0;
666    unsigned int srcCount = 0;
667    unsigned int tokCount = 0;
668
669    while (srcCount < fElemCount && tokCount < tok->fElemCount) {
670
671        XMLInt32 srcBegin = fRanges[srcCount];
672        XMLInt32 srcEnd = fRanges[srcCount + 1];
673        XMLInt32 tokBegin = tok->fRanges[tokCount];
674        XMLInt32 tokEnd = tok->fRanges[tokCount + 1];
675
676        if (srcEnd < tokBegin) {
677            srcCount += 2;
678        }
679        else if (srcEnd >= tokBegin && srcBegin <= tokEnd) {
680
681            if (tokBegin <= srcBegin && srcEnd <= tokEnd) {
682
683                result[newElemCount++] = srcBegin;
684                result[newElemCount++] = srcEnd;
685                srcCount += 2;
686            }
687            else if (tokBegin <= srcBegin) {
688
689                result[newElemCount++] = srcBegin;
690                result[newElemCount++] = tokEnd;
691                tokCount += 2;
692
693                if (tokCount < tok->fElemCount)
694                    fRanges[srcCount] = tokEnd + 1;
695                else
696                    srcCount += 2;
697            }
698            else if (srcEnd <= tokEnd) {
699
700                result[newElemCount++] = tokBegin;
701                result[newElemCount++] = srcEnd;
702                srcCount += 2;
703            }
704            else {
705
706                result[newElemCount++] = tokBegin;
707                result[newElemCount++] = tokEnd;
708                tokCount += 2;
709
710                if (tokCount < tok->fElemCount)
711                    fRanges[srcCount] = tokEnd + 1;
712                else
713                    srcCount += 2;
714            }
715        }
716        else if (tokEnd < srcBegin) {
717            tokCount += 2;
718
719            if (tokCount >= tok->fElemCount)
720                srcCount += 2;
721        }
722        else {
723
724            fMemoryManager->deallocate(result);//delete [] result;
725            ThrowXMLwithMemMgr(RuntimeException, XMLExcepts::Regex_IntersectRangesError, fMemoryManager);
726        }
727    } //end while
728
729    fMemoryManager->deallocate(fRanges);//delete [] fRanges;
730    fRanges = result;
731    fElemCount = newElemCount;
732    fMaxCount = newMax;
733}
734
735/**
736  * for RANGE: Creates complement.
737  * for NRANGE: Creates the same meaning RANGE.
738  */
739RangeToken* RangeToken::complementRanges(RangeToken* const tok,
740                                    TokenFactory* const tokFactory,
741                                    MemoryManager* const manager) {
742
743    if (tok->getTokenType() != T_RANGE && tok->getTokenType() != T_NRANGE)
744        ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::Regex_ComplementRangesInvalidArg, manager);
745
746    tok->sortRanges();
747    tok->compactRanges();
748
749    XMLInt32 lastElem = tok->fRanges[tok->fElemCount - 1];
750    RangeToken* rangeTok = tokFactory->createRange();
751
752    if (tok->fRanges[0] > 0) {
753        rangeTok->addRange(0, tok->fRanges[0] - 1);
754    }
755
756    for (unsigned int i= 1; i< tok->fElemCount - 2; i += 2) {
757        rangeTok->addRange(tok->fRanges[i] + 1, tok->fRanges[i+1] - 1);
758    }
759
760    if (lastElem != UTF16_MAX) {
761        rangeTok->addRange(lastElem + 1, UTF16_MAX);
762    }
763
764    rangeTok->fCompacted = true;
765
766    return rangeTok;
767}
768
769
770// ---------------------------------------------------------------------------
771//  RangeToken: Match methods
772// ---------------------------------------------------------------------------
773bool RangeToken::match(const XMLInt32 ch) {
774
775    createMap();
776
777    bool ret;
778
779    if (getTokenType() == T_RANGE) {
780
781        if (ch < MAPSIZE)
782            return ((fMap[ch/32] & (1<<(ch&0x1f))) != 0);
783
784        ret = false;
785
786        for (unsigned int i= fNonMapIndex; i< fElemCount; i +=2) {
787
788            if (fRanges[i] <= ch && ch <= fRanges[i+1])
789                return true;
790        }
791    }
792    else {
793
794        if (ch < MAPSIZE)
795            return ((fMap[ch/32] & (1<<(ch&0x1f))) == 0);
796
797        ret = true;
798
799        for (unsigned int i= fNonMapIndex; i< fElemCount; i += 2) {
800
801            if (fRanges[i] <= ch && ch <= fRanges[i+1])
802                return false;
803        }
804    }
805
806    return ret;
807}
808
809// ---------------------------------------------------------------------------
810//  RangeToken: Private helpers methods
811// ---------------------------------------------------------------------------
812void RangeToken::expand(const unsigned int length) {
813
814    unsigned int newMax = fElemCount + length;
815
816    // Avoid too many reallocations by expanding by a percentage
817    unsigned int minNewMax = (unsigned int)((double)fElemCount * 1.25);
818    if (newMax < minNewMax)
819        newMax = minNewMax;
820
821    XMLInt32* newList = (XMLInt32*) fMemoryManager->allocate
822    (
823        newMax * sizeof(XMLInt32)
824    );//new XMLInt32[newMax];
825    for (unsigned int index = 0; index < fElemCount; index++)
826        newList[index] = fRanges[index];
827
828    fMemoryManager->deallocate(fRanges);//delete [] fRanges;
829    fRanges = newList;
830    fMaxCount = newMax;
831}
832
833void RangeToken::doCreateMap() {
834
835    assert(!fMap);
836
837    int asize = MAPSIZE/32;
838    fMap = (int*) fMemoryManager->allocate(asize * sizeof(int));//new int[asize];
839    fNonMapIndex = fElemCount;
840
841    for (int i = 0; i < asize; i++) {
842        fMap[i] = 0;
843    }
844
845    for (unsigned int j= 0; j < fElemCount; j += 2) {
846
847        XMLInt32 begin = fRanges[j];
848        XMLInt32 end = fRanges[j+1];
849
850        if (begin < MAPSIZE) {
851
852            for (int k = begin; k <= end && k < MAPSIZE; k++) {
853                fMap[k/32] |= 1<<(k&0x1F);
854            }
855        }
856        else {
857
858            fNonMapIndex = j;
859            break;
860        }
861
862        if (end >= MAPSIZE) {
863
864            fNonMapIndex = j;
865            break;
866        }
867    }
868}
869
870XERCES_CPP_NAMESPACE_END
871
872/**
873  * End of file RangeToken.cpp
874  */
Note: See TracBrowser for help on using the repository browser.