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 static inline size_t br_available_bytes(struct btr_buffer_reference *br)
 145 {
 146         return br->btrb->size - br->consumed;
 147 }
 148
 149 size_t btr_get_buffer_by_reference(struct btr_buffer_reference *br, char **buf)
 150 {
 151         *buf = br->btrb->buf + br->consumed;
 152         return br_available_bytes(br);
 153 }
 154
 155 size_t btr_next_buffer(struct btr_node *btrn, char **bufp)
 156 {
 157         struct btr_buffer_reference *br;
 158
 159         if (list_empty(&btrn->input_queue)) {
 160                 *bufp = NULL;
 161                 return 0;
 162         }
 163         br = list_first_entry(&btrn->input_queue, struct btr_buffer_reference, node);
 164         return btr_get_buffer_by_reference(br, bufp);
 165 }
 166
 167 void btr_consume(struct btr_node *btrn, size_t numbytes)
 168 {
 169         struct btr_buffer_reference *br;
 170
 171         assert(!list_empty(&btrn->input_queue));
 172         br = list_first_entry(&btrn->input_queue, struct btr_buffer_reference, node);
 173         assert(br->consumed + numbytes <= br->btrb->size);
 174         br->consumed += numbytes;
 175         if (br->consumed == br->btrb->size)
 176                 btr_drop_buffer_reference(br);
 177 }
 178
 179 static void flush_input_queue(struct btr_node *btrn)
 180 {
 181         struct btr_buffer_reference *br, *tmp;
 182         FOR_EACH_BUFFER_REF_SAFE(br, tmp, btrn)
 183                 btr_drop_buffer_reference(br);
 184 }
 185
 186 void btr_del_node(struct btr_node *btrn)
 187 {
 188         struct btr_node *ch;
 189
 190         if (!btrn)
 191                 return;
 192         PARA_NOTICE_LOG("deleting %s\n", btrn->name);
 193         FOR_EACH_CHILD(ch, btrn)
 194                 ch->parent = NULL;
 195         flush_input_queue(btrn);
 196         if (btrn->parent)
 197                 list_del(&btrn->node);
 198         free(btrn->name);
 199         free(btrn);
 200 }
 201
 202 size_t btr_get_input_queue_size(struct btr_node *btrn)
 203 {
 204         struct btr_buffer_reference *br;
 205         size_t size = 0;
 206
 207         FOR_EACH_BUFFER_REF(br, btrn)
 208                 size += br_available_bytes(br);
 209         return size;
 210 }
 211
 212 /**
 213  * Return the size of the largest input queue.
 214  *
 215  * Iterates over all children of the given node.
 216  */
 217 size_t btr_bytes_pending(struct btr_node *btrn)
 218 {
 219         size_t max_size = 0;
 220         struct btr_node *ch;
 221
 222         FOR_EACH_CHILD(ch, btrn) {
 223                 size_t size = btr_get_input_queue_size(ch);
 224                 max_size = PARA_MAX(max_size, size);
 225         }
 226         return max_size;
 227 }