1 /* 2 * ALSA sequencer Priority Queue 3 * Copyright (c) 1998-1999 by Frank van de Pol <fvdpol@coil.demon.nl> 4 * 5 * 6 * This program is free software; you can redistribute it and/or modify 7 * it under the terms of the GNU General Public License as published by 8 * the Free Software Foundation; either version 2 of the License, or 9 * (at your option) any later version. 10 * 11 * This program is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU General Public License for more details. 15 * 16 * You should have received a copy of the GNU General Public License 17 * along with this program; if not, write to the Free Software 18 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 19 * 20 */ 21 22 #include <sound/driver.h> 23 #include <linux/time.h> 24 #include <linux/slab.h> 25 #include <sound/core.h> 26 #include "seq_timer.h" 27 #include "seq_prioq.h" 28 29 30 /* Implementation is a simple linked list for now... 31 32 This priority queue orders the events on timestamp. For events with an 33 equeal timestamp the queue behaves as a FIFO. 34 35 * 36 * +-------+ 37 * Head --> | first | 38 * +-------+ 39 * |next 40 * +-----v-+ 41 * | | 42 * +-------+ 43 * | 44 * +-----v-+ 45 * | | 46 * +-------+ 47 * | 48 * +-----v-+ 49 * Tail --> | last | 50 * +-------+ 51 * 52 53 */ 54 55 56 57 /* create new prioq (constructor) */ 58 struct snd_seq_prioq *snd_seq_prioq_new(void) 59 { 60 struct snd_seq_prioq *f; 61 62 f = kzalloc(sizeof(*f), GFP_KERNEL); 63 if (f == NULL) { 64 snd_printd("oops: malloc failed for snd_seq_prioq_new()\n"); 65 return NULL; 66 } 67 68 spin_lock_init(&f->lock); 69 f->head = NULL; 70 f->tail = NULL; 71 f->cells = 0; 72 73 return f; 74 } 75 76 /* delete prioq (destructor) */ 77 void snd_seq_prioq_delete(struct snd_seq_prioq **fifo) 78 { 79 struct snd_seq_prioq *f = *fifo; 80 *fifo = NULL; 81 82 if (f == NULL) { 83 snd_printd("oops: snd_seq_prioq_delete() called with NULL prioq\n"); 84 return; 85 } 86 87 /* release resources...*/ 88 /*....................*/ 89 90 if (f->cells > 0) { 91 /* drain prioQ */ 92 while (f->cells > 0) 93 snd_seq_cell_free(snd_seq_prioq_cell_out(f)); 94 } 95 96 kfree(f); 97 } 98 99 100 101 102 /* compare timestamp between events */ 103 /* return 1 if a >= b; 0 */ 104 static inline int compare_timestamp(struct snd_seq_event *a, 105 struct snd_seq_event *b) 106 { 107 if ((a->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK) { 108 /* compare ticks */ 109 return (snd_seq_compare_tick_time(&a->time.tick, &b->time.tick)); 110 } else { 111 /* compare real time */ 112 return (snd_seq_compare_real_time(&a->time.time, &b->time.time)); 113 } 114 } 115 116 /* compare timestamp between events */ 117 /* return negative if a < b; 118 * zero if a = b; 119 * positive if a > b; 120 */ 121 static inline int compare_timestamp_rel(struct snd_seq_event *a, 122 struct snd_seq_event *b) 123 { 124 if ((a->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK) { 125 /* compare ticks */ 126 if (a->time.tick > b->time.tick) 127 return 1; 128 else if (a->time.tick == b->time.tick) 129 return 0; 130 else 131 return -1; 132 } else { 133 /* compare real time */ 134 if (a->time.time.tv_sec > b->time.time.tv_sec) 135 return 1; 136 else if (a->time.time.tv_sec == b->time.time.tv_sec) { 137 if (a->time.time.tv_nsec > b->time.time.tv_nsec) 138 return 1; 139 else if (a->time.time.tv_nsec == b->time.time.tv_nsec) 140 return 0; 141 else 142 return -1; 143 } else 144 return -1; 145 } 146 } 147 148 /* enqueue cell to prioq */ 149 int snd_seq_prioq_cell_in(struct snd_seq_prioq * f, 150 struct snd_seq_event_cell * cell) 151 { 152 struct snd_seq_event_cell *cur, *prev; 153 unsigned long flags; 154 int count; 155 int prior; 156 157 snd_assert(f, return -EINVAL); 158 snd_assert(cell, return -EINVAL); 159 160 /* check flags */ 161 prior = (cell->event.flags & SNDRV_SEQ_PRIORITY_MASK); 162 163 spin_lock_irqsave(&f->lock, flags); 164 165 /* check if this element needs to inserted at the end (ie. ordered 166 data is inserted) This will be very likeley if a sequencer 167 application or midi file player is feeding us (sequential) data */ 168 if (f->tail && !prior) { 169 if (compare_timestamp(&cell->event, &f->tail->event)) { 170 /* add new cell to tail of the fifo */ 171 f->tail->next = cell; 172 f->tail = cell; 173 cell->next = NULL; 174 f->cells++; 175 spin_unlock_irqrestore(&f->lock, flags); 176 return 0; 177 } 178 } 179 /* traverse list of elements to find the place where the new cell is 180 to be inserted... Note that this is a order n process ! */ 181 182 prev = NULL; /* previous cell */ 183 cur = f->head; /* cursor */ 184 185 count = 10000; /* FIXME: enough big, isn't it? */ 186 while (cur != NULL) { 187 /* compare timestamps */ 188 int rel = compare_timestamp_rel(&cell->event, &cur->event); 189 if (rel < 0) 190 /* new cell has earlier schedule time, */ 191 break; 192 else if (rel == 0 && prior) 193 /* equal schedule time and prior to others */ 194 break; 195 /* new cell has equal or larger schedule time, */ 196 /* move cursor to next cell */ 197 prev = cur; 198 cur = cur->next; 199 if (! --count) { 200 spin_unlock_irqrestore(&f->lock, flags); 201 snd_printk(KERN_ERR "cannot find a pointer.. infinite loop?\n"); 202 return -EINVAL; 203 } 204 } 205 206 /* insert it before cursor */ 207 if (prev != NULL) 208 prev->next = cell; 209 cell->next = cur; 210 211 if (f->head == cur) /* this is the first cell, set head to it */ 212 f->head = cell; 213 if (cur == NULL) /* reached end of the list */ 214 f->tail = cell; 215 f->cells++; 216 spin_unlock_irqrestore(&f->lock, flags); 217 return 0; 218 } 219 220 /* dequeue cell from prioq */ 221 struct snd_seq_event_cell *snd_seq_prioq_cell_out(struct snd_seq_prioq *f) 222 { 223 struct snd_seq_event_cell *cell; 224 unsigned long flags; 225 226 if (f == NULL) { 227 snd_printd("oops: snd_seq_prioq_cell_in() called with NULL prioq\n"); 228 return NULL; 229 } 230 spin_lock_irqsave(&f->lock, flags); 231 232 cell = f->head; 233 if (cell) { 234 f->head = cell->next; 235 236 /* reset tail if this was the last element */ 237 if (f->tail == cell) 238 f->tail = NULL; 239 240 cell->next = NULL; 241 f->cells--; 242 } 243 244 spin_unlock_irqrestore(&f->lock, flags); 245 return cell; 246 } 247 248 /* return number of events available in prioq */ 249 int snd_seq_prioq_avail(struct snd_seq_prioq * f) 250 { 251 if (f == NULL) { 252 snd_printd("oops: snd_seq_prioq_cell_in() called with NULL prioq\n"); 253 return 0; 254 } 255 return f->cells; 256 } 257 258 259 /* peek at cell at the head of the prioq */ 260 struct snd_seq_event_cell *snd_seq_prioq_cell_peek(struct snd_seq_prioq * f) 261 { 262 if (f == NULL) { 263 snd_printd("oops: snd_seq_prioq_cell_in() called with NULL prioq\n"); 264 return NULL; 265 } 266 return f->head; 267 } 268 269 270 static inline int prioq_match(struct snd_seq_event_cell *cell, 271 int client, int timestamp) 272 { 273 if (cell->event.source.client == client || 274 cell->event.dest.client == client) 275 return 1; 276 if (!timestamp) 277 return 0; 278 switch (cell->event.flags & SNDRV_SEQ_TIME_STAMP_MASK) { 279 case SNDRV_SEQ_TIME_STAMP_TICK: 280 if (cell->event.time.tick) 281 return 1; 282 break; 283 case SNDRV_SEQ_TIME_STAMP_REAL: 284 if (cell->event.time.time.tv_sec || 285 cell->event.time.time.tv_nsec) 286 return 1; 287 break; 288 } 289 return 0; 290 } 291 292 /* remove cells for left client */ 293 void snd_seq_prioq_leave(struct snd_seq_prioq * f, int client, int timestamp) 294 { 295 register struct snd_seq_event_cell *cell, *next; 296 unsigned long flags; 297 struct snd_seq_event_cell *prev = NULL; 298 struct snd_seq_event_cell *freefirst = NULL, *freeprev = NULL, *freenext; 299 300 /* collect all removed cells */ 301 spin_lock_irqsave(&f->lock, flags); 302 cell = f->head; 303 while (cell) { 304 next = cell->next; 305 if (prioq_match(cell, client, timestamp)) { 306 /* remove cell from prioq */ 307 if (cell == f->head) { 308 f->head = cell->next; 309 } else { 310 prev->next = cell->next; 311 } 312 if (cell == f->tail) 313 f->tail = cell->next; 314 f->cells--; 315 /* add cell to free list */ 316 cell->next = NULL; 317 if (freefirst == NULL) { 318 freefirst = cell; 319 } else { 320 freeprev->next = cell; 321 } 322 freeprev = cell; 323 } else { 324 #if 0 325 printk("type = %i, source = %i, dest = %i, client = %i\n", 326 cell->event.type, 327 cell->event.source.client, 328 cell->event.dest.client, 329 client); 330 #endif 331 prev = cell; 332 } 333 cell = next; 334 } 335 spin_unlock_irqrestore(&f->lock, flags); 336 337 /* remove selected cells */ 338 while (freefirst) { 339 freenext = freefirst->next; 340 snd_seq_cell_free(freefirst); 341 freefirst = freenext; 342 } 343 } 344 345 static int prioq_remove_match(struct snd_seq_remove_events *info, 346 struct snd_seq_event *ev) 347 { 348 int res; 349 350 if (info->remove_mode & SNDRV_SEQ_REMOVE_DEST) { 351 if (ev->dest.client != info->dest.client || 352 ev->dest.port != info->dest.port) 353 return 0; 354 } 355 if (info->remove_mode & SNDRV_SEQ_REMOVE_DEST_CHANNEL) { 356 if (! snd_seq_ev_is_channel_type(ev)) 357 return 0; 358 /* data.note.channel and data.control.channel are identical */ 359 if (ev->data.note.channel != info->channel) 360 return 0; 361 } 362 if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_AFTER) { 363 if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_TICK) 364 res = snd_seq_compare_tick_time(&ev->time.tick, &info->time.tick); 365 else 366 res = snd_seq_compare_real_time(&ev->time.time, &info->time.time); 367 if (!res) 368 return 0; 369 } 370 if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_BEFORE) { 371 if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_TICK) 372 res = snd_seq_compare_tick_time(&ev->time.tick, &info->time.tick); 373 else 374 res = snd_seq_compare_real_time(&ev->time.time, &info->time.time); 375 if (res) 376 return 0; 377 } 378 if (info->remove_mode & SNDRV_SEQ_REMOVE_EVENT_TYPE) { 379 if (ev->type != info->type) 380 return 0; 381 } 382 if (info->remove_mode & SNDRV_SEQ_REMOVE_IGNORE_OFF) { 383 /* Do not remove off events */ 384 switch (ev->type) { 385 case SNDRV_SEQ_EVENT_NOTEOFF: 386 /* case SNDRV_SEQ_EVENT_SAMPLE_STOP: */ 387 return 0; 388 default: 389 break; 390 } 391 } 392 if (info->remove_mode & SNDRV_SEQ_REMOVE_TAG_MATCH) { 393 if (info->tag != ev->tag) 394 return 0; 395 } 396 397 return 1; 398 } 399 400 /* remove cells matching remove criteria */ 401 void snd_seq_prioq_remove_events(struct snd_seq_prioq * f, int client, 402 struct snd_seq_remove_events *info) 403 { 404 struct snd_seq_event_cell *cell, *next; 405 unsigned long flags; 406 struct snd_seq_event_cell *prev = NULL; 407 struct snd_seq_event_cell *freefirst = NULL, *freeprev = NULL, *freenext; 408 409 /* collect all removed cells */ 410 spin_lock_irqsave(&f->lock, flags); 411 cell = f->head; 412 413 while (cell) { 414 next = cell->next; 415 if (cell->event.source.client == client && 416 prioq_remove_match(info, &cell->event)) { 417 418 /* remove cell from prioq */ 419 if (cell == f->head) { 420 f->head = cell->next; 421 } else { 422 prev->next = cell->next; 423 } 424 425 if (cell == f->tail) 426 f->tail = cell->next; 427 f->cells--; 428 429 /* add cell to free list */ 430 cell->next = NULL; 431 if (freefirst == NULL) { 432 freefirst = cell; 433 } else { 434 freeprev->next = cell; 435 } 436 437 freeprev = cell; 438 } else { 439 prev = cell; 440 } 441 cell = next; 442 } 443 spin_unlock_irqrestore(&f->lock, flags); 444 445 /* remove selected cells */ 446 while (freefirst) { 447 freenext = freefirst->next; 448 snd_seq_cell_free(freefirst); 449 freefirst = freenext; 450 } 451 } 452 453 454