indexed_priority_queue.h revision ece5f705d59c6b73005edc7eeaa6953482f7c6f0
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 170e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz#ifndef STATSD_INDEXED_PRIORITY_QUEUE_H 180e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz#define STATSD_INDEXED_PRIORITY_QUEUE_H 190e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 200e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz// ALOGE can be called from this file. If header loaded by another class, use their LOG_TAG instead. 210e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz#ifndef LOG_TAG 220e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz#define LOG_TAG "statsd(indexed_priority_queue)" 23ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen#endif // LOG_TAG 240e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 250e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz#include <cutils/log.h> 260e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz#include <utils/RefBase.h> 27ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen#include <unordered_map> 280e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz#include <vector> 290e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 300e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatzusing namespace android; 310e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 32b487b5533eba8635232009c7f32a54a0380a532dBookatznamespace android { 33b487b5533eba8635232009c7f32a54a0380a532dBookatznamespace os { 340e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatznamespace statsd { 350e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 360e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz/** Defines a hash function for sp<AA>, returning the hash of the underlying pointer. */ 370e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA> 380e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatzstruct SpHash { 390e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz size_t operator()(const sp<const AA>& k) const { 400e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz return std::hash<const AA*>()(k.get()); 410e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz } 420e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz}; 430e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 440e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz/** 450e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz * Min priority queue for generic type AA. 460e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz * Unlike a regular priority queue, this class is also capable of removing interior elements. 470e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz * @tparam Comparator must implement [bool operator()(sp<const AA> a, sp<const AA> b)], returning 480e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz * whether a should be closer to the top of the queue than b. 490e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz */ 500e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 510e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatzclass indexed_priority_queue { 52ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chenpublic: 530e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz indexed_priority_queue(); 540e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Adds a into the priority queue. If already present or a==nullptr, does nothing. */ 550e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz void push(sp<const AA> a); 560e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Removes a from the priority queue. If not present or a==nullptr, does nothing. */ 570e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz void remove(sp<const AA> a); 58ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz /** Removes the top element, if there is one. */ 59ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz void pop(); 600e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Removes all elements. */ 610e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz void clear(); 620e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Returns whether priority queue contains a (not just a copy of a, but a itself). */ 630e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz bool contains(sp<const AA> a) const; 640e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Returns min element. Returns nullptr iff empty(). */ 650e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz sp<const AA> top() const; 660e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Returns number of elements in priority queue. */ 67ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen size_t size() const { 68ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen return pq.size() - 1; 69ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen } // pq is 1-indexed 700e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Returns true iff priority queue is empty. */ 71ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen bool empty() const { 72ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen return size() < 1; 73ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen } 740e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 75ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chenprivate: 760e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Vector representing a min-heap (1-indexed, with nullptr at 0). */ 770e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz std::vector<sp<const AA>> pq; 780e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Mapping of each element in pq to its index in pq (i.e. the inverse of a=pq[i]). */ 790e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz std::unordered_map<sp<const AA>, size_t, SpHash<AA>> indices; 800e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 810e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz void init(); 820e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz void sift_up(size_t idx); 830e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz void sift_down(size_t idx); 840e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Returns whether pq[idx1] is considered higher than pq[idx2], according to Comparator. */ 850e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz bool higher(size_t idx1, size_t idx2) const; 860e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz void swap_indices(size_t i, size_t j); 870e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz}; 880e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 890e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz// Implementation must be done in this file due to use of template. 900e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 910e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 92ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chenindexed_priority_queue<AA, Comparator>::indexed_priority_queue() { 930e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz init(); 940e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 950e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 960e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 97ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chenvoid indexed_priority_queue<AA, Comparator>::push(sp<const AA> a) { 980e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (a == nullptr) return; 990e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (contains(a)) return; 1000e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz pq.push_back(a); 101ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen size_t idx = size(); // index of last element since 1-indexed 1020e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz indices.insert({a, idx}); 103ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen sift_up(idx); // get the pq back in order 1040e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 1050e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 1060e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 107ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chenvoid indexed_priority_queue<AA, Comparator>::remove(sp<const AA> a) { 1080e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (a == nullptr) return; 1090e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (!contains(a)) return; 1100e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz size_t idx = indices[a]; 1110e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (idx >= pq.size()) { 1120e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz ALOGE("indexed_priority_queue: Invalid index in map of indices."); 1130e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz return; 1140e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz } 115ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen if (idx == size()) { // if a is the last element, i.e. at index idx == size() == (pq.size()-1) 1160e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz pq.pop_back(); 1170e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz indices.erase(a); 1180e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz return; 1190e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz } 1200e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz // move last element (guaranteed not to be at idx) to idx, then delete a 1210e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz sp<const AA> last_a = pq.back(); 1220e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz pq[idx] = last_a; 1230e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz pq.pop_back(); 1240e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz indices[last_a] = idx; 1250e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz indices.erase(a); 1260e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 1270e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz // get the heap back in order (since the element at idx is not in order) 1280e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz sift_up(idx); 1290e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz sift_down(idx); 1300e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 1310e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 132ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz// The same as, but slightly more efficient than, remove(top()). 133ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatztemplate <class AA, class Comparator> 134ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatzvoid indexed_priority_queue<AA, Comparator>::pop() { 135ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz sp<const AA> a = top(); 136ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz if (a == nullptr) return; 137ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz const size_t idx = 1; 138ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz if (idx == size()) { // if a is the last element 139ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz pq.pop_back(); 140ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz indices.erase(a); 141ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz return; 142ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz } 143ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz // move last element (guaranteed not to be at idx) to idx, then delete a 144ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz sp<const AA> last_a = pq.back(); 145ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz pq[idx] = last_a; 146ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz pq.pop_back(); 147ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz indices[last_a] = idx; 148ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz indices.erase(a); 149ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz 150ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz // get the heap back in order (since the element at idx is not in order) 151ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz sift_down(idx); 152ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz} 153ece5f705d59c6b73005edc7eeaa6953482f7c6f0Bookatz 1540e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 155ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chenvoid indexed_priority_queue<AA, Comparator>::clear() { 1560e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz pq.clear(); 1570e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz indices.clear(); 1580e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz init(); 1590e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 1600e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 1610e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 162ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chensp<const AA> indexed_priority_queue<AA, Comparator>::top() const { 1630e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (empty()) return nullptr; 1640e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz return pq[1]; 1650e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 1660e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 1670e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 168ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chenvoid indexed_priority_queue<AA, Comparator>::init() { 169ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen pq.push_back(nullptr); // so that pq is 1-indexed. 170ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen indices.insert({nullptr, 0}); // just to be consistent with pq. 1710e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 1720e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 1730e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 174ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chenvoid indexed_priority_queue<AA, Comparator>::sift_up(size_t idx) { 1750e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz while (idx > 1) { 176ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen size_t parent = idx / 2; 177ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen if (higher(idx, parent)) 178ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen swap_indices(idx, parent); 179ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen else 180ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen break; 1810e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz idx = parent; 1820e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz } 1830e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 1840e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 1850e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 186ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chenvoid indexed_priority_queue<AA, Comparator>::sift_down(size_t idx) { 187ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen while (2 * idx <= size()) { 1880e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz size_t child = 2 * idx; 189ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen if (child < size() && higher(child + 1, child)) child++; 190ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen if (higher(child, idx)) 191ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen swap_indices(child, idx); 192ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen else 193ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen break; 1940e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz idx = child; 1950e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz } 1960e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 1970e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 1980e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 199ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chenbool indexed_priority_queue<AA, Comparator>::higher(size_t idx1, size_t idx2) const { 2000e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (!(0u < idx1 && idx1 < pq.size() && 0u < idx2 && idx2 < pq.size())) { 2010e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz ALOGE("indexed_priority_queue: Attempting to access invalid index"); 202ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen return false; // got to do something. 2030e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz } 2040e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz return Comparator()(pq[idx1], pq[idx2]); 2050e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 2060e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 2070e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 208ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chenbool indexed_priority_queue<AA, Comparator>::contains(sp<const AA> a) const { 209ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen if (a == nullptr) return false; // publicly, we pretend that nullptr is not actually in pq. 2100e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz return indices.count(a) > 0; 2110e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 2120e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 2130e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 214ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chenvoid indexed_priority_queue<AA, Comparator>::swap_indices(size_t i, size_t j) { 2150e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (!(0u < i && i < pq.size() && 0u < j && j < pq.size())) { 2160e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz ALOGE("indexed_priority_queue: Attempting to swap invalid index"); 2170e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz return; 2180e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz } 2190e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz sp<const AA> val_i = pq[i]; 2200e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz sp<const AA> val_j = pq[j]; 2210e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz pq[i] = val_j; 2220e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz pq[j] = val_i; 2230e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz indices[val_i] = j; 2240e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz indices[val_j] = i; 2250e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 2260e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 227ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen} // namespace statsd 228ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen} // namespace os 229ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen} // namespace android 2300e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 231ef99c4fa23b42fe6e58db706b9f4780018b6bf3eYao Chen#endif // STATSD_INDEXED_PRIORITY_QUEUE_H 232