seq_prioq.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453
  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. #include <sound/driver.h>
  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. /* Implementation is a simple linked list for now...
  28. This priority queue orders the events on timestamp. For events with an
  29. equeal timestamp the queue behaves as a FIFO.
  30. *
  31. * +-------+
  32. * Head --> | first |
  33. * +-------+
  34. * |next
  35. * +-----v-+
  36. * | |
  37. * +-------+
  38. * |
  39. * +-----v-+
  40. * | |
  41. * +-------+
  42. * |
  43. * +-----v-+
  44. * Tail --> | last |
  45. * +-------+
  46. *
  47. */
  48. /* create new prioq (constructor) */
  49. struct snd_seq_prioq *snd_seq_prioq_new(void)
  50. {
  51. struct snd_seq_prioq *f;
  52. f = kzalloc(sizeof(*f), GFP_KERNEL);
  53. if (f == NULL) {
  54. snd_printd("oops: malloc failed for snd_seq_prioq_new()\n");
  55. return NULL;
  56. }
  57. spin_lock_init(&f->lock);
  58. f->head = NULL;
  59. f->tail = NULL;
  60. f->cells = 0;
  61. return f;
  62. }
  63. /* delete prioq (destructor) */
  64. void snd_seq_prioq_delete(struct snd_seq_prioq **fifo)
  65. {
  66. struct snd_seq_prioq *f = *fifo;
  67. *fifo = NULL;
  68. if (f == NULL) {
  69. snd_printd("oops: snd_seq_prioq_delete() called with NULL prioq\n");
  70. return;
  71. }
  72. /* release resources...*/
  73. /*....................*/
  74. if (f->cells > 0) {
  75. /* drain prioQ */
  76. while (f->cells > 0)
  77. snd_seq_cell_free(snd_seq_prioq_cell_out(f));
  78. }
  79. kfree(f);
  80. }
  81. /* compare timestamp between events */
  82. /* return 1 if a >= b; 0 */
  83. static inline int compare_timestamp(struct snd_seq_event *a,
  84. struct snd_seq_event *b)
  85. {
  86. if ((a->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK) {
  87. /* compare ticks */
  88. return (snd_seq_compare_tick_time(&a->time.tick, &b->time.tick));
  89. } else {
  90. /* compare real time */
  91. return (snd_seq_compare_real_time(&a->time.time, &b->time.time));
  92. }
  93. }
  94. /* compare timestamp between events */
  95. /* return negative if a < b;
  96. * zero if a = b;
  97. * positive if a > b;
  98. */
  99. static inline int compare_timestamp_rel(struct snd_seq_event *a,
  100. struct snd_seq_event *b)
  101. {
  102. if ((a->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK) {
  103. /* compare ticks */
  104. if (a->time.tick > b->time.tick)
  105. return 1;
  106. else if (a->time.tick == b->time.tick)
  107. return 0;
  108. else
  109. return -1;
  110. } else {
  111. /* compare real time */
  112. if (a->time.time.tv_sec > b->time.time.tv_sec)
  113. return 1;
  114. else if (a->time.time.tv_sec == b->time.time.tv_sec) {
  115. if (a->time.time.tv_nsec > b->time.time.tv_nsec)
  116. return 1;
  117. else if (a->time.time.tv_nsec == b->time.time.tv_nsec)
  118. return 0;
  119. else
  120. return -1;
  121. } else
  122. return -1;
  123. }
  124. }
  125. /* enqueue cell to prioq */
  126. int snd_seq_prioq_cell_in(struct snd_seq_prioq * f,
  127. struct snd_seq_event_cell * cell)
  128. {
  129. struct snd_seq_event_cell *cur, *prev;
  130. unsigned long flags;
  131. int count;
  132. int prior;
  133. snd_assert(f, return -EINVAL);
  134. snd_assert(cell, return -EINVAL);
  135. /* check flags */
  136. prior = (cell->event.flags & SNDRV_SEQ_PRIORITY_MASK);
  137. spin_lock_irqsave(&f->lock, flags);
  138. /* check if this element needs to inserted at the end (ie. ordered
  139. data is inserted) This will be very likeley if a sequencer
  140. application or midi file player is feeding us (sequential) data */
  141. if (f->tail && !prior) {
  142. if (compare_timestamp(&cell->event, &f->tail->event)) {
  143. /* add new cell to tail of the fifo */
  144. f->tail->next = cell;
  145. f->tail = cell;
  146. cell->next = NULL;
  147. f->cells++;
  148. spin_unlock_irqrestore(&f->lock, flags);
  149. return 0;
  150. }
  151. }
  152. /* traverse list of elements to find the place where the new cell is
  153. to be inserted... Note that this is a order n process ! */
  154. prev = NULL; /* previous cell */
  155. cur = f->head; /* cursor */
  156. count = 10000; /* FIXME: enough big, isn't it? */
  157. while (cur != NULL) {
  158. /* compare timestamps */
  159. int rel = compare_timestamp_rel(&cell->event, &cur->event);
  160. if (rel < 0)
  161. /* new cell has earlier schedule time, */
  162. break;
  163. else if (rel == 0 && prior)
  164. /* equal schedule time and prior to others */
  165. break;
  166. /* new cell has equal or larger schedule time, */
  167. /* move cursor to next cell */
  168. prev = cur;
  169. cur = cur->next;
  170. if (! --count) {
  171. spin_unlock_irqrestore(&f->lock, flags);
  172. snd_printk(KERN_ERR "cannot find a pointer.. infinite loop?\n");
  173. return -EINVAL;
  174. }
  175. }
  176. /* insert it before cursor */
  177. if (prev != NULL)
  178. prev->next = cell;
  179. cell->next = cur;
  180. if (f->head == cur) /* this is the first cell, set head to it */
  181. f->head = cell;
  182. if (cur == NULL) /* reached end of the list */
  183. f->tail = cell;
  184. f->cells++;
  185. spin_unlock_irqrestore(&f->lock, flags);
  186. return 0;
  187. }
  188. /* dequeue cell from prioq */
  189. struct snd_seq_event_cell *snd_seq_prioq_cell_out(struct snd_seq_prioq *f)
  190. {
  191. struct snd_seq_event_cell *cell;
  192. unsigned long flags;
  193. if (f == NULL) {
  194. snd_printd("oops: snd_seq_prioq_cell_in() called with NULL prioq\n");
  195. return NULL;
  196. }
  197. spin_lock_irqsave(&f->lock, flags);
  198. cell = f->head;
  199. if (cell) {
  200. f->head = cell->next;
  201. /* reset tail if this was the last element */
  202. if (f->tail == cell)
  203. f->tail = NULL;
  204. cell->next = NULL;
  205. f->cells--;
  206. }
  207. spin_unlock_irqrestore(&f->lock, flags);
  208. return cell;
  209. }
  210. /* return number of events available in prioq */
  211. int snd_seq_prioq_avail(struct snd_seq_prioq * f)
  212. {
  213. if (f == NULL) {
  214. snd_printd("oops: snd_seq_prioq_cell_in() called with NULL prioq\n");
  215. return 0;
  216. }
  217. return f->cells;
  218. }
  219. /* peek at cell at the head of the prioq */
  220. struct snd_seq_event_cell *snd_seq_prioq_cell_peek(struct snd_seq_prioq * f)
  221. {
  222. if (f == NULL) {
  223. snd_printd("oops: snd_seq_prioq_cell_in() called with NULL prioq\n");
  224. return NULL;
  225. }
  226. return f->head;
  227. }
  228. static inline int prioq_match(struct snd_seq_event_cell *cell,
  229. int client, int timestamp)
  230. {
  231. if (cell->event.source.client == client ||
  232. cell->event.dest.client == client)
  233. return 1;
  234. if (!timestamp)
  235. return 0;
  236. switch (cell->event.flags & SNDRV_SEQ_TIME_STAMP_MASK) {
  237. case SNDRV_SEQ_TIME_STAMP_TICK:
  238. if (cell->event.time.tick)
  239. return 1;
  240. break;
  241. case SNDRV_SEQ_TIME_STAMP_REAL:
  242. if (cell->event.time.time.tv_sec ||
  243. cell->event.time.time.tv_nsec)
  244. return 1;
  245. break;
  246. }
  247. return 0;
  248. }
  249. /* remove cells for left client */
  250. void snd_seq_prioq_leave(struct snd_seq_prioq * f, int client, int timestamp)
  251. {
  252. register struct snd_seq_event_cell *cell, *next;
  253. unsigned long flags;
  254. struct snd_seq_event_cell *prev = NULL;
  255. struct snd_seq_event_cell *freefirst = NULL, *freeprev = NULL, *freenext;
  256. /* collect all removed cells */
  257. spin_lock_irqsave(&f->lock, flags);
  258. cell = f->head;
  259. while (cell) {
  260. next = cell->next;
  261. if (prioq_match(cell, client, timestamp)) {
  262. /* remove cell from prioq */
  263. if (cell == f->head) {
  264. f->head = cell->next;
  265. } else {
  266. prev->next = cell->next;
  267. }
  268. if (cell == f->tail)
  269. f->tail = cell->next;
  270. f->cells--;
  271. /* add cell to free list */
  272. cell->next = NULL;
  273. if (freefirst == NULL) {
  274. freefirst = cell;
  275. } else {
  276. freeprev->next = cell;
  277. }
  278. freeprev = cell;
  279. } else {
  280. #if 0
  281. printk("type = %i, source = %i, dest = %i, client = %i\n",
  282. cell->event.type,
  283. cell->event.source.client,
  284. cell->event.dest.client,
  285. client);
  286. #endif
  287. prev = cell;
  288. }
  289. cell = next;
  290. }
  291. spin_unlock_irqrestore(&f->lock, flags);
  292. /* remove selected cells */
  293. while (freefirst) {
  294. freenext = freefirst->next;
  295. snd_seq_cell_free(freefirst);
  296. freefirst = freenext;
  297. }
  298. }
  299. static int prioq_remove_match(struct snd_seq_remove_events *info,
  300. struct snd_seq_event *ev)
  301. {
  302. int res;
  303. if (info->remove_mode & SNDRV_SEQ_REMOVE_DEST) {
  304. if (ev->dest.client != info->dest.client ||
  305. ev->dest.port != info->dest.port)
  306. return 0;
  307. }
  308. if (info->remove_mode & SNDRV_SEQ_REMOVE_DEST_CHANNEL) {
  309. if (! snd_seq_ev_is_channel_type(ev))
  310. return 0;
  311. /* data.note.channel and data.control.channel are identical */
  312. if (ev->data.note.channel != info->channel)
  313. return 0;
  314. }
  315. if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_AFTER) {
  316. if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_TICK)
  317. res = snd_seq_compare_tick_time(&ev->time.tick, &info->time.tick);
  318. else
  319. res = snd_seq_compare_real_time(&ev->time.time, &info->time.time);
  320. if (!res)
  321. return 0;
  322. }
  323. if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_BEFORE) {
  324. if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_TICK)
  325. res = snd_seq_compare_tick_time(&ev->time.tick, &info->time.tick);
  326. else
  327. res = snd_seq_compare_real_time(&ev->time.time, &info->time.time);
  328. if (res)
  329. return 0;
  330. }
  331. if (info->remove_mode & SNDRV_SEQ_REMOVE_EVENT_TYPE) {
  332. if (ev->type != info->type)
  333. return 0;
  334. }
  335. if (info->remove_mode & SNDRV_SEQ_REMOVE_IGNORE_OFF) {
  336. /* Do not remove off events */
  337. switch (ev->type) {
  338. case SNDRV_SEQ_EVENT_NOTEOFF:
  339. /* case SNDRV_SEQ_EVENT_SAMPLE_STOP: */
  340. return 0;
  341. default:
  342. break;
  343. }
  344. }
  345. if (info->remove_mode & SNDRV_SEQ_REMOVE_TAG_MATCH) {
  346. if (info->tag != ev->tag)
  347. return 0;
  348. }
  349. return 1;
  350. }
  351. /* remove cells matching remove criteria */
  352. void snd_seq_prioq_remove_events(struct snd_seq_prioq * f, int client,
  353. struct snd_seq_remove_events *info)
  354. {
  355. struct snd_seq_event_cell *cell, *next;
  356. unsigned long flags;
  357. struct snd_seq_event_cell *prev = NULL;
  358. struct snd_seq_event_cell *freefirst = NULL, *freeprev = NULL, *freenext;
  359. /* collect all removed cells */
  360. spin_lock_irqsave(&f->lock, flags);
  361. cell = f->head;
  362. while (cell) {
  363. next = cell->next;
  364. if (cell->event.source.client == client &&
  365. prioq_remove_match(info, &cell->event)) {
  366. /* remove cell from prioq */
  367. if (cell == f->head) {
  368. f->head = cell->next;
  369. } else {
  370. prev->next = cell->next;
  371. }
  372. if (cell == f->tail)
  373. f->tail = cell->next;
  374. f->cells--;
  375. /* add cell to free list */
  376. cell->next = NULL;
  377. if (freefirst == NULL) {
  378. freefirst = cell;
  379. } else {
  380. freeprev->next = cell;
  381. }
  382. freeprev = cell;
  383. } else {
  384. prev = cell;
  385. }
  386. cell = next;
  387. }
  388. spin_unlock_irqrestore(&f->lock, flags);
  389. /* remove selected cells */
  390. while (freefirst) {
  391. freenext = freefirst->next;
  392. snd_seq_cell_free(freefirst);
  393. freefirst = freenext;
  394. }
  395. }