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) */
snd_seq_prioq_new(void)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) */
snd_seq_prioq_delete(struct snd_seq_prioq ** fifo)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 */
compare_timestamp(struct snd_seq_event * a,struct snd_seq_event * b)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 */
compare_timestamp_rel(struct snd_seq_event * a,struct snd_seq_event * b)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 */
snd_seq_prioq_cell_in(struct snd_seq_prioq * f,struct snd_seq_event_cell * cell)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 */
event_is_ready(struct snd_seq_event * ev,void * current_time)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 */
snd_seq_prioq_cell_out(struct snd_seq_prioq * f,void * current_time)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 */
snd_seq_prioq_avail(struct snd_seq_prioq * f)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
prioq_match(struct snd_seq_event_cell * cell,int client,int timestamp)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 */
snd_seq_prioq_leave(struct snd_seq_prioq * f,int client,int timestamp)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
prioq_remove_match(struct snd_seq_remove_events * info,struct snd_seq_event * ev)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 */
snd_seq_prioq_remove_events(struct snd_seq_prioq * f,int client,struct snd_seq_remove_events * info)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