OSDN Git Service

2005-02-16 Andrew Haley <aph@redhat.com>
authoraph <aph@138bc75d-0d04-0410-961f-82ee72b054a4>
Wed, 16 Feb 2005 17:32:59 +0000 (17:32 +0000)
committeraph <aph@138bc75d-0d04-0410-961f-82ee72b054a4>
Wed, 16 Feb 2005 17:32:59 +0000 (17:32 +0000)
        * gnu/gcj/runtime/PersistentByteMap.java (name, values, fc): new
        fields.
        (PersistentByteMap): Set name
        Magic number changed to 0x67636a64 ("gcjd").
        (init): Force the map to be prime.
        (emptyPersistentByteMap): File name was a string, now a File.
        (addBytes): Share srings between entries.
        (stringTableSize): New method.
        (capacity): Scale by load factor.
        (force): New method.
        (getFile): New method.
        (close): New method.
        (putAll): New method.
        (ByteWrapper): New class.
        * gnu/gcj/tools/gcj_dbtool/Main.java (verbose): New field.
        (main): Guess the average string size as 32, not 64.
        Copy a database before modifying it, so that we can update a
        database in a running system.
        If a database isn't big enough, resize it.
        "-m": new option: merges databases.
        "-a": Create a new detabase if it doesn't exist.
        (usage): Correct, add new option.
        (addJar): Copy a database before modifying it.
        (resizeMap): New method.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@95110 138bc75d-0d04-0410-961f-82ee72b054a4

libjava/ChangeLog
libjava/gnu/gcj/runtime/PersistentByteMap.java
libjava/gnu/gcj/tools/gcj_dbtool/Main.java

index abc0d70..d6a90bd 100644 (file)
@@ -1,3 +1,30 @@
+2005-02-16  Andrew Haley  <aph@redhat.com>
+
+       * gnu/gcj/runtime/PersistentByteMap.java (name, values, fc): new
+       fields.
+       (PersistentByteMap): Set name
+       Magic number changed to 0x67636a64 ("gcjd").
+       (init): Force the map to be prime.
+       (emptyPersistentByteMap): File name was a string, now a File.
+       (addBytes): Share srings between entries.
+       (stringTableSize): New method.
+       (capacity): Scale by load factor.
+       (force): New method.
+       (getFile): New method.
+       (close): New method.
+       (putAll): New method.
+       (ByteWrapper): New class.
+       * gnu/gcj/tools/gcj_dbtool/Main.java (verbose): New field.
+       (main): Guess the average string size as 32, not 64.
+       Copy a database before modifying it, so that we can update a
+       database in a running system.
+       If a database isn't big enough, resize it.
+       "-m": new option: merges databases.
+       "-a": Create a new detabase if it doesn't exist.
+       (usage): Correct, add new option.
+       (addJar): Copy a database before modifying it.
+       (resizeMap): New method.
+
 2005-02-15  David Daney <ddaney@avtrex.com>
            Bryce McKinlay  <mckinlay@redhat.com>
            
index 230d785..a20f5b8 100644 (file)
@@ -39,10 +39,6 @@ USAGE:
 BUGS/FEATURES:
         remove() isn't written yet.
 
-       we can't change the capacity of a PersistentByteMap.
-
-        0x12345678 is a bad choice for the magic number.
-
         capacity is fixed once the map has been created.
 
         We use linear probing to resolve collisions.  It might be
@@ -51,11 +47,7 @@ BUGS/FEATURES:
         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 use unique strings.  This wastes space.
-
-        capacity should probably be prime, but we don't check that.
-
-       we don't do any locking at all: adding to a PersistentByteMap
+       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().
 */
@@ -67,6 +59,7 @@ import java.nio.*;
 import java.nio.channels.*;
 import java.util.*;
 import java.security.MessageDigest;
+import java.math.BigInteger;
 
 public class PersistentByteMap
 {
@@ -94,12 +87,18 @@ public class PersistentByteMap
 
   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;
@@ -108,10 +107,12 @@ public class PersistentByteMap
     {
       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)
     {
@@ -119,8 +120,9 @@ public class PersistentByteMap
     }
   }
 
