← Back to branch summary

~ubuntu-branches/ubuntu/precise/xerces-c/precise

« back to all changes in this revision

Viewing changes to src/xercesc/util/regx/RangeToken.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Jay Berkenbilt
  • Date: 2009-02-22 16:52:23 UTC
  • Revision ID: james.westby@ubuntu.com-20090222165223-klimp8u8m73yn9zp
Tags: upstream-3.0.1
Import upstream version 3.0.1

Show diffs side-by-side

added added

removed removed

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