1 /*
2  * Copyright (C) 2017 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package com.android.internal.util;
17 
18 import android.annotation.IntRange;
19 import android.annotation.NonNull;
20 import android.annotation.Nullable;
21 import android.util.Log;
22 
23 import java.util.Arrays;
24 
25 /**
26  * A histogram for positive integers where each bucket is twice the size of the previous one.
27  */
28 public class ExponentiallyBucketedHistogram {
29     @NonNull
30     private final int[] mData;
31 
32     /**
33      * Create a new histogram.
34      *
35      * @param numBuckets The number of buckets. The highest bucket is for all value >=
36      *                   2<sup>numBuckets - 1</sup>
37      */
ExponentiallyBucketedHistogram(@ntRangefrom = 1, to = 31) int numBuckets)38     public ExponentiallyBucketedHistogram(@IntRange(from = 1, to = 31) int numBuckets) {
39         numBuckets = Preconditions.checkArgumentInRange(numBuckets, 1, 31, "numBuckets");
40 
41         mData = new int[numBuckets];
42     }
43 
44     /**
45      * Add a new value to the histogram.
46      *
47      * All values <= 0 are in the first bucket. The last bucket contains all values >=
48      * 2<sup>numBuckets - 1</sup>
49      *
50      * @param value The value to add
51      */
add(int value)52     public void add(int value) {
53         if (value <= 0) {
54             mData[0]++;
55         } else {
56             mData[Math.min(mData.length - 1, 32 - Integer.numberOfLeadingZeros(value))]++;
57         }
58     }
59 
60     /**
61      * Clear all data from the histogram
62      */
reset()63     public void reset() {
64         Arrays.fill(mData, 0);
65     }
66 
67     /**
68      * Write the histogram to the log.
69      *
70      * @param tag    The tag to use when logging
71      * @param prefix A custom prefix that is printed in front of the histogram
72      */
log(@onNull String tag, @Nullable CharSequence prefix)73     public void log(@NonNull String tag, @Nullable CharSequence prefix) {
74         StringBuilder builder = new StringBuilder(prefix);
75         builder.append('[');
76 
77         for (int i = 0; i < mData.length; i++) {
78             if (i != 0) {
79                 builder.append(", ");
80             }
81 
82             if (i < mData.length - 1) {
83                 builder.append("<");
84                 builder.append(1 << i);
85             } else {
86                 builder.append(">=");
87                 builder.append(1 << (i - 1));
88             }
89 
90             builder.append(": ");
91             builder.append(mData[i]);
92         }
93         builder.append("]");
94 
95         Log.d(tag, builder.toString());
96     }
97 }
98