net.sourceforge.phpeclipse/src/net/sourceforge/phpdt/internal/compiler/util/HashtableOfObject.java

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