+/* Copyright (C) 2009 Andre Noll <maan@tuebingen.mpg.de>, see file COPYING. */
+
+/**
+ * \file buffer_tree.h Buffer tree management.
+ *
+ * Buffer trees and buffer tree nodes.
+ *
+ * The buffer tree API offers an efficient method for managing the data flow
+ * from a producer (e.g. the network receiver) to the consumer(s) (e.g. a sound
+ * card).
+ *
+ * A buffer tree consists of buffer tree nodes which are linked together via
+ * parent/child relationships. Data buffers are propagated down without copying.
+ *
+ * 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. There are no file descriptors, no processes/threads 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 code avoids to
+ * copy buffer contents when possible.
+ *
+ * Communication between nodes is possible via the btr_exec_up() function. For
+ * example, in para_audiod the alsa writer asks all parent nodes for the number
+ * of channels and the sample rate of the current audio file.
+ *
+ * Buffer pools - An alternative to malloc/free buffer management.
+ *
+ * Non-leaf nodes usually create output to be processed by their child nodes.
+ * The data must be fed through the output channel(s) of the node in order to
+ * make that data available to each child.
+ *
+ * The easiest way to do so is to malloc() a buffer, fill it, and then call
+ * 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 is simple but has some drawbacks. For example the data source
+ * represented by the root node does not know in advance how much data will be
+ * available. Therefore the allocated buffer will either be larger than
+ * necessary or 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 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 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
+ * alignment constraints without copying buffer content whenever possible. To
+ * avoid spreading out the input data over the address space like in the
+ * malloc/free approach, a fixed large contiguous buffer (the area) is used
+ * instead. A buffer pool consists basically of an area and two pointers, the
+ * read head and the write head.
+ *
+ * Once a buffer pool has been created, its node, e.g. a receiver, obtains the
+ * current value of the write head and writes new data to this location. Then
+ * it calls btr_add_output_pool() to tell much data it has written. This
+ * advances the write head accordingly, and it also creates references to the
+ * newly written part of the area for the children of the node to consume.
+ *
+ * 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
+ * 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.
+ *
+ * No matter if malloc() or a buffer pool is used, the buffer tree code takes
+ * care of alignment constraints imposed by the consumers. In the buffer pool
+ * case, automatic merging of references to contiguous buffers is performed.
+ * memcpy is only used if a constraint can not be satisfied by using the
+ * remaining part of the area only. This only happens when the end of the area
+ * is reached.
+ */