2
*******************************************************************************
4
* Copyright (C) 2002, International Business Machines
5
* Corporation and others. All Rights Reserved.
7
*******************************************************************************
10
* tab size: 8 (not used)
13
* created on: 2002mar07
14
* created by: Markus W. Scherer
16
* Poor man's C version of UnicodeSet, with only basic functions.
17
* The main data structure, the array of range limits, is
18
* the same as in UnicodeSet, except that the HIGH value is not stored.
20
* There are functions to efficiently serialize a USet into an array of uint16_t
21
* and functions to use such a serialized form efficiently without
22
* instantiating a new USet.
24
* If we needed more of UnicodeSet's functionality, then we should
25
* move UnicodeSet from the i18n to the common library and
27
* The only part of this code that would still be useful is the serialization
28
* and the functions that use the serialized form directly.
31
#include "unicode/utypes.h"
35
#define USET_STATIC_CAPACITY 12
36
#define USET_GROW_DELTA 20
40
int32_t length, capacity;
41
UChar32 staticBuffer[USET_STATIC_CAPACITY];
44
U_CAPI USet * U_EXPORT2
45
uset_open(UChar32 start, UChar32 limit) {
48
set=(USet *)uprv_malloc(sizeof(USet));
50
/* initialize to an empty set */
51
set->array=set->staticBuffer;
53
set->capacity=USET_STATIC_CAPACITY;
55
/* set initial range */
57
start=0; /* UChar32 may be signed! */
76
uset_close(USet *set) {
78
if(set->array!=set->staticBuffer) {
79
uprv_free(set->array);
85
static U_INLINE int32_t
86
findChar(const UChar32 *array, int32_t length, UChar32 c) {
89
/* check the last range limit first for more efficient appending */
91
if(c>=array[length-1]) {
95
/* do not check the last range limit again in the loop below */
99
for(i=0; i<length && c>=array[i]; ++i) {}
104
addRemove(USet *set, UChar32 c, int32_t doRemove) {
105
int32_t i, length, more;
107
if(set==NULL || (uint32_t)c>0x10ffff) {
112
i=findChar(set->array, length, c);
114
/* c is already in the set */
118
/* how many more array items do we need? */
119
if(i<length && (c+1)==set->array[i]) {
120
/* c is just before the following range, extend that in-place by one */
124
if(c==set->array[i]) {
125
/* the previous range collapsed, remove it */
126
set->length=length-=2;
128
uprv_memmove(set->array+i, set->array+i+2, (length-i)*4);
133
} else if(i>0 && c==set->array[i-1]) {
134
/* c is just after the previous range, extend that in-place by one */
137
if(i<length && c==set->array[i]) {
138
/* the following range collapsed, remove it */
140
set->length=length-=2;
142
uprv_memmove(set->array+i, set->array+i+2, (length-i)*4);
146
/* extend the previous range (had limit 0x10ffff) to the end of Unicode */
150
} else if(i==length && c==0x10ffff) {
151
/* insert one range limit c */
154
/* insert two range limits c, c+1 */
158
/* insert <more> range limits */
159
if(length+more>set->capacity) {
161
int32_t newCapacity=set->capacity+set->capacity/2+USET_GROW_DELTA;
162
UChar32 *newArray=(UChar32 *)uprv_malloc(newCapacity*4);
166
set->capacity=newCapacity;
167
uprv_memcpy(newArray, set->array, length*4);
169
if(set->array!=set->staticBuffer) {
170
uprv_free(set->array);
176
uprv_memmove(set->array+i+more, set->array+i, (length-i)*4);
187
U_CAPI UBool U_EXPORT2
188
uset_add(USet *set, UChar32 c) {
189
return addRemove(set, c, 0);
192
U_CAPI void U_EXPORT2
193
uset_remove(USet *set, UChar32 c) {
194
addRemove(set, c, 1);
197
U_CAPI UBool U_EXPORT2
198
uset_isEmpty(const USet *set) {
199
return set==NULL || set->length<=0;
202
U_CAPI UBool U_EXPORT2
203
uset_contains(const USet *set, UChar32 c) {
206
if(set==NULL || (uint32_t)c>0x10ffff) {
210
i=findChar(set->array, set->length, c);
214
U_CAPI int32_t U_EXPORT2
215
uset_containsOne(const USet *set) {
217
((set->length==2 && set->array[0]==(set->array[1]-1)) ||
218
(set->length==1 && set->array[0]==0x10ffff))
220
return (int32_t)set->array[0];
226
U_CAPI int32_t U_EXPORT2
227
uset_countRanges(const USet *set) {
231
return (set->length+1)/2;
235
U_CAPI UBool U_EXPORT2
236
uset_getRange(const USet *set, int32_t rangeIndex,
237
UChar32 *pStart, UChar32 *pLimit) {
238
if(set==NULL || rangeIndex<0) {
243
if(rangeIndex<set->length) {
244
*pStart=set->array[rangeIndex++];
245
if(rangeIndex<set->length) {
246
*pLimit=set->array[rangeIndex];
257
* Serialize a USet into 16-bit units.
258
* Store BMP code points as themselves with one 16-bit unit each.
260
* Important: the code points in the array are in ascending order,
261
* therefore all BMP code points precede all supplementary code points.
263
* Store each supplementary code point in 2 16-bit units,
264
* simply with higher-then-lower 16-bit halfs.
266
* Precede the entire list with the length.
267
* If there are supplementary code points, then set bit 15 in the length
268
* and add the bmpLength between it and the array.
271
* - all BMP: (length=bmpLength) BMP, .., BMP
272
* - some supplementary: (length|0x8000) (bmpLength<length) BMP, .., BMP, supp-high, supp-low, ..
274
U_CAPI int32_t U_EXPORT2
275
uset_serialize(const USet *set, uint16_t *dest, int32_t destCapacity, UErrorCode *pErrorCode) {
276
int32_t bmpLength, length, destLength;
278
if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
282
if(set==NULL || destCapacity<0 || (destCapacity>0 && dest==NULL)) {
283
*pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
287
/* count necessary 16-bit units */
298
if(set->array[length-1]<=0xffff) {
301
} else if(set->array[0]>=0x10000) {
302
/* all supplementary */
306
/* some BMP, some supplementary */
307
for(bmpLength=0; bmpLength<length && set->array[bmpLength]<=0xffff; ++bmpLength) {}
308
length=bmpLength+2*(length-bmpLength);
311
/* length: number of 16-bit array units */
313
/* there are only 15 bits for the length in the first serialized word */
314
*pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR;
319
* total serialized length:
320
* number of 16-bit array units (length) +
321
* 1 length unit (always) +
322
* 1 bmpLength unit (if there are supplementary values)
324
destLength=length+1+(length>bmpLength);
325
if(destLength<=destCapacity) {
329
*dest=(uint16_t)length;
330
if(length>bmpLength) {
332
*++dest=(uint16_t)bmpLength;
336
/* write the BMP part of the array */
338
for(i=0; i<bmpLength; ++i) {
339
*dest++=(uint16_t)*p++;
342
/* write the supplementary part of the array */
343
for(; i<length; i+=2) {
344
*dest++=(uint16_t)(*p>>16);
345
*dest++=(uint16_t)*p++;
348
*pErrorCode=U_BUFFER_OVERFLOW_ERROR;
353
U_CAPI UBool U_EXPORT2
354
uset_getSerializedSet(USerializedSet *fillSet, const uint16_t *src, int32_t srcCapacity) {
360
if(src==NULL || srcCapacity<=0) {
361
fillSet->length=fillSet->bmpLength=0;
367
/* there are supplementary values */
369
if(srcCapacity<(2+length)) {
370
fillSet->length=fillSet->bmpLength=0;
373
fillSet->bmpLength=*src++;
375
/* only BMP values */
376
if(srcCapacity<(1+length)) {
377
fillSet->length=fillSet->bmpLength=0;
380
fillSet->bmpLength=length;
383
fillSet->length=length;
387
U_CAPI void U_EXPORT2
388
uset_setSerializedToOne(USerializedSet *fillSet, UChar32 c) {
389
if(fillSet==NULL || (uint32_t)c>0x10ffff) {
393
fillSet->array=fillSet->staticArray;
395
fillSet->bmpLength=fillSet->length=2;
396
fillSet->staticArray[0]=(uint16_t)c;
397
fillSet->staticArray[1]=(uint16_t)c+1;
398
} else if(c==0xffff) {
399
fillSet->bmpLength=1;
401
fillSet->staticArray[0]=0xffff;
402
fillSet->staticArray[1]=1;
403
fillSet->staticArray[2]=0;
404
} else if(c<0x10ffff) {
405
fillSet->bmpLength=0;
407
fillSet->staticArray[0]=(uint16_t)(c>>16);
408
fillSet->staticArray[1]=(uint16_t)c;
410
fillSet->staticArray[2]=(uint16_t)(c>>16);
411
fillSet->staticArray[3]=(uint16_t)c;
412
} else /* c==0x10ffff */ {
413
fillSet->bmpLength=0;
415
fillSet->staticArray[0]=0x10;
416
fillSet->staticArray[1]=0xffff;
420
U_CAPI UBool U_EXPORT2
421
uset_serializedContains(const USerializedSet *set, UChar32 c) {
422
const uint16_t *array;
424
if(set==NULL || (uint32_t)c>0x10ffff) {
430
/* find c in the BMP part */
431
int32_t i, bmpLength=set->bmpLength;
432
for(i=0; i<bmpLength && (uint16_t)c>=array[i]; ++i) {}
435
/* find c in the supplementary part */
436
int32_t i, length=set->length;
437
uint16_t high=(uint16_t)(c>>16), low=(uint16_t)c;
438
for(i=set->bmpLength;
439
i<length && (high>array[i] || (high==array[i] && low>=array[i+1]));
442
/* count pairs of 16-bit units even per BMP and check if the number of pairs is odd */
443
return (UBool)(((i+set->bmpLength)&2)!=0);
447
U_CAPI int32_t U_EXPORT2
448
uset_countSerializedRanges(const USerializedSet *set) {
453
return (set->bmpLength+(set->length-set->bmpLength)/2+1)/2;
456
U_CAPI UBool U_EXPORT2
457
uset_getSerializedRange(const USerializedSet *set, int32_t rangeIndex,
458
UChar32 *pStart, UChar32 *pLimit) {
459
const uint16_t *array;
460
int32_t bmpLength, length;
462
if(set==NULL || rangeIndex<0 || pStart==NULL || pLimit==NULL) {
468
bmpLength=set->bmpLength;
470
rangeIndex*=2; /* address start/limit pairs */
471
if(rangeIndex<bmpLength) {
472
*pStart=array[rangeIndex++];
473
if(rangeIndex<bmpLength) {
474
*pLimit=array[rangeIndex];
475
} else if(rangeIndex<length) {
476
*pLimit=(((int32_t)array[rangeIndex])<<16)|array[rangeIndex+1];
482
rangeIndex-=bmpLength;
483
rangeIndex*=2; /* address pairs of pairs of units */
485
if(rangeIndex<length) {
487
*pStart=(((int32_t)array[rangeIndex])<<16)|array[rangeIndex+1];
489
if(rangeIndex<length) {
490
*pLimit=(((int32_t)array[rangeIndex])<<16)|array[rangeIndex+1];
added
removed
source/common/uset.c
