lucene-java-3.5.0/lucene/src/java/org/apache/lucene/util/SimpleStringInterner.java

   1 package org.apache.lucene.util;
   2 /**
   3  * Licensed to the Apache Software Foundation (ASF) under one or more
   4  * contributor license agreements.  See the NOTICE file distributed with
   5  * this work for additional information regarding copyright ownership.
   6  * The ASF licenses this file to You under the Apache License, Version 2.0
   7  * (the "License"); you may not use this file except in compliance with
   8  * the License.  You may obtain a copy of the License at
   9  *
  10  *     http://www.apache.org/licenses/LICENSE-2.0
  11  *
  12  * Unless required by applicable law or agreed to in writing, software
  13  * distributed under the License is distributed on an "AS IS" BASIS,
  14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  * See the License for the specific language governing permissions and
  16  * limitations under the License.
  17  */
  18
  19
  20 /**
  21  * Simple lockless and memory barrier free String intern cache that is guaranteed
  22  * to return the same String instance as String.intern()
  23  * does.
  24  *
  25  * @lucene.internal
  26  */
  27 public class SimpleStringInterner extends StringInterner {
  28
  29   private static class Entry {
  30     final private String str;
  31     final private int hash;
  32     private Entry next;
  33     private Entry(String str, int hash, Entry next) {
  34       this.str = str;
  35       this.hash = hash;
  36       this.next = next;
  37     }
  38   }
  39
  40   private final Entry[] cache;
  41   private final int maxChainLength;
  42
  43   /**
  44    * @param tableSize  Size of the hash table, should be a power of two.
  45    * @param maxChainLength  Maximum length of each bucket, after which the oldest item inserted is dropped.
  46    */
  47   public SimpleStringInterner(int tableSize, int maxChainLength) {
  48     cache = new Entry[Math.max(1,BitUtil.nextHighestPowerOfTwo(tableSize))];
  49     this.maxChainLength = Math.max(2,maxChainLength);
  50   }
  51
  52   @Override
  53   public String intern(String s) {
  54     int h = s.hashCode();
  55     // In the future, it may be worth augmenting the string hash
  56     // if the lower bits need better distribution.
  57     int slot = h & (cache.length-1);
  58
  59     Entry first = this.cache[slot];
  60     Entry nextToLast = null;
  61
  62     int chainLength = 0;
  63
  64     for(Entry e=first; e!=null; e=e.next) {
  65       if (e.hash == h && (e.str == s || e.str.compareTo(s)==0)) {
  66       // if (e.str == s || (e.hash == h && e.str.compareTo(s)==0)) {
  67         return e.str;
  68       }
  69
  70       chainLength++;
  71       if (e.next != null) {
  72         nextToLast = e;
  73       }
  74     }
  75
  76     // insertion-order cache: add new entry at head
  77     s = s.intern();
  78     this.cache[slot] = new Entry(s, h, first);
  79     if (chainLength >= maxChainLength) {
  80       // prune last entry
  81       nextToLast.next = null;
  82     }
  83     return s;
  84   }
  85 }