bug#4407: 23.1.50; Re: Recentf cleanup optmization

Dear Stefan, 

I've tried now to follow as strictly as possible the instruction from
info node "(emacs) Sending Patches".

* Explanation of change: function `recentf-cleanup' can be very slow
  when the recentf-max-saved-items is significant, e.g. 60 items. This
  is due to this that duplicate items are removed with a iterative
  search (which means that cleanup is made in quadratic time). The
  change consists in using a search based on a hash table, so that the
  cleanup is in linear time. Function impacted are function
  `recentf-cleanup' and a new function `recentf-string-key' is created.

* patch made with diff -c is attached. 
   file [d:/msys/temp/recentf.el	Fri Sep 11 19:41:51 2009] is download
   from CVS, and file [recentf.el	Wed Sep  2 16:34:04 2009] is the
   modified one.

In GNU Emacs 23.1.50.1 (i386-mingw-nt5.0.2195)
 of 2009-07-25 on COCOTTE
Windowing system distributor `Microsoft Corp.', version 5.0.2195
configured using `configure --with-gcc (3.4)'

Important settings:
  value of $LC_ALL: nil
  value of $LC_COLLATE: nil
  value of $LC_CTYPE: nil
  value of $LC_MESSAGES: nil
  value of $LC_MONETARY: nil
  value of $LC_NUMERIC: nil
  value of $LC_TIME: nil
  value of $LANG: FRA
  value of $XMODIFIERS: nil
  locale-coding-system: cp1252
  default-enable-multibyte-characters: t

Major mode: Info

Minor modes in effect:
  shell-dirtrack-mode: t
  recentf-mode: t
  mail-abbrevs-mode: t
  iswitchb-mode: t
  tooltip-mode: t
  mouse-wheel-mode: t
  menu-bar-mode: t
  file-name-shadow-mode: t
  global-font-lock-mode: t
  font-lock-mode: t
  blink-cursor-mode: t
  global-auto-composition-mode: t
  auto-composition-mode: t
  auto-encryption-mode: t
  auto-compression-mode: t
  line-number-mode: t
  transient-mark-mode: t

Recent input:
) <backspace> <backspace> ) M-q <down> <home> <C-right> 
<C-right> s <end> SPC o n SPC a SPC h a s h SPC t a 
b l e , s SPC o SPC <backspace> <backspace> <backspace> 
<backspace> SPC s o SPC t h <up> <up> <home> <down> 
<end> <down> a t SPC t h e SPC c l e a n u p SPC i 
s SPC i n SPC q u a d r a <backspace> <backspace> <backspace> 
<backspace> <backspace> <backspace> l i n e a r SPC 
t i m e . SPC F u n c t i o n SPC i m p a c t e d SPC 
a r e SPC f u n c t i o n <up> <up> <up> <up> <up> 
<C-left> <C-left> <C-left> <C-left> C-SPC <C-right> 
<C-right> <C-insert> <down> <down> <down> <down> <down> 
<end> SPC ` C-y SPC a n d SPC C-x o <down> <down> <down> 
<down> <down> <down> C-s C-s C-a <up> C-s c l e a n 
C-w C-s C-s C-s C-s C-s C-s C-s C-s C-s C-s <up> <up> 
<left> <C-left> <C-left> C-s C-w C-w C-s C-s C-s C-s 
<down> <down> <down> <down> <down> <down> <down> <down> 
<down> <down> <down> <down> <down> <down> <down> <down> 
<up> <up> <up> <right> <right> <right> <right> <right> 
C-SPC <C-right> <C-right> <C-right> <C-insert> C-x 
o a SPC n e w SPC f u n c t i o n SPC C-y <C-left> 
<C-left> <C-left> ` <end> ' SPC i s SPC c r e a t e 
d . <return> <return> C-x o C-x <kp-0> C-h i <down> 
<down> <down> <down> <down> <down> <down> <down> M-x 
b u g - r e p o r t <tab> <return> C-a M-d <delete> 
<end> <kp-subtract> b u g <tab> <tab> e m <tab> <r
eturn>

Recent messages:
Mark set [4 times]
Auto-saving...done
Mark set
Mark saved where search started
Auto-saving...done
Mark set [2 times]
Mark saved where search started [3 times]
Mark set [2 times]
Making completion list...
iswitchb-read-buffer: Command attempted to use minibuffer while in minibuffer

Load-path shadows:
d:/Programme/GNU/emacs-extension/cedet/common/ezimage hides d:/Programme/GNU/Emacs/lisp/ezimage
c:/Documents and Settings/Vincent/Application Data/.emacs.d/etc/custom hides d:/Programme/GNU/Emacs/lisp/custom

*** recentf.el	Wed Sep  2 16:34:04 2009
--- d:/msys/temp/recentf.el	Fri Sep 11 19:41:51 2009
***************
*** 310,322 ****
        (string-equal (downcase s1) (downcase s2))
      (string-equal s1 s2)))
  
- (defsubst recentf-string-key (s)
-   "Return a string that is used for `recentf-string-equal' or
- `recentf-string-lessp' comparisons. "
-   (if recentf-case-fold-search
-    (downcase s) s))
- 
- 
  (defsubst recentf-string-lessp (s1 s2)
    "Return non-nil if string S1 is less than S2 in lexicographic order.
  Ignore case if `recentf-case-fold-search' is non-nil."
--- 310,315 ----
***************
*** 1314,1334 ****
  That is, remove duplicates, non-kept, and excluded files."
    (interactive)
    (message "Cleaning up the recentf list...")
!   (let ((n 0) 
! 		newlist
! 		hk
! 		(ht (make-hash-table 
! 			 :size recentf-max-saved-items
! 			 :test 'equal)))
      (dolist (f recentf-list)
!       (setq f (recentf-expand-file-name f)
! 			hk (recentf-string-key f))
        (if (and (recentf-include-p f)
                 (recentf-keep-p f)
!                (not (gethash hk ht)))
! 		  (progn
! 			(push f newlist)
! 			(puthash hk t ht))
          (setq n (1+ n))
          (message "File %s removed from the recentf list" f)))
      (message "Cleaning up the recentf list...done (%d removed)" n)
--- 1307,1319 ----
  That is, remove duplicates, non-kept, and excluded files."
    (interactive)
    (message "Cleaning up the recentf list...")
!   (let ((n 0) newlist)
      (dolist (f recentf-list)
!       (setq f (recentf-expand-file-name f))
        (if (and (recentf-include-p f)
                 (recentf-keep-p f)
!                (not (recentf-string-member f newlist)))
!           (push f newlist)
          (setq n (1+ n))
          (message "File %s removed from the recentf list" f)))
      (message "Cleaning up the recentf list...done (%d removed)" n)