paraslash Paraslash Audio Streaming
About   News   Download   Documentation   Development

Macros | Functions
buffer_tree.c File Reference

Buffer tree and buffer pool implementations. More...

#include <regex.h>
#include "para.h"
#include "list.h"
#include "string.h"
#include "buffer_tree.h"
#include "error.h"
#include "sched.h"

Macros

#define FOR_EACH_CHILD(_tn, _btrn)
 
#define FOR_EACH_CHILD_SAFE(_tn, _tmp, _btrn)    list_for_each_entry_safe((_tn), (_tmp), &((_btrn)->children), node)
 
#define FOR_EACH_BUFFER_REF(_br, _btrn)    list_for_each_entry((_br), &(_btrn)->input_queue, node)
 
#define FOR_EACH_BUFFER_REF_SAFE(_br, _tmp, _btrn)    list_for_each_entry_safe((_br), (_tmp), &(_btrn)->input_queue, node)
 
#define BTRN_MAX_PENDING   (96 * 1024)
 640K ought to be enough for everybody ;) More...
 

Functions

struct btr_pool * btr_pool_new (const char *name, size_t area_size)
 Create a new buffer pool. More...
 
void btr_pool_free (struct btr_pool *btrp)
 Deallocate resources used by a buffer pool. More...
 
size_t btr_pool_size (const struct btr_pool *btrp)
 Return the size of the buffer pool area. More...
 
size_t btr_pool_unused (const struct btr_pool *btrp)
 Get the number of unused bytes in the buffer pool. More...
 
size_t btr_pool_get_buffer (const struct btr_pool *btrp, char **result)
 Obtain the current write head. More...
 
int btr_pool_get_buffers (const struct btr_pool *btrp, struct iovec iov[2])
 Get references to buffers pointing to free space of the buffer pool area. More...
 
struct btr_node * btr_new_node (struct btr_node_description *bnd)
 Create a new buffer tree node. More...
 
void btr_add_output (char *buf, size_t size, struct btr_node *btrn)
 Insert a malloced buffer into the buffer tree. More...
 
void btr_add_output_dont_free (const char *buf, size_t size, struct btr_node *btrn)
 Insert a buffer into the buffer tree, non-freeing variant. More...
 
void btr_add_output_pool (struct btr_pool *btrp, size_t size, struct btr_node *btrn)
 Feed data to child nodes of a buffer tree node. More...
 
void btr_copy (const void *src, size_t n, struct btr_pool *btrp, struct btr_node *btrn)
 Copy data to write head of a buffer pool and feed it to all children nodes. More...
 
void btr_pushdown (struct btr_node *btrn)
 Feed all buffer references of the input queue through the output channel. More...
 
void btr_pushdown_one (struct btr_node *btrn)
 Feed the next buffer of the input queue through the output channel. More...
 
bool btr_no_parent (const struct btr_node *btrn)
 Find out whether a node is an orphan. More...
 
bool btr_inplace_ok (const struct btr_node *btrn)
 Find out whether it is OK to change an input buffer. More...
 
size_t btr_next_buffer_omit (const struct btr_node *btrn, size_t omit, char **bufp)
 Obtain the next buffer of the input queue, omitting data. More...
 
size_t btr_next_buffer (const struct btr_node *btrn, char **bufp)
 Obtain the next buffer of the input queue of a buffer tree node. More...
 
void btr_consume (struct btr_node *btrn, size_t numbytes)
 Deallocate the given number of bytes from the input queue. More...
 
void btr_drain (struct btr_node *btrn)
 Clear the input queue of a buffer tree node. More...
 
void btr_remove_node (struct btr_node **btrnp)
 Remove a node from a buffer tree. More...
 
size_t btr_get_input_queue_size (const struct btr_node *btrn)
 Return the amount of available input bytes of a buffer tree node. More...
 
void btr_splice_out_node (struct btr_node **btrnp)
 Remove a node from the buffer tree, reconnecting parent and children. More...
 
size_t btr_get_output_queue_size (const struct btr_node *btrn)
 Return number of queued output bytes of a buffer tree node. More...
 
int btr_exec_up (const struct btr_node *btrn, const char *command, char **value_result)
 Execute an inter-node command on the given node or on a parent node. More...
 
void * btr_context (const struct btr_node *btrn)
 Obtain the context of a buffer node tree. More...
 
