001: /*
002: * $Id: CharStringConverter.java,v 1.3 2004/07/08 08:01:45 yuvalo Exp $
003: *
004: * (C) Copyright 2002-2004 by Yuval Oren. All rights reserved.
005: *
006: * Licensed under the Apache License, Version 2.0 (the "License");
007: * you may not use this file except in compliance with the License.
008: * You may obtain a copy of the License at
009: *
010: * http://www.apache.org/licenses/LICENSE-2.0
011: *
012: * Unless required by applicable law or agreed to in writing, software
013: * distributed under the License is distributed on an "AS IS" BASIS,
014: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015: * See the License for the specific language governing permissions and
016: * limitations under the License.
017: */
018:
019: package com.bluecast.util;
020:
021: import java.io.*;
022: import java.util.*;
023:
024: /**
025: * A fast way to convert character arrays into Strings. This class maintains
026: * a hashtable of char[] -> String mappings. Returned Strings are guaranteed
027: * to be internalized.
028: *
029: * @author Yuval Oren, yuval@bluecast.com
030: * @version $Revision: 1.3 $
031: */
032: final public class CharStringConverter {
033: private static final float DEFAULT_LOAD = 0.70F;
034: private float loadFactor;
035: private int numEntries = 0;
036: private int maxEntries;
037: private int hashmask;
038: private char[][] keys;
039: private String[] values;
040:
041: public CharStringConverter(int initialCapacity, float loadFactor) {
042: if (initialCapacity < 0) {
043: throw new IllegalArgumentException(
044: "Illegal initial capacity: " + initialCapacity);
045: }
046: if (loadFactor < 0 || loadFactor > 1) {
047: throw new IllegalArgumentException("Illegal load factor: "
048: + loadFactor);
049: }
050: int desiredSize = (int) ((float) initialCapacity / loadFactor);
051: int size = 16;
052: while (size < desiredSize) {
053: size <<= 1;
054: }
055: hashmask = size - 1;
056: maxEntries = (int) (size * loadFactor);
057: keys = new char[size][];
058: values = new String[size];
059: this .loadFactor = loadFactor;
060: }
061:
062: public CharStringConverter() {
063: this (0, DEFAULT_LOAD);
064: }
065:
066: public CharStringConverter(int initialCapacity) {
067: this (initialCapacity, DEFAULT_LOAD);
068: }
069:
070: /**
071: * Returns the number of cached conversion mappings.
072: */
073: public int getCacheSize() {
074: return numEntries;
075: }
076:
077: /**
078: * Converts a character array into an internalized String.
079: */
080: public String convert(char[] ch) {
081: return convert(ch, 0, ch.length);
082: }
083:
084: /**
085: * Converts a character array into an internalized String.
086: *
087: * @param ch character array to convert
088: * @param start starting offset of ch[]
089: * @param length number of characters to read
090: */
091: public String convert(char[] ch, int start, int length) {
092: if (numEntries >= maxEntries) {
093: rehash();
094: }
095: // Look for the cached String for this char array
096: int offset = hashKey(ch, start, length) & hashmask;
097: char[] k = null;
098: while ((k = keys[offset]) != null
099: && !keysAreEqual(k, 0, k.length, ch, start, length)) {
100: offset = (offset - 1) & hashmask;
101: }
102: if (k != null) {
103: return values[offset];
104: } else {
105: // Add the conversion to the cache
106: k = new char[length];
107: System.arraycopy(ch, start, k, 0, length);
108: String v = new String(k).intern();
109: keys[offset] = k;
110: values[offset] = v;
111: numEntries++;
112: return v;
113: }
114: }
115:
116: private void rehash() {
117: int newlength = keys.length << 1;
118: char[][] newkeys = new char[newlength][];
119: String[] newvalues = new String[newlength];
120: int newhashmask = newlength - 1;
121: for (int i = 0; i < keys.length; i++) {
122: char[] k = keys[i];
123: String v = values[i];
124: if (k != null) {
125: int newoffset = hashKey(k, 0, k.length) & newhashmask;
126: char[] newk = null;
127: while ((newk = newkeys[newoffset]) != null
128: && !keysAreEqual(newk, 0, newk.length, k, 0,
129: k.length)) {
130: newoffset = (newoffset - 1) & newhashmask;
131: }
132: newkeys[newoffset] = k;
133: newvalues[newoffset] = v;
134: }
135: }
136: keys = newkeys;
137: values = newvalues;
138: maxEntries = (int) (newlength * loadFactor);
139: hashmask = newhashmask;
140: }
141:
142: public void clearCache() {
143: for (int i = 0; i < keys.length; i++) {
144: keys[i] = null;
145: values[i] = null;
146: }
147: numEntries = 0;
148: }
149:
150: private static final boolean keysAreEqual(char[] a, int astart,
151: int alength, char[] b, int bstart, int blength) {
152: if (alength != blength) {
153: return false;
154: } else {
155: for (int i = 0; i < alength; i++) {
156: if (a[astart + i] != b[bstart + i]) {
157: return false;
158: }
159: }
160: return true;
161: }
162: }
163:
164: private static final int hashKey(char ch[], int start, int length) {
165: int hash = 0;
166: for (int i = 0; i < length; i++) {
167: hash = (hash << 5) + ch[start + i];
168: }
169: return hash;
170: }
171: }
|