|
0
|
1 ;;; ring.el --- handle rings of items
|
|
|
2
|
|
|
3 ;; Copyright (C) 1992 Free Software Foundation, Inc.
|
|
|
4
|
|
|
5 ;; Maintainer: FSF
|
|
|
6 ;; Keywords: extensions
|
|
|
7
|
|
2
|
8 ;; This file is part of XEmacs.
|
|
0
|
9
|
|
2
|
10 ;; XEmacs is free software; you can redistribute it and/or modify it
|
|
|
11 ;; under the terms of the GNU General Public License as published by
|
|
0
|
12 ;; the Free Software Foundation; either version 2, or (at your option)
|
|
|
13 ;; any later version.
|
|
|
14
|
|
2
|
15 ;; XEmacs is distributed in the hope that it will be useful, but
|
|
|
16 ;; WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
17 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
|
18 ;; General Public License for more details.
|
|
0
|
19
|
|
|
20 ;; You should have received a copy of the GNU General Public License
|
|
2
|
21 ;; along with XEmacs; see the file COPYING. If not, write to the Free
|
|
|
22 ;; Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
|
|
|
23 ;; 02111-1307, USA.
|
|
0
|
24
|
|
2
|
25 ;;; Synched up with: FSF 19.34.
|
|
0
|
26
|
|
|
27 ;;; Commentary:
|
|
|
28
|
|
2
|
29 ;; This code defines a ring data structure. A ring is a
|
|
|
30 ;; (hd-index length . vector)
|
|
|
31 ;; list. You can insert to, remove from, and rotate a ring. When the ring
|
|
|
32 ;; fills up, insertions cause the oldest elts to be quietly dropped.
|
|
|
33 ;;
|
|
|
34 ;; In ring-ref, 0 is the index of the newest element. Higher indexes
|
|
|
35 ;; correspond to older elements until they wrap.
|
|
|
36 ;;
|
|
|
37 ;; hd-index = index of the newest item on the ring.
|
|
|
38 ;; length = number of ring items.
|
|
|
39 ;;
|
|
|
40 ;; These functions are used by the input history mechanism, but they can
|
|
|
41 ;; be used for other purposes as well.
|
|
0
|
42
|
|
|
43 ;;; Code:
|
|
|
44
|
|
2
|
45 ;; XEmacs change
|
|
0
|
46 ;;;###autoload
|
|
|
47 (defun ringp (x)
|
|
|
48 "Returns t if X is a ring; nil otherwise."
|
|
|
49 (and (consp x) (integerp (car x))
|
|
|
50 (consp (cdr x)) (integerp (car (cdr x)))
|
|
|
51 (vectorp (cdr (cdr x)))))
|
|
|
52
|
|
2
|
53 ;; XEmacs change
|
|
0
|
54 ;;;###autoload
|
|
|
55 (define-obsolete-function-alias 'ring-p 'ringp)
|
|
|
56
|
|
|
57 ;;;###autoload
|
|
|
58 (defun make-ring (size)
|
|
|
59 "Make a ring that can contain SIZE elements."
|
|
|
60 (cons 0 (cons 0 (make-vector size nil))))
|
|
|
61
|
|
|
62 (defun ring-insert-at-beginning (ring item)
|
|
|
63 "Add to RING the item ITEM. Add it at the front (the early end)."
|
|
|
64 (let* ((vec (cdr (cdr ring)))
|
|
|
65 (veclen (length vec))
|
|
|
66 (hd (car ring))
|
|
|
67 (ln (car (cdr ring))))
|
|
|
68 (setq ln (min veclen (1+ ln))
|
|
|
69 hd (ring-minus1 hd veclen))
|
|
|
70 (aset vec hd item)
|
|
|
71 (setcar ring hd)
|
|
|
72 (setcar (cdr ring) ln)))
|
|
|
73
|
|
|
74 (defun ring-plus1 (index veclen)
|
|
|
75 "INDEX+1, with wraparound"
|
|
|
76 (let ((new-index (+ index 1)))
|
|
|
77 (if (= new-index veclen) 0 new-index)))
|
|
|
78
|
|
|
79 (defun ring-minus1 (index veclen)
|
|
|
80 "INDEX-1, with wraparound"
|
|
|
81 (- (if (= 0 index) veclen index) 1))
|
|
|
82
|
|
|
83 (defun ring-length (ring)
|
|
|
84 "Number of elements in the ring."
|
|
|
85 (car (cdr ring)))
|
|
|
86
|
|
|
87 (defun ring-empty-p (ring)
|
|
|
88 (= 0 (car (cdr ring))))
|
|
|
89
|
|
|
90 (defun ring-index (index head ringlen veclen)
|
|
|
91 (setq index (mod index ringlen))
|
|
|
92 (mod (1- (+ head (- ringlen index))) veclen))
|
|
|
93
|
|
|
94 (defun ring-insert (ring item)
|
|
|
95 "Insert onto ring RING the item ITEM, as the newest (last) item.
|
|
|
96 If the ring is full, dump the oldest item to make room."
|
|
|
97 (let* ((vec (cdr (cdr ring)))
|
|
|
98 (veclen (length vec))
|
|
|
99 (hd (car ring))
|
|
|
100 (ln (car (cdr ring))))
|
|
|
101 (prog1
|
|
|
102 (aset vec (mod (+ hd ln) veclen) item)
|
|
|
103 (if (= ln veclen)
|
|
|
104 (setcar ring (ring-plus1 hd veclen))
|
|
|
105 (setcar (cdr ring) (1+ ln))))))
|
|
|
106
|
|
|
107 (defun ring-remove (ring &optional index)
|
|
|
108 "Remove an item from the RING. Return the removed item.
|
|
|
109 If optional INDEX is nil, remove the oldest item. If it's
|
|
|
110 numeric, remove the element indexed."
|
|
|
111 (if (ring-empty-p ring)
|
|
|
112 (error "Ring empty")
|
|
|
113 (let* ((hd (car ring))
|
|
|
114 (ln (car (cdr ring)))
|
|
|
115 (vec (cdr (cdr ring)))
|
|
|
116 (veclen (length vec))
|
|
|
117 (tl (mod (1- (+ hd ln)) veclen))
|
|
|
118 oldelt)
|
|
|
119 (if (null index)
|
|
|
120 (setq index (1- ln)))
|
|
|
121 (setq index (ring-index index hd ln veclen))
|
|
|
122 (setq oldelt (aref vec index))
|
|
|
123 (while (/= index tl)
|
|
|
124 (aset vec index (aref vec (ring-plus1 index veclen)))
|
|
|
125 (setq index (ring-plus1 index veclen)))
|
|
|
126 (aset vec tl nil)
|
|
|
127 (setcar (cdr ring) (1- ln))
|
|
|
128 oldelt)))
|
|
|
129
|
|
|
130 (defun ring-ref (ring index)
|
|
|
131 "Returns RING's INDEX element.
|
|
|
132 INDEX need not be <= the ring length, the appropriate modulo operation
|
|
|
133 will be performed. Element 0 is the most recently inserted; higher indices
|
|
|
134 correspond to older elements until they wrap."
|
|
|
135 (if (ring-empty-p ring)
|
|
|
136 (error "indexed empty ring")
|
|
|
137 (let* ((hd (car ring)) (ln (car (cdr ring))) (vec (cdr (cdr ring))))
|
|
|
138 (aref vec (ring-index index hd ln (length vec))))))
|
|
|
139
|
|
|
140 (provide 'ring)
|
|
|
141
|
|
|
142 ;;; ring.el ends here
|
