src/org/eclipse/jdt/internal/compiler/util/HashtableOfObject.java

   1 /*******************************************************************************
   2  * Copyright (c) 2000, 2004 IBM Corporation and others.
   3  * All rights reserved. This program and the accompanying materials
   4  * are made available under the terms of the Common Public License v1.0
   5  * which accompanies this distribution, and is available at
   6  * http://www.eclipse.org/legal/cpl-v10.html
   7  *
   8  * Contributors:
   9  *     IBM Corporation - initial API and implementation
  10  *******************************************************************************/
  11 package org.eclipse.jdt.internal.compiler.util;
  12
  13 import org.eclipse.jdt.core.compiler.CharOperation;
  14
  15 /**
  16  * Hashtable of {char[] --> Object }
  17  */
  18 public final class HashtableOfObject implements Cloneable {
  19
  20         // to avoid using Enumerations, walk the individual tables skipping nulls
  21         public char[] keyTable[];
  22         public Object valueTable[];
  23
  24         public int elementSize; // number of elements in the table
  25         int threshold;
  26
  27         public HashtableOfObject() {
  28                 this(13);
  29         }
  30
  31         public HashtableOfObject(int size) {
  32
  33                 this.elementSize = 0;
  34                 this.threshold = size; // size represents the expected number of elements
  35                 int extraRoom = (int) (size * 1.75f);
  36                 if (this.threshold == extraRoom)
  37                         extraRoom++;
  38                 this.keyTable = new char[extraRoom][];
  39                 this.valueTable = new Object[extraRoom];
  40         }
  41
  42         public Object clone() throws CloneNotSupportedException {
  43                 HashtableOfObject result = (HashtableOfObject) super.clone();
  44                 result.elementSize = this.elementSize;
  45                 result.threshold = this.threshold;
  46
  47                 int length = this.keyTable.length;
  48                 result.keyTable = new char[length][];
  49                 System.arraycopy(this.keyTable, 0, result.keyTable, 0, length);
  50
  51                 length = this.valueTable.length;
  52                 result.valueTable = new Object[length];
  53                 System.arraycopy(this.valueTable, 0, result.valueTable, 0, length);
  54                 return result;
  55         }
  56
  57         public boolean containsKey(char[] key) {
  58
  59                 int index = CharOperation.hashCode(key) % valueTable.length;
  60                 int keyLength = key.length;
  61                 char[] currentKey;
  62                 while ((currentKey = keyTable[index]) != null) {
  63                         if (currentKey.length == keyLength && CharOperation.equals(currentKey, key))
  64                                 return true;
  65                         index = (index + 1) % keyTable.length;
  66                 }
  67                 return false;
  68         }
  69
  70         public Object get(char[] key) {
  71
  72                 int index = CharOperation.hashCode(key) % valueTable.length;
  73                 int keyLength = key.length;
  74                 char[] currentKey;
  75                 while ((currentKey = keyTable[index]) != null) {
  76                         if (currentKey.length == keyLength && CharOperation.equals(currentKey, key))
  77                                 return valueTable[index];
  78                         index = (index + 1) % keyTable.length;
  79                 }
  80                 return null;
  81         }
  82
  83         public Object put(char[] key, Object value) {
  84
  85                 int index = CharOperation.hashCode(key) % valueTable.length;
  86                 int keyLength = key.length;
  87                 char[] currentKey;
  88                 while ((currentKey = keyTable[index]) != null) {
  89                         if (currentKey.length == keyLength && CharOperation.equals(currentKey, key))
  90                                 return valueTable[index] = value;
  91                         index = (index + 1) % keyTable.length;
  92                 }
  93                 keyTable[index] = key;
  94                 valueTable[index] = value;
  95
  96                 // assumes the threshold is never equal to the size of the table
  97                 if (++elementSize > threshold)
  98                         rehash();
  99                 return value;
 100         }
 101
 102         public Object removeKey(char[] key) {
 103
 104                 int index = CharOperation.hashCode(key) % valueTable.length;
 105                 int keyLength = key.length;
 106                 char[] currentKey;
 107                 while ((currentKey = keyTable[index]) != null) {
 108                         if (currentKey.length == keyLength && CharOperation.equals(currentKey, key)) {
 109                                 Object value = valueTable[index];
 110                                 elementSize--;
 111                                 keyTable[index] = null;
 112                                 valueTable[index] = null;
 113                                 rehash();
 114                                 return value;
 115                         }
 116                         index = (index + 1) % keyTable.length;
 117                 }
 118                 return null;
 119         }
 120
 121         private void rehash() {
 122
 123                 HashtableOfObject newHashtable = new HashtableOfObject(elementSize * 2);                // double the number of expected elements
 124                 char[] currentKey;
 125                 for (int i = keyTable.length; --i >= 0;)
 126                         if ((currentKey = keyTable[i]) != null)
 127                                 newHashtable.put(currentKey, valueTable[i]);
 128
 129                 this.keyTable = newHashtable.keyTable;
 130                 this.valueTable = newHashtable.valueTable;
 131                 this.threshold = newHashtable.threshold;
 132         }
 133
 134         public int size() {
 135                 return elementSize;
 136         }
 137
 138         public String toString() {
 139                 String s = ""; //$NON-NLS-1$
 140                 Object object;
 141                 for (int i = 0, length = valueTable.length; i < length; i++)
 142                         if ((object = valueTable[i]) != null)
 143                                 s += new String(keyTable[i]) + " -> " + object.toString() + "\n";       //$NON-NLS-2$ //$NON-NLS-1$
 144                 return s;
 145         }
 146 }