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