| /* 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; |
| } |
| |
| 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); |
| } |
| } |
| } |