Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
seq_prioq.c
Go to the documentation of this file.
1 /*
2  * ALSA sequencer Priority Queue
3  * Copyright (c) 1998-1999 by Frank van de Pol <[email protected]>
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) */
58 {
59  struct snd_seq_prioq *f;
60 
61  f = kzalloc(sizeof(*f), GFP_KERNEL);
62  if (f == NULL) {
63  snd_printd("oops: malloc failed for snd_seq_prioq_new()\n");
64  return NULL;
65  }
66 
67  spin_lock_init(&f->lock);
68  f->head = NULL;
69  f->tail = NULL;
70  f->cells = 0;
71 
72  return f;
73 }
74 
75 /* delete prioq (destructor) */
77 {
78  struct snd_seq_prioq *f = *fifo;
79  *fifo = NULL;
80 
81  if (f == NULL) {
82  snd_printd("oops: snd_seq_prioq_delete() called with NULL prioq\n");
83  return;
84  }
85 
86  /* release resources...*/
87  /*....................*/
88 
89  if (f->cells > 0) {
90  /* drain prioQ */
91  while (f->cells > 0)
93  }
94 
95  kfree(f);
96 }
97 
98 
99 
100 
101 /* compare timestamp between events */
102 /* return 1 if a >= b; 0 */
103 static inline int compare_timestamp(struct snd_seq_event *a,
104  struct snd_seq_event *b)
105 {
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(struct snd_seq_event *a,
121  struct snd_seq_event *b)
122 {
124  /* compare ticks */
125  if (a->time.tick > b->time.tick)
126  return 1;
127  else if (a->time.tick == b->time.tick)
128  return 0;
129  else
130  return -1;
131  } else {
132  /* compare real time */
133  if (a->time.time.tv_sec > b->time.time.tv_sec)
134  return 1;
135  else if (a->time.time.tv_sec == b->time.time.tv_sec) {
136  if (a->time.time.tv_nsec > b->time.time.tv_nsec)
137  return 1;
138  else if (a->time.time.tv_nsec == b->time.time.tv_nsec)
139  return 0;
140  else
141  return -1;
142  } else
143  return -1;
144  }
145 }
146 
147 /* enqueue cell to prioq */
149  struct snd_seq_event_cell * cell)
150 {
151  struct snd_seq_event_cell *cur, *prev;
152  unsigned long flags;
153  int count;
154  int prior;
155 
156  if (snd_BUG_ON(!f || !cell))
157  return -EINVAL;
158 
159  /* check flags */
160  prior = (cell->event.flags & SNDRV_SEQ_PRIORITY_MASK);
161 
162  spin_lock_irqsave(&f->lock, flags);
163 
164  /* check if this element needs to inserted at the end (ie. ordered
165  data is inserted) This will be very likeley if a sequencer
166  application or midi file player is feeding us (sequential) data */
167  if (f->tail && !prior) {
168  if (compare_timestamp(&cell->event, &f->tail->event)) {
169  /* add new cell to tail of the fifo */
170  f->tail->next = cell;
171  f->tail = cell;
172  cell->next = NULL;
173  f->cells++;
174  spin_unlock_irqrestore(&f->lock, flags);
175  return 0;
176  }
177  }
178  /* traverse list of elements to find the place where the new cell is
179  to be inserted... Note that this is a order n process ! */
180 
181  prev = NULL; /* previous cell */
182  cur = f->head; /* cursor */
183 
184  count = 10000; /* FIXME: enough big, isn't it? */
185  while (cur != NULL) {
186  /* compare timestamps */
187  int rel = compare_timestamp_rel(&cell->event, &cur->event);
188  if (rel < 0)
189  /* new cell has earlier schedule time, */
190  break;
191  else if (rel == 0 && prior)
192  /* equal schedule time and prior to others */
193  break;
194  /* new cell has equal or larger schedule time, */
195  /* move cursor to next cell */
196  prev = cur;
197  cur = cur->next;
198  if (! --count) {
199  spin_unlock_irqrestore(&f->lock, flags);
200  snd_printk(KERN_ERR "cannot find a pointer.. infinite loop?\n");
201  return -EINVAL;
202  }
203  }
204 
205  /* insert it before cursor */
206  if (prev != NULL)
207  prev->next = cell;
208  cell->next = cur;
209 
210  if (f->head == cur) /* this is the first cell, set head to it */
211  f->head = cell;
212  if (cur == NULL) /* reached end of the list */
213  f->tail = cell;
214  f->cells++;
215  spin_unlock_irqrestore(&f->lock, flags);
216  return 0;
217 }
218 
219 /* dequeue cell from prioq */
221 {
222  struct snd_seq_event_cell *cell;
223  unsigned long flags;
224 
225  if (f == NULL) {
226  snd_printd("oops: snd_seq_prioq_cell_in() called with NULL prioq\n");
227  return NULL;
228  }
229  spin_lock_irqsave(&f->lock, flags);
230 
231  cell = f->head;
232  if (cell) {
233  f->head = cell->next;
234 
235  /* reset tail if this was the last element */
236  if (f->tail == cell)
237  f->tail = NULL;
238 
239  cell->next = NULL;
240  f->cells--;
241  }
242 
243  spin_unlock_irqrestore(&f->lock, flags);
244  return cell;
245 }
246 
247 /* return number of events available in prioq */
249 {
250  if (f == NULL) {
251  snd_printd("oops: snd_seq_prioq_cell_in() called with NULL prioq\n");
252  return 0;
253  }
254  return f->cells;
255 }
256 
257 
258 /* peek at cell at the head of the prioq */
260 {
261  if (f == NULL) {
262  snd_printd("oops: snd_seq_prioq_cell_in() called with NULL prioq\n");
263  return NULL;
264  }
265  return f->head;
266 }
267 
268 
269 static inline int prioq_match(struct snd_seq_event_cell *cell,
270  int client, int timestamp)
271 {
272  if (cell->event.source.client == client ||
273  cell->event.dest.client == client)
274  return 1;
275  if (!timestamp)
276  return 0;
277  switch (cell->event.flags & SNDRV_SEQ_TIME_STAMP_MASK) {
279  if (cell->event.time.tick)
280  return 1;
281  break;
283  if (cell->event.time.time.tv_sec ||
284  cell->event.time.time.tv_nsec)
285  return 1;
286  break;
287  }
288  return 0;
289 }
290 
291 /* remove cells for left client */
292 void snd_seq_prioq_leave(struct snd_seq_prioq * f, int client, int timestamp)
293 {
294  register struct snd_seq_event_cell *cell, *next;
295  unsigned long flags;
296  struct snd_seq_event_cell *prev = NULL;
297  struct snd_seq_event_cell *freefirst = NULL, *freeprev = NULL, *freenext;
298 
299  /* collect all removed cells */
300  spin_lock_irqsave(&f->lock, flags);
301  cell = f->head;
302  while (cell) {
303  next = cell->next;
304  if (prioq_match(cell, client, timestamp)) {
305  /* remove cell from prioq */
306  if (cell == f->head) {
307  f->head = cell->next;
308  } else {
309  prev->next = cell->next;
310  }
311  if (cell == f->tail)
312  f->tail = cell->next;
313  f->cells--;
314  /* add cell to free list */
315  cell->next = NULL;
316  if (freefirst == NULL) {
317  freefirst = cell;
318  } else {
319  freeprev->next = cell;
320  }
321  freeprev = cell;
322  } else {
323 #if 0
324  printk(KERN_DEBUG "type = %i, source = %i, dest = %i, "
325  "client = %i\n",
326  cell->event.type,
327  cell->event.source.client,
328  cell->event.dest.client,
329  client);
330 #endif
331  prev = cell;
332  }
333  cell = next;
334  }
335  spin_unlock_irqrestore(&f->lock, flags);
336 
337  /* remove selected cells */
338  while (freefirst) {
339  freenext = freefirst->next;
340  snd_seq_cell_free(freefirst);
341  freefirst = freenext;
342  }
343 }
344 
345 static int prioq_remove_match(struct snd_seq_remove_events *info,
346  struct snd_seq_event *ev)
347 {
348  int res;
349 
350  if (info->remove_mode & SNDRV_SEQ_REMOVE_DEST) {
351  if (ev->dest.client != info->dest.client ||
352  ev->dest.port != info->dest.port)
353  return 0;
354  }
356  if (! snd_seq_ev_is_channel_type(ev))
357  return 0;
358  /* data.note.channel and data.control.channel are identical */
359  if (ev->data.note.channel != info->channel)
360  return 0;
361  }
364  res = snd_seq_compare_tick_time(&ev->time.tick, &info->time.tick);
365  else
366  res = snd_seq_compare_real_time(&ev->time.time, &info->time.time);
367  if (!res)
368  return 0;
369  }
372  res = snd_seq_compare_tick_time(&ev->time.tick, &info->time.tick);
373  else
374  res = snd_seq_compare_real_time(&ev->time.time, &info->time.time);
375  if (res)
376  return 0;
377  }
379  if (ev->type != info->type)
380  return 0;
381  }
383  /* Do not remove off events */
384  switch (ev->type) {
386  /* case SNDRV_SEQ_EVENT_SAMPLE_STOP: */
387  return 0;
388  default:
389  break;
390  }
391  }
393  if (info->tag != ev->tag)
394  return 0;
395  }
396 
397  return 1;
398 }
399 
400 /* remove cells matching remove criteria */
401 void snd_seq_prioq_remove_events(struct snd_seq_prioq * f, int client,
402  struct snd_seq_remove_events *info)
403 {
404  struct snd_seq_event_cell *cell, *next;
405  unsigned long flags;
406  struct snd_seq_event_cell *prev = NULL;
407  struct snd_seq_event_cell *freefirst = NULL, *freeprev = NULL, *freenext;
408 
409  /* collect all removed cells */
410  spin_lock_irqsave(&f->lock, flags);
411  cell = f->head;
412 
413  while (cell) {
414  next = cell->next;
415  if (cell->event.source.client == client &&
416  prioq_remove_match(info, &cell->event)) {
417 
418  /* remove cell from prioq */
419  if (cell == f->head) {
420  f->head = cell->next;
421  } else {
422  prev->next = cell->next;
423  }
424 
425  if (cell == f->tail)
426  f->tail = cell->next;
427  f->cells--;
428 
429  /* add cell to free list */
430  cell->next = NULL;
431  if (freefirst == NULL) {
432  freefirst = cell;
433  } else {
434  freeprev->next = cell;
435  }
436 
437  freeprev = cell;
438  } else {
439  prev = cell;
440  }
441  cell = next;
442  }
443  spin_unlock_irqrestore(&f->lock, flags);
444 
445  /* remove selected cells */
446  while (freefirst) {
447  freenext = freefirst->next;
448  snd_seq_cell_free(freefirst);
449  freefirst = freenext;
450  }
451 }
452 
453