Changeset df6348bb in rtems
- Timestamp:
- Mar 21, 2002, 2:05:57 PM (19 years ago)
- Branches:
- 4.10, 4.11, 4.8, 4.9, 5, master
- Children:
- fd55b7d
- Parents:
- d7478774
- Files:
-
- 9 edited
Legend:
- Unmodified
- Added
- Removed
-
c/src/exec/libblock/ChangeLog
rd7478774 rdf6348bb 1 2002-03-21 Alexander Kukuta <kam@oktet.ru> 2 3 * src/bdbuf.c (avl_insert, avl_remove): Reimplemented from scratch 4 to avoid using GPLed sources in RTEMS core. 5 * src/bdbuf.c, include/rtems/bdbuf.h: Remove "binary tree" 6 implementation which was used for debugging only. 7 8 2002-03-13 Victor V. Vengerov <vvv@oktet.ru> 9 10 * src/bdbuf.c (find_or_assign_buffer, rtems_bdbuf_read, 11 rtems_bdbuf_sync, rtems_bdbuf_syncdev, bdbuf_swapout_task): 12 Fix bug: disable interrupts and set level properly before 13 _CORE_mutex_Seize invocation). 14 1 15 2002-02-28 Joel Sherrill <joel@OARcorp.com> 2 16 -
c/src/exec/libblock/include/rtems/bdbuf.h
rd7478774 rdf6348bb 38 38 Chain_Node link; /* Link in the lru, mod or free chains */ 39 39 40 #ifdef BINARY_TREE41 40 struct bdbuf_avl_node { 42 struct bdbuf_buffer *left; /* link to the left sub-tree */ 43 struct bdbuf_buffer *right; /* link to the right sub-tree */ 44 45 int bf; /* AVL tree node balance factor */ 46 } avl; /* AVL-tree links */ 47 #else /* AVL TREE */ 48 struct bdbuf_avl_node { 49 char cache; /* Cache */ 50 51 struct bdbuf_buffer* link[2]; /* Left and Right Kids */ 52 53 char bal; /* The balance of the sub-tree */ 41 char cache; /* Cache */ 42 43 struct bdbuf_buffer* left; /* Left Child */ 44 struct bdbuf_buffer* right; /* Right Child */ 45 46 char bal; /* The balance of the sub-tree */ 54 47 } avl; 55 #endif 48 56 49 dev_t dev; /* device number */ 57 50 blkdev_bnum block; /* block number on the device */ -
c/src/exec/libblock/src/bdbuf.c
rd7478774 rdf6348bb 6 6 * Author: Andrey G. Ivanov <Andrey.Ivanov@oktet.ru> 7 7 * Victor V. Vengerov <vvv@oktet.ru> 8 * Alexander Kukuta <kam@oktet.ru> 8 9 * 9 10 * @(#) $Id$ … … 22 23 #define BLKDEV_FATAL_BDBUF_CONSISTENCY BLKDEV_FATAL_ERROR(1) 23 24 #define BLKDEV_FATAL_BDBUF_SWAPOUT BLKDEV_FATAL_ERROR(2) 24 25 enum balance_factor {BF_LEFT = -1,26 BF_NONE = 0,27 BF_RIGHT = 1};28 25 29 26 … … 112 109 113 110 114 #ifdef BINARY_TREE115 static bdbuf_buffer *116 avl_search(bdbuf_buffer **root, dev_t dev, blkdev_bnum block)117 {118 bdbuf_buffer *p = *root;119 while ((p != NULL) && ((p->dev != dev) || (p->block != block)))120 {121 if ((p->dev < dev) || ((p->dev == dev) && (p->block < block)))122 p = p->avl.right;123 else124 p = p->avl.left;125 }126 return p;127 }128 129 static bdbuf_buffer *130 avl_search_for_sync(bdbuf_buffer **root, disk_device *dd)131 {132 bdbuf_buffer *p = *root;133 bdbuf_buffer *s[32];134 bdbuf_buffer **sp = s;135 dev_t dev = dd->phys_dev->dev;136 blkdev_bnum b = dd->start;137 blkdev_bnum e = b + dd->size - 1;138 139 while (p != NULL)140 {141 if ((p->dev < dev) || ((p->dev == dev) && (p->block < b)))142 p = p->avl.right;143 else if ((p->dev > dev) || ((p->dev == dev) && (p->block > e)))144 p = p->avl.left;145 else if (p->modified)146 return p;147 else148 {149 if (p->avl.right != NULL)150 *sp++ = p->avl.right;151 p = p->avl.left;152 }153 if ((p == NULL) && (sp > s))154 p = *--sp;155 }156 return p;157 }158 159 static int160 avl_insert(bdbuf_buffer **root, bdbuf_buffer *node)161 {162 bdbuf_buffer **r = root;163 node->avl.left = node->avl.right = NULL;164 while (TRUE)165 {166 bdbuf_buffer *rr = *r;167 if (rr == NULL)168 {169 *r = node;170 return 0;171 }172 else if ((rr->dev < node->dev) || ((rr->dev == node->dev) &&173 (rr->block < node->block)))174 {175 r = &rr->avl.right;176 }177 else if ((rr->dev == node->dev) && (rr->block == node->block))178 {179 return -1;180 }181 else182 {183 r = &rr->avl.left;184 }185 }186 }187 188 static int189 avl_remove(bdbuf_buffer **root, bdbuf_buffer *node)190 {191 bdbuf_buffer **p = root;192 dev_t dev = node->dev;193 blkdev_bnum block = node->block;194 195 while ((*p != NULL) && (*p != node))196 {197 if (((*p)->dev < dev) || (((*p)->dev == dev) && ((*p)->block < block)))198 p = &(*p)->avl.right;199 else200 p = &(*p)->avl.left;201 }202 if (*p == NULL)203 return -1;204 205 *p = node->avl.left;206 while (*p != NULL)207 p = &(*p)->avl.right;208 *p = node->avl.right;209 node->avl.left = node->avl.right = NULL;210 return 0;211 }212 213 #else214 215 111 /* The default maximum height of 32 allows for AVL trees having 216 112 between 5,704,880 and 4,294,967,295 nodes, depending on order of … … 221 117 #endif 222 118 223 224 225 /*226 * avl_cmp_node_node --227 * Compares two avl nodes. Function compares dev/block pairs of228 * the node1 and node2.229 *230 * PARAMETERS:231 * node1 - Pointer to the first node to compare232 * node2 - Pointer to the second node to compare233 *234 * RETURNS:235 * 0 - dev/block of the nodes are equal236 * 1 - dev/block of the second node are less237 * -1 - dev/block of the first node are less238 */239 static inline int240 avl_cmp_node_node(const bdbuf_buffer *const node1,241 const bdbuf_buffer *const node2)242 {243 if (node1->dev < node2->dev)244 return -1;245 else if (node1->dev > node2->dev)246 return +1;247 else if (node1->block < node2->block)248 return -1;249 else if (node1->block > node2->block)250 return +1;251 else252 return 0;253 }254 255 /*256 * avl_cmp_node_pattern -257 * compares the dev/block of the node with specified two.258 *259 * PARAMETERS:260 * node1 - Pointer to the node to compare261 * dev/block - The pattern to compare with262 *263 * RETURNS:264 * 0 - dev/block of the node and specified are equal265 * 1 - dev/block specified are less266 * -1 - dev/block of the first node are less267 *268 */269 static inline int270 avl_cmp_node_pattern(const bdbuf_buffer *const node1,271 dev_t dev,272 blkdev_bnum block)273 {274 if (node1->dev < dev)275 return -1;276 else if (node1->dev > dev)277 return +1;278 else if (node1->block < block)279 return -1;280 else if (node1->block > block)281 return +1;282 else283 return 0;284 }285 286 287 119 /* 288 120 * avl_search -- … … 300 132 avl_search(bdbuf_buffer **root, dev_t dev, blkdev_bnum block) 301 133 { 302 303 134 bdbuf_buffer *p = *root; 135 304 136 while ((p != NULL) && ((p->dev != dev) || (p->block != block))) 305 137 { 306 138 if ((p->dev < dev) || ((p->dev == dev) && (p->block < block))) 307 p = p->avl.link[1]; 139 { 140 p = p->avl.right; 141 } 308 142 else 309 p = p->avl.link[0]; 310 } 143 { 144 p = p->avl.left; 145 } 146 } 147 311 148 return p; 312 149 } 150 313 151 314 152 /* avl_search_for_sync -- … … 327 165 avl_search_for_sync(bdbuf_buffer **root, disk_device *dd) 328 166 { 167 dev_t dev = dd->phys_dev->dev; 168 blkdev_bnum block_start = dd->start; 169 blkdev_bnum block_end = dd->start + dd->size - 1; 170 171 bdbuf_buffer *buf_stack[AVL_MAX_HEIGHT]; 172 bdbuf_buffer **buf_prev = buf_stack; 329 173 bdbuf_buffer *p = *root; 330 bdbuf_buffer *s[AVL_MAX_HEIGHT]; 331 bdbuf_buffer **sp = s; 332 dev_t dev = dd->phys_dev->dev; 333 blkdev_bnum b = dd->start; 334 blkdev_bnum e = b + dd->size - 1; 335 174 336 175 while (p != NULL) 337 176 { 338 if ((p->dev < dev) || ((p->dev == dev) && (p->block < b))) 339 p = p->avl.link[1]; 340 else if ((p->dev > dev) || ((p->dev == dev) && (p->block > e))) 341 p = p->avl.link[0]; 177 if ((p->dev < dev) || ((p->dev == dev) && (p->block < block_start))) 178 { 179 p = p->avl.right; 180 } 181 else if ((p->dev > dev) || ((p->dev == dev) && (p->block > block_end))) 182 { 183 p = p->avl.left; 184 } 342 185 else if (p->modified) 186 { 343 187 return p; 188 } 344 189 else 345 190 { 346 if (p->avl.link[1] != NULL) 347 *sp++ = p->avl.link[1]; 348 p = p->avl.link[0]; 349 } 350 if ((p == NULL) && (sp > s)) 351 p = *--sp; 352 } 191 if (p->avl.right != NULL) 192 { 193 *buf_prev++ = p->avl.right; 194 } 195 p = p->avl.left; 196 } 197 198 if ((p == NULL) && (buf_prev > buf_stack)) 199 { 200 p = *--buf_prev; 201 } 202 } 203 353 204 return p; 354 205 } … … 360 211 * 361 212 * PARAMETERS: 362 * root _addr- Pointer to pointer to the root node213 * root - Pointer to pointer to the root node 363 214 * node - Pointer to the node to add. 364 215 * … … 368 219 */ 369 220 static int 370 avl_insert (bdbuf_buffer **root_addr, bdbuf_buffer *node) 371 { 372 /* Uses Knuth's Algorithm 6.2.3A (balanced tree search and 373 insertion), but caches results of comparisons. In empirical 374 tests this eliminates about 25% of the comparisons seen under 375 random insertions. */ 376 377 /* A1. */ 378 int t_modified = 0; 379 bdbuf_buffer *t; 380 bdbuf_buffer *s, *p, *q, *r; 381 382 bdbuf_buffer *root_link = *root_addr;; 383 384 t = root_link; 385 s = p = t; 386 387 if (s == NULL) 388 { 389 q = t = node; 390 q->avl.link[0] = q->avl.link[1] = NULL; 391 q->avl.bal = 0; 392 *root_addr = t; 221 avl_insert(bdbuf_buffer **root, bdbuf_buffer *node) 222 { 223 dev_t dev = node->dev; 224 blkdev_bnum block = node->block; 225 226 bdbuf_buffer *p = *root; 227 bdbuf_buffer *q, *p1, *p2; 228 bdbuf_buffer *buf_stack[AVL_MAX_HEIGHT]; 229 bdbuf_buffer **buf_prev = buf_stack; 230 231 boolean modified = FALSE; 232 233 if (p == NULL) 234 { 235 *root = node; 236 node->avl.left = NULL; 237 node->avl.right = NULL; 238 node->avl.bal = 0; 393 239 return 0; 394 240 } 395 241 396 for (;;) 397 { 398 /* A2. */ 399 int diff = avl_cmp_node_node(node, p); 400 401 /* A3. */ 402 if (diff < 0) 403 { 404 p->avl.cache = 0; 405 q = p->avl.link[0]; 242 while (p != NULL) 243 { 244 *buf_prev++ = p; 245 246 if ((p->dev < dev) || ((p->dev == dev) && (p->block < block))) 247 { 248 p->avl.cache = 1; 249 q = p->avl.right; 406 250 if (q == NULL) 407 251 { 408 p->avl.link[0] = q = node; 252 q = node; 253 p->avl.right = q = node; 409 254 break; 410 255 } 411 256 } 412 /* A4. */ 413 else 414 if (diff > 0) 415 { 416 p->avl.cache = 1; 417 q = p->avl.link[1]; 418 if (q == NULL) 419 { 420 p->avl.link[1] = q = node; 257 else if ((p->dev != dev) || (p->block != block)) 258 { 259 p->avl.cache = -1; 260 q = p->avl.left; 261 if (q == NULL) 262 { 263 q = node; 264 p->avl.left = q; 265 break; 266 } 267 } 268 else 269 { 270 return -1; 271 } 272 273 p = q; 274 } 275 276 q->avl.left = q->avl.right = NULL; 277 q->avl.bal = 0; 278 modified = TRUE; 279 buf_prev--; 280 281 while (modified) 282 { 283 if (p->avl.cache == -1) 284 { 285 switch (p->avl.bal) 286 { 287 case 1: 288 p->avl.bal = 0; 289 modified = FALSE; 421 290 break; 422 } 291 292 case 0: 293 p->avl.bal = -1; 294 break; 295 296 case -1: 297 p1 = p->avl.left; 298 if (p1->avl.bal == -1) /* simple LL-turn */ 299 { 300 p->avl.left = p1->avl.right; 301 p1->avl.right = p; 302 p->avl.bal = 0; 303 p = p1; 304 } 305 else /* double LR-turn */ 306 { 307 p2 = p1->avl.right; 308 p1->avl.right = p2->avl.left; 309 p2->avl.left = p1; 310 p->avl.left = p2->avl.right; 311 p2->avl.right = p; 312 if (p2->avl.bal == -1) p->avl.bal = +1; else p->avl.bal = 0; 313 if (p2->avl.bal == +1) p1->avl.bal = -1; else p1->avl.bal = 0; 314 p = p2; 315 } 316 p->avl.bal = 0; 317 modified = FALSE; 318 break; 319 320 default: 321 break; 322 } 323 } 324 else 325 { 326 switch (p->avl.bal) 327 { 328 case -1: 329 p->avl.bal = 0; 330 modified = FALSE; 331 break; 332 333 case 0: 334 p->avl.bal = 1; 335 break; 336 337 case 1: 338 p1 = p->avl.right; 339 if (p1->avl.bal == 1) /* simple RR-turn */ 340 { 341 p->avl.right = p1->avl.left; 342 p1->avl.left = p; 343 p->avl.bal = 0; 344 p = p1; 345 } 346 else /* double RL-turn */ 347 { 348 p2 = p1->avl.left; 349 p1->avl.left = p2->avl.right; 350 p2->avl.right = p1; 351 p->avl.right = p2->avl.left; 352 p2->avl.left = p; 353 if (p2->avl.bal == +1) p->avl.bal = -1; else p->avl.bal = 0; 354 if (p2->avl.bal == -1) p1->avl.bal = +1; else p1->avl.bal = 0; 355 p = p2; 356 } 357 p->avl.bal = 0; 358 modified = FALSE; 359 break; 360 361 default: 362 break; 363 } 364 } 365 q = p; 366 if (buf_prev > buf_stack) 367 { 368 p = *--buf_prev; 369 370 if (p->avl.cache == -1) 371 { 372 p->avl.left = q; 423 373 } 424 374 else 425 /* A2. */ 426 { 427 /* 428 * The item found. Nothing changed. Have not to update 429 * root_adr*/ 430 431 return -1; 432 } 433 434 /* A3, A4. */ 435 if (q->avl.bal != 0) 436 { 437 t = p, s = q; 438 t_modified = 1; 439 } 440 p = q; 441 } 442 443 /* A5. */ 444 q->avl.link[0] = q->avl.link[1] = NULL; 445 q->avl.bal = 0; 446 447 /* A6. */ 448 r = p = s->avl.link[(int) s->avl.cache]; 449 while (p != q) 450 { 451 p->avl.bal = p->avl.cache * 2 - 1; 452 p = p->avl.link[(int) p->avl.cache]; 453 } 454 455 /* A7. */ 456 if (s->avl.cache == 0) 457 { 458 /* a = -1. */ 459 if (s->avl.bal == 0) 460 { 461 s->avl.bal = -1; 462 *root_addr = root_link; 463 return 0; 464 } 465 else if (s->avl.bal == +1) 466 { 467 s->avl.bal = 0; 468 *root_addr = root_link; 469 return 0; 470 } 471 472 assert (s->avl.bal == -1); 473 if (r->avl.bal == -1) 474 { 475 /* A8. */ 476 p = r; 477 s->avl.link[0] = r->avl.link[1]; 478 r->avl.link[1] = s; 479 s->avl.bal = r->avl.bal = 0; 375 { 376 p->avl.right = q; 377 } 480 378 } 481 379 else 482 380 { 483 /* A9. */ 484 assert(r->avl.bal == +1); 485 p = r->avl.link[1]; 486 r->avl.link[1] = p->avl.link[0]; 487 p->avl.link[0] = r; 488 s->avl.link[0] = p->avl.link[1]; 489 p->avl.link[1] = s; 490 if (p->avl.bal == -1) 491 s->avl.bal = 1, r->avl.bal = 0; 492 else 493 { 494 if (p->avl.bal == 0) 495 { 496 s->avl.bal = r->avl.bal = 0; 497 } 498 else 499 { 500 assert (p->avl.bal == +1); 501 s->avl.bal = 0, r->avl.bal = -1; 502 } 503 } 504 p->avl.bal = 0; 505 } 506 } 507 else 508 { 509 /* a == +1. */ 510 if (s->avl.bal == 0) 511 { 512 s->avl.bal = 1; 513 *root_addr = root_link; 514 return 0; 515 } 516 else if (s->avl.bal == -1) 517 { 518 s->avl.bal = 0; 519 *root_addr = root_link; 520 return 0; 521 } 522 523 assert(s->avl.bal == +1); 524 if (r->avl.bal == +1) 525 { 526 /* A8. */ 527 p = r; 528 s->avl.link[1] = r->avl.link[0]; 529 r->avl.link[0] = s; 530 s->avl.bal = r->avl.bal = 0; 531 } 532 else 533 { 534 /* A9. */ 535 assert(r->avl.bal == -1); 536 p = r->avl.link[0]; 537 r->avl.link[0] = p->avl.link[1]; 538 p->avl.link[1] = r; 539 s->avl.link[1] = p->avl.link[0]; 540 p->avl.link[0] = s; 541 if (p->avl.bal == +1) 542 { 543 s->avl.bal = -1, r->avl.bal = 0; 544 } 545 else 546 { 547 if (p->avl.bal == 0) 548 { 549 s->avl.bal = r->avl.bal = 0; 550 } 551 else 552 { 553 assert(p->avl.bal == -1); 554 s->avl.bal = 0, r->avl.bal = 1; 555 } 556 } 557 p->avl.bal = 0; 558 } 559 } 560 561 /* A10. */ 562 if (t_modified) 563 { 564 if (s == t->avl.link[1]) 565 t->avl.link[1] = p; 566 else 567 t->avl.link[0] = p; 568 } 569 else 570 { 571 root_link = p; 572 } 573 574 *root_addr = root_link; 381 *root = p; 382 break; 383 } 384 }; 385 575 386 return 0; 576 387 } … … 589 400 */ 590 401 static int 591 avl_remove(bdbuf_buffer **root_addr, const bdbuf_buffer *node) 592 { 593 /* Uses my Algorithm D, which can be found at 594 http://www.msu.edu/user/pfaffben/avl. Algorithm D is based on 595 Knuth's Algorithm 6.2.2D (Tree deletion) and 6.2.3A (Balanced 596 tree search and insertion), as well as the notes on pages 465-466 597 of Vol. 3. */ 598 599 /* D1. */ 600 bdbuf_buffer *pa[AVL_MAX_HEIGHT]; /* Stack P: Nodes. */ 601 char a[AVL_MAX_HEIGHT]; /* Stack P: Bits. */ 602 int k = 1; /* Stack P: Pointer. */ 603 604 bdbuf_buffer **q; 605 bdbuf_buffer *p; 606 607 608 /* 609 * To avoid using unnessary instance of the 'bdbuf_buffer' (as pa[0]) 610 * we will catch all access to pa[0] and use &root_avl instead 611 */ 612 struct bdbuf_avl_node root_avl; 613 614 root_avl.link[0] = *root_addr; 615 root_avl.link[1] = NULL; 616 root_avl.bal = 0; 617 root_avl.cache = 0; 618 619 a[0] = 0; 620 621 p = root_avl.link[0]; 622 623 624 k = 1; 625 626 for (;;) 627 { 628 /* D2. */ 629 int diff; 630 631 if (p == NULL) 632 return -1; 633 634 diff = avl_cmp_node_node(node, p); 635 636 if (diff == 0) 402 avl_remove(bdbuf_buffer **root, const bdbuf_buffer *node) 403 { 404 dev_t dev = node->dev; 405 blkdev_bnum block = node->block; 406 407 bdbuf_buffer *p = *root; 408 bdbuf_buffer *q, *r, *s, *p1, *p2; 409 bdbuf_buffer *buf_stack[AVL_MAX_HEIGHT]; 410 bdbuf_buffer **buf_prev = buf_stack; 411 412 boolean modified = FALSE; 413 414 memset(buf_stack, 0, sizeof(buf_stack)); 415 416 while (p != NULL) 417 { 418 *buf_prev++ = p; 419 420 if ((p->dev < dev) || ((p->dev == dev) && (p->block < block))) 421 { 422 p->avl.cache = 1; 423 p = p->avl.right; 424 } 425 else if ((p->dev != dev) || (p->block != block)) 426 { 427 p->avl.cache = -1; 428 p = p->avl.left; 429 } 430 else 431 { 432 /* node found */ 637 433 break; 638 639 /* D3, D4. */ 640 pa[k] = p; 641 if (diff < 0) 642 { 643 p = p->avl.link[0]; 644 a[k] = 0; 645 } 646 else if (diff > 0) 647 { 648 p = p->avl.link[1]; 649 a[k] = 1; 650 } 651 k++; 652 } 653 654 /* D5. */ 655 if (k == 1) 656 { 657 /* Andron */ 658 q = &root_avl.link[(int) a[k - 1]]; 434 } 435 } 436 437 if (p == NULL) 438 { 439 /* there is no such node */ 440 return -1; 441 } 442 443 q = p; 444 445 buf_prev--; 446 if (buf_prev > buf_stack) 447 { 448 p = *(buf_prev - 1); 659 449 } 660 450 else 661 451 { 662 q = &pa[k - 1]->avl.link[(int) a[k - 1]]; 663 } 664 if (p->avl.link[1] == NULL) 665 { 666 *q = p->avl.link[0]; 667 if (*q) 668 (*q)->avl.bal = 0; 452 p = NULL; 453 } 454 455 /* at this moment q - is a node to delete, p is q's parent */ 456 if (q->avl.right == NULL) 457 { 458 r = q->avl.left; 459 if (r != NULL) 460 { 461 r->avl.bal = 0; 462 } 463 q = r; 669 464 } 670 465 else 671 466 { 672 /* D6. */ 673 bdbuf_buffer *r = p->avl.link[1]; 674 if (r->avl.link[0] == NULL) 675 { 676 r->avl.link[0] = p->avl.link[0]; 677 *q = r; 678 r->avl.bal = p->avl.bal; 679 a[k] = 1; 680 pa[k++] = r; 467 bdbuf_buffer **t; 468 469 r = q->avl.right; 470 471 if (r->avl.left == NULL) 472 { 473 r->avl.left = q->avl.left; 474 r->avl.bal = q->avl.bal; 475 r->avl.cache = 1; 476 *buf_prev++ = q = r; 681 477 } 682 478 else 683 479 { 684 /* D7. */ 685 bdbuf_buffer *s = r->avl.link[0]; 686 int l = k++; 687 688 a[k] = 0; 689 pa[k++] = r; 480 t = buf_prev++; 481 s = r; 690 482 691 /* D8. */ 692 while (s->avl.link[0] != NULL) 693 { 694 r = s; 695 s = r->avl.link[0]; 696 a[k] = 0; 697 pa[k++] = r; 698 } 699 700 /* D9. */ 701 a[l] = 1; 702 pa[l] = s; 703 s->avl.link[0] = p->avl.link[0]; 704 r->avl.link[0] = s->avl.link[1]; 705 s->avl.link[1] = p->avl.link[1]; 706 s->avl.bal = p->avl.bal; 707 *q = s; 708 } 709 } 710 711 assert(k > 0); 712 /* D10. */ 713 while (--k) 714 { 715 bdbuf_buffer *s = pa[k], *r; 716 717 if (a[k] == 0) 718 { 719 /* D10. */ 720 if (s->avl.bal == -1) 721 { 722 s->avl.bal = 0; 723 continue; 724 } 725 else if (s->avl.bal == 0) 726 { 727 s->avl.bal = 1; 728 break; 729 } 730 731 assert(s->avl.bal == +1); 732 r = s->avl.link[1]; 733 734 assert(r != NULL); 735 if (r->avl.bal == 0) 736 { 737 /* D11. */ 738 s->avl.link[1] = r->avl.link[0]; 739 r->avl.link[0] = s; 740 r->avl.bal = -1; 741 if (k == 1) 742 { 743 /* Andron */ 744 root_avl.link[(int) a[k - 1]] = r; 745 } 746 else 747 { 748 pa[k - 1]->avl.link[(int) a[k - 1]] = r; 749 } 750 break; 751 } 752 else 753 if (r->avl.bal == +1) 754 { 755 /* D12. */ 756 s->avl.link[1] = r->avl.link[0]; 757 r->avl.link[0] = s; 758 s->avl.bal = r->avl.bal = 0; 759 if (k == 1) 483 while (s->avl.left != NULL) 484 { 485 *buf_prev++ = r = s; 486 s = r->avl.left; 487 r->avl.cache = -1; 488 } 489 490 s->avl.left = q->avl.left; 491 r->avl.left = s->avl.right; 492 s->avl.right = q->avl.right; 493 s->avl.bal = q->avl.bal; 494 s->avl.cache = 1; 495 496 *t = q = s; 497 } 498 } 499 500 if (p != NULL) 501 { 502 if (p->avl.cache == -1) 503 { 504 p->avl.left = q; 505 } 506 else 507 { 508 p->avl.right = q; 509 } 510 } 511 else 512 { 513 *root = q; 514 } 515 516 modified = TRUE; 517 518 while (modified) 519 { 520 if (buf_prev > buf_stack) 521 { 522 p = *--buf_prev; 523 } 524 else 525 { 526 break; 527 } 528 529 if (p->avl.cache == -1) 530 { 531 /* rebalance left branch */ 532 switch (p->avl.bal) 533 { 534 case -1: 535 p->avl.bal = 0; 536 break; 537 case 0: 538 p->avl.bal = 1; 539 modified = FALSE; 540 break; 541 542 case +1: 543 p1 = p->avl.right; 544 545 if (p1->avl.bal >= 0) /* simple RR-turn */ 760 546 { 761 /* Andron */ 762 root_avl.link[(int) a[k - 1]] = r; 763 } 764 else 765 { 766 pa[k - 1]->avl.link[(int) a[k - 1]] = r; 767 } 768 } 769 else 770 { 771 /* D13. */ 772 assert(r->avl.bal == -1); 773 p = r->avl.link[0]; 774 r->avl.link[0] = p->avl.link[1]; 775 p->avl.link[1] = r; 776 s->avl.link[1] = p->avl.link[0]; 777 p->avl.link[0] = s; 778 if (p->avl.bal == +1) 779 s->avl.bal = -1, r->avl.bal = 0; 780 else if (p->avl.bal == 0) 781 { 782 s->avl.bal = r->avl.bal = 0; 783 } 784 else 785 { 786 assert(p->avl.bal == -1); 787 s->avl.bal = 0, r->avl.bal = +1; 788 } 789 p->avl.bal = 0; 790 if (k == 1) 791 { 792 /* Andron */ 793 root_avl.link[(int) a[k - 1]] = p; 794 } 795 else 796 { 797 pa[k - 1]->avl.link[(int) a[k - 1]] = p; 798 } 799 } 800 } 801 else 802 { 803 assert(a[k] == 1); 804 805 /* D10. */ 806 if (s->avl.bal == +1) 807 { 808 s->avl.bal = 0; 809 continue; 810 } 811 else 812 if (s->avl.bal == 0) 813 { 814 s->avl.bal = -1; 815 break; 816 } 817 818 assert(s->avl.bal == -1); 819 r = s->avl.link[0]; 820 821 if (r == NULL || r->avl.bal == 0) 822 { 823 /* D11. */ 824 s->avl.link[0] = r->avl.link[1]; 825 r->avl.link[1] = s; 826 r->avl.bal = 1; 827 if (k == 1) 828 { 829 /* Andron */ 830 root_avl.link[(int) a[k - 1]] = r; 831 } 832 else 833 { 834 pa[k - 1]->avl.link[(int) a[k - 1]] = r; 835 } 836 837 break; 838 } 839 else 840 if (r->avl.bal == -1) 841 { 842 /* D12. */ 843 s->avl.link[0] = r->avl.link[1]; 844 r->avl.link[1] = s; 845 s->avl.bal = r->avl.bal = 0; 846 if (k == 1) 847 { 848 root_avl.link[(int) a[k - 1]] = r; 849 } 850 else 851 { 852 pa[k - 1]->avl.link[(int) a[k - 1]] = r; 853 } 854 855 } 856 else 857 if (r->avl.bal == +1) 858 { 859 /* D13. */ 860 p = r->avl.link[1]; 861 r->avl.link[1] = p->avl.link[0]; 862 p->avl.link[0] = r; 863 s->avl.link[0] = p->avl.link[1]; 864 p->avl.link[1] = s; 865 if (p->avl.bal == -1) 866 s->avl.bal = 1, r->avl.bal = 0; 867 else 868 if (p->avl.bal == 0) 869 s->avl.bal = r->avl.bal = 0; 870 else 871 { 872 assert(p->avl.bal == 1); 873 s->avl.bal = 0, r->avl.bal = -1; 874 } 875 p->avl.bal = 0; 876 if (k == 1) 547 p->avl.right = p1->avl.left; 548 p1->avl.left = p; 549 550 if (p1->avl.bal == 0) 877 551 { 878 /* Andron */879 root_avl.link[(int) a[k - 1]] = p;552 p1->avl.bal = -1; 553 modified = FALSE; 880 554 } 881 555 else 882 556 { 883 pa[k - 1]->avl.link[(int) a[k - 1]] = p; 557 p->avl.bal = 0; 558 p1->avl.bal = 0; 884 559 } 560 p = p1; 885 561 } 886 } 887 } 888 889 *root_addr = root_avl.link[0]; 562 else /* double RL-turn */ 563 { 564 p2 = p1->avl.left; 565 566 p1->avl.left = p2->avl.right; 567 p2->avl.right = p1; 568 p->avl.right = p2->avl.left; 569 p2->avl.left = p; 570 571 if (p2->avl.bal == +1) p->avl.bal = -1; else p->avl.bal = 0; 572 if (p2->avl.bal == -1) p1->avl.bal = 1; else p1->avl.bal = 0; 573 574 p = p2; 575 p2->avl.bal = 0; 576 } 577 break; 578 579 default: 580 break; 581 } 582 } 583 else 584 { 585 /* rebalance right branch */ 586 switch (p->avl.bal) 587 { 588 case +1: 589 p->avl.bal = 0; 590 break; 591 592 case 0: 593 p->avl.bal = -1; 594 modified = FALSE; 595 break; 596 597 case -1: 598 p1 = p->avl.left; 599 600 if (p1->avl.bal <= 0) /* simple LL-turn */ 601 { 602 p->avl.left = p1->avl.right; 603 p1->avl.right = p; 604 if (p1->avl.bal == 0) 605 { 606 p1->avl.bal = 1; 607 modified = FALSE; 608 } 609 else 610 { 611 p->avl.bal = 0; 612 p1->avl.bal = 0; 613 } 614 p = p1; 615 } 616 else /* double LR-turn */ 617 { 618 p2 = p1->avl.right; 619 620 p1->avl.right = p2->avl.left; 621 p2->avl.left = p1; 622 p->avl.left = p2->avl.right; 623 p2->avl.right = p; 624 625 if (p2->avl.bal == -1) p->avl.bal = 1; else p->avl.bal = 0; 626 if (p2->avl.bal == +1) p1->avl.bal = -1; else p1->avl.bal = 0; 627 628 p = p2; 629 p2->avl.bal = 0; 630 } 631 break; 632 633 default: 634 break; 635 } 636 } 637 638 if (buf_prev > buf_stack) 639 { 640 q = *(buf_prev - 1); 641 642 if (q->avl.cache == -1) 643 { 644 q->avl.left = p; 645 } 646 else 647 { 648 q->avl.right = p; 649 } 650 } 651 else 652 { 653 *root = p; 654 break; 655 } 656 657 } 658 890 659 return 0; 891 660 } 892 893 #endif894 661 895 662 /* bdbuf_initialize_pool -- … … 1182 949 bd_buf->dev = device; 1183 950 bd_buf->block = block; 1184 #ifdef BINARY_TREE 951 #ifdef AVL_GPL 952 bd_buf->avl.link[0] = NULL; 953 bd_buf->avl.link[1] = NULL; 954 #else 1185 955 bd_buf->avl.left = NULL; 1186 956 bd_buf->avl.right = NULL; 1187 #else1188 bd_buf->avl.link[0] = NULL;1189 bd_buf->avl.link[1] = NULL;1190 957 #endif 1191 958 bd_buf->use_count = 1; … … 1242 1009 while (bd_buf->in_progress != 0) 1243 1010 { 1011 rtems_interrupt_disable(level); 1244 1012 _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE, 1245 1013 WATCHDOG_NO_TIMEOUT, level); … … 1460 1228 else 1461 1229 { 1230 rtems_interrupt_disable(level); 1462 1231 _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE, 1463 1232 WATCHDOG_NO_TIMEOUT, level); … … 1651 1420 if (rc == RTEMS_SUCCESSFUL) 1652 1421 { 1422 rtems_interrupt_disable(level); 1653 1423 _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE, 1654 1424 WATCHDOG_NO_TIMEOUT, level); … … 1692 1462 if (bd_buf != NULL /* && bd_buf->modified */) 1693 1463 { 1464 rtems_interrupt_disable(level); 1694 1465 _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE, 1695 1466 WATCHDOG_NO_TIMEOUT, level); … … 1764 1535 if (bd_buf->in_progress) 1765 1536 { 1537 rtems_interrupt_disable(level); 1766 1538 _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE, 0, level); 1767 1539 } -
c/src/libblock/ChangeLog
rd7478774 rdf6348bb 1 2002-03-21 Alexander Kukuta <kam@oktet.ru> 2 3 * src/bdbuf.c (avl_insert, avl_remove): Reimplemented from scratch 4 to avoid using GPLed sources in RTEMS core. 5 * src/bdbuf.c, include/rtems/bdbuf.h: Remove "binary tree" 6 implementation which was used for debugging only. 7 8 2002-03-13 Victor V. Vengerov <vvv@oktet.ru> 9 10 * src/bdbuf.c (find_or_assign_buffer, rtems_bdbuf_read, 11 rtems_bdbuf_sync, rtems_bdbuf_syncdev, bdbuf_swapout_task): 12 Fix bug: disable interrupts and set level properly before 13 _CORE_mutex_Seize invocation). 14 1 15 2002-02-28 Joel Sherrill <joel@OARcorp.com> 2 16 -
c/src/libblock/include/rtems/bdbuf.h
rd7478774 rdf6348bb 38 38 Chain_Node link; /* Link in the lru, mod or free chains */ 39 39 40 #ifdef BINARY_TREE41 40 struct bdbuf_avl_node { 42 struct bdbuf_buffer *left; /* link to the left sub-tree */ 43 struct bdbuf_buffer *right; /* link to the right sub-tree */ 44 45 int bf; /* AVL tree node balance factor */ 46 } avl; /* AVL-tree links */ 47 #else /* AVL TREE */ 48 struct bdbuf_avl_node { 49 char cache; /* Cache */ 50 51 struct bdbuf_buffer* link[2]; /* Left and Right Kids */ 52 53 char bal; /* The balance of the sub-tree */ 41 char cache; /* Cache */ 42 43 struct bdbuf_buffer* left; /* Left Child */ 44 struct bdbuf_buffer* right; /* Right Child */ 45 46 char bal; /* The balance of the sub-tree */ 54 47 } avl; 55 #endif 48 56 49 dev_t dev; /* device number */ 57 50 blkdev_bnum block; /* block number on the device */ -
c/src/libblock/src/bdbuf.c
rd7478774 rdf6348bb 6 6 * Author: Andrey G. Ivanov <Andrey.Ivanov@oktet.ru> 7 7 * Victor V. Vengerov <vvv@oktet.ru> 8 * Alexander Kukuta <kam@oktet.ru> 8 9 * 9 10 * @(#) $Id$ … … 22 23 #define BLKDEV_FATAL_BDBUF_CONSISTENCY BLKDEV_FATAL_ERROR(1) 23 24 #define BLKDEV_FATAL_BDBUF_SWAPOUT BLKDEV_FATAL_ERROR(2) 24 25 enum balance_factor {BF_LEFT = -1,26 BF_NONE = 0,27 BF_RIGHT = 1};28 25 29 26 … … 112 109 113 110 114 #ifdef BINARY_TREE115 static bdbuf_buffer *116 avl_search(bdbuf_buffer **root, dev_t dev, blkdev_bnum block)117 {118 bdbuf_buffer *p = *root;119 while ((p != NULL) && ((p->dev != dev) || (p->block != block)))120 {121 if ((p->dev < dev) || ((p->dev == dev) && (p->block < block)))122 p = p->avl.right;123 else124 p = p->avl.left;125 }126 return p;127 }128 129 static bdbuf_buffer *130 avl_search_for_sync(bdbuf_buffer **root, disk_device *dd)131 {132 bdbuf_buffer *p = *root;133 bdbuf_buffer *s[32];134 bdbuf_buffer **sp = s;135 dev_t dev = dd->phys_dev->dev;136 blkdev_bnum b = dd->start;137 blkdev_bnum e = b + dd->size - 1;138 139 while (p != NULL)140 {141 if ((p->dev < dev) || ((p->dev == dev) && (p->block < b)))142 p = p->avl.right;143 else if ((p->dev > dev) || ((p->dev == dev) && (p->block > e)))144 p = p->avl.left;145 else if (p->modified)146 return p;147 else148 {149 if (p->avl.right != NULL)150 *sp++ = p->avl.right;151 p = p->avl.left;152 }153 if ((p == NULL) && (sp > s))154 p = *--sp;155 }156 return p;157 }158 159 static int160 avl_insert(bdbuf_buffer **root, bdbuf_buffer *node)161 {162 bdbuf_buffer **r = root;163 node->avl.left = node->avl.right = NULL;164 while (TRUE)165 {166 bdbuf_buffer *rr = *r;167 if (rr == NULL)168 {169 *r = node;170 return 0;171 }172 else if ((rr->dev < node->dev) || ((rr->dev == node->dev) &&173 (rr->block < node->block)))174 {175 r = &rr->avl.right;176 }177 else if ((rr->dev == node->dev) && (rr->block == node->block))178 {179 return -1;180 }181 else182 {183 r = &rr->avl.left;184 }185 }186 }187 188 static int189 avl_remove(bdbuf_buffer **root, bdbuf_buffer *node)190 {191 bdbuf_buffer **p = root;192 dev_t dev = node->dev;193 blkdev_bnum block = node->block;194 195 while ((*p != NULL) && (*p != node))196 {197 if (((*p)->dev < dev) || (((*p)->dev == dev) && ((*p)->block < block)))198 p = &(*p)->avl.right;199 else200 p = &(*p)->avl.left;201 }202 if (*p == NULL)203 return -1;204 205 *p = node->avl.left;206 while (*p != NULL)207 p = &(*p)->avl.right;208 *p = node->avl.right;209 node->avl.left = node->avl.right = NULL;210 return 0;211 }212 213 #else214 215 111 /* The default maximum height of 32 allows for AVL trees having 216 112 between 5,704,880 and 4,294,967,295 nodes, depending on order of … … 221 117 #endif 222 118 223 224 225 /*226 * avl_cmp_node_node --227 * Compares two avl nodes. Function compares dev/block pairs of228 * the node1 and node2.229 *230 * PARAMETERS:231 * node1 - Pointer to the first node to compare232 * node2 - Pointer to the second node to compare233 *234 * RETURNS:235 * 0 - dev/block of the nodes are equal236 * 1 - dev/block of the second node are less237 * -1 - dev/block of the first node are less238 */239 static inline int240 avl_cmp_node_node(const bdbuf_buffer *const node1,241 const bdbuf_buffer *const node2)242 {243 if (node1->dev < node2->dev)244 return -1;245 else if (node1->dev > node2->dev)246 return +1;247 else if (node1->block < node2->block)248 return -1;249 else if (node1->block > node2->block)250 return +1;251 else252 return 0;253 }254 255 /*256 * avl_cmp_node_pattern -257 * compares the dev/block of the node with specified two.258 *259 * PARAMETERS:260 * node1 - Pointer to the node to compare261 * dev/block - The pattern to compare with262 *263 * RETURNS:264 * 0 - dev/block of the node and specified are equal265 * 1 - dev/block specified are less266 * -1 - dev/block of the first node are less267 *268 */269 static inline int270 avl_cmp_node_pattern(const bdbuf_buffer *const node1,271 dev_t dev,272 blkdev_bnum block)273 {274 if (node1->dev < dev)275 return -1;276 else if (node1->dev > dev)277 return +1;278 else if (node1->block < block)279 return -1;280 else if (node1->block > block)281 return +1;282 else283 return 0;284 }285 286 287 119 /* 288 120 * avl_search -- … … 300 132 avl_search(bdbuf_buffer **root, dev_t dev, blkdev_bnum block) 301 133 { 302 303 134 bdbuf_buffer *p = *root; 135 304 136 while ((p != NULL) && ((p->dev != dev) || (p->block != block))) 305 137 { 306 138 if ((p->dev < dev) || ((p->dev == dev) && (p->block < block))) 307 p = p->avl.link[1]; 139 { 140 p = p->avl.right; 141 } 308 142 else 309 p = p->avl.link[0]; 310 } 143 { 144 p = p->avl.left; 145 } 146 } 147 311 148 return p; 312 149 } 150 313 151 314 152 /* avl_search_for_sync -- … … 327 165 avl_search_for_sync(bdbuf_buffer **root, disk_device *dd) 328 166 { 167 dev_t dev = dd->phys_dev->dev; 168 blkdev_bnum block_start = dd->start; 169 blkdev_bnum block_end = dd->start + dd->size - 1; 170 171 bdbuf_buffer *buf_stack[AVL_MAX_HEIGHT]; 172 bdbuf_buffer **buf_prev = buf_stack; 329 173 bdbuf_buffer *p = *root; 330 bdbuf_buffer *s[AVL_MAX_HEIGHT]; 331 bdbuf_buffer **sp = s; 332 dev_t dev = dd->phys_dev->dev; 333 blkdev_bnum b = dd->start; 334 blkdev_bnum e = b + dd->size - 1; 335 174 336 175 while (p != NULL) 337 176 { 338 if ((p->dev < dev) || ((p->dev == dev) && (p->block < b))) 339 p = p->avl.link[1]; 340 else if ((p->dev > dev) || ((p->dev == dev) && (p->block > e))) 341 p = p->avl.link[0]; 177 if ((p->dev < dev) || ((p->dev == dev) && (p->block < block_start))) 178 { 179 p = p->avl.right; 180 } 181 else if ((p->dev > dev) || ((p->dev == dev) && (p->block > block_end))) 182 { 183 p = p->avl.left; 184 } 342 185 else if (p->modified) 186 { 343 187 return p; 188 } 344 189 else 345 190 { 346 if (p->avl.link[1] != NULL) 347 *sp++ = p->avl.link[1]; 348 p = p->avl.link[0]; 349 } 350 if ((p == NULL) && (sp > s)) 351 p = *--sp; 352 } 191 if (p->avl.right != NULL) 192 { 193 *buf_prev++ = p->avl.right; 194 } 195 p = p->avl.left; 196 } 197 198 if ((p == NULL) && (buf_prev > buf_stack)) 199 { 200 p = *--buf_prev; 201 } 202 } 203 353 204 return p; 354 205 } … … 360 211 * 361 212 * PARAMETERS: 362 * root _addr- Pointer to pointer to the root node213 * root - Pointer to pointer to the root node 363 214 * node - Pointer to the node to add. 364 215 * … … 368 219 */ 369 220 static int 370 avl_insert (bdbuf_buffer **root_addr, bdbuf_buffer *node) 371 { 372 /* Uses Knuth's Algorithm 6.2.3A (balanced tree search and 373 insertion), but caches results of comparisons. In empirical 374 tests this eliminates about 25% of the comparisons seen under 375 random insertions. */ 376 377 /* A1. */ 378 int t_modified = 0; 379 bdbuf_buffer *t; 380 bdbuf_buffer *s, *p, *q, *r; 381 382 bdbuf_buffer *root_link = *root_addr;; 383 384 t = root_link; 385 s = p = t; 386 387 if (s == NULL) 388 { 389 q = t = node; 390 q->avl.link[0] = q->avl.link[1] = NULL; 391 q->avl.bal = 0; 392 *root_addr = t; 221 avl_insert(bdbuf_buffer **root, bdbuf_buffer *node) 222 { 223 dev_t dev = node->dev; 224 blkdev_bnum block = node->block; 225 226 bdbuf_buffer *p = *root; 227 bdbuf_buffer *q, *p1, *p2; 228 bdbuf_buffer *buf_stack[AVL_MAX_HEIGHT]; 229 bdbuf_buffer **buf_prev = buf_stack; 230 231 boolean modified = FALSE; 232 233 if (p == NULL) 234 { 235 *root = node; 236 node->avl.left = NULL; 237 node->avl.right = NULL; 238 node->avl.bal = 0; 393 239 return 0; 394 240 } 395 241 396 for (;;) 397 { 398 /* A2. */ 399 int diff = avl_cmp_node_node(node, p); 400 401 /* A3. */ 402 if (diff < 0) 403 { 404 p->avl.cache = 0; 405 q = p->avl.link[0]; 242 while (p != NULL) 243 { 244 *buf_prev++ = p; 245 246 if ((p->dev < dev) || ((p->dev == dev) && (p->block < block))) 247 { 248 p->avl.cache = 1; 249 q = p->avl.right; 406 250 if (q == NULL) 407 251 { 408 p->avl.link[0] = q = node; 252 q = node; 253 p->avl.right = q = node; 409 254 break; 410 255 } 411 256 } 412 /* A4. */ 413 else 414 if (diff > 0) 415 { 416 p->avl.cache = 1; 417 q = p->avl.link[1]; 418 if (q == NULL) 419 { 420 p->avl.link[1] = q = node; 257 else if ((p->dev != dev) || (p->block != block)) 258 { 259 p->avl.cache = -1; 260 q = p->avl.left; 261 if (q == NULL) 262 { 263 q = node; 264 p->avl.left = q; 265 break; 266 } 267 } 268 else 269 { 270 return -1; 271 } 272 273 p = q; 274 } 275 276 q->avl.left = q->avl.right = NULL; 277 q->avl.bal = 0; 278 modified = TRUE; 279 buf_prev--; 280 281 while (modified) 282 { 283 if (p->avl.cache == -1) 284 { 285 switch (p->avl.bal) 286 { 287 case 1: 288 p->avl.bal = 0; 289 modified = FALSE; 421 290 break; 422 } 291 292 case 0: 293 p->avl.bal = -1; 294 break; 295 296 case -1: 297 p1 = p->avl.left; 298 if (p1->avl.bal == -1) /* simple LL-turn */ 299 { 300 p->avl.left = p1->avl.right; 301 p1->avl.right = p; 302 p->avl.bal = 0; 303 p = p1; 304 } 305 else /* double LR-turn */ 306 { 307 p2 = p1->avl.right; 308 p1->avl.right = p2->avl.left; 309 p2->avl.left = p1; 310 p->avl.left = p2->avl.right; 311 p2->avl.right = p; 312 if (p2->avl.bal == -1) p->avl.bal = +1; else p->avl.bal = 0; 313 if (p2->avl.bal == +1) p1->avl.bal = -1; else p1->avl.bal = 0; 314 p = p2; 315 } 316 p->avl.bal = 0; 317 modified = FALSE; 318 break; 319 320 default: 321 break; 322 } 323 } 324 else 325 { 326 switch (p->avl.bal) 327 { 328 case -1: 329 p->avl.bal = 0; 330 modified = FALSE; 331 break; 332 333 case 0: 334 p->avl.bal = 1; 335 break; 336 337 case 1: 338 p1 = p->avl.right; 339 if (p1->avl.bal == 1) /* simple RR-turn */ 340 { 341 p->avl.right = p1->avl.left; 342 p1->avl.left = p; 343 p->avl.bal = 0; 344 p = p1; 345 } 346 else /* double RL-turn */ 347 { 348 p2 = p1->avl.left; 349 p1->avl.left = p2->avl.right; 350 p2->avl.right = p1; 351 p->avl.right = p2->avl.left; 352 p2->avl.left = p; 353 if (p2->avl.bal == +1) p->avl.bal = -1; else p->avl.bal = 0; 354 if (p2->avl.bal == -1) p1->avl.bal = +1; else p1->avl.bal = 0; 355 p = p2; 356 } 357 p->avl.bal = 0; 358 modified = FALSE; 359 break; 360 361 default: 362 break; 363 } 364 } 365 q = p; 366 if (buf_prev > buf_stack) 367 { 368 p = *--buf_prev; 369 370 if (p->avl.cache == -1) 371 { 372 p->avl.left = q; 423 373 } 424 374 else 425 /* A2. */ 426 { 427 /* 428 * The item found. Nothing changed. Have not to update 429 * root_adr*/ 430 431 return -1; 432 } 433 434 /* A3, A4. */ 435 if (q->avl.bal != 0) 436 { 437 t = p, s = q; 438 t_modified = 1; 439 } 440 p = q; 441 } 442 443 /* A5. */ 444 q->avl.link[0] = q->avl.link[1] = NULL; 445 q->avl.bal = 0; 446 447 /* A6. */ 448 r = p = s->avl.link[(int) s->avl.cache]; 449 while (p != q) 450 { 451 p->avl.bal = p->avl.cache * 2 - 1; 452 p = p->avl.link[(int) p->avl.cache]; 453 } 454 455 /* A7. */ 456 if (s->avl.cache == 0) 457 { 458 /* a = -1. */ 459 if (s->avl.bal == 0) 460 { 461 s->avl.bal = -1; 462 *root_addr = root_link; 463 return 0; 464 } 465 else if (s->avl.bal == +1) 466 { 467 s->avl.bal = 0; 468 *root_addr = root_link; 469 return 0; 470 } 471 472 assert (s->avl.bal == -1); 473 if (r->avl.bal == -1) 474 { 475 /* A8. */ 476 p = r; 477 s->avl.link[0] = r->avl.link[1]; 478 r->avl.link[1] = s; 479 s->avl.bal = r->avl.bal = 0; 375 { 376 p->avl.right = q; 377 } 480 378 } 481 379 else 482 380 { 483 /* A9. */ 484 assert(r->avl.bal == +1); 485 p = r->avl.link[1]; 486 r->avl.link[1] = p->avl.link[0]; 487 p->avl.link[0] = r; 488 s->avl.link[0] = p->avl.link[1]; 489 p->avl.link[1] = s; 490 if (p->avl.bal == -1) 491 s->avl.bal = 1, r->avl.bal = 0; 492 else 493 { 494 if (p->avl.bal == 0) 495 { 496 s->avl.bal = r->avl.bal = 0; 497 } 498 else 499 { 500 assert (p->avl.bal == +1); 501 s->avl.bal = 0, r->avl.bal = -1; 502 } 503 } 504 p->avl.bal = 0; 505 } 506 } 507 else 508 { 509 /* a == +1. */ 510 if (s->avl.bal == 0) 511 { 512 s->avl.bal = 1; 513 *root_addr = root_link; 514 return 0; 515 } 516 else if (s->avl.bal == -1) 517 { 518 s->avl.bal = 0; 519 *root_addr = root_link; 520 return 0; 521 } 522 523 assert(s->avl.bal == +1); 524 if (r->avl.bal == +1) 525 { 526 /* A8. */ 527 p = r; 528 s->avl.link[1] = r->avl.link[0]; 529 r->avl.link[0] = s; 530 s->avl.bal = r->avl.bal = 0; 531 } 532 else 533 { 534 /* A9. */ 535 assert(r->avl.bal == -1); 536 p = r->avl.link[0]; 537 r->avl.link[0] = p->avl.link[1]; 538 p->avl.link[1] = r; 539 s->avl.link[1] = p->avl.link[0]; 540 p->avl.link[0] = s; 541 if (p->avl.bal == +1) 542 { 543 s->avl.bal = -1, r->avl.bal = 0; 544 } 545 else 546 { 547 if (p->avl.bal == 0) 548 { 549 s->avl.bal = r->avl.bal = 0; 550 } 551 else 552 { 553 assert(p->avl.bal == -1); 554 s->avl.bal = 0, r->avl.bal = 1; 555 } 556 } 557 p->avl.bal = 0; 558 } 559 } 560 561 /* A10. */ 562 if (t_modified) 563 { 564 if (s == t->avl.link[1]) 565 t->avl.link[1] = p; 566 else 567 t->avl.link[0] = p; 568 } 569 else 570 { 571 root_link = p; 572 } 573 574 *root_addr = root_link; 381 *root = p; 382 break; 383 } 384 }; 385 575 386 return 0; 576 387 } … … 589 400 */ 590 401 static int 591 avl_remove(bdbuf_buffer **root_addr, const bdbuf_buffer *node) 592 { 593 /* Uses my Algorithm D, which can be found at 594 http://www.msu.edu/user/pfaffben/avl. Algorithm D is based on 595 Knuth's Algorithm 6.2.2D (Tree deletion) and 6.2.3A (Balanced 596 tree search and insertion), as well as the notes on pages 465-466 597 of Vol. 3. */ 598 599 /* D1. */ 600 bdbuf_buffer *pa[AVL_MAX_HEIGHT]; /* Stack P: Nodes. */ 601 char a[AVL_MAX_HEIGHT]; /* Stack P: Bits. */ 602 int k = 1; /* Stack P: Pointer. */ 603 604 bdbuf_buffer **q; 605 bdbuf_buffer *p; 606 607 608 /* 609 * To avoid using unnessary instance of the 'bdbuf_buffer' (as pa[0]) 610 * we will catch all access to pa[0] and use &root_avl instead 611 */ 612 struct bdbuf_avl_node root_avl; 613 614 root_avl.link[0] = *root_addr; 615 root_avl.link[1] = NULL; 616 root_avl.bal = 0; 617 root_avl.cache = 0; 618 619 a[0] = 0; 620 621 p = root_avl.link[0]; 622 623 624 k = 1; 625 626 for (;;) 627 { 628 /* D2. */ 629 int diff; 630 631 if (p == NULL) 632 return -1; 633 634 diff = avl_cmp_node_node(node, p); 635 636 if (diff == 0) 402 avl_remove(bdbuf_buffer **root, const bdbuf_buffer *node) 403 { 404 dev_t dev = node->dev; 405 blkdev_bnum block = node->block; 406 407 bdbuf_buffer *p = *root; 408 bdbuf_buffer *q, *r, *s, *p1, *p2; 409 bdbuf_buffer *buf_stack[AVL_MAX_HEIGHT]; 410 bdbuf_buffer **buf_prev = buf_stack; 411 412 boolean modified = FALSE; 413 414 memset(buf_stack, 0, sizeof(buf_stack)); 415 416 while (p != NULL) 417 { 418 *buf_prev++ = p; 419 420 if ((p->dev < dev) || ((p->dev == dev) && (p->block < block))) 421 { 422 p->avl.cache = 1; 423 p = p->avl.right; 424 } 425 else if ((p->dev != dev) || (p->block != block)) 426 { 427 p->avl.cache = -1; 428 p = p->avl.left; 429 } 430 else 431 { 432 /* node found */ 637 433 break; 638 639 /* D3, D4. */ 640 pa[k] = p; 641 if (diff < 0) 642 { 643 p = p->avl.link[0]; 644 a[k] = 0; 645 } 646 else if (diff > 0) 647 { 648 p = p->avl.link[1]; 649 a[k] = 1; 650 } 651 k++; 652 } 653 654 /* D5. */ 655 if (k == 1) 656 { 657 /* Andron */ 658 q = &root_avl.link[(int) a[k - 1]]; 434 } 435 } 436 437 if (p == NULL) 438 { 439 /* there is no such node */ 440 return -1; 441 } 442 443 q = p; 444 445 buf_prev--; 446 if (buf_prev > buf_stack) 447 { 448 p = *(buf_prev - 1); 659 449 } 660 450 else 661 451 { 662 q = &pa[k - 1]->avl.link[(int) a[k - 1]]; 663 } 664 if (p->avl.link[1] == NULL) 665 { 666 *q = p->avl.link[0]; 667 if (*q) 668 (*q)->avl.bal = 0; 452 p = NULL; 453 } 454 455 /* at this moment q - is a node to delete, p is q's parent */ 456 if (q->avl.right == NULL) 457 { 458 r = q->avl.left; 459 if (r != NULL) 460 { 461 r->avl.bal = 0; 462 } 463 q = r; 669 464 } 670 465 else 671 466 { 672 /* D6. */ 673 bdbuf_buffer *r = p->avl.link[1]; 674 if (r->avl.link[0] == NULL) 675 { 676 r->avl.link[0] = p->avl.link[0]; 677 *q = r; 678 r->avl.bal = p->avl.bal; 679 a[k] = 1; 680 pa[k++] = r; 467 bdbuf_buffer **t; 468 469 r = q->avl.right; 470 471 if (r->avl.left == NULL) 472 { 473 r->avl.left = q->avl.left; 474 r->avl.bal = q->avl.bal; 475 r->avl.cache = 1; 476 *buf_prev++ = q = r; 681 477 } 682 478 else 683 479 { 684 /* D7. */ 685 bdbuf_buffer *s = r->avl.link[0]; 686 int l = k++; 687 688 a[k] = 0; 689 pa[k++] = r; 480 t = buf_prev++; 481 s = r; 690 482 691 /* D8. */ 692 while (s->avl.link[0] != NULL) 693 { 694 r = s; 695 s = r->avl.link[0]; 696 a[k] = 0; 697 pa[k++] = r; 698 } 699 700 /* D9. */ 701 a[l] = 1; 702 pa[l] = s; 703 s->avl.link[0] = p->avl.link[0]; 704 r->avl.link[0] = s->avl.link[1]; 705 s->avl.link[1] = p->avl.link[1]; 706 s->avl.bal = p->avl.bal; 707 *q = s; 708 } 709 } 710 711 assert(k > 0); 712 /* D10. */ 713 while (--k) 714 { 715 bdbuf_buffer *s = pa[k], *r; 716 717 if (a[k] == 0) 718 { 719 /* D10. */ 720 if (s->avl.bal == -1) 721 { 722 s->avl.bal = 0; 723 continue; 724 } 725 else if (s->avl.bal == 0) 726 { 727 s->avl.bal = 1; 728 break; 729 } 730 731 assert(s->avl.bal == +1); 732 r = s->avl.link[1]; 733 734 assert(r != NULL); 735 if (r->avl.bal == 0) 736 { 737 /* D11. */ 738 s->avl.link[1] = r->avl.link[0]; 739 r->avl.link[0] = s; 740 r->avl.bal = -1; 741 if (k == 1) 742 { 743 /* Andron */ 744 root_avl.link[(int) a[k - 1]] = r; 745 } 746 else 747 { 748 pa[k - 1]->avl.link[(int) a[k - 1]] = r; 749 } 750 break; 751 } 752 else 753 if (r->avl.bal == +1) 754 { 755 /* D12. */ 756 s->avl.link[1] = r->avl.link[0]; 757 r->avl.link[0] = s; 758 s->avl.bal = r->avl.bal = 0; 759 if (k == 1) 483 while (s->avl.left != NULL) 484 { 485 *buf_prev++ = r = s; 486 s = r->avl.left; 487 r->avl.cache = -1; 488 } 489 490 s->avl.left = q->avl.left; 491 r->avl.left = s->avl.right; 492 s->avl.right = q->avl.right; 493 s->avl.bal = q->avl.bal; 494 s->avl.cache = 1; 495 496 *t = q = s; 497 } 498 } 499 500 if (p != NULL) 501 { 502 if (p->avl.cache == -1) 503 { 504 p->avl.left = q; 505 } 506 else 507 { 508 p->avl.right = q; 509 } 510 } 511 else 512 { 513 *root = q; 514 } 515 516 modified = TRUE; 517 518 while (modified) 519 { 520 if (buf_prev > buf_stack) 521 { 522 p = *--buf_prev; 523 } 524 else 525 { 526 break; 527 } 528 529 if (p->avl.cache == -1) 530 { 531 /* rebalance left branch */ 532 switch (p->avl.bal) 533 { 534 case -1: 535 p->avl.bal = 0; 536 break; 537 case 0: 538 p->avl.bal = 1; 539 modified = FALSE; 540 break; 541 542 case +1: 543 p1 = p->avl.right; 544 545 if (p1->avl.bal >= 0) /* simple RR-turn */ 760 546 { 761 /* Andron */ 762 root_avl.link[(int) a[k - 1]] = r; 763 } 764 else 765 { 766 pa[k - 1]->avl.link[(int) a[k - 1]] = r; 767 } 768 } 769 else 770 { 771 /* D13. */ 772 assert(r->avl.bal == -1); 773 p = r->avl.link[0]; 774 r->avl.link[0] = p->avl.link[1]; 775 p->avl.link[1] = r; 776 s->avl.link[1] = p->avl.link[0]; 777 p->avl.link[0] = s; 778 if (p->avl.bal == +1) 779 s->avl.bal = -1, r->avl.bal = 0; 780 else if (p->avl.bal == 0) 781 { 782 s->avl.bal = r->avl.bal = 0; 783 } 784 else 785 { 786 assert(p->avl.bal == -1); 787 s->avl.bal = 0, r->avl.bal = +1; 788 } 789 p->avl.bal = 0; 790 if (k == 1) 791 { 792 /* Andron */ 793 root_avl.link[(int) a[k - 1]] = p; 794 } 795 else 796 { 797 pa[k - 1]->avl.link[(int) a[k - 1]] = p; 798 } 799 } 800 } 801 else 802 { 803 assert(a[k] == 1); 804 805 /* D10. */ 806 if (s->avl.bal == +1) 807 { 808 s->avl.bal = 0; 809 continue; 810 } 811 else 812 if (s->avl.bal == 0) 813 { 814 s->avl.bal = -1; 815 break; 816 } 817 818 assert(s->avl.bal == -1); 819 r = s->avl.link[0]; 820 821 if (r == NULL || r->avl.bal == 0) 822 { 823 /* D11. */ 824 s->avl.link[0] = r->avl.link[1]; 825 r->avl.link[1] = s; 826 r->avl.bal = 1; 827 if (k == 1) 828 { 829 /* Andron */ 830 root_avl.link[(int) a[k - 1]] = r; 831 } 832 else 833 { 834 pa[k - 1]->avl.link[(int) a[k - 1]] = r; 835 } 836 837 break; 838 } 839 else 840 if (r->avl.bal == -1) 841 { 842 /* D12. */ 843 s->avl.link[0] = r->avl.link[1]; 844 r->avl.link[1] = s; 845 s->avl.bal = r->avl.bal = 0; 846 if (k == 1) 847 { 848 root_avl.link[(int) a[k - 1]] = r; 849 } 850 else 851 { 852 pa[k - 1]->avl.link[(int) a[k - 1]] = r; 853 } 854 855 } 856 else 857 if (r->avl.bal == +1) 858 { 859 /* D13. */ 860 p = r->avl.link[1]; 861 r->avl.link[1] = p->avl.link[0]; 862 p->avl.link[0] = r; 863 s->avl.link[0] = p->avl.link[1]; 864 p->avl.link[1] = s; 865 if (p->avl.bal == -1) 866 s->avl.bal = 1, r->avl.bal = 0; 867 else 868 if (p->avl.bal == 0) 869 s->avl.bal = r->avl.bal = 0; 870 else 871 { 872 assert(p->avl.bal == 1); 873 s->avl.bal = 0, r->avl.bal = -1; 874 } 875 p->avl.bal = 0; 876 if (k == 1) 547 p->avl.right = p1->avl.left; 548 p1->avl.left = p; 549 550 if (p1->avl.bal == 0) 877 551 { 878 /* Andron */879 root_avl.link[(int) a[k - 1]] = p;552 p1->avl.bal = -1; 553 modified = FALSE; 880 554 } 881 555 else 882 556 { 883 pa[k - 1]->avl.link[(int) a[k - 1]] = p; 557 p->avl.bal = 0; 558 p1->avl.bal = 0; 884 559 } 560 p = p1; 885 561 } 886 } 887 } 888 889 *root_addr = root_avl.link[0]; 562 else /* double RL-turn */ 563 { 564 p2 = p1->avl.left; 565 566 p1->avl.left = p2->avl.right; 567 p2->avl.right = p1; 568 p->avl.right = p2->avl.left; 569 p2->avl.left = p; 570 571 if (p2->avl.bal == +1) p->avl.bal = -1; else p->avl.bal = 0; 572 if (p2->avl.bal == -1) p1->avl.bal = 1; else p1->avl.bal = 0; 573 574 p = p2; 575 p2->avl.bal = 0; 576 } 577 break; 578 579 default: 580 break; 581 } 582 } 583 else 584 { 585 /* rebalance right branch */ 586 switch (p->avl.bal) 587 { 588 case +1: 589 p->avl.bal = 0; 590 break; 591 592 case 0: 593 p->avl.bal = -1; 594 modified = FALSE; 595 break; 596 597 case -1: 598 p1 = p->avl.left; 599 600 if (p1->avl.bal <= 0) /* simple LL-turn */ 601 { 602 p->avl.left = p1->avl.right; 603 p1->avl.right = p; 604 if (p1->avl.bal == 0) 605 { 606 p1->avl.bal = 1; 607 modified = FALSE; 608 } 609 else 610 { 611 p->avl.bal = 0; 612 p1->avl.bal = 0; 613 } 614 p = p1; 615 } 616 else /* double LR-turn */ 617 { 618 p2 = p1->avl.right; 619 620 p1->avl.right = p2->avl.left; 621 p2->avl.left = p1; 622 p->avl.left = p2->avl.right; 623 p2->avl.right = p; 624 625 if (p2->avl.bal == -1) p->avl.bal = 1; else p->avl.bal = 0; 626 if (p2->avl.bal == +1) p1->avl.bal = -1; else p1->avl.bal = 0; 627 628 p = p2; 629 p2->avl.bal = 0; 630 } 631 break; 632 633 default: 634 break; 635 } 636 } 637 638 if (buf_prev > buf_stack) 639 { 640 q = *(buf_prev - 1); 641 642 if (q->avl.cache == -1) 643 { 644 q->avl.left = p; 645 } 646 else 647 { 648 q->avl.right = p; 649 } 650 } 651 else 652 { 653 *root = p; 654 break; 655 } 656 657 } 658 890 659 return 0; 891 660 } 892 893 #endif894 661 895 662 /* bdbuf_initialize_pool -- … … 1182 949 bd_buf->dev = device; 1183 950 bd_buf->block = block; 1184 #ifdef BINARY_TREE 951 #ifdef AVL_GPL 952 bd_buf->avl.link[0] = NULL; 953 bd_buf->avl.link[1] = NULL; 954 #else 1185 955 bd_buf->avl.left = NULL; 1186 956 bd_buf->avl.right = NULL; 1187 #else1188 bd_buf->avl.link[0] = NULL;1189 bd_buf->avl.link[1] = NULL;1190 957 #endif 1191 958 bd_buf->use_count = 1; … … 1242 1009 while (bd_buf->in_progress != 0) 1243 1010 { 1011 rtems_interrupt_disable(level); 1244 1012 _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE, 1245 1013 WATCHDOG_NO_TIMEOUT, level); … … 1460 1228 else 1461 1229 { 1230 rtems_interrupt_disable(level); 1462 1231 _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE, 1463 1232 WATCHDOG_NO_TIMEOUT, level); … … 1651 1420 if (rc == RTEMS_SUCCESSFUL) 1652 1421 { 1422 rtems_interrupt_disable(level); 1653 1423 _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE, 1654 1424 WATCHDOG_NO_TIMEOUT, level); … … 1692 1462 if (bd_buf != NULL /* && bd_buf->modified */) 1693 1463 { 1464 rtems_interrupt_disable(level); 1694 1465 _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE, 1695 1466 WATCHDOG_NO_TIMEOUT, level); … … 1764 1535 if (bd_buf->in_progress) 1765 1536 { 1537 rtems_interrupt_disable(level); 1766 1538 _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE, 0, level); 1767 1539 } -
cpukit/libblock/ChangeLog
rd7478774 rdf6348bb 1 2002-03-21 Alexander Kukuta <kam@oktet.ru> 2 3 * src/bdbuf.c (avl_insert, avl_remove): Reimplemented from scratch 4 to avoid using GPLed sources in RTEMS core. 5 * src/bdbuf.c, include/rtems/bdbuf.h: Remove "binary tree" 6 implementation which was used for debugging only. 7 8 2002-03-13 Victor V. Vengerov <vvv@oktet.ru> 9 10 * src/bdbuf.c (find_or_assign_buffer, rtems_bdbuf_read, 11 rtems_bdbuf_sync, rtems_bdbuf_syncdev, bdbuf_swapout_task): 12 Fix bug: disable interrupts and set level properly before 13 _CORE_mutex_Seize invocation). 14 1 15 2002-02-28 Joel Sherrill <joel@OARcorp.com> 2 16 -
cpukit/libblock/include/rtems/bdbuf.h
rd7478774 rdf6348bb 38 38 Chain_Node link; /* Link in the lru, mod or free chains */ 39 39 40 #ifdef BINARY_TREE41 40 struct bdbuf_avl_node { 42 struct bdbuf_buffer *left; /* link to the left sub-tree */ 43 struct bdbuf_buffer *right; /* link to the right sub-tree */ 44 45 int bf; /* AVL tree node balance factor */ 46 } avl; /* AVL-tree links */ 47 #else /* AVL TREE */ 48 struct bdbuf_avl_node { 49 char cache; /* Cache */ 50 51 struct bdbuf_buffer* link[2]; /* Left and Right Kids */ 52 53 char bal; /* The balance of the sub-tree */ 41 char cache; /* Cache */ 42 43 struct bdbuf_buffer* left; /* Left Child */ 44 struct bdbuf_buffer* right; /* Right Child */ 45 46 char bal; /* The balance of the sub-tree */ 54 47 } avl; 55 #endif 48 56 49 dev_t dev; /* device number */ 57 50 blkdev_bnum block; /* block number on the device */ -
cpukit/libblock/src/bdbuf.c
rd7478774 rdf6348bb 6 6 * Author: Andrey G. Ivanov <Andrey.Ivanov@oktet.ru> 7 7 * Victor V. Vengerov <vvv@oktet.ru> 8 * Alexander Kukuta <kam@oktet.ru> 8 9 * 9 10 * @(#) $Id$ … … 22 23 #define BLKDEV_FATAL_BDBUF_CONSISTENCY BLKDEV_FATAL_ERROR(1) 23 24 #define BLKDEV_FATAL_BDBUF_SWAPOUT BLKDEV_FATAL_ERROR(2) 24 25 enum balance_factor {BF_LEFT = -1,26 BF_NONE = 0,27 BF_RIGHT = 1};28 25 29 26 … … 112 109 113 110 114 #ifdef BINARY_TREE115 static bdbuf_buffer *116 avl_search(bdbuf_buffer **root, dev_t dev, blkdev_bnum block)117 {118 bdbuf_buffer *p = *root;119 while ((p != NULL) && ((p->dev != dev) || (p->block != block)))120 {121 if ((p->dev < dev) || ((p->dev == dev) && (p->block < block)))122 p = p->avl.right;123 else124 p = p->avl.left;125 }126 return p;127 }128 129 static bdbuf_buffer *130 avl_search_for_sync(bdbuf_buffer **root, disk_device *dd)131 {132 bdbuf_buffer *p = *root;133 bdbuf_buffer *s[32];134 bdbuf_buffer **sp = s;135 dev_t dev = dd->phys_dev->dev;136 blkdev_bnum b = dd->start;137 blkdev_bnum e = b + dd->size - 1;138 139 while (p != NULL)140 {141 if ((p->dev < dev) || ((p->dev == dev) && (p->block < b)))142 p = p->avl.right;143 else if ((p->dev > dev) || ((p->dev == dev) && (p->block > e)))144 p = p->avl.left;145 else if (p->modified)146 return p;147 else148 {149 if (p->avl.right != NULL)150 *sp++ = p->avl.right;151 p = p->avl.left;152 }153 if ((p == NULL) && (sp > s))154 p = *--sp;155 }156 return p;157 }158 159 static int160 avl_insert(bdbuf_buffer **root, bdbuf_buffer *node)161 {162 bdbuf_buffer **r = root;163 node->avl.left = node->avl.right = NULL;164 while (TRUE)165 {166 bdbuf_buffer *rr = *r;167 if (rr == NULL)168 {169 *r = node;170 return 0;171 }172 else if ((rr->dev < node->dev) || ((rr->dev == node->dev) &&173 (rr->block < node->block)))174 {175 r = &rr->avl.right;176 }177 else if ((rr->dev == node->dev) && (rr->block == node->block))178 {179 return -1;180 }181 else182 {183 r = &rr->avl.left;184 }185 }186 }187 188 static int189 avl_remove(bdbuf_buffer **root, bdbuf_buffer *node)190 {191 bdbuf_buffer **p = root;192 dev_t dev = node->dev;193 blkdev_bnum block = node->block;194 195 while ((*p != NULL) && (*p != node))196 {197 if (((*p)->dev < dev) || (((*p)->dev == dev) && ((*p)->block < block)))198 p = &(*p)->avl.right;199 else200 p = &(*p)->avl.left;201 }202 if (*p == NULL)203 return -1;204 205 *p = node->avl.left;206 while (*p != NULL)207 p = &(*p)->avl.right;208 *p = node->avl.right;209 node->avl.left = node->avl.right = NULL;210 return 0;211 }212 213 #else214 215 111 /* The default maximum height of 32 allows for AVL trees having 216 112 between 5,704,880 and 4,294,967,295 nodes, depending on order of … … 221 117 #endif 222 118 223 224 225 /*226 * avl_cmp_node_node --227 * Compares two avl nodes. Function compares dev/block pairs of228 * the node1 and node2.229 *230 * PARAMETERS:231 * node1 - Pointer to the first node to compare232 * node2 - Pointer to the second node to compare233 *234 * RETURNS:235 * 0 - dev/block of the nodes are equal236 * 1 - dev/block of the second node are less237 * -1 - dev/block of the first node are less238 */239 static inline int240 avl_cmp_node_node(const bdbuf_buffer *const node1,241 const bdbuf_buffer *const node2)242 {243 if (node1->dev < node2->dev)244 return -1;245 else if (node1->dev > node2->dev)246 return +1;247 else if (node1->block < node2->block)248 return -1;249 else if (node1->block > node2->block)250 return +1;251 else252 return 0;253 }254 255 /*256 * avl_cmp_node_pattern -257 * compares the dev/block of the node with specified two.258 *259 * PARAMETERS:260 * node1 - Pointer to the node to compare261 * dev/block - The pattern to compare with262 *263 * RETURNS:264 * 0 - dev/block of the node and specified are equal265 * 1 - dev/block specified are less266 * -1 - dev/block of the first node are less267 *268 */269 static inline int270 avl_cmp_node_pattern(const bdbuf_buffer *const node1,271 dev_t dev,272 blkdev_bnum block)273 {274 if (node1->dev < dev)275 return -1;276 else if (node1->dev > dev)277 return +1;278 else if (node1->block < block)279 return -1;280 else if (node1->block > block)281 return +1;282 else283 return 0;284 }285 286 287 119 /* 288 120 * avl_search -- … … 300 132 avl_search(bdbuf_buffer **root, dev_t dev, blkdev_bnum block) 301 133 { 302 303 134 bdbuf_buffer *p = *root; 135 304 136 while ((p != NULL) && ((p->dev != dev) || (p->block != block))) 305 137 { 306 138 if ((p->dev < dev) || ((p->dev == dev) && (p->block < block))) 307 p = p->avl.link[1]; 139 { 140 p = p->avl.right; 141 } 308 142 else 309 p = p->avl.link[0]; 310 } 143 { 144 p = p->avl.left; 145 } 146 } 147 311 148 return p; 312 149 } 150 313 151 314 152 /* avl_search_for_sync -- … … 327 165 avl_search_for_sync(bdbuf_buffer **root, disk_device *dd) 328 166 { 167 dev_t dev = dd->phys_dev->dev; 168 blkdev_bnum block_start = dd->start; 169 blkdev_bnum block_end = dd->start + dd->size - 1; 170 171 bdbuf_buffer *buf_stack[AVL_MAX_HEIGHT]; 172 bdbuf_buffer **buf_prev = buf_stack; 329 173 bdbuf_buffer *p = *root; 330 bdbuf_buffer *s[AVL_MAX_HEIGHT]; 331 bdbuf_buffer **sp = s; 332 dev_t dev = dd->phys_dev->dev; 333 blkdev_bnum b = dd->start; 334 blkdev_bnum e = b + dd->size - 1; 335 174 336 175 while (p != NULL) 337 176 { 338 if ((p->dev < dev) || ((p->dev == dev) && (p->block < b))) 339 p = p->avl.link[1]; 340 else if ((p->dev > dev) || ((p->dev == dev) && (p->block > e))) 341 p = p->avl.link[0]; 177 if ((p->dev < dev) || ((p->dev == dev) && (p->block < block_start))) 178 { 179 p = p->avl.right; 180 } 181 else if ((p->dev > dev) || ((p->dev == dev) && (p->block > block_end))) 182 { 183 p = p->avl.left; 184 } 342 185 else if (p->modified) 186 { 343 187 return p; 188 } 344 189 else 345 190 { 346 if (p->avl.link[1] != NULL) 347 *sp++ = p->avl.link[1]; 348 p = p->avl.link[0]; 349 } 350 if ((p == NULL) && (sp > s)) 351 p = *--sp; 352 } 191 if (p->avl.right != NULL) 192 { 193 *buf_prev++ = p->avl.right; 194 } 195 p = p->avl.left; 196 } 197 198 if ((p == NULL) && (buf_prev > buf_stack)) 199 { 200 p = *--buf_prev; 201 } 202 } 203 353 204 return p; 354 205 } … … 360 211 * 361 212 * PARAMETERS: 362 * root _addr- Pointer to pointer to the root node213 * root - Pointer to pointer to the root node 363 214 * node - Pointer to the node to add. 364 215 * … … 368 219 */ 369 220 static int 370 avl_insert (bdbuf_buffer **root_addr, bdbuf_buffer *node) 371 { 372 /* Uses Knuth's Algorithm 6.2.3A (balanced tree search and 373 insertion), but caches results of comparisons. In empirical 374 tests this eliminates about 25% of the comparisons seen under 375 random insertions. */ 376 377 /* A1. */ 378 int t_modified = 0; 379 bdbuf_buffer *t; 380 bdbuf_buffer *s, *p, *q, *r; 381 382 bdbuf_buffer *root_link = *root_addr;; 383 384 t = root_link; 385 s = p = t; 386 387 if (s == NULL) 388 { 389 q = t = node; 390 q->avl.link[0] = q->avl.link[1] = NULL; 391 q->avl.bal = 0; 392 *root_addr = t; 221 avl_insert(bdbuf_buffer **root, bdbuf_buffer *node) 222 { 223 dev_t dev = node->dev; 224 blkdev_bnum block = node->block; 225 226 bdbuf_buffer *p = *root; 227 bdbuf_buffer *q, *p1, *p2; 228 bdbuf_buffer *buf_stack[AVL_MAX_HEIGHT]; 229 bdbuf_buffer **buf_prev = buf_stack; 230 231 boolean modified = FALSE; 232 233 if (p == NULL) 234 { 235 *root = node; 236 node->avl.left = NULL; 237 node->avl.right = NULL; 238 node->avl.bal = 0; 393 239 return 0; 394 240 } 395 241 396 for (;;) 397 { 398 /* A2. */ 399 int diff = avl_cmp_node_node(node, p); 400 401 /* A3. */ 402 if (diff < 0) 403 { 404 p->avl.cache = 0; 405 q = p->avl.link[0]; 242 while (p != NULL) 243 { 244 *buf_prev++ = p; 245 246 if ((p->dev < dev) || ((p->dev == dev) && (p->block < block))) 247 { 248 p->avl.cache = 1; 249 q = p->avl.right; 406 250 if (q == NULL) 407 251 { 408 p->avl.link[0] = q = node; 252 q = node; 253 p->avl.right = q = node; 409 254 break; 410 255 } 411 256 } 412 /* A4. */ 413 else 414 if (diff > 0) 415 { 416 p->avl.cache = 1; 417 q = p->avl.link[1]; 418 if (q == NULL) 419 { 420 p->avl.link[1] = q = node; 257 else if ((p->dev != dev) || (p->block != block)) 258 { 259 p->avl.cache = -1; 260 q = p->avl.left; 261 if (q == NULL) 262 { 263 q = node; 264 p->avl.left = q; 265 break; 266 } 267 } 268 else 269 { 270 return -1; 271 } 272 273 p = q; 274 } 275 276 q->avl.left = q->avl.right = NULL; 277 q->avl.bal = 0; 278 modified = TRUE; 279 buf_prev--; 280 281 while (modified) 282 { 283 if (p->avl.cache == -1) 284 { 285 switch (p->avl.bal) 286 { 287 case 1: 288 p->avl.bal = 0; 289 modified = FALSE; 421 290 break; 422 } 291 292 case 0: 293 p->avl.bal = -1; 294 break; 295 296 case -1: 297 p1 = p->avl.left; 298 if (p1->avl.bal == -1) /* simple LL-turn */ 299 { 300 p->avl.left = p1->avl.right; 301 p1->avl.right = p; 302 p->avl.bal = 0; 303 p = p1; 304 } 305 else /* double LR-turn */ 306 { 307 p2 = p1->avl.right; 308 p1->avl.right = p2->avl.left; 309 p2->avl.left = p1; 310 p->avl.left = p2->avl.right; 311 p2->avl.right = p; 312 if (p2->avl.bal == -1) p->avl.bal = +1; else p->avl.bal = 0; 313 if (p2->avl.bal == +1) p1->avl.bal = -1; else p1->avl.bal = 0; 314 p = p2; 315 } 316 p->avl.bal = 0; 317 modified = FALSE; 318 break; 319 320 default: 321 break; 322 } 323 } 324 else 325 { 326 switch (p->avl.bal) 327 { 328 case -1: 329 p->avl.bal = 0; 330 modified = FALSE; 331 break; 332 333 case 0: 334 p->avl.bal = 1; 335 break; 336 337 case 1: 338 p1 = p->avl.right; 339 if (p1->avl.bal == 1) /* simple RR-turn */ 340 { 341 p->avl.right = p1->avl.left; 342 p1->avl.left = p; 343 p->avl.bal = 0; 344 p = p1; 345 } 346 else /* double RL-turn */ 347 { 348 p2 = p1->avl.left; 349 p1->avl.left = p2->avl.right; 350 p2->avl.right = p1; 351 p->avl.right = p2->avl.left; 352 p2->avl.left = p; 353 if (p2->avl.bal == +1) p->avl.bal = -1; else p->avl.bal = 0; 354 if (p2->avl.bal == -1) p1->avl.bal = +1; else p1->avl.bal = 0; 355 p = p2; 356 } 357 p->avl.bal = 0; 358 modified = FALSE; 359 break; 360 361 default: 362 break; 363 } 364 } 365 q = p; 366 if (buf_prev > buf_stack) 367 { 368 p = *--buf_prev; 369 370 if (p->avl.cache == -1) 371 { 372 p->avl.left = q; 423 373 } 424 374 else 425 /* A2. */ 426 { 427 /* 428 * The item found. Nothing changed. Have not to update 429 * root_adr*/ 430 431 return -1; 432 } 433 434 /* A3, A4. */ 435 if (q->avl.bal != 0) 436 { 437 t = p, s = q; 438 t_modified = 1; 439 } 440 p = q; 441 } 442 443 /* A5. */ 444 q->avl.link[0] = q->avl.link[1] = NULL; 445 q->avl.bal = 0; 446 447 /* A6. */ 448 r = p = s->avl.link[(int) s->avl.cache]; 449 while (p != q) 450 { 451 p->avl.bal = p->avl.cache * 2 - 1; 452 p = p->avl.link[(int) p->avl.cache]; 453 } 454 455 /* A7. */ 456 if (s->avl.cache == 0) 457 { 458 /* a = -1. */ 459 if (s->avl.bal == 0) 460 { 461 s->avl.bal = -1; 462 *root_addr = root_link; 463 return 0; 464 } 465 else if (s->avl.bal == +1) 466 { 467 s->avl.bal = 0; 468 *root_addr = root_link; 469 return 0; 470 } 471 472 assert (s->avl.bal == -1); 473 if (r->avl.bal == -1) 474 { 475 /* A8. */ 476 p = r; 477 s->avl.link[0] = r->avl.link[1]; 478 r->avl.link[1] = s; 479 s->avl.bal = r->avl.bal = 0; 375 { 376 p->avl.right = q; 377 } 480 378 } 481 379 else 482 380 { 483 /* A9. */ 484 assert(r->avl.bal == +1); 485 p = r->avl.link[1]; 486 r->avl.link[1] = p->avl.link[0]; 487 p->avl.link[0] = r; 488 s->avl.link[0] = p->avl.link[1]; 489 p->avl.link[1] = s; 490 if (p->avl.bal == -1) 491 s->avl.bal = 1, r->avl.bal = 0; 492 else 493 { 494 if (p->avl.bal == 0) 495 { 496 s->avl.bal = r->avl.bal = 0; 497 } 498 else 499 { 500 assert (p->avl.bal == +1); 501 s->avl.bal = 0, r->avl.bal = -1; 502 } 503 } 504 p->avl.bal = 0; 505 } 506 } 507 else 508 { 509 /* a == +1. */ 510 if (s->avl.bal == 0) 511 { 512 s->avl.bal = 1; 513 *root_addr = root_link; 514 return 0; 515 } 516 else if (s->avl.bal == -1) 517 { 518 s->avl.bal = 0; 519 *root_addr = root_link; 520 return 0; 521 } 522 523 assert(s->avl.bal == +1); 524 if (r->avl.bal == +1) 525 { 526 /* A8. */ 527 p = r; 528 s->avl.link[1] = r->avl.link[0]; 529 r->avl.link[0] = s; 530 s->avl.bal = r->avl.bal = 0; 531 } 532 else 533 { 534 /* A9. */ 535 assert(r->avl.bal == -1); 536 p = r->avl.link[0]; 537 r->avl.link[0] = p->avl.link[1]; 538 p->avl.link[1] = r; 539 s->avl.link[1] = p->avl.link[0]; 540 p->avl.link[0] = s; 541 if (p->avl.bal == +1) 542 { 543 s->avl.bal = -1, r->avl.bal = 0; 544 } 545 else 546 { 547 if (p->avl.bal == 0) 548 { 549 s->avl.bal = r->avl.bal = 0; 550 } 551 else 552 { 553 assert(p->avl.bal == -1); 554 s->avl.bal = 0, r->avl.bal = 1; 555 } 556 } 557 p->avl.bal = 0; 558 } 559 } 560 561 /* A10. */ 562 if (t_modified) 563 { 564 if (s == t->avl.link[1]) 565 t->avl.link[1] = p; 566 else 567 t->avl.link[0] = p; 568 } 569 else 570 { 571 root_link = p; 572 } 573 574 *root_addr = root_link; 381 *root = p; 382 break; 383 } 384 }; 385 575 386 return 0; 576 387 } … … 589 400 */ 590 401 static int 591 avl_remove(bdbuf_buffer **root_addr, const bdbuf_buffer *node) 592 { 593 /* Uses my Algorithm D, which can be found at 594 http://www.msu.edu/user/pfaffben/avl. Algorithm D is based on 595 Knuth's Algorithm 6.2.2D (Tree deletion) and 6.2.3A (Balanced 596 tree search and insertion), as well as the notes on pages 465-466 597 of Vol. 3. */ 598 599 /* D1. */ 600 bdbuf_buffer *pa[AVL_MAX_HEIGHT]; /* Stack P: Nodes. */ 601 char a[AVL_MAX_HEIGHT]; /* Stack P: Bits. */ 602 int k = 1; /* Stack P: Pointer. */ 603 604 bdbuf_buffer **q; 605 bdbuf_buffer *p; 606 607 608 /* 609 * To avoid using unnessary instance of the 'bdbuf_buffer' (as pa[0]) 610 * we will catch all access to pa[0] and use &root_avl instead 611 */ 612 struct bdbuf_avl_node root_avl; 613 614 root_avl.link[0] = *root_addr; 615 root_avl.link[1] = NULL; 616 root_avl.bal = 0; 617 root_avl.cache = 0; 618 619 a[0] = 0; 620 621 p = root_avl.link[0]; 622 623 624 k = 1; 625 626 for (;;) 627 { 628 /* D2. */ 629 int diff; 630 631 if (p == NULL) 632 return -1; 633 634 diff = avl_cmp_node_node(node, p); 635 636 if (diff == 0) 402 avl_remove(bdbuf_buffer **root, const bdbuf_buffer *node) 403 { 404 dev_t dev = node->dev; 405 blkdev_bnum block = node->block; 406 407 bdbuf_buffer *p = *root; 408 bdbuf_buffer *q, *r, *s, *p1, *p2; 409 bdbuf_buffer *buf_stack[AVL_MAX_HEIGHT]; 410 bdbuf_buffer **buf_prev = buf_stack; 411 412 boolean modified = FALSE; 413 414 memset(buf_stack, 0, sizeof(buf_stack)); 415 416 while (p != NULL) 417 { 418 *buf_prev++ = p; 419 420 if ((p->dev < dev) || ((p->dev == dev) && (p->block < block))) 421 { 422 p->avl.cache = 1; 423 p = p->avl.right; 424 } 425 else if ((p->dev != dev) || (p->block != block)) 426 { 427 p->avl.cache = -1; 428 p = p->avl.left; 429 } 430 else 431 { 432 /* node found */ 637 433 break; 638 639 /* D3, D4. */ 640 pa[k] = p; 641 if (diff < 0) 642 { 643 p = p->avl.link[0]; 644 a[k] = 0; 645 } 646 else if (diff > 0) 647 { 648 p = p->avl.link[1]; 649 a[k] = 1; 650 } 651 k++; 652 } 653 654 /* D5. */ 655 if (k == 1) 656 { 657 /* Andron */ 658 q = &root_avl.link[(int) a[k - 1]]; 434 } 435 } 436 437 if (p == NULL) 438 { 439 /* there is no such node */ 440 return -1; 441 } 442 443 q = p; 444 445 buf_prev--; 446 if (buf_prev > buf_stack) 447 { 448 p = *(buf_prev - 1); 659 449 } 660 450 else 661 451 { 662 q = &pa[k - 1]->avl.link[(int) a[k - 1]]; 663 } 664 if (p->avl.link[1] == NULL) 665 { 666 *q = p->avl.link[0]; 667 if (*q) 668 (*q)->avl.bal = 0; 452 p = NULL; 453 } 454 455 /* at this moment q - is a node to delete, p is q's parent */ 456 if (q->avl.right == NULL) 457 { 458 r = q->avl.left; 459 if (r != NULL) 460 { 461 r->avl.bal = 0; 462 } 463 q = r; 669 464 } 670 465 else 671 466 { 672 /* D6. */ 673 bdbuf_buffer *r = p->avl.link[1]; 674 if (r->avl.link[0] == NULL) 675 { 676 r->avl.link[0] = p->avl.link[0]; 677 *q = r; 678 r->avl.bal = p->avl.bal; 679 a[k] = 1; 680 pa[k++] = r; 467 bdbuf_buffer **t; 468 469 r = q->avl.right; 470 471 if (r->avl.left == NULL) 472 { 473 r->avl.left = q->avl.left; 474 r->avl.bal = q->avl.bal; 475 r->avl.cache = 1; 476 *buf_prev++ = q = r; 681 477 } 682 478 else 683 479 { 684 /* D7. */ 685 bdbuf_buffer *s = r->avl.link[0]; 686 int l = k++; 687 688 a[k] = 0; 689 pa[k++] = r; 480 t = buf_prev++; 481 s = r; 690 482 691 /* D8. */ 692 while (s->avl.link[0] != NULL) 693 { 694 r = s; 695 s = r->avl.link[0]; 696 a[k] = 0; 697 pa[k++] = r; 698 } 699 700 /* D9. */ 701 a[l] = 1; 702 pa[l] = s; 703 s->avl.link[0] = p->avl.link[0]; 704 r->avl.link[0] = s->avl.link[1]; 705 s->avl.link[1] = p->avl.link[1]; 706 s->avl.bal = p->avl.bal; 707 *q = s; 708 } 709 } 710 711 assert(k > 0); 712 /* D10. */ 713 while (--k) 714 { 715 bdbuf_buffer *s = pa[k], *r; 716 717 if (a[k] == 0) 718 { 719 /* D10. */ 720 if (s->avl.bal == -1) 721 { 722 s->avl.bal = 0; 723 continue; 724 } 725 else if (s->avl.bal == 0) 726 { 727 s->avl.bal = 1; 728 break; 729 } 730 731 assert(s->avl.bal == +1); 732 r = s->avl.link[1]; 733 734 assert(r != NULL); 735 if (r->avl.bal == 0) 736 { 737 /* D11. */ 738 s->avl.link[1] = r->avl.link[0]; 739 r->avl.link[0] = s; 740 r->avl.bal = -1; 741 if (k == 1) 742 { 743 /* Andron */ 744 root_avl.link[(int) a[k - 1]] = r; 745 } 746 else 747 { 748 pa[k - 1]->avl.link[(int) a[k - 1]] = r; 749 } 750 break; 751 } 752 else 753 if (r->avl.bal == +1) 754 { 755 /* D12. */ 756 s->avl.link[1] = r->avl.link[0]; 757 r->avl.link[0] = s; 758 s->avl.bal = r->avl.bal = 0; 759 if (k == 1) 483 while (s->avl.left != NULL) 484 { 485 *buf_prev++ = r = s; 486 s = r->avl.left; 487 r->avl.cache = -1; 488 } 489 490 s->avl.left = q->avl.left; 491 r->avl.left = s->avl.right; 492 s->avl.right = q->avl.right; 493 s->avl.bal = q->avl.bal; 494 s->avl.cache = 1; 495 496 *t = q = s; 497 } 498 } 499 500 if (p != NULL) 501 { 502 if (p->avl.cache == -1) 503 { 504 p->avl.left = q; 505 } 506 else 507 { 508 p->avl.right = q; 509 } 510 } 511 else 512 { 513 *root = q; 514 } 515 516 modified = TRUE; 517 518 while (modified) 519 { 520 if (buf_prev > buf_stack) 521 { 522 p = *--buf_prev; 523 } 524 else 525 { 526 break; 527 } 528 529 if (p->avl.cache == -1) 530 { 531 /* rebalance left branch */ 532 switch (p->avl.bal) 533 { 534 case -1: 535 p->avl.bal = 0; 536 break; 537 case 0: 538 p->avl.bal = 1; 539 modified = FALSE; 540 break; 541 542 case +1: 543 p1 = p->avl.right; 544 545 if (p1->avl.bal >= 0) /* simple RR-turn */ 760 546 { 761 /* Andron */ 762 root_avl.link[(int) a[k - 1]] = r; 763 } 764 else 765 { 766 pa[k - 1]->avl.link[(int) a[k - 1]] = r; 767 } 768 } 769 else 770 { 771 /* D13. */ 772 assert(r->avl.bal == -1); 773 p = r->avl.link[0]; 774 r->avl.link[0] = p->avl.link[1]; 775 p->avl.link[1] = r; 776 s->avl.link[1] = p->avl.link[0]; 777 p->avl.link[0] = s; 778 if (p->avl.bal == +1) 779 s->avl.bal = -1, r->avl.bal = 0; 780 else if (p->avl.bal == 0) 781 { 782 s->avl.bal = r->avl.bal = 0; 783 } 784 else 785 { 786 assert(p->avl.bal == -1); 787 s->avl.bal = 0, r->avl.bal = +1; 788 } 789 p->avl.bal = 0; 790 if (k == 1) 791 { 792 /* Andron */ 793 root_avl.link[(int) a[k - 1]] = p; 794 } 795 else 796 { 797 pa[k - 1]->avl.link[(int) a[k - 1]] = p; 798 } 799 } 800 } 801 else 802 { 803 assert(a[k] == 1); 804 805 /* D10. */ 806 if (s->avl.bal == +1) 807 { 808 s->avl.bal = 0; 809 continue; 810 } 811 else 812 if (s->avl.bal == 0) 813 { 814 s->avl.bal = -1; 815 break; 816 } 817 818 assert(s->avl.bal == -1); 819 r = s->avl.link[0]; 820 821 if (r == NULL || r->avl.bal == 0) 822 { 823 /* D11. */ 824 s->avl.link[0] = r->avl.link[1]; 825 r->avl.link[1] = s; 826 r->avl.bal = 1; 827 if (k == 1) 828 { 829 /* Andron */ 830 root_avl.link[(int) a[k - 1]] = r; 831 } 832 else 833 { 834 pa[k - 1]->avl.link[(int) a[k - 1]] = r; 835 } 836 837 break; 838 } 839 else 840 if (r->avl.bal == -1) 841 { 842 /* D12. */ 843 s->avl.link[0] = r->avl.link[1]; 844 r->avl.link[1] = s; 845 s->avl.bal = r->avl.bal = 0; 846 if (k == 1) 847 { 848 root_avl.link[(int) a[k - 1]] = r; 849 } 850 else 851 { 852 pa[k - 1]->avl.link[(int) a[k - 1]] = r; 853 } 854 855 } 856 else 857 if (r->avl.bal == +1) 858 { 859 /* D13. */ 860 p = r->avl.link[1]; 861 r->avl.link[1] = p->avl.link[0]; 862 p->avl.link[0] = r; 863 s->avl.link[0] = p->avl.link[1]; 864 p->avl.link[1] = s; 865 if (p->avl.bal == -1) 866 s->avl.bal = 1, r->avl.bal = 0; 867 else 868 if (p->avl.bal == 0) 869 s->avl.bal = r->avl.bal = 0; 870 else 871 { 872 assert(p->avl.bal == 1); 873 s->avl.bal = 0, r->avl.bal = -1; 874 } 875 p->avl.bal = 0; 876 if (k == 1) 547 p->avl.right = p1->avl.left; 548 p1->avl.left = p; 549 550 if (p1->avl.bal == 0) 877 551 { 878 /* Andron */879 root_avl.link[(int) a[k - 1]] = p;552 p1->avl.bal = -1; 553 modified = FALSE; 880 554 } 881 555 else 882 556 { 883 pa[k - 1]->avl.link[(int) a[k - 1]] = p; 557 p->avl.bal = 0; 558 p1->avl.bal = 0; 884 559 } 560 p = p1; 885 561 } 886 } 887 } 888 889 *root_addr = root_avl.link[0]; 562 else /* double RL-turn */ 563 { 564 p2 = p1->avl.left; 565 566 p1->avl.left = p2->avl.right; 567 p2->avl.right = p1; 568 p->avl.right = p2->avl.left; 569 p2->avl.left = p; 570 571 if (p2->avl.bal == +1) p->avl.bal = -1; else p->avl.bal = 0; 572 if (p2->avl.bal == -1) p1->avl.bal = 1; else p1->avl.bal = 0; 573 574 p = p2; 575 p2->avl.bal = 0; 576 } 577 break; 578 579 default: 580 break; 581 } 582 } 583 else 584 { 585 /* rebalance right branch */ 586 switch (p->avl.bal) 587 { 588 case +1: 589 p->avl.bal = 0; 590 break; 591 592 case 0: 593 p->avl.bal = -1; 594 modified = FALSE; 595 break; 596 597 case -1: 598 p1 = p->avl.left; 599 600 if (p1->avl.bal <= 0) /* simple LL-turn */ 601 { 602 p->avl.left = p1->avl.right; 603 p1->avl.right = p; 604 if (p1->avl.bal == 0) 605 { 606 p1->avl.bal = 1; 607 modified = FALSE; 608 } 609 else 610 { 611 p->avl.bal = 0; 612 p1->avl.bal = 0; 613 } 614 p = p1; 615 } 616 else /* double LR-turn */ 617 { 618 p2 = p1->avl.right; 619 620 p1->avl.right = p2->avl.left; 621 p2->avl.left = p1; 622 p->avl.left = p2->avl.right; 623 p2->avl.right = p; 624 625 if (p2->avl.bal == -1) p->avl.bal = 1; else p->avl.bal = 0; 626 if (p2->avl.bal == +1) p1->avl.bal = -1; else p1->avl.bal = 0; 627 628 p = p2; 629 p2->avl.bal = 0; 630 } 631 break; 632 633 default: 634 break; 635 } 636 } 637 638 if (buf_prev > buf_stack) 639 { 640 q = *(buf_prev - 1); 641 642 if (q->avl.cache == -1) 643 { 644 q->avl.left = p; 645 } 646 else 647 { 648 q->avl.right = p; 649 } 650 } 651 else 652 { 653 *root = p; 654 break; 655 } 656 657 } 658 890 659 return 0; 891 660 } 892 893 #endif894 661 895 662 /* bdbuf_initialize_pool -- … … 1182 949 bd_buf->dev = device; 1183 950 bd_buf->block = block; 1184 #ifdef BINARY_TREE 951 #ifdef AVL_GPL 952 bd_buf->avl.link[0] = NULL; 953 bd_buf->avl.link[1] = NULL; 954 #else 1185 955 bd_buf->avl.left = NULL; 1186 956 bd_buf->avl.right = NULL; 1187 #else1188 bd_buf->avl.link[0] = NULL;1189 bd_buf->avl.link[1] = NULL;1190 957 #endif 1191 958 bd_buf->use_count = 1; … … 1242 1009 while (bd_buf->in_progress != 0) 1243 1010 { 1011 rtems_interrupt_disable(level); 1244 1012 _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE, 1245 1013 WATCHDOG_NO_TIMEOUT, level); … … 1460 1228 else 1461 1229 { 1230 rtems_interrupt_disable(level); 1462 1231 _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE, 1463 1232 WATCHDOG_NO_TIMEOUT, level); … … 1651 1420 if (rc == RTEMS_SUCCESSFUL) 1652 1421 { 1422 rtems_interrupt_disable(level); 1653 1423 _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE, 1654 1424 WATCHDOG_NO_TIMEOUT, level); … … 1692 1462 if (bd_buf != NULL /* && bd_buf->modified */) 1693 1463 { 1464 rtems_interrupt_disable(level); 1694 1465 _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE, 1695 1466 WATCHDOG_NO_TIMEOUT, level); … … 1764 1535 if (bd_buf->in_progress) 1765 1536 { 1537 rtems_interrupt_disable(level); 1766 1538 _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE, 0, level); 1767 1539 }
Note: See TracChangeset
for help on using the changeset viewer.