diff options
| -rw-r--r-- | ChangeLog | 5 | ||||
| -rw-r--r-- | lib/rinda/rinda.rb | 175 | ||||
| -rw-r--r-- | lib/rinda/ring.rb | 111 | ||||
| -rw-r--r-- | lib/rinda/tuplespace.rb | 249 |
4 files changed, 448 insertions, 92 deletions
@@ -1,3 +1,8 @@ +Tue Oct 25 00:35:33 2005 Masatoshi SEKI <m_seki@mva.biglobe.ne.jp> + + * lib/rinda/*: RDoc documentation from Eric Hodel + <drbrain@segment7.net> added. + Mon Oct 24 21:14:29 2005 Nobuyoshi Nakada <nobu@ruby-lang.org> * configure.in, io.c: use sys/syscall.h if syscall.h is not available. diff --git a/lib/rinda/rinda.rb b/lib/rinda/rinda.rb index 5af8ecb442..6c59e68654 100644 --- a/lib/rinda/rinda.rb +++ b/lib/rinda/rinda.rb @@ -1,100 +1,150 @@ +require 'drb/drb' +require 'thread' + +## +# A module to implement the Linda distributed computing paradigm in Ruby. # -# rinda.rb: A Ruby implementation of the Linda distributed computing paradigm. -# -# <i>Introduction to Linda/rinda?</i> +# Rinda is part of DRb (dRuby). # -# <i>Why is this library separate from <tt>drb</tt>?</i> +# == Example(s) # -# <i>Example(s)</i> +# See the sample/drb/ directory in the Ruby distribution, from 1.8.2 onwards. # -# (See the samples directory in the Ruby distribution, from 1.8.2 onwards.) +#-- +# TODO +# == Introduction to Linda/rinda? # +# == Why is this library separate from DRb? -require 'drb/drb' -require 'thread' - -# -# A module to implement the Linda programming paradigm in Ruby. -# This is part of +drb+ (dRuby). -# module Rinda + + ## + # Rinda error base class + class RindaError < RuntimeError; end + + ## + # Raised when a hash-based tuple has an invalid key. + class InvalidHashTupleKey < RindaError; end + + ## + # Raised when trying to use a canceled tuple. + class RequestCanceledError < ThreadError; end + + ## + # Raised when trying to use an expired tuple. + class RequestExpiredError < ThreadError; end - # + ## # A tuple is the elementary object in Rinda programming. # Tuples may be matched against templates if the tuple and # the template are the same size. - # + class Tuple - # Initialize a tuple with an Array or a Hash. + + ## + # Creates a new Tuple from +ary_or_hash+ which must be an Array or Hash. + def initialize(ary_or_hash) if hash?(ary_or_hash) - init_with_hash(ary_or_hash) + init_with_hash(ary_or_hash) else - init_with_ary(ary_or_hash) + init_with_ary(ary_or_hash) end end + ## # The number of elements in the tuple. + def size @tuple.size end + ## # Accessor method for elements of the tuple. + def [](k) @tuple[k] end + ## + # Fetches item +k+ from the tuple. + def fetch(k) @tuple.fetch(k) end + ## # Iterate through the tuple, yielding the index or key, and the # value, thus ensuring arrays are iterated similarly to hashes. + def each # FIXME if Hash === @tuple - @tuple.each { |k, v| yield(k, v) } + @tuple.each { |k, v| yield(k, v) } else - @tuple.each_with_index { |v, k| yield(k, v) } + @tuple.each_with_index { |v, k| yield(k, v) } end end - # Return the tuple itself -- i.e the Array or hash. + ## + # Return the tuple itself def value @tuple end private + def hash?(ary_or_hash) ary_or_hash.respond_to?(:keys) end - + + ## + # Munges +ary+ into a valid Tuple. + def init_with_ary(ary) @tuple = Array.new(ary.size) @tuple.size.times do |i| - @tuple[i] = ary[i] + @tuple[i] = ary[i] end end + ## + # Ensures +hash+ is a valid Tuple. + def init_with_hash(hash) @tuple = Hash.new hash.each do |k, v| raise InvalidHashTupleKey unless String === k - @tuple[k] = v + @tuple[k] = v end end + end - # + ## # Templates are used to match tuples in Rinda. - # + class Template < Tuple - # Perform the matching of a tuple against a template. An - # element with a +nil+ value in a template acts as a wildcard, - # matching any value in the corresponding position in the tuple. + + ## + # Matches this template against +tuple+. The +tuple+ must be the same + # size as the template. An element with a +nil+ value in a template acts + # as a wildcard, matching any value in the corresponding position in the + # tuple. Elements of the template match the +tuple+ if the are #== or + # #===. + # + # Template.new([:foo, 5]).match Tuple.new([:foo, 5]) # => true + # Template.new([:foo, nil]).match Tuple.new([:foo, 5]) # => true + # Template.new([String]).match Tuple.new(['hello']) # => true + # + # Template.new([:foo]).match Tuple.new([:foo, 5]) # => false + # Template.new([:foo, 6]).match Tuple.new([:foo, 5]) # => false + # Template.new([:foo, nil]).match Tuple.new([:foo]) # => false + # Template.new([:foo, 6]).match Tuple.new([:foo]) # => false + def match(tuple) return false unless tuple.respond_to?(:size) return false unless tuple.respond_to?(:fetch) @@ -105,84 +155,129 @@ module Rinda rescue return false end - next if v.nil? + next if v.nil? next if v == it next if v === it - return false + return false end return true end + ## # Alias for #match. + def ===(tuple) match(tuple) end + end - # + ## # <i>Documentation?</i> - # + class DRbObjectTemplate + + ## + # Creates a new DRbObjectTemplate that will match against +uri+ and +ref+. + def initialize(uri=nil, ref=nil) @drb_uri = uri @drb_ref = ref end + ## + # This DRbObjectTemplate matches +ro+ if the remote object's drburi and + # drbref are the same. +nil+ is used as a wildcard. + def ===(ro) return true if super(ro) unless @drb_uri.nil? - return false unless (@drb_uri === ro.__drburi rescue false) + return false unless (@drb_uri === ro.__drburi rescue false) end unless @drb_ref.nil? - return false unless (@drb_ref === ro.__drbref rescue false) + return false unless (@drb_ref === ro.__drbref rescue false) end true end + end - # + ## # TupleSpaceProxy allows a remote Tuplespace to appear as local. - # + class TupleSpaceProxy + + ## + # Creates a new TupleSpaceProxy to wrap +ts+. + def initialize(ts) @ts = ts end + ## + # Adds +tuple+ to the proxied TupleSpace. See TupleSpace#write. + def write(tuple, sec=nil) @ts.write(tuple, sec) end + ## + # Takes +tuple+ from the proxied TupleSpace. See TupleSpace#take. + def take(tuple, sec=nil, &block) port = [] @ts.move(DRbObject.new(port), tuple, sec, &block) port[0] end + ## + # Reads +tuple+ from the proxied TupleSpace. See TupleSpace#read. + def read(tuple, sec=nil, &block) @ts.read(tuple, sec, &block) end + ## + # Reads all tuples matching +tuple+ from the proxied TupleSpace. See + # TupleSpace#read_all. + def read_all(tuple) @ts.read_all(tuple) end + ## + # Registers for notifications of event +ev+ on the proxied TupleSpace. + # See TupleSpace#notify + def notify(ev, tuple, sec=nil) @ts.notify(ev, tuple, sec) end + end - # - # <i>Documentation?</i> - # + ## + # An SimpleRenewer allows a TupleSpace to check if a TupleEntry is still + # alive. + class SimpleRenewer + include DRbUndumped + + ## + # Creates a new SimpleRenewer that keeps an object alive for another +sec+ + # seconds. + def initialize(sec=180) @sec = sec end + ## + # Called by the TupleSpace to check if the object is still alive. + def renew @sec end end + end diff --git a/lib/rinda/ring.rb b/lib/rinda/ring.rb index bc952032e9..5b2d412451 100644 --- a/lib/rinda/ring.rb +++ b/lib/rinda/ring.rb @@ -6,10 +6,29 @@ require 'rinda/rinda' require 'thread' module Rinda + + ## + # The default port Ring discovery will use. + Ring_PORT = 7647 + + ## + # A RingServer allows a Rinda::TupleSpace to be located via UDP broadcasts. + # Service location uses the following steps: + # + # 1. A RingServer begins listening on the broadcast UDP address. + # 2. A RingFinger sends a UDP packet containing the DRb URI where it will + # listen for a reply. + # 3. The RingServer recieves the UDP packet and connects back to the + # provided DRb URI with the DRb service. + class RingServer + include DRbUndumped + ## + # Advertises +ts+ on the UDP broadcast address at +port+. + def initialize(ts, port=Ring_PORT) @ts = ts @soc = UDPSocket.open @@ -18,6 +37,10 @@ module Rinda @r_service = reply_service end + ## + # Creates a thread that picks up UDP packets and passes them to do_write + # for decoding. + def write_service Thread.new do loop do @@ -27,6 +50,10 @@ module Rinda end end + ## + # Extracts the response URI from +msg+ and adds it to TupleSpace where it + # will be picked up by +reply_service+ for notification. + def do_write(msg) Thread.new do begin @@ -37,6 +64,9 @@ module Rinda end end + ## + # Creates a thread that notifies waiting clients from the TupleSpace. + def reply_service Thread.new do loop do @@ -45,15 +75,34 @@ module Rinda end end + ## + # Pulls lookup tuples out of the TupleSpace and sends their DRb object the + # address of the local TupleSpace. + def do_reply tuple = @ts.take([:lookup_ring, DRbObject]) Thread.new { tuple[1].call(@ts) rescue nil} rescue end + end + ## + # RingFinger is used by RingServer clients to discover the RingServer's + # TupleSpace. Typically, all a client needs to do is call + # RingFinger.primary to retrieve the remote TupleSpace, which it can then + # begin using. + class RingFinger + + @@broadcast_list = ['<broadcast>', 'localhost'] + @@finger = nil + + ## + # Creates a singleton RingFinger and looks for a RingServer. Returns the + # created RingFinger. + def self.finger unless @@finger @@finger = self.new @@ -62,27 +111,56 @@ module Rinda @@finger end + ## + # Returns the first advertised TupleSpace. + def self.primary finger.primary end + ## + # Contains all discoverd TupleSpaces except for the primary. + def self.to_a finger.to_a end - @@broadcast_list = ['<broadcast>', 'localhost'] + ## + # The list of addresses where RingFinger will send query packets. + + attr_accessor :broadcast_list + + ## + # The port that RingFinger will send query packets to. + + attr_accessor :port + + ## + # Contain the first advertised TupleSpace after lookup_ring_any is called. + + attr_accessor :primary + + ## + # Creates a new RingFinger that will look for RingServers at +port+ on + # the addresses in +broadcast_list+. + def initialize(broadcast_list=@@broadcast_list, port=Ring_PORT) @broadcast_list = broadcast_list || ['localhost'] @port = port @primary = nil @rings = [] end - attr_accessor :broadcast_list, :port, :primary + + ## + # Contains all discovered TupleSpaces except for the primary. def to_a @rings end + ## + # Iterates over all discovered TupleSpaces starting with the primary. + def each lookup_ring_any unless @primary return unless @primary @@ -90,6 +168,11 @@ module Rinda @rings.each { |x| yield(x) } end + ## + # Looks up RingServers waiting +timeout+ seconds. RingServers will be + # given +block+ as a callback, which will be called with the remote + # TupleSpace. + def lookup_ring(timeout=5, &block) return lookup_ring_any(timeout) unless block_given? @@ -108,6 +191,10 @@ module Rinda sleep(timeout) end + ## + # Returns the first found remote TupleSpace. Any further recovered + # TupleSpaces can be found by calling +to_a+. + def lookup_ring_any(timeout=5) queue = Queue.new @@ -125,19 +212,38 @@ module Rinda raise('RingNotFound') if @primary.nil? @primary end + end + ## + # RingProvider uses a RingServer advertised TupleSpace as a name service. + # TupleSpace clients can register themselves with the remote TupleSpace and + # look up other provided services via the remote TupleSpace. + # + # Services are registered with a tuple of the format [:name, klass, + # DRbObject, description]. + class RingProvider + + ## + # Creates a RingProvider that will provide a +klass+ service running on + # +front+, with a +description+. +renewer+ is optional. + def initialize(klass, front, desc, renewer = nil) @tuple = [:name, klass, front, desc] @renewer = renewer || Rinda::SimpleRenewer.new end + ## + # Advertises this service on the primary remote TupleSpace. + def provide ts = Rinda::RingFinger.primary ts.write(@tuple, @renewer) end + end + end if __FILE__ == $0 @@ -162,3 +268,4 @@ if __FILE__ == $0 end end end + diff --git a/lib/rinda/tuplespace.rb b/lib/rinda/tuplespace.rb index 67917f99ea..73e79bb401 100644 --- a/lib/rinda/tuplespace.rb +++ b/lib/rinda/tuplespace.rb @@ -1,47 +1,66 @@ -# -# = tuplespace: <i>???</i> -# -# <i>Overview of rinda/tuplespace.rb</i> -# -# <i>Example(s)</i> -# - require 'monitor' require 'thread' require 'drb/drb' require 'rinda/rinda' module Rinda - # + + ## # A TupleEntry is a Tuple (i.e. a possible entry in some Tuplespace) # together with expiry and cancellation data. - # + class TupleEntry + include DRbUndumped + attr_accessor :expires + + ## + # Creates a TupleEntry based on +ary+ with an optional renewer or expiry + # time +sec+. + # + # A renewer must implement the +renew+ method which returns a Numeric, + # nil, or true to indicate when the tuple has expired. + def initialize(ary, sec=nil) @cancel = false + @expires = nil @tuple = make_tuple(ary) @renewer = nil renew(sec) end - attr_accessor :expires + + ## + # Marks this TupleEntry as canceled. def cancel @cancel = true end + ## + # A TupleEntry is dead when it is canceled or expired. + def alive? !canceled? && !expired? end + ## # Return the object which makes up the tuple itself: the Array # or Hash. + def value; @tuple.value; end + ## + # Returns the canceled status. + def canceled?; @cancel; end + ## # Has this tuple expired? (true/false). + # + # A tuple has expired when its expiry timer based on the +sec+ argument to + # #initialize runs out. + def expired? return true unless @expires return false if @expires > Time.now @@ -51,8 +70,8 @@ module Rinda return @expires < Time.now end - # Reset the expiry data according to the supplied argument. If - # the argument is: + ## + # Reset the expiry time according to +sec_or_renewer+. # # +nil+:: it is set to expire in the far future. # +false+:: it has expired. @@ -60,19 +79,19 @@ module Rinda # # Otherwise the argument refers to some kind of renewer object # which will reset its expiry time. + def renew(sec_or_renewer) sec, @renewer = get_renewer(sec_or_renewer) @expires = make_expires(sec) end - # Create an expiry time. Called with: - # - # +true+:: the expiry time is the start of 1970 (i.e. expired). - # +nil+:: it is Tue Jan 19 03:14:07 GMT Standard Time 2038 (i.e. when - # UNIX clocks will die) - # - # otherwise it is +sec+ seconds into the - # future. + ## + # Returns an expiry Time based on +sec+ which can be one of: + # Numeric:: +sec+ seconds into the future + # +true+:: the expiry time is the start of 1970 (i.e. expired) + # +nil+:: it is Tue Jan 19 03:14:07 GMT Standard Time 2038 (i.e. when + # UNIX clocks will die) + def make_expires(sec=nil) case sec when Numeric @@ -84,29 +103,43 @@ module Rinda end end - # Accessor method for the tuple. + ## + # Retrieves +key+ from the tuple. + def [](key) @tuple[key] end + ## + # Fetches +key+ from the tuple. + def fetch(key) @tuple.fetch(key) end + ## # The size of the tuple. + def size @tuple.size end - # Create a new tuple from the supplied object (array-like). + ## + # Creates a Rinda::Tuple for +ary+. + def make_tuple(ary) Rinda::Tuple.new(ary) end private - # Given +true+, +nil+, or +Numeric+, returns that (suitable input to - # make_expires) and +nil+ (no actual +renewer+), else it return the - # time data from the supplied +renewer+. + + ## + # Returns a valid argument to make_expires and the renewer or nil. + # + # Given +true+, +nil+, or Numeric, returns that value and +nil+ (no actual + # renewer). Otherwise it returns an expiry value from calling +it.renew+ + # and the renewer. + def get_renewer(it) case it when Numeric, true, nil @@ -119,35 +152,42 @@ module Rinda end end end + end - # - # The same as a TupleEntry but with methods to do matching. - # + ## + # A TemplateEntry is a Template together with expiry and cancellation data. + class TemplateEntry < TupleEntry + ## + # Matches this TemplateEntry against +tuple+. See Template#match for + # details on how a Template matches a Tuple. + def match(tuple) @tuple.match(tuple) end alias === match - # Create a new Template from the supplied object. - def make_tuple(ary) + def make_tuple(ary) # :nodoc: Rinda::Template.new(ary) end + end - # + ## # <i>Documentation?</i> - # + class WaitTemplateEntry < TemplateEntry + + attr_reader :found + def initialize(place, ary, expires=nil) super(ary, expires) @place = place @cond = place.new_cond @found = nil end - attr_reader :found def cancel super @@ -168,12 +208,39 @@ module Rinda @cond.signal end end + end + ## + # A NotifyTemplateEntry is returned by TupleSpace#notify and is notified of + # TupleSpace changes. You may receive either your subscribed event or the + # 'close' event when iterating over notifications. # - # <i>Documentation?</i> + # See TupleSpace#notify_event for valid notification types. + # + # == Example + # + # ts = Rinda::TupleSpace.new + # observer = ts.notify 'write', [nil] + # + # Thread.start do + # observer.each { |t| p t } + # end + # + # 3.times { |i| ts.write [i] } # + # Outputs: + # + # ['write', [0]] + # ['write', [1]] + # ['write', [2]] + class NotifyTemplateEntry < TemplateEntry + + ## + # Creates a new NotifyTemplateEntry that watches +place+ for +event+s that + # match +tuple+. + def initialize(place, event, tuple, expires=nil) ary = [event, Rinda::Template.new(tuple)] super(ary, expires) @@ -181,10 +248,17 @@ module Rinda @done = false end + ## + # Called by TupleSpace to notify this NotifyTemplateEntry of a new event. + def notify(ev) @queue.push(ev) end + ## + # Retrieves a notification. Raises RequestExpiredError when this + # NotifyTemplateEntry expires. + def pop raise RequestExpiredError if @done it = @queue.pop @@ -192,7 +266,10 @@ module Rinda return it end - def each + ## + # Yields event/tuple pairs until this NotifyTemplateEntry expires. + + def each # :yields: event, tuple while !@done it = pop yield(it) @@ -201,17 +278,22 @@ module Rinda ensure cancel end + end - # + ## # TupleBag is an unordered collection of tuples. It is the basis # of Tuplespace. - # + class TupleBag - def initialize + + def initialize # :nodoc: @hash = {} end + ## + # +true+ if the TupleBag to see if it has any expired entries. + def has_expires? @hash.each do |k, v| v.each do |tuple| @@ -221,43 +303,55 @@ module Rinda false end - # Add the object to the TupleBag. + ## + # Add +ary+ to the TupleBag. + def push(ary) size = ary.size @hash[size] ||= [] @hash[size].push(ary) end - # Remove the object from the TupleBag. + ## + # Removes +ary+ from the TupleBag. + def delete(ary) size = ary.size @hash.fetch(size, []).delete(ary) end - # Finds all tuples that match the template and are alive. + ## + # Finds all live tuples that match +template+. + def find_all(template) @hash.fetch(template.size, []).find_all do |tuple| tuple.alive? && template.match(tuple) end end - # Finds a template that matches and is alive. + ## + # Finds a live tuple that matches +template+. + def find(template) @hash.fetch(template.size, []).find do |tuple| tuple.alive? && template.match(tuple) end end - # Finds all tuples in the TupleBag which when treated as - # templates, match the supplied tuple and are alive. + ## + # Finds all tuples in the TupleBag which when treated as templates, match + # +tuple+ and are alive. + def find_all_template(tuple) @hash.fetch(tuple.size, []).find_all do |template| template.alive? && template.match(tuple) end end - # Delete tuples which are not alive from the TupleBag. Returns - # the list of tuples so deleted. + ## + # Delete tuples which dead tuples from the TupleBag, returning the deleted + # tuples. + def delete_unless_alive deleted = [] @hash.keys.each do |size| @@ -273,15 +367,28 @@ module Rinda end deleted end + end - # + ## # The Tuplespace manages access to the tuples it contains, # ensuring mutual exclusion requirements are met. # + # The +sec+ option for the write, take, move, read and notify methods may + # either be a number of seconds or a Renewer object. + class TupleSpace + include DRbUndumped include MonitorMixin + + ## + # Creates a new TupleSpace. +period+ is used to control how often to look + # for dead tuples after modifications to the TupleSpace. + # + # If no dead tuples are found +period+ seconds after the last + # modification, the TupleSpace will stop looking for dead tuples. + def initialize(period=60) super() @bag = TupleBag.new @@ -292,7 +399,9 @@ module Rinda @keeper = nil end - # Put a tuple into the tuplespace. + ## + # Adds +tuple+ + def write(tuple, sec=nil) entry = TupleEntry.new(tuple, sec) start_keeper @@ -317,11 +426,16 @@ module Rinda entry end - # Remove an entry from the Tuplespace. + ## + # Removes +tuple+ + def take(tuple, sec=nil, &block) move(nil, tuple, sec, &block) end + ## + # Moves +tuple+ to +port+. + def move(port, tuple, sec=nil) template = WaitTemplateEntry.new(self, tuple, sec) yield(template) if block_given? @@ -356,6 +470,9 @@ module Rinda end end + ## + # Reads +tuple+, but does not remove it. + def read(tuple, sec=nil) template = WaitTemplateEntry.new(self, tuple, sec) yield(template) if block_given? @@ -377,6 +494,9 @@ module Rinda end end + ## + # Returns all tuples matching +tuple+. Does not remove the found tuples. + def read_all(tuple) template = WaitTemplateEntry.new(self, tuple, nil) synchronize do @@ -387,6 +507,18 @@ module Rinda end end + ## + # Registers for notifications of +event+. Returns a NotifyTemplateEntry. + # See NotifyTemplateEntry for examples of how to listen for notifications. + # + # +event+ can be: + # 'write':: A tuple was added + # 'take':: A tuple was taken or moved + # 'delete':: A tuple was lost after being overwritten or expiring + # + # The TupleSpace will also notify you of the 'close' event when the + # NotifyTemplateEntry has expired. + def notify(event, tuple, sec=nil) template = NotifyTemplateEntry.new(self, event, tuple, sec) synchronize do @@ -396,6 +528,10 @@ module Rinda end private + + ## + # Removes dead tuples. + def keep_clean synchronize do @read_waiter.delete_unless_alive.each do |e| @@ -413,6 +549,10 @@ module Rinda end end + ## + # Notifies all registered listeners for +event+ of a status change of + # +tuple+. + def notify_event(event, tuple) ev = [event, tuple] @notify_waiter.find_all_template(ev).each do |template| @@ -420,6 +560,9 @@ module Rinda end end + ## + # Creates a thread that scans the tuplespace for expired tuples. + def start_keeper return if @keeper && @keeper.alive? @keeper = Thread.new do @@ -430,11 +573,17 @@ module Rinda end end + ## + # Checks the tuplespace to see if it needs cleaning. + def need_keeper? return true if @bag.has_expires? return true if @read_waiter.has_expires? return true if @take_waiter.has_expires? return true if @notify_waiter.has_expires? end + end + end + |