1 /*
   2  * Copyright (c) 2015, Oracle and/or its affiliates. All rights reserved.
   3  */
   4 /*
   5  * Licensed to the Apache Software Foundation (ASF) under one or more
   6  * contributor license agreements.  See the NOTICE file distributed with
   7  * this work for additional information regarding copyright ownership.
   8  * The ASF licenses this file to You under the Apache License, Version 2.0
   9  * (the "License"); you may not use this file except in compliance with
  10  * the License.  You may obtain a copy of the License at
  11  *
  12  *      http://www.apache.org/licenses/LICENSE-2.0
  13  *
  14  * Unless required by applicable law or agreed to in writing, software
  15  * distributed under the License is distributed on an "AS IS" BASIS,
  16  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  17  * See the License for the specific language governing permissions and
  18  * limitations under the License.
  19  */
  20 
  21 package com.sun.org.apache.xerces.internal.util;
  22 
  23 
  24 /**
  25  * This class is an unsynchronized hash table primary used for String
  26  * to Object mapping.
  27  * <p>
  28  * The hash code uses the same algorithm as SymbolTable class.
  29  *
  30  * @author Elena Litani
  31  */
  32 public class SymbolHash {
  33 
  34     //
  35     // Constants
  36     //
  37 
  38     /** Default table size. */
  39     protected static final int TABLE_SIZE = 101;
  40 
  41     /** Maximum hash collisions per bucket. */
  42     protected static final int MAX_HASH_COLLISIONS = 40;
  43 
  44     protected static final int MULTIPLIERS_SIZE = 1 << 5;
  45     protected static final int MULTIPLIERS_MASK = MULTIPLIERS_SIZE - 1;
  46 
  47     //
  48     // Data
  49     //
  50 
  51     /** Actual table size **/
  52     protected int fTableSize;
  53 
  54     /** Buckets. */
  55     protected Entry[] fBuckets;
  56 
  57     /** Number of elements. */
  58     protected int fNum = 0;
  59 
  60     /**
  61      * Array of randomly selected hash function multipliers or <code>null</code>
  62      * if the default String.hashCode() function should be used.
  63      */
  64     protected int[] fHashMultipliers;
  65 
  66     //
  67     // Constructors
  68     //
  69 
  70     /** Constructs a key table with the default size. */
  71     public SymbolHash() {
  72         this(TABLE_SIZE);
  73     }
  74 
  75     /**
  76      * Constructs a key table with a given size.
  77      *
  78      * @param size  the size of the key table.
  79      */
  80     public SymbolHash(int size) {
  81         fTableSize = size;
  82         fBuckets = new Entry[fTableSize];
  83     }
  84 
  85     //
  86     // Public methods
  87     //
  88 
  89     /**
  90      * Adds the key/value mapping to the key table. If the key already exists,
  91      * the previous value associated with this key is overwritten by the new
  92      * value.
  93      *
  94      * @param key
  95      * @param value
  96      */
  97     public void put(Object key, Object value) {
  98 
  99         // search for identical key
 100         int collisionCount = 0;
 101         final int hash = hash(key);
 102         int bucket = hash % fTableSize;
 103         for (Entry entry = fBuckets[bucket]; entry != null; entry = entry.next) {
 104             if (key.equals(entry.key)) {
 105                 // replace old value
 106                 entry.value = value;
 107                 return;
 108             }
 109             ++collisionCount;
 110         }
 111 
 112         if (fNum >= fTableSize) {
 113             // Rehash the table if the number of entries
 114             // would exceed the number of buckets.
 115             rehash();
 116             bucket = hash % fTableSize;
 117         }
 118         else if (collisionCount >= MAX_HASH_COLLISIONS && key instanceof String) {
 119             // Select a new hash function and rehash the table if
 120             // MAX_HASH_COLLISIONS is exceeded.
 121             rebalance();
 122             bucket = hash(key) % fTableSize;
 123         }
 124 
 125         // create new entry
 126         Entry entry = new Entry(key, value, fBuckets[bucket]);
 127         fBuckets[bucket] = entry;
 128         ++fNum;
 129     }
 130 
 131     /**
 132      * Get the value associated with the given key.
 133      *
 134      * @param key
 135      * @return the value associated with the given key.
 136      */
 137     public Object get(Object key) {
 138         int bucket = hash(key) % fTableSize;
 139         Entry entry = search(key, bucket);
 140         if (entry != null) {
 141             return entry.value;
 142         }
 143         return null;
 144     }
 145 
 146     /**
 147      * Get the number of key/value pairs stored in this table.
 148      *
 149      * @return the number of key/value pairs stored in this table.
 150      */
 151     public int getLength() {
 152         return fNum;
 153     }
 154 
 155     /**
 156      * Add all values to the given array. The array must have enough entry.
 157      *
 158      * @param elements  the array to store the elements
 159      * @param from      where to start store element in the array
 160      * @return          number of elements copied to the array
 161      */
 162     public int getValues(Object[] elements, int from) {
 163         for (int i=0, j=0; i<fTableSize && j<fNum; i++) {
 164             for (Entry entry = fBuckets[i]; entry != null; entry = entry.next) {
 165                 elements[from+j] = entry.value;
 166                 j++;
 167             }
 168         }
 169         return fNum;
 170     }
 171 
 172     /**
 173      * Return key/value pairs of all entries in the map
 174      */
 175     public Object[] getEntries() {
 176         Object[] entries = new Object[fNum << 1];
 177         for (int i=0, j=0; i<fTableSize && j<fNum << 1; i++) {
 178             for (Entry entry = fBuckets[i]; entry != null; entry = entry.next) {
 179                 entries[j] = entry.key;
 180                 entries[++j] = entry.value;
 181                 j++;
 182             }
 183         }
 184         return entries;
 185     }
 186 
 187     /**
 188      * Make a clone of this object.
 189      */
 190     public SymbolHash makeClone() {
 191         SymbolHash newTable = new SymbolHash(fTableSize);
 192         newTable.fNum = fNum;
 193         newTable.fHashMultipliers = fHashMultipliers != null ? (int[]) fHashMultipliers.clone() : null;
 194         for (int i = 0; i < fTableSize; i++) {
 195             if (fBuckets[i] != null) {
 196                 newTable.fBuckets[i] = fBuckets[i].makeClone();
 197             }
 198         }
 199         return newTable;
 200     }
 201 
 202     /**
 203      * Remove all key/value association. This tries to save a bit of GC'ing
 204      * by at least keeping the fBuckets array around.
 205      */
 206     public void clear() {
 207         for (int i=0; i<fTableSize; i++) {
 208             fBuckets[i] = null;
 209         }
 210         fNum = 0;
 211         fHashMultipliers = null;
 212     } // clear():  void
 213 
 214     protected Entry search(Object key, int bucket) {
 215         // search for identical key
 216         for (Entry entry = fBuckets[bucket]; entry != null; entry = entry.next) {
 217             if (key.equals(entry.key))
 218                 return entry;
 219         }
 220         return null;
 221     }
 222 
 223     /**
 224      * Returns a hashcode value for the specified key.
 225      *
 226      * @param key The key to hash.
 227      */
 228     protected int hash(Object key) {
 229         if (fHashMultipliers == null || !(key instanceof String)) {
 230             return key.hashCode() & 0x7FFFFFFF;
 231         }
 232         return hash0((String) key);
 233     } // hash(Object):int
 234 
 235     private int hash0(String symbol) {
 236         int code = 0;
 237         final int length = symbol.length();
 238         final int[] multipliers = fHashMultipliers;
 239         for (int i = 0; i < length; ++i) {
 240             code = code * multipliers[i & MULTIPLIERS_MASK] + symbol.charAt(i);
 241         }
 242         return code & 0x7FFFFFFF;
 243     } // hash0(String):int
 244 
 245     /**
 246      * Increases the capacity of and internally reorganizes this
 247      * SymbolHash, in order to accommodate and access its entries more
 248      * efficiently.  This method is called automatically when the
 249      * number of keys in the SymbolHash exceeds its number of buckets.
 250      */
 251     protected void rehash() {
 252         rehashCommon((fBuckets.length << 1) + 1);
 253     }
 254 
 255     /**
 256      * Randomly selects a new hash function and reorganizes this SymbolHash
 257      * in order to more evenly distribute its entries across the table. This
 258      * method is called automatically when the number keys in one of the
 259      * SymbolHash's buckets exceeds MAX_HASH_COLLISIONS.
 260      */
 261     protected void rebalance() {
 262         if (fHashMultipliers == null) {
 263             fHashMultipliers = new int[MULTIPLIERS_SIZE];
 264         }
 265         PrimeNumberSequenceGenerator.generateSequence(fHashMultipliers);
 266         rehashCommon(fBuckets.length);
 267     }
 268 
 269     private void rehashCommon(final int newCapacity) {
 270 
 271         final int oldCapacity = fBuckets.length;
 272         final Entry[] oldTable = fBuckets;
 273 
 274         final Entry[] newTable = new Entry[newCapacity];
 275 
 276         fBuckets = newTable;
 277         fTableSize = fBuckets.length;
 278 
 279         for (int i = oldCapacity; i-- > 0;) {
 280             for (Entry old = oldTable[i]; old != null; ) {
 281                 Entry e = old;
 282                 old = old.next;
 283 
 284                 int index = hash(e.key) % newCapacity;
 285                 e.next = newTable[index];
 286                 newTable[index] = e;
 287             }
 288         }
 289     }
 290 
 291     //
 292     // Classes
 293     //
 294 
 295     /**
 296      * This class is a key table entry. Each entry acts as a node
 297      * in a linked list.
 298      */
 299     protected static final class Entry {
 300         // key/value
 301         public Object key;
 302         public Object value;
 303         /** The next entry. */
 304         public Entry next;
 305 
 306         public Entry() {
 307             key = null;
 308             value = null;
 309             next = null;
 310         }
 311 
 312         public Entry(Object key, Object value, Entry next) {
 313             this.key = key;
 314             this.value = value;
 315             this.next = next;
 316         }
 317 
 318         public Entry makeClone() {
 319             Entry entry = new Entry();
 320             entry.key = key;
 321             entry.value = value;
 322             if (next != null)
 323                 entry.next = next.makeClone();
 324             return entry;
 325         }
 326     } // entry
 327 
 328 } // class SymbolHash