1 #include <click/config.h>
2 #include "aggtree.hh"
3 #include <click/glue.hh>
4 #include <click/confparse.hh>
5 #include <click/error.hh>
6 #include <click/integers.hh>	// for ffs_msb
7 #include <cstdlib>
8 #include <cstring>
9 #include <cmath>
10 
11 #ifdef HAVE_BYTEORDER_H
12 #include <byteorder.h>
13 #else
bswap_32(uint32_t u)14 static inline uint32_t bswap_32(uint32_t u) {
15     return ((u >> 24) | ((u & 0xff0000) >> 8) | ((u & 0xff00) << 8) | ((u & 0xff) << 24));
16 }
17 #endif
18 
19 
20 void
initialize_root()21 AggregateTree::initialize_root()
22 {
23     if (!(_root = new_node())) {
24 	fprintf(stderr, "out of memory!\n");
25 	abort();
26     }
27     _root->aggregate = 0;
28     _root->count = 0;
29     _root->child[0] = _root->child[1] = 0;
30     _num_nonzero = 0;
31 }
32 
33 void
copy_nodes(const Node * n,uint32_t mask)34 AggregateTree::copy_nodes(const Node *n, uint32_t mask)
35 {
36     if (n->count)
37 	add(n->aggregate & mask, n->count);
38     if (n->child[0]) {
39 	copy_nodes(n->child[0], mask);
40 	copy_nodes(n->child[1], mask);
41     }
42 }
43 
AggregateTree()44 AggregateTree::AggregateTree()
45     : _free(0), _read_format(WR_UNKNOWN)
46 {
47     initialize_root();
48 }
49 
AggregateTree(const AggregateTree & o)50 AggregateTree::AggregateTree(const AggregateTree &o)
51     : _free(0), _read_format(o._read_format)
52 {
53     initialize_root();
54     copy_nodes(o._root);
55 }
56 
~AggregateTree()57 AggregateTree::~AggregateTree()
58 {
59     kill_all_nodes();
60 }
61 
62 AggregateTree &
operator =(const AggregateTree & o)63 AggregateTree::operator=(const AggregateTree &o)
64 {
65     if (&o != this) {
66 	kill_all_nodes();
67 	initialize_root();
68 	copy_nodes(o._root);
69 	_read_format = o._read_format;
70     }
71     return *this;
72 }
73 
74 AggregateTree &
operator +=(const AggregateTree & o)75 AggregateTree::operator+=(const AggregateTree &o)
76 {
77     assert(&o != this);
78     copy_nodes(o._root);
79     return *this;
80 }
81 
82 AggregateTree::Node *
new_node_block()83 AggregateTree::new_node_block()
84 {
85     assert(!_free);
86     Node *block = new Node[BLOCK_SIZE];
87     if (!block)
88 	return 0;
89     _blocks.push_back(block);
90     for (int i = 1; i < BLOCK_SIZE - 1; i++)
91 	block[i].child[0] = &block[i+1];
92     block[BLOCK_SIZE - 1].child[0] = 0;
93     _free = &block[1];
94     return &block[0];
95 }
96 
97 void
kill_all_nodes()98 AggregateTree::kill_all_nodes()
99 {
100     for (int i = 0; i < _blocks.size(); i++)
101 	delete[] _blocks[i];
102     _blocks.clear();
103     _root = _free = 0;
104 }
105 
106 int
mask_to_prefix(uint32_t mask)107 mask_to_prefix(uint32_t mask)
108 {
109     if (mask == 0xFFFFFFFFU)
110 	return 32;
111     int possible_p = ffs_msb(~mask) - 1;
112     uint32_t new_mask = prefix_to_mask(possible_p);
113     return (new_mask == mask ? possible_p : -1);
114 }
115 
116 //
117 // check to see tree is OK
118 //
119 
120 uint32_t
node_ok(Node * n,int last_swivel,ErrorHandler * errh) const121 AggregateTree::node_ok(Node *n, int last_swivel, ErrorHandler *errh) const
122 {
123 #if 0
124     for (int i = 0; i < _blocks.size(); i++)
125 	if (n >= _blocks[i] && n < _blocks[i] + BLOCK_SIZE)
126 	    goto found_block;
127     return errh->error("%x: memory corruption at %p", n->aggregate, n);
128   found_block:
129 #endif
130 
131     if (n->child[0] && n->child[1]) {
132 	int swivel = ffs_msb(n->child[0]->aggregate ^ n->child[1]->aggregate);
133 	if (swivel == 0)
134 	    return errh->error("%x: bad swivel 0 (%x-%x %p-%p)", n->aggregate, n->child[0]->aggregate, n->child[1]->aggregate, n->child[0], n->child[1]);
135 	if (swivel <= last_swivel)
136 	    return errh->error("%x: bad swivel %d <= %d (%x-%x)", n->aggregate, swivel, last_swivel, n->child[0]->aggregate, n->child[1]->aggregate);
137 
138 	uint32_t mask = (swivel == 1 ? 0 : 0xFFFFFFFFU << (33 - swivel));
139 	if ((n->child[0]->aggregate & mask) != (n->aggregate & mask))
140 	    return errh->error("%x: left child doesn't match upper bits (swivel %d)", n->aggregate, swivel);
141 	if ((n->child[1]->aggregate & mask) != (n->aggregate & mask))
142 	    return errh->error("%x: right child doesn't match upper bits (swivel %d)", n->aggregate, swivel);
143 
144 	mask = (1U << (32 - swivel));
145 	if ((n->child[0]->aggregate & mask) != 0)
146 	    return errh->error("%x: left child swivel bit one (swivel %d)", n->aggregate, swivel);
147 	if ((n->child[1]->aggregate & mask) == 0)
148 	    return errh->error("%x: right child swivel bit zero (swivel %d)", n->aggregate, swivel);
149 
150 	mask = (swivel == 1 ? 0xFFFFFFFFU : (1 << (32 - swivel)) - 1);
151 	if (n->aggregate & mask)
152 	    return errh->error("%x: lower bits nonzero (swivel %d)", n->aggregate, swivel);
153 
154 	// check topheaviness
155 	if (n->aggregate == n->child[0]->aggregate && n->child[0]->count)
156 	    return errh->error("%x: packets present in copied left child", n->aggregate);
157 
158 	int ok1 = node_ok(n->child[0], swivel, errh);
159 	int ok2 = node_ok(n->child[1], swivel, errh);
160 	int local_nnz = (n->count ? 1 : 0);
161 	return ok1 + ok2 + local_nnz;
162 
163     } else if (n->child[0] || n->child[1])
164 	return errh->error("%x: only one live child", n->aggregate);
165     else
166 	return (n->count ? 1 : 0);
167 }
168 
169 bool
ok(ErrorHandler * errh) const170 AggregateTree::ok(ErrorHandler *errh) const
171 {
172     if (!errh)
173 	errh = ErrorHandler::default_handler();
174 
175     int before = errh->nerrors();
176     uint32_t nnz = node_ok(_root, -1, errh);
177     if (errh->nerrors() == before && nnz != _num_nonzero)
178 	errh->error("bad num_nonzero: nominally %u, calculated %u", _num_nonzero, nnz);
179 
180     return (errh->nerrors() == before);
181 }
182 
183 
184 //
185 // TREE CONSTRUCTION
186 //
187 
188 AggregateTree::Node *
make_peer(uint32_t a,Node * n)189 AggregateTree::make_peer(uint32_t a, Node *n)
190 {
191     /*
192      * become a peer
193      * algo: create two nodes, the two peers.  leave orig node as
194      * the parent of the two new ones.
195      */
196 
197     Node *down[2];
198     if (!(down[0] = new_node()))
199 	return 0;
200     if (!(down[1] = new_node())) {
201 	free_node(down[0]);
202 	return 0;
203     }
204 
205     // swivel is first bit 'a' and 'old->input' differ
206     int swivel = ffs_msb(a ^ n->aggregate);
207     // bitvalue is the value of that bit of 'a'
208     int bitvalue = (a >> (32 - swivel)) & 1;
209     // mask masks off all bits before swivel
210     uint32_t mask = (swivel == 1 ? 0 : (0xFFFFFFFFU << (33 - swivel)));
211 
212     down[bitvalue]->aggregate = a;
213     down[bitvalue]->count = 0;
214     down[bitvalue]->child[0] = down[bitvalue]->child[1] = 0;
215 
216     *down[1 - bitvalue] = *n;	/* copy orig node down one level */
217 
218     n->aggregate = (down[0]->aggregate & mask);
219     if (down[0]->aggregate == n->aggregate) {
220 	n->count = down[0]->count;
221 	down[0]->count = 0;
222     } else
223 	n->count = 0;
224     n->child[0] = down[0];	/* point to children */
225     n->child[1] = down[1];
226 
227     return (n->aggregate == a ? n : down[bitvalue]);
228 }
229 
230 AggregateTree::Node *
find_node(uint32_t a)231 AggregateTree::find_node(uint32_t a)
232 {
233     // straight outta tcpdpriv
234     Node *n = _root;
235     while (n) {
236 	if (n->aggregate == a)
237 	    return n;
238 	if (!n->child[0])
239 	    n = make_peer(a, n);
240 	else {
241 	    // swivel is the first bit in which the two children differ
242 	    int swivel = ffs_msb(n->child[0]->aggregate ^ n->child[1]->aggregate);
243 	    if (ffs_msb(a ^ n->aggregate) < swivel) // input differs earlier
244 		n = make_peer(a, n);
245 	    else if (a & (1 << (32 - swivel)))
246 		n = n->child[1];
247 	    else
248 		n = n->child[0];
249 	}
250     }
251 
252     fprintf(stderr, "AggregateTree: out of memory!\n");
253     return 0;
254 }
255 
256 AggregateTree::Node *
find_existing_node(uint32_t a) const257 AggregateTree::find_existing_node(uint32_t a) const
258 {
259     // straight outta tcpdpriv
260     Node *n = _root;
261     while (n) {
262 	if (n->aggregate == a)
263 	    return n;
264 	if (!n->child[0])
265 	    return 0;
266 	else {
267 	    // swivel is the first bit in which the two children differ
268 	    int swivel = ffs_msb(n->child[0]->aggregate ^ n->child[1]->aggregate);
269 	    if (ffs_msb(a ^ n->aggregate) < swivel) // input differs earlier
270 		return 0;
271 	    else if (a & (1 << (32 - swivel)))
272 		n = n->child[1];
273 	    else
274 		n = n->child[0];
275 	}
276     }
277     return 0;
278 }
279 
280 void
collapse_subtree(Node * root)281 AggregateTree::collapse_subtree(Node *root)
282 {
283     if (root->child[0]) {
284 	collapse_subtree(root->child[0]);
285 	collapse_subtree(root->child[1]);
286 
287 	int old_nnz = (root->count != 0) + (root->child[0]->count != 0) + (root->child[1]->count != 0);
288 	root->count += root->child[0]->count + root->child[1]->count;
289 	_num_nonzero += (root->count != 0) - old_nnz;
290 
291 	free_node(root->child[0]);
292 	free_node(root->child[1]);
293 	root->child[0] = root->child[1] = 0;
294     }
295 }
296 
297 void
node_zero_aggregate(Node * n,uint32_t mask,uint32_t value)298 AggregateTree::node_zero_aggregate(Node *n, uint32_t mask, uint32_t value)
299 {
300     if ((n->aggregate & mask) == value && n->count) {
301 	n->count = 0;
302 	_num_nonzero--;
303     }
304     if (n->child[0]) {
305 	// swivel is the first bit in which the two children differ
306 	int swivel = ffs_msb(n->child[0]->aggregate ^ n->child[1]->aggregate);
307 	uint32_t swivel_mask = (swivel == 1 ? 0 : 0xFFFFFFFFU << (33 - swivel)) & mask;
308 	if ((n->child[0]->aggregate & swivel_mask) == (value & swivel_mask))
309 	    node_zero_aggregate(n->child[0], mask, value);
310 	if ((n->child[1]->aggregate & swivel_mask) == (value & swivel_mask))
311 	    node_zero_aggregate(n->child[1], mask, value);
312     }
313 }
314 
315 void
zero_aggregate(int prefix_len,uint32_t value)316 AggregateTree::zero_aggregate(int prefix_len, uint32_t value)
317 {
318     uint32_t mask = prefix_to_mask(prefix_len);
319     assert((value & mask) == value);
320     node_zero_aggregate(_root, mask, value);
321     // assert(nnz_match(mask, value) == 0); // expensive
322 }
323 
324 void
zero_masked_aggregate(uint32_t mask,uint32_t value)325 AggregateTree::zero_masked_aggregate(uint32_t mask, uint32_t value)
326 {
327     int p = mask_to_prefix(mask);
328     assert(p >= 0);
329     zero_aggregate(p, value);
330 }
331 
332 //
333 // COUNTING
334 //
335 
336 static uint32_t
node_count_match(AggregateTree::Node * n,uint32_t mask,uint32_t value,bool count)337 node_count_match(AggregateTree::Node *n, uint32_t mask, uint32_t value,
338 		 bool count)
339 {
340     uint32_t result;
341     if (n->count > 0 && (n->aggregate & mask) == value)
342 	result = (count ? n->count : 1);
343     else
344 	result = 0;
345     if (n->child[0])
346 	return (result
347 		+ node_count_match(n->child[0], mask, value, count)
348 		+ node_count_match(n->child[1], mask, value, count));
349     else
350 	return result;
351 }
352 
353 uint32_t
nnz_match(uint32_t mask,uint32_t value) const354 AggregateTree::nnz_match(uint32_t mask, uint32_t value) const
355 {
356     assert((value & mask) == value);
357     return node_count_match(_root, mask, value, false);
358 }
359 
360 
361 static void
node_sum_and_sum_sq(AggregateTree::Node * n,double * sum,double * sum_sq)362 node_sum_and_sum_sq(AggregateTree::Node *n, double *sum, double *sum_sq)
363 {
364     *sum += n->count;
365     *sum_sq += ((double)n->count) * n->count;
366     if (n->child[0]) {
367 	node_sum_and_sum_sq(n->child[0], sum, sum_sq);
368 	node_sum_and_sum_sq(n->child[1], sum, sum_sq);
369     }
370 }
371 
372 void
sum_and_sum_sq(double * sum,double * sum_sq) const373 AggregateTree::sum_and_sum_sq(double *sum, double *sum_sq) const
374 {
375     double s = 0, ss = 0;
376     node_sum_and_sum_sq(_root, &s, &ss);
377     if (sum)
378 	*sum = s;
379     if (sum_sq)
380 	*sum_sq = ss;
381 }
382 
383 
384 static uint32_t *
node_active_counts(AggregateTree::Node * n,uint32_t * vec)385 node_active_counts(AggregateTree::Node *n, uint32_t *vec)
386 {
387     if (n->count)
388 	*vec++ = n->count;
389     if (n->child[0]) {
390 	vec = node_active_counts(n->child[0], vec);
391 	vec = node_active_counts(n->child[1], vec);
392     }
393     return vec;
394 }
395 
396 void
active_counts(Vector<uint32_t> & vec) const397 AggregateTree::active_counts(Vector<uint32_t> &vec) const
398 {
399     vec.resize(_num_nonzero);
400     if (_num_nonzero) {
401 	uint32_t *end_vec = node_active_counts(_root, &vec[0]);
402 	assert((uint32_t)(end_vec - &vec[0]) == _num_nonzero);
403 	(void) end_vec;
404     }
405 }
406 
407 
408 void
node_randomly_assign_counts(Node * n,Vector<uint32_t> & v)409 AggregateTree::node_randomly_assign_counts(Node *n, Vector<uint32_t> &v)
410 {
411     if (n->count) {
412 	int which = random() % v.size();
413 	n->count = v[which];
414 	if (!n->count)
415 	    _num_nonzero--;
416 	v[which] = v.back();
417 	v.pop_back();
418     }
419     if (n->child[0]) {
420 	node_randomly_assign_counts(n->child[0], v);
421 	node_randomly_assign_counts(n->child[1], v);
422     }
423 }
424 
425 void
randomly_assign_counts(const Vector<uint32_t> & vec)426 AggregateTree::randomly_assign_counts(const Vector<uint32_t> &vec)
427 {
428     assert((uint32_t) vec.size() == _num_nonzero);
429     Vector<uint32_t> v(vec);
430     node_randomly_assign_counts(_root, v);
431 }
432 
433 
434 //
435 // POSTERIZATION
436 //
437 
438 static void
node_posterize(AggregateTree::Node * n)439 node_posterize(AggregateTree::Node *n)
440 {
441     if (n->count)
442 	n->count = 1;
443     if (n->child[0]) {
444 	node_posterize(n->child[0]);
445 	node_posterize(n->child[1]);
446     }
447 }
448 
449 void
posterize()450 AggregateTree::posterize()
451 {
452     node_posterize(_root);
453 }
454 
455 
456 //
457 // SAMPLING
458 //
459 
460 void
node_sample(Node * n,uint32_t taking)461 AggregateTree::node_sample(Node *n, uint32_t taking)
462 {
463     if (n->count) {
464 	for (uint32_t i = n->count; i > 0; i--)
465 	    if (((uint32_t)random()) >= taking)
466 		n->count--;
467 	if (!n->count)
468 	    _num_nonzero--;
469     }
470     if (n->child[0]) {
471 	node_sample(n->child[0], taking);
472 	node_sample(n->child[1], taking);
473     }
474 }
475 
476 void
sample(double sample_prob)477 AggregateTree::sample(double sample_prob)
478 {
479     assert(sample_prob >= 0);
480     if (sample_prob < 1) {
481 	uint32_t taking = (uint32_t)(((uint32_t)RAND_MAX + 1) * sample_prob);
482 	node_sample(_root, taking);
483     }
484 }
485 
486 
487 void
node_cut_smaller(Node * n,uint32_t smallest)488 AggregateTree::node_cut_smaller(Node *n, uint32_t smallest)
489 {
490     if (n->count && n->count < smallest) {
491 	n->count = 0;
492 	_num_nonzero--;
493     }
494     if (n->child[0]) {
495 	node_cut_smaller(n->child[0], smallest);
496 	node_cut_smaller(n->child[1], smallest);
497     }
498 }
499 
500 void
cut_smaller(uint32_t smallest)501 AggregateTree::cut_smaller(uint32_t smallest)
502 {
503     node_cut_smaller(_root, smallest);
504 }
505 
506 
507 void
node_cut_larger(Node * n,uint32_t largest)508 AggregateTree::node_cut_larger(Node *n, uint32_t largest)
509 {
510     if (n->count && n->count >= largest) {
511 	n->count = 0;
512 	_num_nonzero--;
513     }
514     if (n->child[0]) {
515 	node_cut_larger(n->child[0], largest);
516 	node_cut_larger(n->child[1], largest);
517     }
518 }
519 
520 void
cut_larger(uint32_t largest)521 AggregateTree::cut_larger(uint32_t largest)
522 {
523     node_cut_larger(_root, largest);
524 }
525 
526 
527 void
node_cut_aggregates(Node * n,uint32_t mask,uint32_t & value,uint32_t & count,uint32_t size_boundary,bool smallerp,bool hostsp)528 AggregateTree::node_cut_aggregates(Node *n, uint32_t mask, uint32_t &value, uint32_t &count, uint32_t size_boundary, bool smallerp, bool hostsp)
529 {
530     if ((n->aggregate & mask) != value) {
531 	assert((n->aggregate & mask) > value);
532 	bool this_smallerp = (count < size_boundary);
533 	if (count && (smallerp == this_smallerp))
534 	    zero_masked_aggregate(mask, value);
535 	count = 0;
536 	value = (n->aggregate & mask);
537     }
538     count += (hostsp ? n->count != 0 : n->count);
539     if (n->child[0]) {
540 	node_cut_aggregates(n->child[0], mask, value, count, size_boundary, smallerp, hostsp);
541 	node_cut_aggregates(n->child[1], mask, value, count, size_boundary, smallerp, hostsp);
542     }
543 }
544 
545 void
cut_smaller_aggregates(int p,uint32_t smallest)546 AggregateTree::cut_smaller_aggregates(int p, uint32_t smallest)
547 {
548     uint32_t value = 0, count = 0;
549     uint32_t mask = prefix_to_mask(p);
550     node_cut_aggregates(_root, mask, value, count, smallest, true, false);
551     if (count && count < smallest)
552 	zero_masked_aggregate(mask, value);
553 }
554 
555 void
cut_larger_aggregates(int p,uint32_t largest)556 AggregateTree::cut_larger_aggregates(int p, uint32_t largest)
557 {
558     uint32_t value = 0, count = 0;
559     uint32_t mask = prefix_to_mask(p);
560     node_cut_aggregates(_root, mask, value, count, largest, false, false);
561     if (count && count >= largest)
562 	zero_masked_aggregate(mask, value);
563 }
564 
565 void
cut_smaller_host_aggregates(int p,uint32_t smallest)566 AggregateTree::cut_smaller_host_aggregates(int p, uint32_t smallest)
567 {
568     uint32_t value = 0, count = 0;
569     uint32_t mask = prefix_to_mask(p);
570     node_cut_aggregates(_root, mask, value, count, smallest, true, true);
571     if (count && count < smallest)
572 	zero_masked_aggregate(mask, value);
573 }
574 
575 void
cut_larger_host_aggregates(int p,uint32_t largest)576 AggregateTree::cut_larger_host_aggregates(int p, uint32_t largest)
577 {
578     uint32_t value = 0, count = 0;
579     uint32_t mask = prefix_to_mask(p);
580     node_cut_aggregates(_root, mask, value, count, largest, false, true);
581     if (count && count >= largest)
582 	zero_masked_aggregate(mask, value);
583 }
584 
585 
586 //
587 // PREFIXES
588 //
589 
590 void
node_prefixize(Node * n,int prefix)591 AggregateTree::node_prefixize(Node *n, int prefix)
592 {
593     uint32_t mask = prefix_to_mask(prefix);
594 
595     if ((n->aggregate & mask) != n->aggregate) {
596 	collapse_subtree(n);
597 	n->aggregate &= mask;
598 
599     } else if (n->child[0]) {
600 	int swivel = ffs_msb(n->child[0]->aggregate ^ n->child[1]->aggregate);
601 	//ErrorHandler::default_handler()->message("%d", swivel);
602 
603 	if (swivel <= prefix) {
604 	    node_prefixize(n->child[0], prefix);
605 	    node_prefixize(n->child[1], prefix);
606 	} else {
607 	    // assert((n->child[0]->aggregate & mask) == (n->child[1]->aggregate & mask)); -- true
608 	    collapse_subtree(n->child[0]);
609 	    collapse_subtree(n->child[1]);
610 	    if (n->child[0]->count && n->child[1]->count)
611 		_num_nonzero--;
612 	    n->child[0]->aggregate &= mask;
613 	    n->child[0]->count += n->child[1]->count;
614 	    n->child[1]->aggregate = n->child[0]->aggregate | 1;
615 	    n->child[1]->count = 0;
616 	}
617 
618 	if (n->child[0]->aggregate == n->aggregate) {
619 	    if (n->child[0]->count && n->count)
620 		_num_nonzero--;
621 	    n->count += n->child[0]->count;
622 	    n->child[0]->count = 0;
623 	}
624     }
625 }
626 
627 void
prefixize(int prefix_len)628 AggregateTree::prefixize(int prefix_len)
629 {
630     assert(prefix_len >= 0 && prefix_len <= 32);
631     if (prefix_len < 32)
632 	node_prefixize(_root, prefix_len);
633 }
634 
635 void
make_prefix(int prefix_len,AggregateTree & t) const636 AggregateTree::make_prefix(int prefix_len, AggregateTree &t) const
637 {
638     assert(prefix_len >= 0 && prefix_len <= 32);
639     t.copy_nodes(_root, prefix_to_mask(prefix_len));
640 }
641 
642 void
num_active_prefixes(Vector<uint32_t> & out) const643 AggregateTree::num_active_prefixes(Vector<uint32_t> &out) const
644 {
645     AggregateTree copy(*this);
646     out.assign(33, 0);
647     out[32] = nnz();
648     for (int i = 31; i >= 0; i--) {
649 	copy.prefixize(i);
650 	out[i] = copy.nnz();
651     }
652 }
653 
654 void
num_active_left_prefixes(Vector<uint32_t> & out) const655 AggregateTree::num_active_left_prefixes(Vector<uint32_t> &out) const
656 {
657     AggregateTree copy(*this);
658     out.assign(33, 0);
659     out[32] = nnz_match(1, 0);
660     for (int i = 31; i >= 0; i--) {
661 	copy.prefixize(i);
662 	out[i] = copy.nnz_match(1 << (32 - i), 0);
663     }
664 }
665 
666 
667 //
668 // MAPPING
669 //
670 
671 static void
node_make_mapped(const AggregateTree::Node * n,AggregateTree & new_tree,int shift,uint32_t neg_mask,const uint32_t * map)672 node_make_mapped(const AggregateTree::Node *n, AggregateTree &new_tree,
673 		 int shift, uint32_t neg_mask, const uint32_t *map)
674 {
675     if (n->count) {
676 	uint32_t new_aggregate = (n->aggregate & neg_mask)
677 	    | (map[n->aggregate >> shift] << shift);
678 	new_tree.add(new_aggregate, n->count);
679     }
680     if (n->child[0]) {
681 	node_make_mapped(n->child[0], new_tree, shift, neg_mask, map);
682 	node_make_mapped(n->child[1], new_tree, shift, neg_mask, map);
683     }
684 }
685 
686 void
make_mapped(int prefix_len,const Vector<uint32_t> & map,AggregateTree & new_tree) const687 AggregateTree::make_mapped(int prefix_len, const Vector<uint32_t> &map, AggregateTree &new_tree) const
688 {
689     assert(prefix_len >= 0 && prefix_len <= 32);
690     if (prefix_len == 0)
691 	new_tree += *this;
692     else {
693 	assert(map.size() == (1 << prefix_len));
694 	node_make_mapped(_root, new_tree, 32 - prefix_len, 0xFFFFFFFFU >> prefix_len, &map[0]);
695     }
696 }
697 
698 
699 //
700 // LEFT/RIGHT BALANCE
701 //
702 
703 static void
node_balance(AggregateTree::Node * n,AggregateTree::Node ** last,uint32_t prefix_mask,FILE * f)704 node_balance(AggregateTree::Node *n, AggregateTree::Node **last,
705 	     uint32_t prefix_mask, FILE *f)
706 {
707     if (n->count) {
708 	assert((n->aggregate & (~prefix_mask >> 1)) == 0);
709 	if (*last && ((*last)->aggregate & prefix_mask) == (n->aggregate & prefix_mask)) {
710 	    assert(n->aggregate & ~prefix_mask);
711 	    fprintf(f, "%u %u %u\n", (n->aggregate & prefix_mask), (*last)->count, n->count);
712 	    *last = 0;
713 	} else {
714 	    if (*last)
715 		fprintf(f, "%u %u 0\n", ((*last)->aggregate & prefix_mask), (*last)->count);
716 	    if (n->aggregate & ~prefix_mask) {
717 		fprintf(f, "%u 0 %u\n", (n->aggregate & prefix_mask), n->count);
718 		*last = 0;
719 	    } else
720 		*last = n;
721 	}
722     }
723 
724     if (n->child[0]) {
725 	node_balance(n->child[0], last, prefix_mask, f);
726 	node_balance(n->child[1], last, prefix_mask, f);
727     }
728 }
729 
730 void
balance(int p,FILE * f) const731 AggregateTree::balance(int p, FILE *f) const
732 {
733     assert(p >= 0 && p <= 31);
734     Node *last = 0;
735     uint32_t prefix_mask = prefix_to_mask(p);
736     node_balance(_root, &last, prefix_mask, f);
737     if (last)
738 	fprintf(f, "%u %u 0\n", (last->aggregate & prefix_mask), last->count);
739 }
740 
741 
742 static void
node_balance_histogram(AggregateTree::Node * n,AggregateTree::Node ** last,uint32_t prefix_mask,double factor,Vector<uint32_t> & v)743 node_balance_histogram(AggregateTree::Node *n, AggregateTree::Node **last,
744 		       uint32_t prefix_mask, double factor, Vector<uint32_t> &v)
745 {
746     if (n->count) {
747 	assert((n->aggregate & (~prefix_mask >> 1)) == 0);
748 	if (*last && ((*last)->aggregate & prefix_mask) == (n->aggregate & prefix_mask)) {
749 	    assert(n->aggregate & ~prefix_mask);
750 	    double c0 = (double)((*last)->count);
751 	    double sum = c0 + (double)n->count;
752 	    if (c0 == 0)
753 		v[0]++;
754 	    else if (c0 == sum)
755 		v.back()++;
756 	    else {
757 		uint32_t which = (uint32_t)ceil((c0 / sum) * factor);
758 		v[which]++;
759 	    }
760 	    *last = 0;
761 	} else {
762 	    if (*last)
763 		v.back()++;
764 	    if (n->aggregate & ~prefix_mask) {
765 		v[0]++;
766 		*last = 0;
767 	    } else
768 		*last = n;
769 	}
770     }
771 
772     if (n->child[0]) {
773 	node_balance_histogram(n->child[0], last, prefix_mask, factor, v);
774 	node_balance_histogram(n->child[1], last, prefix_mask, factor, v);
775     }
776 }
777 
778 void
balance_histogram(int p,uint32_t nbuckets,Vector<uint32_t> & out) const779 AggregateTree::balance_histogram(int p, uint32_t nbuckets, Vector<uint32_t> &out) const
780 {
781     assert(p >= 0 && p <= 31);
782     out.assign(nbuckets + 1, 0);
783     Node *last = 0;
784     uint32_t prefix_mask = prefix_to_mask(p);
785     node_balance_histogram(_root, &last, prefix_mask, nbuckets, out);
786     if (last)
787 	out[0]++;
788 }
789 
790 
791 //
792 // WAVELET STUFF
793 //
794 
795 static double
node_haar_energy(AggregateTree::Node * n,AggregateTree::Node ** last,uint32_t prefix_mask)796 node_haar_energy(AggregateTree::Node *n, AggregateTree::Node **last,
797 		 uint32_t prefix_mask)
798 {
799     double amt = 0;
800 
801     if (n->count) {
802 	if (!*last)
803 	    *last = n;
804 	else if ((n->aggregate & prefix_mask) != ((*last)->aggregate & prefix_mask)) {
805 	    amt = (*last)->count;
806 	    amt *= amt;
807 	    *last = n;
808 	} else {
809 	    amt = (double)(n->count) - (double)((*last)->count);
810 	    amt *= amt;
811 	    *last = 0;
812 	}
813     }
814 
815 
816     if (n->child[0]) {
817 	amt += node_haar_energy(n->child[0], last, prefix_mask);
818 	amt += node_haar_energy(n->child[1], last, prefix_mask);
819     }
820 
821     return amt;
822 }
823 
824 void
haar_wavelet_energy_coeff(Vector<double> & out) const825 AggregateTree::haar_wavelet_energy_coeff(Vector<double> &out) const
826 {
827     AggregateTree copy(*this);
828     out.assign(32, 0);
829 
830     for (int p = 31; p >= 0; p--) {
831 	Node *last = 0;
832 	double sum_sq_diff = node_haar_energy(copy._root, &last, prefix_to_mask(p));
833 	if (last)
834 	    sum_sq_diff += ((double)last->count) * last->count;
835 
836 	out[p] = sum_sq_diff / 4294967296.0;
837 
838 	copy.prefixize(p);
839     }
840 }
841 
842 
843 //
844 // CONDITIONAL SPLIT PROBABILITIES
845 //
846 
847 static void
node_branching_counts(AggregateTree::Node * n,uint32_t mask,uint32_t & value,int shift,int & count,uint32_t * results)848 node_branching_counts(AggregateTree::Node *n, uint32_t mask, uint32_t &value, int shift, int &count, uint32_t *results)
849 {
850     if (n->count > 0 && ((n->aggregate & mask) != value || !count)) {
851 	if ((n->aggregate & (mask << shift)) != (value & (mask << shift))
852 	    && count) {
853 	    results[count]++;
854 	    count = 0;
855 	}
856 	value = (n->aggregate & mask);
857 	count++;
858     }
859     if (n->child[0]) {
860 	node_branching_counts(n->child[0], mask, value, shift, count, results);
861 	node_branching_counts(n->child[1], mask, value, shift, count, results);
862     }
863 }
864 
865 void
branching_counts(int p,int layers_down,Vector<uint32_t> & v) const866 AggregateTree::branching_counts(int p, int layers_down, Vector<uint32_t> &v) const
867 {
868     assert(p >= 0 && layers_down > 0 && p + layers_down <= 32);
869     v.assign((1 << layers_down) + 1, 0);
870     int count = 0;
871     uint32_t value = 0;
872     uint32_t mask = prefix_to_mask(p + layers_down);
873     node_branching_counts(_root, mask, value, layers_down, count, &v[0]);
874     if (count)
875 	v[count]++;
876 }
877 
878 
879 static void
node_subtree_counts(AggregateTree::Node * n,uint32_t mask,uint32_t & value,int shift,int & bits,uint32_t * results)880 node_subtree_counts(AggregateTree::Node *n, uint32_t mask, uint32_t &value, int shift, int &bits, uint32_t *results)
881 {
882     if (n->count > 0 && ((n->aggregate & mask) != value || bits < 0)) {
883 	uint32_t value_highbits = (value & (mask << shift));
884 	uint32_t highbits = (n->aggregate & (mask << shift));
885 	if (value_highbits != highbits || bits < 0) {
886 	    if (bits >= 0)
887 		results[bits]++;
888 	    bits = 0;
889 	}
890 	value = (n->aggregate & mask);
891 	uint32_t bit_delta = ~mask + 1;
892 	assert((bit_delta & mask) == bit_delta);
893 	int which = 0;
894 	for (uint32_t x = highbits; x != value; x += bit_delta)
895 	    which++;
896 	bits |= (1 << which);
897     }
898     if (n->child[0]) {
899 	node_subtree_counts(n->child[0], mask, value, shift, bits, results);
900 	node_subtree_counts(n->child[1], mask, value, shift, bits, results);
901     }
902 }
903 
904 void
subtree_counts(int p,int layers_down,Vector<uint32_t> & v) const905 AggregateTree::subtree_counts(int p, int layers_down, Vector<uint32_t> &v) const
906 {
907     assert(p >= 0 && layers_down > 0 && p + layers_down <= 32 && layers_down < 5);
908     v.assign((1 << (1 << layers_down)), 0);
909     int bits = 0;
910     uint32_t value = 0;
911     uint32_t mask = prefix_to_mask(p + layers_down);
912     node_subtree_counts(_root, mask, value, layers_down, bits, &v[0]);
913     if (_num_nonzero)
914 	v[bits]++;
915 }
916 
917 
918 static void
cond_split_handle_collection(AggregateTree::Node * collection[4],int & pos,uint32_t results[4],uint32_t mask)919 cond_split_handle_collection(AggregateTree::Node *collection[4], int &pos, uint32_t results[4], uint32_t mask)
920 {
921     switch (pos) {
922       case 0: break;
923       case 1: results[0]++; break;
924       case 3: results[2]++; results[3]++; break;
925       case 4: results[3] += 2; break;
926       case 2: {
927 	  if ((collection[0]->aggregate & (mask << 1))
928 	      == (collection[1]->aggregate & (mask << 1)))
929 	      results[1]++;
930 	  else
931 	      results[2] += 2;
932 	  break;
933       }
934       default: assert(0);
935     }
936     pos = 0;
937 }
938 
939 static void
node_conditional_split_counts(AggregateTree::Node * n,uint32_t mask,uint32_t & value,AggregateTree::Node * collection[4],int & pos,uint32_t results[4])940 node_conditional_split_counts(AggregateTree::Node *n, uint32_t mask, uint32_t &value, AggregateTree::Node *collection[4], int &pos, uint32_t results[4])
941 {
942     if (n->count > 0 && ((n->aggregate & mask) != value || !pos)) {
943 	if ((n->aggregate & (mask << 2)) != (value & (mask << 2)))
944 	    cond_split_handle_collection(collection, pos, results, mask);
945 	value = (n->aggregate & mask);
946 	collection[pos++] = n;
947     }
948     if (n->child[0]) {
949 	node_conditional_split_counts(n->child[0], mask, value, collection, pos, results);
950 	node_conditional_split_counts(n->child[1], mask, value, collection, pos, results);
951     }
952 }
953 
954 void
conditional_split_counts(int p,Vector<uint32_t> & v) const955 AggregateTree::conditional_split_counts(int p, Vector<uint32_t> &v) const
956 {
957     assert(p >= 1 && p <= 31);
958     v.assign(4, 0);
959     Node *collection[4];
960     int pos = 0;
961     uint32_t value = 0;
962     uint32_t mask = prefix_to_mask(p + 1);
963     node_conditional_split_counts(_root, mask, value, collection, pos, &v[0]);
964     cond_split_handle_collection(collection, pos, &v[0], mask);
965 }
966 
967 
968 //
969 // COMBINING TREES
970 //
971 
972 static const AggregateTree::Node *
preorder_step(const AggregateTree::Node * other_stack[],int & other_pos)973 preorder_step(const AggregateTree::Node *other_stack[], int &other_pos)
974 {
975     if (other_pos == 0)
976 	return 0;
977 
978     // if current node has a left child, return that
979     const AggregateTree::Node *n = other_stack[other_pos - 1]->child[0];
980     if (n) {
981 	other_stack[other_pos++] = n;
982 	return n;
983     }
984 
985     // otherwise, back up and take a right child
986     other_pos--;
987     while (other_pos > 0 && other_stack[other_pos - 1]->child[1] == other_stack[other_pos])
988 	other_pos--;
989 
990     if (other_pos > 0) {
991 	const AggregateTree::Node *n = other_stack[other_pos - 1]->child[1];
992 	other_stack[other_pos++] = n;
993 	return n;
994     } else
995 	return 0;
996 }
997 
998 void
node_keep_common_hosts(Node * n,const Node * other_stack[],int & other_pos,bool add)999 AggregateTree::node_keep_common_hosts(Node *n, const Node *other_stack[], int &other_pos, bool add)
1000 {
1001     if (n->count) {
1002 	const Node *other = (other_pos ? other_stack[other_pos - 1] : 0);
1003 	while (other && other->aggregate < n->aggregate)
1004 	    other = preorder_step(other_stack, other_pos);
1005 	if (!other || other->aggregate > n->aggregate
1006 	    || (other->aggregate == n->aggregate && other->count == 0)) {
1007 	    n->count = 0;
1008 	    _num_nonzero--;
1009 	} else if (add && other->aggregate == n->aggregate)
1010 	    n->count += other->count;
1011     }
1012     if (n->child[0]) {
1013 	node_keep_common_hosts(n->child[0], other_stack, other_pos, add);
1014 	node_keep_common_hosts(n->child[1], other_stack, other_pos, add);
1015     }
1016 }
1017 
1018 void
keep_common_hosts(const AggregateTree & other,bool add)1019 AggregateTree::keep_common_hosts(const AggregateTree &other, bool add)
1020 {
1021     const Node *other_stack[32];
1022     other_stack[0] = other._root;
1023     int other_pos = 1;
1024     node_keep_common_hosts(_root, other_stack, other_pos, add);
1025 }
1026 
1027 
1028 void
node_drop_common_hosts(Node * n,const Node * other_stack[],int & other_pos)1029 AggregateTree::node_drop_common_hosts(Node *n, const Node *other_stack[], int &other_pos)
1030 {
1031     if (n->count) {
1032 	const Node *other = (other_pos ? other_stack[other_pos - 1] : 0);
1033 	while (other && other->aggregate < n->aggregate)
1034 	    other = preorder_step(other_stack, other_pos);
1035 	if (other && other->aggregate == n->aggregate && other->count != 0) {
1036 	    n->count = 0;
1037 	    _num_nonzero--;
1038 	}
1039     }
1040     if (n->child[0]) {
1041 	node_drop_common_hosts(n->child[0], other_stack, other_pos);
1042 	node_drop_common_hosts(n->child[1], other_stack, other_pos);
1043     }
1044 }
1045 
1046 void
drop_common_hosts(const AggregateTree & other)1047 AggregateTree::drop_common_hosts(const AggregateTree &other)
1048 {
1049     const Node *other_stack[32];
1050     other_stack[0] = other._root;
1051     int other_pos = 1;
1052     node_drop_common_hosts(_root, other_stack, other_pos);
1053 }
1054 
1055 
1056 void
add_new_hosts(const AggregateTree & other)1057 AggregateTree::add_new_hosts(const AggregateTree &other)
1058 {
1059     AggregateTree other_copy(other);
1060     other_copy.drop_common_hosts(*this);
1061     *this += other_copy;
1062 }
1063 
1064 
1065 void
node_drop_common_unequal_hosts(Node * n,const Node * other_stack[],int & other_pos)1066 AggregateTree::node_drop_common_unequal_hosts(Node *n, const Node *other_stack[], int &other_pos)
1067 {
1068     if (n->count) {
1069 	const Node *other = (other_pos ? other_stack[other_pos - 1] : 0);
1070 	while (other && other->aggregate < n->aggregate)
1071 	    other = preorder_step(other_stack, other_pos);
1072 	if (other && other->aggregate == n->aggregate
1073 	    && other->count != 0 && other->count != n->count) {
1074 	    n->count = 0;
1075 	    _num_nonzero--;
1076 	}
1077     }
1078     if (n->child[0]) {
1079 	node_drop_common_unequal_hosts(n->child[0], other_stack, other_pos);
1080 	node_drop_common_unequal_hosts(n->child[1], other_stack, other_pos);
1081     }
1082 }
1083 
1084 void
drop_common_unequal_hosts(const AggregateTree & other)1085 AggregateTree::drop_common_unequal_hosts(const AggregateTree &other)
1086 {
1087     const Node *other_stack[32];
1088     other_stack[0] = other._root;
1089     int other_pos = 1;
1090     node_drop_common_unequal_hosts(_root, other_stack, other_pos);
1091 }
1092 
1093 
1094 void
node_take_nonzero_sizes(Node * n,const Node * other_stack[],int & other_pos,uint32_t mask)1095 AggregateTree::node_take_nonzero_sizes(Node *n, const Node *other_stack[], int &other_pos, uint32_t mask)
1096 {
1097     if (n->count) {
1098 	const Node *other = (other_pos ? other_stack[other_pos - 1] : 0);
1099 	while (other && (other->aggregate & mask) < (n->aggregate & mask))
1100 	    other = preorder_step(other_stack, other_pos);
1101 	if (other && (other->aggregate & mask) == (n->aggregate & mask))
1102 	    n->count = other->count;
1103 	else
1104 	    n->count = 0;
1105 	if (n->count == 0)
1106 	    _num_nonzero--;
1107     }
1108     if (n->child[0]) {
1109 	node_take_nonzero_sizes(n->child[0], other_stack, other_pos, mask);
1110 	node_take_nonzero_sizes(n->child[1], other_stack, other_pos, mask);
1111     }
1112 }
1113 
1114 void
take_nonzero_sizes(const AggregateTree & other,uint32_t mask)1115 AggregateTree::take_nonzero_sizes(const AggregateTree &other, uint32_t mask)
1116 {
1117     const Node *other_stack[32];
1118     other_stack[0] = other._root;
1119     int other_pos = 1;
1120     node_take_nonzero_sizes(_root, other_stack, other_pos, mask);
1121 }
1122 
1123 
1124 //
1125 // READING AND WRITING
1126 //
1127 
1128 void
read_packed_file(FILE * f,int file_byte_order)1129 AggregateTree::read_packed_file(FILE *f, int file_byte_order)
1130 {
1131     uint32_t ubuf[BUFSIZ];
1132     _read_format = WR_BINARY;
1133     if (file_byte_order == CLICK_BYTE_ORDER) {
1134 	while (!feof(f) && !ferror(f)) {
1135 	    size_t howmany = fread(ubuf, 8, BUFSIZ / 2, f);
1136 	    for (size_t i = 0; i < howmany; i++)
1137 		add(ubuf[2*i], ubuf[2*i + 1]);
1138 	}
1139     } else {
1140 	while (!feof(f) && !ferror(f)) {
1141 	    size_t howmany = fread(ubuf, 8, BUFSIZ / 2, f);
1142 	    for (size_t i = 0; i < howmany; i++)
1143 		add(bswap_32(ubuf[2*i]), bswap_32(ubuf[2*i + 1]));
1144 	}
1145     }
1146 }
1147 
1148 int
read_file(FILE * f,ErrorHandler * errh)1149 AggregateTree::read_file(FILE *f, ErrorHandler *errh)
1150 {
1151     char s[BUFSIZ];
1152     uint32_t agg, value, b[4];
1153     _read_format = WR_ASCII;
1154     while (fgets(s, BUFSIZ, f)) {
1155 	if (strlen(s) == BUFSIZ - 1 && s[BUFSIZ - 2] != '\n')
1156 	    return errh->error("line too long");
1157 	if (s[0] == '$' || s[0] == '!') {
1158 	    if (strcmp(s + 1, "packed\n") == 0) {
1159 		errh->warning("file marked '$packed'; change to refer to true byte order");
1160 		read_packed_file(f, CLICK_LITTLE_ENDIAN);
1161 	    } else if (strcmp(s + 1, "packed_le\n") == 0)
1162 		read_packed_file(f, CLICK_LITTLE_ENDIAN);
1163 	    else if (strcmp(s + 1, "packed_be\n") == 0)
1164 		read_packed_file(f, CLICK_BIG_ENDIAN);
1165 	} else if (sscanf(s, "%u %u", &agg, &value) == 2)
1166 	    add(agg, value);
1167 	else if (sscanf(s, "%u.%u.%u.%u %u", &b[0], &b[1], &b[2], &b[3], &value) == 5
1168 		 && b[0] < 256 && b[1] < 256 && b[2] < 256 && b[3] < 256) {
1169 	    add((b[0]<<24) | (b[1]<<16) | (b[2]<<8) | b[3], value);
1170 	    _read_format = WR_ASCII_IP;
1171 	}
1172     }
1173     if (ferror(f))
1174 	return errh->error("file error");
1175     return 0;
1176 }
1177 
1178 void
write_batch(FILE * f,WriteFormat format,uint32_t * buffer,int pos,ErrorHandler *)1179 AggregateTree::write_batch(FILE *f, WriteFormat format,
1180 			   uint32_t *buffer, int pos, ErrorHandler *)
1181 {
1182     if (format == WR_BINARY)
1183 	fwrite(buffer, sizeof(uint32_t), pos, f);
1184     else if (format == WR_ASCII_IP)
1185 	for (int i = 0; i < pos; i += 2)
1186 	    fprintf(f, "%d.%d.%d.%d %u\n", (buffer[i] >> 24) & 255, (buffer[i] >> 16) & 255, (buffer[i] >> 8) & 255, buffer[i] & 255, buffer[i+1]);
1187     else
1188 	for (int i = 0; i < pos; i += 2)
1189 	    fprintf(f, "%u %u\n", buffer[i], buffer[i+1]);
1190 }
1191 
1192 void
write_nodes(Node * n,FILE * f,WriteFormat format,uint32_t * buffer,int & pos,int len,ErrorHandler * errh)1193 AggregateTree::write_nodes(Node *n, FILE *f, WriteFormat format,
1194 			   uint32_t *buffer, int &pos, int len,
1195 			   ErrorHandler *errh)
1196 {
1197     if (n->count > 0) {
1198 	buffer[pos++] = n->aggregate;
1199 	buffer[pos++] = n->count;
1200 	if (pos == len) {
1201 	    write_batch(f, format, buffer, pos, errh);
1202 	    pos = 0;
1203 	}
1204     }
1205 
1206     if (n->child[0])
1207 	write_nodes(n->child[0], f, format, buffer, pos, len, errh);
1208     if (n->child[1])
1209 	write_nodes(n->child[1], f, format, buffer, pos, len, errh);
1210 }
1211 
1212 void
write_hex_nodes(Node * n,FILE * f,ErrorHandler * errh)1213 AggregateTree::write_hex_nodes(Node *n, FILE *f, ErrorHandler *errh)
1214 {
1215     if (n->count > 0)
1216 	fprintf(f, "%08x %u\n", n->aggregate, n->count);
1217     if (n->child[0])
1218 	write_hex_nodes(n->child[0], f, errh);
1219     if (n->child[1])
1220 	write_hex_nodes(n->child[1], f, errh);
1221 }
1222 
1223 int
write_file(FILE * f,WriteFormat format,ErrorHandler * errh) const1224 AggregateTree::write_file(FILE *f, WriteFormat format, ErrorHandler *errh) const
1225 {
1226     fprintf(f, "!num_nonzero %u\n", _num_nonzero);
1227     if (format == WR_BINARY) {
1228 #if CLICK_BYTE_ORDER == CLICK_BIG_ENDIAN
1229 	fprintf(f, "!packed_be\n");
1230 #elif CLICK_BYTE_ORDER == CLICK_LITTLE_ENDIAN
1231 	fprintf(f, "!packed_le\n");
1232 #else
1233 	format = WR_ASCII;
1234 #endif
1235     } else if (format == WR_ASCII_IP)
1236 	fprintf(f, "!ip\n");
1237 
1238     uint32_t buf[1024];
1239     int pos = 0;
1240     write_nodes(_root, f, format, buf, pos, 1024, errh);
1241     if (pos)
1242 	write_batch(f, format, buf, pos, errh);
1243 
1244     if (ferror(f))
1245 	return errh->error("file error");
1246     else
1247 	return 0;
1248 }
1249 
1250 // Vector instance
1251 #include <click/vector.cc>
1252 template class Vector<double>;
1253