Trie.java
// © 2016 and later: Unicode, Inc. and others.
// License & terms of use: http://www.unicode.org/copyright.html
/*
******************************************************************************
* Copyright (C) 1996-2015, International Business Machines Corporation and
* others. All Rights Reserved.
******************************************************************************
*/
package com.ibm.icu.impl;
import com.ibm.icu.lang.UCharacter;
import com.ibm.icu.text.UTF16;
import java.nio.ByteBuffer;
import java.util.Arrays;
/**
* A trie is a kind of compressed, serializable table of values associated with Unicode code points
* (0..0x10ffff).
*
* <p>This class defines the basic structure of a trie and provides methods to <b>retrieve the
* offsets to the actual data</b>.
*
* <p>Data will be the form of an array of basic types, char or int.
*
* <p>The actual data format will have to be specified by the user in the inner static interface
* com.ibm.icu.impl.Trie.DataManipulate.
*
* <p>This trie implementation is optimized for getting offset while walking forward through a
* UTF-16 string. Therefore, the simplest and fastest access macros are the fromLead() and
* fromOffsetTrail() methods. The fromBMP() method are a little more complicated; they get offsets
* even for lead surrogate codepoints, while the fromLead() method get special "folded" offsets for
* lead surrogate code units if there is relevant data associated with them. From such a folded
* offsets, an offset needs to be extracted to supply to the fromOffsetTrail() methods. To handle
* such supplementary codepoints, some offset information are kept in the data.
*
* <p>Methods in com.ibm.icu.impl.Trie.DataManipulate are called to retrieve that offset from the
* folded value for the lead surrogate unit.
*
* <p>For examples of use, see com.ibm.icu.impl.CharTrie or com.ibm.icu.impl.IntTrie.
*
* @author synwee
* @see com.ibm.icu.impl.CharTrie
* @see com.ibm.icu.impl.IntTrie
* @since release 2.1, Jan 01 2002
*/
public abstract class Trie {
// public class declaration ----------------------------------------
/**
* Character data in com.ibm.impl.Trie have different user-specified format for different
* purposes. This interface specifies methods to be implemented in order for com.ibm.impl.Trie,
* to surrogate offset information encapsulated within the data.
*/
public static interface DataManipulate {
/**
* Called by com.ibm.icu.impl.Trie to extract from a lead surrogate's data the index array
* offset of the indexes for that lead surrogate.
*
* @param value data value for a surrogate from the trie, including the folding offset
* @return data offset or 0 if there is no data for the lead surrogate
*/
public int getFoldingOffset(int value);
}
// default implementation
private static class DefaultGetFoldingOffset implements DataManipulate {
@Override
public int getFoldingOffset(int value) {
return value;
}
}
// public methods --------------------------------------------------
/**
* Determines if this trie has a linear latin 1 array
*
* @return true if this trie has a linear latin 1 array, false otherwise
*/
public final boolean isLatin1Linear() {
return m_isLatin1Linear_;
}
/**
* Checks if the argument Trie has the same data as this Trie. Attributes are checked but not
* the index data.
*
* @param other Trie to check
* @return true if the argument Trie has the same data as this Trie, false otherwise
*/
/// CLOVER:OFF
@Override
public boolean equals(Object other) {
if (other == this) {
return true;
}
if (!(other instanceof Trie)) {
return false;
}
Trie othertrie = (Trie) other;
return m_isLatin1Linear_ == othertrie.m_isLatin1Linear_
&& m_options_ == othertrie.m_options_
&& m_dataLength_ == othertrie.m_dataLength_
&& Arrays.equals(m_index_, othertrie.m_index_);
}
@Override
public int hashCode() {
assert false : "hashCode not designed";
return 42;
}
/// CLOVER:ON
/**
* Gets the serialized data file size of the Trie. This is used during trie data reading for
* size checking purposes.
*
* @return size size of serialized trie data file in terms of the number of bytes
*/
public int getSerializedDataSize() {
// includes signature, option, dataoffset and datalength output
int result = (4 << 2);
result += (m_dataOffset_ << 1);
if (isCharTrie()) {
result += (m_dataLength_ << 1);
} else if (isIntTrie()) {
result += (m_dataLength_ << 2);
}
return result;
}
// protected constructor -------------------------------------------
/**
* Trie constructor for CharTrie use.
*
* @param bytes data of an ICU data file, containing the trie
* @param dataManipulate object containing the information to parse the trie data
*/
protected Trie(ByteBuffer bytes, DataManipulate dataManipulate) {
// Magic number to authenticate the data.
int signature = bytes.getInt();
m_options_ = bytes.getInt();
if (!checkHeader(signature)) {
throw new IllegalArgumentException(
"ICU data file error: Trie header authentication failed, please check if you have the most updated ICU data file");
}
if (dataManipulate != null) {
m_dataManipulate_ = dataManipulate;
} else {
m_dataManipulate_ = new DefaultGetFoldingOffset();
}
m_isLatin1Linear_ = (m_options_ & HEADER_OPTIONS_LATIN1_IS_LINEAR_MASK_) != 0;
m_dataOffset_ = bytes.getInt();
m_dataLength_ = bytes.getInt();
unserialize(bytes);
}
/**
* Trie constructor
*
* @param index array to be used for index
* @param options used by the trie
* @param dataManipulate object containing the information to parse the trie data
*/
protected Trie(char index[], int options, DataManipulate dataManipulate) {
m_options_ = options;
if (dataManipulate != null) {
m_dataManipulate_ = dataManipulate;
} else {
m_dataManipulate_ = new DefaultGetFoldingOffset();
}
m_isLatin1Linear_ = (m_options_ & HEADER_OPTIONS_LATIN1_IS_LINEAR_MASK_) != 0;
m_index_ = index;
m_dataOffset_ = m_index_.length;
}
// protected data members ------------------------------------------
/**
* Lead surrogate code points' index displacement in the index array. 0x10000-0xd800=0x2800
* 0x2800 >> INDEX_STAGE_1_SHIFT_
*/
protected static final int LEAD_INDEX_OFFSET_ = 0x2800 >> 5;
/** Shift size for shifting right the input index. 1..9 */
protected static final int INDEX_STAGE_1_SHIFT_ = 5;
/**
* Shift size for shifting left the index array values. Increases possible data size with 16-bit
* index values at the cost of compactability. This requires blocks of stage 2 data to be
* aligned by DATA_GRANULARITY. 0..INDEX_STAGE_1_SHIFT
*/
protected static final int INDEX_STAGE_2_SHIFT_ = 2;
/** Number of data values in a stage 2 (data array) block. */
protected static final int DATA_BLOCK_LENGTH = 1 << INDEX_STAGE_1_SHIFT_;
/** Mask for getting the lower bits from the input index. DATA_BLOCK_LENGTH - 1. */
protected static final int INDEX_STAGE_3_MASK_ = DATA_BLOCK_LENGTH - 1;
/** Number of bits of a trail surrogate that are used in index table lookups. */
protected static final int SURROGATE_BLOCK_BITS = 10 - INDEX_STAGE_1_SHIFT_;
/**
* Number of index (stage 1) entries per lead surrogate. Same as number of index entries for
* 1024 trail surrogates, ==0x400>>INDEX_STAGE_1_SHIFT_
*/
protected static final int SURROGATE_BLOCK_COUNT = (1 << SURROGATE_BLOCK_BITS);
/** Length of the BMP portion of the index (stage 1) array. */
protected static final int BMP_INDEX_LENGTH = 0x10000 >> INDEX_STAGE_1_SHIFT_;
/** Surrogate mask to use when shifting offset to retrieve supplementary values */
protected static final int SURROGATE_MASK_ = 0x3FF;
/** Index or UTF16 characters */
protected char m_index_[];
/**
* Internal TrieValue which handles the parsing of the data value. This class is to be
* implemented by the user
*/
protected DataManipulate m_dataManipulate_;
/**
* Start index of the data portion of the trie. CharTrie combines index and data into a char
* array, so this is used to indicate the initial offset to the data portion. Note this index
* always points to the initial value.
*/
protected int m_dataOffset_;
/** Length of the data array */
protected int m_dataLength_;
// protected methods -----------------------------------------------
/**
* Gets the offset to the data which the surrogate pair points to.
*
* @param lead lead surrogate
* @param trail trailing surrogate
* @return offset to data
*/
protected abstract int getSurrogateOffset(char lead, char trail);
/**
* Gets the value at the argument index
*
* @param index value at index will be retrieved
* @return 32 bit value
*/
protected abstract int getValue(int index);
/**
* Gets the default initial value
*
* @return 32 bit value
*/
protected abstract int getInitialValue();
/**
* Gets the offset to the data which the index ch after variable offset points to. Note for
* locating a non-supplementary character data offset, calling
*
* <p>getRawOffset(0, ch); will do. Otherwise if it is a supplementary character formed by
* surrogates lead and trail. Then we would have to call getRawOffset() with
* getFoldingIndexOffset(). See getSurrogateOffset().
*
* @param offset index offset which ch is to start from
* @param ch index to be used after offset
* @return offset to the data
*/
protected final int getRawOffset(int offset, char ch) {
return (m_index_[offset + (ch >> INDEX_STAGE_1_SHIFT_)] << INDEX_STAGE_2_SHIFT_)
+ (ch & INDEX_STAGE_3_MASK_);
}
/**
* Gets the offset to data which the BMP character points to Treats a lead surrogate as a normal
* code point.
*
* @param ch BMP character
* @return offset to data
*/
protected final int getBMPOffset(char ch) {
return (ch >= UTF16.LEAD_SURROGATE_MIN_VALUE && ch <= UTF16.LEAD_SURROGATE_MAX_VALUE)
? getRawOffset(LEAD_INDEX_OFFSET_, ch)
: getRawOffset(0, ch);
// using a getRawOffset(ch) makes no diff
}
/**
* Gets the offset to the data which this lead surrogate character points to. Data at the
* returned offset may contain folding offset information for the next trailing surrogate
* character.
*
* @param ch lead surrogate character
* @return offset to data
*/
protected final int getLeadOffset(char ch) {
return getRawOffset(0, ch);
}
/**
* Internal trie getter from a code point. Could be faster(?) but longer with if((c32)<=0xd7ff)
* { (result)=_TRIE_GET_RAW(trie, data, 0, c32); } Gets the offset to data which the codepoint
* points to
*
* @param ch codepoint
* @return offset to data
*/
protected final int getCodePointOffset(int ch) {
// if ((ch >> 16) == 0) slower
if (ch < 0) {
return -1;
} else if (ch < UTF16.LEAD_SURROGATE_MIN_VALUE) {
// fastpath for the part of the BMP below surrogates (D800) where getRawOffset() works
return getRawOffset(0, (char) ch);
} else if (ch < UTF16.SUPPLEMENTARY_MIN_VALUE) {
// BMP codepoint
return getBMPOffset((char) ch);
} else if (ch <= UCharacter.MAX_VALUE) {
// look at the construction of supplementary characters
// trail forms the ends of it.
return getSurrogateOffset(UTF16.getLeadSurrogate(ch), (char) (ch & SURROGATE_MASK_));
} else {
// return -1 if there is an error, in this case we return
return -1;
}
}
/**
* Parses the byte buffer and creates the trie index with it.
*
* <p>The position of the input ByteBuffer must be right after the trie header.
*
* <p>This is overwritten by the child classes.
*
* @param bytes buffer containing trie data
*/
protected void unserialize(ByteBuffer bytes) {
m_index_ = ICUBinary.getChars(bytes, m_dataOffset_, 0);
}
/**
* Determines if this is a 32 bit trie
*
* @return true if options specifies this is a 32 bit trie
*/
protected final boolean isIntTrie() {
return (m_options_ & HEADER_OPTIONS_DATA_IS_32_BIT_) != 0;
}
/**
* Determines if this is a 16 bit trie
*
* @return true if this is a 16 bit trie
*/
protected final boolean isCharTrie() {
return (m_options_ & HEADER_OPTIONS_DATA_IS_32_BIT_) == 0;
}
// private data members --------------------------------------------
// struct UTrieHeader {
// int32_t signature;
// int32_t options (a bit field)
// int32_t indexLength
// int32_t dataLength
/** Size of Trie header in bytes */
protected static final int HEADER_LENGTH_ = 4 * 4;
/** Latin 1 option mask */
protected static final int HEADER_OPTIONS_LATIN1_IS_LINEAR_MASK_ = 0x200;
/** Constant number to authenticate the byte block */
protected static final int HEADER_SIGNATURE_ = 0x54726965;
/** Header option formatting */
private static final int HEADER_OPTIONS_SHIFT_MASK_ = 0xF;
protected static final int HEADER_OPTIONS_INDEX_SHIFT_ = 4;
protected static final int HEADER_OPTIONS_DATA_IS_32_BIT_ = 0x100;
/** Flag indicator for Latin quick access data block */
private boolean m_isLatin1Linear_;
/**
* Trie options field.
*
* <p>options bit field:<br>
* 9 1 = Latin-1 data is stored linearly at data + DATA_BLOCK_LENGTH<br>
* 8 0 = 16-bit data, 1=32-bit data<br>
* 7..4 INDEX_STAGE_1_SHIFT // 0..INDEX_STAGE_2_SHIFT<br>
* 3..0 INDEX_STAGE_2_SHIFT // 1..9<br>
*/
private int m_options_;
// private methods ---------------------------------------------------
/**
* Authenticates raw data header. Checking the header information, signature and options.
*
* @param signature This contains the options and type of a Trie
* @return true if the header is authenticated valid
*/
private final boolean checkHeader(int signature) {
// check the signature
// Trie in big-endian US-ASCII (0x54726965).
// Magic number to authenticate the data.
if (signature != HEADER_SIGNATURE_) {
return false;
}
if ((m_options_ & HEADER_OPTIONS_SHIFT_MASK_) != INDEX_STAGE_1_SHIFT_
|| ((m_options_ >> HEADER_OPTIONS_INDEX_SHIFT_) & HEADER_OPTIONS_SHIFT_MASK_)
!= INDEX_STAGE_2_SHIFT_) {
return false;
}
return true;
}
}