sup

commit cfeded5bc63b0de1ad75cefc648660c8fbc7a07d
parent 5c546294804c84062082d8c1a4f6311d56c028bb
Author: Edward Z. Yang <ezyang@MIT.EDU>
Date:   Thu, 20 Jan 2011 17:44:13 -0500

Avoid O(n^2) complexity for maildir deduplication.

Signed-off-by: Edward Z. Yang 

Diffstat:

1 file changed, 5 insertions(+), 3 deletions(-)
diff --git a/lib/sup/maildir.rb b/lib/sup/maildir.rb
@@ -119,14 +119,16 @@ class Maildir < Source
     ## deleted arrays, meaning that its flags changed or that it has
     ## been moved, these ids need to be removed from added and deleted
     add_to_delete = del_to_delete = []
+    map = Hash.new { |hash, key| hash[key] = [] }
+    deleted.each do |id_del|
+        map[maildir_data(id_del)[0]].push id_del
+    end
     added.each do |id_add|
-      deleted.each do |id_del|
-        if maildir_data(id_add)[0] == maildir_data(id_del)[0]
+        map[maildir_data(id_add)[0]].each do |id_del|
           updated.push [ id_del, id_add ]
           add_to_delete.push id_add
           del_to_delete.push id_del
         end
-      end
     end
     added -= add_to_delete
     deleted -= del_to_delete