Merge master.kernel.org:/pub/scm/linux/kernel/git/dwmw2/audit-2.6
[linux-2.6] / 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 = kzalloc(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