001: /*
002: * Modified by Nabh Information Systems, Inc.
003: * Modifications (c) 2006 Nabh Information Systems, Inc.
004: *
005: * Copyright 1999-2005 The Apache Software Foundation
006: *
007: * Licensed under the Apache License, Version 2.0 (the "License");
008: * you may not use this file except in compliance with the License.
009: * You may obtain a copy of the License at
010: *
011: * http://www.apache.org/licenses/LICENSE-2.0
012: *
013: * Unless required by applicable law or agreed to in writing, software
014: * distributed under the License is distributed on an "AS IS" BASIS,
015: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
016: * See the License for the specific language governing permissions and
017: * limitations under the License.
018: */
019: package com.nabhinc.util.md;
020:
021: import java.util.ArrayList;
022: import java.util.HashMap;
023: import java.util.Iterator;
024: import java.util.TreeMap;
025:
026: /**
027: * This class implements a String cache for ByteChunk and CharChunk.
028: *
029: * @author Remy Maucherat
030: */
031: public class StringCache {
032:
033: private static org.apache.commons.logging.Log log = org.apache.commons.logging.LogFactory
034: .getLog(StringCache.class);
035:
036: // ------------------------------------------------------- Static Variables
037:
038: /**
039: * Enabled ?
040: */
041: protected static boolean byteEnabled = ("true".equals(System
042: .getProperty("tomcat.util.buf.StringCache.byte.enabled",
043: "false")));
044:
045: protected static boolean charEnabled = ("true".equals(System
046: .getProperty("tomcat.util.buf.StringCache.char.enabled",
047: "false")));
048:
049: protected static int trainThreshold = Integer.parseInt(System
050: .getProperty("tomcat.util.buf.StringCache.trainThreshold",
051: "20000"));
052:
053: protected static int cacheSize = Integer
054: .parseInt(System.getProperty(
055: "tomcat.util.buf.StringCache.cacheSize", "200"));
056:
057: /**
058: * Statistics hash map for byte chunk.
059: */
060: protected static HashMap bcStats = new HashMap(cacheSize);
061:
062: /**
063: * toString count for byte chunk.
064: */
065: protected static int bcCount = 0;
066:
067: /**
068: * Cache for byte chunk.
069: */
070: protected static ByteEntry[] bcCache = null;
071:
072: /**
073: * Statistics hash map for char chunk.
074: */
075: protected static HashMap ccStats = new HashMap(cacheSize);
076:
077: /**
078: * toString count for char chunk.
079: */
080: protected static int ccCount = 0;
081:
082: /**
083: * Cache for char chunk.
084: */
085: protected static CharEntry[] ccCache = null;
086:
087: /**
088: * Access count.
089: */
090: protected static int accessCount = 0;
091:
092: /**
093: * Hit count.
094: */
095: protected static int hitCount = 0;
096:
097: // ------------------------------------------------------------ Properties
098:
099: /**
100: * @return Returns the cacheSize.
101: */
102: public int getCacheSize() {
103: return cacheSize;
104: }
105:
106: /**
107: * @param cacheSize The cacheSize to set.
108: */
109: public void setCacheSize(int cacheSize) {
110: StringCache.cacheSize = cacheSize;
111: }
112:
113: /**
114: * @return Returns the enabled.
115: */
116: public boolean getByteEnabled() {
117: return byteEnabled;
118: }
119:
120: /**
121: * @param byteEnabled The enabled to set.
122: */
123: public void setByteEnabled(boolean byteEnabled) {
124: StringCache.byteEnabled = byteEnabled;
125: }
126:
127: /**
128: * @return Returns the enabled.
129: */
130: public boolean getCharEnabled() {
131: return charEnabled;
132: }
133:
134: /**
135: * @param charEnabled The enabled to set.
136: */
137: public void setCharEnabled(boolean charEnabled) {
138: StringCache.charEnabled = charEnabled;
139: }
140:
141: /**
142: * @return Returns the trainThreshold.
143: */
144: public int getTrainThreshold() {
145: return trainThreshold;
146: }
147:
148: /**
149: * @param trainThreshold The trainThreshold to set.
150: */
151: public void setTrainThreshold(int trainThreshold) {
152: StringCache.trainThreshold = trainThreshold;
153: }
154:
155: /**
156: * @return Returns the accessCount.
157: */
158: public int getAccessCount() {
159: return accessCount;
160: }
161:
162: /**
163: * @return Returns the hitCount.
164: */
165: public int getHitCount() {
166: return hitCount;
167: }
168:
169: // -------------------------------------------------- Public Static Methods
170:
171: public void reset() {
172: hitCount = 0;
173: accessCount = 0;
174: synchronized (bcStats) {
175: bcCache = null;
176: bcCount = 0;
177: }
178: synchronized (ccStats) {
179: ccCache = null;
180: ccCount = 0;
181: }
182: }
183:
184: public static String toString(ByteChunk bc) {
185:
186: // If the cache is null, then either caching is disabled, or we're
187: // still training
188: if (bcCache == null) {
189: String value = bc.toStringInternal();
190: if (byteEnabled) {
191: // If training, everything is synced
192: synchronized (bcStats) {
193: // If the cache has been generated on a previous invocation
194: // while waiting fot the lock, just return the toString value
195: // we just calculated
196: if (bcCache != null) {
197: return value;
198: }
199: // Two cases: either we just exceeded the train count, in which
200: // case the cache must be created, or we just update the count for
201: // the string
202: if (bcCount > trainThreshold) {
203: long t1 = System.currentTimeMillis();
204: // Sort the entries according to occurrence
205: TreeMap tempMap = new TreeMap();
206: Iterator entries = bcStats.keySet().iterator();
207: while (entries.hasNext()) {
208: ByteEntry entry = (ByteEntry) entries
209: .next();
210: int[] countA = (int[]) bcStats.get(entry);
211: Integer count = new Integer(countA[0]);
212: // Add to the list for that count
213: ArrayList list = (ArrayList) tempMap
214: .get(count);
215: if (list == null) {
216: // Create list
217: list = new ArrayList();
218: tempMap.put(count, list);
219: }
220: list.add(entry);
221: }
222: // Allocate array of the right size
223: int size = bcStats.size();
224: if (size > cacheSize) {
225: size = cacheSize;
226: }
227: ByteEntry[] tempbcCache = new ByteEntry[size];
228: // Fill it up using an alphabetical order
229: // and a dumb insert sort
230: ByteChunk tempChunk = new ByteChunk();
231: int n = 0;
232: while (n < size) {
233: Object key = tempMap.lastKey();
234: ArrayList list = (ArrayList) tempMap
235: .get(key);
236: ByteEntry[] list2 = (ByteEntry[]) list
237: .toArray(new ByteEntry[list.size()]);
238: for (int i = 0; i < list.size() && n < size; i++) {
239: ByteEntry entry = (ByteEntry) list
240: .get(i);
241: tempChunk.setBytes(entry.name, 0,
242: entry.name.length);
243: int insertPos = findClosest(tempChunk,
244: tempbcCache, n);
245: if (insertPos == n) {
246: tempbcCache[n + 1] = entry;
247: } else {
248: System.arraycopy(tempbcCache,
249: insertPos + 1, tempbcCache,
250: insertPos + 2, n
251: - insertPos - 1);
252: tempbcCache[insertPos + 1] = entry;
253: }
254: n++;
255: }
256: tempMap.remove(key);
257: }
258: bcCount = 0;
259: bcStats.clear();
260: bcCache = tempbcCache;
261: if (log.isDebugEnabled()) {
262: long t2 = System.currentTimeMillis();
263: log.debug("ByteCache generation time: "
264: + (t2 - t1) + "ms");
265: }
266: } else {
267: bcCount++;
268: // Allocate new ByteEntry for the lookup
269: ByteEntry entry = new ByteEntry();
270: entry.value = value;
271: int[] count = (int[]) bcStats.get(entry);
272: if (count == null) {
273: int end = bc.getEnd();
274: int start = bc.getStart();
275: // Create byte array and copy bytes
276: entry.name = new byte[bc.getLength()];
277: System.arraycopy(bc.getBuffer(), start,
278: entry.name, 0, end - start);
279: // Set encoding
280: entry.enc = bc.getEncoding();
281: // Initialize occurrence count to one
282: count = new int[1];
283: count[0] = 1;
284: // Set in the stats hash map
285: bcStats.put(entry, count);
286: } else {
287: count[0] = count[0] + 1;
288: }
289: }
290: }
291: }
292: return value;
293: } else {
294: accessCount++;
295: // Find the corresponding String
296: String result = find(bc);
297: if (result == null) {
298: return bc.toStringInternal();
299: }
300: // Note: We don't care about safety for the stats
301: hitCount++;
302: return result;
303: }
304:
305: }
306:
307: public static String toString(CharChunk cc) {
308:
309: // If the cache is null, then either caching is disabled, or we're
310: // still training
311: if (ccCache == null) {
312: String value = cc.toStringInternal();
313: if (charEnabled) {
314: // If training, everything is synced
315: synchronized (ccStats) {
316: // If the cache has been generated on a previous invocation
317: // while waiting fot the lock, just return the toString value
318: // we just calculated
319: if (ccCache != null) {
320: return value;
321: }
322: // Two cases: either we just exceeded the train count, in which
323: // case the cache must be created, or we just update the count for
324: // the string
325: if (ccCount > trainThreshold) {
326: long t1 = System.currentTimeMillis();
327: // Sort the entries according to occurrence
328: TreeMap tempMap = new TreeMap();
329: Iterator entries = ccStats.keySet().iterator();
330: while (entries.hasNext()) {
331: CharEntry entry = (CharEntry) entries
332: .next();
333: int[] countA = (int[]) ccStats.get(entry);
334: Integer count = new Integer(countA[0]);
335: // Add to the list for that count
336: ArrayList list = (ArrayList) tempMap
337: .get(count);
338: if (list == null) {
339: // Create list
340: list = new ArrayList();
341: tempMap.put(count, list);
342: }
343: list.add(entry);
344: }
345: // Allocate array of the right size
346: int size = ccStats.size();
347: if (size > cacheSize) {
348: size = cacheSize;
349: }
350: CharEntry[] tempccCache = new CharEntry[size];
351: // Fill it up using an alphabetical order
352: // and a dumb insert sort
353: CharChunk tempChunk = new CharChunk();
354: int n = 0;
355: while (n < size) {
356: Object key = tempMap.lastKey();
357: ArrayList list = (ArrayList) tempMap
358: .get(key);
359: CharEntry[] list2 = (CharEntry[]) list
360: .toArray(new CharEntry[list.size()]);
361: for (int i = 0; i < list.size() && n < size; i++) {
362: CharEntry entry = (CharEntry) list
363: .get(i);
364: tempChunk.setChars(entry.name, 0,
365: entry.name.length);
366: int insertPos = findClosest(tempChunk,
367: tempccCache, n);
368: if (insertPos == n) {
369: tempccCache[n + 1] = entry;
370: } else {
371: System.arraycopy(tempccCache,
372: insertPos + 1, tempccCache,
373: insertPos + 2, n
374: - insertPos - 1);
375: tempccCache[insertPos + 1] = entry;
376: }
377: n++;
378: }
379: tempMap.remove(key);
380: }
381: ccCount = 0;
382: ccStats.clear();
383: ccCache = tempccCache;
384: if (log.isDebugEnabled()) {
385: long t2 = System.currentTimeMillis();
386: log.debug("CharCache generation time: "
387: + (t2 - t1) + "ms");
388: }
389: } else {
390: ccCount++;
391: // Allocate new CharEntry for the lookup
392: CharEntry entry = new CharEntry();
393: entry.value = value;
394: int[] count = (int[]) ccStats.get(entry);
395: if (count == null) {
396: int end = cc.getEnd();
397: int start = cc.getStart();
398: // Create char array and copy chars
399: entry.name = new char[cc.getLength()];
400: System.arraycopy(cc.getBuffer(), start,
401: entry.name, 0, end - start);
402: // Initialize occurrence count to one
403: count = new int[1];
404: count[0] = 1;
405: // Set in the stats hash map
406: ccStats.put(entry, count);
407: } else {
408: count[0] = count[0] + 1;
409: }
410: }
411: }
412: }
413: return value;
414: } else {
415: accessCount++;
416: // Find the corresponding String
417: String result = find(cc);
418: if (result == null) {
419: return cc.toStringInternal();
420: }
421: // Note: We don't care about safety for the stats
422: hitCount++;
423: return result;
424: }
425:
426: }
427:
428: // ----------------------------------------------------- Protected Methods
429:
430: /**
431: * Compare given byte chunk with byte array.
432: * Return -1, 0 or +1 if inferior, equal, or superior to the String.
433: */
434: protected static final int compare(ByteChunk name, byte[] compareTo) {
435: int result = 0;
436:
437: byte[] b = name.getBuffer();
438: int start = name.getStart();
439: int end = name.getEnd();
440: int len = compareTo.length;
441:
442: if ((end - start) < len) {
443: len = end - start;
444: }
445: for (int i = 0; (i < len) && (result == 0); i++) {
446: if (b[i + start] > compareTo[i]) {
447: result = 1;
448: } else if (b[i + start] < compareTo[i]) {
449: result = -1;
450: }
451: }
452: if (result == 0) {
453: if (compareTo.length > (end - start)) {
454: result = -1;
455: } else if (compareTo.length < (end - start)) {
456: result = 1;
457: }
458: }
459: return result;
460: }
461:
462: /**
463: * Find an entry given its name in the cache and return the associated String.
464: */
465: protected static final String find(ByteChunk name) {
466: int pos = findClosest(name, bcCache, bcCache.length);
467: if ((pos < 0) || (compare(name, bcCache[pos].name) != 0)
468: || !(name.getEncoding().equals(bcCache[pos].enc))) {
469: return null;
470: } else {
471: return bcCache[pos].value;
472: }
473: }
474:
475: /**
476: * Find an entry given its name in a sorted array of map elements.
477: * This will return the index for the closest inferior or equal item in the
478: * given array.
479: */
480: protected static final int findClosest(ByteChunk name,
481: ByteEntry[] array, int len) {
482:
483: int a = 0;
484: int b = len - 1;
485:
486: // Special cases: -1 and 0
487: if (b == -1) {
488: return -1;
489: }
490:
491: if (compare(name, array[0].name) < 0) {
492: return -1;
493: }
494: if (b == 0) {
495: return 0;
496: }
497:
498: int i = 0;
499: while (true) {
500: i = (b + a) / 2;
501: int result = compare(name, array[i].name);
502: if (result == 1) {
503: a = i;
504: } else if (result == 0) {
505: return i;
506: } else {
507: b = i;
508: }
509: if ((b - a) == 1) {
510: int result2 = compare(name, array[b].name);
511: if (result2 < 0) {
512: return a;
513: } else {
514: return b;
515: }
516: }
517: }
518:
519: }
520:
521: /**
522: * Compare given char chunk with char array.
523: * Return -1, 0 or +1 if inferior, equal, or superior to the String.
524: */
525: protected static final int compare(CharChunk name, char[] compareTo) {
526: int result = 0;
527:
528: char[] c = name.getBuffer();
529: int start = name.getStart();
530: int end = name.getEnd();
531: int len = compareTo.length;
532:
533: if ((end - start) < len) {
534: len = end - start;
535: }
536: for (int i = 0; (i < len) && (result == 0); i++) {
537: if (c[i + start] > compareTo[i]) {
538: result = 1;
539: } else if (c[i + start] < compareTo[i]) {
540: result = -1;
541: }
542: }
543: if (result == 0) {
544: if (compareTo.length > (end - start)) {
545: result = -1;
546: } else if (compareTo.length < (end - start)) {
547: result = 1;
548: }
549: }
550: return result;
551: }
552:
553: /**
554: * Find an entry given its name in the cache and return the associated String.
555: */
556: protected static final String find(CharChunk name) {
557: int pos = findClosest(name, ccCache, ccCache.length);
558: if ((pos < 0) || (compare(name, ccCache[pos].name) != 0)) {
559: return null;
560: } else {
561: return ccCache[pos].value;
562: }
563: }
564:
565: /**
566: * Find an entry given its name in a sorted array of map elements.
567: * This will return the index for the closest inferior or equal item in the
568: * given array.
569: */
570: protected static final int findClosest(CharChunk name,
571: CharEntry[] array, int len) {
572:
573: int a = 0;
574: int b = len - 1;
575:
576: // Special cases: -1 and 0
577: if (b == -1) {
578: return -1;
579: }
580:
581: if (compare(name, array[0].name) < 0) {
582: return -1;
583: }
584: if (b == 0) {
585: return 0;
586: }
587:
588: int i = 0;
589: while (true) {
590: i = (b + a) / 2;
591: int result = compare(name, array[i].name);
592: if (result == 1) {
593: a = i;
594: } else if (result == 0) {
595: return i;
596: } else {
597: b = i;
598: }
599: if ((b - a) == 1) {
600: int result2 = compare(name, array[b].name);
601: if (result2 < 0) {
602: return a;
603: } else {
604: return b;
605: }
606: }
607: }
608:
609: }
610:
611: // -------------------------------------------------- ByteEntry Inner Class
612:
613: public static class ByteEntry {
614:
615: public byte[] name = null;
616: public String enc = null;
617: public String value = null;
618:
619: public String toString() {
620: return value;
621: }
622:
623: public int hashCode() {
624: return value.hashCode();
625: }
626:
627: public boolean equals(Object obj) {
628: if (obj instanceof ByteEntry) {
629: return value.equals(((ByteEntry) obj).value);
630: }
631: return false;
632: }
633:
634: }
635:
636: // -------------------------------------------------- CharEntry Inner Class
637:
638: public static class CharEntry {
639:
640: public char[] name = null;
641: public String value = null;
642:
643: public String toString() {
644: return value;
645: }
646:
647: public int hashCode() {
648: return value.hashCode();
649: }
650:
651: public boolean equals(Object obj) {
652: if (obj instanceof CharEntry) {
653: return value.equals(((CharEntry) obj).value);
654: }
655: return false;
656: }
657:
658: }
659:
660: }
|