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

   1 /*******************************************************************************
   2  * Copyright (c) 2000, 2003 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 net.sourceforge.phpdt.internal.compiler.util;
  12
  13 import net.sourceforge.phpdt.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
  64                                 && CharOperation.prefixEquals(currentKey, key))
  65                                 return true;
  66                         index = (index + 1) % keyTable.length;
  67                 }
  68                 return false;
  69         }
  70
  71         public Object get(char[] key) {
  72
  73                 int index = CharOperation.hashCode(key) % valueTable.length;
  74                 int keyLength = key.length;
  75                 char[] currentKey;
  76                 while ((currentKey = keyTable[index]) != null) {
  77                         if (currentKey.length == keyLength
  78                                 && CharOperation.prefixEquals(currentKey, key))
  79                                 return valueTable[index];
  80                         index = (index + 1) % keyTable.length;
  81                 }
  82                 return null;
  83         }
  84
  85         public Object put(char[] key, Object value) {
  86
  87                 int index = CharOperation.hashCode(key) % valueTable.length;
  88                 int keyLength = key.length;
  89                 char[] currentKey;
  90                 while ((currentKey = keyTable[index]) != null) {
  91                         if (currentKey.length == keyLength
  92                                 && CharOperation.prefixEquals(currentKey, key))
  93                                 return valueTable[index] = value;
  94                         index = (index + 1) % keyTable.length;
  95                 }
  96                 keyTable[index] = key;
  97                 valueTable[index] = value;
  98
  99                 // assumes the threshold is never equal to the size of the table
 100                 if (++elementSize > threshold)
 101                         rehash();
 102                 return value;
 103         }
 104
 105         public Object removeKey(char[] key) {
 106
 107                 int index = CharOperation.hashCode(key) % valueTable.length;
 108                 int keyLength = key.length;
 109                 char[] currentKey;
 110                 while ((currentKey = keyTable[index]) != null) {
 111                         if (currentKey.length == keyLength
 112                                 && CharOperation.prefixEquals(currentKey, key)) {
 113                                         Object value = valueTable[index];
 114                                         elementSize--;
 115                                         keyTable[index] = null;
 116                                         valueTable[index] = null;
 117                                         rehash();
 118                                         return value;
 119                                 }
 120                         index = (index + 1) % keyTable.length;
 121                 }
 122                 return null;
 123         }
 124
 125         private void rehash() {
 126
 127                 HashtableOfObject newHashtable = new HashtableOfObject(elementSize * 2);                // double the number of expected elements
 128                 char[] currentKey;
 129                 for (int i = keyTable.length; --i >= 0;)
 130                         if ((currentKey = keyTable[i]) != null)
 131                                 newHashtable.put(currentKey, valueTable[i]);
 132
 133                 this.keyTable = newHashtable.keyTable;
 134                 this.valueTable = newHashtable.valueTable;
 135                 this.threshold = newHashtable.threshold;
 136         }
 137
 138         public int size() {
 139                 return elementSize;
 140         }
 141
 142         public String toString() {
 143                 String s = ""; //$NON-NLS-1$
 144                 Object object;
 145                 for (int i = 0, length = valueTable.length; i < length; i++)
 146                         if ((object = valueTable[i]) != null)
 147                                 s += new String(keyTable[i]) + " -> " + object.toString() + "\n";       //$NON-NLS-2$ //$NON-NLS-1$
 148                 return s;
 149         }
 150 }