Skip to content

Commit

Permalink
Browse files Browse the repository at this point in the history
Preserve order in ThreadGroup#list.
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.
  • Loading branch information
headius committed Dec 22, 2014
1 parent 4f21b1e commit a9fa229
Show file tree
Hide file tree
Showing 3 changed files with 121 additions and 13 deletions.
15 changes: 7 additions & 8 deletions core/src/main/java/org/jruby/RubyThreadGroup.java
Expand Up @@ -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
Expand All @@ -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) {
Expand Down Expand Up @@ -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;
}
Expand All @@ -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
Expand Up @@ -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);
Expand Down Expand Up @@ -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);
Expand All @@ -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 {
Expand All @@ -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();
}

Expand All @@ -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];
Expand All @@ -273,6 +279,7 @@ private void removeEntry(Entry ent) {
if (entry == ent) {
table[idx] = entry.next;
size -= 1;
entryRemoved(entry);
return;

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

Expand All @@ -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
Expand Down
98 changes: 98 additions & 0 deletions core/src/main/java/org/jruby/util/WeakIdentityLinkedHashMap.java
@@ -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.