[Truffle] Make the bucket chain singly linked.

jruby · Dec 16, 2014 · 35c1350 · 35c1350 · eregon · Dec 16, 2014
1 parent 18593e6
commit 35c1350
Show file tree

Hide file tree

Showing 5 changed files with 29 additions and 42 deletions.
diff --git a/core/src/main/java/org/jruby/truffle/nodes/core/HashNodes.java b/core/src/main/java/org/jruby/truffle/nodes/core/HashNodes.java
@@ -467,14 +467,10 @@ public Object delete(VirtualFrame frame, RubyHash hash, Object key) {
 
             // Remove from the lookup chain
 
-            if (bucket.getPreviousInLookup() == null) {
+            if (bucketSearchResult.getPreviousBucket() == null) {
                 ((Bucket[]) hash.getStore())[bucketSearchResult.getIndex()] = bucket.getNextInLookup();
             } else {
-                bucket.getPreviousInLookup().setNextInLookup(bucket.getNextInLookup());
-            }
-
-            if (bucket.getNextInLookup() != null) {
-                bucket.getNextInLookup().setPreviousInLookup(bucket.getPreviousInLookup());
+                bucketSearchResult.getPreviousBucket().setNextInLookup(bucket.getNextInLookup());
             }
 
             hash.setSize(hash.getSize() - 1);

diff --git a/core/src/main/java/org/jruby/truffle/nodes/hash/FindBucketNode.java b/core/src/main/java/org/jruby/truffle/nodes/hash/FindBucketNode.java
@@ -48,18 +48,18 @@ public BucketSearchResult search(VirtualFrame frame, RubyHash hash, Object key)
         final int bucketIndex = (hashed & HashOperations.SIGN_BIT_MASK) % buckets.length;
         Bucket bucket = buckets[bucketIndex];
 
-        Bucket endOfLookupChain = null;
+        Bucket previousBucket = null;
 
         while (bucket != null) {
             if (eqlNode.call(frame, key, "eql?", null, bucket.getKey())) {
-                return new BucketSearchResult(bucketIndex, bucket, bucket);
+                return new BucketSearchResult(bucketIndex, previousBucket, bucket);
             }
 
-            endOfLookupChain = bucket;
+            previousBucket = bucket;
             bucket = bucket.getNextInLookup();
         }
 
-        return new BucketSearchResult(bucketIndex, endOfLookupChain, null);
+        return new BucketSearchResult(bucketIndex, previousBucket, null);
     }
 
     @Override

diff --git a/core/src/main/java/org/jruby/truffle/runtime/hash/Bucket.java b/core/src/main/java/org/jruby/truffle/runtime/hash/Bucket.java
@@ -19,7 +19,6 @@ public class Bucket {
     private Object key;
     private Object value;
 
-    private Bucket previousInLookup;
     private Bucket nextInLookup;
 
     private Bucket previousInSequence;
@@ -46,14 +45,6 @@ public void setValue(Object value) {
         this.value = value;
     }
 
-    public Bucket getPreviousInLookup() {
-        return previousInLookup;
-    }
-
-    public void setPreviousInLookup(Bucket previousInLookup) {
-        this.previousInLookup = previousInLookup;
-    }
-
     public Bucket getNextInLookup() {
         return nextInLookup;
     }

diff --git a/core/src/main/java/org/jruby/truffle/runtime/hash/BucketSearchResult.java b/core/src/main/java/org/jruby/truffle/runtime/hash/BucketSearchResult.java
@@ -10,36 +10,37 @@
 package org.jruby.truffle.runtime.hash;
 
 /**
- * The result of looking for a bucket (a {@link Bucket}) in a Ruby hash. We get the last bucket in the lookup chain for
- * this index, the bucket that was found, and the index that was used. There are three possible outcomes for a search.
+ * The result of looking for a bucket (a {@link Bucket}) in a Ruby hash. We get the previous bucket in the lookup chain
+ * for this index until the bucket was found, the bucket that was found, and the index that was used. There are three
+ * possible outcomes for a search.
  * <ul>
  *     <li>There is nothing at that index, in which case the bucket and last bucket in the chain will be
  *     {@code null}</li>
- *     <li>There were buckets at that index, but none for our key, in which case the bucket will be null, but the last
- *     bucket will the last bucket in the chain at that index, presumably where we will want to insert your new
- *     bucket</li>
- *     <li>A bucket was found for our key, in which case the bucket and the last bucket in the chain will be the
- *     same</li>
+ *     <li>There were buckets at that index, but none for our key, in which case the bucket will be null, but the
+ *     previous bucket will be the last bucket in the chain at that index, presumably where we will want to insert our
+ *     new bucket</li>
+ *     <li>A bucket was found for our key, in which case the bucket will be the one correspond to the key, and the
+ *     previous bucket will be the one in the bucket chain before that one</li>
  * </ul>
  */
 public class BucketSearchResult {
 
-    private final Bucket endOfLookupChain;
+    private final Bucket previousBucket;
     private final Bucket bucket;
     private final int index;
 
-    public BucketSearchResult(int index, Bucket endOfLookupChain, Bucket bucket) {
+    public BucketSearchResult(int index, Bucket previousBucket, Bucket bucket) {
         this.index = index;
-        this.endOfLookupChain = endOfLookupChain;
+        this.previousBucket = previousBucket;
         this.bucket = bucket;
     }
 
     public int getIndex() {
         return index;
     }
 
-    public Bucket getEndOfLookupChain() {
-        return endOfLookupChain;
+    public Bucket getPreviousBucket() {
+        return previousBucket;
     }
 
     public Bucket getBucket() {

diff --git a/core/src/main/java/org/jruby/truffle/runtime/hash/HashOperations.java b/core/src/main/java/org/jruby/truffle/runtime/hash/HashOperations.java
@@ -139,26 +139,32 @@ public static BucketSearchResult verySlowFindBucket(RubyHash hash, Object key) {
         final int bucketIndex = (hashed & SIGN_BIT_MASK) % buckets.length;
         Bucket bucket = buckets[bucketIndex];
 
-        Bucket endOfLookupChain = null;
+        Bucket previousBucket = null;
 
         while (bucket != null) {
             // TODO: cast
 
             if ((boolean) DebugOperations.send(hash.getContext(), key, "eql?", null, bucket.getKey())) {
-                return new BucketSearchResult(bucketIndex, bucket, bucket);
+                return new BucketSearchResult(bucketIndex, previousBucket, bucket);
             }
 
-            endOfLookupChain = bucket;
+            previousBucket = bucket;
             bucket = bucket.getNextInLookup();
         }
 
-        return new BucketSearchResult(bucketIndex, endOfLookupChain, null);
+        return new BucketSearchResult(bucketIndex, previousBucket, null);
     }
 
     public static void setAtBucket(RubyHash hash, BucketSearchResult bucketSearchResult, Object key, Object value) {
         if (bucketSearchResult.getBucket() == null) {
             final Bucket bucket = new Bucket(key, value);
 
+            if (bucketSearchResult.getPreviousBucket() == null) {
+                ((Bucket[]) hash.getStore())[bucketSearchResult.getIndex()] = bucket;
+            } else {
+                bucketSearchResult.getPreviousBucket().setNextInLookup(bucket);
+            }
+
             if (hash.getFirstInSequence() == null) {
                 hash.setFirstInSequence(bucket);
                 hash.setLastInSequence(bucket);
@@ -167,13 +173,6 @@ public static void setAtBucket(RubyHash hash, BucketSearchResult bucketSearchRes
                 bucket.setPreviousInSequence(hash.getLastInSequence());
                 hash.setLastInSequence(bucket);
             }
-
-            if (bucketSearchResult.getEndOfLookupChain() == null) {
-                ((Bucket[]) hash.getStore())[bucketSearchResult.getIndex()] = bucket;
-            } else {
-                bucketSearchResult.getEndOfLookupChain().setNextInLookup(bucket);
-                bucket.setPreviousInLookup(bucketSearchResult.getEndOfLookupChain());
-            }
         } else {
             final Bucket bucket = bucketSearchResult.getBucket();