net.sourceforge.phpeclipse/src/net/sourceforge/phpdt/internal/core/util/SimpleLookupTable.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.core.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         if (size < 3) size = 3;
  32         this.elementSize = 0;
  33         this.threshold = size + 1; // size is the expected number of elements
  34         int tableLength = 2 * size + 1;
  35         this.keyTable = new Object[tableLength];
  36         this.valueTable = new Object[tableLength];
  37 }
  38
  39 public Object clone() throws CloneNotSupportedException {
  40         SimpleLookupTable result = (SimpleLookupTable) super.clone();
  41         result.elementSize = this.elementSize;
  42         result.threshold = this.threshold;
  43
  44         int length = this.keyTable.length;
  45         result.keyTable = new Object[length];
  46         System.arraycopy(this.keyTable, 0, result.keyTable, 0, length);
  47
  48         length = this.valueTable.length;
  49         result.valueTable = new Object[length];
  50         System.arraycopy(this.valueTable, 0, result.valueTable, 0, length);
  51         return result;
  52 }
  53
  54 public boolean containsKey(Object key) {
  55         int length = keyTable.length;
  56         int index = (key.hashCode() & 0x7FFFFFFF) % length;
  57         Object currentKey;
  58         while ((currentKey = keyTable[index]) != null) {
  59                 if (currentKey.equals(key)) return true;
  60                 if (++index == length) index = 0;
  61         }
  62         return false;
  63 }
  64
  65 public Object get(Object key) {
  66         int length = keyTable.length;
  67         int index = (key.hashCode() & 0x7FFFFFFF) % length;
  68         Object currentKey;
  69         while ((currentKey = keyTable[index]) != null) {
  70                 if (currentKey.equals(key)) return valueTable[index];
  71                 if (++index == length) index = 0;
  72         }
  73         return null;
  74 }
  75
  76 public Object keyForValue(Object valueToMatch) {
  77         if (valueToMatch != null)
  78                 for (int i = 0, l = valueTable.length; i < l; i++)
  79                         if (valueToMatch.equals(valueTable[i]))
  80                                 return keyTable[i];
  81         return null;
  82 }
  83
  84 public Object put(Object key, Object value) {
  85         int length = keyTable.length;
  86         int index = (key.hashCode() & 0x7FFFFFFF) % length;
  87         Object currentKey;
  88         while ((currentKey = keyTable[index]) != null) {
  89                 if (currentKey.equals(key)) return valueTable[index] = value;
  90                 if (++index == length) index = 0;
  91         }
  92         keyTable[index] = key;
  93         valueTable[index] = value;
  94
  95         // assumes the threshold is never equal to the size of the table
  96         if (++elementSize > threshold) rehash();
  97         return value;
  98 }
  99
 100 public Object removeKey(Object key) {
 101         int length = keyTable.length;
 102         int index = (key.hashCode() & 0x7FFFFFFF) % length;
 103         Object currentKey;
 104         while ((currentKey = keyTable[index]) != null) {
 105                 if (currentKey.equals(key)) {
 106                         elementSize--;
 107                         Object oldValue = valueTable[index];
 108                         keyTable[index] = null;
 109                         valueTable[index] = null;
 110                         if (keyTable[index + 1 == length ? 0 : index + 1] != null)
 111                                 rehash(); // only needed if a possible collision existed
 112                         return oldValue;
 113                 }
 114                 if (++index == length) index = 0;
 115         }
 116         return null;
 117 }
 118
 119 public void removeValue(Object valueToRemove) {
 120         boolean rehash = false;
 121         for (int i = 0, l = valueTable.length; i < l; i++) {
 122                 Object value = valueTable[i];
 123                 if (value != null && value.equals(valueToRemove)) {
 124                         elementSize--;
 125                         keyTable[i] = null;
 126                         valueTable[i] = null;
 127                         if (!rehash && keyTable[i + 1 == l ? 0 : i + 1] != null)
 128                                 rehash = true; // only needed if a possible collision existed
 129                 }
 130         }
 131         if (rehash) rehash();
 132 }
 133
 134 private void rehash() {
 135         SimpleLookupTable newLookupTable = new SimpleLookupTable(elementSize * 2); // double the number of expected elements
 136         Object currentKey;
 137         for (int i = keyTable.length; --i >= 0;)
 138                 if ((currentKey = keyTable[i]) != null)
 139                         newLookupTable.put(currentKey, valueTable[i]);
 140
 141         this.keyTable = newLookupTable.keyTable;
 142         this.valueTable = newLookupTable.valueTable;
 143         this.elementSize = newLookupTable.elementSize;
 144         this.threshold = newLookupTable.threshold;
 145 }
 146
 147 public String toString() {
 148         String s = ""; //$NON-NLS-1$
 149         Object object;
 150         for (int i = 0, l = valueTable.length; i < l; i++)
 151                 if ((object = valueTable[i]) != null)
 152                         s += keyTable[i].toString() + " -> " + object.toString() + "\n";        //$NON-NLS-2$ //$NON-NLS-1$
 153         return s;
 154 }
 155 }