src/org/eclipse/jdt/internal/compiler/util/SimpleLookupTable.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 /**
  14  * A simple lookup table is a non-synchronized Hashtable, whose keys
  15  * and values are Objects. It also uses linear probing to resolve collisions
  16  * rather than a linked list of hash table entries.
  17  */
  18 public final class SimpleLookupTable implements Cloneable {
  19
  20 // to avoid using Enumerations, walk the individual tables skipping nulls
  21 public Object[] keyTable;
  22 public Object[] valueTable;
  23 public int elementSize; // number of elements in the table
  24 public int threshold;
  25
  26 public SimpleLookupTable() {
  27         this(13);
  28 }
  29
  30 public SimpleLookupTable(int size) {
  31         this.elementSize = 0;
  32         this.threshold = size; // size represents the expected number of elements
  33         int extraRoom = (int) (size * 1.5f);
  34         if (this.threshold == extraRoom)
  35                 extraRoom++;
  36         this.keyTable = new Object[extraRoom];
  37         this.valueTable = new Object[extraRoom];
  38 }
  39
  40 public Object clone() throws CloneNotSupportedException {
  41         SimpleLookupTable result = (SimpleLookupTable) super.clone();
  42         result.elementSize = this.elementSize;
  43         result.threshold = this.threshold;
  44
  45         int length = this.keyTable.length;
  46         result.keyTable = new Object[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(Object key) {
  56         int length = keyTable.length;
  57         int index = (key.hashCode() & 0x7FFFFFFF) % length;
  58         Object currentKey;
  59         while ((currentKey = keyTable[index]) != null) {
  60                 if (currentKey.equals(key)) return true;
  61                 if (++index == length) index = 0;
  62         }
  63         return false;
  64 }
  65
  66 public Object get(Object key) {
  67         int length = keyTable.length;
  68         int index = (key.hashCode() & 0x7FFFFFFF) % length;
  69         Object currentKey;
  70         while ((currentKey = keyTable[index]) != null) {
  71                 if (currentKey.equals(key)) return valueTable[index];
  72                 if (++index == length) index = 0;
  73         }
  74         return null;
  75 }
  76
  77 public Object keyForValue(Object valueToMatch) {
  78         if (valueToMatch != null)
  79                 for (int i = 0, l = valueTable.length; i < l; i++)
  80                         if (valueToMatch.equals(valueTable[i]))
  81                                 return keyTable[i];
  82         return null;
  83 }
  84
  85 public Object put(Object key, Object value) {
  86         int length = keyTable.length;
  87         int index = (key.hashCode() & 0x7FFFFFFF) % length;
  88         Object currentKey;
  89         while ((currentKey = keyTable[index]) != null) {
  90                 if (currentKey.equals(key)) return valueTable[index] = value;
  91                 if (++index == length) index = 0;
  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) rehash();
  98         return value;
  99 }
 100
 101 public Object removeKey(Object key) {
 102         int length = keyTable.length;
 103         int index = (key.hashCode() & 0x7FFFFFFF) % length;
 104         Object currentKey;
 105         while ((currentKey = keyTable[index]) != null) {
 106                 if (currentKey.equals(key)) {
 107                         elementSize--;
 108                         Object oldValue = valueTable[index];
 109                         keyTable[index] = null;
 110                         valueTable[index] = null;
 111                         if (keyTable[index + 1 == length ? 0 : index + 1] != null)
 112                                 rehash(); // only needed if a possible collision existed
 113                         return oldValue;
 114                 }
 115                 if (++index == length) index = 0;
 116         }
 117         return null;
 118 }
 119
 120 public void removeValue(Object valueToRemove) {
 121         boolean rehash = false;
 122         for (int i = 0, l = valueTable.length; i < l; i++) {
 123                 Object value = valueTable[i];
 124                 if (value != null && value.equals(valueToRemove)) {
 125                         elementSize--;
 126                         keyTable[i] = null;
 127                         valueTable[i] = null;
 128                         if (!rehash && keyTable[i + 1 == l ? 0 : i + 1] != null)
 129                                 rehash = true; // only needed if a possible collision existed
 130                 }
 131         }
 132         if (rehash) rehash();
 133 }
 134
 135 private void rehash() {
 136         SimpleLookupTable newLookupTable = new SimpleLookupTable(elementSize * 2); // double the number of expected elements
 137         Object currentKey;
 138         for (int i = keyTable.length; --i >= 0;)
 139                 if ((currentKey = keyTable[i]) != null)
 140                         newLookupTable.put(currentKey, valueTable[i]);
 141
 142         this.keyTable = newLookupTable.keyTable;
 143         this.valueTable = newLookupTable.valueTable;
 144         this.elementSize = newLookupTable.elementSize;
 145         this.threshold = newLookupTable.threshold;
 146 }
 147
 148 public String toString() {
 149         String s = ""; //$NON-NLS-1$
 150         Object object;
 151         for (int i = 0, l = valueTable.length; i < l; i++)
 152                 if ((object = valueTable[i]) != null)
 153                         s += keyTable[i].toString() + " -> " + object.toString() + "\n";        //$NON-NLS-2$ //$NON-NLS-1$
 154         return s;
 155 }
 156 }