Changeset 407 in vbox for trunk/src/VBox/Runtime
- Timestamp:
- Jan 28, 2007 9:47:29 AM (18 years ago)
- svn:sync-xref-src-repo-rev:
- 17978
- File:
-
- 1 edited
-
trunk/src/VBox/Runtime/table/avl_Base.cpp.h (modified) (2 diffs)
Legend:
- Unmodified
- Added
- Removed
-
trunk/src/VBox/Runtime/table/avl_Base.cpp.h
r404 r407 144 144 145 145 146 /******************************************************************************* 147 * Internal Functions * 148 *******************************************************************************/ 149 DECLINLINE(void) KAVL_FN(Rebalance)(PKAVLSTACK pStack); 146 147 /** 148 * Rewinds a stack of pointers to pointers to nodes, rebalancing the tree. 149 * @param pStack Pointer to stack to rewind. 150 * @sketch LOOP thru all stack entries 151 * BEGIN 152 * Get pointer to pointer to node (and pointer to node) from the stack. 153 * IF 2 higher left subtree than in right subtree THEN 154 * BEGIN 155 * IF higher (or equal) left-sub-subtree than right-sub-subtree THEN 156 * * n+2|n+3 157 * / \ / \ 158 * n+2 n ==> n+1 n+1|n+2 159 * / \ / \ 160 * n+1 n|n+1 n|n+1 n 161 * 162 * Or with keys: 163 * 164 * 4 2 165 * / \ / \ 166 * 2 5 ==> 1 4 167 * / \ / \ 168 * 1 3 3 5 169 * 170 * ELSE 171 * * n+2 172 * / \ / \ 173 * n+2 n n+1 n+1 174 * / \ ==> / \ / \ 175 * n n+1 n L R n 176 * / \ 177 * L R 178 * 179 * Or with keys: 180 * 6 4 181 * / \ / \ 182 * 2 7 ==> 2 6 183 * / \ / \ / \ 184 * 1 4 1 3 5 7 185 * / \ 186 * 3 5 187 * END 188 * ELSE IF 2 higher in right subtree than in left subtree THEN 189 * BEGIN 190 * Same as above but left <==> right. (invert the picture) 191 * ELSE 192 * IF correct height THEN break 193 * ELSE correct height. 194 * END 195 */ 196 DECLINLINE(void) KAVL_FN(Rebalance)(PKAVLSTACK pStack) 197 { 198 while (pStack->cEntries > 0) 199 { 200 /** @todo Perhaps some of these KAVL_SET_POINTER_NULL() cases could be optimized away.. */ 201 PPKAVLNODECORE ppNode = pStack->aEntries[--pStack->cEntries]; 202 PKAVLNODECORE pNode = KAVL_GET_POINTER(ppNode); 203 PKAVLNODECORE pLeftNode = KAVL_GET_POINTER_NULL(&pNode->pLeft); 204 unsigned char uchLeftHeight = AVL_HEIGHTOF(pLeftNode); 205 PKAVLNODECORE pRightNode = KAVL_GET_POINTER_NULL(&pNode->pRight); 206 unsigned char uchRightHeight = AVL_HEIGHTOF(pRightNode); 207 208 if (uchRightHeight + 1 < uchLeftHeight) 209 { 210 PKAVLNODECORE pLeftLeftNode = KAVL_GET_POINTER_NULL(&pLeftNode->pLeft); 211 PKAVLNODECORE pLeftRightNode = KAVL_GET_POINTER_NULL(&pLeftNode->pRight); 212 unsigned char uchLeftRightHeight = AVL_HEIGHTOF(pLeftRightNode); 213 214 if (AVL_HEIGHTOF(pLeftLeftNode) >= uchLeftRightHeight) 215 { 216 KAVL_SET_POINTER_NULL(&pNode->pLeft, &pLeftNode->pRight); 217 KAVL_SET_POINTER(&pLeftNode->pRight, pNode); 218 pLeftNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchLeftRightHeight))); 219 KAVL_SET_POINTER(ppNode, pLeftNode); 220 } 221 else 222 { 223 KAVL_SET_POINTER_NULL(&pLeftNode->pRight, &pLeftRightNode->pLeft); 224 KAVL_SET_POINTER_NULL(&pNode->pLeft, &pLeftRightNode->pRight); 225 KAVL_SET_POINTER(&pLeftRightNode->pLeft, pLeftNode); 226 KAVL_SET_POINTER(&pLeftRightNode->pRight, pNode); 227 pLeftNode->uchHeight = pNode->uchHeight = uchLeftRightHeight; 228 pLeftRightNode->uchHeight = uchLeftHeight; 229 KAVL_SET_POINTER(ppNode, pLeftRightNode); 230 } 231 } 232 else if (uchLeftHeight + 1 < uchRightHeight) 233 { 234 PKAVLNODECORE pRightLeftNode = KAVL_GET_POINTER_NULL(&pRightNode->pLeft); 235 unsigned char uchRightLeftHeight = AVL_HEIGHTOF(pRightLeftNode); 236 PKAVLNODECORE pRightRightNode = KAVL_GET_POINTER_NULL(&pRightNode->pRight); 237 238 if (AVL_HEIGHTOF(pRightRightNode) >= uchRightLeftHeight) 239 { 240 KAVL_SET_POINTER_NULL(&pNode->pRight, &pRightNode->pLeft); 241 KAVL_SET_POINTER(&pRightNode->pLeft, pNode); 242 pRightNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchRightLeftHeight))); 243 KAVL_SET_POINTER(ppNode, pRightNode); 244 } 245 else 246 { 247 KAVL_SET_POINTER_NULL(&pRightNode->pLeft, &pRightLeftNode->pRight); 248 KAVL_SET_POINTER_NULL(&pNode->pRight, &pRightLeftNode->pLeft); 249 KAVL_SET_POINTER(&pRightLeftNode->pRight, pRightNode); 250 KAVL_SET_POINTER(&pRightLeftNode->pLeft, pNode); 251 pRightNode->uchHeight = pNode->uchHeight = uchRightLeftHeight; 252 pRightLeftNode->uchHeight = uchRightHeight; 253 KAVL_SET_POINTER(ppNode, pRightLeftNode); 254 } 255 } 256 else 257 { 258 register unsigned char uchHeight = (unsigned char)(KMAX(uchLeftHeight, uchRightHeight) + 1); 259 if (uchHeight == pNode->uchHeight) 260 break; 261 pNode->uchHeight = uchHeight; 262 } 263 } 264 265 } 150 266 151 267 … … 331 447 } 332 448 333 334 /** 335 * Rewinds a stack of pointers to pointers to nodes, rebalancing the tree. 336 * @param pStack Pointer to stack to rewind. 337 * @sketch LOOP thru all stack entries 338 * BEGIN 339 * Get pointer to pointer to node (and pointer to node) from the stack. 340 * IF 2 higher left subtree than in right subtree THEN 341 * BEGIN 342 * IF higher (or equal) left-sub-subtree than right-sub-subtree THEN 343 * * n+2|n+3 344 * / \ / \ 345 * n+2 n ==> n+1 n+1|n+2 346 * / \ / \ 347 * n+1 n|n+1 n|n+1 n 348 * 349 * Or with keys: 350 * 351 * 4 2 352 * / \ / \ 353 * 2 5 ==> 1 4 354 * / \ / \ 355 * 1 3 3 5 356 * 357 * ELSE 358 * * n+2 359 * / \ / \ 360 * n+2 n n+1 n+1 361 * / \ ==> / \ / \ 362 * n n+1 n L R n 363 * / \ 364 * L R 365 * 366 * Or with keys: 367 * 6 4 368 * / \ / \ 369 * 2 7 ==> 2 6 370 * / \ / \ / \ 371 * 1 4 1 3 5 7 372 * / \ 373 * 3 5 374 * END 375 * ELSE IF 2 higher in right subtree than in left subtree THEN 376 * BEGIN 377 * Same as above but left <==> right. (invert the picture) 378 * ELSE 379 * IF correct height THEN break 380 * ELSE correct height. 381 * END 382 */ 383 DECLINLINE(void) KAVL_FN(Rebalance)(PKAVLSTACK pStack) 384 { 385 while (pStack->cEntries > 0) 386 { 387 /** @todo Perhaps some of these KAVL_SET_POINTER_NULL() cases could be optimized away.. */ 388 PPKAVLNODECORE ppNode = pStack->aEntries[--pStack->cEntries]; 389 PKAVLNODECORE pNode = KAVL_GET_POINTER(ppNode); 390 PKAVLNODECORE pLeftNode = KAVL_GET_POINTER_NULL(&pNode->pLeft); 391 unsigned char uchLeftHeight = AVL_HEIGHTOF(pLeftNode); 392 PKAVLNODECORE pRightNode = KAVL_GET_POINTER_NULL(&pNode->pRight); 393 unsigned char uchRightHeight = AVL_HEIGHTOF(pRightNode); 394 395 if (uchRightHeight + 1 < uchLeftHeight) 396 { 397 PKAVLNODECORE pLeftLeftNode = KAVL_GET_POINTER_NULL(&pLeftNode->pLeft); 398 PKAVLNODECORE pLeftRightNode = KAVL_GET_POINTER_NULL(&pLeftNode->pRight); 399 unsigned char uchLeftRightHeight = AVL_HEIGHTOF(pLeftRightNode); 400 401 if (AVL_HEIGHTOF(pLeftLeftNode) >= uchLeftRightHeight) 402 { 403 KAVL_SET_POINTER_NULL(&pNode->pLeft, &pLeftNode->pRight); 404 KAVL_SET_POINTER(&pLeftNode->pRight, pNode); 405 pLeftNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchLeftRightHeight))); 406 KAVL_SET_POINTER(ppNode, pLeftNode); 407 } 408 else 409 { 410 KAVL_SET_POINTER_NULL(&pLeftNode->pRight, &pLeftRightNode->pLeft); 411 KAVL_SET_POINTER_NULL(&pNode->pLeft, &pLeftRightNode->pRight); 412 KAVL_SET_POINTER(&pLeftRightNode->pLeft, pLeftNode); 413 KAVL_SET_POINTER(&pLeftRightNode->pRight, pNode); 414 pLeftNode->uchHeight = pNode->uchHeight = uchLeftRightHeight; 415 pLeftRightNode->uchHeight = uchLeftHeight; 416 KAVL_SET_POINTER(ppNode, pLeftRightNode); 417 } 418 } 419 else if (uchLeftHeight + 1 < uchRightHeight) 420 { 421 PKAVLNODECORE pRightLeftNode = KAVL_GET_POINTER_NULL(&pRightNode->pLeft); 422 unsigned char uchRightLeftHeight = AVL_HEIGHTOF(pRightLeftNode); 423 PKAVLNODECORE pRightRightNode = KAVL_GET_POINTER_NULL(&pRightNode->pRight); 424 425 if (AVL_HEIGHTOF(pRightRightNode) >= uchRightLeftHeight) 426 { 427 KAVL_SET_POINTER_NULL(&pNode->pRight, &pRightNode->pLeft); 428 KAVL_SET_POINTER(&pRightNode->pLeft, pNode); 429 pRightNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchRightLeftHeight))); 430 KAVL_SET_POINTER(ppNode, pRightNode); 431 } 432 else 433 { 434 KAVL_SET_POINTER_NULL(&pRightNode->pLeft, &pRightLeftNode->pRight); 435 KAVL_SET_POINTER_NULL(&pNode->pRight, &pRightLeftNode->pLeft); 436 KAVL_SET_POINTER(&pRightLeftNode->pRight, pRightNode); 437 KAVL_SET_POINTER(&pRightLeftNode->pLeft, pNode); 438 pRightNode->uchHeight = pNode->uchHeight = uchRightLeftHeight; 439 pRightLeftNode->uchHeight = uchRightHeight; 440 KAVL_SET_POINTER(ppNode, pRightLeftNode); 441 } 442 } 443 else 444 { 445 register unsigned char uchHeight = (unsigned char)(KMAX(uchLeftHeight, uchRightHeight) + 1); 446 if (uchHeight == pNode->uchHeight) 447 break; 448 pNode->uchHeight = uchHeight; 449 } 450 } 451 452 } 453 454 #endif 449 #endif
Note:
See TracChangeset
for help on using the changeset viewer.
