Skip to content

Commit

Permalink
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Preserve order in ThreadGroup#list.
Browse files Browse the repository at this point in the history
This is a squashed commit of the following changes for #2221.

Thanks to @godfat for the work on this one.

commit 4bc9e8e
Author: Lin Jen-Shin <godfat@godfat.org>
Date:   Fri Dec 19 04:13:20 2014 +0800

    WeakIdentityLinkedHashMap: Properly set head.

commit fe56e69
Author: Lin Jen-Shin <godfat@godfat.org>
Date:   Fri Dec 19 02:10:43 2014 +0800

    Use WeakIdentityLinkedHashSet for RubyThreadGroup:

    We extend WeakIdentityHashMap for WeakIdentityLinkedHashMap, and use it
    for WeakIdentityLinkedHashSet. Sorry that this was a naive
    implementation and I didn't write any tests for this. Originally I want
    to do something like java.util.LinkedHashMap, but it seems
    WeakIdentityHashMap didn't implement every thing we need to do the same.
    Therefore I decided to just write what we need for RubyThreadGroup.
    We could complete this in the future.

    Note that this should also fix a bug where WeakIdentityHashMap#valueRemoved
    is not called properly.

commit e5bcad9
Author: Lin Jen-Shin <godfat@godfat.org>
Date:   Tue Nov 25 00:43:53 2014 +0800

    Use a ReferenceQueue to sweep dead references

commit 475746f
Author: Lin Jen-Shin <godfat@godfat.org>
Date:   Fri Nov 21 08:06:39 2014 +0800

    Preserve ThreadGroup#list order with ArrayList

    Because MRI uses a linked list which preserves the order of the threads.
    https://github.com/ruby/ruby/blob/2a754a733045da9965e88d1f31e650ea6b3f2b6c/vm_core.h#L973-L978
    This is useful to assume the first thread in the list is the root of a
    group, and saving values in the thread could be shared amongst the
    thread group. If we ever have thread group local variable, this is not
    really needed.
headius committed Dec 22, 2014
1 parent 4f21b1e commit a9fa229
Showing 3 changed files with 121 additions and 13 deletions.
15 changes: 7 additions & 8 deletions core/src/main/java/org/jruby/RubyThreadGroup.java
Original file line number Diff line number Diff line change
@@ -29,16 +29,17 @@
***** END LICENSE BLOCK *****/
package org.jruby;

import java.lang.ref.WeakReference;
import java.util.Collections;
import java.util.Set;
import org.jruby.anno.JRubyMethod;
import org.jruby.anno.JRubyClass;

import org.jruby.util.WeakIdentityLinkedHashSet;
import org.jruby.runtime.Block;
import org.jruby.runtime.ClassIndex;
import org.jruby.runtime.ObjectAllocator;
import org.jruby.runtime.builtin.IRubyObject;
import org.jruby.util.collections.WeakHashSet;