void btr_merge (struct btr_node *btrn, size_t dest_size)
 Combine input queue buffers. More...
 
void btr_log_tree (const struct btr_node *btrn, int loglevel)
 Write the current buffer (sub-)tree to the log. More...
 
struct btr_node * btr_search_node (const char *name, struct btr_node *root)
 Find the node with the given name in the buffer tree. More...
 
int btr_node_status (const struct btr_node *btrn, size_t min_iqs, enum btr_node_type type)
 Return the current state of a buffer tree node. More...
 
void btr_get_node_start (const struct btr_node *btrn, struct timeval *tv)
 Get the time of the first I/O for a buffer tree node. More...
 
struct btr_node * btr_parent (const struct btr_node *btrn)
 Get the parent node of a buffer tree node. More...
 

Detailed Description

Buffer tree and buffer pool implementations.

Macro Definition Documentation

◆ FOR_EACH_CHILD

#define FOR_EACH_CHILD (   _tn,
  _btrn 
)
Value:
&((_btrn)->children), node)

◆ FOR_EACH_CHILD_SAFE

#define FOR_EACH_CHILD_SAFE (   _tn,
  _tmp,
  _btrn 
)     list_for_each_entry_safe((_tn), (_tmp), &((_btrn)->children), node)

◆ FOR_EACH_BUFFER_REF

#define FOR_EACH_BUFFER_REF (   _br,
  _btrn 
)     list_for_each_entry((_br), &(_btrn)->input_queue, node)

◆ FOR_EACH_BUFFER_REF_SAFE

#define FOR_EACH_BUFFER_REF_SAFE (   _br,
  _tmp,
  _btrn 
)     list_for_each_entry_safe((_br), (_tmp), &(_btrn)->input_queue, node)

◆ BTRN_MAX_PENDING

#define BTRN_MAX_PENDING   (96 * 1024)

640K ought to be enough for everybody ;)

Function Documentation

◆ btr_pool_new()

struct btr_pool* btr_pool_new ( const char *  name,
size_t  area_size 
)

Create a new buffer pool.

Parameters
nameThe name of the new buffer pool.
area_sizeThe size in bytes of the pool area.
Returns
An opaque pointer to the newly created buffer pool. It must be passed to btr_pool_free() after it is no longer used to deallocate all resources.

References alloc(), PARA_INFO_LOG, and para_strdup().

◆ btr_pool_free()

void btr_pool_free ( struct btr_pool *  btrp)

Deallocate resources used by a buffer pool.

Parameters
btrpA pointer obtained via btr_pool_new().

◆ btr_pool_size()

size_t btr_pool_size ( const struct btr_pool *  btrp)

Return the size of the buffer pool area.

Parameters
btrpThe buffer pool.
Returns
The same value which was passed during creation time to btr_pool_new().

Referenced by btr_pool_unused().

◆ btr_pool_unused()

size_t btr_pool_unused ( const struct btr_pool *  btrp)

Get the number of unused bytes in the buffer pool.

Parameters
btrpThe pool.
Returns
The number of bytes that can currently be allocated.

Note that in general the returned number of bytes is not available as a single contiguous buffer. Use btr_pool_available() to obtain the length of the largest contiguous buffer that can currently be allocated from the buffer pool.

References btr_pool_size().

Referenced by btr_copy(), and btr_pool_get_buffers().

◆ btr_pool_get_buffer()

size_t btr_pool_get_buffer ( const struct btr_pool *  btrp,
char **  result 
)

Obtain the current write head.

Parameters
btrpThe buffer pool.
resultThe write head is returned here.
Returns
The maximal amount of bytes that may be written to the returned buffer.

Referenced by btr_copy(), and btr_pool_get_buffers().

◆ btr_pool_get_buffers()

int btr_pool_get_buffers ( const struct btr_pool *  btrp,
struct iovec  iov[2] 
)

Get references to buffers pointing to free space of the buffer pool area.

Parameters
btrpThe buffer pool.
iovThe scatter array.
Returns
Zero if the buffer pool is full, one if the free space of the buffer pool area is available as a single contiguous buffer, two if the free space consists of two buffers. If this function returns the value n, then n elements of iov are initialized.

References btr_pool_get_buffer(), and btr_pool_unused().

◆ btr_new_node()

