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