xref: /frameworks/base/cmds/statsd/src/anomaly/indexed_priority_queue.h

/*
 * Copyright (C) 2017 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#pragma once

#include <utils/RefBase.h>
#include <unordered_map>
#include <vector>

using namespace android;

namespace android {
namespace os {
namespace statsd {

/** Defines a hash function for sp<const AA>, returning the hash of the underlying pointer. */
template <class AA>
struct SpHash {
    size_t operator()(const sp<const AA>& k) const {
        return std::hash<const AA*>()(k.get());
    }
};

/**
 * Min priority queue for generic type AA.
 * Unlike a regular priority queue, this class is also capable of removing interior elements.
 * @tparam Comparator must implement [bool operator()(sp<const AA> a, sp<const AA> b)], returning
 *    whether a should be closer to the top of the queue than b.
 */
template <class AA, class Comparator>
class indexed_priority_queue {
public:
    indexed_priority_queue();
    /** Adds a into the priority queue. If already present or a==nullptr, does nothing. */
    void push(sp<const AA> a);
    /*
     * Removes a from the priority queue. If not present or a==nullptr, does nothing.
     * Returns true if a had been present (and is now removed), else false.
     */
    bool remove(sp<const AA> a);
    /** Removes the top element, if there is one. */
    void pop();
    /** Removes all elements. */
    void clear();
    /** Returns whether priority queue contains a (not just a copy of a, but a itself). */
    bool contains(sp<const AA> a) const;
    /** Returns min element. Returns nullptr iff empty(). */
    sp<const AA> top() const;
    /** Returns number of elements in priority queue. */
    size_t size() const {
        return pq.size() - 1;
    }  // pq is 1-indexed
    /** Returns true iff priority queue is empty. */
    bool empty() const {
        return size() < 1;
    }

private:
    /** Vector representing a min-heap (1-indexed, with nullptr at 0). */
    std::vector<sp<const AA>> pq;
    /** Mapping of each element in pq to its index in pq (i.e. the inverse of a=pq[i]). */
    std::unordered_map<sp<const AA>, size_t, SpHash<AA>> indices;

    void init();
    void sift_up(size_t idx);
    void sift_down(size_t idx);
    /** Returns whether pq[idx1] is considered higher than pq[idx2], according to Comparator. */
    bool higher(size_t idx1, size_t idx2) const;
    void swap_indices(size_t i, size_t j);
};

// Implementation must be done in this file due to use of template.

template <class AA, class Comparator>
indexed_priority_queue<AA, Comparator>::indexed_priority_queue() {
    init();
}

template <class AA, class Comparator>
void indexed_priority_queue<AA, Comparator>::push(sp<const AA> a) {
    if (a == nullptr) return;
    if (contains(a)) return;
    pq.push_back(a);
    size_t idx = size();  // index of last element since 1-indexed
    indices.insert({a, idx});
    sift_up(idx);  // get the pq back in order
}

template <class AA, class Comparator>
bool indexed_priority_queue<AA, Comparator>::remove(sp<const AA> a) {
    if (a == nullptr) return false;
    if (!contains(a)) return false;
    size_t idx = indices[a];
    if (idx >= pq.size()) {
        return false;
    }
    if (idx == size()) {  // if a is the last element, i.e. at index idx == size() == (pq.size()-1)
        pq.pop_back();
        indices.erase(a);
        return true;
    }
    // move last element (guaranteed not to be at idx) to idx, then delete a
    sp<const AA> last_a = pq.back();
    pq[idx] = last_a;
    pq.pop_back();
    indices[last_a] = idx;
    indices.erase(a);

    // get the heap back in order (since the element at idx is not in order)
    sift_up(idx);
    sift_down(idx);

    return true;
}

// The same as, but slightly more efficient than, remove(top()).
template <class AA, class Comparator>
void indexed_priority_queue<AA, Comparator>::pop() {
    sp<const AA> a = top();
    if (a == nullptr) return;
    const size_t idx = 1;
    if (idx == size()) {  // if a is the last element
        pq.pop_back();
        indices.erase(a);
        return;
    }
    // move last element (guaranteed not to be at idx) to idx, then delete a
    sp<const AA> last_a = pq.back();
    pq[idx] = last_a;
    pq.pop_back();
    indices[last_a] = idx;
    indices.erase(a);

    // get the heap back in order (since the element at idx is not in order)
    sift_down(idx);
}

template <class AA, class Comparator>
void indexed_priority_queue<AA, Comparator>::clear() {
    pq.clear();
    indices.clear();
    init();
}

template <class AA, class Comparator>
sp<const AA> indexed_priority_queue<AA, Comparator>::top() const {
    if (empty()) return nullptr;
    return pq[1];
}

template <class AA, class Comparator>
void indexed_priority_queue<AA, Comparator>::init() {
    pq.push_back(nullptr);         // so that pq is 1-indexed.
    indices.insert({nullptr, 0});  // just to be consistent with pq.
}

template <class AA, class Comparator>
void indexed_priority_queue<AA, Comparator>::sift_up(size_t idx) {
    while (idx > 1) {
        size_t parent = idx / 2;
        if (higher(idx, parent))
            swap_indices(idx, parent);
        else
            break;
        idx = parent;
    }
}

template <class AA, class Comparator>
void indexed_priority_queue<AA, Comparator>::sift_down(size_t idx) {
    while (2 * idx <= size()) {
        size_t child = 2 * idx;
        if (child < size() && higher(child + 1, child)) child++;
        if (higher(child, idx))
            swap_indices(child, idx);
        else
            break;
        idx = child;
    }
}

template <class AA, class Comparator>
bool indexed_priority_queue<AA, Comparator>::higher(size_t idx1, size_t idx2) const {
    if (!(0u < idx1 && idx1 < pq.size() && 0u < idx2 && idx2 < pq.size())) {
        return false;  // got to do something.
    }
    return Comparator()(pq[idx1], pq[idx2]);
}

template <class AA, class Comparator>
bool indexed_priority_queue<AA, Comparator>::contains(sp<const AA> a) const {
    if (a == nullptr) return false;  // publicly, we pretend that nullptr is not actually in pq.
    return indices.count(a) > 0;
}

template <class AA, class Comparator>
void indexed_priority_queue<AA, Comparator>::swap_indices(size_t i, size_t j) {
    if (!(0u < i && i < pq.size() && 0u < j && j < pq.size())) {
        return;
    }
    sp<const AA> val_i = pq[i];
    sp<const AA> val_j = pq[j];
    pq[i] = val_j;
    pq[j] = val_i;
    indices[val_i] = j;
    indices[val_j] = i;
}

}  // namespace statsd
}  // namespace os
}  // namespace android