giteadmin/script-astra
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
master
script-astra/Android/Sdk/sources/android-35/android/icu/impl/Trie2Writable.java

1222 lines
43 KiB
Java
Raw Permalink Normal View History

init
2025-01-20 15:15:20 +00:00
/* GENERATED SOURCE. DO NOT MODIFY. */
// © 2016 and later: Unicode, Inc. and others.
// License & terms of use: http://www.unicode.org/copyright.html
/*
*******************************************************************************
* Copyright (C) 2009, International Business Machines Corporation and *
* others. All Rights Reserved. *
*******************************************************************************
*/
package android.icu.impl;
/**
* @author aheninger
*
* A Trie2Writable is a modifiable, or build-time Trie2.
* Functions for reading data from the Trie are all from class Trie2.
* @hide Only a subset of ICU is exposed in Android
*
*/
public class Trie2Writable extends Trie2 {
/**
* Create a new, empty, writable Trie2. 32-bit data values are used.
*
* @param initialValueP the initial value that is set for all code points
* @param errorValueP the value for out-of-range code points and illegal UTF-8
*/
public Trie2Writable(int initialValueP, int errorValueP) {
// This constructor corresponds to utrie2_open() in ICU4C.
init(initialValueP, errorValueP);
}
private void init(int initialValueP, int errorValueP) {
this.initialValue = initialValueP;
this.errorValue = errorValueP;
this.highStart = 0x110000;
this.data = new int[UNEWTRIE2_INITIAL_DATA_LENGTH];
this.dataCapacity = UNEWTRIE2_INITIAL_DATA_LENGTH;
this.initialValue = initialValueP;
this.errorValue = errorValueP;
this.highStart = 0x110000;
this.firstFreeBlock = 0; /* no free block in the list */
this.isCompacted = false;
/*
* preallocate and reset
* - ASCII
* - the bad-UTF-8-data block
* - the null data block
*/
int i, j;
for(i=0; i<0x80; ++i) {
data[i] = initialValue;
}
for(; i<0xc0; ++i) {
data[i] = errorValue;
}
for(i=UNEWTRIE2_DATA_NULL_OFFSET; i<UNEWTRIE2_DATA_START_OFFSET; ++i) {
data[i] = initialValue;
}
dataNullOffset = UNEWTRIE2_DATA_NULL_OFFSET;
dataLength = UNEWTRIE2_DATA_START_OFFSET;
/* set the index-2 indexes for the 2=0x80>>UTRIE2_SHIFT_2 ASCII data blocks */
for(i=0, j=0; j<0x80; ++i, j+=UTRIE2_DATA_BLOCK_LENGTH) {
index2[i]=j;
map[i]=1;
}
/* reference counts for the bad-UTF-8-data block */
for(; j<0xc0; ++i, j+=UTRIE2_DATA_BLOCK_LENGTH) {
map[i]=0;
}
/*
* Reference counts for the null data block: all blocks except for the ASCII blocks.
* Plus 1 so that we don't drop this block during compaction.
* Plus as many as needed for lead surrogate code points.
*/
/* i==newTrie->dataNullOffset */
map[i++] =
(0x110000>>UTRIE2_SHIFT_2) -
(0x80>>UTRIE2_SHIFT_2) +
1 +
UTRIE2_LSCP_INDEX_2_LENGTH;
j += UTRIE2_DATA_BLOCK_LENGTH;
for(; j<UNEWTRIE2_DATA_START_OFFSET; ++i, j+=UTRIE2_DATA_BLOCK_LENGTH) {
map[i]=0;
}
/*
* set the remaining indexes in the BMP index-2 block
* to the null data block
*/
for(i=0x80>>UTRIE2_SHIFT_2; i<UTRIE2_INDEX_2_BMP_LENGTH; ++i) {
index2[i]=UNEWTRIE2_DATA_NULL_OFFSET;
}
/*
* Fill the index gap with impossible values so that compaction
* does not overlap other index-2 blocks with the gap.
*/
for(i=0; i<UNEWTRIE2_INDEX_GAP_LENGTH; ++i) {
index2[UNEWTRIE2_INDEX_GAP_OFFSET+i]=-1;
}
/* set the indexes in the null index-2 block */
for(i=0; i<UTRIE2_INDEX_2_BLOCK_LENGTH; ++i) {
index2[UNEWTRIE2_INDEX_2_NULL_OFFSET+i]=UNEWTRIE2_DATA_NULL_OFFSET;
}
index2NullOffset=UNEWTRIE2_INDEX_2_NULL_OFFSET;
index2Length=UNEWTRIE2_INDEX_2_START_OFFSET;
/* set the index-1 indexes for the linear index-2 block */
for(i=0, j=0;
i<UTRIE2_OMITTED_BMP_INDEX_1_LENGTH;
++i, j+=UTRIE2_INDEX_2_BLOCK_LENGTH
) {
index1[i]=j;
}
/* set the remaining index-1 indexes to the null index-2 block */
for(; i<UNEWTRIE2_INDEX_1_LENGTH; ++i) {
index1[i]=UNEWTRIE2_INDEX_2_NULL_OFFSET;
}
/*
* Preallocate and reset data for U+0080..U+07ff,
* for 2-byte UTF-8 which will be compacted in 64-blocks
* even if UTRIE2_DATA_BLOCK_LENGTH is smaller.
*/
for(i=0x80; i<0x800; i+=UTRIE2_DATA_BLOCK_LENGTH) {
set(i, initialValue);
}
}
/**
* Create a new build time (modifiable) Trie2 whose contents are the same as the source Trie2.
*
* @param source the source Trie2. Its contents will be copied into the new Trie2.
*/
public Trie2Writable(Trie2 source) {
init(source.initialValue, source.errorValue);
for (Range r: source) {
setRange(r, true);
}
}
private boolean isInNullBlock(int c, boolean forLSCP) {
int i2, block;
if(Character.isHighSurrogate((char)c) && forLSCP) {
i2=(UTRIE2_LSCP_INDEX_2_OFFSET-(0xd800>>UTRIE2_SHIFT_2))+
(c>>UTRIE2_SHIFT_2);
} else {
i2=index1[c>>UTRIE2_SHIFT_1]+
((c>>UTRIE2_SHIFT_2)&UTRIE2_INDEX_2_MASK);
}
block=index2[i2];
return (block==dataNullOffset);
}
private int allocIndex2Block() {
int newBlock, newTop;
newBlock=index2Length;
newTop=newBlock+UTRIE2_INDEX_2_BLOCK_LENGTH;
if(newTop > index2.length) {
throw new IllegalStateException("Internal error in Trie2 creation.");
/*
* Should never occur.
* Either UTRIE2_MAX_BUILD_TIME_INDEX_LENGTH is incorrect,
* or the code writes more values than should be possible.
*/
}
index2Length=newTop;
System.arraycopy(index2, index2NullOffset, index2, newBlock, UTRIE2_INDEX_2_BLOCK_LENGTH);
return newBlock;
}
private int getIndex2Block(int c, boolean forLSCP) {
int i1, i2;
if(c>=0xd800 && c<0xdc00 && forLSCP) {
return UTRIE2_LSCP_INDEX_2_OFFSET;
}
i1=c>>UTRIE2_SHIFT_1;
i2=index1[i1];
if(i2==index2NullOffset) {
i2=allocIndex2Block();
index1[i1]=i2;
}
return i2;
}
private int allocDataBlock(int copyBlock) {
int newBlock, newTop;
if(firstFreeBlock!=0) {
/* get the first free block */
newBlock=firstFreeBlock;
firstFreeBlock=-map[newBlock>>UTRIE2_SHIFT_2];
} else {
/* get a new block from the high end */
newBlock=dataLength;
newTop=newBlock+UTRIE2_DATA_BLOCK_LENGTH;
if(newTop>dataCapacity) {
/* out of memory in the data array */
int capacity;
int[] newData;
if(dataCapacity<UNEWTRIE2_MEDIUM_DATA_LENGTH) {
capacity=UNEWTRIE2_MEDIUM_DATA_LENGTH;
} else if(dataCapacity<UNEWTRIE2_MAX_DATA_LENGTH) {
capacity=UNEWTRIE2_MAX_DATA_LENGTH;
} else {
/*
* Should never occur.
* Either UNEWTRIE2_MAX_DATA_LENGTH is incorrect,
* or the code writes more values than should be possible.
*/
throw new IllegalStateException("Internal error in Trie2 creation.");
}
newData = new int[capacity];
System.arraycopy(data, 0, newData, 0, dataLength);
data=newData;
dataCapacity=capacity;
}
dataLength=newTop;
}
System.arraycopy(data, copyBlock, data, newBlock, UTRIE2_DATA_BLOCK_LENGTH);
map[newBlock>>UTRIE2_SHIFT_2]=0;
return newBlock;
}
/* call when the block's reference counter reaches 0 */
private void releaseDataBlock(int block) {
/* put this block at the front of the free-block chain */
map[block>>UTRIE2_SHIFT_2]=-firstFreeBlock;
firstFreeBlock=block;
}
private boolean isWritableBlock(int block) {
return (block!=dataNullOffset && 1==map[block>>UTRIE2_SHIFT_2]);
}
private void setIndex2Entry(int i2, int block) {
int oldBlock;
++map[block>>UTRIE2_SHIFT_2]; /* increment first, in case block==oldBlock! */
oldBlock=index2[i2];
if(0 == --map[oldBlock>>UTRIE2_SHIFT_2]) {
releaseDataBlock(oldBlock);
}
index2[i2]=block;
}
/**
* No error checking for illegal arguments.
*
* @hide draft / provisional / internal are hidden on Android
*/
private int getDataBlock(int c, boolean forLSCP) {
int i2, oldBlock, newBlock;
i2=getIndex2Block(c, forLSCP);
i2+=(c>>UTRIE2_SHIFT_2)&UTRIE2_INDEX_2_MASK;
oldBlock=index2[i2];
if(isWritableBlock(oldBlock)) {
return oldBlock;
}
/* allocate a new data block */
newBlock=allocDataBlock(oldBlock);
setIndex2Entry(i2, newBlock);
return newBlock;
}
/**
* Set a value for a code point.
*
* @param c the code point
* @param value the value
*/
public Trie2Writable set(int c, int value) {
if (c<0 || c>0x10ffff) {
throw new IllegalArgumentException("Invalid code point.");
}
set(c, true, value);
fHash = 0;
return this;
}
private Trie2Writable set(int c, boolean forLSCP, int value) {
int block;
if (isCompacted) {
uncompact();
}
block = getDataBlock(c, forLSCP);
data[block + (c&UTRIE2_DATA_MASK)] = value;
return this;
}
/*
* Uncompact a compacted Trie2Writable.
* This is needed if a the WritableTrie2 was compacted in preparation for creating a read-only
* Trie2, and then is subsequently altered.
*
* The structure is a bit awkward - it would be cleaner to leave the original
* Trie2 unaltered - but compacting in place was taken directly from the ICU4C code.
*
* The approach is to create a new (uncompacted) Trie2Writable from this one, then transfer
* the guts from the new to the old.
*/
private void uncompact() {
Trie2Writable tempTrie = new Trie2Writable(this);
// Members from Trie2Writable
this.index1 = tempTrie.index1;
this.index2 = tempTrie.index2;
this.data = tempTrie.data;
this.index2Length = tempTrie.index2Length;
this.dataCapacity = tempTrie.dataCapacity;
this.isCompacted = tempTrie.isCompacted;
// Members From Trie2
this.header = tempTrie.header;
this.index = tempTrie.index;
this.data16 = tempTrie.data16;
this.data32 = tempTrie.data32;
this.indexLength = tempTrie.indexLength;
this.dataLength = tempTrie.dataLength;
this.index2NullOffset = tempTrie.index2NullOffset;
this.initialValue = tempTrie.initialValue;
this.errorValue = tempTrie.errorValue;
this.highStart = tempTrie.highStart;
this.highValueIndex = tempTrie.highValueIndex;
this.dataNullOffset = tempTrie.dataNullOffset;
}
private void writeBlock(int block, int value) {
int limit=block+UTRIE2_DATA_BLOCK_LENGTH;
while(block<limit) {
data[block++]=value;
}
}
/**
* initialValue is ignored if overwrite=true
* @hide draft / provisional / internal are hidden on Android
*/
private void fillBlock(int block, /*UChar32*/ int start, /*UChar32*/ int limit,
int value, int initialValue, boolean overwrite) {
int i;
int pLimit = block+limit;
if(overwrite) {
for (i=block+start; i<pLimit; i++) {
data[i] = value;
}
} else {
for (i=block+start; i<pLimit; i++) {
if(data[i]==initialValue) {
data[i]=value;
}
}
}
}
/**
* Set a value in a range of code points [start..end].
* All code points c with start<=c<=end will get the value if
* overwrite is true or if the old value is the initial value.
*
* @param start the first code point to get the value
* @param end the last code point to get the value (inclusive)
* @param value the value
* @param overwrite flag for whether old non-initial values are to be overwritten
*/
public Trie2Writable setRange(int start, int end,
int value, boolean overwrite) {
/*
* repeat value in [start..end]
* mark index values for repeat-data blocks by setting bit 31 of the index values
* fill around existing values if any, if(overwrite)
*/
int block, rest, repeatBlock;
int /*UChar32*/ limit;
if(start>0x10ffff || start<0 || end>0x10ffff || end<0 || start>end) {
throw new IllegalArgumentException("Invalid code point range.");
}
if(!overwrite && value==initialValue) {
return this; /* nothing to do */
}
fHash = 0;
if(isCompacted) {
this.uncompact();
}
limit=end+1;
if((start&UTRIE2_DATA_MASK) != 0) {
int /*UChar32*/ nextStart;
/* set partial block at [start..following block boundary[ */
block=getDataBlock(start, true);
nextStart=(start+UTRIE2_DATA_BLOCK_LENGTH)&~UTRIE2_DATA_MASK;
if(nextStart<=limit) {
fillBlock(block, start&UTRIE2_DATA_MASK, UTRIE2_DATA_BLOCK_LENGTH,
value, initialValue, overwrite);
start=nextStart;
} else {
fillBlock(block, start&UTRIE2_DATA_MASK, limit&UTRIE2_DATA_MASK,
value, initialValue, overwrite);
return this;
}
}
/* number of positions in the last, partial block */
rest=limit&UTRIE2_DATA_MASK;
/* round down limit to a block boundary */
limit&=~UTRIE2_DATA_MASK;
/* iterate over all-value blocks */
if(value==initialValue) {
repeatBlock=dataNullOffset;
} else {
repeatBlock=-1;
}
while(start<limit) {
int i2;
boolean setRepeatBlock=false;
if(value==initialValue && isInNullBlock(start, true)) {
start+=UTRIE2_DATA_BLOCK_LENGTH; /* nothing to do */
continue;
}
/* get index value */
i2=getIndex2Block(start, true);
i2+=(start>>UTRIE2_SHIFT_2)&UTRIE2_INDEX_2_MASK;
block=index2[i2];
if(isWritableBlock(block)) {
/* already allocated */
if(overwrite && block>=UNEWTRIE2_DATA_0800_OFFSET) {
/*
* We overwrite all values, and it's not a
* protected (ASCII-linear or 2-byte UTF-8) block:
* replace with the repeatBlock.
*/
setRepeatBlock=true;
} else {
/* !overwrite, or protected block: just write the values into this block */
fillBlock(block,
0, UTRIE2_DATA_BLOCK_LENGTH,
value, initialValue, overwrite);
}
} else if(data[block]!=value && (overwrite || block==dataNullOffset)) {
/*
* Set the repeatBlock instead of the null block or previous repeat block:
*
* If !isWritableBlock() then all entries in the block have the same value
* because it's the null block or a range block (the repeatBlock from a previous
* call to utrie2_setRange32()).
* No other blocks are used multiple times before compacting.
*
* The null block is the only non-writable block with the initialValue because
* of the repeatBlock initialization above. (If value==initialValue, then
* the repeatBlock will be the null data block.)
*
* We set our repeatBlock if the desired value differs from the block's value,
* and if we overwrite any data or if the data is all initial values
* (which is the same as the block being the null block, see above).
*/
setRepeatBlock=true;
}
if(setRepeatBlock) {
if(repeatBlock>=0) {
setIndex2Entry(i2, repeatBlock);
} else {
/* create and set and fill the repeatBlock */
repeatBlock=getDataBlock(start, true);
writeBlock(repeatBlock, value);
}
}
start+=UTRIE2_DATA_BLOCK_LENGTH;
}
if(rest>0) {
/* set partial block at [last block boundary..limit[ */
block=getDataBlock(start, true);
fillBlock(block, 0, rest, value, initialValue, overwrite);
}
return this;
}
/**
* Set the values from a Trie2.Range.
*
* All code points within the range will get the value if
* overwrite is true or if the old value is the initial value.
*
* Ranges with the lead surrogate flag set will set the alternate
* lead-surrogate values in the Trie, rather than the code point values.
*
* This function is intended to work with the ranges produced when iterating
* the contents of a source Trie.
*
* @param range contains the range of code points and the value to be set.
* @param overwrite flag for whether old non-initial values are to be overwritten
*/
public Trie2Writable setRange(Trie2.Range range, boolean overwrite) {
fHash = 0;
if (range.leadSurrogate) {
for (int c=range.startCodePoint; c<=range.endCodePoint; c++) {
if (overwrite || getFromU16SingleLead((char)c) == this.initialValue) {
setForLeadSurrogateCodeUnit((char)c, range.value);
}
}
} else {
setRange(range.startCodePoint, range.endCodePoint, range.value, overwrite);
}
return this;
}
/**
* Set a value for a UTF-16 code unit.
* Note that a Trie2 stores separate values for
* supplementary code points in the lead surrogate range
* (accessed via the plain set() and get() interfaces)
* and for lead surrogate code units.
*
* The lead surrogate code unit values are set via this function and
* read by the function getFromU16SingleLead().
*
* For code units outside of the lead surrogate range, this function
* behaves identically to set().
*
* @param codeUnit A UTF-16 code unit.
* @param value the value to be stored in the Trie2.
*/
public Trie2Writable setForLeadSurrogateCodeUnit(char codeUnit, int value) {
fHash = 0;
set(codeUnit, false, value);
return this;
}
/**
* Get the value for a code point as stored in the Trie2.
*
* @param codePoint the code point
* @return the value
*/
@Override
public int get(int codePoint) {
if (codePoint<0 || codePoint>0x10ffff) {
return errorValue;
} else {
return get(codePoint, true);
}
}
private int get(int c, boolean fromLSCP) {
int i2, block;
if(c>=highStart && (!(c>=0xd800 && c<0xdc00) || fromLSCP)) {
return data[dataLength-UTRIE2_DATA_GRANULARITY];
}
if((c>=0xd800 && c<0xdc00) && fromLSCP) {
i2=(UTRIE2_LSCP_INDEX_2_OFFSET-(0xd800>>UTRIE2_SHIFT_2))+
(c>>UTRIE2_SHIFT_2);
} else {
i2=index1[c>>UTRIE2_SHIFT_1]+
((c>>UTRIE2_SHIFT_2)&UTRIE2_INDEX_2_MASK);
}
block=index2[i2];
return data[block+(c&UTRIE2_DATA_MASK)];
}
/**
* Get a trie value for a UTF-16 code unit.
*
* This function returns the same value as get() if the input
* character is outside of the lead surrogate range
*
* There are two values stored in a Trie for inputs in the lead
* surrogate range. This function returns the alternate value,
* while Trie2.get() returns the main value.
*
* @param c the code point or lead surrogate value.
* @return the value
*/
@Override
public int getFromU16SingleLead(char c) {
return get(c, false);
}
/* compaction --------------------------------------------------------------- */
private boolean equal_int(int[] a, int s, int t, int length) {
for (int i=0; i<length; i++) {
if (a[s+i] != a[t+i]) {
return false;
}
}
return true;
}
private int findSameIndex2Block(int index2Length, int otherBlock) {
int block;
/* ensure that we do not even partially get past index2Length */
index2Length-=UTRIE2_INDEX_2_BLOCK_LENGTH;
for(block=0; block<=index2Length; ++block) {
if(equal_int(index2, block, otherBlock, UTRIE2_INDEX_2_BLOCK_LENGTH)) {
return block;
}
}
return -1;
}
private int findSameDataBlock(int dataLength, int otherBlock, int blockLength) {
int block;
/* ensure that we do not even partially get past dataLength */
dataLength-=blockLength;
for(block=0; block<=dataLength; block+=UTRIE2_DATA_GRANULARITY) {
if(equal_int(data, block, otherBlock, blockLength)) {
return block;
}
}
return -1;
}
/*
* Find the start of the last range in the trie by enumerating backward.
* Indexes for supplementary code points higher than this will be omitted.
*/
private int findHighStart(int highValue) {
int value;
int c, prev;
int i1, i2, j, i2Block, prevI2Block, block, prevBlock;
/* set variables for previous range */
if(highValue==initialValue) {
prevI2Block=index2NullOffset;
prevBlock=dataNullOffset;
} else {
prevI2Block=-1;
prevBlock=-1;
}
prev=0x110000;
/* enumerate index-2 blocks */
i1=UNEWTRIE2_INDEX_1_LENGTH;
c=prev;
while(c>0) {
i2Block=index1[--i1];
if(i2Block==prevI2Block) {
/* the index-2 block is the same as the previous one, and filled with highValue */
c-=UTRIE2_CP_PER_INDEX_1_ENTRY;
continue;
}
prevI2Block=i2Block;
if(i2Block==index2NullOffset) {
/* this is the null index-2 block */
if(highValue!=initialValue) {
return c;
}
c-=UTRIE2_CP_PER_INDEX_1_ENTRY;
} else {
/* enumerate data blocks for one index-2 block */
for(i2=UTRIE2_INDEX_2_BLOCK_LENGTH; i2>0;) {
block=index2[i2Block+ --i2];
if(block==prevBlock) {
/* the block is the same as the previous one, and filled with highValue */
c-=UTRIE2_DATA_BLOCK_LENGTH;
continue;
}
prevBlock=block;
if(block==dataNullOffset) {
/* this is the null data block */
if(highValue!=initialValue) {
return c;
}
c-=UTRIE2_DATA_BLOCK_LENGTH;
} else {
for(j=UTRIE2_DATA_BLOCK_LENGTH; j>0;) {
value=data[block+ --j];
if(value!=highValue) {
return c;
}
--c;
}
}
}
}
}
/* deliver last range */
return 0;
}
/*
* Compact a build-time trie.
*
* The compaction
* - removes blocks that are identical with earlier ones
* - overlaps adjacent blocks as much as possible (if overlap==true)
* - moves blocks in steps of the data granularity
* - moves and overlaps blocks that overlap with multiple values in the overlap region
*
* It does not
* - try to move and overlap blocks that are not already adjacent
*/
private void compactData() {
int start, newStart, movedStart;
int blockLength, overlap;
int i, mapIndex, blockCount;
/* do not compact linear-ASCII data */
newStart=UTRIE2_DATA_START_OFFSET;
for(start=0, i=0; start<newStart; start+=UTRIE2_DATA_BLOCK_LENGTH, ++i) {
map[i]=start;
}
/*
* Start with a block length of 64 for 2-byte UTF-8,
* then switch to UTRIE2_DATA_BLOCK_LENGTH.
*/
blockLength=64;
blockCount=blockLength>>UTRIE2_SHIFT_2;
for(start=newStart; start<dataLength;) {
/*
* start: index of first entry of current block
* newStart: index where the current block is to be moved
* (right after current end of already-compacted data)
*/
if(start==UNEWTRIE2_DATA_0800_OFFSET) {
blockLength=UTRIE2_DATA_BLOCK_LENGTH;
blockCount=1;
}
/* skip blocks that are not used */
if(map[start>>UTRIE2_SHIFT_2]<=0) {
/* advance start to the next block */
start+=blockLength;
/* leave newStart with the previous block! */
continue;
}
/* search for an identical block */
movedStart=findSameDataBlock(newStart, start, blockLength);
if(movedStart >= 0) {
/* found an identical block, set the other block's index value for the current block */
for(i=blockCount, mapIndex=start>>UTRIE2_SHIFT_2; i>0; --i) {
map[mapIndex++]=movedStart;
movedStart+=UTRIE2_DATA_BLOCK_LENGTH;
}
/* advance start to the next block */
start+=blockLength;
/* leave newStart with the previous block! */
continue;
}
/* see if the beginning of this block can be overlapped with the end of the previous block */
/* look for maximum overlap (modulo granularity) with the previous, adjacent block */
for(overlap=blockLength-UTRIE2_DATA_GRANULARITY;
overlap>0 && !equal_int(data, (newStart-overlap), start, overlap);
overlap-=UTRIE2_DATA_GRANULARITY) {}
if(overlap>0 || newStart<start) {
/* some overlap, or just move the whole block */
movedStart=newStart-overlap;
for(i=blockCount, mapIndex=start>>UTRIE2_SHIFT_2; i>0; --i) {
map[mapIndex++]=movedStart;
movedStart+=UTRIE2_DATA_BLOCK_LENGTH;
}
/* move the non-overlapping indexes to their new positions */
start+=overlap;
for(i=blockLength-overlap; i>0; --i) {
data[newStart++]=data[start++];
}
} else /* no overlap && newStart==start */ {
for(i=blockCount, mapIndex=start>>UTRIE2_SHIFT_2; i>0; --i) {
map[mapIndex++]=start;
start+=UTRIE2_DATA_BLOCK_LENGTH;
}
newStart=start;
}
}
/* now adjust the index-2 table */
for(i=0; i<index2Length; ++i) {
if(i==UNEWTRIE2_INDEX_GAP_OFFSET) {
/* Gap indexes are invalid (-1). Skip over the gap. */
i+=UNEWTRIE2_INDEX_GAP_LENGTH;
}
index2[i]=map[index2[i]>>UTRIE2_SHIFT_2];
}
dataNullOffset=map[dataNullOffset>>UTRIE2_SHIFT_2];
/* ensure dataLength alignment */
while((newStart&(UTRIE2_DATA_GRANULARITY-1))!=0) {
data[newStart++]=initialValue;
}
if (UTRIE2_DEBUG) {
/* we saved some space */
System.out.printf("compacting UTrie2: count of 32-bit data words %d->%d%n",
dataLength, newStart);
}
dataLength=newStart;
}
private void compactIndex2() {
int i, start, newStart, movedStart, overlap;
/* do not compact linear-BMP index-2 blocks */
newStart=UTRIE2_INDEX_2_BMP_LENGTH;
for(start=0, i=0; start<newStart; start+=UTRIE2_INDEX_2_BLOCK_LENGTH, ++i) {
map[i]=start;
}
/* Reduce the index table gap to what will be needed at runtime. */
newStart+=UTRIE2_UTF8_2B_INDEX_2_LENGTH+((highStart-0x10000)>>UTRIE2_SHIFT_1);
for(start=UNEWTRIE2_INDEX_2_NULL_OFFSET; start<index2Length;) {
/*
* start: index of first entry of current block
* newStart: index where the current block is to be moved
* (right after current end of already-compacted data)
*/
/* search for an identical block */
if( (movedStart=findSameIndex2Block(newStart, start))
>=0
) {
/* found an identical block, set the other block's index value for the current block */
map[start>>UTRIE2_SHIFT_1_2]=movedStart;
/* advance start to the next block */
start+=UTRIE2_INDEX_2_BLOCK_LENGTH;
/* leave newStart with the previous block! */
continue;
}
/* see if the beginning of this block can be overlapped with the end of the previous block */
/* look for maximum overlap with the previous, adjacent block */
for(overlap=UTRIE2_INDEX_2_BLOCK_LENGTH-1;
overlap>0 && !equal_int(index2, newStart-overlap, start, overlap);
--overlap) {}
if(overlap>0 || newStart<start) {
/* some overlap, or just move the whole block */
map[start>>UTRIE2_SHIFT_1_2]=newStart-overlap;
/* move the non-overlapping indexes to their new positions */
start+=overlap;
for(i=UTRIE2_INDEX_2_BLOCK_LENGTH-overlap; i>0; --i) {
index2[newStart++]=index2[start++];
}
} else /* no overlap && newStart==start */ {
map[start>>UTRIE2_SHIFT_1_2]=start;
start+=UTRIE2_INDEX_2_BLOCK_LENGTH;
newStart=start;
}
}
/* now adjust the index-1 table */
for(i=0; i<UNEWTRIE2_INDEX_1_LENGTH; ++i) {
index1[i]=map[index1[i]>>UTRIE2_SHIFT_1_2];
}
index2NullOffset=map[index2NullOffset>>UTRIE2_SHIFT_1_2];
/*
* Ensure data table alignment:
* Needs to be granularity-aligned for 16-bit trie
* (so that dataMove will be down-shiftable),
* and 2-aligned for uint32_t data.
*/
while((newStart&((UTRIE2_DATA_GRANULARITY-1)|1))!=0) {
/* Arbitrary value: 0x3fffc not possible for real data. */
index2[newStart++]=0x0000ffff<<UTRIE2_INDEX_SHIFT;
}
if (UTRIE2_DEBUG) {
/* we saved some space */
System.out.printf("compacting UTrie2: count of 16-bit index-2 words %d->%d%n",
index2Length, newStart);
}
index2Length=newStart;
}
private void compactTrie() {
int localHighStart;
int suppHighStart;
int highValue;
/* find highStart and round it up */
highValue=get(0x10ffff);
localHighStart=findHighStart(highValue);
localHighStart=(localHighStart+(UTRIE2_CP_PER_INDEX_1_ENTRY-1))&~(UTRIE2_CP_PER_INDEX_1_ENTRY-1);
if(localHighStart==0x110000) {
highValue=errorValue;
}
/*
* Set trie->highStart only after utrie2_get32(trie, highStart).
* Otherwise utrie2_get32(trie, highStart) would try to read the highValue.
*/
this.highStart=localHighStart;
if (UTRIE2_DEBUG) {
System.out.printf("UTrie2: highStart U+%04x highValue 0x%x initialValue 0x%x%n",
highStart, highValue, initialValue);
}
if(highStart<0x110000) {
/* Blank out [highStart..10ffff] to release associated data blocks. */
suppHighStart= highStart<=0x10000 ? 0x10000 : highStart;
setRange(suppHighStart, 0x10ffff, initialValue, true);
}
compactData();
if(highStart>0x10000) {
compactIndex2();
} else {
if (UTRIE2_DEBUG) {
System.out.printf("UTrie2: highStart U+%04x count of 16-bit index-2 words %d->%d%n",
highStart, index2Length, UTRIE2_INDEX_1_OFFSET);
}
}
/*
* Store the highValue in the data array and round up the dataLength.
* Must be done after compactData() because that assumes that dataLength
* is a multiple of UTRIE2_DATA_BLOCK_LENGTH.
*/
data[dataLength++]=highValue;
while((dataLength&(UTRIE2_DATA_GRANULARITY-1))!=0) {
data[dataLength++]=initialValue;
}
isCompacted=true;
}
/**
* Produce an optimized, read-only Trie2_16 from this writable Trie.
* The data values outside of the range that will fit in a 16 bit
* unsigned value will be truncated.
*/
public Trie2_16 toTrie2_16() {
Trie2_16 frozenTrie = new Trie2_16();
freeze(frozenTrie, ValueWidth.BITS_16);
return frozenTrie;
}
/**
* Produce an optimized, read-only Trie2_32 from this writable Trie.
*
*/
public Trie2_32 toTrie2_32() {
Trie2_32 frozenTrie = new Trie2_32();
freeze(frozenTrie, ValueWidth.BITS_32);
return frozenTrie;
}
/**
* Maximum length of the runtime index array.
* Limited by its own 16-bit index values, and by uint16_t UTrie2Header.indexLength.
* (The actual maximum length is lower,
* (0x110000>>UTRIE2_SHIFT_2)+UTRIE2_UTF8_2B_INDEX_2_LENGTH+UTRIE2_MAX_INDEX_1_LENGTH.)
*/
private static final int UTRIE2_MAX_INDEX_LENGTH = 0xffff;
/**
* Maximum length of the runtime data array.
* Limited by 16-bit index values that are left-shifted by UTRIE2_INDEX_SHIFT,
* and by uint16_t UTrie2Header.shiftedDataLength.
*/
private static final int UTRIE2_MAX_DATA_LENGTH = 0xffff<<UTRIE2_INDEX_SHIFT;
/* Compact the data and then populate an optimized read-only Trie. */
private void freeze(Trie2 dest, ValueWidth valueBits) {
int i;
int allIndexesLength;
int dataMove; /* >0 if the data is moved to the end of the index array */
/* compact if necessary */
if(!isCompacted) {
compactTrie();
}
if(highStart<=0x10000) {
allIndexesLength=UTRIE2_INDEX_1_OFFSET;
} else {
allIndexesLength=index2Length;
}
if(valueBits==ValueWidth.BITS_16) {
dataMove=allIndexesLength;
} else {
dataMove=0;
}
/* are indexLength and dataLength within limits? */
if( /* for unshifted indexLength */
allIndexesLength>UTRIE2_MAX_INDEX_LENGTH ||
/* for unshifted dataNullOffset */
(dataMove+dataNullOffset)>0xffff ||
/* for unshifted 2-byte UTF-8 index-2 values */
(dataMove+UNEWTRIE2_DATA_0800_OFFSET)>0xffff ||
/* for shiftedDataLength */
(dataMove+dataLength)>UTRIE2_MAX_DATA_LENGTH) {
throw new UnsupportedOperationException("Trie2 data is too large.");
}
/* calculate the sizes of, and allocate, the index and data arrays */
int indexLength = allIndexesLength;
if (valueBits==ValueWidth.BITS_16) {
indexLength += dataLength;
} else {
dest.data32 = new int[dataLength];
}
dest.index = new char[indexLength];
dest.indexLength = allIndexesLength;
dest.dataLength = dataLength;
if(highStart<=0x10000) {
dest.index2NullOffset = 0xffff;
} else {
dest.index2NullOffset = UTRIE2_INDEX_2_OFFSET + index2NullOffset;
}
dest.initialValue = initialValue;
dest.errorValue = errorValue;
dest.highStart = highStart;
dest.highValueIndex = dataMove + dataLength - UTRIE2_DATA_GRANULARITY;
dest.dataNullOffset = (dataMove+dataNullOffset);
// Create a header and set the its fields.
// (This is only used in the event that we serialize the Trie, but is
// convenient to do here.)
dest.header = new Trie2.UTrie2Header();
dest.header.signature = 0x54726932; /* "Tri2" */
dest.header.options = valueBits==ValueWidth.BITS_16 ? 0 : 1;
dest.header.indexLength = dest.indexLength;
dest.header.shiftedDataLength = dest.dataLength>>UTRIE2_INDEX_SHIFT;
dest.header.index2NullOffset = dest.index2NullOffset;
dest.header.dataNullOffset = dest.dataNullOffset;
dest.header.shiftedHighStart = dest.highStart>>UTRIE2_SHIFT_1;
/* write the index-2 array values shifted right by UTRIE2_INDEX_SHIFT, after adding dataMove */
int destIdx = 0;
for(i=0; i<UTRIE2_INDEX_2_BMP_LENGTH; i++) {
dest.index[destIdx++] = (char)((index2[i]+dataMove) >> UTRIE2_INDEX_SHIFT);
}
if (UTRIE2_DEBUG) {
System.out.println("\n\nIndex2 for BMP limit is " + Integer.toHexString(destIdx));
}
/* write UTF-8 2-byte index-2 values, not right-shifted */
for(i=0; i<(0xc2-0xc0); ++i) { /* C0..C1 */
dest.index[destIdx++] = (char)(dataMove+UTRIE2_BAD_UTF8_DATA_OFFSET);
}
for(; i<(0xe0-0xc0); ++i) { /* C2..DF */
dest.index[destIdx++]=(char)(dataMove+index2[i<<(6-UTRIE2_SHIFT_2)]);
}
if (UTRIE2_DEBUG) {
System.out.println("Index2 for UTF-8 2byte values limit is " + Integer.toHexString(destIdx));
}
if(highStart>0x10000) {
int index1Length = (highStart-0x10000)>>UTRIE2_SHIFT_1;
int index2Offset = UTRIE2_INDEX_2_BMP_LENGTH + UTRIE2_UTF8_2B_INDEX_2_LENGTH + index1Length;
/* write 16-bit index-1 values for supplementary code points */
//p=(uint32_t *)newTrie->index1+UTRIE2_OMITTED_BMP_INDEX_1_LENGTH;
for(i=0; i<index1Length; i++) {
//*dest16++=(uint16_t)(UTRIE2_INDEX_2_OFFSET + *p++);
dest.index[destIdx++] = (char)(UTRIE2_INDEX_2_OFFSET + index1[i+UTRIE2_OMITTED_BMP_INDEX_1_LENGTH]);
}
if (UTRIE2_DEBUG) {
System.out.println("Index 1 for supplementals, limit is " + Integer.toHexString(destIdx));
}
/*
* write the index-2 array values for supplementary code points,
* shifted right by UTRIE2_INDEX_SHIFT, after adding dataMove
*/
for(i=0; i<index2Length-index2Offset; i++) {
dest.index[destIdx++] = (char)((dataMove + index2[index2Offset+i])>>UTRIE2_INDEX_SHIFT);
}
if (UTRIE2_DEBUG) {
System.out.println("Index 2 for supplementals, limit is " + Integer.toHexString(destIdx));
}
}
/* write the 16/32-bit data array */
switch(valueBits) {
case BITS_16:
/* write 16-bit data values */
assert(destIdx == dataMove);
dest.data16 = destIdx;
for(i=0; i<dataLength; i++) {
dest.index[destIdx++] = (char)data[i];
}
break;
case BITS_32:
/* write 32-bit data values */
for (i=0; i<dataLength; i++) {
dest.data32[i] = this.data[i];
}
break;
}
// The writable, but compressed, Trie2 stays around unless the caller drops its references to it.
}
/* Start with allocation of 16k data entries. */
private static final int UNEWTRIE2_INITIAL_DATA_LENGTH = 1<<14;
/* Grow about 8x each time. */
private static final int UNEWTRIE2_MEDIUM_DATA_LENGTH = 1<<17;
/** The null index-2 block, following the gap in the index-2 table. */
private static final int UNEWTRIE2_INDEX_2_NULL_OFFSET = UNEWTRIE2_INDEX_GAP_OFFSET + UNEWTRIE2_INDEX_GAP_LENGTH;
/** The start of allocated index-2 blocks. */
private static final int UNEWTRIE2_INDEX_2_START_OFFSET = UNEWTRIE2_INDEX_2_NULL_OFFSET + UTRIE2_INDEX_2_BLOCK_LENGTH;
/**
* The null data block.
* Length 64=0x40 even if UTRIE2_DATA_BLOCK_LENGTH is smaller,
* to work with 6-bit trail bytes from 2-byte UTF-8.
*/
private static final int UNEWTRIE2_DATA_NULL_OFFSET = UTRIE2_DATA_START_OFFSET;
/** The start of allocated data blocks. */
private static final int UNEWTRIE2_DATA_START_OFFSET = UNEWTRIE2_DATA_NULL_OFFSET+0x40;
/**
* The start of data blocks for U+0800 and above.
* Below, compaction uses a block length of 64 for 2-byte UTF-8.
* From here on, compaction uses UTRIE2_DATA_BLOCK_LENGTH.
* Data values for 0x780 code points beyond ASCII.
*/
private static final int UNEWTRIE2_DATA_0800_OFFSET = UNEWTRIE2_DATA_START_OFFSET+0x780;
//
// Private data members. From struct UNewTrie2 in ICU4C
//
private int[] index1 = new int[UNEWTRIE2_INDEX_1_LENGTH];
private int[] index2 = new int[UNEWTRIE2_MAX_INDEX_2_LENGTH];
private int[] data;
private int index2Length;
private int dataCapacity;
private int firstFreeBlock;
private int index2NullOffset;
private boolean isCompacted;
/*
* Multi-purpose per-data-block table.
*
* Before compacting:
*
* Per-data-block reference counters/free-block list.
* 0: unused
* >0: reference counter (number of index-2 entries pointing here)
* <0: next free data block in free-block list
*
* While compacting:
*
* Map of adjusted indexes, used in compactData() and compactIndex2().
* Maps from original indexes to new ones.
*/
private int[] map = new int[UNEWTRIE2_MAX_DATA_LENGTH>>UTRIE2_SHIFT_2];
private boolean UTRIE2_DEBUG = false;
}
Reference in New Issue Copy Permalink