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