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) */ 58struct 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) */ 77void 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 */ 104static 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 */ 121static 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 */ 149int 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; 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 */ 221struct 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 */ 249int 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 */ 260struct 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 270static 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 */ 293void 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 prev = cell; 325 } 326 cell = next; 327 } 328 spin_unlock_irqrestore(&f->lock, flags); 329 330 /* remove selected cells */ 331 while (freefirst) { 332 freenext = freefirst->next; 333 snd_seq_cell_free(freefirst); 334 freefirst = freenext; 335 } 336} 337 338static int prioq_remove_match(struct snd_seq_remove_events *info, 339 struct snd_seq_event *ev) 340{ 341 int res; 342 343 if (info->remove_mode & SNDRV_SEQ_REMOVE_DEST) { 344 if (ev->dest.client != info->dest.client || 345 ev->dest.port != info->dest.port) 346 return 0; 347 } 348 if (info->remove_mode & SNDRV_SEQ_REMOVE_DEST_CHANNEL) { 349 if (! snd_seq_ev_is_channel_type(ev)) 350 return 0; 351 /* data.note.channel and data.control.channel are identical */ 352 if (ev->data.note.channel != info->channel) 353 return 0; 354 } 355 if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_AFTER) { 356 if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_TICK) 357 res = snd_seq_compare_tick_time(&ev->time.tick, &info->time.tick); 358 else 359 res = snd_seq_compare_real_time(&ev->time.time, &info->time.time); 360 if (!res) 361 return 0; 362 } 363 if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_BEFORE) { 364 if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_TICK) 365 res = snd_seq_compare_tick_time(&ev->time.tick, &info->time.tick); 366 else 367 res = snd_seq_compare_real_time(&ev->time.time, &info->time.time); 368 if (res) 369 return 0; 370 } 371 if (info->remove_mode & SNDRV_SEQ_REMOVE_EVENT_TYPE) { 372 if (ev->type != info->type) 373 return 0; 374 } 375 if (info->remove_mode & SNDRV_SEQ_REMOVE_IGNORE_OFF) { 376 /* Do not remove off events */ 377 switch (ev->type) { 378 case SNDRV_SEQ_EVENT_NOTEOFF: 379 /* case SNDRV_SEQ_EVENT_SAMPLE_STOP: */ 380 return 0; 381 default: 382 break; 383 } 384 } 385 if (info->remove_mode & SNDRV_SEQ_REMOVE_TAG_MATCH) { 386 if (info->tag != ev->tag) 387 return 0; 388 } 389 390 return 1; 391} 392 393/* remove cells matching remove criteria */ 394void snd_seq_prioq_remove_events(struct snd_seq_prioq * f, int client, 395 struct snd_seq_remove_events *info) 396{ 397 struct snd_seq_event_cell *cell, *next; 398 unsigned long flags; 399 struct snd_seq_event_cell *prev = NULL; 400 struct snd_seq_event_cell *freefirst = NULL, *freeprev = NULL, *freenext; 401 402 /* collect all removed cells */ 403 spin_lock_irqsave(&f->lock, flags); 404 cell = f->head; 405 406 while (cell) { 407 next = cell->next; 408 if (cell->event.source.client == client && 409 prioq_remove_match(info, &cell->event)) { 410 411 /* remove cell from prioq */ 412 if (cell == f->head) { 413 f->head = cell->next; 414 } else { 415 prev->next = cell->next; 416 } 417 418 if (cell == f->tail) 419 f->tail = cell->next; 420 f->cells--; 421 422 /* add cell to free list */ 423 cell->next = NULL; 424 if (freefirst == NULL) { 425 freefirst = cell; 426 } else { 427 freeprev->next = cell; 428 } 429 430 freeprev = cell; 431 } else { 432 prev = cell; 433 } 434 cell = next; 435 } 436 spin_unlock_irqrestore(&f->lock, flags); 437 438 /* remove selected cells */ 439 while (freefirst) { 440 freenext = freefirst->next; 441 snd_seq_cell_free(freefirst); 442 freefirst = freenext; 443 } 444} 445