struct btr_node* btr_new_node ( struct btr_node_description bnd)

Create a new buffer tree node.

Parameters
bndSpecifies how to create the new node.
Returns
A pointer to the newly allocated node.

This function always succeeds (or calls exit()). The returned pointer must be freed using btr_free_node() after the node has been removed from the buffer tree via btr_remove_node().

References alloc(), btr_node_description::context, btr_node_description::handler, btr_node_description::name, para_strdup(), and btr_node_description::parent.

Referenced by check_wav_init(), and register_writer_node().

◆ btr_add_output()

void btr_add_output ( char *  buf,
size_t  size,
struct btr_node *  btrn 
)

Insert a malloced buffer into the buffer tree.

Parameters
bufThe buffer to insert.
sizeThe size of buf in bytes.
btrnPosition in the buffer tree to create the output.

This creates references to buf and adds these references to each child of btrn. The buffer will be freed using standard free() once no buffer tree node is referencing it any more.

Note that this function must not be used if buf was obtained from a buffer pool. Use btr_add_output_pool() in this case.

◆ btr_add_output_dont_free()

void btr_add_output_dont_free ( const char *  buf,
size_t  size,
struct btr_node *  btrn 
)

Insert a buffer into the buffer tree, non-freeing variant.

Parameters
bufSee btr_add_output().
sizeSee btr_add_output().
btrnSee btr_add_output().

This is similar to btr_add_output() but additionally sets the dont_free flag on buf. If the refcount for the buffer drops to zero, buf will not be deallocated if this flag is set.

The dont_free bit also prevents the children of btrn from modifying the buffer contents inplace. Specifically, btr_inplace_ok() returns false if there is any buffer in the input queue with the dont_free bit set.

◆ btr_add_output_pool()

void btr_add_output_pool ( struct btr_pool *  btrp,
size_t  size,
struct btr_node *  btrn 
)

Feed data to child nodes of a buffer tree node.

Parameters
btrpThe buffer pool.
sizeThe number of bytes to be allocated and fed to each child.
btrnThe node whose children are to be fed.

This function allocates the amount of bytes from the buffer pool area, starting at the current value of the write head, and creates buffer references to the resulting part of the buffer pool area, one for each child of btrn. The references are then fed into the input queue of each child.

Referenced by btr_copy().

◆ btr_copy()

void btr_copy ( const void *  src,
size_t  n,
struct btr_pool *  btrp,
struct btr_node *  btrn 
)

Copy data to write head of a buffer pool and feed it to all children nodes.

Parameters
srcThe source buffer.
nThe size of the source buffer in bytes.
btrpThe destination buffer pool.
btrnAdd the data as output of this node.

This is expensive. The caller must make sure the data fits into the buffer pool area.

References btr_add_output_pool(), btr_pool_get_buffer(), btr_pool_unused(), and PARA_MIN.

◆ btr_pushdown()

void btr_pushdown ( struct btr_node *  btrn)

Feed all buffer references of the input queue through the output channel.

Parameters
btrnThe node whose buffer references should be pushed down.

This function is useful for filters that do not change the contents of the buffers at all, like the wav filter or the amp filter if no amplification was specified. This function is rather cheap.

See also
btr_pushdown_one().

References FOR_EACH_BUFFER_REF_SAFE.

Referenced by btr_splice_out_node().

◆ btr_pushdown_one()

void btr_pushdown_one ( struct btr_node *  btrn)

Feed the next buffer of the input queue through the output channel.

Parameters
btrnThe node whose first input queue buffer should be pushed down.

This works like btr_pushdown() but pushes down only one buffer reference.

◆ btr_no_parent()

bool btr_no_parent ( const struct btr_node *  btrn)

Find out whether a node is an orphan.

Parameters
btrnThe buffer tree node.
Returns
True if btrn has no parent.

This function returns true for the root node and false for any other node.

After a (non-leaf) node was removed removed from the tree, the function returns true for all child nodes.

◆ btr_inplace_ok()

bool btr_inplace_ok ( const struct btr_node *  btrn)

Find out whether it is OK to change an input buffer.

Parameters
btrnThe buffer tree node to check.

