From 5374ad8fad0d5eabc002b01aa5a2815880a9e019 Mon Sep 17 00:00:00 2001 From: Andre Noll Date: Sat, 26 Dec 2009 15:52:31 +0100 Subject: [PATCH] First implementation of the buffer tree code. --- buffer_tree.c | 195 ++++++++++++++++++++++++++++++++++++++++++++++++++ list.h | 22 ++++++ 2 files changed, 217 insertions(+) create mode 100644 buffer_tree.c diff --git a/buffer_tree.c b/buffer_tree.c new file mode 100644 index 00000000..ba2a0875 --- /dev/null +++ b/buffer_tree.c @@ -0,0 +1,195 @@ +#include +#include + +#include "para.h" +#include "list.h" +#include "string.h" +//#include "buffer_tree.h" + + +struct btr_buffer { + char *buf; + size_t size; + /** The number of references to this buffer. */ + int refcount; +}; + +struct btr_buffer_reference { + struct btr_buffer *btrb; + size_t consumed; + /* Each buffer reference belongs to the buffer queue list of some buffer tree node. */ + struct list_head node; +}; + +struct btr_node { + char *name; + struct btr_node *parent; + /* The position of this btr node in the buffer tree. */ + struct list_head node; + /* The children nodes of this btr node are linked together in a list. */ + struct list_head children; + /** + * The input queue is a list of references to btr buffers. Each item on + * the list represents an input buffer which has not been completely + * used by this btr node. + */ + struct list_head buffer_queue; +}; + +#define FOR_EACH_TARGET_NODE(_tn, _btrn) list_for_each_entry((_tn), \ + &((_btrn)->children), node) + +#define FOR_EACH_BUFFER_REF(_br, _btrn) \ + list_for_each_entry((_br), &(_btrn)->buffer_queue, node) +#define FOR_EACH_BUFFER_REF_SAFE(_br, _tmp, _btrn) \ + list_for_each_entry_safe((_br), (_tmp), &(_btrn)->buffer_queue, node) + +INIT_STDERR_LOGGING(0); + +struct btr_node *btr_new_node(char *name, struct btr_node *parent) +{ + struct btr_node *btrn = para_malloc(sizeof(*btrn)); + + btrn->name = para_strdup(name); + btrn->parent = parent; + if (parent) + list_add_tail(&btrn->node, &parent->children); + INIT_LIST_HEAD(&btrn->children); + INIT_LIST_HEAD(&btrn->buffer_queue); + return btrn; +} + +static struct btr_buffer *new_btrb(char *buf, size_t size) +{ + struct btr_buffer *btrb = para_malloc(sizeof(*btrb)); + + btrb->buf = buf; + btrb->size = size; + btrb->refcount = 0; + return btrb; +} + +void btr_drop_buffer_reference(struct btr_buffer_reference *br) +{ + struct btr_buffer *btrb = br->btrb; + + list_del(&br->node); + free(br); + btrb->refcount--; + if (btrb->refcount == 0) { + free(btrb->buf); + free(btrb); + } +} + +static void add_btrb_to_targets(struct btr_buffer *btrb, struct btr_node *btrn) +{ + struct btr_node *tn; /* target node */ + + FOR_EACH_TARGET_NODE(tn, btrn) { + struct btr_buffer_reference *br = para_malloc(sizeof(*br)); + br->btrb = btrb; + br->consumed = 0; + list_add_tail(&br->node, &tn->buffer_queue); + btrb->refcount++; + } +} + +void btr_add_output(char *buf, size_t size, struct btr_node *btrn) +{ + struct btr_buffer *btrb; + + btrb = new_btrb(buf, size); + add_btrb_to_targets(btrb, btrn); +} + +void btr_pushdown_br(struct btr_buffer_reference *br, struct btr_node *btrn) +{ + add_btrb_to_targets(br->btrb, btrn); + btr_drop_buffer_reference(br); +} + +void btr_pushdown(struct btr_node *btrn) +{ + struct btr_buffer_reference *br, *tmp; + + FOR_EACH_BUFFER_REF_SAFE(br, tmp, btrn) + btr_pushdown_br(br, btrn); +} + +bool btr_no_children(struct btr_node *btrn) +{ + return list_empty(&btrn->children); +} + +bool btr_no_parent(struct btr_node *btrn) +{ + return !btrn->parent; +} + +bool btr_inplace_ok(struct btr_node *btrn) +{ + if (!btrn->parent) + return true; + return list_is_singular(&btrn->parent->children); +} + +struct btr_buffer_reference *btr_next_br(struct btr_node *btrn) +{ + if (list_empty(&btrn->buffer_queue)) + return NULL; + return list_first_entry(&btrn->buffer_queue, struct btr_buffer_reference, node); +} + +static inline size_t br_available_bytes(struct btr_buffer_reference *br) +{ + return br->btrb->size - br->consumed; +} + +size_t btr_get_buffer_by_reference(struct btr_buffer_reference *br, char **buf) +{ + *buf = br->btrb->buf + br->consumed; + return br_available_bytes(br); +} + +void btr_increase_used_bytes(struct btr_buffer_reference *br, size_t consumed) +{ + br->consumed += consumed; + if (br->consumed == br->btrb->size) + btr_drop_buffer_reference(br); +} + +static void flush_input_queue(struct btr_node *btrn) +{ + struct btr_buffer_reference *br, *tmp; + FOR_EACH_BUFFER_REF_SAFE(br, tmp, btrn) + btr_drop_buffer_reference(br); +} + +void btr_del_node(struct btr_node *btrn) +{ + struct btr_node *tn; + + FOR_EACH_TARGET_NODE(tn, btrn) + tn->parent = NULL; + flush_input_queue(btrn); + if (btrn->parent) + list_del(&btrn->node); + free(btrn->name); + free(btrn); +} + +size_t btr_get_input_queue_size(struct btr_node *btrn) +{ + struct btr_buffer_reference *br; + size_t size = 0; + + FOR_EACH_BUFFER_REF(br, btrn) + size += br_available_bytes(br); + return size; +} + +int main(void) +{ + return 1; +} diff --git a/list.h b/list.h index 80f36a1b..e4b5a1f6 100644 --- a/list.h +++ b/list.h @@ -204,3 +204,25 @@ static inline int list_empty(const struct list_head *head) n = list_entry(pos->member.prev, typeof(*pos), member); \ &pos->member != (head); \ pos = n, n = list_entry(n->member.prev, typeof(*n), member)) + +/** + * Get the first element from a list + * \param ptr the list head to take the element from. + * \param type The type of the struct this is embedded in. + * \param member The name of the list_struct within the struct. + * + * Note that list is expected to be not empty. + */ +#define list_first_entry(ptr, type, member) \ + list_entry((ptr)->next, type, member) + +/** + * Test whether a list has just one entry. + * + * \param head The list to test. + */ +static inline int list_is_singular(const struct list_head *head) +{ + return !list_empty(head) && (head->next == head->prev); +} + -- 2.39.5