StringCache


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