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