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