xref: /openbmc/linux/sound/core/seq/seq_prioq.c (revision 1da177e4) 
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) */
58 prioq_t *snd_seq_prioq_new(void)
59 {
60 	prioq_t *f;
61 
62 	f = kcalloc(1, 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) */
77 void snd_seq_prioq_delete(prioq_t **fifo)
78 {
79 	prioq_t *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 */
104 static inline int compare_timestamp(snd_seq_event_t * a, snd_seq_event_t * 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  */
120 static inline int compare_timestamp_rel(snd_seq_event_t *a, snd_seq_event_t *b)
121 {
122 	if ((a->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK) {
123 		/* compare ticks */
124 		if (a->time.tick > b->time.tick)
125 			return 1;
126 		else if (a->time.tick == b->time.tick)
127 			return 0;
128 		else
129 			return -1;
130 	} else {
131 		/* compare real time */
132 		if (a->time.time.tv_sec > b->time.time.tv_sec)
133 			return 1;
134 		else if (a->time.time.tv_sec == b->time.time.tv_sec) {
135 			if (a->time.time.tv_nsec > b->time.time.tv_nsec)
136 				return 1;
137 			else if (a->time.time.tv_nsec == b->time.time.tv_nsec)
138 				return 0;
139 			else
140 				return -1;
141 		} else
142 			return -1;
143 	}
144 }
145 
146 /* enqueue cell to prioq */
147 int snd_seq_prioq_cell_in(prioq_t * f, snd_seq_event_cell_t * cell)
148 {
149 	snd_seq_event_cell_t *cur, *prev;
150 	unsigned long flags;
151 	int count;
152 	int prior;
153 
154 	snd_assert(f, return -EINVAL);
155 	snd_assert(cell, 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 			snd_printk(KERN_ERR "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 */
218 snd_seq_event_cell_t *snd_seq_prioq_cell_out(prioq_t * f)
219 {
220 	snd_seq_event_cell_t *cell;
221 	unsigned long flags;
222 
223 	if (f == NULL) {
224 		snd_printd("oops: 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 */
246 int snd_seq_prioq_avail(prioq_t * f)
247 {
248 	if (f == NULL) {
249 		snd_printd("oops: 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 */
257 snd_seq_event_cell_t *snd_seq_prioq_cell_peek(prioq_t * f)
258 {
259 	if (f == NULL) {
260 		snd_printd("oops: snd_seq_prioq_cell_in() called with NULL prioq\n");
261 		return NULL;
262 	}
263 	return f->head;
264 }
265 
266 
267 static inline int prioq_match(snd_seq_event_cell_t *cell, int client, int timestamp)
268 {
269 	if (cell->event.source.client == client ||
270 	    cell->event.dest.client == client)
271 		return 1;
272 	if (!timestamp)
273 		return 0;
274 	switch (cell->event.flags & SNDRV_SEQ_TIME_STAMP_MASK) {
275 	case SNDRV_SEQ_TIME_STAMP_TICK:
276 		if (cell->event.time.tick)
277 			return 1;
278 		break;
279 	case SNDRV_SEQ_TIME_STAMP_REAL:
280 		if (cell->event.time.time.tv_sec ||
281 		    cell->event.time.time.tv_nsec)
282 			return 1;
283 		break;
284 	}
285 	return 0;
286 }
287 
288 /* remove cells for left client */
289 void snd_seq_prioq_leave(prioq_t * f, int client, int timestamp)
290 {
291 	register snd_seq_event_cell_t *cell, *next;
292 	unsigned long flags;
293 	snd_seq_event_cell_t *prev = NULL;
294 	snd_seq_event_cell_t *freefirst = NULL, *freeprev = NULL, *freenext;
295 
296 	/* collect all removed cells */
297 	spin_lock_irqsave(&f->lock, flags);
298 	cell = f->head;
299 	while (cell) {
300 		next = cell->next;
301 		if (prioq_match(cell, client, timestamp)) {
302 			/* remove cell from prioq */
303 			if (cell == f->head) {
304 				f->head = cell->next;
305 			} else {
306 				prev->next = cell->next;
307 			}
308 			if (cell == f->tail)
309 				f->tail = cell->next;
310 			f->cells--;
311 			/* add cell to free list */
312 			cell->next = NULL;
313 			if (freefirst == NULL) {
314 				freefirst = cell;
315 			} else {
316 				freeprev->next = cell;
317 			}
318 			freeprev = cell;
319 		} else {
320 #if 0
321 			printk("type = %i, source = %i, dest = %i, client = %i\n",
322 				cell->event.type,
323 				cell->event.source.client,
324 				cell->event.dest.client,
325 				client);
326 #endif
327 			prev = cell;
328 		}
329 		cell = next;
330 	}
331 	spin_unlock_irqrestore(&f->lock, flags);
332 
333 	/* remove selected cells */
334 	while (freefirst) {
335 		freenext = freefirst->next;
336 		snd_seq_cell_free(freefirst);
337 		freefirst = freenext;
338 	}
339 }
340 
341 static int prioq_remove_match(snd_seq_remove_events_t *info,
342 	snd_seq_event_t *ev)
343 {
344 	int res;
345 
346 	if (info->remove_mode & SNDRV_SEQ_REMOVE_DEST) {
347 		if (ev->dest.client != info->dest.client ||
348 				ev->dest.port != info->dest.port)
349 			return 0;
350 	}
351 	if (info->remove_mode & SNDRV_SEQ_REMOVE_DEST_CHANNEL) {
352 		if (! snd_seq_ev_is_channel_type(ev))
353 			return 0;
354 		/* data.note.channel and data.control.channel are identical */
355 		if (ev->data.note.channel != info->channel)
356 			return 0;
357 	}
358 	if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_AFTER) {
359 		if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_TICK)
360 			res = snd_seq_compare_tick_time(&ev->time.tick, &info->time.tick);
361 		else
362 			res = snd_seq_compare_real_time(&ev->time.time, &info->time.time);
363 		if (!res)
364 			return 0;
365 	}
366 	if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_BEFORE) {
367 		if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_TICK)
368 			res = snd_seq_compare_tick_time(&ev->time.tick, &info->time.tick);
369 		else
370 			res = snd_seq_compare_real_time(&ev->time.time, &info->time.time);
371 		if (res)
372 			return 0;
373 	}
374 	if (info->remove_mode & SNDRV_SEQ_REMOVE_EVENT_TYPE) {
375 		if (ev->type != info->type)
376 			return 0;
377 	}
378 	if (info->remove_mode & SNDRV_SEQ_REMOVE_IGNORE_OFF) {
379 		/* Do not remove off events */
380 		switch (ev->type) {
381 		case SNDRV_SEQ_EVENT_NOTEOFF:
382 		/* case SNDRV_SEQ_EVENT_SAMPLE_STOP: */
383 			return 0;
384 		default:
385 			break;
386 		}
387 	}
388 	if (info->remove_mode & SNDRV_SEQ_REMOVE_TAG_MATCH) {
389 		if (info->tag != ev->tag)
390 			return 0;
391 	}
392 
393 	return 1;
394 }
395 
396 /* remove cells matching remove criteria */
397 void snd_seq_prioq_remove_events(prioq_t * f, int client,
398 	snd_seq_remove_events_t *info)
399 {
400 	register snd_seq_event_cell_t *cell, *next;
401 	unsigned long flags;
402 	snd_seq_event_cell_t *prev = NULL;
403 	snd_seq_event_cell_t *freefirst = NULL, *freeprev = NULL, *freenext;
404 
405 	/* collect all removed cells */
406 	spin_lock_irqsave(&f->lock, flags);
407 	cell = f->head;
408 
409 	while (cell) {
410 		next = cell->next;
411 		if (cell->event.source.client == client &&
412 			prioq_remove_match(info, &cell->event)) {
413 
414 			/* remove cell from prioq */
415 			if (cell == f->head) {
416 				f->head = cell->next;
417 			} else {
418 				prev->next = cell->next;
419 			}
420 
421 			if (cell == f->tail)
422 				f->tail = cell->next;
423 			f->cells--;
424 
425 			/* add cell to free list */
426 			cell->next = NULL;
427 			if (freefirst == NULL) {
428 				freefirst = cell;
429 			} else {
430 				freeprev->next = cell;
431 			}
432 
433 			freeprev = cell;
434 		} else {
435 			prev = cell;
436 		}
437 		cell = next;
438 	}
439 	spin_unlock_irqrestore(&f->lock, flags);
440 
441 	/* remove selected cells */
442 	while (freefirst) {
443 		freenext = freefirst->next;
444 		snd_seq_cell_free(freefirst);
445 		freefirst = freenext;
446 	}
447 }
448 
449 
450