~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/sound/core/seq/seq_prioq.c

Version: ~ [ linux-5.2-rc1 ] ~ [ linux-5.1.2 ] ~ [ linux-5.0.16 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.43 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.119 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.176 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.179 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.139 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.67 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.39.4 ] ~ [ linux-2.6.38.8 ] ~ [ linux-2.6.37.6 ] ~ [ linux-2.6.36.4 ] ~ [ linux-2.6.35.14 ] ~ [ linux-2.6.34.15 ] ~ [ linux-2.6.33.20 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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 <linux/time.h>
 23 #include <linux/slab.h>
 24 #include <sound/core.h>
 25 #include "seq_timer.h"
 26 #include "seq_prioq.h"
 27 
 28 
 29 /* Implementation is a simple linked list for now...
 30 
 31    This priority queue orders the events on timestamp. For events with an
 32    equeal timestamp the queue behaves as a FIFO. 
 33 
 34    *
 35    *           +-------+
 36    *  Head --> | first |
 37    *           +-------+
 38    *                 |next
 39    *           +-----v-+
 40    *           |       |
 41    *           +-------+
 42    *                 |
 43    *           +-----v-+
 44    *           |       |
 45    *           +-------+
 46    *                 |
 47    *           +-----v-+
 48    *  Tail --> | last  |
 49    *           +-------+
 50    *
 51 
 52  */
 53 
 54 
 55 
 56 /* create new prioq (constructor) */
 57 struct snd_seq_prioq *snd_seq_prioq_new(void)
 58 {
 59         struct snd_seq_prioq *f;
 60 
 61         f = kzalloc(sizeof(*f), GFP_KERNEL);
 62         if (!f)
 63                 return NULL;
 64         
 65         spin_lock_init(&f->lock);
 66         f->head = NULL;
 67         f->tail = NULL;
 68         f->cells = 0;
 69         
 70         return f;
 71 }
 72 
 73 /* delete prioq (destructor) */
 74 void snd_seq_prioq_delete(struct snd_seq_prioq **fifo)
 75 {
 76         struct snd_seq_prioq *f = *fifo;
 77         *fifo = NULL;
 78 
 79         if (f == NULL) {
 80                 pr_debug("ALSA: seq: snd_seq_prioq_delete() called with NULL prioq\n");
 81                 return;
 82         }
 83 
 84         /* release resources...*/
 85         /*....................*/
 86         
 87         if (f->cells > 0) {
 88                 /* drain prioQ */
 89                 while (f->cells > 0)
 90                         snd_seq_cell_free(snd_seq_prioq_cell_out(f));
 91         }
 92         
 93         kfree(f);
 94 }
 95 
 96 
 97 
 98 
 99 /* compare timestamp between events */
100 /* return 1 if a >= b; 0 */
101 static inline int compare_timestamp(struct snd_seq_event *a,
102                                     struct snd_seq_event *b)
103 {
104         if ((a->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK) {
105                 /* compare ticks */
106                 return (snd_seq_compare_tick_time(&a->time.tick, &b->time.tick));
107         } else {
108                 /* compare real time */
109                 return (snd_seq_compare_real_time(&a->time.time, &b->time.time));
110         }
111 }
112 
113 /* compare timestamp between events */
114 /* return negative if a < b;
115  *        zero     if a = b;
116  *        positive if a > b;
117  */
118 static inline int compare_timestamp_rel(struct snd_seq_event *a,
119                                         struct snd_seq_event *b)
120 {
121         if ((a->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK) {
122                 /* compare ticks */
123                 if (a->time.tick > b->time.tick)
124                         return 1;
125                 else if (a->time.tick == b->time.tick)
126                         return 0;
127                 else
128                         return -1;
129         } else {
130                 /* compare real time */
131                 if (a->time.time.tv_sec > b->time.time.tv_sec)
132                         return 1;
133                 else if (a->time.time.tv_sec == b->time.time.tv_sec) {
134                         if (a->time.time.tv_nsec > b->time.time.tv_nsec)
135                                 return 1;
136                         else if (a->time.time.tv_nsec == b->time.time.tv_nsec)
137                                 return 0;
138                         else
139                                 return -1;
140                 } else
141                         return -1;
142         }
143 }
144 
145 /* enqueue cell to prioq */
146 int snd_seq_prioq_cell_in(struct snd_seq_prioq * f,
147                           struct snd_seq_event_cell * cell)
148 {
149         struct snd_seq_event_cell *cur, *prev;
150         unsigned long flags;
151         int count;
152         int prior;
153 
154         if (snd_BUG_ON(!f || !cell))
155                 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                         pr_err("ALSA: seq: 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 struct snd_seq_event_cell *snd_seq_prioq_cell_out(struct snd_seq_prioq *f)
219 {
220         struct snd_seq_event_cell *cell;
221         unsigned long flags;
222 
223         if (f == NULL) {
224                 pr_debug("ALSA: seq: 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(struct snd_seq_prioq * f)
247 {
248         if (f == NULL) {
249                 pr_debug("ALSA: seq: 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 struct snd_seq_event_cell *snd_seq_prioq_cell_peek(struct snd_seq_prioq * f)
258 {
259         if (f == NULL) {
260                 pr_debug("ALSA: seq: 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(struct snd_seq_event_cell *cell,
268                               int client, int timestamp)
269 {
270         if (cell->event.source.client == client ||
271             cell->event.dest.client == client)
272                 return 1;
273         if (!timestamp)
274                 return 0;
275         switch (cell->event.flags & SNDRV_SEQ_TIME_STAMP_MASK) {
276         case SNDRV_SEQ_TIME_STAMP_TICK:
277                 if (cell->event.time.tick)
278                         return 1;
279                 break;
280         case SNDRV_SEQ_TIME_STAMP_REAL:
281                 if (cell->event.time.time.tv_sec ||
282                     cell->event.time.time.tv_nsec)
283                         return 1;
284                 break;
285         }
286         return 0;
287 }
288 
289 /* remove cells for left client */
290 void snd_seq_prioq_leave(struct snd_seq_prioq * f, int client, int timestamp)
291 {
292         register struct snd_seq_event_cell *cell, *next;
293         unsigned long flags;
294         struct snd_seq_event_cell *prev = NULL;
295         struct snd_seq_event_cell *freefirst = NULL, *freeprev = NULL, *freenext;
296 
297         /* collect all removed cells */
298         spin_lock_irqsave(&f->lock, flags);
299         cell = f->head;
300         while (cell) {
301                 next = cell->next;
302                 if (prioq_match(cell, client, timestamp)) {
303                         /* remove cell from prioq */
304                         if (cell == f->head) {
305                                 f->head = cell->next;
306                         } else {
307                                 prev->next = cell->next;
308                         }
309                         if (cell == f->tail)
310                                 f->tail = cell->next;
311                         f->cells--;
312                         /* add cell to free list */
313                         cell->next = NULL;
314                         if (freefirst == NULL) {
315                                 freefirst = cell;
316                         } else {
317                                 freeprev->next = cell;
318                         }
319                         freeprev = cell;
320                 } else {
321 #if 0
322                         pr_debug("ALSA: seq: type = %i, source = %i, dest = %i, "
323                                "client = %i\n",
324                                 cell->event.type,
325                                 cell->event.source.client,
326                                 cell->event.dest.client,
327                                 client);
328 #endif
329                         prev = cell;
330                 }
331                 cell = next;            
332         }
333         spin_unlock_irqrestore(&f->lock, flags);        
334 
335         /* remove selected cells */
336         while (freefirst) {
337                 freenext = freefirst->next;
338                 snd_seq_cell_free(freefirst);
339                 freefirst = freenext;
340         }
341 }
342 
343 static int prioq_remove_match(struct snd_seq_remove_events *info,
344                               struct snd_seq_event *ev)
345 {
346         int res;
347 
348         if (info->remove_mode & SNDRV_SEQ_REMOVE_DEST) {
349                 if (ev->dest.client != info->dest.client ||
350                                 ev->dest.port != info->dest.port)
351                         return 0;
352         }
353         if (info->remove_mode & SNDRV_SEQ_REMOVE_DEST_CHANNEL) {
354                 if (! snd_seq_ev_is_channel_type(ev))
355                         return 0;
356                 /* data.note.channel and data.control.channel are identical */
357                 if (ev->data.note.channel != info->channel)
358                         return 0;
359         }
360         if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_AFTER) {
361                 if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_TICK)
362                         res = snd_seq_compare_tick_time(&ev->time.tick, &info->time.tick);
363                 else
364                         res = snd_seq_compare_real_time(&ev->time.time, &info->time.time);
365                 if (!res)
366                         return 0;
367         }
368         if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_BEFORE) {
369                 if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_TICK)
370                         res = snd_seq_compare_tick_time(&ev->time.tick, &info->time.tick);
371                 else
372                         res = snd_seq_compare_real_time(&ev->time.time, &info->time.time);
373                 if (res)
374                         return 0;
375         }
376         if (info->remove_mode & SNDRV_SEQ_REMOVE_EVENT_TYPE) {
377                 if (ev->type != info->type)
378                         return 0;
379         }
380         if (info->remove_mode & SNDRV_SEQ_REMOVE_IGNORE_OFF) {
381                 /* Do not remove off events */
382                 switch (ev->type) {
383                 case SNDRV_SEQ_EVENT_NOTEOFF:
384                 /* case SNDRV_SEQ_EVENT_SAMPLE_STOP: */
385                         return 0;
386                 default:
387                         break;
388                 }
389         }
390         if (info->remove_mode & SNDRV_SEQ_REMOVE_TAG_MATCH) {
391                 if (info->tag != ev->tag)
392                         return 0;
393         }
394 
395         return 1;
396 }
397 
398 /* remove cells matching remove criteria */
399 void snd_seq_prioq_remove_events(struct snd_seq_prioq * f, int client,
400                                  struct snd_seq_remove_events *info)
401 {
402         struct snd_seq_event_cell *cell, *next;
403         unsigned long flags;
404         struct snd_seq_event_cell *prev = NULL;
405         struct snd_seq_event_cell *freefirst = NULL, *freeprev = NULL, *freenext;
406 
407         /* collect all removed cells */
408         spin_lock_irqsave(&f->lock, flags);
409         cell = f->head;
410 
411         while (cell) {
412                 next = cell->next;
413                 if (cell->event.source.client == client &&
414                         prioq_remove_match(info, &cell->event)) {
415 
416                         /* remove cell from prioq */
417                         if (cell == f->head) {
418                                 f->head = cell->next;
419                         } else {
420                                 prev->next = cell->next;
421                         }
422 
423                         if (cell == f->tail)
424                                 f->tail = cell->next;
425                         f->cells--;
426 
427                         /* add cell to free list */
428                         cell->next = NULL;
429                         if (freefirst == NULL) {
430                                 freefirst = cell;
431                         } else {
432                                 freeprev->next = cell;
433                         }
434 
435                         freeprev = cell;
436                 } else {
437                         prev = cell;
438                 }
439                 cell = next;            
440         }
441         spin_unlock_irqrestore(&f->lock, flags);        
442 
443         /* remove selected cells */
444         while (freefirst) {
445                 freenext = freefirst->next;
446                 snd_seq_cell_free(freefirst);
447                 freefirst = freenext;
448         }
449 }
450 
451 
452 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp