2 * Copyright (C) 2009, Frederic Weisbecker <fweisbec@gmail.com>
4 * Handle the callchains from the stream in an ad-hoc radix tree and then
5 * sort them in an rbtree.
14 #include "callchain.h"
17 static void rb_insert_callchain(struct rb_root *root, struct callchain_node *chain)
19 struct rb_node **p = &root->rb_node;
20 struct rb_node *parent = NULL;
21 struct callchain_node *rnode;
25 rnode = rb_entry(parent, struct callchain_node, rb_node);
27 if (rnode->hit < chain->hit)
33 rb_link_node(&chain->rb_node, parent, p);
34 rb_insert_color(&chain->rb_node, root);
38 * Once we get every callchains from the stream, we can now
41 void sort_chain_to_rbtree(struct rb_root *rb_root, struct callchain_node *node)
43 struct callchain_node *child;
45 list_for_each_entry(child, &node->children, brothers)
46 sort_chain_to_rbtree(rb_root, child);
49 rb_insert_callchain(rb_root, node);
52 static struct callchain_node *create_child(struct callchain_node *parent)
54 struct callchain_node *new;
56 new = malloc(sizeof(*new));
58 perror("not enough memory to create child for code path tree");
62 INIT_LIST_HEAD(&new->children);
63 INIT_LIST_HEAD(&new->val);
64 list_add_tail(&new->brothers, &parent->children);
70 fill_node(struct callchain_node *node, struct ip_callchain *chain, int start)
74 for (i = start; i < chain->nr; i++) {
75 struct callchain_list *call;
77 call = malloc(sizeof(*chain));
79 perror("not enough memory for the code path tree");
82 call->ip = chain->ips[i];
83 list_add_tail(&call->list, &node->val);
85 node->val_nr = i - start;
88 static void add_child(struct callchain_node *parent, struct ip_callchain *chain)
90 struct callchain_node *new;
92 new = create_child(parent);
93 fill_node(new, chain, parent->val_nr);
99 split_add_child(struct callchain_node *parent, struct ip_callchain *chain,
100 struct callchain_list *to_split, int idx)
102 struct callchain_node *new;
105 new = create_child(parent);
106 list_move_tail(&to_split->list, &new->val);
107 new->hit = parent->hit;
109 parent->val_nr = idx;
111 /* create the new one */
112 add_child(parent, chain);
116 __append_chain(struct callchain_node *root, struct ip_callchain *chain,
120 __append_chain_children(struct callchain_node *root, struct ip_callchain *chain)
122 struct callchain_node *rnode;
124 /* lookup in childrens */
125 list_for_each_entry(rnode, &root->children, brothers) {
126 int ret = __append_chain(rnode, chain, root->val_nr);
134 __append_chain(struct callchain_node *root, struct ip_callchain *chain,
137 struct callchain_list *cnode;
141 /* lookup in the current node */
142 list_for_each_entry(cnode, &root->val, list) {
143 if (cnode->ip != chain->ips[i++])
151 /* matches not, relay on the parent */
155 /* we match only a part of the node. Split it and add the new chain */
156 if (i < root->val_nr) {
157 split_add_child(root, chain, cnode, i);
161 /* we match 100% of the path, increment the hit */
162 if (i == root->val_nr) {
167 return __append_chain_children(root, chain);
170 void append_chain(struct callchain_node *root, struct ip_callchain *chain)
172 if (__append_chain_children(root, chain) == -1)
173 add_child(root, chain);