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