From 455818b4d559c0294788f7b12ec64055244cb55f Mon Sep 17 00:00:00 2001 From: Andre Noll Date: Sun, 17 Jan 2010 13:27:46 +0100 Subject: [PATCH] [btr] Documentation update. --- buffer_tree.c | 128 +++++++++++++++++++++++++++++++++++++++++--------- buffer_tree.h | 43 ++++++++--------- stat.c | 2 +- 3 files changed, 128 insertions(+), 45 deletions(-) diff --git a/buffer_tree.c b/buffer_tree.c index 9862a4f1..a5b1fd23 100644 --- a/buffer_tree.c +++ b/buffer_tree.c @@ -17,16 +17,12 @@ struct btr_pool { char *whead; }; -enum btr_buffer_flags { - /* changes the way the buffer is deallocated */ - BTR_BF_BTR_POOL = 1, -}; - struct btr_buffer { char *buf; size_t size; /** The number of references to this buffer. */ int refcount; + /* NULL means no buffer pool but a malloced buffer. */ struct btr_pool *pool; }; @@ -118,6 +114,18 @@ size_t btr_pool_filled(struct btr_pool *btrp) return btr_pool_size(btrp) - (btrp->rhead - btrp->whead); } +/** + * Get the number of unused bytes in the buffer pool. + * + * \param btrp The pool. + * + * \return 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. + */ size_t btr_pool_unused(struct btr_pool *btrp) { return btr_pool_size(btrp) - btr_pool_filled(btrp); @@ -209,6 +217,15 @@ static void btr_pool_deallocate(struct btr_pool *btrp, size_t size) #define FOR_EACH_BUFFER_REF_SAFE(_br, _tmp, _btrn) \ list_for_each_entry_safe((_br), (_tmp), &(_btrn)->input_queue, node) +/** + * Create a new buffer tree node. + * + * \param bnd Specifies how to create the new node. + * + * This function always succeeds (or calls exit()). The returned pointer + * must be freed using btr_free_node() after it has been removed from + * the buffer tree via btr_remove_node(). + */ struct btr_node *btr_new_node(struct btr_node_description *bnd) { struct btr_node *btrn = para_malloc(sizeof(*btrn)); @@ -312,6 +329,20 @@ static void add_btrb_to_children(struct btr_buffer *btrb, } } +/** + * Insert a malloced buffer into the buffer tree. + * + * \param buf The buffer to insert. + * \param size The size of \a buf in bytes. + * \param btrn Position in the buffer tree to create the output. + * + * This creates references to \a buf and adds these references to each child of + * \a 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 \a buf was obtained from a + * buffer pool. Use btr_add_output_pool() in this case. + */ void btr_add_output(char *buf, size_t size, struct btr_node *btrn) { struct btr_buffer *btrb; @@ -326,10 +357,16 @@ void btr_add_output(char *buf, size_t size, struct btr_node *btrn) } /** - * Feed data to child nodes of the buffer tree. + * Feed data to child nodes of a buffer tree node. * * \param btrp The buffer pool. - * + * \param size The number of bytes to be allocated and fed to each child. + * \param btrn The 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 \a btrn. The references are then fed into the input queue of each child. */ void btr_add_output_pool(struct btr_pool *btrp, size_t size, struct btr_node *btrn) @@ -406,12 +443,28 @@ int btr_pushdown_one(struct btr_node *btrn) return 1; } -/* Return true if this node has no children. */ -bool btr_no_children(struct btr_node *btrn) +/* + * Find out whether a node is a leaf node. + * + * \param btrn The node to check. + * + * \return True if this node has no children. False otherwise. + */ +static bool btr_no_children(struct btr_node *btrn) { return list_empty(&btrn->children); } +/** + * Find out whether a node is an orphan node. + * + * \param btrn The buffer tree node. + * + * \return True if \a btrn has no parent. + * + * This function will always return true for the root node. However in case + * nodes have been removed from the tree, other nodes may become orphans too. + */ bool btr_no_parent(struct btr_node *btrn) { return !btrn->parent; @@ -437,7 +490,13 @@ size_t btr_get_buffer_by_reference(struct btr_buffer_reference *br, char **buf) } /** - * \return zero if the input buffer queue is empty. + * Obtain the next buffer of the input queue of a buffer tree node. + * + * \param btrn The node whose input queue is to be queried. + * \param bufp Result pointer. + * + * \return The number of bytes that can be read from buf. Zero if the input + * buffer queue is empty. In this case the value of \a bufp is undefined. */ size_t btr_next_buffer(struct btr_node *btrn, char **bufp) { @@ -465,6 +524,21 @@ size_t btr_next_buffer(struct btr_node *btrn, char **bufp) return rv; } +/** + * Deallocate the given number of bytes from the input queue. + * + * \param btrn The buffer tree node. + * \param numbytes The 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 tree case) or the read head of + * the buffer pool is being advanced. + * + * Note that \a 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. + */ void btr_consume(struct btr_node *btrn, size_t numbytes) { struct btr_buffer_reference *br, *tmp; @@ -492,16 +566,14 @@ void btr_consume(struct btr_node *btrn, size_t numbytes) assert(true); } /* - - We have a wrap buffer, consume from it. If in total, - i.e. including previous calls to brt_consume(), less than - wrap_count has been consumed, there's nothing more we can do. - - Otherwise we drop the wrap buffer and consume from subsequent - buffers of the input queue the correct amount of bytes. This - is the total number of bytes that have been consumed from the - wrap buffer. -*/ + * We have a wrap buffer, consume from it. If in total, i.e. including + * previous calls to brt_consume(), less than wrap_count has been + * consumed, there's nothing more we can do. + * + * Otherwise we drop the wrap buffer and consume from subsequent + * buffers of the input queue the correct amount of bytes. This is the + * total number of bytes that have been consumed from the wrap buffer. + */ PARA_DEBUG_LOG("consuming %zu/%zu bytes from wrap buffer\n", numbytes, br_available_bytes(br)); @@ -546,6 +618,17 @@ void btr_remove_node(struct btr_node *btrn) list_del(&btrn->node); } +/** + * Return the amount of available input bytes of a buffer tree node. + * + * \param btrn The node whose input size should be computed. + * + * \return 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. + */ size_t btr_get_input_queue_size(struct btr_node *btrn) { struct btr_buffer_reference *br; @@ -587,7 +670,7 @@ void btr_splice_out_node(struct btr_node *btrn) * * Iterates over all children of the given node. */ -size_t btr_bytes_pending(struct btr_node *btrn) +static size_t btr_bytes_pending(struct btr_node *btrn) { size_t max_size = 0; struct btr_node *ch; @@ -608,6 +691,9 @@ int btr_exec(struct btr_node *btrn, const char *command, char **value_result) return btrn->execute(btrn, command, value_result); } +/** + * Execute a inter-node command. + */ int btr_exec_up(struct btr_node *btrn, const char *command, char **value_result) { int ret; diff --git a/buffer_tree.h b/buffer_tree.h index 0bb31b18..157c17c2 100644 --- a/buffer_tree.h +++ b/buffer_tree.h @@ -1,18 +1,19 @@ /** - * Buffer trees and buffer tree nodes. + * \file buffer_tree.h Buffer tree management. * + * \par Buffer trees and buffer tree nodes. * The buffer tree API offers a more powerful method than standard unix pipes * for managing the data flow from the producer of the data (e.g. the network * receiver) to its consumer(s) (e.g. a sound card). * - * Each data buffer starts its way from the root of the buffer tree. At each - * child node the data is investigated and new data is fed to each child. - * Everything happens within one single-treaded process. There are no file - * descriptors, no calls to read() or write(). - * * A buffer tree consists of buffer tree nodes linked via certain parent/child * relationships. * + * Each data buffer starts its way from the root of the buffer tree. At each + * node the data is investigated and possibly changed. New data is then fed to + * each child. Everything happens within one single-treaded process. There are + * no file descriptors and no calls to read() or write(). + * * Whenever a node in the buffer tree creates output, either by creating a new * buffer or by pushing down buffers received from its parent, references to * that buffer are created for all children of the node. The buffer tree code @@ -23,10 +24,7 @@ * For example, in para_audiod the alsa writer asks all parent nodes * for for the number of channels and the sample rate of the current * audio file. - */ -struct btr_node; - -/** + * * Buffer pools - An alternative to malloc/free buffer management. * * Non-leaf nodes usually create output to be processed by their children. The @@ -37,21 +35,21 @@ struct btr_node; * btr_add_output(). This adds references to that buffer to all children. The * buffer is automatically freed if no buffer tree node is using it any more. * - * This approach, while simple, has some drawbacks, especially affecting the - * root nodes of the buffer tree. Often the data source which is represented by - * a root node does not know in advance how much data will be available. - * Therefore the allocated buffer is either larger than what can currently be - * read, or is too small so that multiple buffers have to be used. + * This approach, while being simple, has some drawbacks, especially affecting + * the root nodes of the buffer tree. Often the data source which is + * represented by a root node does not know in advance how much data will be + * available. Therefore the allocated buffer is either larger than what can + * currently be read, or is too small so that multiple buffers have to be used. * * While this could be worked around by using a large buffer and calling * realloc() afterwards to shrink the buffer according to how much has been * read, there is a second problem which comes from the alignment constraints - * of some filters, mainly the decoders. These need a minimal amount of data to - * proceed, and most of them even need this amount as one contiguous buffer, - * i.e. not spread out over two or more buffers. + * of some filters, mainly the decoders like mp3dec. These need a minimal + * amount of data to proceed, and most of them even need this amount as one + * contiguous buffer, i.e. not spread out over two or more buffers. * * Although the buffer tree code handles this case just fine, it can be - * expensive because two or more buffers must be combined by copying buffer + * expensive because two or more buffers must be merged by copying buffer * contents around in order to satisfy the constraint. * * This is where buffer pools come into play. Buffer pools try to satisfy @@ -70,7 +68,7 @@ struct btr_node; * Child nodes consume data by working through their input queue, which is a * list of buffer references. Once the content of a buffer is no longer needed * by a child node, the child calls btr_consume() to indicate the amount of - * data which can be dropped from the child's point of view. If no reference + * data which can be dropped from the child's point of view. If no reference * to some region of the buffer pool area remains, the read head of the buffer * pool advances, making space available for the receiver node to fill. * @@ -81,6 +79,8 @@ struct btr_node; * remaining part of the area only. This only happens when the end of the area * is reached. */ + +struct btr_node; struct btr_pool; /** @@ -178,13 +178,10 @@ struct btr_node *btr_new_node(struct btr_node_description *bnd); void btr_remove_node(struct btr_node *btrn); void btr_free_node(struct btr_node *btrn); void btr_add_output(char *buf, size_t size, struct btr_node *btrn); -bool btr_no_children(struct btr_node *btrn); -size_t btr_bytes_pending(struct btr_node *btrn); size_t btr_get_input_queue_size(struct btr_node *btrn); bool btr_no_parent(struct btr_node *btrn); size_t btr_next_buffer(struct btr_node *btrn, char **bufp); void btr_consume(struct btr_node *btrn, size_t numbytes); -int btr_exec(struct btr_node *btrn, const char *command, char **value_result); int btr_exec_up(struct btr_node *btrn, const char *command, char **value_result); void btr_splice_out_node(struct btr_node *btrn); void btr_pushdown(struct btr_node *btrn); diff --git a/stat.c b/stat.c index 27ffab5e..33690917 100644 --- a/stat.c +++ b/stat.c @@ -27,7 +27,7 @@ * \param item_handler Function to call for each complete item. * * \return Negative on errors, the number of bytes _not_ passed to \a - * item_handler. + * item_handler on success. * * Status items are expected in the format used by parser-friendly output mode * of the stat command of para_client/para_audioc. -- 2.30.2