* lib/rinda/tuplespace.rb (Rinda::TupleBag): create index on tuple bag

	  by first column.



git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/branches/ruby_1_8@12416 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

1 files changed, 64 insertions, 24 deletions

diff --git a/lib/rinda/tuplespace.rb b/lib/rinda/tuplespace.rb
index d5042e00c6..21389abdeb 100644
--- a/lib/rinda/tuplespace.rb
+++ b/lib/rinda/tuplespace.rb
@@ -2,6 +2,8 @@ require 'monitor'
 require 'thread'
 require 'drb/drb'
 require 'rinda/rinda'
+require 'enumerator'
+require 'forwardable'
 
 module Rinda
 
@@ -286,50 +288,70 @@ module Rinda
   # of Tuplespace.
 
   class TupleBag
+    class TupleBin
+      extend Forwardable
+      def_delegators '@bin', :find_all, :delete_if, :each, :empty?
+
+      def initialize
+        @bin = []
+      end
+      
+      def add(tuple)
+        @bin.push(tuple)
+      end
+      
+      def delete(tuple)
+        idx = @bin.rindex(tuple)
+        @bin.delete_at(idx) if idx
+      end
+      
+      def find(&blk)
+        @bin.reverse_each do |x|
+          return x if yield(x)
+        end
+        nil
+      end
+    end
 
     def initialize # :nodoc:
       @hash = {}
+      @enum = Enumerable::Enumerator.new(self, :each_entry)
     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|
-          return true if tuple.expires
-        end
+      @enum.find do |tuple|
+        tuple.expires
       end
-      false
     end
 
     ##
     # Add +tuple+ to the TupleBag.
 
     def push(tuple)
-      size = tuple.size
-      @hash[size] ||= []
-      @hash[size].push(tuple)
+      key = bin_key(tuple)
+      @hash[key] ||= TupleBin.new
+      @hash[key].add(tuple)
     end
 
     ##
     # Removes +tuple+ from the TupleBag.
 
     def delete(tuple)
-      key = tuple.size
-      ary = @hash[key]
-      return unless ary
-      pos = ary.rindex(tuple)
-      return unless pos
-      ary.delete_at(pos)
-      @hash.delete(key) if ary.empty?
+      key = bin_key(tuple)
+      bin = @hash[key]
+      return nil unless bin
+      bin.delete(tuple)
+      @hash.delete(key) if bin.empty?
+      tuple
     end
 
     ##
     # Finds all live tuples that match +template+.
-
     def find_all(template)
-      @hash.fetch(template.size, []).find_all do |tuple|
+      bin_for_find(template).find_all do |tuple|
         tuple.alive? && template.match(tuple)
       end
     end
@@ -338,7 +360,7 @@ module Rinda
     # Finds a live tuple that matches +template+.
 
     def find(template)
-      @hash.fetch(template.size, []).find do |tuple|
+      bin_for_find(template).find do |tuple|
         tuple.alive? && template.match(tuple)
       end
     end
@@ -348,7 +370,7 @@ module Rinda
     # +tuple+ and are alive.
 
     def find_all_template(tuple)
-      @hash.fetch(tuple.size, []).find_all do |template|
+      @enum.find_all do |template|
         template.alive? && template.match(tuple)
       end
     end
@@ -359,20 +381,38 @@ module Rinda
 
     def delete_unless_alive
       deleted = []
-      @hash.keys.each do |size|
-        ary = []
-        @hash[size].each do |tuple|
+      @hash.each do |key, bin|
+        bin.delete_if do |tuple|
           if tuple.alive?
-            ary.push(tuple)
+            false
           else
             deleted.push(tuple)
+            true
           end
         end
-        @hash[size] = ary
       end
       deleted
     end
 
+    private
+    def each_entry(&blk)
+      @hash.each do |k, v|
+        v.each(&blk)
+      end
+    end
+
+    def bin_key(tuple)
+      head = tuple[0]
+      if head.class == Symbol
+        return head
+      else
+        false
+      end
+    end
+
+    def bin_for_find(template)
+      @hash.fetch(bin_key(template), @enum)
+    end
   end
 
   ##