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 last node)
79 (setq node (symbol-value symbol)
80 previous (riece-lru-node-previous node)
81 next (riece-lru-node-next node)
82 last (riece-lru-map-last map))
84 (riece-lru-node-set-next previous next))
86 (riece-lru-node-set-previous next previous))
87 (riece-lru-node-set-next node nil)
88 (riece-lru-node-set-previous node last)
89 (riece-lru-node-set-next last node)
90 (riece-lru-map-set-last map node)
91 (if (and (eq node (riece-lru-map-first map)) next)
92 (riece-lru-map-set-first map next))
95 (defun riece-lru-delete (map key)
96 (let ((symbol (intern-soft key (riece-lru-map-hash-obarray map)))
99 (setq node (symbol-value symbol)
100 previous (riece-lru-node-previous node)
101 next (riece-lru-node-next node))
103 (riece-lru-node-set-next previous next))
105 (riece-lru-node-set-previous next previous))
106 (if (eq (riece-lru-map-last map) node)
107 (riece-lru-map-set-last map previous))
108 (if (eq (riece-lru-map-first map) node)
109 (riece-lru-map-set-first map next))
110 (unintern symbol (riece-lru-map-hash-obarray map))
111 (riece-lru-map-set-hash-length map (1- (riece-lru-map-hash-length map)))
112 (riece-lru-node-value node))))
114 (defun riece-lru-set (map key value)
115 (let ((node (riece-lru-get-node map key))
119 (if (>= (riece-lru-map-hash-length map)
120 (riece-lru-map-max-length map))
121 (riece-lru-delete map (riece-lru-node-key
122 (riece-lru-map-first map))))
123 (setq node (riece-lru-make-node key value (riece-lru-map-last map) nil))
124 (set (intern key (riece-lru-map-hash-obarray map)) node)
125 (riece-lru-map-set-hash-length map (1+ (riece-lru-map-hash-length map)))
126 (unless (riece-lru-map-first map)
127 (riece-lru-map-set-first map node))
128 (if (riece-lru-map-last map)
130 (riece-lru-node-set-next (riece-lru-map-last map) node)
131 (riece-lru-node-set-previous node (riece-lru-map-last map))))
132 (riece-lru-map-set-last map node))))