1 (defun riece-lru-make-node (key value &optional previous next)
2 "Make riece-lru-node object."
3 (vector key value previous next))
5 (defun riece-lru-node-key (node)
9 (defun riece-lru-node-value (node)
10 "Return value of NODE."
13 (defun riece-lru-node-next (node)
14 "Return next of NODE."
17 (defun riece-lru-node-set-next (node next)
18 "Set next of NODE to NEXT."
21 (defun riece-lru-node-previous (node)
22 "Return previous of NODE."
25 (defun riece-lru-node-set-previous (node previous)
26 "Set previous of NODE to PREVIOUS."
27 (aset node 2 previous))
29 (defun riece-lru-make-map (max-length)
30 "Make riece-lru-map object."
31 (vector max-length (make-vector (* max-length 2) 0) 0 nil nil))
33 (defun riece-lru-map-max-length (map)
34 "Return max-length of MAP."
37 (defun riece-lru-map-hash-obarray (map)
38 "Return hash-obarray of MAP."
41 (defun riece-lru-map-hash-length (map)
42 "Return hash-length of MAP."
45 (defun riece-lru-map-set-hash-length (map hash-length)
46 "Set hash-length of MAP to HASH-LENGTH."
47 (aset map 2 hash-length))
49 (defun riece-lru-map-first (map)
50 "Return first of MAP."
53 (defun riece-lru-map-set-first (map first)
54 "Set first of MAP to FIRST."
57 (defun riece-lru-map-last (map)
61 (defun riece-lru-map-set-last (map last)
62 "Set last of MAP to LAST."
65 (defalias 'riece-make-lru 'riece-lru-make-map)
67 (defun riece-lru-contains (map key)
68 (intern-soft key (riece-lru-map-hash-obarray map)))
70 (defun riece-lru-get (map key)
71 (let ((node (riece-lru-get-node map key)))
73 (riece-lru-node-value node))))
75 (defun riece-lru-get-node (map key)
76 (let ((symbol (intern-soft key (riece-lru-map-hash-obarray map)))
77 previous next first last node)
79 (setq node (symbol-value symbol)
80 previous (riece-lru-node-previous node)
81 next (riece-lru-node-next node)
82 first (riece-lru-map-first map)
83 last (riece-lru-map-last map))
85 (riece-lru-node-set-next previous next))
87 (riece-lru-node-set-previous next previous))
88 (riece-lru-node-set-next node nil)
89 (riece-lru-node-set-previous node last)
90 (riece-lru-node-set-next last node)
91 (riece-lru-map-set-last map node)
92 (if (and (eq node (riece-lru-map-first map)) next)
93 (riece-lru-map-set-first map next))
96 (defun riece-lru-delete (map key)
97 (let ((symbol (intern-soft key (riece-lru-map-hash-obarray map)))
100 (setq node (symbol-value symbol)
101 previous (riece-lru-node-previous node)
102 next (riece-lru-node-next node))
104 (riece-lru-node-set-next previous next))
106 (riece-lru-node-set-previous next previous))
107 (if (eq (riece-lru-map-last map) node)
108 (riece-lru-map-set-last map previous))
109 (if (eq (riece-lru-map-first map) node)
110 (riece-lru-map-set-first map next))
111 (unintern symbol (riece-lru-map-hash-obarray map))
112 (riece-lru-map-set-hash-length map (1- (riece-lru-map-hash-length map)))
113 (riece-lru-node-value node))))
115 (defun riece-lru-set (map key value)
116 (let ((node (riece-lru-get-node map key))
120 (if (>= (riece-lru-map-hash-length map)
121 (riece-lru-map-max-length map))
122 (riece-lru-delete map (riece-lru-node-key
123 (riece-lru-map-first map))))
124 (setq node (riece-lru-make-node key value (riece-lru-map-last map) nil))
125 (set (intern key (riece-lru-map-hash-obarray map)) node)
126 (riece-lru-map-set-hash-length map (1+ (riece-lru-map-hash-length map)))
127 (unless (riece-lru-map-first map)
128 (riece-lru-map-set-first map node))
129 (if (riece-lru-map-last map)
131 (riece-lru-node-set-next (riece-lru-map-last map) node)
132 (riece-lru-node-set-previous node (riece-lru-map-last map))))
133 (riece-lru-map-set-last map node))))