123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385 |
- // Copyright (c) 2017 Google Inc.
- //
- // 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.
- #ifndef SOURCE_COMP_MOVE_TO_FRONT_H_
- #define SOURCE_COMP_MOVE_TO_FRONT_H_
- #include <cassert>
- #include <cstdint>
- #include <map>
- #include <set>
- #include <unordered_map>
- #include <vector>
- namespace spvtools {
- namespace comp {
- // Log(n) move-to-front implementation. Implements the following functions:
- // Insert - pushes value to the front of the mtf sequence
- // (only unique values allowed).
- // Remove - remove value from the sequence.
- // ValueFromRank - access value by its 1-indexed rank in the sequence.
- // RankFromValue - get the rank of the given value in the sequence.
- // Accessing a value with ValueFromRank or RankFromValue moves the value to the
- // front of the sequence (rank of 1).
- //
- // The implementation is based on an AVL-based order statistic tree. The tree
- // is ordered by timestamps issued when values are inserted or accessed (recent
- // values go to the left side of the tree, old values are gradually rotated to
- // the right side).
- //
- // Terminology
- // rank: 1-indexed rank showing how recently the value was inserted or accessed.
- // node: handle used internally to access node data.
- // size: size of the subtree of a node (including the node).
- // height: distance from a node to the farthest leaf.
- class MoveToFront {
- public:
- explicit MoveToFront(size_t reserve_capacity = 4) {
- nodes_.reserve(reserve_capacity);
- // Create NIL node.
- nodes_.emplace_back(Node());
- }
- virtual ~MoveToFront() = default;
- // Inserts value in the move-to-front sequence. Does nothing if the value is
- // already in the sequence. Returns true if insertion was successful.
- // The inserted value is placed at the front of the sequence (rank 1).
- bool Insert(uint32_t value);
- // Removes value from move-to-front sequence. Returns false iff the value
- // was not found.
- bool Remove(uint32_t value);
- // Computes 1-indexed rank of value in the move-to-front sequence and moves
- // the value to the front. Example:
- // Before the call: 4 8 2 1 7
- // RankFromValue(8) returns 2
- // After the call: 8 4 2 1 7
- // Returns true iff the value was found in the sequence.
- bool RankFromValue(uint32_t value, uint32_t* rank);
- // Returns value corresponding to a 1-indexed rank in the move-to-front
- // sequence and moves the value to the front. Example:
- // Before the call: 4 8 2 1 7
- // ValueFromRank(2) returns 8
- // After the call: 8 4 2 1 7
- // Returns true iff the rank is within bounds [1, GetSize()].
- bool ValueFromRank(uint32_t rank, uint32_t* value);
- // Moves the value to the front of the sequence.
- // Returns false iff value is not in the sequence.
- bool Promote(uint32_t value);
- // Returns true iff the move-to-front sequence contains the value.
- bool HasValue(uint32_t value) const;
- // Returns the number of elements in the move-to-front sequence.
- uint32_t GetSize() const { return SizeOf(root_); }
- protected:
- // Internal tree data structure uses handles instead of pointers. Leaves and
- // root parent reference a singleton under handle 0. Although dereferencing
- // a null pointer is not possible, inappropriate access to handle 0 would
- // cause an assertion. Handles are not garbage collected if value was
- // deprecated
- // with DeprecateValue(). But handles are recycled when a node is
- // repositioned.
- // Internal tree data structure node.
- struct Node {
- // Timestamp from a logical clock which updates every time the element is
- // accessed through ValueFromRank or RankFromValue.
- uint32_t timestamp = 0;
- // The size of the node's subtree, including the node.
- // SizeOf(LeftOf(node)) + SizeOf(RightOf(node)) + 1.
- uint32_t size = 0;
- // Handles to connected nodes.
- uint32_t left = 0;
- uint32_t right = 0;
- uint32_t parent = 0;
- // Distance to the farthest leaf.
- // Leaves have height 0, real nodes at least 1.
- uint32_t height = 0;
- // Stored value.
- uint32_t value = 0;
- };
- // Creates node and sets correct values. Non-NIL nodes should be created only
- // through this function. If the node with this value has been created
- // previously
- // and since orphaned, reuses the old node instead of creating a new one.
- uint32_t CreateNode(uint32_t timestamp, uint32_t value);
- // Node accessor methods. Naming is designed to be similar to natural
- // language as these functions tend to be used in sequences, for example:
- // ParentOf(LeftestDescendentOf(RightOf(node)))
- // Returns value of the node referenced by |handle|.
- uint32_t ValueOf(uint32_t node) const { return nodes_.at(node).value; }
- // Returns left child of |node|.
- uint32_t LeftOf(uint32_t node) const { return nodes_.at(node).left; }
- // Returns right child of |node|.
- uint32_t RightOf(uint32_t node) const { return nodes_.at(node).right; }
- // Returns parent of |node|.
- uint32_t ParentOf(uint32_t node) const { return nodes_.at(node).parent; }
- // Returns timestamp of |node|.
- uint32_t TimestampOf(uint32_t node) const {
- assert(node);
- return nodes_.at(node).timestamp;
- }
- // Returns size of |node|.
- uint32_t SizeOf(uint32_t node) const { return nodes_.at(node).size; }
- // Returns height of |node|.
- uint32_t HeightOf(uint32_t node) const { return nodes_.at(node).height; }
- // Returns mutable reference to value of |node|.
- uint32_t& MutableValueOf(uint32_t node) {
- assert(node);
- return nodes_.at(node).value;
- }
- // Returns mutable reference to handle of left child of |node|.
- uint32_t& MutableLeftOf(uint32_t node) {
- assert(node);
- return nodes_.at(node).left;
- }
- // Returns mutable reference to handle of right child of |node|.
- uint32_t& MutableRightOf(uint32_t node) {
- assert(node);
- return nodes_.at(node).right;
- }
- // Returns mutable reference to handle of parent of |node|.
- uint32_t& MutableParentOf(uint32_t node) {
- assert(node);
- return nodes_.at(node).parent;
- }
- // Returns mutable reference to timestamp of |node|.
- uint32_t& MutableTimestampOf(uint32_t node) {
- assert(node);
- return nodes_.at(node).timestamp;
- }
- // Returns mutable reference to size of |node|.
- uint32_t& MutableSizeOf(uint32_t node) {
- assert(node);
- return nodes_.at(node).size;
- }
- // Returns mutable reference to height of |node|.
- uint32_t& MutableHeightOf(uint32_t node) {
- assert(node);
- return nodes_.at(node).height;
- }
- // Returns true iff |node| is left child of its parent.
- bool IsLeftChild(uint32_t node) const {
- assert(node);
- return LeftOf(ParentOf(node)) == node;
- }
- // Returns true iff |node| is right child of its parent.
- bool IsRightChild(uint32_t node) const {
- assert(node);
- return RightOf(ParentOf(node)) == node;
- }
- // Returns true iff |node| has no relatives.
- bool IsOrphan(uint32_t node) const {
- assert(node);
- return !ParentOf(node) && !LeftOf(node) && !RightOf(node);
- }
- // Returns true iff |node| is in the tree.
- bool IsInTree(uint32_t node) const {
- assert(node);
- return node == root_ || !IsOrphan(node);
- }
- // Returns the height difference between right and left subtrees.
- int BalanceOf(uint32_t node) const {
- return int(HeightOf(RightOf(node))) - int(HeightOf(LeftOf(node)));
- }
- // Updates size and height of the node, assuming that the children have
- // correct values.
- void UpdateNode(uint32_t node);
- // Returns the most LeftOf(LeftOf(... descendent which is not leaf.
- uint32_t LeftestDescendantOf(uint32_t node) const {
- uint32_t parent = 0;
- while (node) {
- parent = node;
- node = LeftOf(node);
- }
- return parent;
- }
- // Returns the most RightOf(RightOf(... descendent which is not leaf.
- uint32_t RightestDescendantOf(uint32_t node) const {
- uint32_t parent = 0;
- while (node) {
- parent = node;
- node = RightOf(node);
- }
- return parent;
- }
- // Inserts node in the tree. The node must be an orphan.
- void InsertNode(uint32_t node);
- // Removes node from the tree. May change value_to_node_ if removal uses a
- // scapegoat. Returns the removed (orphaned) handle for recycling. The
- // returned handle may not be equal to |node| if scapegoat was used.
- uint32_t RemoveNode(uint32_t node);
- // Rotates |node| left, reassigns all connections and returns the node
- // which takes place of the |node|.
- uint32_t RotateLeft(const uint32_t node);
- // Rotates |node| right, reassigns all connections and returns the node
- // which takes place of the |node|.
- uint32_t RotateRight(const uint32_t node);
- // Root node handle. The tree is empty if root_ is 0.
- uint32_t root_ = 0;
- // Incremented counters for next timestamp and value.
- uint32_t next_timestamp_ = 1;
- // Holds all tree nodes. Indices of this vector are node handles.
- std::vector<Node> nodes_;
- // Maps ids to node handles.
- std::unordered_map<uint32_t, uint32_t> value_to_node_;
- // Cache for the last accessed value in the sequence.
- uint32_t last_accessed_value_ = 0;
- bool last_accessed_value_valid_ = false;
- };
- class MultiMoveToFront {
- public:
- // Inserts |value| to sequence with handle |mtf|.
- // Returns false if |mtf| already has |value|.
- bool Insert(uint64_t mtf, uint32_t value) {
- if (GetMtf(mtf).Insert(value)) {
- val_to_mtfs_[value].insert(mtf);
- return true;
- }
- return false;
- }
- // Removes |value| from sequence with handle |mtf|.
- // Returns false if |mtf| doesn't have |value|.
- bool Remove(uint64_t mtf, uint32_t value) {
- if (GetMtf(mtf).Remove(value)) {
- val_to_mtfs_[value].erase(mtf);
- return true;
- }
- assert(val_to_mtfs_[value].count(mtf) == 0);
- return false;
- }
- // Removes |value| from all sequences which have it.
- void RemoveFromAll(uint32_t value) {
- auto it = val_to_mtfs_.find(value);
- if (it == val_to_mtfs_.end()) return;
- auto& mtfs_containing_value = it->second;
- for (uint64_t mtf : mtfs_containing_value) {
- GetMtf(mtf).Remove(value);
- }
- val_to_mtfs_.erase(value);
- }
- // Computes rank of |value| in sequence |mtf|.
- // Returns false if |mtf| doesn't have |value|.
- bool RankFromValue(uint64_t mtf, uint32_t value, uint32_t* rank) {
- return GetMtf(mtf).RankFromValue(value, rank);
- }
- // Finds |value| with |rank| in sequence |mtf|.
- // Returns false if |rank| is out of bounds.
- bool ValueFromRank(uint64_t mtf, uint32_t rank, uint32_t* value) {
- return GetMtf(mtf).ValueFromRank(rank, value);
- }
- // Returns size of |mtf| sequence.
- uint32_t GetSize(uint64_t mtf) { return GetMtf(mtf).GetSize(); }
- // Promotes |value| in all sequences which have it.
- void Promote(uint32_t value) {
- const auto it = val_to_mtfs_.find(value);
- if (it == val_to_mtfs_.end()) return;
- const auto& mtfs_containing_value = it->second;
- for (uint64_t mtf : mtfs_containing_value) {
- GetMtf(mtf).Promote(value);
- }
- }
- // Inserts |value| in sequence |mtf| or promotes if it's already there.
- void InsertOrPromote(uint64_t mtf, uint32_t value) {
- if (!Insert(mtf, value)) {
- GetMtf(mtf).Promote(value);
- }
- }
- // Returns if |mtf| sequence has |value|.
- bool HasValue(uint64_t mtf, uint32_t value) {
- return GetMtf(mtf).HasValue(value);
- }
- private:
- // Returns actual MoveToFront object corresponding to |handle|.
- // As multiple operations are often performed consecutively for the same
- // sequence, the last returned value is cached.
- MoveToFront& GetMtf(uint64_t handle) {
- if (!cached_mtf_ || cached_handle_ != handle) {
- cached_handle_ = handle;
- cached_mtf_ = &mtfs_[handle];
- }
- return *cached_mtf_;
- }
- // Container holding MoveToFront objects. Map key is sequence handle.
- std::map<uint64_t, MoveToFront> mtfs_;
- // Container mapping value to sequences which contain that value.
- std::unordered_map<uint32_t, std::set<uint64_t>> val_to_mtfs_;
- // Cache for the last accessed sequence.
- uint64_t cached_handle_ = 0;
- MoveToFront* cached_mtf_ = nullptr;
- };
- } // namespace comp
- } // namespace spvtools
- #endif // SOURCE_COMP_MOVE_TO_FRONT_H_
|