persistentbytemap.java

gcc的组建

        
  public byte[] get(byte[] digest)
  {
    int hashIndex = hash(digest);

    do
      {
        int k = getKeyPos(hashIndex);
        if (k == UNUSED_ENTRY)
          return null;

        if (Arrays.equals ((byte[])digest, getBytes(k)))
          return getBytes(getValuePos(hashIndex));
                
        // Use linear probing to resolve hash collisions.  This may
        // not be theoretically as good as open addressing, but it has
        // good cache behviour.
        hashIndex++;
        hashIndex %= capacity;
      }
    while (true);
  }

  public void put(byte[] digest, byte[] value)
    throws IllegalAccessException
  {
    int hashIndex = hash(digest);

    if (elements >= capacity())
      throw new IllegalAccessException("Table Full: " + elements);

    do
      {
        int k = getKeyPos(hashIndex);
        if (k == UNUSED_ENTRY)
          {
            int newKey = addBytes(digest);
            putKeyPos(newKey, hashIndex);
            int newValue = addBytes(value);
            putValuePos(newValue, hashIndex);
            elements++;
            putWord(elements, ELEMENTS);            
            return;
          }
        else if (Arrays.equals (digest, getBytes(k)))
          {
            int newValue = addBytes((byte[])value);
            putValuePos(newValue, hashIndex);
            return;
          }
                
        hashIndex++;
        hashIndex %= capacity;
      }
    while (true);
  }

  private int addBytes (byte[] data)
    throws IllegalAccessException
  {
    if (data.length > 16)
      {
	// Keep track of long strings in the hope that we will be able
	// to re-use them.
	if (values == null)
	  {
	    values = new HashMap();
	
	    for (int i = 0; i < capacity; i++)
	      if (getKeyPos(i) != UNUSED_ENTRY)
		{
		  int pos = getValuePos(i);
		  ByteWrapper bytes = new ByteWrapper(getBytes(pos));
		  values.put(bytes, new Integer(pos));
		}
	  }

	{
	  Object result = values.get(new ByteWrapper(data));
	  if (result != null)
	    {
	      // We already have this value in the string table
	      return ((Integer)result).intValue();
	    }
	}
      }

    if (data.length + INT_SIZE >= this.length)
      throw new IllegalAccessException("String table Full");

    int extent = string_base+string_size;
    int top = extent;
    putWord(data.length, extent);
    extent += INT_SIZE;
    buf.position(extent);
    buf.put(data, 0, data.length);
    extent += data.length;
    extent += INT_SIZE-1;
    extent &= ~(INT_SIZE-1); // align
    string_size = extent - string_base;
    file_size = extent;
    putWord (string_size, STRING_SIZE);
    putWord (file_size, FILE_SIZE);

    if (data.length > 16)
      values.put(new ByteWrapper(data), new Integer(top - string_base));
        
    return top - string_base;
  }

  public Iterator iterator(int type)
  {
    return new HashIterator(type);
  }

  public int size()
  {
    return elements;
  }

  public int stringTableSize()
  {
    return string_size;
  }

  public int capacity()
  {
    // With the the table 2/3 full there will be on average 2 probes
    // for a successful search and 5 probes for an unsuccessful one.
    return capacity * 2/3;
  }

  public void force()
  {
    buf.force();
  }

  public File getFile()
  {
    return name;
  }

  // Close the map.  Once this has been done, the map can no longer be
  // used.
  public void close() throws IOException
  {
    force();
    fc.close();
  }

  public void 
  putAll(PersistentByteMap t)
    throws IllegalAccessException
  {
    // We can use a fast copy if the size of a map has not changed.
    if (this.elements == 0 && t.capacity == this.capacity
	&& t.length == this.length)
      {
	this.buf.position(0);
	t.buf.position(0);
	this.buf.put(t.buf);
	this.table_base = t.table_base;
	this.string_base = t.string_base;
	this.string_size = t.string_size;
	this.file_size = t.file_size;
	this.elements = t.elements;
	if (t.values != null)
	  this.values = (HashMap)t.values.clone();
	return;
      }

    // Otherwise do it the hard way.
    Iterator iterator = t.iterator(PersistentByteMap.ENTRIES);
    while (iterator.hasNext())
      {
	PersistentByteMap.MapEntry entry 
	  = (PersistentByteMap.MapEntry)iterator.next();
	this.put((byte[])entry.getKey(), (byte[])entry.getValue());
      }
  }
	

  private final class HashIterator implements Iterator
  {
    /** Current index in the physical hash table. */

    private int idx;
    private int count;
    private final int type;

    /**
     * Construct a new HashIterator with the supplied type.
     * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
     */
    HashIterator(int type)
    {
      this.type = type;
      count = elements;
      idx = 0;
    }

    /**
     * Returns true if the Iterator has more elements.
     * @return true if there are more elements
     * @throws ConcurrentModificationException if the HashMap was modified
     */
    public boolean hasNext()
    {
      return count > 0;
    }

    /**
     * Returns the next element in the Iterator's sequential view.
     * @return the next element
     * @throws ConcurrentModificationException if the HashMap was modified
     * @throws NoSuchElementException if there is none
     */
    public Object next()
    {
      count--;
      for (int i = idx; i < capacity; i++)
        if (getKeyPos(i) != UNUSED_ENTRY)
          {
            idx = i+1;
            if (type == VALUES)
              return getBytes(getValuePos(i));
            if (type == KEYS)
              return getBytes(getKeyPos(i));
            return new MapEntry(i,
                                getBytes(getKeyPos(i)),
                                getBytes(getValuePos(i)));
          }
      return null;
    }    

    /**
     * Remove from the underlying collection the last element returned
     * by next (optional operation). This method can be called only
     * once after each call to <code>next()</code>. It does not affect
     * what will be returned by subsequent calls to next.
     *
     * @throws IllegalStateException if next has not yet been called
     *         or remove has already been called since the last call
     *         to next.
     * @throws UnsupportedOperationException if this Iterator does not
     *         support the remove operation.
     */
     public void remove()
    {
      throw new UnsupportedOperationException();
    }
  }

  static public final class MapEntry
  {
    private final Object key;
    private final Object value;
    private final int bucket;

    public MapEntry(int bucket, Object newKey, Object newValue)
    {
      this.key = newKey;
      this.value = newValue;
      this.bucket = bucket;
    }

    public final Object getKey()
    {
      return key;
    }

    public final Object getValue()
    {
      return value;
    }

    public final int getBucket()
    {
      return bucket;
    }
  }

  // A wrapper class for a byte array that allows collections to be
  // made.
  private final class ByteWrapper
  {
    final byte[] bytes;
    final int hash;

    public ByteWrapper (byte[] bytes)
    {
      int sum = 0;
      this.bytes = bytes;
      for (int i = 0; i < bytes.length; i++)
	sum += bytes[i];
      hash = sum;
    }

    public int hashCode()
    {
      return hash;
    }
  
    public boolean equals(Object obj)
    {
      return Arrays.equals(bytes, ((ByteWrapper)obj).bytes);
    }
  }
}