From 983a626beb91c9c7129d506f181b509b22c8e4b5 Mon Sep 17 00:00:00 2001
From: bdemsky <bdemsky>
Date: Fri, 3 Nov 2006 01:54:26 +0000
Subject: [PATCH] Add HashTable

---
 Robust/src/ClassLibrary/HashEntry.java |   6 ++
 Robust/src/ClassLibrary/HashMap.java   | 112 +++++++++++++++++++++++++
 Robust/src/ClassLibrary/Object.java    |   2 +-
 Robust/src/Main/Main.java              |   2 +
 Robust/src/Runtime/runtime.c           |   2 +-
 5 files changed, 122 insertions(+), 2 deletions(-)
 create mode 100644 Robust/src/ClassLibrary/HashEntry.java
 create mode 100644 Robust/src/ClassLibrary/HashMap.java

diff --git a/Robust/src/ClassLibrary/HashEntry.java b/Robust/src/ClassLibrary/HashEntry.java
new file mode 100644
index 00000000..904d16f4
--- /dev/null
+++ b/Robust/src/ClassLibrary/HashEntry.java
@@ -0,0 +1,6 @@
+class HashEntry {
+    public HashEntry() {}
+    Object key;
+    Object value;
+    HashEntry next;    
+}
diff --git a/Robust/src/ClassLibrary/HashMap.java b/Robust/src/ClassLibrary/HashMap.java
new file mode 100644
index 00000000..c814f6b5
--- /dev/null
+++ b/Robust/src/ClassLibrary/HashMap.java
@@ -0,0 +1,112 @@
+public class HashMap {
+    HashEntry[] table;
+    float loadFactor;
+    int numItems;
+
+    public HashMap() {
+	init(16, 0.75f);
+    }
+
+    public HashMap(int initialCapacity) {
+	init(initialCapacity, 0.75f);
+    }
+    
+    public HashMap(int initialCapacity, float loadFactor) {
+	init(initialCapacity, loadFactor);
+    }
+    
+    private void init(int initialCapacity, float loadFactor) {
+	table=new HashEntry[initialCapacity];
+	this.loadFactor=loadFactor;
+	this.numItems=0;
+    }
+
+    void resize() {
+	int newCapacity=2*table.length+1;
+	HashEntry[] newtable=new HashEntry[newCapacity];
+	for(int i=0;i<table.length;i++) {
+	    HashEntry e=table[i];
+	    while(e!=null) {
+		HashEntry next=e.next;
+		int bin=e.key.hashCode()%newCapacity;
+		e.next=newtable[bin];
+		newtable[bin]=e;
+		e=next;
+	    }
+	}
+	this.table=newtable;
+    }
+
+    public boolean isEmpty() {
+	return numItems==0;
+    }
+
+    public int size() {
+	return numItems;
+    }
+
+    Object remove(Object key) {
+	int bin=key.hashCode()%table.length;
+	HashEntry ptr=table[bin];
+	if (ptr.key==key) {
+	    table[bin]=ptr.next;
+	    numItems--;
+	    return ptr.value;
+	}
+	while(ptr.next!=null) {
+	    if (ptr.next.key==key) {
+		Object oldvalue=ptr.value;
+		ptr.next=ptr.next.next;
+		numItems--;
+		return oldvalue;
+	    }
+	}
+	return null;
+    }
+
+    Object get(Object key) {
+	int bin=key.hashCode()%table.length;
+	HashEntry ptr=table[bin];
+	while(ptr!=null) {
+	    if (ptr.key==key) {
+		return ptr.value;
+	    }
+	}
+	return null;
+    }
+
+    boolean containsKey(Object key) {
+	int bin=key.hashCode()%table.length;
+	HashEntry ptr=table[bin];
+	while(ptr!=null) {
+	    if (ptr.key==key) {
+		return true;
+	    }
+	}
+	return false;
+    }
+
+    Object put(Object key, Object value) {
+	numItems++;
+	if (numItems>(loadFactor*table.length)) {
+	    //Resize the table
+	    resize();
+	}
+	int bin=key.hashCode()%table.length;
+	HashEntry ptr=table[bin];
+	while(ptr!=null) {
+	    if (ptr.key==key) {
+		Object oldvalue=ptr.value;
+		ptr.value=value;
+		return oldvalue;
+	    }
+	}
+	HashEntry he=new HashEntry();
+	he.value=value;
+	he.key=key;
+	he.next=table[bin];
+	table[bin]=he;
+	return null;
+    }
+
+}
diff --git a/Robust/src/ClassLibrary/Object.java b/Robust/src/ClassLibrary/Object.java
index 1e66c956..0b0a4346 100644
--- a/Robust/src/ClassLibrary/Object.java
+++ b/Robust/src/ClassLibrary/Object.java
@@ -1,5 +1,5 @@
 public class Object {
-    public native int hashcode();
+    public native int hashCode();
 
     public String toString() {
 	return String.valueOf(this);
diff --git a/Robust/src/Main/Main.java b/Robust/src/Main/Main.java
index 8e7f8850..ec7687ad 100644
--- a/Robust/src/Main/Main.java
+++ b/Robust/src/Main/Main.java
@@ -55,6 +55,8 @@ public class Main {
       readSourceFile(state, ClassLibraryPrefix+"Object.java");
       readSourceFile(state, ClassLibraryPrefix+"System.java");
       readSourceFile(state, ClassLibraryPrefix+"String.java");
+      readSourceFile(state, ClassLibraryPrefix+"HashMap.java");
+      readSourceFile(state, ClassLibraryPrefix+"HashEntry.java");
       readSourceFile(state, ClassLibraryPrefix+"Integer.java");
       readSourceFile(state, ClassLibraryPrefix+"StringBuffer.java");
       readSourceFile(state, ClassLibraryPrefix+"FileInputStream.java");
diff --git a/Robust/src/Runtime/runtime.c b/Robust/src/Runtime/runtime.c
index 5d3e9b2a..816fa839 100644
--- a/Robust/src/Runtime/runtime.c
+++ b/Robust/src/Runtime/runtime.c
@@ -459,7 +459,7 @@ void injectinstructionfailure() {
 #endif
 }
 
-int ___Object______hashcode____(struct ___Object___ * ___this___) {
+int ___Object______hashCode____(struct ___Object___ * ___this___) {
   return (int) ___this___;
 }
 
-- 
2.34.1