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