net.sourceforge.phpeclipse/src/net/sourceforge/phpdt/internal/compiler/util/HashtableOfIntValues.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 net.sourceforge.phpdt.internal.compiler.util;
  12
  13 import net.sourceforge.phpdt.core.compiler.CharOperation;
  14
  15 /**
  16  * Hashtable of {char[] --> int}
  17  */
  18 public final class HashtableOfIntValues implements Cloneable {
  19
  20         public static final int NO_VALUE = Integer.MIN_VALUE;
  21
  22         // to avoid using Enumerations, walk the individual tables skipping nulls
  23         public char[] keyTable[];
  24         public int valueTable[];
  25
  26         public int elementSize; // number of elements in the table
  27         int threshold;
  28
  29         public HashtableOfIntValues() {
  30                 this(13);
  31         }
  32
  33         public HashtableOfIntValues(int size) {
  34
  35                 this.elementSize = 0;
  36                 this.threshold = size; // size represents the expected number of elements
  37                 int extraRoom = (int) (size * 1.75f);
  38                 if (this.threshold == extraRoom)
  39                         extraRoom++;
  40                 this.keyTable = new char[extraRoom][];
  41                 this.valueTable = new int[extraRoom];
  42         }
  43
  44         public Object clone() throws CloneNotSupportedException {
  45                 HashtableOfIntValues result = (HashtableOfIntValues) super.clone();
  46                 result.elementSize = this.elementSize;
  47                 result.threshold = this.threshold;
  48
  49                 int length = this.keyTable.length;
  50                 result.keyTable = new char[length][];
  51                 System.arraycopy(this.keyTable, 0, result.keyTable, 0, length);
  52
  53                 length = this.valueTable.length;
  54                 result.valueTable = new int[length];
  55                 System.arraycopy(this.valueTable, 0, result.valueTable, 0, length);
  56                 return result;
  57         }
  58
  59         public boolean containsKey(char[] key) {
  60
  61                 int index = CharOperation.hashCode(key) % valueTable.length;
  62                 int keyLength = key.length;
  63                 char[] currentKey;
  64                 while ((currentKey = keyTable[index]) != null) {
  65                         if (currentKey.length == keyLength && CharOperation.equals(currentKey, key))
  66                                 return true;
  67                         index = (index + 1) % keyTable.length;
  68                 }
  69                 return false;
  70         }
  71
  72         public int get(char[] key) {
  73
  74                 int index = CharOperation.hashCode(key) % valueTable.length;
  75                 int keyLength = key.length;
  76                 char[] currentKey;
  77                 while ((currentKey = keyTable[index]) != null) {
  78                         if (currentKey.length == keyLength && CharOperation.equals(currentKey, key))
  79                                 return valueTable[index];
  80                         index = (index + 1) % keyTable.length;
  81                 }
  82                 return NO_VALUE;
  83         }
  84
  85         public int put(char[] key, int 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 && CharOperation.equals(currentKey, key))
  92                                 return valueTable[index] = value;
  93                         index = (index + 1) % keyTable.length;
  94                 }
  95                 keyTable[index] = key;
  96                 valueTable[index] = value;
  97
  98                 // assumes the threshold is never equal to the size of the table
  99                 if (++elementSize > threshold)
 100                         rehash();
 101                 return value;
 102         }
 103
 104         public int removeKey(char[] key) {
 105
 106                 int index = CharOperation.hashCode(key) % valueTable.length;
 107                 int keyLength = key.length;
 108                 char[] currentKey;
 109                 while ((currentKey = keyTable[index]) != null) {
 110                         if (currentKey.length == keyLength && CharOperation.equals(currentKey, key)) {
 111                                 int value = valueTable[index];
 112                                 elementSize--;
 113                                 keyTable[index] = null;
 114                                 valueTable[index] = NO_VALUE;
 115                                 rehash();
 116                                 return value;
 117                         }
 118                         index = (index + 1) % keyTable.length;
 119                 }
 120                 return NO_VALUE;
 121         }
 122
 123         private void rehash() {
 124
 125                 HashtableOfIntValues newHashtable = new HashtableOfIntValues(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                 char[] key;
 143                 for (int i = 0, length = valueTable.length; i < length; i++)
 144                         if ((key = keyTable[i]) != null)
 145                                 s += new String(key) + " -> " + valueTable[i] + "\n";   //$NON-NLS-2$ //$NON-NLS-1$
 146                 return s;
 147         }
 148 }