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 <linux/time.h> 23 #include <linux/slab.h> 24 #include <sound/core.h> 25 #include "seq_timer.h" 26 #include "seq_prioq.h" 27 28 29 /* Implementation is a simple linked list for now... 30 31 This priority queue orders the events on timestamp. For events with an 32 equeal timestamp the queue behaves as a FIFO. 33 34 * 35 * +-------+ 36 * Head --> | first | 37 * +-------+ 38 * |next 39 * +-----v-+ 40 * | | 41 * +-------+ 42 * | 43 * +-----v-+ 44 * | | 45 * +-------+ 46 * | 47 * +-----v-+ 48 * Tail --> | last | 49 * +-------+ 50 * 51 52 */ 53 54 55 56 /* create new prioq (constructor) */ 57 struct snd_seq_prioq *snd_seq_prioq_new(void) 58 { 59 struct snd_seq_prioq *f; 60 61 f = kzalloc(sizeof(*f), GFP_KERNEL); 62 if (f == NULL) { 63 snd_printd("oops: malloc failed for snd_seq_prioq_new()\n"); 64 return NULL; 65 } 66 67 spin_lock_init(&f->lock); 68 f->head = NULL; 69 f->tail = NULL; 70 f->cells = 0; 71 72 return f; 73 } 74 75 /* delete prioq (destructor) */ 76 void snd_seq_prioq_delete(struct snd_seq_prioq **fifo) 77 { 78 struct snd_seq_prioq *f = *fifo; 79 *fifo = NULL; 80 81 if (f == NULL) { 82 snd_printd("oops: snd_seq_prioq_delete() called with NULL prioq\n"); 83 return; 84 } 85 86 /* release resources...*/ 87 /*....................*/ 88 89 if (f->cells > 0) { 90 /* drain prioQ */ 91 while (f->cells > 0) 92 snd_seq_cell_free(snd_seq_prioq_cell_out(f)); 93 } 94 95 kfree(f); 96 } 97 98 99 100 101 /* compare timestamp between events */ 102 /* return 1 if a >= b; 0 */ 103 static inline int compare_timestamp(struct snd_seq_event *a, 104 struct snd_seq_event *b) 105 { 106 if ((a->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK) { 107 /* compare ticks */ 108 return (snd_seq_compare_tick_time(&a->time.tick, &b->time.tick)); 109 } else { 110 /* compare real time */ 111 return (snd_seq_compare_real_time(&a->time.time, &b->time.time)); 112 } 113 } 114 115 /* compare timestamp between events */ 116 /* return negative if a < b; 117 * zero if a = b; 118 * positive if a > b; 119 */ 120 static inline int compare_timestamp_rel(struct snd_seq_event *a, 121 struct snd_seq_event *b) 122 { 123 if ((a->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK) { 124 /* compare ticks */ 125 if (a->time.tick > b->time.tick) 126 return 1; 127 else if (a->time.tick == b->time.tick) 128 return 0; 129 else 130 return -1; 131 } else { 132 /* compare real time */ 133 if (a->time.time.tv_sec > b->time.time.tv_sec) 134 return 1; 135 else if (a->time.time.tv_sec == b->time.time.tv_sec) { 136 if (a->time.time.tv_nsec > b->time.time.tv_nsec) 137 return 1; 138 else if (a->time.time.tv_nsec == b->time.time.tv_nsec) 139 return 0; 140 else 141 return -1; 142 } else 143 return -1; 144 } 145 } 146 147 /* enqueue cell to prioq */ 148 int snd_seq_prioq_cell_in(struct snd_seq_prioq * f, 149 struct snd_seq_event_cell * cell) 150 { 151 struct snd_seq_event_cell *cur, *prev; 152 unsigned long flags; 153 int count; 154 int prior; 155 156 if (snd_BUG_ON(!f || !cell)) 157 return -EINVAL; 158 159 /* check flags */ 160 prior = (cell->event.flags & SNDRV_SEQ_PRIORITY_MASK); 161 162 spin_lock_irqsave(&f->lock, flags); 163 164 /* check if this element needs to inserted at the end (ie. ordered 165 data is inserted) This will be very likeley if a sequencer 166 application or midi file player is feeding us (sequential) data */ 167 if (f->tail && !prior) { 168 if (compare_timestamp(&cell->event, &f->tail->event)) { 169 /* add new cell to tail of the fifo */ 170 f->tail->next = cell; 171 f->tail = cell; 172 cell->next = NULL; 173 f->cells++; 174 spin_unlock_irqrestore(&f->lock, flags); 175 return 0; 176 } 177 } 178 /* traverse list of elements to find the place where the new cell is 179 to be inserted... Note that this is a order n process ! */ 180 181 prev = NULL; /* previous cell */ 182 cur = f->head; /* cursor */ 183 184 count = 10000; /* FIXME: enough big, isn't it? */ 185 while (cur != NULL) { 186 /* compare timestamps */ 187 int rel = compare_timestamp_rel(&cell->event, &cur->event); 188 if (rel < 0) 189 /* new cell has earlier schedule time, */ 190 break; 191 else if (rel == 0 && prior) 192 /* equal schedule time and prior to others */ 193 break; 194 /* new cell has equal or larger schedule time, */ 195 /* move cursor to next cell */ 196 prev = cur; 197 cur = cur->next; 198 if (! --count) { 199 spin_unlock_irqrestore(&f->lock, flags); 200 snd_printk(KERN_ERR "cannot find a pointer.. infinite loop?\n"); 201 return -EINVAL; 202 } 203 } 204 205 /* insert it before cursor */ 206 if (prev != NULL) 207 prev->next = cell; 208 cell->next = cur; 209 210 if (f->head == cur) /* this is the first cell, set head to it */ 211 f->head = cell; 212 if (cur == NULL) /* reached end of the list */ 213 f->tail = cell; 214 f->cells++; 215 spin_unlock_irqrestore(&f->lock, flags); 216 return 0; 217 } 218 219 /* dequeue cell from prioq */ 220 struct snd_seq_event_cell *snd_seq_prioq_cell_out(struct snd_seq_prioq *f) 221 { 222 struct snd_seq_event_cell *cell; 223 unsigned long flags; 224 225 if (f == NULL) { 226 snd_printd("oops: snd_seq_prioq_cell_in() called with NULL prioq\n"); 227 return NULL; 228 } 229 spin_lock_irqsave(&f->lock, flags); 230 231 cell = f->head; 232 if (cell) { 233 f->head = cell->next; 234 235 /* reset tail if this was the last element */ 236 if (f->tail == cell) 237 f->tail = NULL; 238 239 cell->next = NULL; 240 f->cells--; 241 } 242 243 spin_unlock_irqrestore(&f->lock, flags); 244 return cell; 245 } 246 247 /* return number of events available in prioq */ 248 int snd_seq_prioq_avail(struct snd_seq_prioq * f) 249 { 250 if (f == NULL) { 251 snd_printd("oops: snd_seq_prioq_cell_in() called with NULL prioq\n"); 252 return 0; 253 } 254 return f->cells; 255 } 256 257 258 /* peek at cell at the head of the prioq */ 259 struct snd_seq_event_cell *snd_seq_prioq_cell_peek(struct snd_seq_prioq * f) 260 { 261 if (f == NULL) { 262 snd_printd("oops: snd_seq_prioq_cell_in() called with NULL prioq\n"); 263 return NULL; 264 } 265 return f->head; 266 } 267 268 269 static inline int prioq_match(struct snd_seq_event_cell *cell, 270 int client, int timestamp) 271 { 272 if (cell->event.source.client == client || 273 cell->event.dest.client == client) 274 return 1; 275 if (!timestamp) 276 return 0; 277 switch (cell->event.flags & SNDRV_SEQ_TIME_STAMP_MASK) { 278 case SNDRV_SEQ_TIME_STAMP_TICK: 279 if (cell->event.time.tick) 280 return 1; 281 break; 282 case SNDRV_SEQ_TIME_STAMP_REAL: 283 if (cell->event.time.time.tv_sec || 284 cell->event.time.time.tv_nsec) 285 return 1; 286 break; 287 } 288 return 0; 289 } 290 291 /* remove cells for left client */ 292 void snd_seq_prioq_leave(struct snd_seq_prioq * f, int client, int timestamp) 293 { 294 register struct snd_seq_event_cell *cell, *next; 295 unsigned long flags; 296 struct snd_seq_event_cell *prev = NULL; 297 struct snd_seq_event_cell *freefirst = NULL, *freeprev = NULL, *freenext; 298 299 /* collect all removed cells */ 300 spin_lock_irqsave(&f->lock, flags); 301 cell = f->head; 302 while (cell) { 303 next = cell->next; 304 if (prioq_match(cell, client, timestamp)) { 305 /* remove cell from prioq */ 306 if (cell == f->head) { 307 f->head = cell->next; 308 } else { 309 prev->next = cell->next; 310 } 311 if (cell == f->tail) 312 f->tail = cell->next; 313 f->cells--; 314 /* add cell to free list */ 315 cell->next = NULL; 316 if (freefirst == NULL) { 317 freefirst = cell; 318 } else { 319 freeprev->next = cell; 320 } 321 freeprev = cell; 322 } else { 323 #if 0 324 printk(KERN_DEBUG "type = %i, source = %i, dest = %i, " 325 "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