1 /*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License, Version 1.0 only
6 * (the "License"). You may not use this file except in compliance
7 * with the License.
8 *
9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10 * or http://www.opensolaris.org/os/licensing.
11 * See the License for the specific language governing permissions
12 * and limitations under the License.
13 *
14 * When distributing Covered Code, include this CDDL HEADER in each
15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16 * If applicable, add the following below this CDDL HEADER, with the
17 * fields enclosed by brackets "[]" replaced with your own identifying
18 * information: Portions Copyright [yyyy] [name of copyright owner]
19 *
20 * CDDL HEADER END
21 */
22 /*
23 * Copyright (c) 1985, 1997 by Sun Microsystems, Inc.
24 * All rights reserved.
25 */
26
27 /*
28 * Vuid (Virtual User Input Device) queue management.
29 */
30
31 #include <sys/types.h>
32 #include <sys/time.h>
33 #include <sys/vuid_event.h>
34 #include <sys/vuid_queue.h>
35
36 static Vuid_q_node *vq_alloc_node(Vuid_queue *vq);
37 static void vq_free_node(Vuid_queue *vq, Vuid_q_node *vqn);
38
39 static int tv_equal(struct timeval32 a, struct timeval32 b);
40 static struct timeval32 tv_subt(struct timeval32 atv, struct timeval32 btv);
41 static struct timeval32 tv_divide(struct timeval32 tv, int dividend);
42 static struct timeval32 tv_mult(struct timeval32 tv, int multiplier);
43 #define tv_to_usec(tv) (((tv).tv_sec * 1000000) + (tv).tv_usec)
44 /* Works for small numbers (< 1000) of seconds */
45 static struct timeval32 usec_to_tv(int usec);
46
47 void
vq_initialize(Vuid_queue * vq,caddr_t data,u_int bytes)48 vq_initialize(Vuid_queue *vq, caddr_t data, u_int bytes)
49 {
50 Vuid_q_node *new_vqns, *vqn;
51
52 /* Initialize vq */
53 vq->top = vq->bottom = vq->free = VUID_Q_NODE_NULL;
54 vq->size = 1 + (bytes - sizeof (Vuid_q_node)) / sizeof (Vuid_q_node);
55 /* Place in pool by freeing all nodes (fudge vq->num for this) */
56 new_vqns = (Vuid_q_node *)data;
57 vq->num = vq->size;
58 for (vqn = new_vqns; vqn < new_vqns + vq->size; vqn++)
59 vq_free_node(vq, vqn);
60 }
61
62 Vuid_q_code
vq_put(Vuid_queue * vq,Firm_event * firm_event)63 vq_put(Vuid_queue *vq, Firm_event *firm_event)
64 {
65 Vuid_q_node *vp;
66
67 /* Merge into existing events based on time stamp */
68 for (vp = vq->bottom; vp; vp = vp->prev) {
69 /* Put later times closer to the bottom than earlier ones */
70 if (timercmp(&vp->firm_event.time, &firm_event->time,
71 < /* comment to make cstyle happy - heinous! */) ||
72 tv_equal(vp->firm_event.time, firm_event->time)) {
73 Vuid_q_node *vqn = vq_alloc_node(vq);
74
75 if (vqn == VUID_Q_NODE_NULL)
76 return (VUID_Q_OVERFLOW);
77 vqn->firm_event = *firm_event;
78 /* Insert vqn before vq (neither are null) */
79 /* Initialize vqn's next and prev */
80 vqn->next = vp->next;
81 vqn->prev = vp;
82 /* Fix up vp next's prev */
83 if (vp->next != VUID_Q_NODE_NULL)
84 vp->next->prev = vqn;
85 /* Fix up vp's next */
86 vp->next = vqn;
87 /* Change bottom */
88 if (vp == vq->bottom)
89 vq->bottom = vqn;
90 /* Change top */
91 if (vq->top == VUID_Q_NODE_NULL)
92 vq->top = vqn;
93 return (VUID_Q_OK);
94 }
95 }
96 /* Place at top of queue */
97 return (vq_putback(vq, firm_event));
98 }
99
100 Vuid_q_code
vq_get(Vuid_queue * vq,Firm_event * firm_event)101 vq_get(Vuid_queue *vq, Firm_event *firm_event)
102 {
103 Vuid_q_node *vqn = vq->top;
104
105 if (vqn == VUID_Q_NODE_NULL)
106 return (VUID_Q_EMPTY);
107 /* Conditionally copy data */
108 if (firm_event != FIRM_EVENT_NULL)
109 *firm_event = vqn->firm_event;
110 /* Change top */
111 vq->top = vqn->next;
112 /* Null new top's prev */
113 if (vq->top != VUID_Q_NODE_NULL)
114 vq->top->prev = VUID_Q_NODE_NULL;
115 /* Change bottom */
116 if (vq->bottom == vqn)
117 vq->bottom = VUID_Q_NODE_NULL;
118 /* Release storage */
119 vq_free_node(vq, vqn);
120 return (VUID_Q_OK);
121 }
122
123 Vuid_q_code
vq_peek(Vuid_queue * vq,Firm_event * firm_event)124 vq_peek(Vuid_queue *vq, Firm_event *firm_event)
125 {
126 if (vq->top == VUID_Q_NODE_NULL)
127 return (VUID_Q_EMPTY);
128 *firm_event = vq->top->firm_event;
129 return (VUID_Q_OK);
130 }
131
132 Vuid_q_code
vq_putback(Vuid_queue * vq,Firm_event * firm_event)133 vq_putback(Vuid_queue *vq, Firm_event *firm_event)
134 {
135 Vuid_q_node *vqn = vq_alloc_node(vq);
136
137 if (vqn == VUID_Q_NODE_NULL)
138 return (VUID_Q_OVERFLOW);
139 vqn->firm_event = *firm_event;
140 /* Change new top's next */
141 vqn->next = vq->top;
142 /* Null new top's prev */
143 vqn->prev = VUID_Q_NODE_NULL;
144 /* Change old top's prev */
145 if (vq->top != VUID_Q_NODE_NULL)
146 vq->top->prev = vqn;
147 /* Change top */
148 vq->top = vqn;
149 /* Change bottom */
150 if (vq->bottom == VUID_Q_NODE_NULL)
151 vq->bottom = vqn;
152 return (VUID_Q_OK);
153 }
154
155 int
vq_compress(Vuid_queue * vq,int factor)156 vq_compress(Vuid_queue *vq, int factor)
157 {
158 struct timeval32 tv_interval, tv_avg_diff, tv_diff; /* Intermediates */
159 struct timeval32 tv_threshold;
160 Vuid_q_node *base, *victim;
161 Vuid_q_node *victim_next;
162 int num_start;
163
164 if (vq->top == VUID_Q_NODE_NULL)
165 return (0);
166 num_start = vq->num;
167 /*
168 * Determine the threshold time interval under which events of
169 * the same type (valuator only) are collapsed.
170 * min_time_betvqnen_values = ((first_entry_time - last_entry_time) /
171 * max_number_of_queue_entries) * factor_by_which_to_compress_queue;
172 */
173 tv_interval = tv_subt(vq->bottom->firm_event.time,
174 vq->top->firm_event.time);
175 tv_avg_diff = tv_divide(tv_interval, vq->num);
176 tv_threshold = tv_mult(tv_avg_diff, factor);
177 /* March down list */
178 for (base = vq->top; base; base = base->next) {
179 /* See if valuator event */
180 if (!vq_is_valuator(base))
181 continue;
182 /* Run down list looking for a collapse victim */
183 for (victim = base->next; victim; victim = victim_next) {
184 /* Remember next victim incase axe victim below */
185 victim_next = victim->next;
186 /* Fail if not valuator event */
187 if (!vq_is_valuator(victim))
188 goto Advance_Base;
189 /*
190 * May peek ahead and do the collapse as long as the
191 * intervening times of other valuator event types
192 * are the same. Fail if intervening event's time
193 * differs from victim's.
194 */
195 if (victim->prev != base) {
196 if (!tv_equal(victim->prev->firm_event.time,
197 victim->firm_event.time))
198 goto Advance_Base;
199 }
200 /* Fail if time difference is above threshold */
201 tv_diff = tv_subt(victim->firm_event.time,
202 base->firm_event.time);
203 /* Zero factor means collapse regardless of threshold */
204 if ((factor > 0) &&
205 (timercmp(&tv_diff, &tv_threshold, > /* cstyle */)))
206 goto Advance_Base;
207 /* Do collapse if same event id */
208 if (victim->firm_event.id == base->firm_event.id) {
209 /* Collapse value into base event */
210 switch (base->firm_event.pair_type) {
211 case FE_PAIR_ABSOLUTE:
212 /* id is delta */
213 base->firm_event.value +=
214 victim->firm_event.value;
215 break;
216 case FE_PAIR_DELTA:
217 /* id is absolute */
218 /* Fall through */
219 default:
220 /* Assume id is absolute */
221 base->firm_event.value =
222 victim->firm_event.value;
223 break;
224 }
225 /* Remove victim node */
226 vq_delete_node(vq, victim);
227 }
228 }
229 Advance_Base:
230 {}
231 }
232 return (num_start - vq->num);
233 }
234
235 int
vq_is_valuator(Vuid_q_node * vqn)236 vq_is_valuator(Vuid_q_node *vqn)
237 {
238 return ((vqn->firm_event.value < 1 && vqn->firm_event.value > -1) ||
239 (vqn->firm_event.pair_type == FE_PAIR_DELTA) ||
240 (vqn->firm_event.pair_type == FE_PAIR_ABSOLUTE));
241 }
242
243 void
vq_delete_node(Vuid_queue * vq,Vuid_q_node * vqn)244 vq_delete_node(Vuid_queue *vq, Vuid_q_node *vqn)
245 {
246 /* Use get if removing off top of queue */
247 if (vqn == vq->top) {
248 (void) vq_get(vq, FIRM_EVENT_NULL);
249 return;
250 }
251 /* Update previous next link (not null else vqn would be top) */
252 vqn->prev->next = vqn->next;
253 /* Change bottom */
254 if (vq->bottom == vqn)
255 vq->bottom = vqn->prev;
256 else
257 /* Update next previous link (if null else vqn is bottom) */
258 vqn->next->prev = vqn->prev;
259 /* Release storage */
260 vq_free_node(vq, vqn);
261 }
262
263 /*
264 * Caller must initialize data returned from vq_alloc_node.
265 * VUID_Q_NODE_NULL is possible.
266 */
267 static Vuid_q_node *
vq_alloc_node(Vuid_queue * vq)268 vq_alloc_node(Vuid_queue *vq)
269 {
270 Vuid_q_node *vqn;
271
272 if (vq->free == VUID_Q_NODE_NULL)
273 return (VUID_Q_NODE_NULL);
274 vqn = vq->free;
275 vq->free = vq->free->next;
276 vq->num++;
277 vqn->next = VUID_Q_NODE_NULL;
278 return (vqn);
279 }
280
281 static void
vq_free_node(Vuid_queue * vq,Vuid_q_node * vqn)282 vq_free_node(Vuid_queue *vq, Vuid_q_node *vqn)
283 {
284 vqn->next = vq->free;
285 vqn->prev = VUID_Q_NODE_NULL;
286 vq->free = vqn;
287 vq->num--;
288 }
289
290 static int
tv_equal(struct timeval32 a,struct timeval32 b)291 tv_equal(struct timeval32 a, struct timeval32 b)
292 {
293 return (a.tv_sec == b.tv_sec && a.tv_usec == b.tv_usec);
294 }
295
296 /* atv-btv */
297 static struct timeval32
tv_subt(struct timeval32 atv,struct timeval32 btv)298 tv_subt(struct timeval32 atv, struct timeval32 btv)
299 {
300 if ((atv.tv_usec < btv.tv_usec) && atv.tv_sec) {
301 atv.tv_usec += 1000000;
302 atv.tv_sec--;
303 }
304 if (atv.tv_usec > btv.tv_usec)
305 atv.tv_usec -= btv.tv_usec;
306 else
307 atv.tv_usec = 0;
308 if (atv.tv_sec > btv.tv_sec)
309 atv.tv_sec -= btv.tv_sec;
310 else {
311 if (atv.tv_sec < btv.tv_sec)
312 atv.tv_usec = 0;
313 atv.tv_sec = 0;
314 }
315 return (atv);
316 }
317
318 /* tv / dividend */
319 static struct timeval32
tv_divide(struct timeval32 tv,int dividend)320 tv_divide(struct timeval32 tv, int dividend)
321 {
322 int usecs;
323
324 if (dividend == 0)
325 return (tv);
326 usecs = tv_to_usec(tv);
327 usecs /= dividend;
328 tv = usec_to_tv(usecs);
329 return (tv);
330 }
331
332 /* tv * multiplier (works for small multipliers * seconds, < 1000) */
333 static struct timeval32
tv_mult(struct timeval32 tv,int multiplier)334 tv_mult(struct timeval32 tv, int multiplier)
335 {
336 int usecs;
337
338 usecs = tv_to_usec(tv);
339 usecs *= multiplier;
340 tv = usec_to_tv(usecs);
341 return (tv);
342 }
343
344 static struct timeval32
usec_to_tv(int usec)345 usec_to_tv(int usec)
346 {
347 struct timeval32 tv;
348
349 tv.tv_sec = usec / 1000000;
350 tv.tv_usec = usec % 1000000;
351 return (tv);
352 }
353