Rationale for add-to-ordered-list

Rationale for add-to-ordered-list

[Kim F. Storm]

The following change:

2005-06-13  Kim F. Storm  <storm@cua.dk>

	* subr.el (add-to-ordered-list): New defun.

	* emulation/cua-base.el (cua-mode): Use add-to-ordered-list to
	add cua--keymap-alist to emulation-mode-map-alists.


was installed as a preparation for allowing cua-mode and viper-mode
to co-exist and co-operate seamlessly, when viper-mode has been
changed to use emulation-mode-map-alists.

The benefit of the change is that it becomes trivial to ensure that
the viper and cua entries in emulation-mode-map-alists are always in
the proper order (viper first), if future modes need to use the list
too.

The reason why at present only symbol elements can be ordered is a
practical one for the up-coming release -- it is sufficient for the
specific case of emulation-mode-map-alists.

A general solution is non-trivial, as there is a potential risk of memory
leaks, as associating ordering information with arbitrary lisp objects
means that we must store a pointer to such objects somewhere, and thus
may leave references to otherwise unused data.

So IMHO it was better to choose the trivial implementation now and
leave enhancements for after the release.

--
Kim F. Storm <storm@cua.dk> http://www.cua.dk

Re: Rationale for add-to-ordered-list

[Stefan Monnier]

> A general solution is non-trivial, as there is a potential risk of memory
> leaks, as associating ordering information with arbitrary lisp objects
> means that we must store a pointer to such objects somewhere, and thus
> may leave references to otherwise unused data.

How 'bout the patch below?  Look 'ma, no leak!


        Stefan


--- subr.el	14 jun 2005 13:16:55 -0400	1.464
+++ subr.el	14 jun 2005 13:23:20 -0400	
@@ -974,25 +974,21 @@
 `list-order' property.
 
 The return value is the new value of LIST-VAR."
-  (let* ((ordering (get list-var 'list-order))
-	 (cur (and (symbolp element) (assq element ordering))))
+  (let ((ordering (get list-var 'list-order)))
+    (unless ordering
+      (put list-var 'list-order
+           (setq ordering (make-hash-table :weakness 'key :test 'eq))))
     (when order
-      (unless (symbolp element)
-	(error "cannot specify order for non-symbols"))
-      (if cur
-	  (setcdr cur order)
-	(setq cur (cons element order))
-	(setq ordering (cons cur ordering))
-	(put list-var 'list-order ordering)))
+      (puthash element order ordering))
     (add-to-list list-var element)
     (set list-var (sort (symbol-value list-var)
 			(lambda (a b)
-			  (let ((oa (and (symbolp a) (assq a ordering)))
-				(ob (and (symbolp b) (assq b ordering))))
+			  (let ((oa (gethash a ordering))
+				(ob (gethash b ordering)))
 			    (cond
 			     ((not oa) nil)
 			     ((not ob) t)
-			     (t (< (cdr oa) (cdr ob))))))))))
+			     (t (< oa ob)))))))))
 
 \f
 ;;; Load history

Re: Rationale for add-to-ordered-list

[Kim F. Storm]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> A general solution is non-trivial, as there is a potential risk of memory
>> leaks, as associating ordering information with arbitrary lisp objects
>> means that we must store a pointer to such objects somewhere, and thus
>> may leave references to otherwise unused data.
>
> How 'bout the patch below?  Look 'ma, no leak!

Very clever -- I have to tune into weak hash tables more often :-)

I'm all for it.  Remember to update doc string and lispref too.

>
>
>         Stefan
>
>
> --- subr.el	14 jun 2005 13:16:55 -0400	1.464
> +++ subr.el	14 jun 2005 13:23:20 -0400	
> @@ -974,25 +974,21 @@
>  `list-order' property.
>  
>  The return value is the new value of LIST-VAR."
> -  (let* ((ordering (get list-var 'list-order))
> -	 (cur (and (symbolp element) (assq element ordering))))
> +  (let ((ordering (get list-var 'list-order)))
> +    (unless ordering
> +      (put list-var 'list-order
> +           (setq ordering (make-hash-table :weakness 'key :test 'eq))))
>      (when order
> -      (unless (symbolp element)
> -	(error "cannot specify order for non-symbols"))
> -      (if cur
> -	  (setcdr cur order)
> -	(setq cur (cons element order))
> -	(setq ordering (cons cur ordering))
> -	(put list-var 'list-order ordering)))
> +      (puthash element order ordering))
>      (add-to-list list-var element)
>      (set list-var (sort (symbol-value list-var)
>  			(lambda (a b)
> -			  (let ((oa (and (symbolp a) (assq a ordering)))
> -				(ob (and (symbolp b) (assq b ordering))))
> +			  (let ((oa (gethash a ordering))
> +				(ob (gethash b ordering)))
>  			    (cond
>  			     ((not oa) nil)
>  			     ((not ob) t)
> -			     (t (< (cdr oa) (cdr ob))))))))))
> +			     (t (< oa ob)))))))))
>  
>  \f
>  ;;; Load history
>
>

-- 
Kim F. Storm <storm@cua.dk> http://www.cua.dk