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) */
57struct 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) */
74void 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 */
101static 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 */
118static 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 */
146int 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 */
218struct 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 */
246int 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 */
257struct 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
267static 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 */
290void 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
343static 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 */
399void 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