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