This is used by filters that produce exactly the same amount of output as there is input. The amp filter which multiplies each sample by some number is an example of such a filter. If there are no other nodes in the buffer tree that read the same input stream (i.e. if btrn has no siblings), a node may modify its input buffer directly and push down the modified buffer to its children, thereby avoiding to allocate a possibly large additional buffer.

Since the buffer tree may change at any time, this function should be called during each post_monitor call.

Returns
True if btrn has no siblings.

References FOR_EACH_BUFFER_REF.

◆ btr_next_buffer_omit()

size_t btr_next_buffer_omit ( const struct btr_node *  btrn,
size_t  omit,
char **  bufp 
)

Obtain the next buffer of the input queue, omitting data.

Parameters
btrnThe node whose input queue is to be queried.
omitNumber of bytes to be omitted.
bufpResult pointer. It is OK to pass NULL here.

If a buffer tree node needs more input data but can not consume the data it already has (because it might be needed again later) this function can be used instead of btr_next_buffer() to get a reference to the buffer obtained by skipping the given number of bytes. Skipped input bytes are not consumed.

With a zero omit argument, this function is equivalent to btr_next_buffer().

Returns
Number of bytes in bufp. If there are less than or equal to omit many bytes available in the input queue of the buffer tree node pointed to by btrn, the function returns zero and the value of bufp is undefined.

Referenced by btr_next_buffer().

◆ btr_next_buffer()

size_t btr_next_buffer ( const struct btr_node *  btrn,
char **  bufp 
)

Obtain the next buffer of the input queue of a buffer tree node.

Parameters
btrnThe node whose input queue is to be queried.
bufpResult pointer.
Returns
The number of bytes that can be read from buf.

The call of this function is is equivalent to calling btr_next_buffer_omit() with an omit value of zero.

References btr_next_buffer_omit().

Referenced by check_wav_post_monitor().

◆ btr_consume()

void btr_consume ( struct btr_node *  btrn,
size_t  numbytes 
)

Deallocate the given number of bytes from the input queue.

Parameters
btrnThe buffer tree node.
numbytesThe number of bytes to be deallocated.

This function must be used to get rid of existing buffer references in the node's input queue. If no references to a buffer remain, the underlying buffers are either freed (in the non-buffer pool case) or the read head of the buffer pool is being advanced.

Note that numbytes may be smaller than the buffer size. In this case the buffer is not deallocated and subsequent calls to btr_next_buffer() return the remaining part of the buffer.

◆ btr_drain()

void btr_drain ( struct btr_node *  btrn)

Clear the input queue of a buffer tree node.

Parameters
btrnThe node whose input queue should be cleared.

References FOR_EACH_BUFFER_REF_SAFE.

Referenced by btr_remove_node().

◆ btr_remove_node()

void btr_remove_node ( struct btr_node **  btrnp)

Remove a node from a buffer tree.

Parameters
btrnpDetermines the node to remove.

This orphans all children of the node given by btrnp and removes this node from the child list of its parent. Moreover, the input queue is flushed and the node pointer given by btrp is set to NULL.

See also
btr_splice_out_node.

References btr_drain(), FOR_EACH_CHILD, and PARA_INFO_LOG.

Referenced by i9e_attach_to_stdout().

◆ btr_get_input_queue_size()

size_t btr_get_input_queue_size ( const struct btr_node *  btrn)

Return the amount of available input bytes of a buffer tree node.

Parameters
btrnThe node whose input size should be computed.
Returns
The total number of bytes available in the node's input queue.

This simply iterates over all buffer references in the input queue and returns the sum of the sizes of all references.

References FOR_EACH_BUFFER_REF.

Referenced by btr_get_output_queue_size().

◆ btr_splice_out_node()

void btr_splice_out_node ( struct btr_node **  btrnp)

Remove a node from the buffer tree, reconnecting parent and children.

Parameters
btrnpThe node to splice out.

This function is used by buffer tree nodes that do not exist during the whole lifetime of the buffer tree. Unlike btr_remove_node(), calling btr_splice_out_node() does not split the tree into disconnected components but reconnects the buffer tree by making all child nodes of btrn children of the parent of btrn.

References btr_pushdown(), and PARA_NOTICE_LOG.

◆ btr_get_output_queue_size()

size_t btr_get_output_queue_size ( const struct btr_node *  btrn)

Return number of queued output bytes of a buffer tree node.

