1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.tomcat.util.buf;
18
19 import java.nio.charset.Charset;
20 import java.util.ArrayList;
21 import java.util.HashMap;
22 import java.util.Map.Entry;
23 import java.util.TreeMap;
24
25 import org.apache.juli.logging.Log;
26 import org.apache.juli.logging.LogFactory;
27
28 /**
29 * This class implements a String cache for ByteChunk and CharChunk.
30 *
31 * @author Remy Maucherat
32 */
33 public class StringCache {
34
35
36 private static final Log log = LogFactory.getLog(StringCache.class);
37
38
39 // ------------------------------------------------------- Static Variables
40
41
42 /**
43 * Enabled ?
44 */
45 protected static boolean byteEnabled = ("true".equals(System.getProperty(
46 "tomcat.util.buf.StringCache.byte.enabled", "false")));
47
48
49 protected static boolean charEnabled = ("true".equals(System.getProperty(
50 "tomcat.util.buf.StringCache.char.enabled", "false")));
51
52
53 protected static int trainThreshold = Integer.parseInt(System.getProperty(
54 "tomcat.util.buf.StringCache.trainThreshold", "20000"));
55
56
57 protected static int cacheSize = Integer.parseInt(System.getProperty(
58 "tomcat.util.buf.StringCache.cacheSize", "200"));
59
60
61 protected static final int maxStringSize =
62 Integer.parseInt(System.getProperty(
63 "tomcat.util.buf.StringCache.maxStringSize", "128"));
64
65
66 /**
67 * Statistics hash map for byte chunk.
68 */
69 protected static final HashMap<ByteEntry,int[]> bcStats =
70 new HashMap<>(cacheSize);
71
72
73 /**
74 * toString count for byte chunk.
75 */
76 protected static int bcCount = 0;
77
78
79 /**
80 * Cache for byte chunk.
81 */
82 protected static volatile ByteEntry[] bcCache = null;
83
84
85 /**
86 * Statistics hash map for char chunk.
87 */
88 protected static final HashMap<CharEntry,int[]> ccStats =
89 new HashMap<>(cacheSize);
90
91
92 /**
93 * toString count for char chunk.
94 */
95 protected static int ccCount = 0;
96
97
98 /**
99 * Cache for char chunk.
100 */
101 protected static volatile CharEntry[] ccCache = null;
102
103
104 /**
105 * Access count.
106 */
107 protected static int accessCount = 0;
108
109
110 /**
111 * Hit count.
112 */
113 protected static int hitCount = 0;
114
115
116 // ------------------------------------------------------------ Properties
117
118
119 /**
120 * @return Returns the cacheSize.
121 */
122 public int getCacheSize() {
123 return cacheSize;
124 }
125
126
127 /**
128 * @param cacheSize The cacheSize to set.
129 */
130 public void setCacheSize(int cacheSize) {
131 StringCache.cacheSize = cacheSize;
132 }
133
134
135 /**
136 * @return Returns the enabled.
137 */
138 public boolean getByteEnabled() {
139 return byteEnabled;
140 }
141
142
143 /**
144 * @param byteEnabled The enabled to set.
145 */
146 public void setByteEnabled(boolean byteEnabled) {
147 StringCache.byteEnabled = byteEnabled;
148 }
149
150
151 /**
152 * @return Returns the enabled.
153 */
154 public boolean getCharEnabled() {
155 return charEnabled;
156 }
157
158
159 /**
160 * @param charEnabled The enabled to set.
161 */
162 public void setCharEnabled(boolean charEnabled) {
163 StringCache.charEnabled = charEnabled;
164 }
165
166
167 /**
168 * @return Returns the trainThreshold.
169 */
170 public int getTrainThreshold() {
171 return trainThreshold;
172 }
173
174
175 /**
176 * @param trainThreshold The trainThreshold to set.
177 */
178 public void setTrainThreshold(int trainThreshold) {
179 StringCache.trainThreshold = trainThreshold;
180 }
181
182
183 /**
184 * @return Returns the accessCount.
185 */
186 public int getAccessCount() {
187 return accessCount;
188 }
189
190
191 /**
192 * @return Returns the hitCount.
193 */
194 public int getHitCount() {
195 return hitCount;
196 }
197
198
199 // -------------------------------------------------- Public Static Methods
200
201
202 public void reset() {
203 hitCount = 0;
204 accessCount = 0;
205 synchronized (bcStats) {
206 bcCache = null;
207 bcCount = 0;
208 }
209 synchronized (ccStats) {
210 ccCache = null;
211 ccCount = 0;
212 }
213 }
214
215
216 public static String toString(ByteChunk bc) {
217
218 // If the cache is null, then either caching is disabled, or we're
219 // still training
220 if (bcCache == null) {
221 String value = bc.toStringInternal();
222 if (byteEnabled && (value.length() < maxStringSize)) {
223 // If training, everything is synced
224 synchronized (bcStats) {
225 // If the cache has been generated on a previous invocation
226 // while waiting for the lock, just return the toString
227 // value we just calculated
228 if (bcCache != null) {
229 return value;
230 }
231 // Two cases: either we just exceeded the train count, in
232 // which case the cache must be created, or we just update
233 // the count for the string
234 if (bcCount > trainThreshold) {
235 long t1 = System.currentTimeMillis();
236 // Sort the entries according to occurrence
237 TreeMap<Integer,ArrayList<ByteEntry>> tempMap =
238 new TreeMap<>();
239 for (Entry<ByteEntry,int[]> item : bcStats.entrySet()) {
240 ByteEntry entry = item.getKey();
241 int[] countA = item.getValue();
242 Integer count = Integer.valueOf(countA[0]);
243 // Add to the list for that count
244 ArrayList<ByteEntry> list = tempMap.get(count);
245 if (list == null) {
246 // Create list
247 list = new ArrayList<>();
248 tempMap.put(count, list);
249 }
250 list.add(entry);
251 }
252 // Allocate array of the right size
253 int size = bcStats.size();
254 if (size > cacheSize) {
255 size = cacheSize;
256 }
257 ByteEntry[] tempbcCache = new ByteEntry[size];
258 // Fill it up using an alphabetical order
259 // and a dumb insert sort
260 ByteChunk tempChunk = new ByteChunk();
261 int n = 0;
262 while (n < size) {
263 Object key = tempMap.lastKey();
264 ArrayList<ByteEntry> list = tempMap.get(key);
265 for (int i = 0; i < list.size() && n < size; i++) {
266 ByteEntry entry = list.get(i);
267 tempChunk.setBytes(entry.name, 0,
268 entry.name.length);
269 int insertPos = findClosest(tempChunk,
270 tempbcCache, n);
271 if (insertPos == n) {
272 tempbcCache[n + 1] = entry;
273 } else {
274 System.arraycopy(tempbcCache, insertPos + 1,
275 tempbcCache, insertPos + 2,
276 n - insertPos - 1);
277 tempbcCache[insertPos + 1] = entry;
278 }
279 n++;
280 }
281 tempMap.remove(key);
282 }
283 bcCount = 0;
284 bcStats.clear();
285 bcCache = tempbcCache;
286 if (log.isDebugEnabled()) {
287 long t2 = System.currentTimeMillis();
288 log.debug("ByteCache generation time: " +
289 (t2 - t1) + "ms");
290 }
291 } else {
292 bcCount++;
293 // Allocate new ByteEntry for the lookup
294 ByteEntry entry = new ByteEntry();
295 entry.value = value;
296 int[] count = bcStats.get(entry);
297 if (count == null) {
298 int end = bc.getEnd();
299 int start = bc.getStart();
300 // Create byte array and copy bytes
301 entry.name = new byte[bc.getLength()];
302 System.arraycopy(bc.getBuffer(), start, entry.name,
303 0, end - start);
304 // Set encoding
305 entry.charset = bc.getCharset();
306 // Initialize occurrence count to one
307 count = new int[1];
308 count[0] = 1;
309 // Set in the stats hash map
310 bcStats.put(entry, count);
311 } else {
312 count[0] = count[0] + 1;
313 }
314 }
315 }
316 }
317 return value;
318 } else {
319 accessCount++;
320 // Find the corresponding String
321 String result = find(bc);
322 if (result == null) {
323 return bc.toStringInternal();
324 }
325 // Note: We don't care about safety for the stats
326 hitCount++;
327 return result;
328 }
329
330 }
331
332
333 public static String toString(CharChunk cc) {
334
335 // If the cache is null, then either caching is disabled, or we're
336 // still training
337 if (ccCache == null) {
338 String value = cc.toStringInternal();
339 if (charEnabled && (value.length() < maxStringSize)) {
340 // If training, everything is synced
341 synchronized (ccStats) {
342 // If the cache has been generated on a previous invocation
343 // while waiting for the lock, just return the toString
344 // value we just calculated
345 if (ccCache != null) {
346 return value;
347 }
348 // Two cases: either we just exceeded the train count, in
349 // which case the cache must be created, or we just update
350 // the count for the string
351 if (ccCount > trainThreshold) {
352 long t1 = System.currentTimeMillis();
353 // Sort the entries according to occurrence
354 TreeMap<Integer,ArrayList<CharEntry>> tempMap =
355 new TreeMap<>();
356 for (Entry<CharEntry,int[]> item : ccStats.entrySet()) {
357 CharEntry entry = item.getKey();
358 int[] countA = item.getValue();
359 Integer count = Integer.valueOf(countA[0]);
360 // Add to the list for that count
361 ArrayList<CharEntry> list = tempMap.get(count);
362 if (list == null) {
363 // Create list
364 list = new ArrayList<>();
365 tempMap.put(count, list);
366 }
367 list.add(entry);
368 }
369 // Allocate array of the right size
370 int size = ccStats.size();
371 if (size > cacheSize) {
372 size = cacheSize;
373 }
374 CharEntry[] tempccCache = new CharEntry[size];
375 // Fill it up using an alphabetical order
376 // and a dumb insert sort
377 CharChunk tempChunk = new CharChunk();
378 int n = 0;
379 while (n < size) {
380 Object key = tempMap.lastKey();
381 ArrayList<CharEntry> list = tempMap.get(key);
382 for (int i = 0; i < list.size() && n < size; i++) {
383 CharEntry entry = list.get(i);
384 tempChunk.setChars(entry.name, 0,
385 entry.name.length);
386 int insertPos = findClosest(tempChunk,
387 tempccCache, n);
388 if (insertPos == n) {
389 tempccCache[n + 1] = entry;
390 } else {
391 System.arraycopy(tempccCache, insertPos + 1,
392 tempccCache, insertPos + 2,
393 n - insertPos - 1);
394 tempccCache[insertPos + 1] = entry;
395 }
396 n++;
397 }
398 tempMap.remove(key);
399 }
400 ccCount = 0;
401 ccStats.clear();
402 ccCache = tempccCache;
403 if (log.isDebugEnabled()) {
404 long t2 = System.currentTimeMillis();
405 log.debug("CharCache generation time: " +
406 (t2 - t1) + "ms");
407 }
408 } else {
409 ccCount++;
410 // Allocate new CharEntry for the lookup
411 CharEntry entry = new CharEntry();
412 entry.value = value;
413 int[] count = ccStats.get(entry);
414 if (count == null) {
415 int end = cc.getEnd();
416 int start = cc.getStart();
417 // Create char array and copy chars
418 entry.name = new char[cc.getLength()];
419 System.arraycopy(cc.getBuffer(), start, entry.name,
420 0, end - start);
421 // Initialize occurrence count to one
422 count = new int[1];
423 count[0] = 1;
424 // Set in the stats hash map
425 ccStats.put(entry, count);
426 } else {
427 count[0] = count[0] + 1;
428 }
429 }
430 }
431 }
432 return value;
433 } else {
434 accessCount++;
435 // Find the corresponding String
436 String result = find(cc);
437 if (result == null) {
438 return cc.toStringInternal();
439 }
440 // Note: We don't care about safety for the stats
441 hitCount++;
442 return result;
443 }
444
445 }
446
447
448 // ----------------------------------------------------- Protected Methods
449
450
451 /**
452 * Compare given byte chunk with byte array.
453 * @param name The name to compare
454 * @param compareTo The compared to data
455 * @return -1, 0 or +1 if inferior, equal, or superior to the String.
456 */
457 protected static final int compare(ByteChunk name, byte[] compareTo) {
458 int result = 0;
459
460 byte[] b = name.getBuffer();
461 int start = name.getStart();
462 int end = name.getEnd();
463 int len = compareTo.length;
464
465 if ((end - start) < len) {
466 len = end - start;
467 }
468 for (int i = 0; (i < len) && (result == 0); i++) {
469 if (b[i + start] > compareTo[i]) {
470 result = 1;
471 } else if (b[i + start] < compareTo[i]) {
472 result = -1;
473 }
474 }
475 if (result == 0) {
476 if (compareTo.length > (end - start)) {
477 result = -1;
478 } else if (compareTo.length < (end - start)) {
479 result = 1;
480 }
481 }
482 return result;
483 }
484
485
486 /**
487 * Find an entry given its name in the cache and return the associated
488 * String.
489 * @param name The name to find
490 * @return the corresponding value
491 */
492 protected static final String find(ByteChunk name) {
493 int pos = findClosest(name, bcCache, bcCache.length);
494 if ((pos < 0) || (compare(name, bcCache[pos].name) != 0)
495 || !(name.getCharset().equals(bcCache[pos].charset))) {
496 return null;
497 } else {
498 return bcCache[pos].value;
499 }
500 }
501
502
503 /**
504 * Find an entry given its name in a sorted array of map elements.
505 * This will return the index for the closest inferior or equal item in the
506 * given array.
507 * @param name The name to find
508 * @param array The array in which to look
509 * @param len The effective length of the array
510 * @return the position of the best match
511 */
512 protected static final int findClosest(ByteChunk name, ByteEntry[] array,
513 int len) {
514
515 int a = 0;
516 int b = len - 1;
517
518 // Special cases: -1 and 0
519 if (b == -1) {
520 return -1;
521 }
522
523 if (compare(name, array[0].name) < 0) {
524 return -1;
525 }
526 if (b == 0) {
527 return 0;
528 }
529
530 int i = 0;
531 while (true) {
532 i = (b + a) >>> 1;
533 int result = compare(name, array[i].name);
534 if (result == 1) {
535 a = i;
536 } else if (result == 0) {
537 return i;
538 } else {
539 b = i;
540 }
541 if ((b - a) == 1) {
542 int result2 = compare(name, array[b].name);
543 if (result2 < 0) {
544 return a;
545 } else {
546 return b;
547 }
548 }
549 }
550
551 }
552
553
554 /**
555 * Compare given char chunk with char array.
556 * @param name The name to compare
557 * @param compareTo The compared to data
558 * @return -1, 0 or +1 if inferior, equal, or superior to the String.
559 */
560 protected static final int compare(CharChunk name, char[] compareTo) {
561 int result = 0;
562
563 char[] c = name.getBuffer();
564 int start = name.getStart();
565 int end = name.getEnd();
566 int len = compareTo.length;
567
568 if ((end - start) < len) {
569 len = end - start;
570 }
571 for (int i = 0; (i < len) && (result == 0); i++) {
572 if (c[i + start] > compareTo[i]) {
573 result = 1;
574 } else if (c[i + start] < compareTo[i]) {
575 result = -1;
576 }
577 }
578 if (result == 0) {
579 if (compareTo.length > (end - start)) {
580 result = -1;
581 } else if (compareTo.length < (end - start)) {
582 result = 1;
583 }
584 }
585 return result;
586 }
587
588
589 /**
590 * Find an entry given its name in the cache and return the associated
591 * String.
592 * @param name The name to find
593 * @return the corresponding value
594 */
595 protected static final String find(CharChunk name) {
596 int pos = findClosest(name, ccCache, ccCache.length);
597 if ((pos < 0) || (compare(name, ccCache[pos].name) != 0)) {
598 return null;
599 } else {
600 return ccCache[pos].value;
601 }
602 }
603
604
605 /**
606 * Find an entry given its name in a sorted array of map elements.
607 * This will return the index for the closest inferior or equal item in the
608 * given array.
609 * @param name The name to find
610 * @param array The array in which to look
611 * @param len The effective length of the array
612 * @return the position of the best match
613 */
614 protected static final int findClosest(CharChunk name, CharEntry[] array,
615 int len) {
616
617 int a = 0;
618 int b = len - 1;
619
620 // Special cases: -1 and 0
621 if (b == -1) {
622 return -1;
623 }
624
625 if (compare(name, array[0].name) < 0 ) {
626 return -1;
627 }
628 if (b == 0) {
629 return 0;
630 }
631
632 int i = 0;
633 while (true) {
634 i = (b + a) >>> 1;
635 int result = compare(name, array[i].name);
636 if (result == 1) {
637 a = i;
638 } else if (result == 0) {
639 return i;
640 } else {
641 b = i;
642 }
643 if ((b - a) == 1) {
644 int result2 = compare(name, array[b].name);
645 if (result2 < 0) {
646 return a;
647 } else {
648 return b;
649 }
650 }
651 }
652
653 }
654
655
656 // -------------------------------------------------- ByteEntry Inner Class
657
658
659 private static class ByteEntry {
660
661 private byte[] name = null;
662 private Charset charset = null;
663 private String value = null;
664
665 @Override
666 public String toString() {
667 return value;
668 }
669 @Override
670 public int hashCode() {
671 return value.hashCode();
672 }
673 @Override
674 public boolean equals(Object obj) {
675 if (obj instanceof ByteEntry) {
676 return value.equals(((ByteEntry) obj).value);
677 }
678 return false;
679 }
680
681 }
682
683
684 // -------------------------------------------------- CharEntry Inner Class
685
686
687 private static class CharEntry {
688
689 private char[] name = null;
690 private String value = null;
691
692 @Override
693 public String toString() {
694 return value;
695 }
696 @Override
697 public int hashCode() {
698 return value.hashCode();
699 }
700 @Override
701 public boolean equals(Object obj) {
702 if (obj instanceof CharEntry) {
703 return value.equals(((CharEntry) obj).value);
704 }
705 return false;
706 }
707
708 }
709
710
711 }
712