sound/core/seq/seq_prioq.c

   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