Synchronous Cycle Collectionの適当なRuby実装

元の論文はこれです。
Concurrent Cycle Collection in Reference Counted Systems

http://www.research.ibm.com/people/d/dfb/papers/Bacon01Concurrent.pdf

この中の、Fig. 2. Synchronous Cycle Collectionを丸写してクラスメソッドにしました。
以下ソースです。

require 'set'

class S
	attr_accessor :color, :buffered, :rc, :children

	def initialize(data)
		@rc = 0
		@children = Hash.new
		@color = :black
		@buffered = false
		@data = data
		@@roots = Set.new
		print "new("+@data+")\n"
	end

	def delete()
		print "delete("+@data+")\n"
	end

	def []=(i, o)
		if (@children.key?(i))
			self.class.decrement(@children[i])
		end

		if (o == nil)
			@children.delete(i)
		else
			@children[i] = o
			self.class.increment(o)
		end
	end

	def [](i)
		@children[i]
	end

	def self.increment(s)
		s.rc = s.rc + 1
		s.color = :black
	end

	def self.decrement(s)
		s.rc = s.rc - 1
		if (s.rc == 0)
			release(s)
		else
			possibleRoot(s)
		end
	end

	def self.release(s)
		s.children.each do |k,t|
			decrement(t)
		end
		s.color = :black
		if (!s.buffered)
			 s.delete
		end
	end

	def self.possibleRoot(s)
		if (s.color != :purple)
			s.color = :purple
			if (!s.buffered)
				s.buffered = true
				@@roots.add(s)
			end
		end
	end

	def self.collectCycles()
		markRoots()
		scanRoots()
		collectRoots()
	end

	def self.markRoots()
		@@roots.each do |s|
			if (s.color == :purple)
				markGray(s)
			else
				s.buffered = false
				@@roots.delete(s)
				if (s.color == :black && s.rc == 0)
					s.delete
				end
			end
		end
	end

	def self.scanRoots()
		@@roots.each do |s|
			scan(s)
		end
	end

	def self.collectRoots()
		@@roots.each do |s|
			s.buffered = false
			collectWhite(s)
		end
		@@roots.clear
	end

	def self.markGray(s)
		if (s.color != :gray)
			s.color = :gray
			s.children.each do |k,t|
				t.rc = t.rc - 1
				markGray(t)
			end
		end
	end

	def self.scan(s)
		if (s.color == :gray)
			if (s.rc > 0)
				scanBlack(s)
			else
				s.color = :white
				s.children.each do |k,t|
					scan(t)
				end
			end
		end
	end

	def self.scanBlack(s)
		s.color = :black
		s.children.each do |k,t|
			t.rc = t.rc + 1
			if (t.color != :black)
				scanBlack(t)
			end
		end
	end

	def self.collectWhite(s)
		if (s.color == :white && !s.buffered)
			s.color = :black
			s.children.each do |k,t|
				collectWhite(t)
			end
			s.delete
		end

	end

end

def main()
	t = S.new("root")
	S.increment(t)

	t[:a] = S.new("a")
	t[:b] = S.new("b")
	print("delete root\n")
	t[:a] = nil
	t[:b] = nil
	print("ok\n")
	print("increment root 2\n")
	t[:a] = S.new("d")
	t[:a][:a] = S.new("e")
	t[:a][:a][:a] = S.new("f")
	print("--\n")
	print("increment root 3\n")
	t[:b] = S.new("g")
	t[:b][:a] = S.new("h")
	t[:b][:a][:a] = t[:b]
	print("make cycle ref\n")
	t[:b] = nil
	print("collect\n")
	S.collectCycles()

	print("delete root\n")
	S.decrement(t)
end

main