buffer_tree.c

   1 #include <regex.h>
   2 #include <stdbool.h>
   3
   4 #include "para.h"
   5 #include "list.h"
   6 #include "string.h"
   7 #include "buffer_tree.h"
   8
   9
  10 struct btr_buffer {
  11         char *buf;
  12         size_t size;
  13         /** The number of references to this buffer. */
  14         int refcount;
  15 };
  16
  17 struct btr_buffer_reference {
  18         struct btr_buffer *btrb;
  19         size_t consumed;
  20         /* Each buffer reference belongs to the buffer queue list of some buffer tree node. */
  21         struct list_head node;
  22 };
  23
  24 struct btr_node {
  25         char *name;
  26         struct btr_node *parent;
  27         /* The position of this btr node in the buffer tree. */
  28         struct list_head node;
  29         /* The children nodes of this btr node are linked together in a list. */
  30         struct list_head children;
  31         /**
  32          * The input queue is a list of references to btr buffers. Each item on
  33          * the list represents an input buffer which has not been completely
  34          * used by this btr node.
  35          */
  36         struct list_head input_queue;
  37 };
  38
  39 #define FOR_EACH_CHILD(_tn, _btrn) list_for_each_entry((_tn), \
  40         &((_btrn)->children), node)
  41
  42 #define FOR_EACH_BUFFER_REF(_br, _btrn) \
  43         list_for_each_entry((_br), &(_btrn)->input_queue, node)
  44 #define FOR_EACH_BUFFER_REF_SAFE(_br, _tmp, _btrn) \
  45         list_for_each_entry_safe((_br), (_tmp), &(_btrn)->input_queue, node)
  46
  47 struct btr_node *btr_new_node(char *name, struct btr_node *parent)
  48 {
  49         struct btr_node *btrn = para_malloc(sizeof(*btrn));
  50
  51         btrn->name = para_strdup(name);
  52         btrn->parent = parent;
  53         if (parent)
  54                 list_add_tail(&btrn->node, &parent->children);
  55         INIT_LIST_HEAD(&btrn->children);
  56         INIT_LIST_HEAD(&btrn->input_queue);
  57         return btrn;
  58 }
  59
  60 /*
  61  * Allocate a new btr buffer.
  62  *
  63  * The freshly allocated buffer will have a zero refcount.
  64  */
  65 static struct btr_buffer *new_btrb(char *buf, size_t size)
  66 {
  67         struct btr_buffer *btrb = para_malloc(sizeof(*btrb));
  68
  69         btrb->buf = buf;
  70         btrb->size = size;
  71         btrb->refcount = 0;
  72         return btrb;
  73 }
  74
  75 /*
  76  * Deallocate the reference, release the resources if refcount drops to zero.
  77  */
  78 static void btr_drop_buffer_reference(struct btr_buffer_reference *br)
  79 {
  80         struct btr_buffer *btrb = br->btrb;
  81
  82         list_del(&br->node);
  83         free(br);
  84         btrb->refcount--;
  85         if (btrb->refcount == 0) {
  86                 free(btrb->buf);
  87                 free(btrb);
  88         }
  89 }
  90
  91 static void add_btrb_to_children(struct btr_buffer *btrb, struct btr_node *btrn)
  92 {
  93         struct btr_node *ch;
  94
  95         FOR_EACH_CHILD(ch, btrn) {
  96                 struct btr_buffer_reference *br = para_malloc(sizeof(*br));
  97                 br->btrb = btrb;
  98                 br->consumed = 0;
  99                 list_add_tail(&br->node, &ch->input_queue);
 100                 btrb->refcount++;
 101         }
 102 }
 103
 104 void btr_add_output(char *buf, size_t size, struct btr_node *btrn)
 105 {
 106         struct btr_buffer *btrb;
 107
 108         btrb = new_btrb(buf, size);
 109         add_btrb_to_children(btrb, btrn);
 110 }
 111
 112 static void btr_pushdown_br(struct btr_buffer_reference *br, struct btr_node *btrn)
 113 {
 114         add_btrb_to_children(br->btrb, btrn);
 115         btr_drop_buffer_reference(br);
 116 }
 117
 118 void btr_pushdown(struct btr_node *btrn)
 119 {
 120         struct btr_buffer_reference *br, *tmp;
 121
 122         FOR_EACH_BUFFER_REF_SAFE(br, tmp, btrn)
 123                 btr_pushdown_br(br, btrn);
 124 }
 125
 126 /* Return true if this node has no children. */
 127 bool btr_is_leaf_node(struct btr_node *btrn)
 128 {
 129         return list_empty(&btrn->children);
 130 }
 131
 132 bool btr_no_parent(struct btr_node *btrn)
 133 {
 134         return !btrn->parent;
 135 }
 136
 137 bool btr_inplace_ok(struct btr_node *btrn)
 138 {
 139         if (!btrn->parent)
 140                 return true;
 141         return list_is_singular(&btrn->parent->children);
 142 }
 143
 144 struct btr_buffer_reference *btr_next_br(struct btr_node *btrn)
 145 {
 146         if (list_empty(&btrn->input_queue))
 147                 return NULL;
 148         return list_first_entry(&btrn->input_queue, struct btr_buffer_reference, node);
 149 }
 150
 151
 152 static inline size_t br_available_bytes(struct btr_buffer_reference *br)
 153 {
 154         return br->btrb->size - br->consumed;
 155 }
 156
 157 size_t btr_get_buffer_by_reference(struct btr_buffer_reference *br, char **buf)
 158 {
 159         *buf = br->btrb->buf + br->consumed;
 160         return br_available_bytes(br);
 161 }
 162
 163 void btr_increase_used_bytes(struct btr_buffer_reference *br, size_t consumed)
 164 {
 165         br->consumed += consumed;
 166         if (br->consumed == br->btrb->size)
 167                 btr_drop_buffer_reference(br);
 168 }
 169
 170 static void flush_input_queue(struct btr_node *btrn)
 171 {
 172         struct btr_buffer_reference *br, *tmp;
 173         FOR_EACH_BUFFER_REF_SAFE(br, tmp, btrn)
 174                 btr_drop_buffer_reference(br);
 175 }
 176
 177 void btr_del_node(struct btr_node *btrn)
 178 {
 179         struct btr_node *ch;
 180
 181         FOR_EACH_CHILD(ch, btrn)
 182                 ch->parent = NULL;
 183         flush_input_queue(btrn);
 184         if (btrn->parent)
 185                 list_del(&btrn->node);
 186         free(btrn->name);
 187         free(btrn);
 188 }
 189
 190 size_t btr_get_input_queue_size(struct btr_node *btrn)
 191 {
 192         struct btr_buffer_reference *br;
 193         size_t size = 0;
 194
 195         FOR_EACH_BUFFER_REF(br, btrn)
 196                 size += br_available_bytes(br);
 197         return size;
 198 }
 199
 200 /**
 201  * Return the size of the largest input queue.
 202  *
 203  * Iterates over all children of the given node.
 204  */
 205 size_t btr_bytes_pending(struct btr_node *btrn)
 206 {
 207         size_t max_size = 0;
 208         struct btr_node *ch;
 209
 210         FOR_EACH_CHILD(ch, btrn) {
 211                 size_t size = btr_get_input_queue_size(ch);
 212                 max_size = PARA_MAX(max_size, size);
 213         }
 214         return max_size;
 215 }