Advanced Linux Sound Architecture

SEQUENCER

5.1 Memory management

Goal is to provide one unified pool of event memory (fixed size, in kernel space). All priority queues and FIFOs can allocate memory from this pool.

The presence of this pool allows allocation and releasing memory for events in constant time, and with no memory overhead.

On-line statistics will be kept to see the current number in use and peak number in use of:

client connections (user land)
client connections (kernel)
number of events stored in queue
number of events stored in FIFO
free space in memery pool (peak is lowest figure)

If needed the pool can dynamicly be expanded... Size of the pool (number of elements) is passed as a parameter when loading the sequencer module.

5.1.1 Free list

The elements in the pool of free cells are implemented as records that form a linked list. This makes memory allocation an constant time operation and there will be no fragmentation problems.

Following (internal) functions are provided:

/* release this cell */
extern void snd_seq_cell_free(snd_seq_event_cell_t* cell);

/* return pointer to cell, NULL on failure */
extern snd_seq_event_cell_t *snd_seq_cell_alloc(void);

/* duplicate event, NULL on failure */
extern snd_seq_event_cell_t *snd_seq_event_dup(snd_seq_event_t *event);

/* duplicate event cell, NULL on failure */
extern snd_seq_event_cell_t *snd_seq_cell_dup(snd_seq_event_cell_t *event);

/* return number of unused (free) cells */
extern int snd_seq_unused_cells(void);

/* return total number of allocated cells */
extern int snd_seq_total_cells(void);

5.1.2 FIFO

A FIFO is easily implemented as a linked list. The application only needs to have a pointer to the head and the tail of the queue. Insertion and deletion can be performed in constant time. Schematic diagram of organisation of the data.

Following (internal) functions are provided:

/* initialise fifo */
extern void snd_seq_fifo_init(fifo_t *f);

/* enqueue cell to fifo */
extern void snd_seq_fifo_cell_in(fifo_t *f, snd_seq_event_cell_t *cell);

/* dequeue cell from fifo */ 
extern snd_seq_event_cell_t *snd_seq_fifo_cell_out(fifo_t *f);

/* return number of events available in fifo */
extern int snd_seq_fifo_avail(fifo_t *f);

/* peek at cell at the head of the fifo */
extern snd_seq_event_cell_t *snd_seq_fifo_cell_peek(fifo_t *f);

5.1.3 Priority queue

The priority queue is special queue that maintains a sorted ordering for all the events that are stored in the queue. For events with a equal time stamp the queue behaves as a FIFO. The priority queue is implementated as a single linked list, similar to the FIFO. This gives the queue the advantage that the queue can dynamicly be sized without the need for additional memory. To achieve a better runtime performance the queue is optimised for operations that are most common for sequencer applications.

Check element at front: constant time
Remove element at front: constant time
Insert at front of queue: constant time
Insert at tail of queue: constant time
Insert in somewhere in the middle: order n, the list has to be traversed from front until the location where the event has to be inserted is found.

As most events that are enqueued have a timestamp of 'now' and go directly to the front of the queue, or they have a increasing timestamp (eg. sequencer or MIDI file playback) and go to the tail the queue.

Insertions in the middle take more time when the queue becomes longer. Try to keep not more than a few hundered events queued if possible.

In a future this priority queue can be optimised by using a better, more efficient algorithm (e.g. heap). Care should be taken no to make the common cases much worse than they are now.

Following (internal) functions are provided:

/* initialise prioq */
extern void snd_seq_prioq_init(prioq_t *f);

/* enqueue cell to prioq */
extern void snd_seq_prioq_cell_in(prioq_t *f, snd_seq_event_cell_t *cell);

/* dequeue cell from prioq */ 
extern snd_seq_event_cell_t *snd_seq_prioq_cell_out(prioq_t *f);

/* return number of events available in prioq */
extern int snd_seq_prioq_avail(prioq_t *f);

/* peek at cell at the head of the prioq */
extern snd_seq_event_cell_t *snd_seq_prioq_cell_peek(prioq_t *f);

Version 0.036, April 2nd, 1999	Usage:
Copyright (c) 1998 by Frank van de Pol, Netherlands	Advanced Linux Sound Architecture