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) 63 return NULL; 64 65 spin_lock_init(&f->lock); 66 f->head = NULL; 67 f->tail = NULL; 68 f->cells = 0; 69 70 return f; 71 } 72 73 /* delete prioq (destructor) */ 74 void snd_seq_prioq_delete(struct snd_seq_prioq **fifo) 75 { 76 struct snd_seq_prioq *f = *fifo; 77 *fifo = NULL; 78 79 if (f == NULL) { 80 pr_debug("ALSA: seq: snd_seq_prioq_delete() called with NULL prioq\n"); 81 return; 82 } 83 84 /* release resources...*/ 85 /*....................*/ 86 87 if (f->cells > 0) { 88 /* drain prioQ */ 89 while (f->cells > 0) 90 snd_seq_cell_free(snd_seq_prioq_cell_out(f)); 91 } 92 93 kfree(f); 94 } 95 96 97 98 99 /* compare timestamp between events */ 100 /* return 1 if a >= b; 0 */ 101 static inline int compare_timestamp(struct snd_seq_event *a, 102 struct snd_seq_event *b) 103 { 104 if ((a->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK) { 105 /* compare ticks */ 106 return (snd_seq_compare_tick_time(&a->time.tick, &b->time.tick)); 107 } else { 108 /* compare real time */ 109 return (snd_seq_compare_real_time(&a->time.time, &b->time.time)); 110 } 111 } 112 113 /* compare timestamp between events */ 114 /* return negative if a < b; 115 * zero if a = b; 116 * positive if a > b; 117 */ 118 static inline int compare_timestamp_rel(struct snd_seq_event *a, 119 struct snd_seq_event *b) 120 { 121 if ((a->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK) { 122 /* compare ticks */ 123 if (a->time.tick > b->time.tick) 124 return 1; 125 else if (a->time.tick == b->time.tick) 126 return 0; 127 else 128 return -1; 129 } else { 130 /* compare real time */ 131 if (a->time.time.tv_sec > b->time.time.tv_sec) 132 return 1; 133 else if (a->time.time.tv_sec == b->time.time.tv_sec) { 134 if (a->time.time.tv_nsec > b->time.time.tv_nsec) 135 return 1; 136 else if (a->time.time.tv_nsec == b->time.time.tv_nsec) 137 return 0; 138 else 139 return -1; 140 } else 141 return -1; 142 } 143 } 144 145 /* enqueue cell to prioq */ 146 int snd_seq_prioq_cell_in(struct snd_seq_prioq * f, 147 struct snd_seq_event_cell * cell) 148 { 149 struct snd_seq_event_cell *cur, *prev; 150 unsigned long flags; 151 int count; 152 int prior; 153 154 if (snd_BUG_ON(!f || !cell)) 155 return -EINVAL; 156 157 /* check flags */ 158 prior = (cell->event.flags & SNDRV_SEQ_PRIORITY_MASK); 159 160 spin_lock_irqsave(&f->lock, flags); 161 162 /* check if this element needs to inserted at the end (ie. ordered 163 data is inserted) This will be very likeley if a sequencer 164 application or midi file player is feeding us (sequential) data */ 165 if (f->tail && !prior) { 166 if (compare_timestamp(&cell->event, &f->tail->event)) { 167 /* add new cell to tail of the fifo */ 168 f->tail->next = cell; 169 f->tail = cell; 170 cell->next = NULL; 171 f->cells++; 172 spin_unlock_irqrestore(&f->lock, flags); 173 return 0; 174 } 175 } 176 /* traverse list of elements to find the place where the new cell is 177 to be inserted... Note that this is a order n process ! */ 178 179 prev = NULL; /* previous cell */ 180 cur = f->head; /* cursor */ 181 182 count = 10000; /* FIXME: enough big, isn't it? */ 183 while (cur != NULL) { 184 /* compare timestamps */ 185 int rel = compare_timestamp_rel(&cell->event, &cur->event); 186 if (rel < 0) 187 /* new cell has earlier schedule time, */ 188 break; 189 else if (rel == 0 && prior) 190 /* equal schedule time and prior to others */ 191 break; 192 /* new cell has equal or larger schedule time, */ 193 /* move cursor to next cell */ 194 prev = cur; 195 cur = cur->next; 196 if (! --count) { 197 spin_unlock_irqrestore(&f->lock, flags); 198 pr_err("ALSA: seq: cannot find a pointer.. infinite loop?\n"); 199 return -EINVAL; 200 } 201 } 202 203 /* insert it before cursor */ 204 if (prev != NULL) 205 prev->next = cell; 206 cell->next = cur; 207 208 if (f->head == cur) /* this is the first cell, set head to it */ 209 f->head = cell; 210 if (cur == NULL) /* reached end of the list */ 211 f->tail = cell; 212 f->cells++; 213 spin_unlock_irqrestore(&f->lock, flags); 214 return 0; 215 } 216 217 /* dequeue cell from prioq */ 218 struct snd_seq_event_cell *snd_seq_prioq_cell_out(struct snd_seq_prioq *f) 219 { 220 struct snd_seq_event_cell *cell; 221 unsigned long flags; 222 223 if (f == NULL) { 224 pr_debug("ALSA: seq: snd_seq_prioq_cell_in() called with NULL prioq\n"); 225 return NULL; 226 } 227 spin_lock_irqsave(&f->lock, flags); 228 229 cell = f->head; 230 if (cell) { 231 f->head = cell->next; 232 233 /* reset tail if this was the last element */ 234 if (f->tail == cell) 235 f->tail = NULL; 236 237 cell->next = NULL; 238 f->cells--; 239 } 240 241 spin_unlock_irqrestore(&f->lock, flags); 242 return cell; 243 } 244 245 /* return number of events available in prioq */ 246 int snd_seq_prioq_avail(struct snd_seq_prioq * f) 247 { 248 if (f == NULL) { 249 pr_debug("ALSA: seq: snd_seq_prioq_cell_in() called with NULL prioq\n"); 250 return 0; 251 } 252 return f->cells; 253 } 254 255 256 /* peek at cell at the head of the prioq */ 257 struct snd_seq_event_cell *snd_seq_prioq_cell_peek(struct snd_seq_prioq * f) 258 { 259 if (f == NULL) { 260 pr_debug("ALSA: seq: snd_seq_prioq_cell_in() called with NULL prioq\n"); 261 return NULL; 262 } 263 return f->head; 264 } 265 266 267 static inline int prioq_match(struct snd_seq_event_cell *cell, 268 int client, int timestamp) 269 { 270 if (cell->event.source.client == client || 271 cell->event.dest.client == client) 272 return 1; 273 if (!timestamp) 274 return 0; 275 switch (cell->event.flags & SNDRV_SEQ_TIME_STAMP_MASK) { 276 case SNDRV_SEQ_TIME_STAMP_TICK: 277 if (cell->event.time.tick) 278 return 1; 279 break; 280 case SNDRV_SEQ_TIME_STAMP_REAL: 281 if (cell->event.time.time.tv_sec || 282 cell->event.time.time.tv_nsec) 283 return 1; 284 break; 285 } 286 return 0; 287 } 288 289 /* remove cells for left client */ 290 void snd_seq_prioq_leave(struct snd_seq_prioq * f, int client, int timestamp) 291 { 292 register struct snd_seq_event_cell *cell, *next; 293 unsigned long flags; 294 struct snd_seq_event_cell *prev = NULL; 295 struct snd_seq_event_cell *freefirst = NULL, *freeprev = NULL, *freenext; 296 297 /* collect all removed cells */ 298 spin_lock_irqsave(&f->lock, flags); 299 cell = f->head; 300 while (cell) { 301 next = cell->next; 302 if (prioq_match(cell, client, timestamp)) { 303 /* remove cell from prioq */ 304 if (cell == f->head) { 305 f->head = cell->next; 306 } else { 307 prev->next = cell->next; 308 } 309 if (cell == f->tail) 310 f->tail = cell->next; 311 f->cells--; 312 /* add cell to free list */ 313 cell->next = NULL; 314 if (freefirst == NULL) { 315 freefirst = cell; 316 } else { 317 freeprev->next = cell; 318 } 319 freeprev = cell; 320 } else { 321 #if 0 322 pr_debug("ALSA: seq: type = %i, source = %i, dest = %i, " 323 "client = %i\n", 324 cell->event.type, 325 cell->event.source.client, 326 cell->event.dest.client, 327 client); 328 #endif 329 prev = cell; 330 } 331 cell = next; 332 } 333 spin_unlock_irqrestore(&f->lock, flags); 334 335 /* remove selected cells */ 336 while (freefirst) { 337 freenext = freefirst->next; 338 snd_seq_cell_free(freefirst); 339 freefirst = freenext; 340 } 341 } 342 343 static int prioq_remove_match(struct snd_seq_remove_events *info, 344 struct snd_seq_event *ev) 345 { 346 int res; 347 348 if (info->remove_mode & SNDRV_SEQ_REMOVE_DEST) { 349 if (ev->dest.client != info->dest.client || 350 ev->dest.port != info->dest.port) 351 return 0; 352 } 353 if (info->remove_mode & SNDRV_SEQ_REMOVE_DEST_CHANNEL) { 354 if (! snd_seq_ev_is_channel_type(ev)) 355 return 0; 356 /* data.note.channel and data.control.channel are identical */ 357 if (ev->data.note.channel != info->channel) 358 return 0; 359 } 360 if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_AFTER) { 361 if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_TICK) 362 res = snd_seq_compare_tick_time(&ev->time.tick, &info->time.tick); 363 else 364 res = snd_seq_compare_real_time(&ev->time.time, &info->time.time); 365 if (!res) 366 return 0; 367 } 368 if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_BEFORE) { 369 if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_TICK) 370 res = snd_seq_compare_tick_time(&ev->time.tick, &info->time.tick); 371 else 372 res = snd_seq_compare_real_time(&ev->time.time, &info->time.time); 373 if (res) 374 return 0; 375 } 376 if (info->remove_mode & SNDRV_SEQ_REMOVE_EVENT_TYPE) { 377 if (ev->type != info->type) 378 return 0; 379 } 380 if (info->remove_mode & SNDRV_SEQ_REMOVE_IGNORE_OFF) { 381 /* Do not remove off events */ 382 switch (ev->type) { 383 case SNDRV_SEQ_EVENT_NOTEOFF: 384 /* case SNDRV_SEQ_EVENT_SAMPLE_STOP: */ 385 return 0; 386 default: 387 break; 388 } 389 } 390 if (info->remove_mode & SNDRV_SEQ_REMOVE_TAG_MATCH) { 391 if (info->tag != ev->tag) 392 return 0; 393 } 394 395 return 1; 396 } 397 398 /* remove cells matching remove criteria */ 399 void snd_seq_prioq_remove_events(struct snd_seq_prioq * f, int client, 400 struct snd_seq_remove_events *info) 401 { 402 struct snd_seq_event_cell *cell, *next; 403 unsigned long flags; 404 struct snd_seq_event_cell *prev = NULL; 405 struct snd_seq_event_cell *freefirst = NULL, *freeprev = NULL, *freenext; 406 407 /* collect all removed cells */ 408 spin_lock_irqsave(&f->lock, flags); 409 cell = f->head; 410 411 while (cell) { 412 next = cell->next; 413 if (cell->event.source.client == client && 414 prioq_remove_match(info, &cell->event)) { 415 416 /* remove cell from prioq */ 417 if (cell == f->head) { 418 f->head = cell->next; 419 } else { 420 prev->next = cell->next; 421 } 422 423 if (cell == f->tail) 424 f->tail = cell->next; 425 f->cells--; 426 427 /* add cell to free list */ 428 cell->next = NULL; 429 if (freefirst == NULL) { 430 freefirst = cell; 431 } else { 432 freeprev->next = cell; 433 } 434 435 freeprev = cell; 436 } else { 437 prev = cell; 438 } 439 cell = next; 440 } 441 spin_unlock_irqrestore(&f->lock, flags); 442 443 /* remove selected cells */ 444 while (freefirst) { 445 freenext = freefirst->next; 446 snd_seq_cell_free(freefirst); 447 freefirst = freenext; 448 } 449 } 450 451 452