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