persistentbytemap.java

gcc的组建

/* Copyright (C) 2004, 2005  Free Software Foundation

   This file is part of libgcj.

This software is copyrighted work licensed under the terms of the
Libgcj License.  Please consult the file "LIBGCJ_LICENSE" for
details.  */



/*  A PersistentByteMap maps a byte array to another byte array.  It
uses a file that does not need to be serialized but may be
memory-mapped and read in-place.  So, even if there are many instances
of gcj applications running, they can share PersistentByteMaps.

The idea is to make searches as fast as possible: opening a
PersistentByteMap is cheap and search time doesn't grow with the
number of entries in the table.  On the other hand, enumerating the
map is slow, but that is a relatively uncommon operation.

The main use of this class is to provide a way to map the
MessageDigest of a class file to the location of a DSO that contains
the compiled version of that class.  It is up the the installer of an
application to keep the DSO up to date with the jar.  

USAGE:
        MessageDigest md = MessageDigest.getInstance("MD5");
        digest = md.digest(bytes);

        PersistentByteMap map 
          = new PersistentByteMap
            (fileName, PersistentByteMap.AccessMode.READ_ONLY);

        byte[] soName = map.get(digest);
        if (soName)
          {
            String SharedLibraryName = new String(soName);

BUGS/FEATURES:
        remove() isn't written yet.

        capacity is fixed once the map has been created.

        We use linear probing to resolve collisions.  It might be
        better to use a scheme that results in fewer probes to
        determine that an item isn't found.  However, even when the
        table is half full there are only on average 1.5 probes for a
        successful search and 2.5 probes for an unsuccessful one.

	We don't do any locking at all: adding to a PersistentByteMap
	at runtime is possible, but it requires filesystem locks
	around get(), put(), and remove().
*/

package gnu.gcj.runtime;

import java.io.*;
import java.nio.*;
import java.nio.channels.*;
import java.util.*;
import java.security.MessageDigest;
import java.math.BigInteger;

public class PersistentByteMap
{
  private MappedByteBuffer buf;

  static private final int MAGIC = 0;
  static private final int VERSION = 4;
  static private final int CAPACITY = 8;
  static private final int TABLE_BASE = 12;
  static private final int STRING_BASE = 16;
  static private final int STRING_SIZE = 20;
  static private final int FILE_SIZE = 24;
  static private final int ELEMENTS = 28;
  
  static private final int INT_SIZE = 4;

  static private final int TABLE_ENTRY_SIZE = 2 * INT_SIZE;

  private int capacity;   // number of entries
  private int table_base;   // offset from start of file, in bytes
  private int string_base;  // offset from start of file, in bytes
  private int string_size;  // size of string table, in bytes
  private int file_size;    // size of file, in bytes;
  private int elements;     // number of elements in table

  private long length;      // the length of the underlying file

  private final File name;  // The name of the underlying file

  static private final int UNUSED_ENTRY = -1; 

  static public final int KEYS = 0;
  static public final int VALUES = 1;
  static public final int ENTRIES = 2;

  private HashMap values;   // A map of strings in the string table.

  FileChannel fc;           // The underlying file channel.

  static final public class AccessMode
  {
    private final FileChannel.MapMode mapMode;

    static
    {
      READ_ONLY = new AccessMode(FileChannel.MapMode.READ_ONLY);
      READ_WRITE = new AccessMode(FileChannel.MapMode.READ_WRITE);
      PRIVATE = new AccessMode(FileChannel.MapMode.PRIVATE);
    }

    public static final AccessMode READ_ONLY;
    public static final AccessMode READ_WRITE; 
    public static final AccessMode PRIVATE;

    private AccessMode(FileChannel.MapMode mode)
    {
      this.mapMode = mode;
    }
  }

  private PersistentByteMap(File name)
  {
    this.name = name;
  }

  public PersistentByteMap(String filename, AccessMode mode)
    throws IOException 
  {
    this(new File(filename), mode);
  }

  public PersistentByteMap(File f, AccessMode mode)
    throws IOException 
  {
    name = f;

    if (mode == AccessMode.READ_ONLY)
      {
        FileInputStream fis = new FileInputStream(f);
        fc = fis.getChannel();
      }
    else
      {
        RandomAccessFile fos = new RandomAccessFile(f, "rw");
        fc = fos.getChannel();
      }

    length = fc.size();
    buf = fc.map(mode.mapMode, 0, length);

    int magic = getWord (MAGIC);
    if (magic != 0x67636a64) /* "gcjd" */
      throw new IllegalArgumentException(f.getName());

    table_base = getWord (TABLE_BASE);
    capacity = getWord (CAPACITY);
    string_base = getWord (STRING_BASE);
    string_size = getWord (STRING_SIZE);
    file_size = getWord (FILE_SIZE);
    elements = getWord (ELEMENTS);

    // FIXME:  Insert a bunch of sanity checks here
  }

