+2000-12-11 Bryce McKinlay <bryce@albatross.co.nz>
+
+ * Makefile.am: Add HashSet.java and java/lang/ref classes.
+ Remove BasicMapEntry.java and Bucket.java.
+ * Makefile.in: Rebuilt.
+ * java/util/HashMap.java: Rewritten.
+ * java/util/HashSet.java: Imported from classpath.
+ * java/util/WeakHashMap.java: Imported from classpath.
+ * java/util/Hashtable.java: Rewritten based on new HashMap code.
+ * java/util/Bucket.java: Deleted.
+ * java/util/BasicMapEntry.java: Deleted.
+ * java/util/Collections.java (search): Use a for-loop, not iterator
+ hasNext().
+ (copy): Use a for-loop. Throw an IndexOutOfBoundsException if run out
+ of elements in source.
+ (max): Use a for-loop.
+ (min): Ditto.
+ (reverse): Keep track of positions instead of using Iterator's
+ nextIndex() and previousIndex().
+ (shuffle(List)): Initialize defaultRandom if required using
+ double-check thread safety idiom. Call two-argument shuffle method
+ using defaultRandom.
+ (defaultRandom): New field.
+ (shuffle(List, Random)): Use a for-loop. Keep track of pos instead of
+ using previousIndex() and nextIndex().
+ (singletonMap(iterator)): Use a HashMap.Entry, not BasicMapEntry.
+ * java/util/AbstractCollection.java (toString): Use a StringBuffer.
+ * java/util/AbstractMap.java (toString): Use StringBuffer.
+ * java/lang/ref/PhantomReference.java: Imported from classpath.
+ * java/lang/ref/SoftReference.java: Ditto.
+ * java/lang/ref/Reference.java: Ditto.
+ * java/lang/ref/WeakReference.java: Ditto.
+ * java/lang/ref/ReferenceQueue.java: Ditto.
+
2000-12-10 Richard Henderson <rth@redhat.com>
* configure.host: Recognize alpha*-*, not alphaev6-*.
java/lang/VerifyError.java \
java/lang/VirtualMachineError.java \
java/lang/Void.java \
-java/lang/reflect/AccessibleObject.java \
-java/lang/reflect/Array.java \
-java/lang/reflect/Constructor.java \
-java/lang/reflect/Field.java \
-java/lang/reflect/InvocationTargetException.java \
-java/lang/reflect/Member.java \
-java/lang/reflect/Method.java \
-java/lang/reflect/Modifier.java \
-java/lang/reflect/ReflectPermission.java \
java/io/BlockDataException.java \
java/io/BufferedInputStream.java \
java/io/BufferedOutputStream.java \
java/util/AbstractSet.java \
java/util/ArrayList.java \
java/util/Arrays.java \
-java/util/BasicMapEntry.java \
java/util/BitSet.java \
-java/util/Bucket.java \
java/util/Calendar.java \
java/util/Collection.java \
java/util/Collections.java \
java/util/EventObject.java \
java/util/GregorianCalendar.java \
java/util/HashMap.java \
+java/util/HashSet.java \
java/util/Hashtable.java \
java/util/Iterator.java \
java/util/LinkedList.java \
java/util/TimerTask.java \
java/util/TooManyListenersException.java \
java/util/Vector.java
+#java/util/WeakHashmap.java
## List of all .java files to be compiled. Please keep this list
gnu/java/security/provider/Gnu.java \
gnu/java/security/provider/SHA.java \
gnu/java/security/provider/SHA1PRNG.java \
+java/lang/ref/PhantomReference.java \
+java/lang/ref/Reference.java \
+java/lang/ref/ReferenceQueue.java \
+java/lang/ref/SoftReference.java \
+java/lang/ref/WeakReference.java \
+java/lang/reflect/AccessibleObject.java \
+java/lang/reflect/Array.java \
+java/lang/reflect/Constructor.java \
+java/lang/reflect/Field.java \
+java/lang/reflect/InvocationTargetException.java \
+java/lang/reflect/Member.java \
+java/lang/reflect/Method.java \
+java/lang/reflect/Modifier.java \
+java/lang/reflect/ReflectPermission.java \
java/math/BigDecimal.java \
java/math/BigInteger.java \
java/net/BindException.java \
libgcj_basedir = @libgcj_basedir@
AUTOMAKE_OPTIONS = foreign no-installinfo
-@TESTSUBDIR_TRUE@SUBDIRS = \
-@TESTSUBDIR_TRUE@$(DIRLTDL) testsuite gcj include
-@TESTSUBDIR_FALSE@SUBDIRS = \
-@TESTSUBDIR_FALSE@$(DIRLTDL) gcj include
-@USE_LIBDIR_TRUE@toolexeclibdir = \
-@USE_LIBDIR_TRUE@$(libdir)$(MULTISUBDIR)
-@USE_LIBDIR_FALSE@toolexeclibdir = \
-@USE_LIBDIR_FALSE@$(toolexecdir)/lib$(MULTISUBDIR)
-@USE_LIBDIR_FALSE@toolexecdir = \
-@USE_LIBDIR_FALSE@$(exec_prefix)/$(target_alias)
-@NO_X_TRUE@cond_x_ltlibrary = \
-@NO_X_FALSE@cond_x_ltlibrary = \
-@NO_X_FALSE@libgcjx.la
+@TESTSUBDIR_TRUE@SUBDIRS = @TESTSUBDIR_TRUE@$(DIRLTDL) testsuite gcj include
+@TESTSUBDIR_FALSE@SUBDIRS = @TESTSUBDIR_FALSE@$(DIRLTDL) gcj include
+@USE_LIBDIR_TRUE@toolexeclibdir = @USE_LIBDIR_TRUE@$(libdir)$(MULTISUBDIR)
+@USE_LIBDIR_FALSE@toolexeclibdir = @USE_LIBDIR_FALSE@$(toolexecdir)/lib$(MULTISUBDIR)
+@USE_LIBDIR_FALSE@toolexecdir = @USE_LIBDIR_FALSE@$(exec_prefix)/$(target_alias)
+@NO_X_TRUE@cond_x_ltlibrary =
+@NO_X_FALSE@cond_x_ltlibrary = @NO_X_FALSE@libgcjx.la
toolexeclib_LTLIBRARIES = libgcj.la $(cond_x_ltlibrary)
toolexeclib_DATA = libgcj.spec
data_DATA = libgcj.jar
-@NEEDS_DATA_START_TRUE@toolexeclib_LIBRARIES = \
-@NEEDS_DATA_START_TRUE@libgcjdata.a
-@NEEDS_DATA_START_TRUE@libgcjdata_a_SOURCES = \
-@NEEDS_DATA_START_TRUE@libgcjdata.c
+@NEEDS_DATA_START_TRUE@toolexeclib_LIBRARIES = @NEEDS_DATA_START_TRUE@libgcjdata.a
+@NEEDS_DATA_START_TRUE@libgcjdata_a_SOURCES = @NEEDS_DATA_START_TRUE@libgcjdata.c
-@NATIVE_TRUE@bin_PROGRAMS = \
-@NATIVE_TRUE@jv-convert gij
+@NATIVE_TRUE@bin_PROGRAMS = @NATIVE_TRUE@jv-convert gij
bin_SCRIPTS = addr2name.awk
-@CANADIAN_TRUE@@NULL_TARGET_TRUE@ZIP = \
-@CANADIAN_TRUE@@NULL_TARGET_TRUE@$(MULTIBUILDTOP)../$(COMPPATH)/fastjar/fastjar$(EXEEXT)
-@CANADIAN_TRUE@@NULL_TARGET_FALSE@ZIP = \
-@CANADIAN_TRUE@@NULL_TARGET_FALSE@fastjar
-@CANADIAN_FALSE@ZIP = \
-@CANADIAN_FALSE@$(MULTIBUILDTOP)../$(COMPPATH)/fastjar/fastjar$(EXEEXT)
-@CANADIAN_TRUE@GCJH = \
-@CANADIAN_TRUE@gcjh
-@CANADIAN_FALSE@GCJH = \
-@CANADIAN_FALSE@$(MULTIBUILDTOP)../$(COMPPATH)/gcc/gcjh$(EXEEXT)
+@CANADIAN_TRUE@@NULL_TARGET_TRUE@ZIP = @CANADIAN_TRUE@@NULL_TARGET_TRUE@$(MULTIBUILDTOP)../$(COMPPATH)/fastjar/fastjar$(EXEEXT)
+@CANADIAN_TRUE@@NULL_TARGET_FALSE@ZIP = @CANADIAN_TRUE@@NULL_TARGET_FALSE@fastjar
+@CANADIAN_FALSE@ZIP = @CANADIAN_FALSE@$(MULTIBUILDTOP)../$(COMPPATH)/fastjar/fastjar$(EXEEXT)
+@CANADIAN_TRUE@GCJH = @CANADIAN_TRUE@gcjh
+@CANADIAN_FALSE@GCJH = @CANADIAN_FALSE@$(MULTIBUILDTOP)../$(COMPPATH)/gcc/gcjh$(EXEEXT)
GCJCOMPILE = $(LIBTOOL) --tag=GCJ --mode=compile $(GCJ) -fassume-compiled -fclasspath=$(here) -L$(here) $(JC1FLAGS) -MD -MT $@ -MF $(@:.lo=.d) -c
GCJLINK = $(LIBTOOL) --mode=link $(GCJ) -L$(here) $(JC1FLAGS) $(LDFLAGS) -o $@
-fdollars-in-identifiers \
@LIBGCJ_CXXFLAGS@ @EXCEPTIONSPEC@ @X_CFLAGS@ $(WARNINGS) -D_GNU_SOURCE
-@USING_GCC_TRUE@AM_CFLAGS = \
-@USING_GCC_TRUE@@LIBGCJ_CFLAGS@ $(WARNINGS)
-@USING_GCC_FALSE@AM_CFLAGS = \
-@USING_GCC_FALSE@@LIBGCJ_CFLAGS@
+@USING_GCC_TRUE@AM_CFLAGS = @USING_GCC_TRUE@@LIBGCJ_CFLAGS@ $(WARNINGS)
+@USING_GCC_FALSE@AM_CFLAGS = @USING_GCC_FALSE@@LIBGCJ_CFLAGS@
JCFLAGS = -g
JC1FLAGS = -g @LIBGCJ_JAVAFLAGS@
NM = nm
-@NATIVE_TRUE@@MAINTAINER_MODE_TRUE@noinst_PROGRAMS = \
-@NATIVE_TRUE@@MAINTAINER_MODE_TRUE@gen-from-JIS
+@NATIVE_TRUE@@MAINTAINER_MODE_TRUE@noinst_PROGRAMS = @NATIVE_TRUE@@MAINTAINER_MODE_TRUE@gen-from-JIS
CONVERT_DIR = gnu/gcj/convert
java/lang/VerifyError.java \
java/lang/VirtualMachineError.java \
java/lang/Void.java \
-java/lang/reflect/AccessibleObject.java \
-java/lang/reflect/Array.java \
-java/lang/reflect/Constructor.java \
-java/lang/reflect/Field.java \
-java/lang/reflect/InvocationTargetException.java \
-java/lang/reflect/Member.java \
-java/lang/reflect/Method.java \
-java/lang/reflect/Modifier.java \
-java/lang/reflect/ReflectPermission.java \
java/io/BlockDataException.java \
java/io/BufferedInputStream.java \
java/io/BufferedOutputStream.java \
java/util/AbstractSet.java \
java/util/ArrayList.java \
java/util/Arrays.java \
-java/util/BasicMapEntry.java \
java/util/BitSet.java \
-java/util/Bucket.java \
java/util/Calendar.java \
java/util/Collection.java \
java/util/Collections.java \
java/util/EventObject.java \
java/util/GregorianCalendar.java \
java/util/HashMap.java \
+java/util/HashSet.java \
java/util/Hashtable.java \
java/util/Iterator.java \
java/util/LinkedList.java \
java/util/TooManyListenersException.java \
java/util/Vector.java
+#java/util/WeakHashmap.java
ordinary_java_source_files = $(core_java_source_files) \
gnu/gcj/RawData.java \
gnu/java/security/provider/Gnu.java \
gnu/java/security/provider/SHA.java \
gnu/java/security/provider/SHA1PRNG.java \
+java/lang/ref/PhantomReference.java \
+java/lang/ref/Reference.java \
+java/lang/ref/ReferenceQueue.java \
+java/lang/ref/SoftReference.java \
+java/lang/ref/WeakReference.java \
+java/lang/reflect/AccessibleObject.java \
+java/lang/reflect/Array.java \
+java/lang/reflect/Constructor.java \
+java/lang/reflect/Field.java \
+java/lang/reflect/InvocationTargetException.java \
+java/lang/reflect/Member.java \
+java/lang/reflect/Method.java \
+java/lang/reflect/Modifier.java \
+java/lang/reflect/ReflectPermission.java \
java/math/BigDecimal.java \
java/math/BigInteger.java \
java/net/BindException.java \
DISTFILES = $(DIST_COMMON) $(SOURCES) $(HEADERS) $(TEXINFOS) $(EXTRA_DIST)
-TAR = tar
+TAR = gtar
GZIP_ENV = --best
DIST_SUBDIRS = @DIRLTDL@ testsuite gcj include @DIRLTDL@ gcj include
DEP_FILES = .deps/$(srcdir)/$(CONVERT_DIR)/gen-from-JIS.P \
.deps/java/lang/natMath.P .deps/java/lang/natObject.P \
.deps/java/lang/natRuntime.P .deps/java/lang/natString.P \
.deps/java/lang/natSystem.P .deps/java/lang/natThread.P \
-.deps/java/lang/natThrowable.P \
+.deps/java/lang/natThrowable.P .deps/java/lang/ref/PhantomReference.P \
+.deps/java/lang/ref/Reference.P .deps/java/lang/ref/ReferenceQueue.P \
+.deps/java/lang/ref/SoftReference.P .deps/java/lang/ref/WeakReference.P \
.deps/java/lang/reflect/AccessibleObject.P \
.deps/java/lang/reflect/Array.P .deps/java/lang/reflect/Constructor.P \
.deps/java/lang/reflect/Field.P \
.deps/java/util/AbstractCollection.P .deps/java/util/AbstractList.P \
.deps/java/util/AbstractMap.P .deps/java/util/AbstractSequentialList.P \
.deps/java/util/AbstractSet.P .deps/java/util/ArrayList.P \
-.deps/java/util/Arrays.P .deps/java/util/BasicMapEntry.P \
-.deps/java/util/BitSet.P .deps/java/util/Bucket.P \
+.deps/java/util/Arrays.P .deps/java/util/BitSet.P \
.deps/java/util/Calendar.P .deps/java/util/Collection.P \
.deps/java/util/Collections.P .deps/java/util/Comparator.P \
.deps/java/util/ConcurrentModificationException.P \
.deps/java/util/EmptyStackException.P .deps/java/util/Enumeration.P \
.deps/java/util/EventListener.P .deps/java/util/EventObject.P \
.deps/java/util/GregorianCalendar.P .deps/java/util/HashMap.P \
-.deps/java/util/Hashtable.P .deps/java/util/Iterator.P \
-.deps/java/util/LinkedList.P .deps/java/util/List.P \
-.deps/java/util/ListIterator.P .deps/java/util/ListResourceBundle.P \
-.deps/java/util/Locale.P .deps/java/util/Map.P \
-.deps/java/util/MissingResourceException.P \
+.deps/java/util/HashSet.P .deps/java/util/Hashtable.P \
+.deps/java/util/Iterator.P .deps/java/util/LinkedList.P \
+.deps/java/util/List.P .deps/java/util/ListIterator.P \
+.deps/java/util/ListResourceBundle.P .deps/java/util/Locale.P \
+.deps/java/util/Map.P .deps/java/util/MissingResourceException.P \
.deps/java/util/NoSuchElementException.P .deps/java/util/Observable.P \
.deps/java/util/Observer.P .deps/java/util/Properties.P \
.deps/java/util/PropertyPermission.P \
@for file in $(DISTFILES); do \
d=$(srcdir); \
if test -d $$d/$$file; then \
- cp -pr $$/$$file $(distdir)/$$file; \
+ cp -pr $$d/$$file $(distdir)/$$file; \
else \
test -f $(distdir)/$$file \
|| ln $$d/$$file $(distdir)/$$file 2> /dev/null \
--- /dev/null
+/* java.lang.ref.PhantomReference
+ Copyright (C) 1999 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.
+
+As a special exception, if you link this library with other files to
+produce an executable, this library does not by itself cause the
+resulting executable to be covered by the GNU General Public License.
+This exception does not however invalidate any other reasons why the
+executable file might be covered by the GNU General Public License. */
+
+
+package java.lang.ref;
+
+/**
+ * A phantom reference is useful, to get notified, when an object got
+ * finalized. You can't access that object though, since it is
+ * finalized. This is the reason, why <code>get()</code> always
+ * returns null.
+ *
+ * @author Jochen Hoenicke
+ */
+public class PhantomReference
+ extends Reference
+{
+ /**
+ * Creates a new phantom reference.
+ * @param referent the object that should be watched.
+ * @param q the queue that should be notified, if the referent was
+ * finalized. This mustn't be <code>null</code>.
+ * @exception NullPointerException if q is null.
+ */
+ public PhantomReference(Object referent, ReferenceQueue q)
+ {
+ super(referent, q);
+ }
+
+ /**
+ * Returns the object, this reference refers to.
+ * @return <code>null</code>, since the refered object may be
+ * finalized and thus not accessible.
+ */
+ public Object get()
+ {
+ return null;
+ }
+}
--- /dev/null
+/* java.lang.ref.Reference
+ Copyright (C) 1999 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.
+
+As a special exception, if you link this library with other files to
+produce an executable, this library does not by itself cause the
+resulting executable to be covered by the GNU General Public License.
+This exception does not however invalidate any other reasons why the
+executable file might be covered by the GNU General Public License. */
+
+
+package java.lang.ref;
+
+/**
+ * This is the base class of all references. A reference allows
+ * refering to an object without preventing the garbage collection to
+ * collect it. The only way to get the referred object is via the
+ * <code>get()</code>-method. This method will return
+ * <code>null</code> if the object was collected. <br>
+ *
+ * A reference may be registered with a queue. When a referred
+ * element gets collected the reference will be put on the queue, so
+ * that you will be notified. <br>
+ *
+ * There are currently three types of references: soft reference,
+ * weak reference and phantom reference. <br>
+ *
+ * Soft references will be cleared if the garbage collection is told
+ * to free some memory and there are no unreferenced or weakly referenced
+ * objects. It is useful for caches. <br>
+ *
+ * Weak references will be cleared as soon as the garbage collection
+ * determines that the refered object is only weakly reachable. They
+ * are useful as keys in hashtables (see <code>WeakHashtable</code>) as
+ * you get notified when nobody has the key anymore.
+ *
+ * Phantom references don't prevent finalization. If an object is only
+ * phantom reachable, it will be finalized, and the reference will be
+ * enqueued, but not cleared. Since you mustn't access an finalized
+ * object, the <code>get</code> method of a phantom reference will never
+ * work. It is useful to keep track, when an object is finalized.
+ *
+ * @author Jochen Hoenicke
+ * @see java.util.WeakHashtable
+ */
+public abstract class Reference
+{
+ /**
+ * The underlying object. This field is handled in a special way by
+ * the garbage collection.
+ */
+ Object referent;
+
+ /**
+ * The queue this reference is registered on. This is null, if this
+ * wasn't registered to any queue or reference was already enqueued.
+ */
+ ReferenceQueue queue;
+
+ /**
+ * Link to the next entry on the queue. If this is null, this
+ * reference is not enqueued. Otherwise it points to the next
+ * reference. The last reference on a queue will point to itself
+ * (not to null, that value is used to mark a not enqueued
+ * reference).
+ */
+ Reference nextOnQueue;
+
+ /**
+ * This lock should be taken by the garbage collection, before
+ * determining reachability. It will prevent the get()-method to
+ * return the reference so that reachability doesn't change.
+ */
+ static Object lock = new Object();
+
+ /**
+ * Creates a new reference that is not registered to any queue.
+ * Since it is package private, it is not possible to overload this
+ * class in a different package.
+ * @param referent the object we refer to.
+ */
+ Reference(Object ref)
+ {
+ referent = ref;
+ }
+
+ /**
+ * Creates a reference that is registered to a queue. Since this is
+ * package private, it is not possible to overload this class in a
+ * different package.
+ * @param referent the object we refer to.
+ * @param q the reference queue to register on.
+ * @exception NullPointerException if q is null.
+ */
+ Reference(Object ref, ReferenceQueue q)
+ {
+ if (q == null)
+ throw new NullPointerException();
+ referent = ref;
+ queue = q;
+ }
+
+ /**
+ * Returns the object, this reference refers to.
+ * @return the object, this reference refers to, or null if the
+ * reference was cleared.
+ */
+ public Object get()
+ {
+ synchronized(lock)
+ {
+ return referent;
+ }
+ }
+
+ /**
+ * Clears the reference, so that it doesn't refer to its object
+ * anymore. For soft and weak references this is called by the
+ * garbage collection. For phantom references you should call
+ * this when enqueuing the reference.
+ */
+ public void clear()
+ {
+ referent = null;
+ }
+
+ /**
+ * Tells if the object is enqueued on a reference queue.
+ * @return true if it is enqueued, false otherwise.
+ */
+ public boolean isEnqueued()
+ {
+ return nextOnQueue != null;
+ }
+
+ /**
+ * Enqueue an object on a reference queue. This is normally executed
+ * by the garbage collection.
+ */
+ public boolean enqueue()
+ {
+ if (queue != null)
+ {
+ queue.enqueue(this);
+ queue = null;
+ return true;
+ }
+ return false;
+ }
+}
--- /dev/null
+/* java.lang.ref.ReferenceQueue
+ Copyright (C) 1999 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.
+
+As a special exception, if you link this library with other files to
+produce an executable, this library does not by itself cause the
+resulting executable to be covered by the GNU General Public License.
+This exception does not however invalidate any other reasons why the
+executable file might be covered by the GNU General Public License. */
+
+
+package java.lang.ref;
+
+/**
+ * This is the queue, where references can enqueue themselve on. Each
+ * reference may be registered to a queue at initialization time and
+ * will be appended to the queue, when the enqueue method is called.
+ *
+ * The enqueue method may be automatically called by the garbage
+ * collector if it detects, that the object is only reachable through
+ * the Reference objects.
+ *
+ * @author Jochen Hoenicke
+ * @see Reference#enqueue()
+ */
+public class ReferenceQueue
+{
+ /**
+ * This is a linked list of references. If this is null, the list is
+ * empty. Otherwise this points to the first reference on the queue.
+ * The first reference will point to the next reference via the
+ * <code>nextOnQueue</code> field. The last reference will point to
+ * itself (not to null, since <code>nextOnQueue</code> is used to
+ * determine if a reference is enqueued).
+ */
+ private Reference first;
+
+ /**
+ * Creates a new empty reference queue.
+ */
+ public ReferenceQueue()
+ {
+ }
+
+ /**
+ * Checks if there is a reference on the queue, returning it
+ * immediately. The reference will be dequeued.
+ *
+ * @return a reference on the queue, if there is one,
+ * <code>null</code> otherwise.
+ */
+ public synchronized Reference poll()
+ {
+ return dequeue();
+ }
+
+ /**
+ * This is called by reference to enqueue itself on this queue.
+ * @param ref the reference that should be enqueued.
+ */
+ synchronized void enqueue(Reference ref)
+ {
+ /* last reference will point to itself */
+ ref.nextOnQueue = first == null ? ref : first;
+ first = ref;
+ /* this wakes only one remove thread. */
+ notify();
+ }
+
+ /**
+ * Remove a reference from the queue, if there is one.
+ * @return the first element of the queue, or null if there isn't any.
+ */
+ private Reference dequeue()
+ {
+ if (first == null)
+ return null;
+
+ Reference result = first;
+ first = (first == first.nextOnQueue) ? null : first.nextOnQueue;
+ result.nextOnQueue = null;
+ return result;
+ }
+
+ /**
+ * Removes a reference from the queue, blocking for <code>timeout</code>
+ * until a reference is enqueued.
+ * @param timeout the timeout period in milliseconds, <code>0</code> means
+ * wait forever.
+ * @return the reference removed from the queue, or
+ * <code>null</code> if timeout period expired.
+ * @exception InterruptedException if the wait was interrupted.
+ */
+ public synchronized Reference remove(long timeout)
+ throws InterruptedException
+ {
+ if (first == null)
+ {
+ wait(timeout);
+ }
+
+ return dequeue();
+ }
+
+
+ /**
+ * Removes a reference from the queue, blocking until a reference is
+ * enqueued.
+ *
+ * @return the reference removed from the queue.
+ * @exception InterruptedException if the wait was interrupted.
+ */
+ public Reference remove()
+ throws InterruptedException
+ {
+ return remove(0L);
+ }
+}
--- /dev/null
+/* java.lang.ref.SoftReference
+ Copyright (C) 1999 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.
+
+As a special exception, if you link this library with other files to
+produce an executable, this library does not by itself cause the
+resulting executable to be covered by the GNU General Public License.
+This exception does not however invalidate any other reasons why the
+executable file might be covered by the GNU General Public License. */
+
+
+package java.lang.ref;
+
+/**
+ * A soft reference will be cleared, if the object is only softly
+ * reachable and the garbage collection needs more memory. The garbage
+ * collection will use an intelligent strategy to determine which soft
+ * references it should clear. This makes a soft reference ideal for
+ * caches.<br>
+ *
+ * @author Jochen Hoenicke
+ */
+public class SoftReference
+ extends Reference
+{
+ /**
+ * Create a new soft reference, that is not registered to any queue.
+ * @param referent the object we refer to.
+ */
+ public SoftReference(Object referent)
+ {
+ super(referent);
+ }
+
+ /**
+ * Create a new soft reference.
+ * @param referent the object we refer to.
+ * @param q the reference queue to register on.
+ * @exception NullPointerException if q is null.
+ */
+ public SoftReference(Object referent, ReferenceQueue q)
+ {
+ super(referent, q);
+ }
+
+ /**
+ * Returns the object, this reference refers to.
+ * @return the object, this reference refers to, or null if the
+ * reference was cleared.
+ */
+ public Object get()
+ {
+ /* Why is this overloaded???
+ * Maybe for a kind of LRU strategy. */
+ return super.get();
+ }
+}
--- /dev/null
+/* java.lang.ref.WeakReference
+ Copyright (C) 1999 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.
+
+As a special exception, if you link this library with other files to
+produce an executable, this library does not by itself cause the
+resulting executable to be covered by the GNU General Public License.
+This exception does not however invalidate any other reasons why the
+executable file might be covered by the GNU General Public License. */
+
+
+package java.lang.ref;
+
+/**
+ * A weak reference will be cleared, if the object is only weakly
+ * reachable. It is useful for lookup tables, where you aren't
+ * interested in an entry, if the key isn't reachable anymore.
+ * <code>WeakHashtable</code> is a complete implementation of such a
+ * table. <br>
+ *
+ * It is also useful to make objects unique: You create a set of weak
+ * references to those objects, and when you create a new object you
+ * look in this set, if the object already exists and return it. If
+ * an object is not referenced anymore, the reference will
+ * automatically cleared, and you may remove it from the set. <br>
+ *
+ * @author Jochen Hoenicke
+ * @see java.util.WeakHashtable
+ */
+public class WeakReference
+ extends Reference
+{
+ /**
+ * Create a new weak reference, that is not registered to any queue.
+ * @param referent the object we refer to.
+ */
+ public WeakReference(Object referent)
+ {
+ super(referent);
+ }
+
+ /**
+ * Create a new weak reference.
+ * @param referent the object we refer to.
+ * @param q the reference queue to register on.
+ * @exception NullPointerException if q is null.
+ */
+ public WeakReference(Object referent, ReferenceQueue q)
+ {
+ super(referent, q);
+ }
+}
{
Iterator itr = iterator();
int size = size();
- String r = "[";
+ StringBuffer r = new StringBuffer("[");
for (int pos = 0; pos < size; pos++)
{
- r += itr.next();
+ r.append(itr.next());
if (pos < size - 1)
- r += ", ";
+ r.append(", ");
}
- r += "]";
- return r;
+ r.append("]");
+ return r.toString();
}
}
{
Iterator entries = entrySet().iterator();
int size = size();
- String r = "{";
+ StringBuffer r = new StringBuffer("{");
for (int pos = 0; pos < size; pos++)
{
- r += entries.next();
+ // Append the toString value of the entries rather than calling
+ // getKey/getValue. This is more efficient and it matches the JDK
+ // behaviour.
+ r.append(entries.next());
if (pos < size - 1)
- r += ", ";
+ r.append(", ");
}
- r += "}";
- return r;
+ r.append("}");
+ return r.toString();
}
public Collection values()
*/
public abstract class AbstractSet extends AbstractCollection implements Set
{
-
/**
* Tests whether the given object is equal to this Set. This implementation
* first checks whether this set <em>is</em> the given object, and returns
+++ /dev/null
-/* BasicMapEntry.java -- a class providing a plain-vanilla implementation of
- the Map.Entry interface; could be used anywhere in java.util
- Copyright (C) 1998 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.
-
-As a special exception, if you link this library with other files to
-produce an executable, this library does not by itself cause the
-resulting executable to be covered by the GNU General Public License.
-This exception does not however invalidate any other reasons why the
-executable file might be covered by the GNU General Public License. */
-
-
-package java.util;
-
-/**
- * a class which implements Map.Entry
- *
- * @author Jon Zeppieri
- * @version $Revision: 1.3 $
- * @modified $Id: BasicMapEntry.java,v 1.3 2000/03/15 21:59:07 rao Exp $
- */
-class BasicMapEntry implements Map.Entry
-{
- /** the key */
- Object key;
- /** the value */
- Object value;
-
- /**
- * construct a new BasicMapEntry with the given key and value
- *
- * @param newKey the key of this Entry
- * @param newValue the value of this Entry
- */
- BasicMapEntry(Object newKey, Object newValue)
- {
- key = newKey;
- value = newValue;
- }
-
- /**
- * returns true if <pre>o</pre> is a Map.Entry and
- * <pre>
- * (((o.getKey == null) ? (key == null) :
- * o.getKey().equals(key)) &&
- * ((o.getValue() == null) ? (value == null) :
- * o.getValue().equals(value)))
- * </pre>
- *
- * NOTE: the calls to getKey() and getValue() in this implementation
- * are <i>NOT</i> superfluous and should not be removed. They insure
- * that subclasses such as HashMapEntry work correctly
- *
- * @param o the Object being tested for equality
- */
- public boolean equals(Object o)
- {
- Map.Entry tester;
- Object oTestingKey, oTestingValue;
- Object oKey, oValue;
- if (o instanceof Map.Entry)
- {
- tester = (Map.Entry) o;
- oKey = getKey();
- oValue = getValue();
- oTestingKey = tester.getKey();
- oTestingValue = tester.getValue();
- return (((oTestingKey == null) ? (oKey == null) :
- oTestingKey.equals(oKey)) &&
- ((oTestingValue == null) ? (oValue == null) :
- oTestingValue.equals(oValue)));
- }
- return false;
- }
-
- /** returns the key */
- public Object getKey()
- {
- return key;
- }
-
- /** returns the value */
- public Object getValue()
- {
- return value;
- }
-
- /** the hashCode() for a Map.Entry is
- * <pre>
- * ((getKey() == null) ? 0 : getKey().hashCode()) ^
- * ((getValue() == null) ? 0 : getValue().hashCode());
- * </pre>
- *
- * NOTE: the calls to getKey() and getValue() in this implementation
- * are <i>NOT</i> superfluous and should not be removed. They insure
- * that subclasses such as HashMapEntry work correctly
- */
- public int hashCode()
- {
- Object oKey = getKey();
- Object oValue = getValue();
- return ((oKey == null) ? 0 : oKey.hashCode()) ^
- ((oValue == null) ? 0 : oValue.hashCode());
- }
-
- /**
- * sets the value of this Map.Entry
- *
- * @param newValue the new value of this Map.Entry
- */
- public Object setValue(Object newValue)
- throws java.lang.UnsupportedOperationException, ClassCastException,
- IllegalArgumentException, NullPointerException
- {
- Object oVal = value;
- value = newValue;
- return oVal;
- }
-}
+++ /dev/null
-/* Bucket.java -- a class providing a hash-bucket data structure
- (a lightweight linked list)
- Copyright (C) 1998, 2000 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.
-
-As a special exception, if you link this library with other files to
-produce an executable, this library does not by itself cause the
-resulting executable to be covered by the GNU General Public License.
-This exception does not however invalidate any other reasons why the
-executable file might be covered by the GNU General Public License. */
-
-
-package java.util;
-
-/**
- * a class representing a simple, lightweight linked-list, using Node
- * objects as its linked nodes; this is used by Hashtable and HashMap
- *
- * @author Jon Zeppieri
- * @version $Revision: 1.3 $
- * @modified $Id: Bucket.java,v 1.3 2000/03/15 21:59:08 rao Exp $
- */
-class Bucket
-{
- /** the first node of the lined list, originally null */
- Node first;
-
- /** trivial constructor for a Bucket */
- Bucket()
- {
- }
-
- /** add this key / value pair to the list
- *
- * @param newNode a Node object to be added to this list
- * @return the old value mapped to the key if there was one,
- * otherwise null.
- */
- Object add(Node newNode)
- {
- Object oKey;
- Object oTestKey = newNode.getKey();
- Node it = first;
- Node prev = null;
- if (it == null) // if the list is empty (the ideal case), we make a new single-node list
- {
- first = newNode;
- return null;
- }
- else // otherwise try to find where this key already exists in the list,
- {// and if it does, replace the value with the new one (and return the old one)
- while (it != null)
- {
- oKey = it.getKey();
- if ((oKey == null) ? (oTestKey == null) :
- oKey.equals(oTestKey))
- {
- Object oldValue = it.value;
- it.value = newNode.getValue();
- return oldValue;
- }
- prev = it;
- it = it.next;
- }
- prev.next = newNode; // otherwise, just stick this at the
- return null; // end of the list
- }
- }
-
- /**
- * remove a Map.Entry in this list with the supplied key and return its value,
- * if it exists, else return null
- *
- * @param key the key we are looking for in this list
- */
- Object removeByKey(Object key)
- {
- Object oEntryKey;
- Node prev = null;
- Node it = first;
- while (it != null)
- {
- oEntryKey = it.getKey();
- if ((oEntryKey == null) ? (key == null) : oEntryKey.equals(key))
- {
- if (prev == null) // we are removing the first element
- first = it.next;
- else
- prev.next = it.next;
- return it.getValue();
- }
- else
- {
- prev = it;
- it = it.next;
- }
- }
- return null;
- }
-
- /**
- * return the value which the supplied key maps to, if it maps to anything in this list,
- * otherwise, return null
- *
- * @param key the key mapping to a value that we are looking for
- */
- Object getValueByKey(Object key)
- {
- Node entry = getEntryByKey(key);
- return (entry == null) ? null : entry.getValue();
- }
-
- /**
- * return the Map.Entry which the supplied key is a part of, if such a Map.Entry exists,
- * null otherwise
- *
- * this method is important for HashMap, which can hold null values and the null key
- *
- * @param key the key for which we are finding the corresponding Map.Entry
- */
- Node getEntryByKey(Object key)
- {
- Object oEntryKey;
- Node it = first;
- while (it != null)
- {
- oEntryKey = it.getKey();
- if ((oEntryKey == null) ? (key == null) : oEntryKey.equals(key))
- return it;
- it = it.next;
- }
- return null;
- }
-
- /**
- * return true if this list has a Map.Entry whose value equals() the supplied value
- *
- * @param value the value we are looking to match in this list
- */
- boolean containsValue(Object value)
- {
- Object oEntryValue;
- Node it = first;
- while (it != null)
- {
- oEntryValue = it.getValue();
- if ((oEntryValue == null) ? (value == null) : oEntryValue.equals(value))
- return true;
- it = it.next;
- }
- return false;
- }
-
- // INNSER CLASSES ----------------------------------------------------------
-
- /**
- * a class represnting a node in our lightweight linked-list
- * that we use for hash buckets; a Node object contains a Map.Entry as its
- * <pre>value</pre> property and a reference (possibly, even hopefully, null)
- * to another Node as its <pre>next</pre> property.
- *
- * There <i>is</i> a reason for not using a highly generic "LinkedNode" type
- * class: we want to eliminate runtime typechecks.
- *
- * @author Jon Zeppieri
- * @version $Revision: 1.3 $
- * @modified $Id: Bucket.java,v 1.3 2000/03/15 21:59:08 rao Exp $
- */
- static class Node extends BasicMapEntry implements Map.Entry
- {
- /** a reference to the next node in the linked list */
- Node next;
-
- /** non-trivial contructor -- sets the <pre>value</pre> of the Bucket upon instantiation */
- Node(Object key, Object value)
- {
- super(key, value);
- }
-
-
- }
- // EOF ------------------------------------------------------------------------
-}
// is sequential-access.
if (l instanceof AbstractSequentialList)
{
- ListIterator i = l.listIterator();
- while (i.hasNext())
+ ListIterator itr = l.listIterator();
+ for (int i = l.size() - 1; i >= 0; --i)
{
- final int d = compare(key, i.next(), c);
+ final int d = compare(key, itr.next(), c);
if (d == 0)
{
return pos;
{
Iterator i1 = source.iterator();
ListIterator i2 = dest.listIterator();
- while (i1.hasNext())
+
+ try
+ {
+ for (int i = source.size() - 1; i >= 0; --i)
+ {
+ i2.next();
+ i2.set(i1.next());
+ }
+ }
+ catch (NoSuchElementException x)
{
- i2.next();
- i2.set(i1.next());
+ throw new IndexOutOfBoundsException("Source doesn't fit in dest.");
}
}
*/
public static void fill(List l, Object val)
{
- ListIterator i = l.listIterator();
- while (i.hasNext())
+ ListIterator itr = l.listIterator();
+ for (int i = l.size() - 1; i >= 0; --i)
{
- i.next();
- i.set(val);
+ itr.next();
+ itr.set(val);
}
}
*/
public static Object max(Collection c)
{
- Iterator i = c.iterator();
- Comparable max = (Comparable) i.next(); // throws NoSuchElementException
- while (i.hasNext())
+ Iterator itr = c.iterator();
+ Comparable max = (Comparable) itr.next(); // throws NoSuchElementException
+ int csize = c.size();
+ for (int i = 1; i < csize; i++)
{
- Object o = i.next();
+ Object o = itr.next();
if (max.compareTo(o) < 0)
{
max = (Comparable) o;
*/
public static Object max(Collection c, Comparator order)
{
- Iterator i = c.iterator();
- Object max = i.next(); // throws NoSuchElementException
- while (i.hasNext())
+ Iterator itr = c.iterator();
+ Object max = itr.next(); // throws NoSuchElementException
+ int csize = c.size();
+ for (int i = 1; i < csize; i++)
{
- Object o = i.next();
+ Object o = itr.next();
if (order.compare(max, o) < 0)
- {
- max = o;
- }
+ max = o;
}
return max;
}
*/
public static Object min(Collection c)
{
- Iterator i = c.iterator();
- Comparable min = (Comparable) i.next(); // throws NoSuchElementException
- while (i.hasNext())
+ Iterator itr = c.iterator();
+ Comparable min = (Comparable) itr.next(); // throws NoSuchElementException
+ int csize = c.size();
+ for (int i = 1; i < csize; i++)
{
- Object o = i.next();
+ Object o = itr.next();
if (min.compareTo(o) > 0)
- {
- min = (Comparable) o;
- }
+ min = (Comparable) o;
}
return min;
}
*/
public static Object min(Collection c, Comparator order)
{
- Iterator i = c.iterator();
- Object min = i.next(); // throws NoSuchElementExcception
- while (i.hasNext())
+ Iterator itr = c.iterator();
+ Object min = itr.next(); // throws NoSuchElementExcception
+ int csize = c.size();
+ for (int i = 1; i < csize; i++)
{
- Object o = i.next();
+ Object o = itr.next();
if (order.compare(min, o) > 0)
- {
- min = o;
- }
+ min = o;
}
return min;
}
public static void reverse(List l)
{
ListIterator i1 = l.listIterator();
- ListIterator i2 = l.listIterator(l.size());
- while (i1.nextIndex() < i2.previousIndex())
+ int pos1 = 0;
+ int pos2 = l.size();
+ ListIterator i2 = l.listIterator(pos2);
+ while (pos1 < pos2)
{
Object o = i1.next();
i1.set(i2.previous());
i2.set(o);
+ ++pos1;
+ --pos2;
}
}
*/
public static void shuffle(List l)
{
- shuffle(l, new Random());
+ if (defaultRandom == null)
+ {
+ synchronized (Collections.class)
+ {
+ if (defaultRandom == null)
+ defaultRandom = new Random();
+ }
+ }
+ shuffle(l, defaultRandom);
}
+ /** Cache a single Random object for use by shuffle(List). This improves
+ * performance as well as ensuring that sequential calls to shuffle() will
+ * not result in the same shuffle order occuring: the resolution of
+ * System.currentTimeMillis() is not sufficient to guarantee a unique seed.
+ */
+ private static Random defaultRandom = null;
+
/**
* Shuffle a list according to a given source of randomness. The algorithm
* used iterates backwards over the list, swapping each element with an
public static void shuffle(List l, Random r)
{
Object[] a = l.toArray(); // Dump l into an array
- ListIterator i = l.listIterator(l.size());
+ int lsize = l.size();
+ ListIterator i = l.listIterator(lsize);
// Iterate backwards over l
- while (i.hasPrevious())
+ for (int pos = lsize - 1; pos >= 0; --pos)
{
- // Obtain a random position to swap with. nextIndex is used so that the
+ // Obtain a random position to swap with. pos + 1 is used so that the
// range of the random number includes the current position.
- int swap = r.nextInt(i.nextIndex());
+ int swap = r.nextInt(pos + 1);
// Swap the swapth element of the array with the next element of the
// list.
Object o = a[swap];
- a[swap] = a[i.previousIndex()];
- a[i.previousIndex()] = o;
+ a[swap] = a[pos];
+ a[pos] = o;
// Set the element in the original list accordingly.
i.previous();
{
public Set entrySet()
{
- return singleton(new BasicMapEntry(key, value));
+ return singleton(new HashMap.Entry(key, value));
}
};
}
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
import java.io.Serializable;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
-import java.io.ObjectStreamField;
+
+// NOTE: This implementation is very similar to that of Hashtable. If you fix
+// a bug in here, chances are you should make a similar change to the Hashtable
+// code.
/**
* This class provides a hashtable-backed implementation of the
* does not support "Enumeration views."
*
* @author Jon Zeppieri
- * @version $Revision: 1.6 $
- * @modified $Id: HashMap.java,v 1.6 2000/03/15 21:59:13 rao Exp $
+ * @author Jochen Hoenicke
+ * @author Bryce McKinlay
+ * @version $Revision: 1.8 $
+ * @modified $Id: HashMap.java,v 1.8 2000/10/26 10:19:00 bryce Exp $
*/
-public class HashMap extends AbstractMap
- implements Map, Cloneable, Serializable
+public class HashMap extends AbstractMap
+ implements Map, Cloneable, Serializable
{
- // STATIC (CLASS) VARIABLES ------------------------------------------
-
- /**
- * the default capacity for an instance of HashMap -- I think this
- * is low, and perhaps it shoudl be raised; Sun's documentation mildly
- * suggests that this (11) is the correct value, though
- */
- private static final int DEFAULT_CAPACITY = 11;
-
- /** the default load factor of a HashMap */
- private static final float DEFAULT_LOAD_FACTOR = 0.75F;
-
- /** used internally to represent the null key */
- private static final HashMap.Null NULL_KEY = new HashMap.Null();
-
- /** used internally to parameterize the creation of set/collection views */
- private static final int KEYS = 0;
-
- /** used internally to parameterize the creation of set/collection views */
- private static final int VALUES = 1;
-
- /** used internally to parameterize the creation of set/collection views */
- private static final int ENTRIES = 2;
-
- private static final long serialVersionUID = 362498820763181265L;
-
- // INSTANCE VARIABLES -------------------------------------------------
-
- /** the capacity of this HashMap: denotes the size of the bucket array */
- transient int capacity;
-
- /** the size of this HashMap: denotes the number of key-value pairs */
- private transient int size;
-
- /** the load factor of this HashMap: used in computing the threshold
- * @serial
- */
- float loadFactor;
-
- /* the rounded product of the capacity and the load factor; when the number of
- * elements exceeds the threshold, the HashMap calls <pre>rehash()</pre>
- * @serial
- */
- private int threshold;
-
- /**
- * this data structure contains the actual key-value mappings; a
- * <pre>BucketList</pre> is a lightweight linked list of "Buckets",
- * which, in turn, are linked nodes containing a key-value mapping
- * and a reference to the "next" Bucket in the list
- */
- private transient Bucket[] buckets;
-
- /**
- * counts the number of modifications this HashMap has undergone; used by Iterators
- * to know when to throw ConcurrentModificationExceptions (idea ripped-off from
- * Stuart Ballard's AbstractList implementation)
- */
- private transient int modCount;
-
-
- // CONSTRUCTORS ---------------------------------------------------------
+ /** Default number of buckets. This is the value the JDK 1.3 uses. Some
+ * early documentation specified this value as 101. That is incorrect. */
+ private static final int DEFAULT_CAPACITY = 11;
+ /** The defaulty load factor; this is explicitly specified by Sun */
+ private static final float DEFAULT_LOAD_FACTOR = 0.75f;
+
+ private static final long serialVersionUID = 362498820763181265L;
+
+ /**
+ * The rounded product of the capacity and the load factor; when the number
+ * of elements exceeds the threshold, the HashMap calls <pre>rehash()</pre>.
+ * @serial
+ */
+ int threshold;
+
+ /** Load factor of this HashMap: used in computing the threshold.
+ * @serial
+ */
+ float loadFactor = DEFAULT_LOAD_FACTOR;
+
+ /**
+ * Array containing the actual key-value mappings
+ */
+ transient Entry[] buckets;
+
+ /**
+ * counts the number of modifications this HashMap has undergone, used
+ * by Iterators to know when to throw ConcurrentModificationExceptions.
+ */
+ transient int modCount;
+
+ /** the size of this HashMap: denotes the number of key-value pairs */
+ transient int size;
+
+ /**
+ * Class to represent an entry in the hash table. Holds a single key-value
+ * pair.
+ */
+ static class Entry implements Map.Entry
+ {
+ Object key;
+ Object value;
+ Entry next;
- /**
- * construct a new HashMap with the default capacity and the default
- * load factor
- */
- public HashMap()
+ Entry(Object key, Object value)
{
- init(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
+ this.key = key;
+ this.value = value;
}
- /**
- * construct a new HashMap with a specific inital capacity and load factor
- *
- * @param initialCapacity the initial capacity of this HashMap (>=0)
- * @param initialLoadFactor the load factor of this HashMap
- * (a misnomer, really, since the load factor of
- * a HashMap does not change)
- *
- * @throws IllegalArgumentException if (initialCapacity < 0) ||
- * (initialLoadFactor > 1.0) ||
- * (initialLoadFactor <= 0.0)
- */
- public HashMap(int initialCapacity, float initialLoadFactor)
- throws IllegalArgumentException
+ public boolean equals(Object o)
{
- if (initialCapacity < 0 || initialLoadFactor <= 0 || initialLoadFactor > 1)
- throw new IllegalArgumentException();
- else
- init(initialCapacity, initialLoadFactor);
- }
-
- /**
- * construct a new HashMap with a specific inital capacity
- *
- * @param initialCapacity the initial capacity of this HashMap (>=0)
- *
- * @throws IllegalArgumentException if (initialCapacity < 0)
- */
- public HashMap(int initialCapacity)
- throws IllegalArgumentException
- {
- if (initialCapacity < 0)
- throw new IllegalArgumentException();
- else
- init(initialCapacity, DEFAULT_LOAD_FACTOR);
- }
-
- /**
- * construct a new HashMap from the given Map
- *
- * every element in Map t will be put into this new HashMap
- *
- * @param t 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>
- */
- public HashMap(Map t)
- {
- int mapSize = t.size() * 2;
- init(((mapSize > DEFAULT_CAPACITY) ? mapSize : DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR);
- putAll(t);
- }
-
-
- // PUBLIC METHODS ---------------------------------------------------------
-
- /** returns the number of kay-value mappings currently in this Map */
- public int size()
- {
- return size;
- }
-
- /** returns true if there are no key-value mappings currently in this Map */
- public boolean isEmpty()
- {
- return size == 0;
- }
-
- /** empties this HashMap of all elements */
- public void clear()
- {
- size = 0;
- modCount++;
- buckets = new Bucket[capacity];
- }
-
- /**
- * returns a shallow clone of this HashMap (i.e. the Map itself is cloned, but
- * its contents are not)
- */
- public Object clone()
- {
- Map.Entry entry;
- Iterator it = entrySet().iterator();
- HashMap clone = new HashMap(capacity, loadFactor);
- while (it.hasNext())
- {
- entry = (Map.Entry) it.next();
- clone.internalPut(entry.getKey(), entry.getValue());
- }
- return clone;
- }
-
- /** returns a "set view" of this HashMap's keys */
- public Set keySet()
- {
- return new HashMapSet(KEYS);
- }
-
- /** returns a "set view" of this HashMap's entries */
- public Set entrySet()
- {
- return new HashMapSet(ENTRIES);
- }
-
- /** returns a "collection view" (or "bag view") of this HashMap's values */
- public Collection values()
- {
- return new HashMapCollection();
- }
-
- /**
- * returns true if the supplied object equals (<pre>equals()</pre>) a key
- * in this HashMap
- *
- * @param key the key to search for in this HashMap
- */
- public boolean containsKey(Object key)
- {
- return (internalGet(key) != null);
+ if (!(o instanceof Map.Entry))
+ return false;
+ Map.Entry e = (Map.Entry) o;
+ return (key == null ? e.getKey() == null : key.equals(e.getKey())
+ && value == null ? e.getValue() == null :
+ value.equals(e.getValue()));
}
- /**
- * returns true if this HashMap contains a value <pre>o</pre>, such that
- * <pre>o.equals(value)</pre>.
- *
- * @param value the value to search for in this Hashtable
- */
- public boolean containsValue(Object value)
+ public Object getKey()
{
- int i;
- Bucket list;
-
- for (i = 0; i < capacity; i++)
- {
- list = buckets[i];
- if (list != null && list.containsValue(value))
- return true;
- }
- return false;
+ return key;
}
- /*
- * return the value in this Hashtable associated with the supplied key, or <pre>null</pre>
- * if the key maps to nothing
- *
- * @param key the key for which to fetch an associated value
- */
- public Object get(Object key)
+ public Object getValue()
{
- Map.Entry oResult = internalGet(key);
- return (oResult == null) ? null : oResult.getValue();
+ return value;
}
-
- /**
- * puts the supplied value into the Map, mapped by the supplied key
- *
- * @param key the HashMap key used to locate the value
- * @param value the value to be stored in the HashMap
- */
- public Object put(Object key, Object value)
+
+ public int hashCode()
{
- return internalPut(key, value);
+ int kc = (key == null ? 0 : key.hashCode());
+ int vc = (value == null ? 0 : value.hashCode());
+ return kc ^ vc;
}
-
- /**
- * removes from the HashMap and returns the value which is mapped by the
- * supplied key; if the key maps to nothing, then the HashMap remains unchanged,
- * and <pre>null</pre> is returned
- *
- * @param key the key used to locate the value to remove from the HashMap
- */
- public Object remove(Object key)
+
+ public Object setValue(Object newVal)
{
- Bucket list;
- int index;
- Object result = null;
- if (size > 0)
- {
- index = hash(((key == null) ? NULL_KEY : key));
- list = buckets[index];
- if (list != null)
- {
- result = list.removeByKey(key);
- if (result != null)
- {
- size--;
- modCount++;
- if (list.first == null)
- buckets[index] = null;
- }
- }
- }
- return result;
+ Object r = value;
+ value = newVal;
+ return r;
}
-
-
- // PRIVATE METHODS -----------------------------------------------------------
-
- /**
- * puts the given key-value pair into this HashMap; a private method is used
- * because it is called by the rehash() method as well as the put() method,
- * and if a subclass overrides put(), then rehash would do funky things
- * if it called put()
- *
- * @param key the HashMap key used to locate the value
- * @param value the value to be stored in the HashMap
- */
- private Object internalPut(Object key, Object value)
+
+ public String toString()
{
- HashMapEntry entry;
- Bucket list;
- int hashIndex;
- Object oResult;
- Object oRealKey = ((key == null) ? NULL_KEY : key);
-
- entry = new HashMapEntry(oRealKey, value);
- hashIndex = hash(oRealKey);
- list = buckets[hashIndex];
- if (list == null)
+ return key + "=" + value;
+ }
+ }
+
+ /**
+ * construct a new HashMap with the default capacity (11) and the default
+ * load factor (0.75).
+ */
+ public HashMap()
+ {
+ this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
+ }
+
+ /**
+ * construct a new HashMap from the given Map
+ *
+ * every element in Map t will be put into this new HashMap
+ *
+ * @param t 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>
+ */
+ public HashMap(Map m)
+ {
+ int size = Math.max(m.size() * 2, DEFAULT_CAPACITY);
+ buckets = new Entry[size];
+ threshold = (int) (size * loadFactor);
+ putAll(m);
+ }
+
+ /**
+ * construct a new HashMap with a specific inital capacity
+ *
+ * @param initialCapacity the initial capacity of this HashMap (>=0)
+ *
+ * @throws IllegalArgumentException if (initialCapacity < 0)
+ */
+ public HashMap(int initialCapacity) throws IllegalArgumentException
+ {
+ this(initialCapacity, DEFAULT_LOAD_FACTOR);
+ }
+
+ /**
+ * construct a new HashMap with a specific inital capacity and load factor
+ *
+ * @param initialCapacity the initial capacity (>=0)
+ * @param loadFactor the load factor
+ *
+ * @throws IllegalArgumentException if (initialCapacity < 0) ||
+ * (initialLoadFactor > 1.0) ||
+ * (initialLoadFactor <= 0.0)
+ */
+ public HashMap(int initialCapacity, float loadFactor)
+ throws IllegalArgumentException
+ {
+ if (initialCapacity < 0 || loadFactor <= 0 || loadFactor > 1)
+ throw new IllegalArgumentException();
+
+ buckets = new Entry[initialCapacity];
+ this.loadFactor = loadFactor;
+ this.threshold = (int) (initialCapacity * loadFactor);
+ }
+
+ /** returns the number of kay-value mappings currently in this Map */
+ public int size()
+ {
+ return size;
+ }
+
+ /** returns true if there are no key-value mappings currently in this Map */
+ public boolean isEmpty()
+ {
+ return size == 0;
+ }
+
+ /**
+ * returns true if this HashMap contains a value <pre>o</pre>, such that
+ * <pre>o.equals(value)</pre>.
+ *
+ * @param value the value to search for in this Hashtable
+ */
+ public boolean containsValue(Object value)
+ {
+ for (int i = 0; i < buckets.length; i++)
+ {
+ Entry e = buckets[i];
+ while (e != null)
{
- list = new Bucket();
- buckets[hashIndex] = list;
+ if (value == null ? e.value == null : value.equals(e.value))
+ return true;
+ e = e.next;
+ }
+ }
+ return false;
+ }
+
+ /**
+ * returns true if the supplied object equals (<pre>equals()</pre>) a key
+ * in this HashMap
+ *
+ * @param key the key to search for in this HashMap
+ */
+ public boolean containsKey(Object key)
+ {
+ int idx = hash(key);
+ Entry e = buckets[idx];
+ while (e != null)
+ {
+ if (key == null ? e.key == null : key.equals(e.key))
+ return true;
+ e = e.next;
+ }
+ return false;
+ }
+
+ /**
+ * return the value in this Hashtable associated with the supplied key, or <pre>null</pre>
+ * if the key maps to nothing
+ *
+ * @param key the key for which to fetch an associated value
+ */
+ public Object get(Object key)
+ {
+ int idx = hash(key);
+ Entry e = buckets[idx];
+ while (e != null)
+ {
+ if (key == null ? e.key == null : key.equals(e.key))
+ return e.value;
+ e = e.next;
+ }
+ return null;
+ }
+
+ /**
+ * puts the supplied value into the Map, mapped by the supplied key
+ *
+ * @param key the HashMap key used to locate the value
+ * @param value the value to be stored in the HashMap
+ */
+ public Object put(Object key, Object value)
+ {
+ modCount++;
+ int idx = hash(key);
+ Entry e = buckets[idx];
+ Entry last = e; // Final entry in bucket's linked list, if any.
+
+ while (e != null)
+ {
+ if (key == null ? e.key == null : key.equals(e.key))
+ {
+ Object r = e.value;
+ e.value = value;
+ return r;
}
- oResult = list.add(entry);
- if (oResult == null)
- {
- modCount++;
- if (size++ == threshold)
- rehash();
- return null;
- }
else
- {
- // SEH: if key already exists, we don't rehash & we don't update the modCount
- // because it is not a "structural" modification
- return oResult;
- }
- }
-
- /**
- * a private method, called by all of the constructors to initialize a new HashMap
- *
- * @param initialCapacity the initial capacity of this HashMap (>=0)
- * @param initialLoadFactor the load factor of this HashMap
- * (a misnomer, really, since the load factor of
- * a HashMap does not change)
- */
- private void init(int initialCapacity, float initialLoadFactor)
- {
- size = 0;
- modCount = 0;
- capacity = initialCapacity;
- loadFactor = initialLoadFactor;
- threshold = (int) ((float) capacity * loadFactor);
- buckets = new Bucket[capacity];
- }
-
- /** private -- simply hashes a non-null Object to its array index */
- private int hash(Object key)
- {
- return Math.abs(key.hashCode() % capacity);
- }
-
- /**
- * increases the size of the HashMap and rehashes all keys to new array indices;
- * this is called when the addition of a new value would cause size() > threshold
- */
- private void rehash()
- {
- int i;
- Bucket[] data = buckets;
- Bucket.Node node;
-
- modCount++;
- capacity = (capacity * 2) + 1;
- size = 0;
- threshold = (int) ((float) capacity * loadFactor);
- buckets = new Bucket[capacity];
- for (i = 0; i < data.length; i++)
- {
- if (data[i] != null)
- {
- node = data[i].first;
- while (node != null)
- {
- internalPut(node.getKey(), node.getValue());
- node = node.next;
- }
- }
- }
- }
-
- /**
- * a private method which does the "dirty work" (or some of it anyway) of fetching a value
- * with a key
- *
- * @param key the key for which to fetch an associated value
- */
- private Map.Entry internalGet(Object key)
- {
- Bucket list;
- if (size == 0)
- {
- return null;
- }
+ {
+ last = e;
+ e = e.next;
+ }
+ }
+
+ // At this point, we know we need to add a new entry.
+ if (++size > threshold)
+ {
+ rehash();
+ // Need a new hash value to suit the bigger table.
+ idx = hash(key);
+ }
+
+ e = new Entry(key, value);
+
+ if (last != null)
+ last.next = e;
+ else
+ buckets[idx] = e;
+
+ return null;
+ }
+
+ /**
+ * removes from the HashMap and returns the value which is mapped by the
+ * supplied key; if the key maps to nothing, then the HashMap remains unchanged,
+ * and <pre>null</pre> is returned
+ *
+ * @param key the key used to locate the value to remove from the HashMap
+ */
+ public Object remove(Object key)
+ {
+ modCount++;
+ int idx = hash(key);
+ Entry e = buckets[idx];
+ Entry last = null;
+
+ while (e != null)
+ {
+ if (key == null ? e.key == null : key.equals(e.key))
+ {
+ if (last == null)
+ buckets[idx] = e.next;
+ else
+ last.next = e.next;
+ size--;
+ return e.value;
+ }
+ last = e;
+ e = e.next;
+ }
+ return null;
+ }
+
+ public void putAll(Map m)
+ {
+ int msize = m.size();
+ Iterator itr = m.entrySet().iterator();
+
+ for (int i=0; i < msize; i++)
+ {
+ Map.Entry e = (Map.Entry) itr.next();
+ // Optimize in case the Entry is one of our own.
+ if (e instanceof Entry)
+ {
+ Entry entry = (Entry) e;
+ put(entry.key, entry.value);
+ }
else
- {
- list = buckets[hash(((key == null) ? NULL_KEY : key))];
- return (list == null) ? null : list.getEntryByKey(key);
- }
- }
-
- /**
- * a private method used by inner class HashMapSet to implement its own
- * <pre>contains(Map.Entry)</pre> method; returns true if the supplied
- * key / value pair is found in this HashMap (again, using <pre>equals()</pre>,
- * rather than <pre>==</pre>)
- *
- * @param entry a Map.Entry to match against key / value pairs in
- * this HashMap
- */
- private boolean containsEntry(Map.Entry entry)
+ {
+ put(e.getKey(), e.getValue());
+ }
+ }
+ }
+
+ public void clear()
+ {
+ modCount++;
+ for (int i=0; i < buckets.length; i++)
+ {
+ buckets[i] = null;
+ }
+ size = 0;
+ }
+
+ /**
+ * returns a shallow clone of this HashMap (i.e. the Map itself is cloned, but
+ * its contents are not)
+ */
+ public Object clone()
+ {
+ HashMap copy = null;
+ try
+ {
+ copy = (HashMap) super.clone();
+ }
+ catch (CloneNotSupportedException x)
+ {
+ }
+ copy.buckets = new Entry[buckets.length];
+
+ for (int i=0; i < buckets.length; i++)
+ {
+ Entry e = buckets[i];
+ Entry last = null;
+
+ while (e != null)
+ {
+ if (last == null)
+ {
+ copy.buckets[i] = new Entry(e.key, e.value);
+ last = copy.buckets[i];
+ }
+ else
+ {
+ last.next = new Entry(e.key, e.value);
+ last = last.next;
+ }
+ e = e.next;
+ }
+ }
+ return copy;
+ }
+
+ /** returns a "set view" of this HashMap's keys */
+ public Set keySet()
+ {
+ // Create an AbstractSet with custom implementations of those methods that
+ // can be overriden easily and efficiently.
+ return new AbstractSet()
{
- Map.Entry oInternalEntry;
- if (entry == null)
- {
- return false;
- }
- else
- {
- oInternalEntry = internalGet(entry.getKey());
- return (oInternalEntry != null && oInternalEntry.equals(entry));
- }
- }
-
- /**
- * Serializes this object to the given stream.
- * @serialdata the <i>capacity</i>(int) that is the length of the
- * bucket array, the <i>size</i>(int) of the hash map are emitted
- * first. They are followed by size entries, each consisting of
- * a key (Object) and a value (Object).
- */
- private void writeObject(ObjectOutputStream s)
- throws IOException
+ public int size()
+ {
+ return size;
+ }
+
+ public Iterator iterator()
+ {
+ return new HashIterator(HashIterator.KEYS);
+ }
+
+ public void clear()
+ {
+ HashMap.this.clear();
+ }
+
+ public boolean contains(Object o)
+ {
+ return HashMap.this.containsKey(o);
+ }
+
+ public boolean remove(Object o)
+ {
+ // Test against the size of the HashMap to determine if anything
+ // really got removed. This is neccessary because the return value of
+ // HashMap.remove() is ambiguous in the null case.
+ int oldsize = size;
+ HashMap.this.remove(o);
+ return (oldsize != size);
+ }
+ };
+ }
+
+ /** Returns a "collection view" (or "bag view") of this HashMap's values. */
+ public Collection values()
+ {
+ // We don't bother overriding many of the optional methods, as doing so
+ // wouldn't provide any significant performance advantage.
+ return new AbstractCollection()
{
- // the fields
- s.defaultWriteObject();
-
- s.writeInt(capacity);
- s.writeInt(size);
- Iterator it = entrySet().iterator();
- while (it.hasNext())
- {
- Map.Entry oEntry = (Map.Entry) it.next();
- s.writeObject(oEntry.getKey());
- s.writeObject(oEntry.getValue());
- }
- }
-
- /**
- * Deserializes this object from the given stream.
- * @serialdata the <i>capacity</i>(int) that is the length of the
- * bucket array, the <i>size</i>(int) of the hash map are emitted
- * first. They are followed by size entries, each consisting of
- * a key (Object) and a value (Object).
- */
- private void readObject(ObjectInputStream s)
- throws IOException, ClassNotFoundException
+ public int size()
+ {
+ return size;
+ }
+
+ public Iterator iterator()
+ {
+ return new HashIterator(HashIterator.VALUES);
+ }
+
+ public void clear()
+ {
+ HashMap.this.clear();
+ }
+ };
+ }
+
+ /** Returns a "set view" of this HashMap's entries. */
+ public Set entrySet()
+ {
+ // Create an AbstractSet with custom implementations of those methods that
+ // can be overriden easily and efficiently.
+ return new AbstractSet()
{
- // the fields
- s.defaultReadObject();
-
- capacity = s.readInt();
- int iLen = s.readInt();
- size = 0;
- modCount = 0;
- buckets = new Bucket[capacity];
-
- for (int i = 0; i < iLen; i++)
- {
- Object oKey = s.readObject();
- Object oValue = s.readObject();
- internalPut(oKey, oValue);
- }
- }
-
- // INNER CLASSES -------------------------------------------------------------
- // ---------------------------------------------------------------------------
+ public int size()
+ {
+ return size;
+ }
+
+ public Iterator iterator()
+ {
+ return new HashIterator(HashIterator.ENTRIES);
+ }
+
+ public void clear()
+ {
+ HashMap.this.clear();
+ }
+
+ public boolean contains(Object o)
+ {
+ if (!(o instanceof Map.Entry))
+ return false;
+ Map.Entry me = (Map.Entry) o;
+ Entry e = getEntry(me);
+ return (e != null);
+ }
+
+ public boolean remove(Object o)
+ {
+ if (!(o instanceof Map.Entry))
+ return false;
+ Map.Entry me = (Map.Entry) o;
+ Entry e = getEntry(me);
+ if (e != null)
+ {
+ HashMap.this.remove(e.key);
+ return true;
+ }
+ return false;
+ }
+ };
+ }
+
+ /** Return an index in the buckets array for `key' based on its hashCode() */
+ private int hash(Object key)
+ {
+ return (key == null ? 0 : Math.abs(key.hashCode() % buckets.length));
+ }
+
+ /** Return an Entry who's key and value equal the supplied Map.Entry.
+ * This is used by entrySet's contains() and remove() methods. They can't
+ * use contains(key) and remove(key) directly because that would result
+ * in entries with the same key but a different value being matched. */
+ private Entry getEntry(Map.Entry me)
+ {
+ int idx = hash(me.getKey());
+ Entry e = buckets[idx];
+ while (e != null)
+ {
+ if (e.equals(me))
+ return e;
+ e = e.next;
+ }
+ return null;
+ }
+
+ /**
+ * increases the size of the HashMap and rehashes all keys to new array
+ * indices; this is called when the addition of a new value would cause
+ * size() > threshold. Note that the existing Entry objects are reused in
+ * the new hash table.
+ */
+ private void rehash()
+ {
+ Entry[] oldBuckets = buckets;
- /**
- * an inner class providing a Set view of a HashMap; this implementation is
- * parameterized to view either a Set of keys or a Set of Map.Entry objects
- *
- * Note: a lot of these methods are implemented by AbstractSet, and would work
- * just fine without any meddling, but far greater efficiency can be gained by
- * overriding a number of them. And so I did.
- *
- * @author Jon Zeppieri
- * @version $Revision: 1.6 $
- * @modified $Id: HashMap.java,v 1.6 2000/03/15 21:59:13 rao Exp $
- */
- private class HashMapSet extends AbstractSet
- implements Set
- {
- /** the type of this Set view: KEYS or ENTRIES */
- private int setType;
-
- /** construct a new HashtableSet with the supplied view type */
- HashMapSet(int type)
- {
- setType = type;
- }
-
- /**
- * adding an element is unsupported; this method simply throws an exception
- *
- * @throws UnsupportedOperationException
- */
- public boolean add(Object o) throws UnsupportedOperationException
- {
- throw new UnsupportedOperationException();
- }
-
- /**
- * adding an element is unsupported; this method simply throws an exception
- *
- * @throws UnsupportedOperationException
- */
- public boolean addAll(Collection c) throws UnsupportedOperationException
- {
- throw new UnsupportedOperationException();
- }
-
- /**
- * clears the backing HashMap; this is a prime example of an overridden implementation
- * which is far more efficient than its superclass implementation (which uses an iterator
- * and is O(n) -- this is an O(1) call)
- */
- public void clear()
- {
- HashMap.this.clear();
- }
-
- /**
- * returns true if the supplied object is contained by this Set
- *
- * @param o an Object being testing to see if it is in this Set
- */
- public boolean contains(Object o)
- {
- if (setType == KEYS)
- return HashMap.this.containsKey(o);
- else
- return (o instanceof Map.Entry) ? HashMap.this.containsEntry((Map.Entry) o) : false;
- }
-
- /**
- * returns true if the backing HashMap is empty (which is the only case either a KEYS
- * Set or an ENTRIES Set would be empty)
- */
- public boolean isEmpty()
- {
- return HashMap.this.isEmpty();
- }
-
- /**
- * removes the supplied Object from the Set
- *
- * @param o the Object to be removed
- */
- public boolean remove(Object o)
- {
- if (setType == KEYS)
- return (HashMap.this.remove(o) != null);
+ int newcapacity = (buckets.length * 2) + 1;
+ threshold = (int) (newcapacity * loadFactor);
+ buckets = new Entry[newcapacity];
+
+ for (int i = 0; i < oldBuckets.length; i++)
+ {
+ Entry e = oldBuckets[i];
+ while (e != null)
+ {
+ int idx = hash(e.key);
+ Entry dest = buckets[idx];
+
+ if (dest != null)
+ {
+ while (dest.next != null)
+ dest = dest.next;
+ dest.next = e;
+ }
else
- return (o instanceof Map.Entry) ?
- (HashMap.this.remove(((Map.Entry) o).getKey()) != null) : false;
- }
-
- /** returns the size of this Set (always equal to the size of the backing Hashtable) */
- public int size()
- {
- return HashMap.this.size();
- }
+ {
+ buckets[idx] = e;
+ }
- /** returns an Iterator over the elements of this Set */
- public Iterator iterator()
- {
- return new HashMapIterator(setType);
- }
- }
-
- /**
- * Like the above Set view, except this one if for values, which are not
- * guaranteed to be unique in a Map; this prvides a Bag of values
- * in the HashMap
- *
- * @author Jon Zeppieri
- * @version $Revision: 1.6 $
- * @modified $Id: HashMap.java,v 1.6 2000/03/15 21:59:13 rao Exp $
- */
- private class HashMapCollection extends AbstractCollection
- implements Collection
+ Entry next = e.next;
+ e.next = null;
+ e = next;
+ }
+ }
+ }
+
+ /**
+ * Serializes this object to the given stream.
+ * @serialdata the <i>capacity</i>(int) that is the length of the
+ * bucket array, the <i>size</i>(int) of the hash map are emitted
+ * first. They are followed by size entries, each consisting of
+ * a key (Object) and a value (Object).
+ */
+ private void writeObject(ObjectOutputStream s) throws IOException
+ {
+ // the threshold and loadFactor fields
+ s.defaultWriteObject();
+
+ s.writeInt(buckets.length);
+ s.writeInt(size);
+ Iterator it = entrySet().iterator();
+ while (it.hasNext())
+ {
+ Map.Entry entry = (Map.Entry) it.next();
+ s.writeObject(entry.getKey());
+ s.writeObject(entry.getValue());
+ }
+ }
+
+ /**
+ * Deserializes this object from the given stream.
+ * @serialdata the <i>capacity</i>(int) that is the length of the
+ * bucket array, the <i>size</i>(int) of the hash map are emitted
+ * first. They are followed by size entries, each consisting of
+ * a key (Object) and a value (Object).
+ */
+ private void readObject(ObjectInputStream s)
+ throws IOException, ClassNotFoundException
+ {
+ // the threshold and loadFactor fields
+ s.defaultReadObject();
+
+ int capacity = s.readInt();
+ int len = s.readInt();
+ size = 0;
+ modCount = 0;
+ buckets = new Entry[capacity];
+
+ for (int i = 0; i < len; i++)
+ {
+ Object key = s.readObject();
+ Object value = s.readObject();
+ put(key, value);
+ }
+ }
+
+ /**
+ * a class which implements the Iterator interface and is used for
+ * iterating over HashMaps;
+ * this implementation is parameterized to give a sequential view of
+ * keys, values, or entries; it also allows the removal of elements,
+ * as per the Javasoft spec.
+ *
+ * @author Jon Zeppieri
+ * @version $Revision: 1.8 $
+ * @modified $Id: HashMap.java,v 1.8 2000/10/26 10:19:00 bryce Exp $
+ */
+ class HashIterator implements Iterator
+ {
+ static final int KEYS = 0,
+ VALUES = 1,
+ ENTRIES = 2;
+
+ // the type of this Iterator: KEYS, VALUES, or ENTRIES.
+ int type;
+ // the number of modifications to the backing Hashtable that we know about.
+ int knownMod;
+ // The total number of elements returned by next(). Used to determine if
+ // there are more elements remaining.
+ int count;
+ // Current index in the physical hash table.
+ int idx;
+ // The last Entry returned by a next() call.
+ Entry last;
+ // The next entry that should be returned by next(). It is set to something
+ // if we're iterating through a bucket that contains multiple linked
+ // entries. It is null if next() needs to find a new bucket.
+ Entry next;
+
+ /* construct a new HashtableIterator with the supllied type:
+ KEYS, VALUES, or ENTRIES */
+ HashIterator(int type)
{
- /** a trivial contructor for HashMapCollection */
- HashMapCollection()
- {
- }
-
- /**
- * adding elements is not supported by this Collection;
- * this method merely throws an exception
- *
- * @throws UnsupportedOperationException
- */
- public boolean add(Object o) throws UnsupportedOperationException
- {
- throw new UnsupportedOperationException();
- }
-
- /**
- * adding elements is not supported by this Collection;
- * this method merely throws an exception
- *
- * @throws UnsupportedOperationException
- */
- public boolean addAll(Collection c) throws UnsupportedOperationException
- {
- throw new UnsupportedOperationException();
- }
-
- /** removes all elements from this Collection (and from the backing HashMap) */
- public void clear()
- {
- HashMap.this.clear();
- }
-
- /**
- * returns true if this Collection contains at least one Object which equals() the
- * supplied Object
- *
- * @param o the Object to compare against those in the Set
- */
- public boolean contains(Object o)
- {
- return HashMap.this.containsValue(o);
- }
-
- /** returns true IFF the Collection has no elements */
- public boolean isEmpty()
- {
- return HashMap.this.isEmpty();
- }
-
- /** returns the size of this Collection */
- public int size()
- {
- return HashMap.this.size();
- }
-
- /** returns an Iterator over the elements in this Collection */
- public Iterator iterator()
- {
- return new HashMapIterator(VALUES);
- }
+ this.type = type;
+ knownMod = HashMap.this.modCount;
+ count = 0;
+ idx = buckets.length;
}
- /**
- * a class which implements the Iterator interface and is used for
- * iterating over HashMaps;
- * this implementation is parameterized to give a sequential view of
- * keys, values, or entries; it also allows the removal of elements,
- * as per the Javasoft spec.
- *
- * @author Jon Zeppieri
- * @version $Revision: 1.6 $
- * @modified $Id: HashMap.java,v 1.6 2000/03/15 21:59:13 rao Exp $
- */
- class HashMapIterator implements Iterator
+ /** returns true if the Iterator has more elements */
+ public boolean hasNext()
{
- /** the type of this Iterator: KEYS, VALUES, or ENTRIES */
- private int myType;
- /**
- * the number of modifications to the backing Hashtable for which
- * this Iterator can account (idea ripped off from Stuart Ballard)
- */
- private int knownMods;
- /** the location of our sequential "cursor" */
- private int position;
- /** the current index of the BucketList array */
- private int bucketIndex;
- /** a reference, originally null, to the specific Bucket our "cursor" is pointing to */
- private Bucket.Node currentNode;
- /** a reference to the current key -- used fro removing elements via the Iterator */
- private Object currentKey;
-
- /** construct a new HashtableIterator with the supllied type: KEYS, VALUES, or ENTRIES */
- HashMapIterator(int type)
- {
- myType = type;
- knownMods = HashMap.this.modCount;
- position = 0;
- bucketIndex = -1;
- currentNode = null;
- currentKey = null;
- }
-
- /**
- * Stuart Ballard's code: if the backing HashMap has been altered through anything
- * but <i>this</i> Iterator's <pre>remove()</pre> method, we will give up right here,
- * rather than risking undefined behavior
- *
- * @throws ConcurrentModificationException
- */
- private void checkMod()
- {
- if (knownMods != HashMap.this.modCount)
- throw new ConcurrentModificationException();
- }
-
- /** returns true if the Iterator has more elements */
- public boolean hasNext()
- {
- checkMod();
- return position < HashMap.this.size();
- }
-
- /** returns the next element in the Iterator's sequential view */
- public Object next()
- {
- Bucket list = null;
- Object result;
- checkMod();
- try
- {
- while (currentNode == null)
- {
- while (list == null)
- list = HashMap.this.buckets[++bucketIndex];
- currentNode = list.first;
- }
- currentKey = currentNode.getKey();
- result = (myType == KEYS) ? currentKey :
- ((myType == VALUES) ? currentNode.getValue() : currentNode);
- currentNode = currentNode.next;
- }
- catch(Exception e)
- {
- throw new NoSuchElementException();
- }
- position++;
- return result;
- }
-
- /**
- * removes from the backing HashMap the last element which was fetched with the
- * <pre>next()</pre> method
- */
- public void remove()
- {
- checkMod();
- if (currentKey == null)
- {
- throw new IllegalStateException();
- }
- else
- {
- HashMap.this.remove(currentKey);
- knownMods++;
- position--;
- currentKey = null;
- }
- }
+ if (knownMod != HashMap.this.modCount)
+ throw new ConcurrentModificationException();
+ return count < size;
}
- /**
- * a singleton instance of this class (HashMap.NULL_KEY)
- * is used to represent the null key in HashMap objects
- *
- * @author Jon Zeppieri
- * @version $Revision: 1.6 $
- * @modified $Id: HashMap.java,v 1.6 2000/03/15 21:59:13 rao Exp $
- */
- private static class Null
+ /** returns the next element in the Iterator's sequential view */
+ public Object next()
{
- /** trivial constructor */
- Null()
- {
+ if (knownMod != HashMap.this.modCount)
+ throw new ConcurrentModificationException();
+ if (count == size)
+ throw new NoSuchElementException();
+ count++;
+ Entry e = null;
+ if (next != null)
+ e = next;
+
+ while (e == null)
+ {
+ e = buckets[--idx];
}
+
+ next = e.next;
+ last = e;
+ if (type == VALUES)
+ return e.value;
+ else if (type == KEYS)
+ return e.key;
+ return e;
}
- /**
- * a HashMap version of Map.Entry -- one thing in this implementation is
- * HashMap-specific: if the key is HashMap.NULL_KEY, getKey() will return
- * null
- *
- * Simply, a key / value pair
- *
- * @author Jon Zeppieri
- * @version $Revision: 1.6 $
- * @modified $Id: HashMap.java,v 1.6 2000/03/15 21:59:13 rao Exp $
+ /**
+ * removes from the backing HashMap the last element which was fetched with the
+ * <pre>next()</pre> method
*/
- private static class HashMapEntry extends Bucket.Node implements Map.Entry
+ public void remove()
{
- /** construct a new HashMapEntry with the given key and value */
- public HashMapEntry(Object key, Object value)
+ if (knownMod != HashMap.this.modCount)
+ throw new ConcurrentModificationException();
+ if (last == null)
{
- super(key, value);
+ throw new IllegalStateException();
}
-
- /**
- * if the key == HashMap.NULL_KEY, null is returned, otherwise the actual
- * key is returned
- */
- public Object getKey()
+ else
{
- Object oResult = super.getKey();
- return (oResult == HashMap.NULL_KEY) ? null : oResult;
+ HashMap.this.remove(last.key);
+ knownMod++;
+ count--;
+ last = null;
}
}
- // EOF -----------------------------------------------------------------------
+ }
}
--- /dev/null
+/* HashSet.java -- a class providing a HashMap-backet Set
+ Copyright (C) 1998, 1999 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.
+
+As a special exception, if you link this library with other files to
+produce an executable, this library does not by itself cause the
+resulting executable to be covered by the GNU General Public License.
+This exception does not however invalidate any other reasons why the
+executable file might be covered by the GNU General Public License. */
+
+
+package java.util;
+
+import java.io.IOException;
+import java.io.Serializable;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+
+/**
+ * This class provides a HashMap-backed implementation of the
+ * Set interface.
+ *
+ * Each element in the Set is a key in the backing HashMap; each key
+ * maps to a static token, denoting that the key does, in fact, exist.
+ *
+ * Most operations are O(1), assuming no hash collisions. In the worst
+ * case (where all hases collide), operations are O(n).
+ *
+ * HashSet is a part of the JDK1.2 Collections API.
+ *
+ * @author Jon Zeppieri
+ * @version $Revision: 1.5 $
+ * @modified $Id: HashSet.java,v 1.5 2000/10/26 10:19:00 bryce Exp $
+ */
+public class HashSet extends AbstractSet
+ implements Set, Cloneable, Serializable
+{
+ /** the HashMap which backs this Set */
+ transient HashMap map;
+ static final long serialVersionUID = -5024744406713321676L;
+
+ /**
+ * construct a new, empty HashSet whose backing HashMap has the default
+ * capacity and loadFacor
+ */
+ public HashSet()
+ {
+ map = new HashMap();
+ }
+
+ /**
+ * construct a new, empty HashSet whose backing HashMap has the supplied
+ * capacity and the default load factor
+ *
+ * @param initialCapacity the initial capacity of the backing
+ * HashMap
+ */
+ public HashSet(int initialCapacity)
+ {
+ map = new HashMap(initialCapacity);
+ }
+
+ /**
+ * construct a new, empty HashSet whose backing HashMap has the supplied
+ * capacity and load factor
+ *
+ * @param initialCapacity the initial capacity of the backing
+ * HashMap
+ * @param loadFactor the load factor of the backing HashMap
+ */
+ public HashSet(int initialCapacity, float loadFactor)
+ {
+ map = new HashMap(initialCapacity, loadFactor);
+ }
+
+ /**
+ * construct a new HashSet with the same elements as are in the supplied
+ * collection (eliminating any duplicates, of course; the backing HashMap
+ * will have the default capacity and load factor
+ *
+ * @param c a collection containing the elements with
+ * which this set will be initialized
+ */
+ public HashSet(Collection c)
+ {
+ map = new HashMap();
+ addAll(c);
+ }
+
+ /**
+ * adds the given Object to the set if it is not already in the Set,
+ * returns true if teh element was added, false otherwise
+ *
+ * @param o the Object to add to this Set
+ */
+ public boolean add(Object o)
+ {
+ return (map.put(o, Boolean.TRUE) == null);
+ }
+
+ /**
+ * empties this Set of all elements; this is a fast operation [O(1)]
+ */
+ public void clear()
+ {
+ map.clear();
+ }
+
+ /**
+ * returns a shallow copy of this Set (the Set itself is cloned; its
+ * elements are not)
+ */
+ public Object clone()
+ {
+ HashSet copy = null;
+ try
+ {
+ copy = (HashSet) super.clone();
+ copy.map = (HashMap) map.clone();
+ }
+ catch (CloneNotSupportedException ex)
+ {
+ }
+
+ return copy;
+ }
+
+ /**
+ * returns true if the supplied element is in this Set, false otherwise
+ *
+ * @param o the Object whose presence in this Set we are testing for
+ */
+ public boolean contains(Object o)
+ {
+ return map.containsKey(o);
+ }
+
+ /**
+ * returns true if this set has no elements in it (size() == 0)
+ */
+ public boolean isEmpty()
+ {
+ return map.isEmpty();
+ }
+
+ /**
+ * returns an Iterator over the elements of this Set; the Iterator allows
+ * removal of elements
+ */
+ public Iterator iterator()
+ {
+ return map.keySet().iterator();
+ }
+
+ /**
+ * removes the supplied Object from this Set if it is in the Set; returns
+ * true if an element was removed, false otherwise
+ */
+ public boolean remove(Object o)
+ {
+ return (map.remove(o) != null);
+ }
+
+ /**
+ * returns the number of elements in this Set
+ */
+ public int size()
+ {
+ return map.size();
+ }
+
+ /** Serialize this Object in a manner which is binary-compatible with the
+ * JDK */
+ private void writeObject(ObjectOutputStream s) throws IOException
+ {
+ Iterator it = iterator();
+ s.writeInt(map.buckets.length);
+ s.writeFloat(map.loadFactor);
+ s.writeInt(map.size);
+ while (it.hasNext())
+ s.writeObject(it.next());
+ }
+
+ /** Deserialize this Object in a manner which is binary-compatible with
+ * the JDK */
+ private void readObject(ObjectInputStream s) throws IOException,
+ ClassNotFoundException
+ {
+ int i, size, capacity;
+ float loadFactor;
+ Object element;
+
+ capacity = s.readInt();
+ loadFactor = s.readFloat();
+ size = s.readInt();
+
+ map = new HashMap(capacity, loadFactor);
+
+ for (i = 0; i < size; i++)
+ {
+ element = s.readObject();
+ map.put(element, Boolean.TRUE);
+ }
+ }
+}
This exception does not however invalidate any other reasons why the
executable file might be covered by the GNU General Public License. */
-
package java.util;
import java.io.IOException;
import java.io.Serializable;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
-import java.io.ObjectStreamField;
+
+// NOTE: This implementation is very similar to that of HashMap. If you fix
+// a bug in here, chances are you should make a similar change to the HashMap
+// code.
/**
* a class which implements a Hashtable data structure
* Enumeration. The latter can end up in an undefined state if the Hashtable
* changes while the Enumeration is open.
*
+ * Unlike HashMap, Hashtable does not accept `null' as a key value.
+ *
* @author Jon Zeppieri
- * @version $Revision: 1.7 $
- * @modified $Id: Hashtable.java,v 1.7 2000/03/15 21:59:13 rao Exp $
+ * @author Warren Levy
+ * @author Bryce McKinlay
+ * @version $Revision: 1.6 $
+ * @modified $Id: Hashtable.java,v 1.6 2000/08/19 18:19:42 green Exp $
*/
public class Hashtable extends Dictionary
implements Map, Cloneable, Serializable
{
- // STATIC VARIABLES
- // ----------------
-
- /**
- * the default capacity of a Hashtable
- *
- * This value strikes me as absurdly low, an invitation to all manner of
- * hash collisions. Perhaps it should be raised. I set it to 11 since the
- * JDK-1.2b4 specification uses that value in the third constructor
- * Hashtable(Map t) if the given Map is small. */
- private static final int DEFAULT_CAPACITY = 11;
-
- /** the defaulty load factor; this is explicitly specified by Sun */
- private static final float DEFAULT_LOAD_FACTOR = 0.75F;
-
- // used internally for parameterizing inner classes
- private static final int KEYS = 0;
- private static final int VALUES = 1;
- private static final int ENTRIES = 2;
-
- // used for serializing instances of this class
- private static final ObjectStreamField[] serialPersistentFields =
- { new ObjectStreamField("loadFactor", float.class),
- new ObjectStreamField("threshold", int.class) };
+ /** Default number of buckets. This is the value the JDK 1.3 uses. Some
+ * early documentation specified this value as 101. That is incorrect. */
+ private static final int DEFAULT_CAPACITY = 11;
+ /** The defaulty load factor; this is explicitly specified by Sun */
+ private static final float DEFAULT_LOAD_FACTOR = 0.75f;
+
private static final long serialVersionUID = 1421746759512286392L;
-
- // INSTANCE VARIABLES
- // ------------------
-
- /** the capacity of this Hashtable: denotes the size of the bucket array */
- private int capacity;
-
- /** the size of this Hashtable: denotes the number of elements currently in
- * <pre>this</pre> */
- private int size;
-
- /** the load factor of this Hashtable: used in computing the threshold */
- private float loadFactor;
-
- /* the rounded product of the capacity and the load factor; when the
- * number of elements exceeds the threshold, the Hashtable calls
- * <pre>rehash()</pre> */
- private int threshold;
-
- /** where the data is actually stored; Bucket implements
- * a very simple, lightweight (and hopefully fast) linked-list */
- Bucket[] buckets;
-
- /** counts the number of modifications this Hashtable has undergone;
- * used by Iterators to know when to throw
- * ConcurrentModificationExceptions (idea ripped-off from Stuart
- * Ballard's AbstractList implementation) */
- int modCount;
-
- /**
- * construct a new Hashtable with the default capacity and the
- * default load factor */
+
+ /**
+ * The rounded product of the capacity and the load factor; when the number
+ * of elements exceeds the threshold, the Hashtable calls <pre>rehash()</pre>.
+ * @serial
+ */
+ int threshold;
+
+ /** Load factor of this Hashtable: used in computing the threshold.
+ * @serial
+ */
+ float loadFactor = DEFAULT_LOAD_FACTOR;
+
+ /**
+ * Array containing the actual key-value mappings
+ */
+ transient HashMap.Entry[] buckets;
+
+ /**
+ * counts the number of modifications this Hashtable has undergone, used
+ * by Iterators to know when to throw ConcurrentModificationExceptions.
+ */
+ transient int modCount;
+
+ /** the size of this Hashtable: denotes the number of key-value pairs */
+ transient int size;
+
+ /**
+ * Class to represent an entry in the hash table. Holds a single key-value
+ * pair. A Hashtable Entry is identical to a HashMap Entry, except that
+ * `null' is not allowed for keys and values.
+ */
+ static class Entry extends HashMap.Entry
+ {
+ Entry(Object key, Object value)
+ {
+ super(key, value);
+ }
+
+ public Object setValue(Object newVal)
+ {
+ if (newVal == null)
+ throw new NullPointerException();
+ return super.setValue(newVal);
+ }
+ }
+
+ /**
+ * construct a new Hashtable with the default capacity (11) and the default
+ * load factor (0.75).
+ */
public Hashtable()
{
- init (DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
+ this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
}
-
+
/**
- * construct a new Hashtable with a specific inital capacity and load factor
- *
- * @param initialCapacity the initial capacity of this Hashtable (>=0)
- * @param initialLoadFactor the load factor of this Hashtable
- * (a misnomer, really, since the load factor of
- * a Hashtable does not change)
+ * construct a new Hashtable from the given Map
*
- * @throws IllegalArgumentException if (initialCapacity < 0) ||
- * (initialLoadFactor > 1.0) ||
- * (initialLoadFactor <= 0.0)
+ * every element in Map t will be put into this new Hashtable
+ *
+ * @param t a Map whose key / value pairs will be put into
+ * the new Hashtable. <b>NOTE: key / value pairs
+ * are not cloned in this constructor</b>
*/
- public Hashtable(int initialCapacity, float initialLoadFactor)
- throws IllegalArgumentException
+ public Hashtable(Map m)
{
- if (initialCapacity < 0 || initialLoadFactor <= 0 || initialLoadFactor > 1)
- throw new IllegalArgumentException();
- else
- init(initialCapacity, initialLoadFactor);
+ int size = Math.max(m.size() * 2, DEFAULT_CAPACITY);
+ buckets = new Entry[size];
+ threshold = (int) (size * loadFactor);
+ putAll(m);
}
-
+
/**
* construct a new Hashtable with a specific inital capacity
*
*
* @throws IllegalArgumentException if (initialCapacity < 0)
*/
- public Hashtable(int initialCapacity)
- throws IllegalArgumentException
+ public Hashtable(int initialCapacity) throws IllegalArgumentException
{
- if (initialCapacity < 0)
- throw new IllegalArgumentException();
- else
- init(initialCapacity, DEFAULT_LOAD_FACTOR);
+ this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
-
+
/**
- * construct a new Hashtable from the given Map
- *
- * every element in Map t will be put into this new Hashtable
+ * construct a new Hashtable with a specific inital capacity and load factor
*
- * @param t a Map whose key / value pairs will be put into
- * the new Hashtable. <b>NOTE: key / value pairs
- * are not cloned in this constructor</b>
+ * @param initialCapacity the initial capacity (>=0)
+ * @param loadFactor the load factor
+ *
+ * @throws IllegalArgumentException if (initialCapacity < 0) ||
+ * (initialLoadFactor > 1.0) ||
+ * (initialLoadFactor <= 0.0)
*/
- public Hashtable(Map t)
+ public Hashtable(int initialCapacity, float loadFactor)
+ throws IllegalArgumentException
{
- int mapSize = t.size() * 2;
- init (((mapSize > DEFAULT_CAPACITY) ? mapSize : DEFAULT_CAPACITY),
- DEFAULT_LOAD_FACTOR);
- putAll (t);
+ if (initialCapacity < 0 || loadFactor <= 0 || loadFactor > 1)
+ throw new IllegalArgumentException();
+
+ buckets = new Entry[initialCapacity];
+ this.loadFactor = loadFactor;
+ this.threshold = (int) (initialCapacity * loadFactor);
}
-
-
- /** returns the number of key / value pairs stored in this Hashtable */
- public synchronized int size()
+
+ /** Returns the number of key-value mappings currently in this Map */
+ public int size()
{
return size;
}
-
- /** returns true if this Hashtable is empty (size() == 0), false otherwise */
- public synchronized boolean isEmpty()
+
+ /** returns true if there are no key-value mappings currently in this Map */
+ public boolean isEmpty()
{
return size == 0;
}
-
- /** returns an Enumeration of the keys in this Hashtable
- *
- * <b>WARNING: if a Hashtable is changed while an Enumeration is
- * iterating over it, the behavior of the Enumeration is undefined.
- * Use keySet().iterator() if you want to be safe.</b> */
+
+ /** */
public synchronized Enumeration keys()
{
- return new HashtableEnumeration(KEYS);
+ return new Enumerator(Enumerator.KEYS);
}
- /**
- * returns an Enumeration of the values in this Hashtable
- *
- * <b>WARNING: if a Hashtable is changed while an Enumeration is
- * iterating over it, the behavior of the Enumeration is undefined.
- * Use values().ieterator() if you want to be safe.</b> */
public synchronized Enumeration elements()
{
- return new HashtableEnumeration(VALUES);
+ return new Enumerator(Enumerator.VALUES);
}
-
+
/**
* returns true if this Hashtable contains a value <pre>o</pre>,
* such that <pre>o.equals(value)</pre>.
*
* @param value the value to search for in this Hashtable
*
- * @throws NullPointerException if <pre>value</pre> is null */
- public boolean contains(Object value) throws NullPointerException
- {
- if (value == null)
- throw new NullPointerException();
- else
- return containsValue(value);
- }
-
- /**
- * behaves identically to <pre>contains()</pre>, except it does not
- * throw a NullPointerException when given a null argument (Note:
- * Sun's implementation (JDK1.2beta4) <i>does</i> throw a
- * NullPointerException when given a null argument, but this seems
- * to go against the Collections Framework specifications, so I have
- * not reproduced this behavior. I have submitted a bug report to
- * Sun on the mater, but have not received any response yet (26
- * September 1998)
- *
- * @param value the value to search for in this Hashtable */
- public synchronized boolean containsValue(Object value)
+ * @throws NullPointerException if <pre>value</pre> is null
+ */
+ public synchronized boolean contains(Object value)
{
- int i;
- Bucket list;
-
- for (i = 0; i < capacity; i++)
+ for (int i = 0; i < buckets.length; i++)
{
- list = buckets[i];
- if (list != null && list.containsValue(value))
- return true;
+ HashMap.Entry e = buckets[i];
+ while (e != null)
+ {
+ if (value.equals(e.value))
+ return true;
+ e = e.next;
+ }
}
return false;
}
-
+
/**
- * returns true if the supplied key is found in this Hashtable
- * (strictly, if there exists a key <pre>k</pre> in the Hashtable,
- * such that <pre>k.equals(key)</pre>)
+ * returns true if this Hashtable contains a value <pre>o</pre>, such that
+ * <pre>o.equals(value)</pre>.
*
- * @param key the key to search for in this Hashtable */
- public synchronized boolean containsKey(Object key)
+ * @param value the value to search for in this Hashtable
+ *
+ * @throws NullPointerException if <pre>value</pre> is null
+ */
+ public boolean containsValue(Object value)
{
- return (internalGet(key) != null);
+ return contains(value);
}
-
- /**
- * a private method used by inner class HashtableSet to implement
- * its own <pre>contains(Map.Entry)</pre> method; returns true if
- * the supplied key / value pair is found in this Hashtable (again,
- * using <pre>equals()</pre>, rather than <pre>==</pre>)
+
+ /**
+ * returns true if the supplied object equals (<pre>equals()</pre>) a key
+ * in this Hashtable
*
- * @param entry a Map.Entry to match against key / value pairs in
- * this Hashtable */
- private synchronized boolean containsEntry(Map.Entry entry)
+ * @param key the key to search for in this Hashtable
+ */
+ public synchronized boolean containsKey(Object key)
{
- Object o;
- if (entry == null)
+ int idx = hash(key);
+ HashMap.Entry e = buckets[idx];
+ while (e != null)
{
- return false;
- }
- else
- {
- o = internalGet(entry.getKey());
- return (o != null && o.equals(entry.getValue()));
+ if (key.equals(e.key))
+ return true;
+ e = e.next;
}
+ return false;
}
-
- /*
- * return the value in this Hashtable associated with the supplied
- * key, or <pre>null</pre> if the key maps to nothing
+
+ /**
+ * return the value in this Hashtable associated with the supplied key, or <pre>null</pre>
+ * if the key maps to nothing
*
- * @param key the key for which to fetch an associated value */
+ * @param key the key for which to fetch an associated value
+ */
public synchronized Object get(Object key)
{
- return internalGet(key);
- }
-
- /**
- * a private method which does the "dirty work" (or some of it
- * anyway) of fetching a value with a key
- *
- * @param key the key for which to fetch an associated value */
- private Object internalGet(Object key)
- {
- Bucket list;
- if (key == null || size == 0)
+ int idx = hash(key);
+ HashMap.Entry e = buckets[idx];
+ while (e != null)
{
- return null;
- }
- else
- {
- list = buckets[hash(key)];
- return (list == null) ? null : list.getValueByKey(key);
+ if (key.equals(e.key))
+ return e.value;
+ e = e.next;
}
+ return null;
}
-
- /**
- * increases the size of the Hashtable and rehashes all keys to new
- * array indices; this is called when the addition of a new value
- * would cause size() > threshold */
- protected void rehash()
+
+ /**
+ * puts the supplied value into the Map, mapped by the supplied key
+ *
+ * @param key the key used to locate the value
+ * @param value the value to be stored in the table
+ */
+ public synchronized Object put(Object key, Object value)
{
- int i;
- Bucket[] data = buckets;
- Bucket.Node node;
-
modCount++;
- capacity = (capacity * 2) + 1;
- size = 0;
- threshold = (int) ((float) capacity * loadFactor);
- buckets = new Bucket[capacity];
- for (i = 0; i < data.length; i++)
+ int idx = hash(key);
+ HashMap.Entry e = buckets[idx];
+ HashMap.Entry last = e; // Final entry in bucket's linked list, if any.
+
+ // Hashtable does not accept null values. This method doesn't dereference
+ // `value' anywhere, so check for it explicitly.
+ if (value == null)
+ throw new NullPointerException();
+
+ while (e != null)
{
- if (data[i] != null)
+ if (key.equals(e.key))
{
- node = data[i].first;
- while (node != null)
- {
- internalPut(node.getKey(), node.getValue());
- node = node.next;
- }
+ Object r = e.value;
+ e.value = value;
+ return r;
+ }
+ else
+ {
+ last = e;
+ e = e.next;
}
}
- }
-
- /**
- * puts the supplied value into the Hashtable, mapped by the
- * supplied key; neither the key nore the value is allowed to be
- * <pre>null</pre>, otherwise a <pre>NullPointerException</pre> will
- * be thrown
- *
- * @param key the Hashtable key used to locate the value
- * @param value the value to be stored in the Hashtable */
- public synchronized Object put(Object key, Object value)
- throws NullPointerException
- {
- if (key == null || value == null)
- throw new NullPointerException();
- else
- return internalPut(key, value);
- }
-
- /**
- * A private method with a semi-interesting history (it's at least
- * two hours old now); orginally, this functionality was in the
- * public <pre>put()</pre> method, but while searching (fruitlessly)
- * on the JDC for some clarification of Javasoft's bizarre
- * Serialization documentation, I instead came across a JDK bug
- * which had been fixed in JDK-1.2b3. Extending Hashtable was a
- * pain, because <pre>put()</pre> was apparently being used
- * internally by the class when the Hashtable was rehashed, and this
- * was causing odd behavior for people who had overridden
- * <pre>put()</pre> in a Hashtable subclass. Well, I was also
- * calling <pre>put()</pre> internally, and realized that my code
- * would have the same problem. [No, I have never looked at the
- * Javasoft code; it was just the easiest thing to do]. So I put
- * the real work in a private method, and I call <i>this</i> for
- * internal use. Except...not all the time. What about
- * <pre>putAll()</pre>? Well, it seems reasonably clear from the
- * Collections spec that <pre>putAll()</pre> is <i>supposed</i> to
- * call <pre>put()</pre>. So, it still does. Confused yet?
- *
- * @param key the Hashtable key used to locate the value
- * @param value the value to be stored in the Hashtable */
- private Object internalPut(Object key, Object value)
- {
- HashtableEntry entry;
- Bucket list;
- int hashIndex;
- Object oResult;
- modCount++;
- if (size == threshold)
- rehash();
- entry = new HashtableEntry(key, value);
- hashIndex = hash(key);
- list = buckets[hashIndex];
- if (list == null)
+ // At this point, we know we need to add a new entry.
+ if (++size > threshold)
{
- list = new Bucket();
- buckets[hashIndex] = list;
- }
- oResult = list.add(entry);
- if (oResult == null)
- {
- size++;
- return null;
+ rehash();
+ // Need a new hash value to suit the bigger table.
+ idx = hash(key);
}
+
+ e = new Entry(key, value);
+
+ if (last != null)
+ last.next = e;
else
- {
- return oResult;
- }
+ buckets[idx] = e;
+
+ return null;
}
-
+
/**
- * removes from the Hashtable and returns the value which is mapped
- * by the supplied key; if the key maps to nothing, then the
- * Hashtable remains unchanged, and <pre>null</pre> is returned
+ * removes from the table and returns the value which is mapped by the
+ * supplied key; if the key maps to nothing, then the table remains
+ * unchanged, and <pre>null</pre> is returned
*
- * @param key the key used to locate the value to remove from the Hashtable */
+ * @param key the key used to locate the value to remove
+ */
public synchronized Object remove(Object key)
{
- Bucket list;
- int index;
- Object result = null;
- if (key != null && size > 0)
+ modCount++;
+ int idx = hash(key);
+ HashMap.Entry e = buckets[idx];
+ HashMap.Entry last = null;
+
+ while (e != null)
{
- index = hash(key);
- list = buckets[index];
- if (list != null)
+ if (key.equals(e.key))
{
- result = list.removeByKey(key);
- if (result != null)
- {
- size--;
- modCount++;
- if (list.first == null)
- buckets[index] = null;
- }
+ if (last == null)
+ buckets[idx] = e.next;
+ else
+ last.next = e.next;
+ size--;
+ return e.value;
}
+ last = e;
+ e = e.next;
}
- return result;
+ return null;
}
-
- /**
- * part of the Map interface; for each Map.Entry in t, the key/value
- * pair is added to this Hashtable, <b>using the <pre>put()</pre>
- * method -- this may not be you want, so be warned (see notes to
- * <pre>internalPut()</pre>, above</b>
- *
- * @param t a Map whose key/value pairs will be added to this Hashtable */
- public synchronized void putAll(Map t) throws NullPointerException
+
+ public synchronized void putAll(Map m)
{
- Map.Entry entry;
- Iterator it = t.entrySet().iterator();
- while (it.hasNext())
+ int msize = m.size();
+ Iterator itr = m.entrySet().iterator();
+
+ for (int i=0; i < msize; i++)
{
- entry = (Map.Entry) it.next();
- put(entry.getKey(), entry.getValue());
+ Map.Entry e = (Map.Entry) itr.next();
+ // Optimize in case the Entry is one of our own.
+ if (e instanceof Entry)
+ {
+ Entry entry = (Entry) e;
+ put(entry.key, entry.value);
+ }
+ else
+ {
+ put(e.getKey(), e.getValue());
+ }
}
}
-
- /** empties this Hashtable of all elements */
public synchronized void clear()
{
- size = 0;
modCount++;
- buckets = new Bucket[capacity];
+ for (int i=0; i < buckets.length; i++)
+ {
+ buckets[i] = null;
+ }
+ size = 0;
}
-
+
/**
- * returns a shallow clone of this Hashtable (i.e. the Hashtable
- * itself is cloned, but its contents are not) */
+ * returns a shallow clone of this Hashtable (i.e. the Map itself is cloned,
+ * but its contents are not)
+ */
public synchronized Object clone()
{
- Map.Entry entry;
- Iterator it = entrySet().iterator();
- Hashtable clone = new Hashtable(capacity, loadFactor);
- while (it.hasNext())
+ Hashtable copy = null;
+ try
+ {
+ copy = (Hashtable) super.clone();
+ }
+ catch (CloneNotSupportedException x)
+ {
+ }
+ copy.buckets = new Entry[buckets.length];
+
+ for (int i=0; i < buckets.length; i++)
{
- entry = (Map.Entry) it.next();
- clone.internalPut(entry.getKey(), entry.getValue());
+ HashMap.Entry e = buckets[i];
+ HashMap.Entry last = null;
+
+ while (e != null)
+ {
+ if (last == null)
+ {
+ copy.buckets[i] = new Entry(e.key, e.value);
+ last = copy.buckets[i];
+ }
+ else
+ {
+ last.next = new Entry(e.key, e.value);
+ last = last.next;
+ }
+ e = e.next;
+ }
}
- return clone;
+ return copy;
}
- /**
- * returns a String representation of this Hashtable
- *
- * the String representation of a Hashtable is defined by Sun and
- * looks like this:
- * <pre>
- * {name_1=value_1, name_2=value_2, name_3=value_3, ..., name_N=value_N}
- * </pre>
- * for N elements in this Hashtable */
public synchronized String toString()
{
- Map.Entry entry;
- Iterator it = entrySet().iterator();
- StringBuffer sb = new StringBuffer("{");
- boolean isFirst = true;
- while (it.hasNext())
+ Iterator entries = entrySet().iterator();
+ StringBuffer r = new StringBuffer("{");
+ for (int pos = 0; pos < size; pos++)
{
- entry = (Map.Entry) it.next();
- if (isFirst)
- isFirst = false;
- else
- sb.append(", ");
- sb.append(entry.getKey().toString()).append("=").append(entry.getValue().toString());
+ r.append(entries.next());
+ if (pos < size - 1)
+ r.append(", ");
}
- sb.append("}");
- return sb.toString();
+ r.append("}");
+ return r.toString();
}
-
- /** returns a Set of Keys in this Hashtable */
- public synchronized Set keySet()
+
+ /** returns a "set view" of this Hashtable's keys */
+ public Set keySet()
{
- return new HashtableSet(KEYS);
+ // Create a synchronized AbstractSet with custom implementations of those
+ // methods that can be overriden easily and efficiently.
+ Set r = new AbstractSet()
+ {
+ public int size()
+ {
+ return size;
+ }
+
+ public Iterator iterator()
+ {
+ return new HashIterator(HashIterator.KEYS);
+ }
+
+ public void clear()
+ {
+ Hashtable.this.clear();
+ }
+
+ public boolean contains(Object o)
+ {
+ return Hashtable.this.containsKey(o);
+ }
+
+ public boolean remove(Object o)
+ {
+ return (Hashtable.this.remove(o) != null);
+ }
+ };
+
+ return Collections.synchronizedSet(r);
}
- /**
- * returns a Set of Map.Entry objects in this Hashtable;
- * note, this was called <pre>entries()</pre> prior to JDK-1.2b4 */
- public synchronized Set entrySet()
+ /** Returns a "collection view" (or "bag view") of this Hashtable's values.
+ */
+ public Collection values()
{
- return new HashtableSet(ENTRIES);
+ // We don't bother overriding many of the optional methods, as doing so
+ // wouldn't provide any significant performance advantage.
+ Collection r = new AbstractCollection()
+ {
+ public int size()
+ {
+ return size;
+ }
+
+ public Iterator iterator()
+ {
+ return new HashIterator(HashIterator.VALUES);
+ }
+
+ public void clear()
+ {
+ Hashtable.this.clear();
+ }
+ };
+
+ return Collections.synchronizedCollection(r);
}
-
- // This is the pre JDK1.2b4 named method for the above
- // public Set entries()
- // {
- // return entrySet();
- // }
-
- /** returns a Collection of values in this Hashtable */
- public synchronized Collection values()
+
+ /** Returns a "set view" of this Hashtable's entries. */
+ public Set entrySet()
{
- return new HashtableCollection();
+ // Create an AbstractSet with custom implementations of those methods that
+ // can be overriden easily and efficiently.
+ Set r = new AbstractSet()
+ {
+ public int size()
+ {
+ return size;
+ }
+
+ public Iterator iterator()
+ {
+ return new HashIterator(HashIterator.ENTRIES);
+ }
+
+ public void clear()
+ {
+ Hashtable.this.clear();
+ }
+
+ public boolean contains(Object o)
+ {
+ if (!(o instanceof Map.Entry))
+ return false;
+ Map.Entry me = (Map.Entry) o;
+ HashMap.Entry e = getEntry(me);
+ return (e != null);
+ }
+
+ public boolean remove(Object o)
+ {
+ if (!(o instanceof Map.Entry))
+ return false;
+ Map.Entry me = (Map.Entry) o;
+ HashMap.Entry e = getEntry(me);
+ if (e != null)
+ {
+ Hashtable.this.remove(e.key);
+ return true;
+ }
+ return false;
+ }
+ };
+
+ return Collections.synchronizedSet(r);
}
/** returns true if this Hashtable equals the supplied Object <pre>o</pre>;
* for each key in o.keySet(), o.get(key).equals(get(key))
*</pre>
*/
- public synchronized boolean equals(Object o)
+ public boolean equals(Object o)
{
- Map other;
- Set keys = keySet();
- Object currentKey;
- Iterator it;
- if (o instanceof Map)
+ if (o == this)
+ return true;
+ if (!(o instanceof Map))
+ return false;
+
+ Map m = (Map) o;
+ Set s = m.entrySet();
+ Iterator itr = entrySet().iterator();
+
+ if (m.size() != size)
+ return false;
+
+ for (int pos = 0; pos < size; pos++)
{
- other = (Map) o;
- if (other.keySet().equals(keys))
- {
- it = keys.iterator();
- while (it.hasNext())
- {
- currentKey = it.next();
- if (!get(currentKey).equals(other.get(currentKey)))
- return false;
- }
- return true;
- }
+ if (!s.contains(itr.next()))
+ return false;
}
- return false;
+ return true;
}
/** a Map's hashCode is the sum of the hashCodes of all of its
Map.Entry objects */
- public synchronized int hashCode()
+ public int hashCode()
{
- Iterator it = entrySet().iterator();
- int result = 0;
- while (it.hasNext())
- result += it.next().hashCode();
- return result;
- }
-
- /**
- * a private method, called by all of the constructors to initialize a new Hashtable
- *
- * @param initialCapacity the initial capacity of this Hashtable (>=0)
- * @param initialLoadFactor the load factor of this Hashtable
- * (a misnomer, really, since the load factor of
- * a Hashtable does not change)
- */
- private void init(int initialCapacity, float initialLoadFactor)
- {
- size = 0;
- modCount = 0;
- capacity = initialCapacity;
- loadFactor = initialLoadFactor;
- threshold = (int) ((float) capacity * loadFactor);
- buckets = new Bucket[capacity];
+ int hashcode = 0;
+ Iterator itr = entrySet().iterator();
+ for (int pos = 0; pos < size; pos++)
+ {
+ hashcode += itr.next().hashCode();
+ }
+ return hashcode;
}
- /** private -- simply hashes a non-null Object to its array index */
+ /** Return an index in the buckets array for `key' based on its hashCode() */
private int hash(Object key)
{
- return Math.abs(key.hashCode() % capacity);
+ return Math.abs(key.hashCode() % buckets.length);
}
-
- /** Serialize this Object in a manner which is binary-compatible
- with the JDK */
- private void writeObject(ObjectOutputStream s) throws IOException
+
+ private HashMap.Entry getEntry(Map.Entry me)
{
- ObjectOutputStream.PutField oFields;
- Iterator it = entrySet().iterator();
- Map.Entry oEntry;
- oFields = s.putFields();
- oFields.put("loadFactor", loadFactor);
- oFields.put("threshold", threshold);
- s.writeFields();
-
- s.writeInt(capacity);
- s.writeInt(size);
- while (it.hasNext())
+ int idx = hash(me.getKey());
+ HashMap.Entry e = buckets[idx];
+ while (e != null)
{
- oEntry = (Map.Entry) it.next();
- s.writeObject(oEntry.getKey());
- s.writeObject(oEntry.getValue());
+ if (e.equals(me))
+ return e;
+ e = e.next;
}
+ return null;
}
- /** Deserialize this Object in a manner which is binary-compatible
- with the JDK */
- private void readObject(ObjectInputStream s)
- throws IOException, ClassNotFoundException
+ /**
+ * increases the size of the Hashtable and rehashes all keys to new array
+ * indices; this is called when the addition of a new value would cause
+ * size() > threshold. Note that the existing Entry objects are reused in
+ * the new hash table.
+ */
+ protected void rehash()
{
- int i;
- int iLen;
- Object oKey, oValue;
- ObjectInputStream.GetField oFields;
- oFields = s.readFields();
- loadFactor = oFields.get("loadFactor", DEFAULT_LOAD_FACTOR);
- threshold = oFields.get("threshold",
- (int) (DEFAULT_LOAD_FACTOR
- * (float) DEFAULT_CAPACITY));
+ HashMap.Entry[] oldBuckets = buckets;
- capacity = s.readInt();
- iLen = s.readInt();
- size = 0;
- modCount = 0;
- buckets = new Bucket[capacity];
+ int newcapacity = (buckets.length * 2) + 1;
+ threshold = (int) (newcapacity * loadFactor);
+ buckets = new Entry[newcapacity];
- for (i = 0; i < iLen; i++)
+ for (int i = 0; i < oldBuckets.length; i++)
{
- oKey = s.readObject();
- oValue = s.readObject();
- internalPut(oKey, oValue);
+ HashMap.Entry e = oldBuckets[i];
+ while (e != null)
+ {
+ int idx = hash(e.key);
+ HashMap.Entry dest = buckets[idx];
+
+ if (dest != null)
+ {
+ while (dest.next != null)
+ dest = dest.next;
+ dest.next = e;
+ }
+ else
+ {
+ buckets[idx] = e;
+ }
+
+ HashMap.Entry next = e.next;
+ e.next = null;
+ e = next;
+ }
}
}
-
+
/**
- * a Hashtable version of Map.Entry -- one thing in this implementation is
- * Hashtable-specific: a NullPointerException is thrown if someone calls
- * <pre>setValue(null)</pre>
- *
- * Simply, a key / value pair
- *
- * @author Jon Zeppieri
- * @version $Revision: 1.7 $
- * @modified $Id: Hashtable.java,v 1.7 2000/03/15 21:59:13 rao Exp $
+ * Serializes this object to the given stream.
+ * @serialdata the <i>capacity</i>(int) that is the length of the
+ * bucket array, the <i>size</i>(int) of the hash map are emitted
+ * first. They are followed by size entries, each consisting of
+ * a key (Object) and a value (Object).
*/
- private static class HashtableEntry extends Bucket.Node implements Map.Entry
- {
- /** construct a new HastableEntry with the given key and value */
- public HashtableEntry(Object key, Object value)
- {
- super(key, value);
- }
-
- /** sets the value of this Map.Entry; throws NullPointerException if
- * <pre>newValue</pre> is null
- *
- * @throws NullPointerException if <pre>newValue</pre> is null
- */
- public Object setValue(Object newValue)
- throws UnsupportedOperationException, ClassCastException,
- IllegalArgumentException, NullPointerException
- {
- if (newValue == null)
- throw new NullPointerException();
- else
- return super.setValue(newValue);
- }
- }
-
-
- /**
- * an inner class representing an Enumeration view of this
- * Hashtable, providing sequential access to its elements; this
- * implementation is parameterized to provide access either to the
- * keys or to the values in the Hashtable
- *
- * @author Jon Zeppieri
- * @version $Revision: 1.7 $
- * @modified $Id: Hashtable.java,v 1.7 2000/03/15 21:59:13 rao Exp $ */
- private class HashtableEnumeration implements Enumeration
- {
- /** the type of Enumeration: KEYS or VALUES */
- private int myType;
- /** where are we in our iteration over the elements of this Hashtable */
- private int position;
- /** our current index into the BucketList array */
- private int bucketIndex;
- /** a reference to the specific Bucket at which our "cursor" is positioned */
- private Bucket.Node currentNode;
-
- /**
- * construct a new HashtableEnumeration with the given type of view
- *
- * @param type KEYS or VALUES: the type of view this Enumeration is
- * providing
- */
- HashtableEnumeration(int type)
- {
- myType = type;
- position = 0;
- bucketIndex = -1;
- currentNode = null;
- }
-
- /**
- * returns true if not all elements have been retrived from the Enuemration
- *
- * <b>NOTE: modifications to the backing Hashtable while iterating
- * through an Enumeration can result in undefined behavior, as the
- * cursor may no longer be appropriately positioned</b> */
- public boolean hasMoreElements()
- {
- return position < Hashtable.this.size();
- }
-
- /**
- * returns the next element from the Enuemration
- *
- * <b>NOTE: modifications to the backing Hashtable while iterating
- * through an Enumeration can result in undefined behavior, as the
- * cursor may no longer be appropriately positioned</b>
- *
- * @throws NoSuchElementException if there are no more elements left in
- * the sequential view */
- public Object nextElement()
- {
- Bucket list = null;
- Object result;
- try
- {
- while (currentNode == null)
- {
- while (list == null)
- list = Hashtable.this.buckets[++bucketIndex];
- currentNode = list.first;
- }
- result = (myType == KEYS) ? currentNode.getKey() :
- currentNode.getValue();
- currentNode = currentNode.next;
- }
- catch(Exception e)
- {
- throw new NoSuchElementException();
- }
- position++;
- return result;
- }
- }
-
- /**
- * an inner class providing a Set view of a Hashtable; this
- * implementation is parameterized to view either a Set of keys or a
- * Set of Map.Entry objects
- *
- * Note: a lot of these methods are implemented by AbstractSet, and
- * would work just fine without any meddling, but far greater
- * efficiency can be gained by overriding a number of them. And so
- * I did.
- *
- * @author Jon Zeppieri
- * @version $Revision: 1.7 $
- * @modified $Id: Hashtable.java,v 1.7 2000/03/15 21:59:13 rao Exp $ */
- private class HashtableSet extends AbstractSet
+ private void writeObject(ObjectOutputStream s) throws IOException
{
- /** the type of this Set view: KEYS or ENTRIES */
- private int setType;
-
- /** construct a new HashtableSet with the supplied view type */
- HashtableSet(int type)
- {
- setType = type;
- }
-
- /**
- * adding an element is unsupported; this method simply throws an
- * exception
- *
- * @throws UnsupportedOperationException */
- public boolean add(Object o) throws UnsupportedOperationException
- {
- throw new UnsupportedOperationException();
- }
-
- /**
- * adding an element is unsupported; this method simply throws an
- * exception
- *
- * @throws UnsupportedOperationException */
- public boolean addAll(Collection c) throws UnsupportedOperationException
- {
- throw new UnsupportedOperationException();
- }
-
- /**
- * clears the backing Hashtable; this is a prime example of an
- * overridden implementation which is far more efficient than its
- * superclass implementation (which uses an iterator and is O(n)
- * -- this is an O(1) call) */
- public void clear()
- {
- Hashtable.this.clear();
- }
-
- /**
- * returns true if the supplied object is contained by this Set
- *
- * @param o an Object being testing to see if it is in this Set
- */
- public boolean contains(Object o)
- {
- if (setType == KEYS)
- return Hashtable.this.containsKey(o);
- else
- return (o instanceof Map.Entry) ? Hashtable.this.containsEntry((Map.Entry) o) : false;
- }
-
- /**
- * returns true if the backing Hashtable is empty (which is the
- * only case either a KEYS Set or an ENTRIES Set would be empty) */
- public boolean isEmpty()
- {
- return Hashtable.this.isEmpty();
- }
-
- /**
- * removes the supplied Object from the Set
- *
- * @param o the Object to be removed
- */
- public boolean remove(Object o)
- {
- if (setType == KEYS)
- return (Hashtable.this.remove(o) != null);
- else
- return (o instanceof Map.Entry) ?
- (Hashtable.this.remove(((Map.Entry) o).getKey()) != null) : false;
- }
-
- /** returns the size of this Set (always equal to the size of the
- backing Hashtable) */
- public int size()
- {
- return Hashtable.this.size();
- }
-
- /** returns an Iterator over the elements of this Set */
- public Iterator iterator()
- {
- return new HashtableIterator(setType);
- }
+ // the threshold and loadFactor fields
+ s.defaultWriteObject();
+
+ s.writeInt(buckets.length);
+ s.writeInt(size);
+ Iterator it = entrySet().iterator();
+ while (it.hasNext())
+ {
+ Map.Entry entry = (Map.Entry) it.next();
+ s.writeObject(entry.getKey());
+ s.writeObject(entry.getValue());
+ }
}
-
+
/**
- * Like the above Set view, except this one if for values, which are not
- * guaranteed to be unique in a Hashtable; this prvides a Bag of values
- * in the Hashtable
- *
- * @author Jon Zeppieri
- * @version $Revision: 1.7 $
- * @modified $Id: Hashtable.java,v 1.7 2000/03/15 21:59:13 rao Exp $
+ * Deserializes this object from the given stream.
+ * @serialdata the <i>capacity</i>(int) that is the length of the
+ * bucket array, the <i>size</i>(int) of the hash map are emitted
+ * first. They are followed by size entries, each consisting of
+ * a key (Object) and a value (Object).
*/
- private class HashtableCollection extends AbstractCollection
+ private void readObject(ObjectInputStream s)
+ throws IOException, ClassNotFoundException
{
- /** a trivial contructor for HashtableCollection */
- HashtableCollection()
- {
- }
-
- /**
- * adding elements is not supported by this Collection;
- * this method merely throws an exception
- *
- * @throws UnsupportedOperationException
- */
- public boolean add(Object o) throws UnsupportedOperationException
- {
- throw new UnsupportedOperationException();
- }
-
- /**
- * adding elements is not supported by this Collection;
- * this method merely throws an exception
- *
- * @throws UnsupportedOperationException
- */
- public boolean addAll(Collection c) throws UnsupportedOperationException
- {
- throw new UnsupportedOperationException();
- }
-
- /** removes all elements from this Set (and from the backing Hashtable) */
- public void clear()
- {
- Hashtable.this.clear();
- }
-
- /**
- * returns true if this Collection contains at least one Object which equals() the
- * supplied Object
- *
- * @param o the Object to compare against those in the Set
- */
- public boolean contains(Object o)
- {
- return Hashtable.this.containsValue(o);
- }
-
- /** returns true IFF the Collection has no elements */
- public boolean isEmpty()
- {
- return Hashtable.this.isEmpty();
- }
-
- /** returns the size of this Collection */
- public int size()
- {
- return Hashtable.this.size();
- }
-
- /** returns an Iterator over the elements in this Collection */
- public Iterator iterator()
- {
- return new HashtableIterator(VALUES);
- }
+ // the threshold and loadFactor fields
+ s.defaultReadObject();
+
+ int capacity = s.readInt();
+ int len = s.readInt();
+ size = 0;
+ modCount = 0;
+ buckets = new Entry[capacity];
+
+ for (int i = 0; i < len; i++)
+ {
+ Object key = s.readObject();
+ Object value = s.readObject();
+ put(key, value);
+ }
}
-
+
/**
- * Hashtable's version of the JDK-1.2 counterpart to the Enumeration;
+ * a class which implements the Iterator interface and is used for
+ * iterating over Hashtables;
* this implementation is parameterized to give a sequential view of
* keys, values, or entries; it also allows the removal of elements,
* as per the Javasoft spec.
*
* @author Jon Zeppieri
- * @version $Revision: 1.7 $
- * @modified $Id: Hashtable.java,v 1.7 2000/03/15 21:59:13 rao Exp $
+ * @version $Revision: 1.8 $
+ * @modified $Id: HashMap.java,v 1.8 2000/10/26 10:19:00 bryce Exp $
*/
- class HashtableIterator implements Iterator
- {
- /** the type of this Iterator: KEYS, VALUES, or ENTRIES */
- private int myType;
- /**
- * the number of modifications to the backing Hashtable for which
- * this Iterator can account (idea ripped off from Stuart Ballard)
- */
- private int knownMods;
- /** the location of our sequential "cursor" */
- private int position;
- /** the current index of the BucketList array */
- private int bucketIndex;
- /** a reference, originally null, to the specific Bucket our
- "cursor" is pointing to */
- private Bucket.Node currentNode;
- /** a reference to the current key -- used fro removing elements
- via the Iterator */
- private Object currentKey;
-
- /** construct a new HashtableIterator with the supllied type:
- KEYS, VALUES, or ENTRIES */
- HashtableIterator(int type)
- {
- myType = type;
- knownMods = Hashtable.this.modCount;
- position = 0;
- bucketIndex = -1;
- currentNode = null;
- currentKey = null;
- }
-
- /**
- * Stuart Ballard's code: if the backing Hashtable has been
- * altered through anything but <i>this</i> Iterator's
- * <pre>remove()</pre> method, we will give up right here, rather
- * than risking undefined behavior
- *
- * @throws ConcurrentModificationException */
- private void checkMod()
+ class HashIterator implements Iterator
+ {
+ static final int KEYS = 0,
+ VALUES = 1,
+ ENTRIES = 2;
+
+ // The type of this Iterator: KEYS, VALUES, or ENTRIES.
+ int type;
+ // The number of modifications to the backing Hashtable that we know about.
+ int knownMod;
+ // The total number of elements returned by next(). Used to determine if
+ // there are more elements remaining.
+ int count;
+ // Current index in the physical hash table.
+ int idx;
+ // The last Entry returned by a next() call.
+ HashMap.Entry last;
+ // The next entry that should be returned by next(). It is set to something
+ // if we're iterating through a bucket that contains multiple linked
+ // entries. It is null if next() needs to find a new bucket.
+ HashMap.Entry next;
+
+ /* Construct a new HashIterator with the supplied type:
+ KEYS, VALUES, or ENTRIES */
+ HashIterator(int type)
{
- if (knownMods != Hashtable.this.modCount)
- throw new ConcurrentModificationException();
+ this.type = type;
+ knownMod = Hashtable.this.modCount;
+ count = 0;
+ idx = buckets.length;
}
-
+
/** returns true if the Iterator has more elements */
public boolean hasNext()
{
- checkMod();
- return position < Hashtable.this.size();
+ if (knownMod != Hashtable.this.modCount)
+ throw new ConcurrentModificationException();
+ return count < size;
}
-
- /** returns the next element in the Iterator's sequential view */
+
+ /** Returns the next element in the Iterator's sequential view. */
public Object next()
{
- Bucket list = null;
- Object result;
- checkMod();
- try
- {
- while (currentNode == null)
- {
- while (list == null)
- list = Hashtable.this.buckets[++bucketIndex];
- currentNode = list.first;
- }
- currentKey = currentNode.getKey();
- result = (myType == KEYS) ? currentKey :
- ((myType == VALUES) ? currentNode.getValue() : currentNode);
- currentNode = currentNode.next;
- }
- catch(Exception e)
- {
- throw new NoSuchElementException();
+ if (knownMod != Hashtable.this.modCount)
+ throw new ConcurrentModificationException();
+ if (count == size)
+ throw new NoSuchElementException();
+ count++;
+ HashMap.Entry e = null;
+ if (next != null)
+ e = next;
+
+ while (e == null)
+ {
+ e = buckets[--idx];
}
- position++;
- return result;
+
+ next = e.next;
+ last = e;
+ if (type == VALUES)
+ return e.value;
+ else if (type == KEYS)
+ return e.key;
+ return e;
}
-
+
/**
- * removes from the backing Hashtable the last element which was
- * fetched with the <pre>next()</pre> method */
+ * Removes from the backing Hashtable the last element which was fetched
+ * with the <pre>next()</pre> method.
+ */
public void remove()
{
- checkMod();
- if (currentKey == null)
+ if (knownMod != Hashtable.this.modCount)
+ throw new ConcurrentModificationException();
+ if (last == null)
{
throw new IllegalStateException();
}
else
{
- Hashtable.this.remove(currentKey);
- knownMods++;
- position--;
- currentKey = null;
+ Hashtable.this.remove(last.key);
+ knownMod++;
+ count--;
+ last = null;
}
}
}
-}
-
-
+ /**
+ * Enumeration view of this Hashtable, providing sequential access to its
+ * elements; this implementation is parameterized to provide access either
+ * to the keys or to the values in the Hashtable.
+ *
+ * <b>NOTE: Enumeration is not safe if new elements are put in the table as
+ * this could cause a rehash and we'd completely lose our place. Even
+ * without a rehash, it is undetermined if a new element added would
+ * appear in the enumeration. The spec says nothing about this, but
+ * the "Java Class Libraries" book infers that modifications to the
+ * hashtable during enumeration causes indeterminate results. Don't do it!
+ *
+ * @author Jon Zeppieri
+ * @version $Revision: 1.6 $
+ * @modified $Id: Hashtable.java,v 1.6 2000/08/19 18:19:42 green Exp $ */
+ class Enumerator implements Enumeration
+ {
+ static final int KEYS = 0;
+ static final int VALUES = 1;
+
+ int type;
+ // The total number of elements returned by nextElement(). Used to
+ // determine if there are more elements remaining.
+ int count;
+ // current index in the physical hash table.
+ int idx;
+ // the last Entry returned.
+ HashMap.Entry last;
+
+ Enumerator(int type)
+ {
+ this.type = type;
+ this.count = 0;
+ this.idx = buckets.length;
+ }
+ public boolean hasMoreElements()
+ {
+ return count < Hashtable.this.size;
+ }
+ public Object nextElement()
+ {
+ if (count >= size)
+ throw new NoSuchElementException();
+ count++;
+ HashMap.Entry e;
+ if (last != null)
+ e = last.next;
+ while (e == null)
+ {
+ e = buckets[--idx];
+ }
+ last = e;
+ if (type == VALUES)
+ return e.value;
+ return e.key;
+ }
+ }
+}
--- /dev/null
+/* java.util.WeakHashMap
+ Copyright (C) 1999, 2000 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.
+
+As a special exception, if you link this library with other files to
+produce an executable, this library does not by itself cause the
+resulting executable to be covered by the GNU General Public License.
+This exception does not however invalidate any other reasons why the
+executable file might be covered by the GNU General Public License. */
+
+
+package java.util;
+import java.lang.ref.WeakReference;
+import java.lang.ref.ReferenceQueue;
+
+/**
+ * A weak hash map has only weak references to the key. This means
+ * that it allows the key to be garbage collected if they are not used
+ * otherwise. If this happens, the weak hash map will eventually
+ * remove the whole entry from this map. <br>
+ *
+ * A weak hash map makes most sense, if the keys doesn't override the
+ * <code>equals</code>-method: If there is no other reference to the
+ * key nobody can ever look up the key in this table and so the entry
+ * can be removed. This table also works, if the <code>equals</code>
+ * method is overloaded, e.g. with Strings as keys, but you should be
+ * prepared that some entries disappear spontaneously. <br>
+ *
+ * You should also be prepared that this hash map behaves very
+ * strange: The size of this map may spontaneously shrink (even if you
+ * use a synchronized map and synchronize it); it behaves as if
+ * another thread removes entries from this table without
+ * synchronizations. The entry set returned by <code>entrySet</code>
+ * has similar phenomenons: The size may spontaneously shrink, or an
+ * entry, that was in the set before, suddenly disappears. <br>
+ *
+ * A weak hash map is not meant for caches; use a normal map, with
+ * soft references as values instead. <br>
+ *
+ * The weak hash map supports null values and null keys. Null keys
+ * are never deleted from the map (except explictly of course).
+ * The performance of the methods are similar to that of a hash map. <br>
+ *
+ * The value object are strongly referenced by this table. So if a
+ * value object maintains a strong reference to the key (either direct
+ * or indirect) the key will never be removed from this map. According
+ * to Sun, this problem may be fixed in a future release. It is not
+ * possible to do it with the jdk 1.2 reference model, though.
+ *
+ * @since jdk1.2
+ * @author Jochen Hoenicke
+ * @see HashMap
+ * @see WeakReference */
+public class WeakHashMap extends AbstractMap implements Map
+{
+ /**
+ * The default capacity for an instance of HashMap.
+ * Sun's documentation mildly suggests that this (11) is the correct
+ * value.
+ */
+ private static final int DEFAULT_CAPACITY = 11;
+
+ /**
+ * The default load factor of a HashMap
+ */
+ private static final float DEFAULT_LOAD_FACTOR = 0.75F;
+
+ /**
+ * This is used instead of the key value <i>null</i>. It is needed
+ * to distinguish between an null key and a removed key.
+ */
+ private static final Object NULL_KEY = new Object();
+
+ /**
+ * The reference queue where our buckets (which are WeakReferences) are
+ * registered to.
+ */
+ private ReferenceQueue queue;
+
+ /**
+ * The number of entries in this hash map.
+ */
+ private int size;
+
+ /**
+ * The load factor of this WeakHashMap. This is the maximum ratio of
+ * size versus number of buckets. If size grows the number of buckets
+ * must grow, too.
+ */
+ private float loadFactor;
+
+ /**
+ * The rounded product of the capacity (i.e. number of buckets) and
+ * the load factor. When the number of elements exceeds the
+ * threshold, the HashMap calls <pre>rehash()</pre>.
+ */
+ private int threshold;
+
+ /**
+ * The number of structural modifications. This is used by
+ * iterators, to see if they should fail. This doesn't count
+ * the silent key removals, when a weak reference is cleared
+ * by the garbage collection. Instead the iterators must make
+ * sure to have strong references to the entries they rely on.
+ */
+ private int modCount;
+
+ /**
+ * The entry set. There is only one instance per hashmap, namely
+ * theEntrySet. Note that the entry set may silently shrink, just
+ * like the WeakHashMap.
+ */
+ private class WeakEntrySet extends AbstractSet
+ {
+ /**
+ * Returns the size of this set.
+ */
+ public int size()
+ {
+ return size;
+ }
+
+ /**
+ * Returns an iterator for all entries.
+ */
+ public Iterator iterator()
+ {
+ return new Iterator()
+ {
+ /**
+ * The entry that was returned by the last
+ * <code>next()</code> call. This is also the entry whose
+ * bucket should be removed by the <code>remove</code> call. <br>
+ *
+ * It is null, if the <code>next</code> method wasn't
+ * called yet, or if the entry was already removed. <br>
+ *
+ * Remembering this entry here will also prevent it from
+ * being removed under us, since the entry strongly refers
+ * to the key.
+ */
+ WeakBucket.Entry lastEntry;
+
+ /**
+ * The entry that will be returned by the next
+ * <code>next()</code> call. It is <code>null</code> if there
+ * is no further entry. <br>
+ *
+ * Remembering this entry here will also prevent it from
+ * being removed under us, since the entry strongly refers
+ * to the key.
+ */
+ WeakBucket.Entry nextEntry = findNext(null);
+
+ /**
+ * The known number of modification to the list, if it differs
+ * from the real number, we through an exception.
+ */
+ int knownMod = modCount;
+
+ /**
+ * Check the known number of modification to the number of
+ * modifications of the table. If it differs from the real
+ * number, we throw an exception.
+ * @exception ConcurrentModificationException if the number
+ * of modifications doesn't match.
+ */
+ private void checkMod()
+ {
+ /* This method will get inlined */
+ if (knownMod != modCount)
+ throw new ConcurrentModificationException();
+ }
+
+ /**
+ * Get a strong reference to the next entry after
+ * lastBucket.
+ * @param lastBucket the previous bucket, or null if we should
+ * get the first entry.
+ * @return the next entry.
+ */
+ private WeakBucket.Entry findNext(WeakBucket.Entry lastEntry)
+ {
+ int slot;
+ WeakBucket nextBucket;
+ if (lastEntry != null)
+ {
+ nextBucket = lastEntry.getBucket().next;
+ slot = lastEntry.getBucket().slot;
+ }
+ else
+ {
+ nextBucket = buckets[0];
+ slot = 0;
+ }
+
+ while (true)
+ {
+ while (nextBucket != null)
+ {
+ WeakBucket.Entry entry = nextBucket.getEntry();
+ if (entry != null)
+ /* This is the next entry */
+ return entry;
+
+ /* entry was cleared, try next */
+ nextBucket = nextBucket.next;
+ }
+
+ slot++;
+ if (slot == buckets.length)
+ /* No more buckets, we are through */
+ return null;
+
+ nextBucket = buckets[slot];
+ }
+ }
+
+
+ /**
+ * Checks if there are more entries.
+ * @return true, iff there are more elements.
+ * @exception IllegalModificationException if the hash map was
+ * modified.
+ */
+ public boolean hasNext()
+ {
+ cleanQueue();
+ checkMod();
+ return (nextEntry != null);
+ }
+
+ /**
+ * Returns the next entry.
+ * @return the next entry.
+ * @exception IllegalModificationException if the hash map was
+ * modified.
+ * @exception NoSuchElementException if there is no entry.
+ */
+ public Object next()
+ {
+ cleanQueue();
+ checkMod();
+ if (nextEntry == null)
+ throw new NoSuchElementException();
+ lastEntry = nextEntry;
+ nextEntry = findNext(lastEntry);
+ return lastEntry;
+ }
+
+ /**
+ * Removes the last returned entry from this set. This will
+ * also remove the bucket of the underlying weak hash map.
+ * @exception IllegalModificationException if the hash map was
+ * modified.
+ * @exception IllegalStateException if <code>next()</code> was
+ * never called or the element was already removed.
+ */
+ public void remove()
+ {
+ cleanQueue();
+ checkMod();
+ if (lastEntry == null)
+ throw new IllegalStateException();
+ internalRemove(lastEntry.getBucket());
+ lastEntry = null;
+ modCount++;
+ knownMod = modCount;
+ }
+ };
+ }
+ }
+
+ /**
+ * A bucket is a weak reference to the key, that contains a strong
+ * reference to the value, a pointer to the next bucket and its slot
+ * number. <br>
+ *
+ * It would be cleaner to have a WeakReference as field, instead of
+ * extending it, but if a weak reference get cleared, we only get
+ * the weak reference (by queue.poll) and wouldn't know where to
+ * look for this reference in the hashtable, to remove that entry.
+ *
+ * @author Jochen Hoenicke
+ */
+ private static class WeakBucket extends WeakReference
+ {
+ /**
+ * The value of this entry. The key is stored in the weak
+ * reference that we extend.
+ */
+ Object value;
+
+ /**
+ * The next bucket describing another entry that uses the same
+ * slot.
+ */
+ WeakBucket next;
+
+ /**
+ * The slot of this entry. This should be
+ * <pre>
+ * Math.abs(key.hashCode() % buckets.length)
+ * </pre>
+ * But since the key may be silently removed we have to remember
+ * the slot number.
+ * If this bucket was removed the slot is -1. This marker will
+ * prevent the bucket from being removed twice.
+ */
+ int slot;
+
+ /**
+ * Creates a new bucket for the given key/value pair and the specified
+ * slot.
+ * @param key the key
+ * @param value the value
+ * @param slot the slot. This must match the slot where this bucket
+ * will be enqueued.
+ */
+ public WeakBucket(Object key, ReferenceQueue queue, Object value,
+ int slot)
+ {
+ super(key, queue);
+ this.value = value;
+ this.slot = slot;
+ }
+
+ /**
+ * This class gives the <code>Entry</code> representation of the
+ * current bucket. It also keeps a strong reference to the
+ * key; bad things may happen otherwise.
+ */
+ class Entry implements Map.Entry
+ {
+ /**
+ * The strong ref to the key.
+ */
+ Object key;
+
+ /**
+ * Creates a new entry for the key.
+ */
+ public Entry(Object key)
+ {
+ this.key = key;
+ }
+
+ /**
+ * Returns the underlying bucket.
+ */
+ public WeakBucket getBucket()
+ {
+ return WeakBucket.this;
+ }
+
+ /**
+ * Returns the key.
+ */
+ public Object getKey()
+ {
+ return key == NULL_KEY ? null : key;
+ }
+
+ /**
+ * Returns the value.
+ */
+ public Object getValue()
+ {
+ return value;
+ }
+
+ /**
+ * This changes the value. This change takes place in
+ * the underlying hash map.
+ */
+ public Object setValue(Object newVal)
+ {
+ Object oldVal = value;
+ value = newVal;
+ return oldVal;
+ }
+
+ /**
+ * The hashCode as specified in the Entry interface.
+ */
+ public int hashCode()
+ {
+ return (key == NULL_KEY ? 0 : key.hashCode())
+ ^ (value == null ? 0 : value.hashCode());
+ }
+
+ /**
+ * The equals method as specified in the Entry interface.
+ */
+ public boolean equals(Object o)
+ {
+ if (o instanceof Map.Entry)
+ {
+ Map.Entry e = (Map.Entry) o;
+ return (key == NULL_KEY
+ ? e.getKey() == null : key.equals(e.getKey()))
+ && (value == null
+ ? e.getValue() == null : value.equals(e.getValue()));
+ }
+ return false;
+ }
+ }
+
+ /**
+ * This returns the entry stored in this bucket, or null, if the
+ * bucket got cleared in the mean time.
+ */
+ Entry getEntry()
+ {
+ final Object key = this.get();
+ if (key == null)
+ return null;
+ return new Entry(key);
+ }
+ }
+
+ /**
+ * The entry set returned by <code>entrySet()</code>.
+ */
+ private WeakEntrySet theEntrySet;
+
+ /**
+ * The hash buckets. This are linked lists.
+ */
+ private WeakBucket[] buckets;
+
+ /**
+ * Creates a new weak hash map with default load factor and default
+ * capacity.
+ */
+ public WeakHashMap()
+ {
+ this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
+ }
+
+ /**
+ * Creates a new weak hash map with default load factor and the given
+ * capacity.
+ * @param initialCapacity the initial capacity
+ */
+ public WeakHashMap(int initialCapacity)
+ {
+ this(initialCapacity, DEFAULT_LOAD_FACTOR);
+ }
+
+ /**
+ * Creates a new weak hash map with the given initial capacity and
+ * load factor.
+ * @param initialCapacity the initial capacity.
+ * @param loadFactor the load factor (see class description of HashMap).
+ */
+ public WeakHashMap(int initialCapacity, float loadFactor)
+ {
+ if (initialCapacity < 0 || loadFactor <= 0 || loadFactor > 1)
+ throw new IllegalArgumentException();
+ this.loadFactor = loadFactor;
+ threshold = (int) (initialCapacity * loadFactor);
+ theEntrySet = new WeakEntrySet();
+ queue = new ReferenceQueue();
+ buckets = new WeakBucket[initialCapacity];
+ }
+
+ /**
+ * simply hashes a non-null Object to its array index
+ */
+ private int hash(Object key)
+ {
+ return Math.abs(key.hashCode() % buckets.length);
+ }
+
+ /**
+ * Cleans the reference queue. This will poll all references (which
+ * are WeakBuckets) from the queue and remove them from this map.
+ * This will not change modCount, even if it modifies the map. The
+ * iterators have to make sure that nothing bad happens. <br>
+ *
+ * Currently the iterator maintains a strong reference to the key, so
+ * that is no problem.
+ */
+ private void cleanQueue()
+ {
+ Object bucket = queue.poll();
+ while (bucket != null)
+ {
+ internalRemove((WeakBucket) bucket);
+ bucket = queue.poll();
+ }
+ }
+
+ /**
+ * Rehashes this hashtable. This will be called by the
+ * <code>add()</code> method if the size grows beyond the threshold.
+ * It will grow the bucket size at least by factor two and allocates
+ * new buckets.
+ */
+ private void rehash()
+ {
+ WeakBucket[] oldBuckets = buckets;
+ int newsize = buckets.length * 2 + 1; // XXX should be prime.
+ threshold = (int) (newsize * loadFactor);
+ buckets = new WeakBucket[newsize];
+
+ /* Now we have to insert the buckets again.
+ */
+ for (int i = 0; i < oldBuckets.length; i++)
+ {
+ WeakBucket bucket = oldBuckets[i];
+ WeakBucket nextBucket;
+ while (bucket != null)
+ {
+ nextBucket = bucket.next;
+
+ Object key = bucket.get();
+ if (key == null)
+ {
+ /* This bucket should be removed; it is probably
+ * already on the reference queue. We don't insert it
+ * at all, and mark it as cleared. */
+ bucket.slot = -1;
+ size--;
+ }
+ else
+ {
+ /* add this bucket to its new slot */
+ int slot = hash(key);
+ bucket.slot = slot;
+ bucket.next = buckets[slot];
+ buckets[slot] = bucket;
+ }
+ bucket = nextBucket;
+ }
+ }
+ }
+
+ /**
+ * Finds the entry corresponding to key. Since it returns an Entry
+ * it will also prevent the key from being removed under us.
+ * @param key the key. It may be null.
+ * @return The WeakBucket.Entry or null, if the key wasn't found.
+ */
+ private WeakBucket.Entry internalGet(Object key)
+ {
+ if (key == null)
+ key = NULL_KEY;
+ int slot = hash(key);
+ WeakBucket bucket = buckets[slot];
+ while (bucket != null)
+ {
+ WeakBucket.Entry entry = bucket.getEntry();
+ if (entry != null && key.equals(entry.key))
+ return entry;
+
+ bucket = bucket.next;
+ }
+ return null;
+ }
+
+ /**
+ * Adds a new key/value pair to the hash map.
+ * @param key the key. This mustn't exists in the map. It may be null.
+ * @param value the value.
+ */
+ private void internalAdd(Object key, Object value)
+ {
+ if (key == null)
+ key = NULL_KEY;
+ int slot = hash(key);
+ WeakBucket bucket = new WeakBucket(key, queue, value, slot);
+ bucket.next = buckets[slot];
+ buckets[slot] = bucket;
+ size++;
+ }
+
+ /**
+ * Removes a bucket from this hash map, if it wasn't removed before
+ * (e.g. one time through rehashing and one time through reference queue)
+ * @param bucket the bucket to remove.
+ */
+ private void internalRemove(WeakBucket bucket)
+ {
+ int slot = bucket.slot;
+ if (slot == -1)
+ /* this bucket was already removed. */
+ return;
+
+ /* mark the bucket as removed. This is necessary, since the
+ * bucket may be enqueued later by the garbage collection and
+ * internalRemove, will be called a second time.
+ */
+ bucket.slot = -1;
+ if (buckets[slot] == bucket)
+ buckets[slot] = bucket.next;
+ else
+ {
+ WeakBucket prev = buckets[slot];
+ /* This may throw a NullPointerException. It shouldn't but if
+ * a race condition occured (two threads removing the same
+ * bucket at the same time) it may happen. <br>
+ * But with race condition many much worse things may happen
+ * anyway.
+ */
+ while (prev.next != bucket)
+ prev = prev.next;
+ prev.next = bucket.next;
+ }
+ size--;
+ }
+
+ /**
+ * Returns the size of this hash map. Note that the size() may shrink
+ * spontanously, if the some of the keys were only weakly reachable.
+ * @return the number of entries in this hash map.
+ */
+ public int size()
+ {
+ cleanQueue();
+ return size;
+ }
+
+ /**
+ * Tells if the map is empty. Note that the result may change
+ * spontanously, if all of the keys were only weakly reachable.
+ * @return true, iff the map is empty.
+ */
+ public boolean isEmpty()
+ {
+ cleanQueue();
+ return size == 0;
+ }
+
+ /**
+ * Tells if the map contains the given key. Note that the result
+ * may change spontanously, if all the key was only weakly
+ * reachable.
+ * @return true, iff the map contains an entry for the given key.
+ */
+ public boolean containsKey(Object key)
+ {
+ cleanQueue();
+ return internalGet(key) != null;
+ }
+
+ /**
+ * Gets the value the key will be mapped to.
+ * @return the value the key was mapped to. It returns null if
+ * the key wasn't in this map, or if the mapped value was explicitly
+ * set to null.
+ */
+ public Object get(Object key)
+ {
+ cleanQueue();
+ WeakBucket.Entry entry = internalGet(key);
+ return entry == null ? null : entry.getValue();
+ }
+
+ /**
+ * Adds a new key/value mapping to this map.
+ * @param key the key. This may be null.
+ * @param value the value. This may be null.
+ * @return the value the key was mapped to previously. It returns
+ * null if the key wasn't in this map, or if the mapped value was
+ * explicitly set to null.
+ */
+ public Object put(Object key, Object value)
+ {
+ cleanQueue();
+ WeakBucket.Entry entry = internalGet(key);
+ if (entry != null)
+ return entry.setValue(value);
+
+ if (size >= threshold)
+ rehash();
+
+ internalAdd(key, value);
+ modCount++;
+ return null;
+ }
+
+ /**
+ * Removes the key and the corresponding value from this map.
+ * @param key the key. This may be null.
+ * @return the value the key was mapped to previously. It returns
+ * null if the key wasn't in this map, or if the mapped value was
+ * explicitly set to null. */
+ public Object remove(Object key)
+ {
+ cleanQueue();
+ WeakBucket.Entry entry = internalGet(key);
+ if (entry == null)
+ {
+ return null;
+ }
+ internalRemove(entry.getBucket());
+ modCount++;
+ return entry.getValue();
+ }
+
+ /**
+ * Returns a set representation of the entries in this map. This
+ * set will not have strong references to the keys, so they can be
+ * silently removed. The returned set has therefore the same
+ * strange behaviour (shrinking size(), disappearing entries) as
+ * this weak hash map.
+ * @return a set representation of the entries. */
+ public Set entrySet()
+ {
+ cleanQueue();
+ return theEntrySet;
+ }
+}