-  private PersistentByteMap()
+  private PersistentByteMap(File name)
   {
+    this.name = name;
   }
 
   public PersistentByteMap(String filename, AccessMode mode)
@@ -132,7 +134,7 @@ public class PersistentByteMap
   public PersistentByteMap(File f, AccessMode mode)
     throws IOException 
   {
-    FileChannel fc;
+    name = f;
 
     if (mode == AccessMode.READ_ONLY)
       {
@@ -149,7 +151,7 @@ public class PersistentByteMap
     buf = fc.map(mode.mapMode, 0, length);
 
     int magic = getWord (MAGIC);
-    if (magic != 0x12345678)
+    if (magic != 0x67636a64) /* "gcjd" */
       throw new IllegalArgumentException(f.getName());
 
     table_base = getWord (TABLE_BASE);
@@ -167,8 +169,27 @@ public class PersistentByteMap
   {
     f.createNewFile();
     RandomAccessFile raf = new RandomAccessFile(f, "rw");
-        
-    this.capacity = capacity;
+
+    {        
+      // 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 because the hash table is
+      // intolerably slow when more than 2/3 full.
+      
+      BigInteger size = new BigInteger(Integer.toString(capacity * 3/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;
@@ -183,13 +204,13 @@ public class PersistentByteMap
     for (long i = 0; i < totalFileSize; i+= 4096)
       raf.write(_4k);
         
-    FileChannel fc = raf.getChannel();
+    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(0x12345678, MAGIC);
+    putWord(0x67636a64, MAGIC);
     putWord(0x01, VERSION);
     putWord(capacity, CAPACITY);
     putWord(table_base, TABLE_BASE);
@@ -197,15 +218,17 @@ public class PersistentByteMap
     putWord(file_size, FILE_SIZE);
     putWord(elements, ELEMENTS);
     buf.force();
+
+    length = fc.size();
+    string_size = 0;
   }     
 
-  static public PersistentByteMap emptyPersistentByteMap(String filename, 
-                                                         int capacity, int strtabSize)
+  static public PersistentByteMap 
+  emptyPersistentByteMap(File name, int capacity, int strtabSize)
     throws IOException 
   {
-    File f = new File(filename);
-    PersistentByteMap m = new PersistentByteMap();
-    m.init(m, f, capacity, strtabSize);
+    PersistentByteMap m = new PersistentByteMap(name);
+    m.init(m, name, capacity, strtabSize);
     return m;
   }     
 
@@ -313,9 +336,7 @@ public class PersistentByteMap
   {
     int hashIndex = hash(digest);
 
-    // 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.
-    if (elements >= capacity * 2/3)
+    if (elements >= capacity())
       throw new IllegalAccessException("Table Full: " + elements);
 
     do
@@ -336,7 +357,7 @@ public class PersistentByteMap
             int newValue = addBytes((byte[])value);
             putValuePos(newValue, hashIndex);
             return;
-          }         
+          }
                 
         hashIndex++;
         hashIndex %= capacity;
@@ -347,6 +368,33 @@ public class PersistentByteMap
   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");
 
@@ -363,6 +411,9 @@ public class PersistentByteMap
     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;
   }
@@ -377,11 +428,68 @@ public class PersistentByteMap
     return elements;
   }
 
+  public int stringTableSize()
+  {
+    return string_size;
+  }
+
   public int capacity()
   {
-    return 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()
+  {
+    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. */
@@ -481,4 +589,31 @@ public class PersistentByteMap
       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);
+    }
+  }
 }
