| 802 | |
| 803 | |
| 804 | void intersection_of(const interval_set &a, const interval_set &b) { |
| 805 | ceph_assert(&a != this); |
| 806 | ceph_assert(&b != this); |
| 807 | clear(); |
| 808 | |
| 809 | const interval_set *s, *l; |
| 810 | |
| 811 | if (a.size() < b.size()) { |
| 812 | s = &a; |
| 813 | l = &b; |
| 814 | } else { |
| 815 | s = &b; |
| 816 | l = &a; |
| 817 | } |
| 818 | |
| 819 | if (!s->size()) |
| 820 | return; |
| 821 | |
| 822 | /* |
| 823 | * Use the lower_bound algorithm for larger size ratios |
| 824 | * where it performs better, but not for smaller size |
| 825 | * ratios where sequential search performs better. |
| 826 | */ |
| 827 | if (l->size() / s->size() >= 10) { |
| 828 | intersection_size_asym(*s, *l); |
| 829 | return; |
| 830 | } |
| 831 | |
| 832 | auto pa = a.m.begin(); |
| 833 | auto pb = b.m.begin(); |
| 834 | auto mi = m.begin(); |
| 835 | |
| 836 | while (pa != a.m.end() && pb != b.m.end()) { |
| 837 | // passing? |
| 838 | if (pa->first + pa->second <= pb->first) |
| 839 | { pa++; continue; } |
| 840 | if (pb->first + pb->second <= pa->first) |
| 841 | { pb++; continue; } |
| 842 | |
| 843 | if (*pa == *pb) { |
| 844 | do { |
| 845 | mi = m.insert(mi, *pa); |
| 846 | _size += pa->second; |
| 847 | ++pa; |
| 848 | ++pb; |
| 849 | } while (pa != a.m.end() && pb != b.m.end() && *pa == *pb); |
| 850 | continue; |
| 851 | } |
| 852 | |
| 853 | T start = std::max(pa->first, pb->first); |
| 854 | T en = std::min(pa->first+pa->second, pb->first+pb->second); |
| 855 | ceph_assert(en > start); |
| 856 | mi = m.emplace_hint(mi, start, en - start); |
| 857 | _size += mi->second; |
| 858 | if (pa->first+pa->second > pb->first+pb->second) |
| 859 | pb++; |
| 860 | else |
| 861 | pa++; |