1 // Copyright (c) 2018 Google Inc. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #include "source/comp/move_to_front.h" 16 17 #include <algorithm> 18 #include <iomanip> 19 #include <iostream> 20 #include <ostream> 21 #include <sstream> 22 #include <unordered_set> 23 #include <utility> 24 25 namespace spvtools { 26 namespace comp { 27 28 bool MoveToFront::Insert(uint32_t value) { 29 auto it = value_to_node_.find(value); 30 if (it != value_to_node_.end() && IsInTree(it->second)) return false; 31 32 const uint32_t old_size = GetSize(); 33 (void)old_size; 34 35 InsertNode(CreateNode(next_timestamp_++, value)); 36 37 last_accessed_value_ = value; 38 last_accessed_value_valid_ = true; 39 40 assert(value_to_node_.count(value)); 41 assert(old_size + 1 == GetSize()); 42 return true; 43 } 44 45 bool MoveToFront::Remove(uint32_t value) { 46 auto it = value_to_node_.find(value); 47 if (it == value_to_node_.end()) return false; 48 49 if (!IsInTree(it->second)) return false; 50 51 if (last_accessed_value_ == value) last_accessed_value_valid_ = false; 52 53 const uint32_t orphan = RemoveNode(it->second); 54 (void)orphan; 55 // The node of |value| is still alive but it's orphaned now. Can still be 56 // reused later. 57 assert(!IsInTree(orphan)); 58 assert(ValueOf(orphan) == value); 59 return true; 60 } 61 62 bool MoveToFront::RankFromValue(uint32_t value, uint32_t* rank) { 63 if (last_accessed_value_valid_ && last_accessed_value_ == value) { 64 *rank = 1; 65 return true; 66 } 67 68 const uint32_t old_size = GetSize(); 69 if (old_size == 1) { 70 if (ValueOf(root_) == value) { 71 *rank = 1; 72 return true; 73 } else { 74 return false; 75 } 76 } 77 78 const auto it = value_to_node_.find(value); 79 if (it == value_to_node_.end()) { 80 return false; 81 } 82 83 uint32_t target = it->second; 84 85 if (!IsInTree(target)) { 86 return false; 87 } 88 89 uint32_t node = target; 90 *rank = 1 + SizeOf(LeftOf(node)); 91 while (node) { 92 if (IsRightChild(node)) *rank += 1 + SizeOf(LeftOf(ParentOf(node))); 93 node = ParentOf(node); 94 } 95 96 // Don't update timestamp if the node has rank 1. 97 if (*rank != 1) { 98 // Update timestamp and reposition the node. 99 target = RemoveNode(target); 100 assert(ValueOf(target) == value); 101 assert(old_size == GetSize() + 1); 102 MutableTimestampOf(target) = next_timestamp_++; 103 InsertNode(target); 104 assert(old_size == GetSize()); 105 } 106 107 last_accessed_value_ = value; 108 last_accessed_value_valid_ = true; 109 return true; 110 } 111 112 bool MoveToFront::HasValue(uint32_t value) const { 113 const auto it = value_to_node_.find(value); 114 if (it == value_to_node_.end()) { 115 return false; 116 } 117 118 return IsInTree(it->second); 119 } 120 121 bool MoveToFront::Promote(uint32_t value) { 122 if (last_accessed_value_valid_ && last_accessed_value_ == value) { 123 return true; 124 } 125 126 const uint32_t old_size = GetSize(); 127 if (old_size == 1) return ValueOf(root_) == value; 128 129 const auto it = value_to_node_.find(value); 130 if (it == value_to_node_.end()) { 131 return false; 132 } 133 134 uint32_t target = it->second; 135 136 if (!IsInTree(target)) { 137 return false; 138 } 139 140 // Update timestamp and reposition the node. 141 target = RemoveNode(target); 142 assert(ValueOf(target) == value); 143 assert(old_size == GetSize() + 1); 144 145 MutableTimestampOf(target) = next_timestamp_++; 146 InsertNode(target); 147 assert(old_size == GetSize()); 148 149 last_accessed_value_ = value; 150 last_accessed_value_valid_ = true; 151 return true; 152 } 153 154 bool MoveToFront::ValueFromRank(uint32_t rank, uint32_t* value) { 155 if (last_accessed_value_valid_ && rank == 1) { 156 *value = last_accessed_value_; 157 return true; 158 } 159 160 const uint32_t old_size = GetSize(); 161 if (rank <= 0 || rank > old_size) { 162 return false; 163 } 164 165 if (old_size == 1) { 166 *value = ValueOf(root_); 167 return true; 168 } 169 170 const bool update_timestamp = (rank != 1); 171 172 uint32_t node = root_; 173 while (node) { 174 const uint32_t left_subtree_num_nodes = SizeOf(LeftOf(node)); 175 if (rank == left_subtree_num_nodes + 1) { 176 // This is the node we are looking for. 177 // Don't update timestamp if the node has rank 1. 178 if (update_timestamp) { 179 node = RemoveNode(node); 180 assert(old_size == GetSize() + 1); 181 MutableTimestampOf(node) = next_timestamp_++; 182 InsertNode(node); 183 assert(old_size == GetSize()); 184 } 185 *value = ValueOf(node); 186 last_accessed_value_ = *value; 187 last_accessed_value_valid_ = true; 188 return true; 189 } 190 191 if (rank < left_subtree_num_nodes + 1) { 192 // Descend into the left subtree. The rank is still valid. 193 node = LeftOf(node); 194 } else { 195 // Descend into the right subtree. We leave behind the left subtree and 196 // the current node, adjust the |rank| accordingly. 197 rank -= left_subtree_num_nodes + 1; 198 node = RightOf(node); 199 } 200 } 201 202 assert(0); 203 return false; 204 } 205 206 uint32_t MoveToFront::CreateNode(uint32_t timestamp, uint32_t value) { 207 uint32_t handle = static_cast<uint32_t>(nodes_.size()); 208 const auto result = value_to_node_.emplace(value, handle); 209 if (result.second) { 210 // Create new node. 211 nodes_.emplace_back(Node()); 212 Node& node = nodes_.back(); 213 node.timestamp = timestamp; 214 node.value = value; 215 node.size = 1; 216 // Non-NIL nodes start with height 1 because their NIL children are 217 // leaves. 218 node.height = 1; 219 } else { 220 // Reuse old node. 221 handle = result.first->second; 222 assert(!IsInTree(handle)); 223 assert(ValueOf(handle) == value); 224 assert(SizeOf(handle) == 1); 225 assert(HeightOf(handle) == 1); 226 MutableTimestampOf(handle) = timestamp; 227 } 228 229 return handle; 230 } 231 232 void MoveToFront::InsertNode(uint32_t node) { 233 assert(!IsInTree(node)); 234 assert(SizeOf(node) == 1); 235 assert(HeightOf(node) == 1); 236 assert(TimestampOf(node)); 237 238 if (!root_) { 239 root_ = node; 240 return; 241 } 242 243 uint32_t iter = root_; 244 uint32_t parent = 0; 245 246 // Will determine if |node| will become the right or left child after 247 // insertion (but before balancing). 248 bool right_child = true; 249 250 // Find the node which will become |node|'s parent after insertion 251 // (but before balancing). 252 while (iter) { 253 parent = iter; 254 assert(TimestampOf(iter) != TimestampOf(node)); 255 right_child = TimestampOf(iter) > TimestampOf(node); 256 iter = right_child ? RightOf(iter) : LeftOf(iter); 257 } 258 259 assert(parent); 260 261 // Connect node and parent. 262 MutableParentOf(node) = parent; 263 if (right_child) 264 MutableRightOf(parent) = node; 265 else 266 MutableLeftOf(parent) = node; 267 268 // Insertion is finished. Start the balancing process. 269 bool needs_rebalancing = true; 270 parent = ParentOf(node); 271 272 while (parent) { 273 UpdateNode(parent); 274 275 if (needs_rebalancing) { 276 const int parent_balance = BalanceOf(parent); 277 278 if (RightOf(parent) == node) { 279 // Added node to the right subtree. 280 if (parent_balance > 1) { 281 // Parent is right heavy, rotate left. 282 if (BalanceOf(node) < 0) RotateRight(node); 283 parent = RotateLeft(parent); 284 } else if (parent_balance == 0 || parent_balance == -1) { 285 // Parent is balanced or left heavy, no need to balance further. 286 needs_rebalancing = false; 287 } 288 } else { 289 // Added node to the left subtree. 290 if (parent_balance < -1) { 291 // Parent is left heavy, rotate right. 292 if (BalanceOf(node) > 0) RotateLeft(node); 293 parent = RotateRight(parent); 294 } else if (parent_balance == 0 || parent_balance == 1) { 295 // Parent is balanced or right heavy, no need to balance further. 296 needs_rebalancing = false; 297 } 298 } 299 } 300 301 assert(BalanceOf(parent) >= -1 && (BalanceOf(parent) <= 1)); 302 303 node = parent; 304 parent = ParentOf(parent); 305 } 306 } 307 308 uint32_t MoveToFront::RemoveNode(uint32_t node) { 309 if (LeftOf(node) && RightOf(node)) { 310 // If |node| has two children, then use another node as scapegoat and swap 311 // their contents. We pick the scapegoat on the side of the tree which has 312 // more nodes. 313 const uint32_t scapegoat = SizeOf(LeftOf(node)) >= SizeOf(RightOf(node)) 314 ? RightestDescendantOf(LeftOf(node)) 315 : LeftestDescendantOf(RightOf(node)); 316 assert(scapegoat); 317 std::swap(MutableValueOf(node), MutableValueOf(scapegoat)); 318 std::swap(MutableTimestampOf(node), MutableTimestampOf(scapegoat)); 319 value_to_node_[ValueOf(node)] = node; 320 value_to_node_[ValueOf(scapegoat)] = scapegoat; 321 node = scapegoat; 322 } 323 324 // |node| may have only one child at this point. 325 assert(!RightOf(node) || !LeftOf(node)); 326 327 uint32_t parent = ParentOf(node); 328 uint32_t child = RightOf(node) ? RightOf(node) : LeftOf(node); 329 330 // Orphan |node| and reconnect parent and child. 331 if (child) MutableParentOf(child) = parent; 332 333 if (parent) { 334 if (LeftOf(parent) == node) 335 MutableLeftOf(parent) = child; 336 else 337 MutableRightOf(parent) = child; 338 } 339 340 MutableParentOf(node) = 0; 341 MutableLeftOf(node) = 0; 342 MutableRightOf(node) = 0; 343 UpdateNode(node); 344 const uint32_t orphan = node; 345 346 if (root_ == node) root_ = child; 347 348 // Removal is finished. Start the balancing process. 349 bool needs_rebalancing = true; 350 node = child; 351 352 while (parent) { 353 UpdateNode(parent); 354 355 if (needs_rebalancing) { 356 const int parent_balance = BalanceOf(parent); 357 358 if (parent_balance == 1 || parent_balance == -1) { 359 // The height of the subtree was not changed. 360 needs_rebalancing = false; 361 } else { 362 if (RightOf(parent) == node) { 363 // Removed node from the right subtree. 364 if (parent_balance < -1) { 365 // Parent is left heavy, rotate right. 366 const uint32_t sibling = LeftOf(parent); 367 if (BalanceOf(sibling) > 0) RotateLeft(sibling); 368 parent = RotateRight(parent); 369 } 370 } else { 371 // Removed node from the left subtree. 372 if (parent_balance > 1) { 373 // Parent is right heavy, rotate left. 374 const uint32_t sibling = RightOf(parent); 375 if (BalanceOf(sibling) < 0) RotateRight(sibling); 376 parent = RotateLeft(parent); 377 } 378 } 379 } 380 } 381 382 assert(BalanceOf(parent) >= -1 && (BalanceOf(parent) <= 1)); 383 384 node = parent; 385 parent = ParentOf(parent); 386 } 387 388 return orphan; 389 } 390 391 uint32_t MoveToFront::RotateLeft(const uint32_t node) { 392 const uint32_t pivot = RightOf(node); 393 assert(pivot); 394 395 // LeftOf(pivot) gets attached to node in place of pivot. 396 MutableRightOf(node) = LeftOf(pivot); 397 if (RightOf(node)) MutableParentOf(RightOf(node)) = node; 398 399 // Pivot gets attached to ParentOf(node) in place of node. 400 MutableParentOf(pivot) = ParentOf(node); 401 if (!ParentOf(node)) 402 root_ = pivot; 403 else if (IsLeftChild(node)) 404 MutableLeftOf(ParentOf(node)) = pivot; 405 else 406 MutableRightOf(ParentOf(node)) = pivot; 407 408 // Node is child of pivot. 409 MutableLeftOf(pivot) = node; 410 MutableParentOf(node) = pivot; 411 412 // Update both node and pivot. Pivot is the new parent of node, so node should 413 // be updated first. 414 UpdateNode(node); 415 UpdateNode(pivot); 416 417 return pivot; 418 } 419 420 uint32_t MoveToFront::RotateRight(const uint32_t node) { 421 const uint32_t pivot = LeftOf(node); 422 assert(pivot); 423 424 // RightOf(pivot) gets attached to node in place of pivot. 425 MutableLeftOf(node) = RightOf(pivot); 426 if (LeftOf(node)) MutableParentOf(LeftOf(node)) = node; 427 428 // Pivot gets attached to ParentOf(node) in place of node. 429 MutableParentOf(pivot) = ParentOf(node); 430 if (!ParentOf(node)) 431 root_ = pivot; 432 else if (IsLeftChild(node)) 433 MutableLeftOf(ParentOf(node)) = pivot; 434 else 435 MutableRightOf(ParentOf(node)) = pivot; 436 437 // Node is child of pivot. 438 MutableRightOf(pivot) = node; 439 MutableParentOf(node) = pivot; 440 441 // Update both node and pivot. Pivot is the new parent of node, so node should 442 // be updated first. 443 UpdateNode(node); 444 UpdateNode(pivot); 445 446 return pivot; 447 } 448 449 void MoveToFront::UpdateNode(uint32_t node) { 450 MutableSizeOf(node) = 1 + SizeOf(LeftOf(node)) + SizeOf(RightOf(node)); 451 MutableHeightOf(node) = 452 1 + std::max(HeightOf(LeftOf(node)), HeightOf(RightOf(node))); 453 } 454 455 } // namespace comp 456 } // namespace spvtools 457