All Packages  This Package  Class Hierarchy  Class Search  Index

Class calypso.util.IDMap

java.lang.Object
   |
   +----calypso.util.IDMap

An identifier mapper. This provides a 1-1 map between strings and integers where the strings are unique within the map.

public class  IDMap
     extends java.lang.Object
{
          // Fields 12
     private static final int A;
     private static final int DEFAULT;
     private static final int EMPTY;
     private int fCapacity;
     private int fCount;
     private int[] fHashCodes;
     private int fIndexMask;
     private Object[] fKeys;
     private int fNumStrings;
     private int fShift;
     private String[] fStrings;
     private int[] fValues;

          // Constructors 1
     public IDMap();

          // Methods 11
     private int addString(String);
     private void grow();
     private final int hashCodeForString(String);
     private final int hashCodeForStringBuf(StringBuf);
     public String idToString(int);
     private final boolean keysAreEqual(Object, Object);
     public synchronized int stringBufToID(StringBuf);
     public synchronized String stringBufToString(StringBuf);
     public synchronized int stringToID(String);
     public synchronized String stringToString(String);
     private int tableIndexFor(Object, int);
}

• fKeys

   private Object[] fKeys

• fHashCodes

   private int[] fHashCodes

• fValues

   private int[] fValues

• fStrings

   private String[] fStrings

• fNumStrings

   private int fNumStrings

• fShift

   private int fShift

• fIndexMask

   private int fIndexMask

• fCount

   private int fCount

• fCapacity

   private int fCapacity

• A

   private static final int A

For the multiplicative hash, choose the golden ratio:

     A = ((sqrt(5) - 1) / 2) * (1 << 32)
 

ala Knuth...

• EMPTY

   private static final int EMPTY

We use EMPTY and REMOVED as special markers in the table. If some poor object returns one of these two values as their hashCode, it is wacked to DEFAULT.

• DEFAULT

   private static final int DEFAULT

• IDMap

   public IDMap() 

• stringToID

   public synchronized int stringToID(String aStr) 

Given a string, find an id for it. If the string is already present return the old id. Otherwise allocate a new one.

• stringBufToID

   public synchronized int stringBufToID(StringBuf aStrBuf) 

Given a StringBuf, find an id for it. If the string is already present return the old id. Otherwise allocate a new one.

• stringBufToString

   public synchronized String stringBufToString(StringBuf aStrBuf) 

• stringToString

   public synchronized String stringToString(String aStr) 

If the argument string is already present in the map return the original string object. Otherwise, allocate a new id and return the argument string.

• idToString

   public String idToString(int aID) 

Given an id, return the string it maps to.

• addString

   private int addString(String aString) 

Add string to the end of the internal strings array. Return the index in the array.

• hashCodeForString

   private final int hashCodeForString(String str) 

Provide hashcode for a given key

• hashCodeForStringBuf

   private final int hashCodeForStringBuf(StringBuf strBuf) 

• keysAreEqual

   private final boolean keysAreEqual(Object aKey1, 
                                      Object aKey2) 

• tableIndexFor

   private int tableIndexFor(Object aKey, 
                             int aHash) 

Primitive method used internally to find slots in the table. If the key is present in the table, this method will return the index under which it is stored. If the key is not present, then this method will return the index under which it can be put. The caller must look at the hashCode at that index to differentiate between the two possibilities.

• grow

   private void grow() 

Grows the table by a factor of 2 (or creates it if necessary). All the REMOVED markers go away and the elements are rehashed into the bigger table.

All Packages  This Package  Class Hierarchy  Class Search  Index