Function: rng-memo-map-add

rng-memo-map-add is a byte-compiled function defined in rng-match.el.gz.

Signature

(rng-memo-map-add KEY VALUE MM &optional WEAKNESS)

Documentation

Associate KEY with VALUE in memo-map MM and return the new memo-map.

The new memo-map may or may not be a different object from MM.

Alists are better for small maps. Hash tables are better for large maps. A memo-map therefore starts off as an alist and switches to a hash table for large memo-maps. A memo-map is always a list. An empty memo-map is represented by nil. A large memo-map is represented by a list containing just a hash-table. A small memo map is represented by a list whose cdr is an alist and whose car is the number of entries in the alist. The complete memo-map can be passed to assoc without problems: assoc ignores any members that are not cons cells. There is therefore minimal overhead in successful lookups on small lists
(which is the most common case).

Source Code

;; Defined in /usr/src/emacs/lisp/nxml/rng-match.el.gz
(defun rng-memo-map-add (key value mm &optional weakness)
  "Associate KEY with VALUE in memo-map MM and return the new memo-map.
The new memo-map may or may not be a different object from MM.

Alists are better for small maps.  Hash tables are better for large
maps.  A memo-map therefore starts off as an alist and switches to a
hash table for large memo-maps.  A memo-map is always a list.  An empty
memo-map is represented by nil.  A large memo-map is represented by a
list containing just a hash-table.  A small memo map is represented by
a list whose cdr is an alist and whose car is the number of entries in
the alist.  The complete memo-map can be passed to `assoc' without
problems: assoc ignores any members that are not cons cells.  There is
therefore minimal overhead in successful lookups on small lists
\(which is the most common case)."
  (if (null mm)
      (list 1 (cons key value))
    (let ((head (car mm)))
      (cond ((hash-table-p head)
	     (puthash key value head)
	     mm)
	    ((>= head rng-memo-map-alist-max)
	     (let ((ht (make-hash-table :test 'equal
					:weakness weakness
					:size (* 2 rng-memo-map-alist-max))))
	       (setq mm (cdr mm))
	       (while mm
		 (setq head (car mm))
		 (puthash (car head) (cdr head) ht)
		 (setq mm (cdr mm)))
	       (cons ht nil)))
	    (t (cons (1+ head)
		     (cons (cons key value)
			   (cdr mm))))))))