/**
* Implementation of Ruby's <code>ThreadGroup</code> class. This is currently
@@ -49,7 +50,7 @@
*/
@JRubyClass(name="ThreadGroup")
public class RubyThreadGroup extends RubyObject {
private final Set<RubyThread> rubyThreadList = Collections.synchronizedSet(new WeakHashSet<RubyThread>());
private final Set rubyThreadList = Collections.synchronizedSet(new WeakIdentityLinkedHashSet());
private boolean enclosed = false;

public static RubyClass createThreadGroupClass(Ruby runtime) {
@@ -145,11 +146,10 @@ public IRubyObject enclosed_p(Block block) {
@JRubyMethod
public IRubyObject list(Block block) {
RubyArray ary = RubyArray.newArray(getRuntime());
synchronized (ary) {
for (RubyThread thread : rubyThreadList) {
if (thread != null) {
ary.append(thread);
}
synchronized (ary) {
for (Object obj : rubyThreadList) {
RubyThread thread = (RubyThread) obj;
ary.add(thread);
}
return ary;
}
@@ -158,5 +158,4 @@ public IRubyObject list(Block block) {
private RubyThreadGroup(Ruby runtime, RubyClass type) {
super(runtime, type);
}

}
21 changes: 16 additions & 5 deletions core/src/main/java/org/jruby/util/WeakIdentityHashMap.java
Original file line number Diff line number Diff line change
@@ -151,7 +151,7 @@ private void clear(int size) {
table = new Entry[range];
}

private void expunge() {
protected void expunge() {
Entry e;
while ((e = (Entry) queue.poll()) != null) {
removeEntry(e);
@@ -219,13 +219,17 @@ private Object put(int hash, Object masked_key, Object value) {
idx = index(hash);
}

table[idx] = new Entry(hash, masked_key, value, table[idx], queue);
table[idx] = newEntry(hash, masked_key, value, table[idx], queue);

size += 1;

return null;
}

protected Entry newEntry(int hash, Object masked_key, Object value, Entry next, ReferenceQueue queue) {
return new Entry(hash, masked_key, value, next, queue);
}

public Object remove(Object key) {
key = maskKey(key);
int hash = keyHash(key);
@@ -242,6 +246,7 @@ public Object remove(int hash, Object key) {
if (entry.sameKey(hash, key)) {
table[idx] = entry.next;
size -= 1;
entryRemoved(entry);
return entry.getValue();

} else {
@@ -251,6 +256,7 @@ public Object remove(int hash, Object key) {
if (ahead.sameKey(hash, key)) {
entry.next = ahead.next;
size -= 1;
entryRemoved(ahead);
return ahead.getValue();
}

@@ -264,7 +270,7 @@ public Object remove(int hash, Object key) {
return null;
}

private void removeEntry(Entry ent) {
protected void removeEntry(Entry ent) {
int idx = index(ent.key_hash);

Entry entry = table[idx];
@@ -273,6 +279,7 @@ private void removeEntry(Entry ent) {
if (entry == ent) {
table[idx] = entry.next;
size -= 1;
entryRemoved(entry);
return;

} else {
@@ -282,6 +289,7 @@ private void removeEntry(Entry ent) {
if (ahead == ent) {
entry.next = ahead.next;
size -= 1;
entryRemoved(ahead);
return;
}

@@ -290,8 +298,11 @@ private void removeEntry(Entry ent) {
}
}
}

valueRemoved(ent.value);
}

// can be overridden to be informed when entries are removed
protected void entryRemoved(Entry entry) {
valueRemoved(entry.value);
}

// can be overridden to be informed when objects are removed
98 changes: 98 additions & 0 deletions core/src/main/java/org/jruby/util/WeakIdentityLinkedHashMap.java
Original file line number Diff line number Diff line change
@@ -0,0 +1,98 @@

package org.jruby.util;

import java.lang.ref.ReferenceQueue;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class WeakIdentityLinkedHashMap extends WeakIdentityHashMap {
public WeakIdentityLinkedHashMap() {
super();
}

public WeakIdentityLinkedHashMap(int size) {
super(size);
}

class Entry extends WeakIdentityHashMap.Entry {
Entry before, after;

Entry(int hash, Object masked_key, Object value, WeakIdentityHashMap.Entry next, ReferenceQueue queue, Entry tail) {
super(hash, masked_key, value, next, queue);
before = tail;
if (tail != null) {
tail.after = this;
}
}
}

// The head (eldest) of the doubly linked list.
transient Entry head;

// The tail (youngest) of the doubly linked list.
transient Entry tail;

@Override
public void clear() {
head = tail = null;
super.clear();
}

@Override
protected WeakIdentityHashMap.Entry newEntry(int hash, Object masked_key, Object value, WeakIdentityHashMap.Entry next, ReferenceQueue queue) {
Entry newTail = new Entry(hash, masked_key, value, next, queue, tail);
if (head == null) {
head = newTail;
}
tail = newTail;
return newTail;
}

@Override
protected void entryRemoved(WeakIdentityHashMap.Entry entry) {
Entry ent = (Entry) entry;
if (ent.before == null) {
head = ent.after;
}
else {
ent.before.after = ent.after;
}
super.entryRemoved(entry);
}

@Override
protected Iterator entryIterator() {
return new EntryIterator();
}

final class EntryIterator implements Iterator {
private Entry entry;

EntryIterator() {
expunge();
entry = head;
}

public boolean hasNext() {
return (entry != null);
}

public Object next() {
Object result = entry;

if (result == null) {
throw new NoSuchElementException();
} else {
entry = entry.after;
return result;
}
}

public void remove() {
Entry removed = entry;
expunge();
entry = entry.after;
WeakIdentityLinkedHashMap.this.removeEntry(removed);
}
}
}

0 comments on commit a9fa229

Please sign in to comment.