401 lines · c
1// SPDX-License-Identifier: GPL-2.0-or-later2/*3 * ALSA sequencer Priority Queue4 * 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 an17 equeal timestamp the queue behaves as a FIFO. 18 19 *20 * +-------+21 * Head --> | first |22 * +-------+23 * |next24 * +-----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) */42struct 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) */59void 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 */86static 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 */103static 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 else113 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 else124 return -1;125 } else126 return -1;127 }128}129 130/* enqueue cell to prioq */131int 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 int count;136 int prior;137 138 if (snd_BUG_ON(!f || !cell))139 return -EINVAL;140 141 /* check flags */142 prior = (cell->event.flags & SNDRV_SEQ_PRIORITY_MASK);143 144 guard(spinlock_irqsave)(&f->lock);145 146 /* check if this element needs to inserted at the end (ie. ordered 147 data is inserted) This will be very likeley if a sequencer 148 application or midi file player is feeding us (sequential) data */149 if (f->tail && !prior) {150 if (compare_timestamp(&cell->event, &f->tail->event)) {151 /* add new cell to tail of the fifo */152 f->tail->next = cell;153 f->tail = cell;154 cell->next = NULL;155 f->cells++;156 return 0;157 }158 }159 /* traverse list of elements to find the place where the new cell is160 to be inserted... Note that this is a order n process ! */161 162 prev = NULL; /* previous cell */163 cur = f->head; /* cursor */164 165 count = 10000; /* FIXME: enough big, isn't it? */166 while (cur != NULL) {167 /* compare timestamps */168 int rel = compare_timestamp_rel(&cell->event, &cur->event);169 if (rel < 0)170 /* new cell has earlier schedule time, */171 break;172 else if (rel == 0 && prior)173 /* equal schedule time and prior to others */174 break;175 /* new cell has equal or larger schedule time, */176 /* move cursor to next cell */177 prev = cur;178 cur = cur->next;179 if (! --count) {180 pr_err("ALSA: seq: cannot find a pointer.. infinite loop?\n");181 return -EINVAL;182 }183 }184 185 /* insert it before cursor */186 if (prev != NULL)187 prev->next = cell;188 cell->next = cur;189 190 if (f->head == cur) /* this is the first cell, set head to it */191 f->head = cell;192 if (cur == NULL) /* reached end of the list */193 f->tail = cell;194 f->cells++;195 return 0;196}197 198/* return 1 if the current time >= event timestamp */199static int event_is_ready(struct snd_seq_event *ev, void *current_time)200{201 if ((ev->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK)202 return snd_seq_compare_tick_time(current_time, &ev->time.tick);203 else204 return snd_seq_compare_real_time(current_time, &ev->time.time);205}206 207/* dequeue cell from prioq */208struct snd_seq_event_cell *snd_seq_prioq_cell_out(struct snd_seq_prioq *f,209 void *current_time)210{211 struct snd_seq_event_cell *cell;212 213 if (f == NULL) {214 pr_debug("ALSA: seq: snd_seq_prioq_cell_in() called with NULL prioq\n");215 return NULL;216 }217 218 guard(spinlock_irqsave)(&f->lock);219 cell = f->head;220 if (cell && current_time && !event_is_ready(&cell->event, current_time))221 cell = NULL;222 if (cell) {223 f->head = cell->next;224 225 /* reset tail if this was the last element */226 if (f->tail == cell)227 f->tail = NULL;228 229 cell->next = NULL;230 f->cells--;231 }232 233 return cell;234}235 236/* return number of events available in prioq */237int snd_seq_prioq_avail(struct snd_seq_prioq * f)238{239 if (f == NULL) {240 pr_debug("ALSA: seq: snd_seq_prioq_cell_in() called with NULL prioq\n");241 return 0;242 }243 return f->cells;244}245 246/* remove cells matching with the condition */247static void prioq_remove_cells(struct snd_seq_prioq *f,248 bool (*match)(struct snd_seq_event_cell *cell,249 void *arg),250 void *arg)251{252 register struct snd_seq_event_cell *cell, *next;253 struct snd_seq_event_cell *prev = NULL;254 struct snd_seq_event_cell *freefirst = NULL, *freeprev = NULL, *freenext;255 256 /* collect all removed cells */257 scoped_guard(spinlock_irqsave, &f->lock) {258 for (cell = f->head; cell; cell = next) {259 next = cell->next;260 if (!match(cell, arg)) {261 prev = cell;262 continue;263 }264 265 /* remove cell from prioq */266 if (cell == f->head)267 f->head = cell->next;268 else269 prev->next = cell->next;270 if (cell == f->tail)271 f->tail = cell->next;272 f->cells--;273 274 /* add cell to free list */275 cell->next = NULL;276 if (freefirst == NULL)277 freefirst = cell;278 else279 freeprev->next = cell;280 freeprev = cell;281 }282 }283 284 /* remove selected cells */285 while (freefirst) {286 freenext = freefirst->next;287 snd_seq_cell_free(freefirst);288 freefirst = freenext;289 }290}291 292struct prioq_match_arg {293 int client;294 int timestamp;295};296 297static inline bool prioq_match(struct snd_seq_event_cell *cell, void *arg)298{299 struct prioq_match_arg *v = arg;300 301 if (cell->event.source.client == v->client ||302 cell->event.dest.client == v->client)303 return true;304 if (!v->timestamp)305 return false;306 switch (cell->event.flags & SNDRV_SEQ_TIME_STAMP_MASK) {307 case SNDRV_SEQ_TIME_STAMP_TICK:308 if (cell->event.time.tick)309 return true;310 break;311 case SNDRV_SEQ_TIME_STAMP_REAL:312 if (cell->event.time.time.tv_sec ||313 cell->event.time.time.tv_nsec)314 return true;315 break;316 }317 return false;318}319 320/* remove cells for left client */321void snd_seq_prioq_leave(struct snd_seq_prioq *f, int client, int timestamp)322{323 struct prioq_match_arg arg = { client, timestamp };324 325 return prioq_remove_cells(f, prioq_match, &arg);326}327 328struct prioq_remove_match_arg {329 int client;330 struct snd_seq_remove_events *info;331};332 333static bool prioq_remove_match(struct snd_seq_event_cell *cell, void *arg)334{335 struct prioq_remove_match_arg *v = arg;336 struct snd_seq_event *ev = &cell->event;337 struct snd_seq_remove_events *info = v->info;338 int res;339 340 if (ev->source.client != v->client)341 return false;342 343 if (info->remove_mode & SNDRV_SEQ_REMOVE_DEST) {344 if (ev->dest.client != info->dest.client ||345 ev->dest.port != info->dest.port)346 return false;347 }348 if (info->remove_mode & SNDRV_SEQ_REMOVE_DEST_CHANNEL) {349 if (! snd_seq_ev_is_channel_type(ev))350 return false;351 /* data.note.channel and data.control.channel are identical */352 if (ev->data.note.channel != info->channel)353 return false;354 }355 if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_AFTER) {356 if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_TICK)357 res = snd_seq_compare_tick_time(&ev->time.tick, &info->time.tick);358 else359 res = snd_seq_compare_real_time(&ev->time.time, &info->time.time);360 if (!res)361 return false;362 }363 if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_BEFORE) {364 if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_TICK)365 res = snd_seq_compare_tick_time(&ev->time.tick, &info->time.tick);366 else367 res = snd_seq_compare_real_time(&ev->time.time, &info->time.time);368 if (res)369 return false;370 }371 if (info->remove_mode & SNDRV_SEQ_REMOVE_EVENT_TYPE) {372 if (ev->type != info->type)373 return false;374 }375 if (info->remove_mode & SNDRV_SEQ_REMOVE_IGNORE_OFF) {376 /* Do not remove off events */377 switch (ev->type) {378 case SNDRV_SEQ_EVENT_NOTEOFF:379 /* case SNDRV_SEQ_EVENT_SAMPLE_STOP: */380 return false;381 default:382 break;383 }384 }385 if (info->remove_mode & SNDRV_SEQ_REMOVE_TAG_MATCH) {386 if (info->tag != ev->tag)387 return false;388 }389 390 return true;391}392 393/* remove cells matching remove criteria */394void snd_seq_prioq_remove_events(struct snd_seq_prioq * f, int client,395 struct snd_seq_remove_events *info)396{397 struct prioq_remove_match_arg arg = { client, info };398 399 return prioq_remove_cells(f, prioq_remove_match, &arg);400}401