indexed_priority_queue.h revision 9fc9edf95a308f5884bf541cac81ce1f41aba0ba
10e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz/* 20e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz * Copyright (C) 2017 The Android Open Source Project 30e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz * 40e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz * Licensed under the Apache License, Version 2.0 (the "License"); 50e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz * you may not use this file except in compliance with the License. 60e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz * You may obtain a copy of the License at 70e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz * 80e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz * http://www.apache.org/licenses/LICENSE-2.0 90e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz * 100e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz * Unless required by applicable law or agreed to in writing, software 110e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz * distributed under the License is distributed on an "AS IS" BASIS, 120e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 130e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz * See the License for the specific language governing permissions and 140e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz * limitations under the License. 150e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz */ 160e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 179fc9edf95a308f5884bf541cac81ce1f41aba0baJoe Onorato#pragma once 180e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 199fc9edf95a308f5884bf541cac81ce1f41aba0baJoe Onorato#include "Log.h" 200e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 210e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz#include <utils/RefBase.h> 22ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen#include <unordered_map> 230e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz#include <vector> 240e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 250e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatzusing namespace android; 260e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 27b487b5533eba8635232009c7f32a54a0380a532dBookatznamespace android { 28b487b5533eba8635232009c7f32a54a0380a532dBookatznamespace os { 290e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatznamespace statsd { 300e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 310e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz/** Defines a hash function for sp<AA>, returning the hash of the underlying pointer. */ 320e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA> 330e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatzstruct SpHash { 340e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz size_t operator()(const sp<const AA>& k) const { 350e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz return std::hash<const AA*>()(k.get()); 360e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz } 370e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz}; 380e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 390e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz/** 400e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz * Min priority queue for generic type AA. 410e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz * Unlike a regular priority queue, this class is also capable of removing interior elements. 420e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz * @tparam Comparator must implement [bool operator()(sp<const AA> a, sp<const AA> b)], returning 430e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz * whether a should be closer to the top of the queue than b. 440e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz */ 450e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 460e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatzclass indexed_priority_queue { 47ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chenpublic: 480e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz indexed_priority_queue(); 490e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Adds a into the priority queue. If already present or a==nullptr, does nothing. */ 500e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz void push(sp<const AA> a); 510e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Removes a from the priority queue. If not present or a==nullptr, does nothing. */ 520e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz void remove(sp<const AA> a); 53ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz /** Removes the top element, if there is one. */ 54ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz void pop(); 550e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Removes all elements. */ 560e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz void clear(); 570e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Returns whether priority queue contains a (not just a copy of a, but a itself). */ 580e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz bool contains(sp<const AA> a) const; 590e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Returns min element. Returns nullptr iff empty(). */ 600e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz sp<const AA> top() const; 610e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Returns number of elements in priority queue. */ 62ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen size_t size() const { 63ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen return pq.size() - 1; 64ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen } // pq is 1-indexed 650e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Returns true iff priority queue is empty. */ 66ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen bool empty() const { 67ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen return size() < 1; 68ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen } 690e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 70ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chenprivate: 710e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Vector representing a min-heap (1-indexed, with nullptr at 0). */ 720e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz std::vector<sp<const AA>> pq; 730e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Mapping of each element in pq to its index in pq (i.e. the inverse of a=pq[i]). */ 740e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz std::unordered_map<sp<const AA>, size_t, SpHash<AA>> indices; 750e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 760e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz void init(); 770e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz void sift_up(size_t idx); 780e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz void sift_down(size_t idx); 790e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Returns whether pq[idx1] is considered higher than pq[idx2], according to Comparator. */ 800e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz bool higher(size_t idx1, size_t idx2) const; 810e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz void swap_indices(size_t i, size_t j); 820e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz}; 830e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 840e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz// Implementation must be done in this file due to use of template. 850e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 860e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 87ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chenindexed_priority_queue<AA, Comparator>::indexed_priority_queue() { 880e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz init(); 890e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 900e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 910e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 92ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chenvoid indexed_priority_queue<AA, Comparator>::push(sp<const AA> a) { 930e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (a == nullptr) return; 940e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (contains(a)) return; 950e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz pq.push_back(a); 96ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen size_t idx = size(); // index of last element since 1-indexed 970e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz indices.insert({a, idx}); 98ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen sift_up(idx); // get the pq back in order 990e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 1000e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 1010e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 102ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chenvoid indexed_priority_queue<AA, Comparator>::remove(sp<const AA> a) { 1030e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (a == nullptr) return; 1040e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (!contains(a)) return; 1050e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz size_t idx = indices[a]; 1060e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (idx >= pq.size()) { 1070e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz ALOGE("indexed_priority_queue: Invalid index in map of indices."); 1080e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz return; 1090e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz } 110ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen if (idx == size()) { // if a is the last element, i.e. at index idx == size() == (pq.size()-1) 1110e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz pq.pop_back(); 1120e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz indices.erase(a); 1130e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz return; 1140e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz } 1150e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz // move last element (guaranteed not to be at idx) to idx, then delete a 1160e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz sp<const AA> last_a = pq.back(); 1170e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz pq[idx] = last_a; 1180e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz pq.pop_back(); 1190e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz indices[last_a] = idx; 1200e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz indices.erase(a); 1210e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 1220e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz // get the heap back in order (since the element at idx is not in order) 1230e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz sift_up(idx); 1240e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz sift_down(idx); 1250e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 1260e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 127ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz// The same as, but slightly more efficient than, remove(top()). 128ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatztemplate <class AA, class Comparator> 129ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatzvoid indexed_priority_queue<AA, Comparator>::pop() { 1309fc9edf95a308f5884bf541cac81ce1f41aba0baJoe Onorato sp<const AA> a = top(); 1319fc9edf95a308f5884bf541cac81ce1f41aba0baJoe Onorato if (a == nullptr) return; 1329fc9edf95a308f5884bf541cac81ce1f41aba0baJoe Onorato const size_t idx = 1; 1339fc9edf95a308f5884bf541cac81ce1f41aba0baJoe Onorato if (idx == size()) { // if a is the last element 1349fc9edf95a308f5884bf541cac81ce1f41aba0baJoe Onorato pq.pop_back(); 1359fc9edf95a308f5884bf541cac81ce1f41aba0baJoe Onorato indices.erase(a); 1369fc9edf95a308f5884bf541cac81ce1f41aba0baJoe Onorato return; 1379fc9edf95a308f5884bf541cac81ce1f41aba0baJoe Onorato } 1389fc9edf95a308f5884bf541cac81ce1f41aba0baJoe Onorato // move last element (guaranteed not to be at idx) to idx, then delete a 1399fc9edf95a308f5884bf541cac81ce1f41aba0baJoe Onorato sp<const AA> last_a = pq.back(); 1409fc9edf95a308f5884bf541cac81ce1f41aba0baJoe Onorato pq[idx] = last_a; 141ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz pq.pop_back(); 1429fc9edf95a308f5884bf541cac81ce1f41aba0baJoe Onorato indices[last_a] = idx; 143ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz indices.erase(a); 1449fc9edf95a308f5884bf541cac81ce1f41aba0baJoe Onorato 1459fc9edf95a308f5884bf541cac81ce1f41aba0baJoe Onorato // get the heap back in order (since the element at idx is not in order) 1469fc9edf95a308f5884bf541cac81ce1f41aba0baJoe Onorato sift_down(idx); 147ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz} 148ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz 1490e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 150ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chenvoid indexed_priority_queue<AA, Comparator>::clear() { 1510e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz pq.clear(); 1520e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz indices.clear(); 1530e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz init(); 1540e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 1550e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 1560e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 157ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chensp<const AA> indexed_priority_queue<AA, Comparator>::top() const { 1580e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (empty()) return nullptr; 1590e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz return pq[1]; 1600e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 1610e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 1620e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 163ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chenvoid indexed_priority_queue<AA, Comparator>::init() { 164ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen pq.push_back(nullptr); // so that pq is 1-indexed. 165ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen indices.insert({nullptr, 0}); // just to be consistent with pq. 1660e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 1670e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 1680e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 169ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chenvoid indexed_priority_queue<AA, Comparator>::sift_up(size_t idx) { 1700e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz while (idx > 1) { 171ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen size_t parent = idx / 2; 172ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen if (higher(idx, parent)) 173ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen swap_indices(idx, parent); 174ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen else 175ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen break; 1760e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz idx = parent; 1770e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz } 1780e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 1790e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 1800e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 181ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chenvoid indexed_priority_queue<AA, Comparator>::sift_down(size_t idx) { 182ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen while (2 * idx <= size()) { 1830e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz size_t child = 2 * idx; 184ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen if (child < size() && higher(child + 1, child)) child++; 185ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen if (higher(child, idx)) 186ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen swap_indices(child, idx); 187ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen else 188ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen break; 1890e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz idx = child; 1900e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz } 1910e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 1920e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 1930e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 194ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chenbool indexed_priority_queue<AA, Comparator>::higher(size_t idx1, size_t idx2) const { 1950e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (!(0u < idx1 && idx1 < pq.size() && 0u < idx2 && idx2 < pq.size())) { 1960e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz ALOGE("indexed_priority_queue: Attempting to access invalid index"); 197ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen return false; // got to do something. 1980e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz } 1990e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz return Comparator()(pq[idx1], pq[idx2]); 2000e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 2010e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 2020e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 203ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chenbool indexed_priority_queue<AA, Comparator>::contains(sp<const AA> a) const { 204ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen if (a == nullptr) return false; // publicly, we pretend that nullptr is not actually in pq. 2050e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz return indices.count(a) > 0; 2060e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 2070e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 2080e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 209ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chenvoid indexed_priority_queue<AA, Comparator>::swap_indices(size_t i, size_t j) { 2100e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (!(0u < i && i < pq.size() && 0u < j && j < pq.size())) { 2110e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz ALOGE("indexed_priority_queue: Attempting to swap invalid index"); 2120e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz return; 2130e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz } 2140e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz sp<const AA> val_i = pq[i]; 2150e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz sp<const AA> val_j = pq[j]; 2160e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz pq[i] = val_j; 2170e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz pq[j] = val_i; 2180e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz indices[val_i] = j; 2190e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz indices[val_j] = i; 2200e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 2210e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 222ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen} // namespace statsd 223ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen} // namespace os 224ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen} // namespace android 225