xref: /linux/sound/core/seq/seq_prioq.c (revision 24bce201d79807b668bf9d9e0aca801c5c0d5f78) 
1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /*
3  *   ALSA sequencer Priority Queue
4  *   Copyright (c) 1998-1999 by Frank van de Pol <fvdpol@coil.demon.nl>
5  */
6 
7 #include <linux/time.h>
8 #include <linux/slab.h>
9 #include <sound/core.h>
10 #include "seq_timer.h"
11 #include "seq_prioq.h"
12 
13 
14 /* Implementation is a simple linked list for now...
15 
16    This priority queue orders the events on timestamp. For events with an
17    equeal timestamp the queue behaves as a FIFO.
18 
19    *
20    *           +-------+
21    *  Head --> | first |
22    *           +-------+
23    *                 |next
24    *           +-----v-+
25    *           |       |
26    *           +-------+
27    *                 |
28    *           +-----v-+
29    *           |       |
30    *           +-------+
31    *                 |
32    *           +-----v-+
33    *  Tail --> | last  |
34    *           +-------+
35    *
36 
37  */
38 
39 
40 
41 /* create new prioq (constructor) */
42 struct snd_seq_prioq *snd_seq_prioq_new(void)
43 {
44 	struct snd_seq_prioq *f;
45 
46 	f = kzalloc(sizeof(*f), GFP_KERNEL);
47 	if (!f)
48 		return NULL;
49 
50 	spin_lock_init(&f->lock);
51 	f->head = NULL;
52 	f->tail = NULL;
53 	f->cells = 0;
54 
55 	return f;
56 }
57 
58 /* delete prioq (destructor) */
59 void snd_seq_prioq_delete(struct snd_seq_prioq **fifo)
60 {
61 	struct snd_seq_prioq *f = *fifo;
62 	*fifo = NULL;
63 
64 	if (f == NULL) {
65 		pr_debug("ALSA: seq: snd_seq_prioq_delete() called with NULL prioq\n");
66 		return;
67 	}
68 
69 	/* release resources...*/
70 	/*....................*/
71 
72 	if (f->cells > 0) {
73 		/* drain prioQ */
74 		while (f->cells > 0)
75 			snd_seq_cell_free(snd_seq_prioq_cell_out(f, NULL));
76 	}
77 
78 	kfree(f);
79 }
80 
81 
82 
83 
84 /* compare timestamp between events */
85 /* return 1 if a >= b; 0 */
86 static inline int compare_timestamp(struct snd_seq_event *a,
87 				    struct snd_seq_event *b)
88 {
89 	if ((a->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK) {
90 		/* compare ticks */
91 		return (snd_seq_compare_tick_time(&a->time.tick, &b->time.tick));
92 	} else {
93 		/* compare real time */
94 		return (snd_seq_compare_real_time(&a->time.time, &b->time.time));
95 	}
96 }
97 
98 /* compare timestamp between events */
99 /* return negative if a < b;
100  *        zero     if a = b;
101  *        positive if a > b;
102  */
103 static inline int compare_timestamp_rel(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 		if (a->time.tick > b->time.tick)
109 			return 1;
110 		else if (a->time.tick == b->time.tick)
111 			return 0;
112 		else
113 			return -1;
114 	} else {
115 		/* compare real time */
116 		if (a->time.time.tv_sec > b->time.time.tv_sec)
117 			return 1;
118 		else if (a->time.time.tv_sec == b->time.time.tv_sec) {
119 			if (a->time.time.tv_nsec > b->time.time.tv_nsec)
120 				return 1;
121 			else if (a->time.time.tv_nsec == b->time.time.tv_nsec)
122 				return 0;
123 			else
124 				return -1;
125 		} else
126 			return -1;
127 	}
128 }
129 
130 /* enqueue cell to prioq */
131 int snd_seq_prioq_cell_in(struct snd_seq_prioq * f,
132 			  struct snd_seq_event_cell * cell)
133 {
134 	struct snd_seq_event_cell *cur, *prev;
135 	unsigned long flags;
136 	int count;
137 	int prior;
138 
139 	if (snd_BUG_ON(!f || !cell))
140 		return -EINVAL;
141 
142 	/* check flags */
143 	prior = (cell->event.flags & SNDRV_SEQ_PRIORITY_MASK);
144 
145 	spin_lock_irqsave(&f->lock, flags);
146 
147 	/* check if this element needs to inserted at the end (ie. ordered
148 	   data is inserted) This will be very likeley if a sequencer
149 	   application or midi file player is feeding us (sequential) data */
150 	if (f->tail && !prior) {
151 		if (compare_timestamp(&cell->event, &f->tail->event)) {
152 			/* add new cell to tail of the fifo */
153 			f->tail->next = cell;
154 			f->tail = cell;
155 			cell->next = NULL;
156 			f->cells++;
157 			spin_unlock_irqrestore(&f->lock, flags);
158 			return 0;
159 		}
160 	}
161 	/* traverse list of elements to find the place where the new cell is
162 	   to be inserted... Note that this is a order n process ! */
163 
164 	prev = NULL;		/* previous cell */
165 	cur = f->head;		/* cursor */
166 
167 	count = 10000; /* FIXME: enough big, isn't it? */
168 	while (cur != NULL) {
169 		/* compare timestamps */
170 		int rel = compare_timestamp_rel(&cell->event, &cur->event);
171 		if (rel < 0)
172 			/* new cell has earlier schedule time, */
173 			break;
174 		else if (rel == 0 && prior)
175 			/* equal schedule time and prior to others */
176 			break;
177 		/* new cell has equal or larger schedule time, */
178 		/* move cursor to next cell */
179 		prev = cur;
180 		cur = cur->next;
181 		if (! --count) {
182 			spin_unlock_irqrestore(&f->lock, flags);
183 			pr_err("ALSA: seq: cannot find a pointer.. infinite loop?\n");
184 			return -EINVAL;
185 		}
186 	}
187 
188 	/* insert it before cursor */
189 	if (prev != NULL)
190 		prev->next = cell;
191 	cell->next = cur;
192 
193 	if (f->head == cur) /* this is the first cell, set head to it */
194 		f->head = cell;
195 	if (cur == NULL) /* reached end of the list */
196 		f->tail = cell;
197 	f->cells++;
198 	spin_unlock_irqrestore(&f->lock, flags);
199 	return 0;
200 }
201 
202 /* return 1 if the current time >= event timestamp */
203 static int event_is_ready(struct snd_seq_event *ev, void *current_time)
204 {
205 	if ((ev->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK)
206 		return snd_seq_compare_tick_time(current_time, &ev->time.tick);
207 	else
208 		return snd_seq_compare_real_time(current_time, &ev->time.time);
209 }
210 
211 /* dequeue cell from prioq */
212 struct snd_seq_event_cell *snd_seq_prioq_cell_out(struct snd_seq_prioq *f,
213 						  void *current_time)
214 {
215 	struct snd_seq_event_cell *cell;
216 	unsigned long flags;
217 
218 	if (f == NULL) {
219 		pr_debug("ALSA: seq: snd_seq_prioq_cell_in() called with NULL prioq\n");
220 		return NULL;
221 	}
222 	spin_lock_irqsave(&f->lock, flags);
223 
224 	cell = f->head;
225 	if (cell && current_time && !event_is_ready(&cell->event, current_time))
226 		cell = NULL;
227 	if (cell) {
228 		f->head = cell->next;
229 
230 		/* reset tail if this was the last element */
231 		if (f->tail == cell)
232 			f->tail = NULL;
233 
234 		cell->next = NULL;
235 		f->cells--;
236 	}
237 
238 	spin_unlock_irqrestore(&f->lock, flags);
239 	return cell;
240 }
241 
242 /* return number of events available in prioq */
243 int snd_seq_prioq_avail(struct snd_seq_prioq * f)
244 {
245 	if (f == NULL) {
246 		pr_debug("ALSA: seq: snd_seq_prioq_cell_in() called with NULL prioq\n");
247 		return 0;
248 	}
249 	return f->cells;
250 }
251 
252 static inline int prioq_match(struct snd_seq_event_cell *cell,
253 			      int client, int timestamp)
254 {
255 	if (cell->event.source.client == client ||
256 	    cell->event.dest.client == client)
257 		return 1;
258 	if (!timestamp)
259 		return 0;
260 	switch (cell->event.flags & SNDRV_SEQ_TIME_STAMP_MASK) {
261 	case SNDRV_SEQ_TIME_STAMP_TICK:
262 		if (cell->event.time.tick)
263 			return 1;
264 		break;
265 	case SNDRV_SEQ_TIME_STAMP_REAL:
266 		if (cell->event.time.time.tv_sec ||
267 		    cell->event.time.time.tv_nsec)
268 			return 1;
269 		break;
270 	}
271 	return 0;
272 }
273 
274 /* remove cells for left client */
275 void snd_seq_prioq_leave(struct snd_seq_prioq * f, int client, int timestamp)
276 {
277 	register struct snd_seq_event_cell *cell, *next;
278 	unsigned long flags;
279 	struct snd_seq_event_cell *prev = NULL;
280 	struct snd_seq_event_cell *freefirst = NULL, *freeprev = NULL, *freenext;
281 
282 	/* collect all removed cells */
283 	spin_lock_irqsave(&f->lock, flags);
284 	cell = f->head;
285 	while (cell) {
286 		next = cell->next;
287 		if (prioq_match(cell, client, timestamp)) {
288 			/* remove cell from prioq */
289 			if (cell == f->head) {
290 				f->head = cell->next;
291 			} else {
292 				prev->next = cell->next;
293 			}
294 			if (cell == f->tail)
295 				f->tail = cell->next;
296 			f->cells--;
297 			/* add cell to free list */
298 			cell->next = NULL;
299 			if (freefirst == NULL) {
300 				freefirst = cell;
301 			} else {
302 				freeprev->next = cell;
303 			}
304 			freeprev = cell;
305 		} else {
306 #if 0
307 			pr_debug("ALSA: seq: type = %i, source = %i, dest = %i, "
308 			       "client = %i\n",
309 				cell->event.type,
310 				cell->event.source.client,
311 				cell->event.dest.client,
312 				client);
313 #endif
314 			prev = cell;
315 		}
316 		cell = next;
317 	}
318 	spin_unlock_irqrestore(&f->lock, flags);
319 
320 	/* remove selected cells */
321 	while (freefirst) {
322 		freenext = freefirst->next;
323 		snd_seq_cell_free(freefirst);
324 		freefirst = freenext;
325 	}
326 }
327 
328 static int prioq_remove_match(struct snd_seq_remove_events *info,
329 			      struct snd_seq_event *ev)
330 {
331 	int res;
332 
333 	if (info->remove_mode & SNDRV_SEQ_REMOVE_DEST) {
334 		if (ev->dest.client != info->dest.client ||
335 				ev->dest.port != info->dest.port)
336 			return 0;
337 	}
338 	if (info->remove_mode & SNDRV_SEQ_REMOVE_DEST_CHANNEL) {
339 		if (! snd_seq_ev_is_channel_type(ev))
340 			return 0;
341 		/* data.note.channel and data.control.channel are identical */
342 		if (ev->data.note.channel != info->channel)
343 			return 0;
344 	}
345 	if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_AFTER) {
346 		if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_TICK)
347 			res = snd_seq_compare_tick_time(&ev->time.tick, &info->time.tick);
348 		else
349 			res = snd_seq_compare_real_time(&ev->time.time, &info->time.time);
350 		if (!res)
351 			return 0;
352 	}
353 	if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_BEFORE) {
354 		if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_TICK)
355 			res = snd_seq_compare_tick_time(&ev->time.tick, &info->time.tick);
356 		else
357 			res = snd_seq_compare_real_time(&ev->time.time, &info->time.time);
358 		if (res)
359 			return 0;
360 	}
361 	if (info->remove_mode & SNDRV_SEQ_REMOVE_EVENT_TYPE) {
362 		if (ev->type != info->type)
363 			return 0;
364 	}
365 	if (info->remove_mode & SNDRV_SEQ_REMOVE_IGNORE_OFF) {
366 		/* Do not remove off events */
367 		switch (ev->type) {
368 		case SNDRV_SEQ_EVENT_NOTEOFF:
369 		/* case SNDRV_SEQ_EVENT_SAMPLE_STOP: */
370 			return 0;
371 		default:
372 			break;
373 		}
374 	}
375 	if (info->remove_mode & SNDRV_SEQ_REMOVE_TAG_MATCH) {
376 		if (info->tag != ev->tag)
377 			return 0;
378 	}
379 
380 	return 1;
381 }
382 
383 /* remove cells matching remove criteria */
384 void snd_seq_prioq_remove_events(struct snd_seq_prioq * f, int client,
385 				 struct snd_seq_remove_events *info)
386 {
387 	struct snd_seq_event_cell *cell, *next;
388 	unsigned long flags;
389 	struct snd_seq_event_cell *prev = NULL;
390 	struct snd_seq_event_cell *freefirst = NULL, *freeprev = NULL, *freenext;
391 
392 	/* collect all removed cells */
393 	spin_lock_irqsave(&f->lock, flags);
394 	cell = f->head;
395 
396 	while (cell) {
397 		next = cell->next;
398 		if (cell->event.source.client == client &&
399 			prioq_remove_match(info, &cell->event)) {
400 
401 			/* remove cell from prioq */
402 			if (cell == f->head) {
403 				f->head = cell->next;
404 			} else {
405 				prev->next = cell->next;
406 			}
407 
408 			if (cell == f->tail)
409 				f->tail = cell->next;
410 			f->cells--;
411 
412 			/* add cell to free list */
413 			cell->next = NULL;
414 			if (freefirst == NULL) {
415 				freefirst = cell;
416 			} else {
417 				freeprev->next = cell;
418 			}
419 
420 			freeprev = cell;
421 		} else {
422 			prev = cell;
423 		}
424 		cell = next;
425 	}
426 	spin_unlock_irqrestore(&f->lock, flags);
427 
428 	/* remove selected cells */
429 	while (freefirst) {
430 		freenext = freefirst->next;
431 		snd_seq_cell_free(freefirst);
432 		freefirst = freenext;
433 	}
434 }
435 
436 
437