1 #ifndef AGGTREE_HH
2 #define AGGTREE_HH
3 #include <click/vector.hh>
4 #include <click/error.hh>
5 #include <cstdio>
6 class AggregateWTree;
7 struct AggregateWTree_WNode;
8
9 class AggregateTree { public:
10
11 enum WriteFormat { WR_UNKNOWN = -1, WR_ASCII = 0, WR_BINARY = 1, WR_ASCII_IP = 2 };
12
13 AggregateTree();
14 AggregateTree(const AggregateTree &);
15 AggregateTree(const AggregateWTree &);
16 ~AggregateTree();
17
18 bool ok(ErrorHandler * = 0) const;
19
num_nonzero() const20 uint32_t num_nonzero() const { return _num_nonzero; }
nnz() const21 uint32_t nnz() const { return _num_nonzero; }
22 uint32_t nnz_match(uint32_t mask, uint32_t value) const;
23
24 inline void add(uint32_t aggregate, int32_t count = 1);
25 void zero_aggregate(int, uint32_t);
26 void zero_masked_aggregate(uint32_t, uint32_t);
27
28 void posterize();
29
30 void prefixize(int prefix_len);
31 void make_prefix(int prefix_len, AggregateTree &) const;
32
33 void sample(double);
34 void cut_smaller(uint32_t);
35 void cut_larger(uint32_t);
36 void cut_smaller_aggregates(int, uint32_t);
37 void cut_larger_aggregates(int, uint32_t);
38 void cut_smaller_host_aggregates(int, uint32_t);
39 void cut_larger_host_aggregates(int, uint32_t);
40
41 void make_mapped(int prefix_len, const Vector<uint32_t> &map, AggregateTree &) const;
42
43 void num_active_prefixes(Vector<uint32_t> &) const;
44 void num_active_left_prefixes(Vector<uint32_t> &) const;
45
46 void haar_wavelet_energy_coeff(Vector<double> &) const;
47
48 void active_counts(Vector<uint32_t> &) const;
49 void randomly_assign_counts(const Vector<uint32_t> &);
50
51 void sum_and_sum_sq(double *, double *) const;
52
53 void balance(int prefix_len, FILE *) const;
54 void balance_histogram(int prefix_len, uint32_t nbuckets, Vector<uint32_t> &) const;
55
56 void branching_counts(int p, int layers_down, Vector<uint32_t> &) const;
57 void subtree_counts(int p, int layers_down, Vector<uint32_t> &) const;
58 void conditional_split_counts(int p, Vector<uint32_t> &) const;
59
60 void keep_common_hosts(const AggregateTree &, bool add = false);
61 void drop_common_hosts(const AggregateTree &);
62 void drop_common_unequal_hosts(const AggregateTree &);
63 void add_new_hosts(const AggregateTree &);
64 void take_nonzero_sizes(const AggregateTree &, uint32_t mask =0xFFFFFFFFU);
65
66 int read_file(FILE *, ErrorHandler *);
read_format() const67 WriteFormat read_format() const { return _read_format; }
68 int write_file(FILE *, WriteFormat, ErrorHandler *) const;
69
70 AggregateTree &operator=(const AggregateTree &);
71 AggregateTree &operator+=(const AggregateTree &);
72 AggregateTree &operator=(const AggregateWTree &);
73
74 struct Node {
75 uint32_t aggregate;
76 uint32_t count;
77 union {
78 Node *child[2];
79 AggregateWTree_WNode *wchild[2];
80 };
81 };
82
83 private:
84
85 Node *_root;
86 Node *_free;
87 enum { BLOCK_SIZE = 1024 };
88 Vector<Node *> _blocks;
89
90 uint32_t _num_nonzero;
91 WriteFormat _read_format;
92
93 inline Node *new_node();
94 Node *new_node_block();
95 inline void free_node(Node *);
96 void initialize_root();
97 void copy_nodes(const Node *, uint32_t = 0xFFFFFFFFU);
98 void kill_all_nodes();
99
100 Node *make_peer(uint32_t, Node *);
101 Node *find_node(uint32_t);
102 Node *find_existing_node(uint32_t) const;
103
104 uint32_t node_ok(Node *, int, ErrorHandler *) const;
105 void collapse_subtree(Node *);
106 void node_zero_aggregate(Node *, uint32_t, uint32_t);
107 void node_prefixize(Node *, int);
108 uint32_t node_to_discriminated_by(Node *, const AggregateTree &, uint32_t, bool);
109 void node_sample(Node *, uint32_t);
110 void node_cut_smaller(Node *, uint32_t);
111 void node_cut_larger(Node *, uint32_t);
112 void node_cut_aggregates(Node *, uint32_t, uint32_t &, uint32_t &, uint32_t, bool smaller, bool hosts);
113 void node_keep_common_hosts(Node *, const Node *[], int &, bool);
114 void node_drop_common_hosts(Node *, const Node *[], int &);
115 void node_drop_common_unequal_hosts(Node *, const Node *[], int &);
116 void node_take_nonzero_sizes(Node *, const Node *[], int &, uint32_t);
117 void node_randomly_assign_counts(Node *, Vector<uint32_t> &);
118
119 void read_packed_file(FILE *, int file_byte_order);
120 static void write_batch(FILE *, WriteFormat, uint32_t *, int, ErrorHandler *);
121 static void write_nodes(Node *, FILE *, WriteFormat, uint32_t *, int &, int, ErrorHandler *);
122 static void write_hex_nodes(Node *, FILE *, ErrorHandler *);
123
124 friend class AggregateWTree;
125
126 };
127
128 inline AggregateTree::Node *
new_node()129 AggregateTree::new_node()
130 {
131 if (_free) {
132 Node *n = _free;
133 _free = n->child[0];
134 return n;
135 } else
136 return new_node_block();
137 }
138
139 inline void
free_node(Node * n)140 AggregateTree::free_node(Node *n)
141 {
142 n->child[0] = _free;
143 _free = n;
144 }
145
146 inline void
add(uint32_t aggregate,int32_t count)147 AggregateTree::add(uint32_t aggregate, int32_t count)
148 {
149 if (count == 0)
150 /* nada */;
151 else if (Node *n = find_node(aggregate)) {
152 n->count += count;
153 if (n->count == (uint32_t)count)
154 _num_nonzero++;
155 else if (n->count == 0)
156 _num_nonzero--;
157 }
158 }
159
160 static inline uint32_t
prefix_to_mask(int p)161 prefix_to_mask(int p)
162 {
163 assert(p >= 0 && p <= 32);
164 return (p == 0 ? 0 : (0xFFFFFFFFU << (32 - p)));
165 }
166
167 extern int mask_to_prefix(uint32_t);
168
169 #endif
170