index b9bea0e..256b619 100644 (file)
@@ -1,4 +1,4 @@
-/* Copyright (C) 2004  Free Software Foundation
+/* Copyright (C) 2004, 2005  Free Software Foundation
 
    This file is part of libgcj.
 
@@ -11,13 +11,15 @@ package gnu.gcj.tools.gcj_dbtool;
 
 import gnu.gcj.runtime.PersistentByteMap;
 import java.io.*;
+import java.nio.channels.*;
 import java.util.*;
 import java.util.jar.*;
 import java.security.MessageDigest;
-import java.math.BigInteger;
 
 public class Main
 {
+  static private boolean verbose = false;
+
   public static void main (String[] s)
   {
     insist (s.length >= 1);
@@ -29,7 +31,7 @@ public class Main
                           + ") "
                           + System.getProperty("java.vm.version"));
        System.out.println();
-       System.out.println("Copyright 2004 Free Software Foundation, Inc.");
+       System.out.println("Copyright 2004, 2005 Free Software Foundation, Inc.");
        System.out.println("This is free software; see the source for copying conditions.  There is NO");
        System.out.println("warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.");
        return;
@@ -42,26 +44,14 @@ public class Main
 
     if (s[0].equals("-n"))
       {
+       // Create a new database.
        insist (s.length >= 2 && s.length <= 3);
 
        int capacity = 32749;
 
        if (s.length == 3)
-         {
-           // 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.
-
-           BigInteger size = new BigInteger(s[2], 10);
-           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);
-
-           capacity = size.intValue();
+         {         
+           capacity = Integer.parseInt(s[2]);
 
            if (capacity <= 2)
              {
@@ -73,7 +63,8 @@ public class Main
        try
          {
            PersistentByteMap b 
-             = PersistentByteMap.emptyPersistentByteMap (s[1], capacity, capacity*64);
+             = PersistentByteMap.emptyPersistentByteMap(new File(s[1]), 
+                                                        capacity, capacity*32);
          }
        catch (Exception e)
          {
@@ -86,18 +77,26 @@ public class Main
 
     if (s[0].equals("-a"))
       {
+       // Add a jar file to a database, creating it if necessary.
+       // Copies the database, adds the jar file to the copy, and
+       // then renames the new database over the old.
        try
          {
            insist (s.length == 4);
-           File jar = new File(s[2]);
-           PersistentByteMap b 
-             = new PersistentByteMap(new File(s[1]), 
-                                     PersistentByteMap.AccessMode.READ_WRITE);
+           File database = new File(s[1]);
+           database = database.getAbsoluteFile();
+           File jar = new File(s[2]);  
+           PersistentByteMap map; 
+           if (database.isFile())
+             map = new PersistentByteMap(database, 
+                                         PersistentByteMap.AccessMode.READ_ONLY);
+           else
+             map = PersistentByteMap.emptyPersistentByteMap(database, 
+                                                            100, 100*32);
            File soFile = new File(s[3]);
            if (! soFile.isFile())
              throw new IllegalArgumentException(s[3] + " is not a file");
-           
-           addJar(jar, b, soFile);
+           map = addJar(jar, map, soFile);
          }
        catch (Exception e)
          {
@@ -110,6 +109,7 @@ public class Main
 
     if (s[0].equals("-t"))
       {
+       // Test
        try
          {
            insist (s.length == 2);
@@ -142,8 +142,60 @@ public class Main
        return;
       }
         
+    if (s[0].equals("-m"))
+      {
+       // Merge databases.
+       insist (s.length >= 3);
+       try
+         {
+           File database = new File(s[1]);
+           database = database.getAbsoluteFile();
+           File temp = File.createTempFile(database.getName(), "", 
+                                           database.getParentFile());
+               
+           int newSize = 0;
+           int newStringTableSize = 0;
+           PersistentByteMap[] sourceMaps = new PersistentByteMap[s.length - 2];
+           // Scan all the input files, calculating worst case string
+           // table and hash table use.
+           for (int i = 2; i < s.length; i++)
+             {
+               PersistentByteMap b 
+                 = new PersistentByteMap(new File(s[i]),
+                                         PersistentByteMap.AccessMode.READ_ONLY);
+               newSize += b.size();
+               newStringTableSize += b.stringTableSize();
+               sourceMaps[i - 2] = b;
+             }
+           
+           newSize *= 1.5; // Scaling the new size by 1.5 results in
+                           // fewer collisions.
+           PersistentByteMap map 
+             = PersistentByteMap.emptyPersistentByteMap
+               (temp, newSize, newStringTableSize);
+
+           for (int i = 0; i < sourceMaps.length; i++)
+             {
+               if (verbose)
+                 System.err.println("adding " + sourceMaps[i].size() 
+                                    + " elements from "
+                                    + sourceMaps[i].getFile());
+               map.putAll(sourceMaps[i]);
+             }
+           map.close();
+           temp.renameTo(database);
+         }
+       catch (Exception e)
+         {
+           e.printStackTrace();
+           System.exit(3);
+         }
+       return;
+      }
+
     if (s[0].equals("-l"))
       {
+       // List a database.
        insist (s.length == 2);
        try
          {
@@ -180,6 +232,7 @@ public class Main
 
     if (s[0].equals("-d"))
       {
+       // For testing only: fill the byte map with random data.
        insist (s.length == 2);
        try
          {    
@@ -225,20 +278,49 @@ public class Main
        + "  Usage: \n"
        + "    gcj-dbtool -n file.gcjdb [size]     - Create a new gcj map database\n"
        + "    gcj-dbtool -a file.gcjdb file.jar file.so\n"
-       + "            - Add the contents of file.jar to the database\n"
+       + "            - Add the contents of file.jar to a new gcj map database\n"
        + "    gcj-dbtool -t file.gcjdb            - Test a gcj map database\n"
-       + "    gcj-dbtool -l file.gcjdb            - List a gcj map database\n");
+       + "    gcj-dbtool -l file.gcjdb            - List a gcj map database\n"
+       + "    gcj-dbtool -m dest.gcjdb [source.gcjdb]...\n"
+       + "             - Merge gcj map databases into dest\n"
+       + "               Replaces dest\n"
+       + "               To add to dest, include dest in the list of sources");
   }
-      
 
-  private static void addJar(File f, PersistentByteMap b, File soFile)
-   throws Exception
+  // Add a jar to a map.  This copies the map first and returns a
+  // different map that contains the data.  The original map is
+  // closed.
+
+  private static PersistentByteMap 
+  addJar(File f, PersistentByteMap b, File soFile)
+    throws Exception
   {
     MessageDigest md = MessageDigest.getInstance("MD5");
 
     JarFile jar = new JarFile (f);
+
+    int count = 0;
+    {
+      Enumeration entries = jar.entries();      
+      while (entries.hasMoreElements())
+       {
+         JarEntry classfile = (JarEntry)entries.nextElement();
+         if (classfile.getName().endsWith(".class"))
+           count++;
+       }
+    }
+
+    if (verbose)
+      System.err.println("adding " + count + " elements from "
+                        + f + " to " + b.getFile());
+    
+    // Maybe resize the destination map.  We're allowing plenty of
+    // extra space by using a loadFactor of 2.  
+    b = resizeMap(b, (b.size() + count) * 2, true);
+
     Enumeration entries = jar.entries();
 
+    byte[] soFileName = soFile.getCanonicalPath().getBytes("UTF-8");
     while (entries.hasMoreElements())
       {
        JarEntry classfile = (JarEntry)entries.nextElement();
@@ -259,12 +341,41 @@ public class Main
                                         + classfile.getName());
                pos += len;
              }
-           b.put(md.digest(data), 
-                 soFile.getCanonicalPath().getBytes());
+           b.put(md.digest(data), soFileName);
          }
-      }              
+      }
+    return b;
   }    
 
+  // Resize a map by creating a new one with the same data and
+  // renaming it.  If close is true, close the original map.
+
+  static PersistentByteMap resizeMap(PersistentByteMap m, int newCapacity, boolean close)
+    throws IOException, IllegalAccessException
+  {
+    newCapacity = Math.max(m.capacity(), newCapacity);
+    File name = m.getFile();
+    File copy = File.createTempFile(name.getName(), "", name.getParentFile());
+    try
+      {
+       PersistentByteMap dest 
+         = PersistentByteMap.emptyPersistentByteMap
+         (copy, newCapacity, newCapacity*32);
+       dest.putAll(m);
+       dest.force();
+       if (close)
+         m.close();
+       copy.renameTo(name);
+       return dest;
+      }
+    catch (Exception e)
+      {
+       copy.delete();
+      }
+    return null;
+  }
+    
+        
   static String bytesToString(byte[] b)
   {
     StringBuffer hexBytes = new StringBuffer();