core/seq/seq_prioq.c

0001 // SPDX-License-Identifier: GPL-2.0-or-later
0002 /*
0003  *   ALSA sequencer Priority Queue
0004  *   Copyright (c) 1998-1999 by Frank van de Pol <fvdpol@coil.demon.nl>
0005  */
0006
0007 #include <linux/time.h>
0008 #include <linux/slab.h>
0009 #include <sound/core.h>
0010 #include "seq_timer.h"
0011 #include "seq_prioq.h"
0012
0013
0014 /* Implementation is a simple linked list for now...
0015
0016    This priority queue orders the events on timestamp. For events with an
0017    equeal timestamp the queue behaves as a FIFO.
0018
0019    *
0020    *           +-------+
0021    *  Head --> | first |
0022    *           +-------+
0023    *                 |next
0024    *           +-----v-+
0025    *           |       |
0026    *           +-------+
0027    *                 |
0028    *           +-----v-+
0029    *           |       |
0030    *           +-------+
0031    *                 |
0032    *           +-----v-+
0033    *  Tail --> | last  |
0034    *           +-------+
0035    *
0036
0037  */
0038
0039
0040
0041 /* create new prioq (constructor) */
0042 struct snd_seq_prioq *snd_seq_prioq_new(void)
0043 {
0044     struct snd_seq_prioq *f;
0045
0046     f = kzalloc(sizeof(*f), GFP_KERNEL);
0047     if (!f)
0048         return NULL;
0049
0050     spin_lock_init(&f->lock);
0051     f->head = NULL;
0052     f->tail = NULL;
0053     f->cells = 0;
0054
0055     return f;
0056 }
0057
0058 /* delete prioq (destructor) */
0059 void snd_seq_prioq_delete(struct snd_seq_prioq **fifo)
0060 {
0061     struct snd_seq_prioq *f = *fifo;
0062     *fifo = NULL;
0063
0064     if (f == NULL) {
0065         pr_debug("ALSA: seq: snd_seq_prioq_delete() called with NULL prioq\n");
0066         return;
0067     }
0068
0069     /* release resources...*/
0070     /*....................*/
0071
0072     if (f->cells > 0) {
0073         /* drain prioQ */
0074         while (f->cells > 0)
0075             snd_seq_cell_free(snd_seq_prioq_cell_out(f, NULL));
0076     }
0077
0078     kfree(f);
0079 }
0080
0081
0082
0083
0084 /* compare timestamp between events */
0085 /* return 1 if a >= b; 0 */
0086 static inline int compare_timestamp(struct snd_seq_event *a,
0087                     struct snd_seq_event *b)
0088 {
0089     if ((a->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK) {
0090         /* compare ticks */
0091         return (snd_seq_compare_tick_time(&a->time.tick, &b->time.tick));
0092     } else {
0093         /* compare real time */
0094         return (snd_seq_compare_real_time(&a->time.time, &b->time.time));
0095     }
0096 }
0097
0098 /* compare timestamp between events */
0099 /* return negative if a < b;
0100  *        zero     if a = b;
0101  *        positive if a > b;
0102  */
0103 static inline int compare_timestamp_rel(struct snd_seq_event *a,
0104                     struct snd_seq_event *b)
0105 {
0106     if ((a->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK) {
0107         /* compare ticks */
0108         if (a->time.tick > b->time.tick)
0109             return 1;
0110         else if (a->time.tick == b->time.tick)
0111             return 0;
0112         else
0113             return -1;
0114     } else {
0115         /* compare real time */
0116         if (a->time.time.tv_sec > b->time.time.tv_sec)
0117             return 1;
0118         else if (a->time.time.tv_sec == b->time.time.tv_sec) {
0119             if (a->time.time.tv_nsec > b->time.time.tv_nsec)
0120                 return 1;
0121             else if (a->time.time.tv_nsec == b->time.time.tv_nsec)
0122                 return 0;
0123             else
0124                 return -1;
0125         } else
0126             return -1;
0127     }
0128 }
0129
0130 /* enqueue cell to prioq */
0131 int snd_seq_prioq_cell_in(struct snd_seq_prioq * f,
0132               struct snd_seq_event_cell * cell)
0133 {
0134     struct snd_seq_event_cell *cur, *prev;
0135     unsigned long flags;
0136     int count;
0137     int prior;
0138
0139     if (snd_BUG_ON(!f || !cell))
0140         return -EINVAL;
0141
0142     /* check flags */
0143     prior = (cell->event.flags & SNDRV_SEQ_PRIORITY_MASK);
0144
0145     spin_lock_irqsave(&f->lock, flags);
0146
0147     /* check if this element needs to inserted at the end (ie. ordered
0148        data is inserted) This will be very likeley if a sequencer
0149        application or midi file player is feeding us (sequential) data */
0150     if (f->tail && !prior) {
0151         if (compare_timestamp(&cell->event, &f->tail->event)) {
0152             /* add new cell to tail of the fifo */
0153             f->tail->next = cell;
0154             f->tail = cell;
0155             cell->next = NULL;
0156             f->cells++;
0157             spin_unlock_irqrestore(&f->lock, flags);
0158             return 0;
0159         }
0160     }
0161     /* traverse list of elements to find the place where the new cell is
0162        to be inserted... Note that this is a order n process ! */
0163
0164     prev = NULL;        /* previous cell */
0165     cur = f->head;      /* cursor */
0166
0167     count = 10000; /* FIXME: enough big, isn't it? */
0168     while (cur != NULL) {
0169         /* compare timestamps */
0170         int rel = compare_timestamp_rel(&cell->event, &cur->event);
0171         if (rel < 0)
0172             /* new cell has earlier schedule time, */
0173             break;
0174         else if (rel == 0 && prior)
0175             /* equal schedule time and prior to others */
0176             break;
0177         /* new cell has equal or larger schedule time, */
0178         /* move cursor to next cell */
0179         prev = cur;
0180         cur = cur->next;
0181         if (! --count) {
0182             spin_unlock_irqrestore(&f->lock, flags);
0183             pr_err("ALSA: seq: cannot find a pointer.. infinite loop?\n");
0184             return -EINVAL;
0185         }
0186     }
0187
0188     /* insert it before cursor */
0189     if (prev != NULL)
0190         prev->next = cell;
0191     cell->next = cur;
0192
0193     if (f->head == cur) /* this is the first cell, set head to it */
0194         f->head = cell;
0195     if (cur == NULL) /* reached end of the list */
0196         f->tail = cell;
0197     f->cells++;
0198     spin_unlock_irqrestore(&f->lock, flags);
0199     return 0;
0200 }
0201
0202 /* return 1 if the current time >= event timestamp */
0203 static int event_is_ready(struct snd_seq_event *ev, void *current_time)
0204 {
0205     if ((ev->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK)
0206         return snd_seq_compare_tick_time(current_time, &ev->time.tick);
0207     else
0208         return snd_seq_compare_real_time(current_time, &ev->time.time);
0209 }
0210
0211 /* dequeue cell from prioq */
0212 struct snd_seq_event_cell *snd_seq_prioq_cell_out(struct snd_seq_prioq *f,
0213                           void *current_time)
0214 {
0215     struct snd_seq_event_cell *cell;
0216     unsigned long flags;
0217
0218     if (f == NULL) {
0219         pr_debug("ALSA: seq: snd_seq_prioq_cell_in() called with NULL prioq\n");
0220         return NULL;
0221     }
0222     spin_lock_irqsave(&f->lock, flags);
0223
0224     cell = f->head;
0225     if (cell && current_time && !event_is_ready(&cell->event, current_time))
0226         cell = NULL;
0227     if (cell) {
0228         f->head = cell->next;
0229
0230         /* reset tail if this was the last element */
0231         if (f->tail == cell)
0232             f->tail = NULL;
0233
0234         cell->next = NULL;
0235         f->cells--;
0236     }
0237
0238     spin_unlock_irqrestore(&f->lock, flags);
0239     return cell;
0240 }
0241
0242 /* return number of events available in prioq */
0243 int snd_seq_prioq_avail(struct snd_seq_prioq * f)
0244 {
0245     if (f == NULL) {
0246         pr_debug("ALSA: seq: snd_seq_prioq_cell_in() called with NULL prioq\n");
0247         return 0;
0248     }
0249     return f->cells;
0250 }
0251
0252 static inline int prioq_match(struct snd_seq_event_cell *cell,
0253                   int client, int timestamp)
0254 {
0255     if (cell->event.source.client == client ||
0256         cell->event.dest.client == client)
0257         return 1;
0258     if (!timestamp)
0259         return 0;
0260     switch (cell->event.flags & SNDRV_SEQ_TIME_STAMP_MASK) {
0261     case SNDRV_SEQ_TIME_STAMP_TICK:
0262         if (cell->event.time.tick)
0263             return 1;
0264         break;
0265     case SNDRV_SEQ_TIME_STAMP_REAL:
0266         if (cell->event.time.time.tv_sec ||
0267             cell->event.time.time.tv_nsec)
0268             return 1;
0269         break;
0270     }
0271     return 0;
0272 }
0273
0274 /* remove cells for left client */
0275 void snd_seq_prioq_leave(struct snd_seq_prioq * f, int client, int timestamp)
0276 {
0277     register struct snd_seq_event_cell *cell, *next;
0278     unsigned long flags;
0279     struct snd_seq_event_cell *prev = NULL;
0280     struct snd_seq_event_cell *freefirst = NULL, *freeprev = NULL, *freenext;
0281
0282     /* collect all removed cells */
0283     spin_lock_irqsave(&f->lock, flags);
0284     cell = f->head;
0285     while (cell) {
0286         next = cell->next;
0287         if (prioq_match(cell, client, timestamp)) {
0288             /* remove cell from prioq */
0289             if (cell == f->head) {
0290                 f->head = cell->next;
0291             } else {
0292                 prev->next = cell->next;
0293             }
0294             if (cell == f->tail)
0295                 f->tail = cell->next;
0296             f->cells--;
0297             /* add cell to free list */
0298             cell->next = NULL;
0299             if (freefirst == NULL) {
0300                 freefirst = cell;
0301             } else {
0302                 freeprev->next = cell;
0303             }
0304             freeprev = cell;
0305         } else {
0306 #if 0
0307             pr_debug("ALSA: seq: type = %i, source = %i, dest = %i, "
0308                    "client = %i\n",
0309                 cell->event.type,
0310                 cell->event.source.client,
0311                 cell->event.dest.client,
0312                 client);
0313 #endif
0314             prev = cell;
0315         }
0316         cell = next;
0317     }
0318     spin_unlock_irqrestore(&f->lock, flags);
0319
0320     /* remove selected cells */
0321     while (freefirst) {
0322         freenext = freefirst->next;
0323         snd_seq_cell_free(freefirst);
0324         freefirst = freenext;
0325     }
0326 }
0327
0328 static int prioq_remove_match(struct snd_seq_remove_events *info,
0329                   struct snd_seq_event *ev)
0330 {
0331     int res;
0332
0333     if (info->remove_mode & SNDRV_SEQ_REMOVE_DEST) {
0334         if (ev->dest.client != info->dest.client ||
0335                 ev->dest.port != info->dest.port)
0336             return 0;
0337     }
0338     if (info->remove_mode & SNDRV_SEQ_REMOVE_DEST_CHANNEL) {
0339         if (! snd_seq_ev_is_channel_type(ev))
0340             return 0;
0341         /* data.note.channel and data.control.channel are identical */
0342         if (ev->data.note.channel != info->channel)
0343             return 0;
0344     }
0345     if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_AFTER) {
0346         if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_TICK)
0347             res = snd_seq_compare_tick_time(&ev->time.tick, &info->time.tick);
0348         else
0349             res = snd_seq_compare_real_time(&ev->time.time, &info->time.time);
0350         if (!res)
0351             return 0;
0352     }
0353     if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_BEFORE) {
0354         if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_TICK)
0355             res = snd_seq_compare_tick_time(&ev->time.tick, &info->time.tick);
0356         else
0357             res = snd_seq_compare_real_time(&ev->time.time, &info->time.time);
0358         if (res)
0359             return 0;
0360     }
0361     if (info->remove_mode & SNDRV_SEQ_REMOVE_EVENT_TYPE) {
0362         if (ev->type != info->type)
0363             return 0;
0364     }
0365     if (info->remove_mode & SNDRV_SEQ_REMOVE_IGNORE_OFF) {
0366         /* Do not remove off events */
0367         switch (ev->type) {
0368         case SNDRV_SEQ_EVENT_NOTEOFF:
0369         /* case SNDRV_SEQ_EVENT_SAMPLE_STOP: */
0370             return 0;
0371         default:
0372             break;
0373         }
0374     }
0375     if (info->remove_mode & SNDRV_SEQ_REMOVE_TAG_MATCH) {
0376         if (info->tag != ev->tag)
0377             return 0;
0378     }
0379
0380     return 1;
0381 }
0382
0383 /* remove cells matching remove criteria */
0384 void snd_seq_prioq_remove_events(struct snd_seq_prioq * f, int client,
0385                  struct snd_seq_remove_events *info)
0386 {
0387     struct snd_seq_event_cell *cell, *next;
0388     unsigned long flags;
0389     struct snd_seq_event_cell *prev = NULL;
0390     struct snd_seq_event_cell *freefirst = NULL, *freeprev = NULL, *freenext;
0391
0392     /* collect all removed cells */
0393     spin_lock_irqsave(&f->lock, flags);
0394     cell = f->head;
0395
0396     while (cell) {
0397         next = cell->next;
0398         if (cell->event.source.client == client &&
0399             prioq_remove_match(info, &cell->event)) {
0400
0401             /* remove cell from prioq */
0402             if (cell == f->head) {
0403                 f->head = cell->next;
0404             } else {
0405                 prev->next = cell->next;
0406             }
0407
0408             if (cell == f->tail)
0409                 f->tail = cell->next;
0410             f->cells--;
0411
0412             /* add cell to free list */
0413             cell->next = NULL;
0414             if (freefirst == NULL) {
0415                 freefirst = cell;
0416             } else {
0417                 freeprev->next = cell;
0418             }
0419
0420             freeprev = cell;
0421         } else {
0422             prev = cell;
0423         }
0424         cell = next;
0425     }
0426     spin_unlock_irqrestore(&f->lock, flags);
0427
0428     /* remove selected cells */
0429     while (freefirst) {
0430         freenext = freefirst->next;
0431         snd_seq_cell_free(freefirst);
0432         freefirst = freenext;
0433     }
0434 }
0435
0436