2 * ALSA sequencer Priority Queue
3 * Copyright (c) 1998-1999 by Frank van de Pol <fvdpol@coil.demon.nl>
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.
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.
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
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"
29 /* Implementation is a simple linked list for now...
31 This priority queue orders the events on timestamp. For events with an
32 equeal timestamp the queue behaves as a FIFO.
56 /* create new prioq (constructor) */
57 struct snd_seq_prioq *snd_seq_prioq_new(void)
59 struct snd_seq_prioq *f;
61 f = kzalloc(sizeof(*f), GFP_KERNEL);
65 spin_lock_init(&f->lock);
73 /* delete prioq (destructor) */
74 void snd_seq_prioq_delete(struct snd_seq_prioq **fifo)
76 struct snd_seq_prioq *f = *fifo;
80 pr_debug("ALSA: seq: snd_seq_prioq_delete() called with NULL prioq\n");
84 /* release resources...*/
85 /*....................*/
90 snd_seq_cell_free(snd_seq_prioq_cell_out(f, NULL));
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)
104 if ((a->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK) {
106 return (snd_seq_compare_tick_time(&a->time.tick, &b->time.tick));
108 /* compare real time */
109 return (snd_seq_compare_real_time(&a->time.time, &b->time.time));
113 /* compare timestamp between events */
114 /* return negative if a < b;
118 static inline int compare_timestamp_rel(struct snd_seq_event *a,
119 struct snd_seq_event *b)
121 if ((a->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK) {
123 if (a->time.tick > b->time.tick)
125 else if (a->time.tick == b->time.tick)
130 /* compare real time */
131 if (a->time.time.tv_sec > b->time.time.tv_sec)
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)
136 else if (a->time.time.tv_nsec == b->time.time.tv_nsec)
145 /* enqueue cell to prioq */
146 int snd_seq_prioq_cell_in(struct snd_seq_prioq * f,
147 struct snd_seq_event_cell * cell)
149 struct snd_seq_event_cell *cur, *prev;
154 if (snd_BUG_ON(!f || !cell))
158 prior = (cell->event.flags & SNDRV_SEQ_PRIORITY_MASK);
160 spin_lock_irqsave(&f->lock, flags);
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;
172 spin_unlock_irqrestore(&f->lock, flags);
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 ! */
179 prev = NULL; /* previous cell */
180 cur = f->head; /* cursor */
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);
187 /* new cell has earlier schedule time, */
189 else if (rel == 0 && prior)
190 /* equal schedule time and prior to others */
192 /* new cell has equal or larger schedule time, */
193 /* move cursor to next cell */
197 spin_unlock_irqrestore(&f->lock, flags);
198 pr_err("ALSA: seq: cannot find a pointer.. infinite loop?\n");
203 /* insert it before cursor */
208 if (f->head == cur) /* this is the first cell, set head to it */
210 if (cur == NULL) /* reached end of the list */
213 spin_unlock_irqrestore(&f->lock, flags);
217 /* return 1 if the current time >= event timestamp */
218 static int event_is_ready(struct snd_seq_event *ev, void *current_time)
220 if ((ev->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK)
221 return snd_seq_compare_tick_time(current_time, &ev->time.tick);
223 return snd_seq_compare_real_time(current_time, &ev->time.time);
226 /* dequeue cell from prioq */
227 struct snd_seq_event_cell *snd_seq_prioq_cell_out(struct snd_seq_prioq *f,
230 struct snd_seq_event_cell *cell;
234 pr_debug("ALSA: seq: snd_seq_prioq_cell_in() called with NULL prioq\n");
237 spin_lock_irqsave(&f->lock, flags);
240 if (cell && current_time && !event_is_ready(&cell->event, current_time))
243 f->head = cell->next;
245 /* reset tail if this was the last element */
253 spin_unlock_irqrestore(&f->lock, flags);
257 /* return number of events available in prioq */
258 int snd_seq_prioq_avail(struct snd_seq_prioq * f)
261 pr_debug("ALSA: seq: snd_seq_prioq_cell_in() called with NULL prioq\n");
267 static inline int prioq_match(struct snd_seq_event_cell *cell,
268 int client, int timestamp)
270 if (cell->event.source.client == client ||
271 cell->event.dest.client == client)
275 switch (cell->event.flags & SNDRV_SEQ_TIME_STAMP_MASK) {
276 case SNDRV_SEQ_TIME_STAMP_TICK:
277 if (cell->event.time.tick)
280 case SNDRV_SEQ_TIME_STAMP_REAL:
281 if (cell->event.time.time.tv_sec ||
282 cell->event.time.time.tv_nsec)
289 /* remove cells for left client */
290 void snd_seq_prioq_leave(struct snd_seq_prioq * f, int client, int timestamp)
292 register struct snd_seq_event_cell *cell, *next;
294 struct snd_seq_event_cell *prev = NULL;
295 struct snd_seq_event_cell *freefirst = NULL, *freeprev = NULL, *freenext;
297 /* collect all removed cells */
298 spin_lock_irqsave(&f->lock, flags);
302 if (prioq_match(cell, client, timestamp)) {
303 /* remove cell from prioq */
304 if (cell == f->head) {
305 f->head = cell->next;
307 prev->next = cell->next;
310 f->tail = cell->next;
312 /* add cell to free list */
314 if (freefirst == NULL) {
317 freeprev->next = cell;
322 pr_debug("ALSA: seq: type = %i, source = %i, dest = %i, "
325 cell->event.source.client,
326 cell->event.dest.client,
333 spin_unlock_irqrestore(&f->lock, flags);
335 /* remove selected cells */
337 freenext = freefirst->next;
338 snd_seq_cell_free(freefirst);
339 freefirst = freenext;
343 static int prioq_remove_match(struct snd_seq_remove_events *info,
344 struct snd_seq_event *ev)
348 if (info->remove_mode & SNDRV_SEQ_REMOVE_DEST) {
349 if (ev->dest.client != info->dest.client ||
350 ev->dest.port != info->dest.port)
353 if (info->remove_mode & SNDRV_SEQ_REMOVE_DEST_CHANNEL) {
354 if (! snd_seq_ev_is_channel_type(ev))
356 /* data.note.channel and data.control.channel are identical */
357 if (ev->data.note.channel != info->channel)
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);
364 res = snd_seq_compare_real_time(&ev->time.time, &info->time.time);
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);
372 res = snd_seq_compare_real_time(&ev->time.time, &info->time.time);
376 if (info->remove_mode & SNDRV_SEQ_REMOVE_EVENT_TYPE) {
377 if (ev->type != info->type)
380 if (info->remove_mode & SNDRV_SEQ_REMOVE_IGNORE_OFF) {
381 /* Do not remove off events */
383 case SNDRV_SEQ_EVENT_NOTEOFF:
384 /* case SNDRV_SEQ_EVENT_SAMPLE_STOP: */
390 if (info->remove_mode & SNDRV_SEQ_REMOVE_TAG_MATCH) {
391 if (info->tag != ev->tag)
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)
402 struct snd_seq_event_cell *cell, *next;
404 struct snd_seq_event_cell *prev = NULL;
405 struct snd_seq_event_cell *freefirst = NULL, *freeprev = NULL, *freenext;
407 /* collect all removed cells */
408 spin_lock_irqsave(&f->lock, flags);
413 if (cell->event.source.client == client &&
414 prioq_remove_match(info, &cell->event)) {
416 /* remove cell from prioq */
417 if (cell == f->head) {
418 f->head = cell->next;
420 prev->next = cell->next;
424 f->tail = cell->next;
427 /* add cell to free list */
429 if (freefirst == NULL) {
432 freeprev->next = cell;
441 spin_unlock_irqrestore(&f->lock, flags);
443 /* remove selected cells */
445 freenext = freefirst->next;
446 snd_seq_cell_free(freefirst);
447 freefirst = freenext;