Parameters
btrnThe node whose output queue size should be computed.
Returns
This function iterates over all children of the given node and returns the size of the largest input queue.

References btr_get_input_queue_size(), FOR_EACH_CHILD, and PARA_MAX.

◆ btr_exec_up()

int btr_exec_up ( const struct btr_node *  btrn,
const char *  command,
char **  value_result 
)

Execute an inter-node command on the given node or on a parent node.

Parameters
btrnThe node to start looking.
commandThe command to execute.
value_resultAdditional arguments and result value.

This function traverses the buffer tree from btrn upwards and looks for the first node that understands command. On this node command is executed, and the result is stored in value_result.

Returns
-ENOTSUP if no parent node of btrn understands command. Otherwise the return value of the command handler is returned.
See also
receiver::execute, filter::execute, writer::execute.

References ERRNO_TO_PARA_ERROR, and PARA_INFO_LOG.

◆ btr_context()

void* btr_context ( const struct btr_node *  btrn)

Obtain the context of a buffer node tree.

Parameters
btrnThe node whose output queue size should be computed.
Returns
A pointer to the context address specified at node creation time.
See also
btr_new_node(), struct btr_node_description.

◆ btr_merge()

void btr_merge ( struct btr_node *  btrn,
size_t  dest_size 
)

Combine input queue buffers.

Parameters
btrnThe buffer tree node whose input should be merged.
dest_sizeStop merging if a buffer of at least this size exists.

Used to combine as many buffers as needed into a single buffer whose size is at least dest_size. This function is rather cheap in case the parent node uses buffer pools and rather expensive otherwise.

Note that if less than dest_size bytes are available in total, this function does nothing and subsequent calls to btr_next_buffer() will still return a buffer size less than dest_size.

Referenced by check_wav_post_monitor().

◆ btr_log_tree()

void btr_log_tree ( const struct btr_node *  btrn,
int  loglevel 
)

Write the current buffer (sub-)tree to the log.

Parameters
btrnStart logging at this node.
loglevelSet severity with which the tree should be logged.

◆ btr_search_node()

struct btr_node* btr_search_node ( const char *  name,
struct btr_node *  root 
)

Find the node with the given name in the buffer tree.

Parameters
nameThe name of the node to search.
rootWhere to start the search.
Returns
A pointer to the node with the given name on success. If name is NULL, the function returns root. If there is no node with the given name, NULL is returned.

References btr_search_node(), and FOR_EACH_CHILD.

Referenced by btr_search_node().

◆ btr_node_status()

int btr_node_status ( const struct btr_node *  btrn,
size_t  min_iqs,
enum btr_node_type  type 
)

Return the current state of a buffer tree node.

Parameters
btrnThe node whose state should be queried.
min_iqsThe minimal input queue size.
typeThe supposed type of btrn.

Most users of the buffer tree subsystem call this function from both their ->pre_monitor() and ->post_monitor() methods.

Returns
Negative if an error condition was detected, zero if there is nothing to do and positive otherwise.

Examples:

  • If a non-root node has no parent and an empty input queue, the function returns -E_BTR_EOF. Similarly, if a non-leaf node has no children, -E_BTR_NO_CHILD is returned.
  • If less than min_iqs many bytes are available in the input queue and no EOF condition was detected, the function returns zero.
  • If there's plenty of data left in the input queue of the children of btrn, the function also returns zero in order to bound the memory usage of the buffer tree.

References BTR_NT_LEAF.

Referenced by check_wav_post_monitor(), check_wav_pre_monitor(), generic_filter_pre_monitor(), and generic_recv_pre_monitor().

◆ btr_get_node_start()

void btr_get_node_start ( const struct btr_node *  btrn,
struct timeval *  tv 
)

Get the time of the first I/O for a buffer tree node.

Parameters
btrnThe node whose I/O time should be obtained.
tvResult pointer.

Mainly useful for the time display of para_audiod.

Referenced by audiod_get_btr_root().

◆ btr_parent()

struct btr_node* btr_parent ( const struct btr_node *  btrn)

Get the parent node of a buffer tree node.

Parameters
btrnThe node whose parent should be returned.

btrn must not be NULL.

Returns
The parent of btrn, or NULL if btrn is the root node of the buffer tree.
list_for_each_entry
#define list_for_each_entry(pos, head, member)
Iterate over a list.
Definition: list.h:134