1 /* 2 * Copyright (c) 1996, 2011, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 /* 27 * (C) Copyright Taligent, Inc. 1996 - All Rights Reserved 28 * (C) Copyright IBM Corp. 1996 - All Rights Reserved 29 * 30 * The original version of this source code and documentation is copyrighted 31 * and owned by Taligent, Inc., a wholly-owned subsidiary of IBM. These 32 * materials are provided under terms of a License Agreement between Taligent 33 * and Sun. This technology is protected by multiple US and International 34 * patents. This notice and attribution to Taligent may not be removed. 35 * Taligent is a registered trademark of Taligent, Inc. 36 * 37 */ 38 39 package sun.text; 40 41 42 /** 43 * class CompactATypeArray : use only on primitive data types 44 * Provides a compact way to store information that is indexed by Unicode 45 * values, such as character properties, types, keyboard values, etc.This 46 * is very useful when you have a block of Unicode data that contains 47 * significant values while the rest of the Unicode data is unused in the 48 * application or when you have a lot of redundance, such as where all 21,000 49 * Han ideographs have the same value. However, lookup is much faster than a 50 * hash table. 51 * A compact array of any primitive data type serves two purposes: 52 * <UL type = circle> 53 * <LI>Fast access of the indexed values. 54 * <LI>Smaller memory footprint. 55 * </UL> 56 * A compact array is composed of a index array and value array. The index 57 * array contains the indicies of Unicode characters to the value array. 58 * 59 * @see CompactIntArray 60 * @see CompactShortArray 61 * @author Helena Shih 62 */ 63 public final class CompactByteArray implements Cloneable { 64 65 /** 66 * The total number of Unicode characters. 67 */ 68 public static final int UNICODECOUNT =65536; 69 70 /** 71 * Constructor for CompactByteArray. 72 * @param defaultValue the default value of the compact array. 73 */ 74 public CompactByteArray(byte defaultValue) 75 { 76 int i; 77 values = new byte[UNICODECOUNT]; 78 indices = new short[INDEXCOUNT]; 79 hashes = new int[INDEXCOUNT]; 80 for (i = 0; i < UNICODECOUNT; ++i) { 81 values[i] = defaultValue; 82 } 83 for (i = 0; i < INDEXCOUNT; ++i) { 84 indices[i] = (short)(i<<BLOCKSHIFT); 85 hashes[i] = 0; 86 } 87 isCompact = false; 88 } 89 90 /** 91 * Constructor for CompactByteArray. 92 * @param indexArray the indicies of the compact array. 93 * @param newValues the values of the compact array. 94 * @exception IllegalArgumentException If index is out of range. 95 */ 96 public CompactByteArray(short indexArray[], 97 byte newValues[]) 98 { 99 int i; 100 if (indexArray.length != INDEXCOUNT) 101 throw new IllegalArgumentException("Index out of bounds!"); 102 for (i = 0; i < INDEXCOUNT; ++i) { 103 short index = indexArray[i]; 104 if ((index < 0) || (index >= newValues.length+BLOCKCOUNT)) 105 throw new IllegalArgumentException("Index out of bounds!"); 106 } 107 indices = indexArray; 108 values = newValues; 109 isCompact = true; 110 } 111 112 /** 113 * Get the mapped value of a Unicode character. 114 * @param index the character to get the mapped value with 115 * @return the mapped value of the given character 116 */ 117 public byte elementAt(char index) 118 { 119 return (values[(indices[index >> BLOCKSHIFT] & 0xFFFF) 120 + (index & BLOCKMASK)]); 121 } 122 /** 123 * Set a new value for a Unicode character. 124 * Set automatically expands the array if it is compacted. 125 * @param index the character to set the mapped value with 126 * @param value the new mapped value 127 */ 128 public void setElementAt(char index, byte value) 129 { 130 if (isCompact) 131 expand(); 132 values[(int)index] = value; 133 touchBlock(index >> BLOCKSHIFT, value); 134 } 135 136 /** 137 * Set new values for a range of Unicode character. 138 * @param start the starting offset o of the range 139 * @param end the ending offset of the range 140 * @param value the new mapped value 141 */ 142 public void setElementAt(char start, char end, byte value) 143 { 144 int i; 145 if (isCompact) { 146 expand(); 147 } 148 for (i = start; i <= end; ++i) { 149 values[i] = value; 150 touchBlock(i >> BLOCKSHIFT, value); 151 } 152 } 153 154 /** 155 *Compact the array. 156 */ 157 public void compact() 158 { 159 if (!isCompact) { 160 int limitCompacted = 0; 161 int iBlockStart = 0; 162 short iUntouched = -1; 163 164 for (int i = 0; i < indices.length; ++i, iBlockStart += BLOCKCOUNT) { 165 indices[i] = -1; 166 boolean touched = blockTouched(i); 167 if (!touched && iUntouched != -1) { 168 // If no values in this block were set, we can just set its 169 // index to be the same as some other block with no values 170 // set, assuming we've seen one yet. 171 indices[i] = iUntouched; 172 } else { 173 int jBlockStart = 0; 174 int j = 0; 175 for (j = 0; j < limitCompacted; 176 ++j, jBlockStart += BLOCKCOUNT) { 177 if (hashes[i] == hashes[j] && 178 arrayRegionMatches(values, iBlockStart, 179 values, jBlockStart, BLOCKCOUNT)) { 180 indices[i] = (short)jBlockStart; 181 break; 182 } 183 } 184 if (indices[i] == -1) { 185 // we didn't match, so copy & update 186 System.arraycopy(values, iBlockStart, 187 values, jBlockStart, BLOCKCOUNT); 188 indices[i] = (short)jBlockStart; 189 hashes[j] = hashes[i]; 190 ++limitCompacted; 191 192 if (!touched) { 193 // If this is the first untouched block we've seen, 194 // remember its index. 195 iUntouched = (short)jBlockStart; 196 } 197 } 198 } 199 } 200 // we are done compacting, so now make the array shorter 201 int newSize = limitCompacted*BLOCKCOUNT; 202 byte[] result = new byte[newSize]; 203 System.arraycopy(values, 0, result, 0, newSize); 204 values = result; 205 isCompact = true; 206 hashes = null; 207 } 208 } 209 210 /** 211 * Convenience utility to compare two arrays of doubles. 212 * @param len the length to compare. 213 * The start indices and start+len must be valid. 214 */ 215 static final boolean arrayRegionMatches(byte[] source, int sourceStart, 216 byte[] target, int targetStart, 217 int len) 218 { 219 int sourceEnd = sourceStart + len; 220 int delta = targetStart - sourceStart; 221 for (int i = sourceStart; i < sourceEnd; i++) { 222 if (source[i] != target[i + delta]) 223 return false; 224 } 225 return true; 226 } 227 228 /** 229 * Remember that a specified block was "touched", i.e. had a value set. 230 * Untouched blocks can be skipped when compacting the array 231 */ 232 private final void touchBlock(int i, int value) { 233 hashes[i] = (hashes[i] + (value<<1)) | 1; 234 } 235 236 /** 237 * Query whether a specified block was "touched", i.e. had a value set. 238 * Untouched blocks can be skipped when compacting the array 239 */ 240 private final boolean blockTouched(int i) { 241 return hashes[i] != 0; 242 } 243 244 /** For internal use only. Do not modify the result, the behavior of 245 * modified results are undefined. 246 */ 247 public short getIndexArray()[] 248 { 249 return indices; 250 } 251 252 /** For internal use only. Do not modify the result, the behavior of 253 * modified results are undefined. 254 */ 255 public byte getStringArray()[] 256 { 257 return values; 258 } 259 260 /** 261 * Overrides Cloneable 262 */ 263 public Object clone() 264 { 265 try { 266 CompactByteArray other = (CompactByteArray) super.clone(); 267 other.values = values.clone(); 268 other.indices = indices.clone(); 269 if (hashes != null) other.hashes = hashes.clone(); 270 return other; 271 } catch (CloneNotSupportedException e) { 272 throw new InternalError(e); 273 } 274 } 275 276 /** 277 * Compares the equality of two compact array objects. 278 * @param obj the compact array object to be compared with this. 279 * @return true if the current compact array object is the same 280 * as the compact array object obj; false otherwise. 281 */ 282 public boolean equals(Object obj) { 283 if (obj == null) return false; 284 if (this == obj) // quick check 285 return true; 286 if (getClass() != obj.getClass()) // same class? 287 return false; 288 CompactByteArray other = (CompactByteArray) obj; 289 for (int i = 0; i < UNICODECOUNT; i++) { 290 // could be sped up later 291 if (elementAt((char)i) != other.elementAt((char)i)) 292 return false; 293 } 294 return true; // we made it through the guantlet. 295 } 296 297 /** 298 * Generates the hash code for the compact array object 299 */ 300 301 public int hashCode() { 302 int result = 0; 303 int increment = Math.min(3, values.length/16); 304 for (int i = 0; i < values.length; i+= increment) { 305 result = result * 37 + values[i]; 306 } 307 return result; 308 } 309 310 // -------------------------------------------------------------- 311 // package private 312 // -------------------------------------------------------------- 313 /** 314 * Expanding takes the array back to a 65536 element array. 315 */ 316 private void expand() 317 { 318 int i; 319 if (isCompact) { 320 byte[] tempArray; 321 hashes = new int[INDEXCOUNT]; 322 tempArray = new byte[UNICODECOUNT]; 323 for (i = 0; i < UNICODECOUNT; ++i) { 324 byte value = elementAt((char)i); 325 tempArray[i] = value; 326 touchBlock(i >> BLOCKSHIFT, value); 327 } 328 for (i = 0; i < INDEXCOUNT; ++i) { 329 indices[i] = (short)(i<<BLOCKSHIFT); 330 } 331 values = null; 332 values = tempArray; 333 isCompact = false; 334 } 335 } 336 337 private byte[] getArray() 338 { 339 return values; 340 } 341 342 private static final int BLOCKSHIFT =7; 343 private static final int BLOCKCOUNT =(1<<BLOCKSHIFT); 344 private static final int INDEXSHIFT =(16-BLOCKSHIFT); 345 private static final int INDEXCOUNT =(1<<INDEXSHIFT); 346 private static final int BLOCKMASK = BLOCKCOUNT - 1; 347 348 private byte[] values; // char -> short (char parameterized short) 349 private short indices[]; 350 private boolean isCompact; 351 private int[] hashes; 352 };