[kaffe] CVS kaffe (robilad): Resynced with GNU Classpath: linkedHashMap fix
Kaffe CVS
cvs-commits at kaffe.org
Fri Jun 10 12:42:04 PDT 2005
PatchSet 6612
Date: 2005/06/10 19:36:20
Author: robilad
Branch: HEAD
Tag: (none)
Log:
Resynced with GNU Classpath: linkedHashMap fix
Members:
ChangeLog:1.4138->1.4139
libraries/javalib/java/util/LinkedHashMap.java:INITIAL->1.3
Index: kaffe/ChangeLog
diff -u kaffe/ChangeLog:1.4138 kaffe/ChangeLog:1.4139
--- kaffe/ChangeLog:1.4138 Thu Jun 9 10:52:23 2005
+++ kaffe/ChangeLog Fri Jun 10 19:36:20 2005
@@ -1,3 +1,11 @@
+2005-06-10 Dalibor Topic <robilad at kaffe.org>
+
+ Resynced with GNU Classpath.
+
+ 2005-05-29 Michael Koch <konqueror at gmx.de>
+
+ * java/util/LinkedHashMap.java (access): Set 'root.pred'.
+
2005-06-09 Helmer Kraemer <hkraemer at freenet.de>
* kaffe/kaffevm/classMethod.c (expandMethods): create new parsed_signature_t for
===================================================================
Checking out kaffe/libraries/javalib/java/util/LinkedHashMap.java
RCS: /home/cvs/kaffe/kaffe/libraries/javalib/java/util/LinkedHashMap.java,v
VERS: 1.3
***************
--- /dev/null Sun Aug 4 19:57:58 2002
+++ kaffe/libraries/javalib/java/util/LinkedHashMap.java Fri Jun 10 19:42:03 2005
@@ -0,0 +1,501 @@
+/* LinkedHashMap.java -- a class providing hashtable data structure,
+ mapping Object --> Object, with linked list traversal
+ Copyright (C) 2001, 2002, 2005 Free Software Foundation, Inc.
+
+This file is part of GNU Classpath.
+
+GNU Classpath is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+GNU Classpath is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING. If not, write to the
+Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+02111-1307 USA.
+
+Linking this library statically or dynamically with other modules is
+making a combined work based on this library. Thus, the terms and
+conditions of the GNU General Public License cover the whole
+combination.
+
+As a special exception, the copyright holders of this library give you
+permission to link this library with independent modules to produce an
+executable, regardless of the license terms of these independent
+modules, and to copy and distribute the resulting executable under
+terms of your choice, provided that you also meet, for each linked
+independent module, the terms and conditions of the license of that
+module. An independent module is a module which is not derived from
+or based on this library. If you modify this library, you may extend
+this exception to your version of the library, but you are not
+obligated to do so. If you do not wish to do so, delete this
+exception statement from your version. */
+
+
+package java.util;
+
+/**
+ * This class provides a hashtable-backed implementation of the
+ * Map interface, with predictable traversal order.
+ * <p>
+ *
+ * It uses a hash-bucket approach; that is, hash collisions are handled
+ * by linking the new node off of the pre-existing node (or list of
+ * nodes). In this manner, techniques such as linear probing (which
+ * can cause primary clustering) and rehashing (which does not fit very
+ * well with Java's method of precomputing hash codes) are avoided. In
+ * addition, this maintains a doubly-linked list which tracks either
+ * insertion or access order.
+ * <p>
+ *
+ * In insertion order, calling <code>put</code> adds the key to the end of
+ * traversal, unless the key was already in the map; changing traversal order
+ * requires removing and reinserting a key. On the other hand, in access
+ * order, all calls to <code>put</code> and <code>get</code> cause the
+ * accessed key to move to the end of the traversal list. Note that any
+ * accesses to the map's contents via its collection views and iterators do
+ * not affect the map's traversal order, since the collection views do not
+ * call <code>put</code> or <code>get</code>.
+ * <p>
+ *
+ * One of the nice features of tracking insertion order is that you can
+ * copy a hashtable, and regardless of the implementation of the original,
+ * produce the same results when iterating over the copy. This is possible
+ * without needing the overhead of <code>TreeMap</code>.
+ * <p>
+ *
+ * When using this {@link #LinkedHashMap(int, float, boolean) constructor},
+ * you can build an access-order mapping. This can be used to implement LRU
+ * caches, for example. By overriding {@link #removeEldestEntry(Map.Entry)},
+ * you can also control the removal of the oldest entry, and thereby do
+ * things like keep the map at a fixed size.
+ * <p>
+ *
+ * Under ideal circumstances (no collisions), LinkedHashMap offers O(1)
+ * performance on most operations (<code>containsValue()</code> is,
+ * of course, O(n)). In the worst case (all keys map to the same
+ * hash code -- very unlikely), most operations are O(n). Traversal is
+ * faster than in HashMap (proportional to the map size, and not the space
+ * allocated for the map), but other operations may be slower because of the
+ * overhead of the maintaining the traversal order list.
+ * <p>
+ *
+ * LinkedHashMap accepts the null key and null values. It is not
+ * synchronized, so if you need multi-threaded access, consider using:<br>
+ * <code>Map m = Collections.synchronizedMap(new LinkedHashMap(...));</code>
+ * <p>
+ *
+ * The iterators are <i>fail-fast</i>, meaning that any structural
+ * modification, except for <code>remove()</code> called on the iterator
+ * itself, cause the iterator to throw a
+ * {@link ConcurrentModificationException} rather than exhibit
+ * non-deterministic behavior.
+ *
+ * @author Eric Blake (ebb9 at email.byu.edu)
+ * @see Object#hashCode()
+ * @see Collection
+ * @see Map
+ * @see HashMap
+ * @see TreeMap
+ * @see Hashtable
+ * @since 1.4
+ * @status updated to 1.4
+ */
+public class LinkedHashMap extends HashMap
+{
+ /**
+ * Compatible with JDK 1.4.
+ */
+ private static final long serialVersionUID = 3801124242820219131L;
+
+ /**
+ * The oldest Entry to begin iteration at.
+ */
+ transient LinkedHashEntry root;
+
+ /**
+ * The iteration order of this linked hash map: <code>true</code> for
+ * access-order, <code>false</code> for insertion-order.
+ *
+ * @serial true for access order traversal
+ */
+ final boolean accessOrder;
+
+ /**
+ * Class to represent an entry in the hash table. Holds a single key-value
+ * pair and the doubly-linked insertion order list.
+ */
+ class LinkedHashEntry extends HashEntry
+ {
+ /**
+ * The predecessor in the iteration list. If this entry is the root
+ * (eldest), pred points to the newest entry.
+ */
+ LinkedHashEntry pred;
+
+ /** The successor in the iteration list, null if this is the newest. */
+ LinkedHashEntry succ;
+
+ /**
+ * Simple constructor.
+ *
+ * @param key the key
+ * @param value the value
+ */
+ LinkedHashEntry(Object key, Object value)
+ {
+ super(key, value);
+ if (root == null)
+ {
+ root = this;
+ pred = this;
+ }
+ else
+ {
+ pred = root.pred;
+ pred.succ = this;
+ root.pred = this;
+ }
+ }
+
+ /**
+ * Called when this entry is accessed via put or get. This version does
+ * the necessary bookkeeping to keep the doubly-linked list in order,
+ * after moving this element to the newest position in access order.
+ */
+ void access()
+ {
+ if (accessOrder && succ != null)
+ {
+ modCount++;
+ if (this == root)
+ {
+ root = succ;
+ pred.succ = this;
+ succ = null;
+ }
+ else
+ {
+ pred.succ = succ;
+ succ.pred = pred;
+ succ = null;
+ pred = root.pred;
+ pred.succ = this;
+ root.pred = this;
+ }
+ }
+ }
+
+ /**
+ * Called when this entry is removed from the map. This version does
+ * the necessary bookkeeping to keep the doubly-linked list in order.
+ *
+ * @return the value of this key as it is removed
+ */
+ Object cleanup()
+ {
+ if (this == root)
+ {
+ root = succ;
+ if (succ != null)
+ succ.pred = pred;
+ }
+ else if (succ == null)
+ {
+ pred.succ = null;
+ root.pred = pred;
+ }
+ else
+ {
+ pred.succ = succ;
+ succ.pred = pred;
+ }
+ return value;
+ }
+ } // class LinkedHashEntry
+
+ /**
+ * Construct a new insertion-ordered LinkedHashMap with the default
+ * capacity (11) and the default load factor (0.75).
+ */
+ public LinkedHashMap()
+ {
+ super();
+ accessOrder = false;
+ }
+
+ /**
+ * Construct a new insertion-ordered LinkedHashMap from the given Map,
+ * with initial capacity the greater of the size of <code>m</code> or
+ * the default of 11.
+ * <p>
+ *
+ * Every element in Map m will be put into this new HashMap, in the
+ * order of m's iterator.
+ *
+ * @param m a Map whose key / value pairs will be put into
+ * the new HashMap. <b>NOTE: key / value pairs
+ * are not cloned in this constructor.</b>
+ * @throws NullPointerException if m is null
+ */
+ public LinkedHashMap(Map m)
+ {
+ super(m);
+ accessOrder = false;
+ }
+
+ /**
+ * Construct a new insertion-ordered LinkedHashMap with a specific
+ * inital capacity and default load factor of 0.75.
+ *
+ * @param initialCapacity the initial capacity of this HashMap (>= 0)
+ * @throws IllegalArgumentException if (initialCapacity < 0)
+ */
+ public LinkedHashMap(int initialCapacity)
+ {
+ super(initialCapacity);
+ accessOrder = false;
+ }
+
+ /**
+ * Construct a new insertion-orderd LinkedHashMap with a specific
+ * inital capacity and load factor.
+ *
+ * @param initialCapacity the initial capacity (>= 0)
+ * @param loadFactor the load factor (> 0, not NaN)
+ * @throws IllegalArgumentException if (initialCapacity < 0) ||
+ * ! (loadFactor > 0.0)
+ */
+ public LinkedHashMap(int initialCapacity, float loadFactor)
+ {
+ super(initialCapacity, loadFactor);
+ accessOrder = false;
+ }
+
+ /**
+ * Construct a new LinkedHashMap with a specific inital capacity, load
+ * factor, and ordering mode.
+ *
+ * @param initialCapacity the initial capacity (>=0)
+ * @param loadFactor the load factor (>0, not NaN)
+ * @param accessOrder true for access-order, false for insertion-order
+ * @throws IllegalArgumentException if (initialCapacity < 0) ||
+ * ! (loadFactor > 0.0)
+ */
+ public LinkedHashMap(int initialCapacity, float loadFactor,
+ boolean accessOrder)
+ {
+ super(initialCapacity, loadFactor);
+ this.accessOrder = accessOrder;
+ }
+
+ /**
+ * Clears the Map so it has no keys. This is O(1).
+ */
+ public void clear()
+ {
+ super.clear();
+ root = null;
+ }
+
+ /**
+ * Returns <code>true</code> if this HashMap contains a value
+ * <code>o</code>, such that <code>o.equals(value)</code>.
+ *
+ * @param value the value to search for in this HashMap
+ * @return <code>true</code> if at least one key maps to the value
+ */
+ public boolean containsValue(Object value)
+ {
+ LinkedHashEntry e = root;
+ while (e != null)
+ {
+ if (equals(value, e.value))
+ return true;
+ e = e.succ;
+ }
+ return false;
+ }
+
+ /**
+ * Return the value in this Map associated with the supplied key,
+ * or <code>null</code> if the key maps to nothing. If this is an
+ * access-ordered Map and the key is found, this performs structural
+ * modification, moving the key to the newest end of the list. NOTE:
+ * Since the value could also be null, you must use containsKey to
+ * see if this key actually maps to something.
+ *
+ * @param key the key for which to fetch an associated value
+ * @return what the key maps to, if present
+ * @see #put(Object, Object)
+ * @see #containsKey(Object)
+ */
+ public Object get(Object key)
+ {
+ int idx = hash(key);
+ HashEntry e = buckets[idx];
+ while (e != null)
+ {
+ if (equals(key, e.key))
+ {
+ e.access();
+ return e.value;
+ }
+ e = e.next;
+ }
+ return null;
+ }
+
+ /**
+ * Returns <code>true</code> if this map should remove the eldest entry.
+ * This method is invoked by all calls to <code>put</code> and
+ * <code>putAll</code> which place a new entry in the map, providing
+ * the implementer an opportunity to remove the eldest entry any time
+ * a new one is added. This can be used to save memory usage of the
+ * hashtable, as well as emulating a cache, by deleting stale entries.
+ * <p>
+ *
+ * For example, to keep the Map limited to 100 entries, override as follows:
+ * <pre>
+ * private static final int MAX_ENTRIES = 100;
+ * protected boolean removeEldestEntry(Map.Entry eldest)
+ * {
+ * return size() > MAX_ENTRIES;
+ * }
+ * </pre><p>
+ *
+ * Typically, this method does not modify the map, but just uses the
+ * return value as an indication to <code>put</code> whether to proceed.
+ * However, if you override it to modify the map, you must return false
+ * (indicating that <code>put</code> should leave the modified map alone),
+ * or you face unspecified behavior. Remember that in access-order mode,
+ * even calling <code>get</code> is a structural modification, but using
+ * the collections views (such as <code>keySet</code>) is not.
+ * <p>
+ *
+ * This method is called after the eldest entry has been inserted, so
+ * if <code>put</code> was called on a previously empty map, the eldest
+ * entry is the one you just put in! The default implementation just
+ * returns <code>false</code>, so that this map always behaves like
+ * a normal one with unbounded growth.
+ *
+ * @param eldest the eldest element which would be removed if this
+ * returns true. For an access-order map, this is the least
+ * recently accessed; for an insertion-order map, this is the
+ * earliest element inserted.
+ * @return true if <code>eldest</code> should be removed
+ */
+ protected boolean removeEldestEntry(Map.Entry eldest)
+ {
+ return false;
+ }
+
+ /**
+ * Helper method called by <code>put</code>, which creates and adds a
+ * new Entry, followed by performing bookkeeping (like removeEldestEntry).
+ *
+ * @param key the key of the new Entry
+ * @param value the value
+ * @param idx the index in buckets where the new Entry belongs
+ * @param callRemove whether to call the removeEldestEntry method
+ * @see #put(Object, Object)
+ * @see #removeEldestEntry(Map.Entry)
+ * @see LinkedHashEntry#LinkedHashEntry(Object, Object)
+ */
+ void addEntry(Object key, Object value, int idx, boolean callRemove)
+ {
+ LinkedHashEntry e = new LinkedHashEntry(key, value);
+ e.next = buckets[idx];
+ buckets[idx] = e;
+ if (callRemove && removeEldestEntry(root))
+ remove(root.key);
+ }
+
+ /**
+ * Helper method, called by clone() to reset the doubly-linked list.
+ *
+ * @param m the map to add entries from
+ * @see #clone()
+ */
+ void putAllInternal(Map m)
+ {
+ root = null;
+ super.putAllInternal(m);
+ }
+
+ /**
+ * Generates a parameterized iterator. This allows traversal to follow
+ * the doubly-linked list instead of the random bin order of HashMap.
+ *
+ * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
+ * @return the appropriate iterator
+ */
+ Iterator iterator(final int type)
+ {
+ return new Iterator()
+ {
+ /** The current Entry. */
+ LinkedHashEntry current = root;
+
+ /** The previous Entry returned by next(). */
+ LinkedHashEntry last;
+
+ /** The number of known modifications to the backing Map. */
+ int knownMod = modCount;
+
+ /**
+ * 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()
+ {
+ if (knownMod != modCount)
+ throw new ConcurrentModificationException();
+ return current != null;
+ }
+
+ /**
+ * 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()
+ {
+ if (knownMod != modCount)
+ throw new ConcurrentModificationException();
+ if (current == null)
+ throw new NoSuchElementException();
+ last = current;
+ current = current.succ;
+ return type == VALUES ? last.value : type == KEYS ? last.key : last;
+ }
+
+ /**
+ * Removes from the backing HashMap the last element which was fetched
+ * with the <code>next()</code> method.
+ *
+ * @throws ConcurrentModificationException if the HashMap was modified
+ * @throws IllegalStateException if called when there is no last element
+ */
+ public void remove()
+ {
+ if (knownMod != modCount)
+ throw new ConcurrentModificationException();
+ if (last == null)
+ throw new IllegalStateException();
+ LinkedHashMap.this.remove(last.key);
+ last = null;
+ knownMod++;
+ }
+ };
+ }
+} // class LinkedHashMap
More information about the kaffe
mailing list