indexed_priority_queue.h revision 0e95909ef0b2aac44f305551ea2aa03209b1eec0
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)" 230e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz#endif //LOG_TAG 240e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 250e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz#include <cutils/log.h> 260e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz#include <unordered_map> 270e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz#include <utils/RefBase.h> 280e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz#include <vector> 290e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 300e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatzusing namespace android; 310e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 320e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatznamespace statsd { 330e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 340e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz/** Defines a hash function for sp<AA>, returning the hash of the underlying pointer. */ 350e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA> 360e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatzstruct SpHash { 370e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz size_t operator()(const sp<const AA>& k) const { 380e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz return std::hash<const AA*>()(k.get()); 390e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz } 400e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz}; 410e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 420e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz/** 430e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz * Min priority queue for generic type AA. 440e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz * Unlike a regular priority queue, this class is also capable of removing interior elements. 450e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz * @tparam Comparator must implement [bool operator()(sp<const AA> a, sp<const AA> b)], returning 460e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz * whether a should be closer to the top of the queue than b. 470e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz */ 480e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 490e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatzclass indexed_priority_queue { 500e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz public: 510e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz indexed_priority_queue(); 520e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Adds a into the priority queue. If already present or a==nullptr, does nothing. */ 530e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz void push(sp<const AA> a); 540e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Removes a from the priority queue. If not present or a==nullptr, does nothing. */ 550e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz void remove(sp<const AA> a); 560e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Removes all elements. */ 570e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz void clear(); 580e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Returns whether priority queue contains a (not just a copy of a, but a itself). */ 590e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz bool contains(sp<const AA> a) const; 600e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Returns min element. Returns nullptr iff empty(). */ 610e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz sp<const AA> top() const; 620e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Returns number of elements in priority queue. */ 630e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz size_t size() const { return pq.size() - 1; } // pq is 1-indexed 640e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Returns true iff priority queue is empty. */ 650e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz bool empty() const { return size() < 1; } 660e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 670e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz private: 680e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Vector representing a min-heap (1-indexed, with nullptr at 0). */ 690e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz std::vector<sp<const AA>> pq; 700e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Mapping of each element in pq to its index in pq (i.e. the inverse of a=pq[i]). */ 710e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz std::unordered_map<sp<const AA>, size_t, SpHash<AA>> indices; 720e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 730e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz void init(); 740e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz void sift_up(size_t idx); 750e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz void sift_down(size_t idx); 760e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz /** Returns whether pq[idx1] is considered higher than pq[idx2], according to Comparator. */ 770e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz bool higher(size_t idx1, size_t idx2) const; 780e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz void swap_indices(size_t i, size_t j); 790e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz}; 800e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 810e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz// Implementation must be done in this file due to use of template. 820e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 830e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 840e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatzindexed_priority_queue<AA,Comparator>::indexed_priority_queue() { 850e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz init(); 860e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 870e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 880e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 890e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatzvoid indexed_priority_queue<AA,Comparator>::push(sp<const AA> a) { 900e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (a == nullptr) return; 910e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (contains(a)) return; 920e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz pq.push_back(a); 930e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz size_t idx = size(); // index of last element since 1-indexed 940e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz indices.insert({a, idx}); 950e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz sift_up(idx); // get the pq back in order 960e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 970e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 980e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 990e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatzvoid indexed_priority_queue<AA,Comparator>::remove(sp<const AA> a) { 1000e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (a == nullptr) return; 1010e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (!contains(a)) return; 1020e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz size_t idx = indices[a]; 1030e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (idx >= pq.size()) { 1040e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz ALOGE("indexed_priority_queue: Invalid index in map of indices."); 1050e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz return; 1060e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz } 1070e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (idx == size()) { // if a is the last element, i.e. at index idx == size() == (pq.size()-1) 1080e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz pq.pop_back(); 1090e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz indices.erase(a); 1100e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz return; 1110e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz } 1120e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz // move last element (guaranteed not to be at idx) to idx, then delete a 1130e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz sp<const AA> last_a = pq.back(); 1140e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz pq[idx] = last_a; 1150e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz pq.pop_back(); 1160e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz indices[last_a] = idx; 1170e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz indices.erase(a); 1180e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 1190e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz // get the heap back in order (since the element at idx is not in order) 1200e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz sift_up(idx); 1210e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz sift_down(idx); 1220e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 1230e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 1240e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 1250e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatzvoid indexed_priority_queue<AA,Comparator>::clear() { 1260e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz pq.clear(); 1270e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz indices.clear(); 1280e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz init(); 1290e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 1300e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 1310e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 1320e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatzsp<const AA> indexed_priority_queue<AA,Comparator>::top() const { 1330e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (empty()) return nullptr; 1340e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz return pq[1]; 1350e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 1360e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 1370e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 1380e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatzvoid indexed_priority_queue<AA,Comparator>::init() { 1390e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz pq.push_back(nullptr); // so that pq is 1-indexed. 1400e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz indices.insert({nullptr, 0}); // just to be consistent with pq. 1410e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 1420e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 1430e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 1440e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatzvoid indexed_priority_queue<AA,Comparator>::sift_up(size_t idx) { 1450e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz while (idx > 1) { 1460e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz size_t parent = idx/2; 1470e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (higher(idx, parent)) swap_indices(idx, parent); 1480e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz else break; 1490e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz idx = parent; 1500e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz } 1510e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 1520e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 1530e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 1540e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatzvoid indexed_priority_queue<AA,Comparator>::sift_down(size_t idx) { 1550e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz while (2*idx <= size()) { 1560e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz size_t child = 2 * idx; 1570e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (child < size() && higher(child+1, child)) child++; 1580e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (higher(child, idx)) swap_indices(child, idx); 1590e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz else break; 1600e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz idx = child; 1610e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz } 1620e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 1630e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 1640e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 1650e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatzbool indexed_priority_queue<AA,Comparator>::higher(size_t idx1, size_t idx2) const { 1660e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (!(0u < idx1 && idx1 < pq.size() && 0u < idx2 && idx2 < pq.size())) { 1670e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz ALOGE("indexed_priority_queue: Attempting to access invalid index"); 1680e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz return false; // got to do something. 1690e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz } 1700e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz return Comparator()(pq[idx1], pq[idx2]); 1710e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 1720e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 1730e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 1740e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatzbool indexed_priority_queue<AA,Comparator>::contains(sp<const AA> a) const { 1750e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (a == nullptr) return false; // publicly, we pretend that nullptr is not actually in pq. 1760e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz return indices.count(a) > 0; 1770e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 1780e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 1790e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatztemplate <class AA, class Comparator> 1800e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatzvoid indexed_priority_queue<AA,Comparator>::swap_indices(size_t i, size_t j) { 1810e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz if (!(0u < i && i < pq.size() && 0u < j && j < pq.size())) { 1820e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz ALOGE("indexed_priority_queue: Attempting to swap invalid index"); 1830e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz return; 1840e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz } 1850e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz sp<const AA> val_i = pq[i]; 1860e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz sp<const AA> val_j = pq[j]; 1870e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz pq[i] = val_j; 1880e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz pq[j] = val_i; 1890e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz indices[val_i] = j; 1900e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz indices[val_j] = i; 1910e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} 1920e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 1930e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz} // namespace statsd 1940e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz 1950e95909ef0b2aac44f305551ea2aa03209b1eec0Bookatz#endif //STATSD_INDEXED_PRIORITY_QUEUE_H 196