  private void init (PersistentByteMap m, File f, int capacity, int strtabSize)
    throws IOException 
  {
    f.createNewFile();
    RandomAccessFile raf = new RandomAccessFile(f, "rw");

    {        
      // The user has explicitly provided a size for the table.
      // We're going to make that size prime.  This isn't
      // strictly necessary but it can't hurt.
      //
      // We expand the size by 3/2 and round the result because the
      // hash table is intolerably slow when more than 2/3 full.
      
      BigInteger size = new BigInteger(Integer.toString(((capacity*3)+1)/2));
      BigInteger two = BigInteger.ONE.add(BigInteger.ONE);
      
      if (size.getLowestSetBit() != 0) // A hard way to say isEven()
	size = size.add(BigInteger.ONE);
    
      while (! size.isProbablePrime(10))
	size = size.add(two);
      
      this.capacity = capacity = size.intValue();
    }

    table_base = 64;
    string_base = table_base + capacity * TABLE_ENTRY_SIZE;
    string_size = 0;
    file_size = string_base;
    elements = 0;

    int totalFileSize = string_base + strtabSize;

    // Create the file; this rounds up the size of the file to a fixed
    // number of 4k pages.
    byte[] _4k = new byte[4096];
    for (long i = 0; i < totalFileSize; i+= 4096)
      raf.write(_4k);
        
    fc = raf.getChannel();
    buf = fc.map(FileChannel.MapMode.READ_WRITE, 0, raf.length());

    for (int i = 0; i < capacity; i++)
      putKeyPos(UNUSED_ENTRY, i);
        
    putWord(0x67636a64, MAGIC);
    putWord(0x01, VERSION);
    putWord(capacity, CAPACITY);
    putWord(table_base, TABLE_BASE);
    putWord(string_base, STRING_BASE);
    putWord(file_size, FILE_SIZE);
    putWord(elements, ELEMENTS);
    buf.force();

    length = fc.size();
    string_size = 0;
  }     

  static public PersistentByteMap 
  emptyPersistentByteMap(File name, int capacity, int strtabSize)
    throws IOException 
  {
    PersistentByteMap m = new PersistentByteMap(name);
    m.init(m, name, capacity, strtabSize);
    return m;
  }     

  private int getWord (int index)
  {
    buf.position(index);
    byte[] wordBuf = new byte[4];
    buf.get(wordBuf);

    int result = (int)wordBuf[0]&0xff;
    result += ((int)wordBuf[1]&0xff) << 8;
    result += ((int)wordBuf[2]&0xff) << 16;
    result += ((int)wordBuf[3]&0xff) << 24;
    return result;
  }

  private void putWord (int word, int index)
  {
    buf.position(index);
    byte[] wordBuf = new byte[4];
    wordBuf[0] = (byte)(word);
    wordBuf[1] = (byte)(word >>> 8);
    wordBuf[2] = (byte)(word >>> 16);
    wordBuf[3] = (byte)(word >>> 24);
    buf.put(wordBuf);
  }

  public Set entrySet()
  {
    return null;
  }

  private int getBucket(int n)
  {
    return table_base + (2*n * INT_SIZE);
  }

  private int getKeyPos(int n)
  {
    return getWord(getBucket(n));
  }
  
  private int getValuePos(int n)
  {
    return getWord(getBucket(n) + INT_SIZE);
  }

  private void putKeyPos(int index, int n)
  {
    putWord(index, getBucket(n));
  }

  private void putValuePos(int index, int n)
  {
    putWord(index, getBucket(n) + INT_SIZE);
  }

  private byte[] getBytes(int n)
  {
    int len = getWord (string_base + n);
    int base = string_base + n + INT_SIZE;
    byte[] key = new byte[len];
    buf.position(base);
    buf.get(key, 0, len);
    return key;
  }

  private int hash (byte[] b)
  {    
    // We assume that the message digest is evenly distributed, so we
    // only need to use a few bytes of it as the hash function.
    long hashIndex 
      = ((b[0]&0xffL)
         + ((b[1]&0xffL)<<8) 
         + ((b[2]&0xffL)<<16) 
         + ((b[3]&0xffL)<<24));
    long result = hashIndex % (long)capacity;
    return (int)result;
  }