Merge branch 'core/percpu' into percpu-cpumask-x86-for-linus-2
[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 <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 == 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) */
76 void snd_seq_prioq_delete(struct snd_seq_prioq **fifo)
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)
92                         snd_seq_cell_free(snd_seq_prioq_cell_out(f));
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 {
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(struct snd_seq_event *a,
121                                         struct snd_seq_event *b)
122 {
123         if ((a->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK) {
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 */
148 int snd_seq_prioq_cell_in(struct snd_seq_prioq * f,
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 */
220 struct snd_seq_event_cell *snd_seq_prioq_cell_out(struct snd_seq_prioq *f)
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 */
248 int snd_seq_prioq_avail(struct snd_seq_prioq * f)
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 */
259 struct snd_seq_event_cell *snd_seq_prioq_cell_peek(struct snd_seq_prioq * f)
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) {
278         case SNDRV_SEQ_TIME_STAMP_TICK:
279                 if (cell->event.time.tick)
280                         return 1;
281                 break;
282         case SNDRV_SEQ_TIME_STAMP_REAL:
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         }
355         if (info->remove_mode & SNDRV_SEQ_REMOVE_DEST_CHANNEL) {
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         }
362         if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_AFTER) {
363                 if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_TICK)
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         }
370         if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_BEFORE) {
371                 if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_TICK)
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         }
378         if (info->remove_mode & SNDRV_SEQ_REMOVE_EVENT_TYPE) {
379                 if (ev->type != info->type)
380                         return 0;
381         }
382         if (info->remove_mode & SNDRV_SEQ_REMOVE_IGNORE_OFF) {
383                 /* Do not remove off events */
384                 switch (ev->type) {
385                 case SNDRV_SEQ_EVENT_NOTEOFF:
386                 /* case SNDRV_SEQ_EVENT_SAMPLE_STOP: */
387                         return 0;
388                 default:
389                         break;
390                 }
391         }
392         if (info->remove_mode & SNDRV_SEQ_REMOVE_TAG_MATCH) {
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