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 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 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 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 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 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 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 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 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 * 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 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 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 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 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 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 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