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 INIT_STDERR_LOGGING(0);
  48
  49 struct btr_node *btr_new_node(char *name, struct btr_node *parent)
  50 {
  51         struct btr_node *btrn = para_malloc(sizeof(*btrn));
  52
  53         btrn->name = para_strdup(name);
  54         btrn->parent = parent;
  55         if (parent)
  56                 list_add_tail(&btrn->node, &parent->children);
  57         INIT_LIST_HEAD(&btrn->children);
  58         INIT_LIST_HEAD(&btrn->input_queue);
  59         return btrn;
  60 }
  61
  62 /*
  63  * Allocate a new btr buffer.
  64  *
  65  * The freshly allocated buffer will have a zero refcount.
  66  */
  67 static struct btr_buffer *new_btrb(char *buf, size_t size)
  68 {
  69         struct btr_buffer *btrb = para_malloc(sizeof(*btrb));
  70
  71         btrb->buf = buf;
  72         btrb->size = size;
  73         btrb->refcount = 0;
  74         return btrb;
  75 }
  76
  77 /*
  78  * Deallocate the reference, release the resources if refcount drops to zero.
  79  */
  80 void btr_drop_buffer_reference(struct btr_buffer_reference *br)
  81 {
  82         struct btr_buffer *btrb = br->btrb;
  83
  84         list_del(&br->node);
  85         free(br);
  86         btrb->refcount--;
  87         if (btrb->refcount == 0) {
  88                 free(btrb->buf);
  89                 free(btrb);
  90         }
  91 }
  92
  93 static void add_btrb_to_children(struct btr_buffer *btrb, struct btr_node *btrn)
  94 {
  95         struct btr_node *ch;
  96
  97         FOR_EACH_CHILD(ch, btrn) {
  98                 struct btr_buffer_reference *br = para_malloc(sizeof(*br));
  99                 br->btrb = btrb;
 100                 br->consumed = 0;
 101                 list_add_tail(&br->node, &ch->input_queue);
 102                 btrb->refcount++;
 103         }
 104 }
 105
 106 void btr_add_output(char *buf, size_t size, struct btr_node *btrn)
 107 {
 108         struct btr_buffer *btrb;
 109
 110         btrb = new_btrb(buf, size);
 111         add_btrb_to_children(btrb, btrn);
 112 }
 113
 114 void btr_pushdown_br(struct btr_buffer_reference *br, struct btr_node *btrn)
 115 {
 116         add_btrb_to_children(br->btrb, btrn);
 117         btr_drop_buffer_reference(br);
 118 }
 119
 120 void btr_pushdown(struct btr_node *btrn)
 121 {
 122         struct btr_buffer_reference *br, *tmp;
 123
 124         FOR_EACH_BUFFER_REF_SAFE(br, tmp, btrn)
 125                 btr_pushdown_br(br, btrn);
 126 }
 127
 128 /* Return true if this node has no children. */
 129 bool btr_is_leaf_node(struct btr_node *btrn)
 130 {
 131         return list_empty(&btrn->children);
 132 }
 133
 134 bool btr_no_parent(struct btr_node *btrn)
 135 {
 136         return !btrn->parent;
 137 }
 138
 139 bool btr_inplace_ok(struct btr_node *btrn)
 140 {
 141         if (!btrn->parent)
 142                 return true;
 143         return list_is_singular(&btrn->parent->children);
 144 }
 145
 146 struct btr_buffer_reference *btr_next_br(struct btr_node *btrn)
 147 {
 148         if (list_empty(&btrn->input_queue))
 149                 return NULL;
 150         return list_first_entry(&btrn->input_queue, struct btr_buffer_reference, node);
 151 }
 152
 153 static inline size_t br_available_bytes(struct btr_buffer_reference *br)
 154 {
 155         return br->btrb->size - br->consumed;
 156 }
 157
 158 size_t btr_get_buffer_by_reference(struct btr_buffer_reference *br, char **buf)
 159 {
 160         *buf = br->btrb->buf + br->consumed;
 161         return br_available_bytes(br);
 162 }
 163
 164 void btr_increase_used_bytes(struct btr_buffer_reference *br, size_t consumed)
 165 {
 166         br->consumed += consumed;
 167         if (br->consumed == br->btrb->size)
 168                 btr_drop_buffer_reference(br);
 169 }
 170
 171 static void flush_input_queue(struct btr_node *btrn)
 172 {
 173         struct btr_buffer_reference *br, *tmp;
 174         FOR_EACH_BUFFER_REF_SAFE(br, tmp, btrn)
 175                 btr_drop_buffer_reference(br);
 176 }
 177
 178 void btr_del_node(struct btr_node *btrn)
 179 {
 180         struct btr_node *ch;
 181
 182         FOR_EACH_CHILD(ch, btrn)
 183                 ch->parent = NULL;
 184         flush_input_queue(btrn);
 185         if (btrn->parent)
 186                 list_del(&btrn->node);
 187         free(btrn->name);
 188         free(btrn);
 189 }
 190
 191 size_t btr_get_input_queue_size(struct btr_node *btrn)
 192 {
 193         struct btr_buffer_reference *br;
 194         size_t size = 0;
 195
 196         FOR_EACH_BUFFER_REF(br, btrn)
 197                 size += br_available_bytes(br);
 198         return size;
 199 }
 200
 201 int main(void)
 202 {
 203         return 1;
 204 }