Changeset df6348bb in rtems


Ignore:
Timestamp:
03/21/02 14:05:57 (20 years ago)
Author:
Joel Sherrill <joel.sherrill@…>
Branches:
4.10, 4.11, 4.8, 4.9, 5, master
Children:
fd55b7d
Parents:
d7478774
Message:

2002-03-21 Alexander Kukuta <kam@…>

  • src/bdbuf.c (avl_insert, avl_remove): Reimplemented from scratch to avoid using GPLed sources in RTEMS core.
  • src/bdbuf.c, include/rtems/bdbuf.h: Remove "binary tree" implementation which was used for debugging only.
Files:
9 edited

Legend:

Unmodified
Added
Removed

  • c/src/exec/libblock/ChangeLog

    rd7478774 rdf6348bb  
     12002-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
     82002-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
    1152002-02-28      Joel Sherrill <joel@OARcorp.com>
    216

  • c/src/exec/libblock/include/rtems/bdbuf.h

    rd7478774 rdf6348bb  
    3838    Chain_Node link; /* Link in the lru, mod or free chains */
    3939
    40 #ifdef BINARY_TREE
    4140    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 */
    5447    } avl;
    55 #endif
     48
    5649    dev_t       dev;     /* device number */
    5750    blkdev_bnum block;   /* block number on the device */

  • c/src/exec/libblock/src/bdbuf.c

    rd7478774 rdf6348bb  
    66 * Author: Andrey G. Ivanov <Andrey.Ivanov@oktet.ru>
    77 *         Victor V. Vengerov <vvv@oktet.ru>
     8 *         Alexander Kukuta <kam@oktet.ru>
    89 *
    910 * @(#) $Id$
    … …  
    2223#define BLKDEV_FATAL_BDBUF_CONSISTENCY BLKDEV_FATAL_ERROR(1)
    2324#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};
    2825
    2926
    … …  
    112109
    113110
    114 #ifdef BINARY_TREE
    115 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         else
    124             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         else
    148         {
    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 int
    160 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         else
    182         {
    183             r = &rr->avl.left;
    184         }
    185     }
    186 }
    187 
    188 static int
    189 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         else
    200             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 #else
    214 
    215111/* The default maximum height of 32 allows for AVL trees having
    216112   between 5,704,880 and 4,294,967,295 nodes, depending on order of
    … …  
    221117#endif
    222118
    223 
    224 
    225 /*
    226  * avl_cmp_node_node --
    227  *     Compares two avl nodes. Function compares dev/block pairs of
    228  *     the node1 and node2.
    229  *
    230  * PARAMETERS:
    231  *     node1 - Pointer to the first node to compare
    232  *     node2 - Pointer to the second node to compare
    233  *
    234  * RETURNS:
    235  *     0 - dev/block of the nodes are equal
    236  *     1 - dev/block of the second node are less
    237  *    -1 - dev/block of the first node are less
    238  */
    239 static inline int
    240 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     else
    252         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 compare
    261  *     dev/block - The pattern to compare with
    262  *
    263  * RETURNS:
    264  *     0 - dev/block of the node and specified are equal
    265  *     1 - dev/block specified are less
    266  *    -1 - dev/block of the first node are less
    267  *
    268  */
    269 static inline int
    270 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     else
    283         return 0;
    284 }
    285 
    286 
    287119/*
    288120 * avl_search --
    … …  
    300132avl_search(bdbuf_buffer **root, dev_t dev, blkdev_bnum block)
    301133{
    302 
    303134    bdbuf_buffer *p = *root;
     135
    304136    while ((p != NULL) && ((p->dev != dev) || (p->block != block)))
    305137    {
    306138        if ((p->dev < dev) || ((p->dev == dev) && (p->block < block)))
    307             p = p->avl.link[1];
     139        {
     140            p = p->avl.right;
     141        }
    308142        else
    309             p = p->avl.link[0];
    310     }
     143        {
     144            p = p->avl.left;
     145        }
     146    }
     147   
    311148    return p;
    312149}
     150
    313151
    314152/* avl_search_for_sync --
    … …  
    327165avl_search_for_sync(bdbuf_buffer **root, disk_device *dd)
    328166{
     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;
    329173    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
    336175    while (p != NULL)
    337176    {
    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        }
    342185        else if (p->modified)
     186        {
    343187            return p;
     188        }
    344189        else
    345190        {
    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
    353204    return p;
    354205}
    … …  
    360211 *
    361212 * PARAMETERS:
    362  *     root_addr - Pointer to pointer to the root node
     213 *     root - Pointer to pointer to the root node
    363214 *     node - Pointer to the node to add.
    364215 *
    … …  
    368219 */
    369220static 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;
     221avl_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;
    393239        return 0;
    394240    }
    395241
    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;
    406250            if (q == NULL)
    407251            {
    408                 p->avl.link[0] = q = node;
     252                q = node;
     253                p->avl.right = q = node;
    409254                break;
    410255            }
    411256        }
    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;
    421290                    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;
    423373            }
    424374            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            }
    480378        }
    481379        else
    482380        {
    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
    575386    return 0;
    576387}
    … …  
    589400 */
    590401static 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)
     402avl_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 */
    637433            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);
    659449    }
    660450    else
    661451    {
    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;
    669464    }
    670465    else
    671466    {
    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;
    681477        }
    682478        else
    683479        {
    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;
    690482           
    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 */
    760546                    {
    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)
    877551                        {
    878                             /* Andron */
    879                             root_avl.link[(int) a[k - 1]] = p;
     552                            p1->avl.bal = -1;
     553                            modified = FALSE;
    880554                        }
    881555                        else
    882556                        {
    883                             pa[k - 1]->avl.link[(int) a[k - 1]] = p;
     557                            p->avl.bal = 0;
     558                            p1->avl.bal = 0;
    884559                        }
     560                        p = p1;
    885561                    }
    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   
    890659    return 0;
    891660}
    892 
    893 #endif
    894661
    895662/* bdbuf_initialize_pool --
    … …  
    1182949            bd_buf->dev = device;
    1183950            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
    1185955            bd_buf->avl.left = NULL;
    1186956            bd_buf->avl.right = NULL;
    1187 #else
    1188             bd_buf->avl.link[0] = NULL;
    1189             bd_buf->avl.link[1] = NULL;
    1190957#endif
    1191958            bd_buf->use_count = 1;
    … …  
    12421009        while (bd_buf->in_progress != 0)
    12431010        {
     1011            rtems_interrupt_disable(level);
    12441012            _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE,
    12451013                              WATCHDOG_NO_TIMEOUT, level);
    … …  
    14601228        else
    14611229        {
     1230            rtems_interrupt_disable(level);
    14621231            _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE,
    14631232                              WATCHDOG_NO_TIMEOUT, level);
    … …  
    16511420    if (rc == RTEMS_SUCCESSFUL)
    16521421    {
     1422        rtems_interrupt_disable(level);
    16531423        _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE,
    16541424                          WATCHDOG_NO_TIMEOUT, level);
    … …  
    16921462        if (bd_buf != NULL /* && bd_buf->modified */)
    16931463        {
     1464            rtems_interrupt_disable(level);
    16941465            _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE,
    16951466                              WATCHDOG_NO_TIMEOUT, level);
    … …  
    17641535            if (bd_buf->in_progress)
    17651536            {
     1537                rtems_interrupt_disable(level);
    17661538                _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE, 0, level);
    17671539            }

  • c/src/libblock/ChangeLog

    rd7478774 rdf6348bb  
     12002-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
     82002-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
    1152002-02-28      Joel Sherrill <joel@OARcorp.com>
    216

  • c/src/libblock/include/rtems/bdbuf.h

    rd7478774 rdf6348bb  
    3838    Chain_Node link; /* Link in the lru, mod or free chains */
    3939
    40 #ifdef BINARY_TREE
    4140    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 */
    5447    } avl;
    55 #endif
     48
    5649    dev_t       dev;     /* device number */
    5750    blkdev_bnum block;   /* block number on the device */

  • c/src/libblock/src/bdbuf.c

    rd7478774 rdf6348bb  
    66 * Author: Andrey G. Ivanov <Andrey.Ivanov@oktet.ru>
    77 *         Victor V. Vengerov <vvv@oktet.ru>
     8 *         Alexander Kukuta <kam@oktet.ru>
    89 *
    910 * @(#) $Id$
    … …  
    2223#define BLKDEV_FATAL_BDBUF_CONSISTENCY BLKDEV_FATAL_ERROR(1)
    2324#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};
    2825
    2926
    … …  
    112109
    113110
    114 #ifdef BINARY_TREE
    115 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         else
    124             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         else
    148         {
    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 int
    160 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         else
    182         {
    183             r = &rr->avl.left;
    184         }
    185     }
    186 }
    187 
    188 static int
    189 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         else
    200             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 #else
    214 
    215111/* The default maximum height of 32 allows for AVL trees having
    216112   between 5,704,880 and 4,294,967,295 nodes, depending on order of
    … …  
    221117#endif
    222118
    223 
    224 
    225 /*
    226  * avl_cmp_node_node --
    227  *     Compares two avl nodes. Function compares dev/block pairs of
    228  *     the node1 and node2.
    229  *
    230  * PARAMETERS:
    231  *     node1 - Pointer to the first node to compare
    232  *     node2 - Pointer to the second node to compare
    233  *
    234  * RETURNS:
    235  *     0 - dev/block of the nodes are equal
    236  *     1 - dev/block of the second node are less
    237  *    -1 - dev/block of the first node are less
    238  */
    239 static inline int
    240 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     else
    252         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 compare
    261  *     dev/block - The pattern to compare with
    262  *
    263  * RETURNS:
    264  *     0 - dev/block of the node and specified are equal
    265  *     1 - dev/block specified are less
    266  *    -1 - dev/block of the first node are less
    267  *
    268  */
    269 static inline int
    270 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     else
    283         return 0;
    284 }
    285 
    286 
    287119/*
    288120 * avl_search --
    … …  
    300132avl_search(bdbuf_buffer **root, dev_t dev, blkdev_bnum block)
    301133{
    302 
    303134    bdbuf_buffer *p = *root;
     135
    304136    while ((p != NULL) && ((p->dev != dev) || (p->block != block)))
    305137    {
    306138        if ((p->dev < dev) || ((p->dev == dev) && (p->block < block)))
    307             p = p->avl.link[1];
     139        {
     140            p = p->avl.right;
     141        }
    308142        else
    309             p = p->avl.link[0];
    310     }
     143        {
     144            p = p->avl.left;
     145        }
     146    }
     147   
    311148    return p;
    312149}
     150
    313151
    314152/* avl_search_for_sync --
    … …  
    327165avl_search_for_sync(bdbuf_buffer **root, disk_device *dd)
    328166{
     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;
    329173    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
    336175    while (p != NULL)
    337176    {
    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        }
    342185        else if (p->modified)
     186        {
    343187            return p;
     188        }
    344189        else
    345190        {
    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
    353204    return p;
    354205}
    … …  
    360211 *
    361212 * PARAMETERS:
    362  *     root_addr - Pointer to pointer to the root node
     213 *     root - Pointer to pointer to the root node
    363214 *     node - Pointer to the node to add.
    364215 *
    … …  
    368219 */
    369220static 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;
     221avl_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;
    393239        return 0;
    394240    }
    395241
    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;
    406250            if (q == NULL)
    407251            {
    408                 p->avl.link[0] = q = node;
     252                q = node;
     253                p->avl.right = q = node;
    409254                break;
    410255            }
    411256        }
    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;
    421290                    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;
    423373            }
    424374            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            }
    480378        }
    481379        else
    482380        {
    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
    575386    return 0;
    576387}
    … …  
    589400 */
    590401static 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)
     402avl_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 */
    637433            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);
    659449    }
    660450    else
    661451    {
    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;
    669464    }
    670465    else
    671466    {
    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;
    681477        }
    682478        else
    683479        {
    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;
    690482           
    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 */
    760546                    {
    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)
    877551                        {
    878                             /* Andron */
    879                             root_avl.link[(int) a[k - 1]] = p;
     552                            p1->avl.bal = -1;
     553                            modified = FALSE;
    880554                        }
    881555                        else
    882556                        {
    883                             pa[k - 1]->avl.link[(int) a[k - 1]] = p;
     557                            p->avl.bal = 0;
     558                            p1->avl.bal = 0;
    884559                        }
     560                        p = p1;
    885561                    }
    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   
    890659    return 0;
    891660}
    892 
    893 #endif
    894661
    895662/* bdbuf_initialize_pool --
    … …  
    1182949            bd_buf->dev = device;
    1183950            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
    1185955            bd_buf->avl.left = NULL;
    1186956            bd_buf->avl.right = NULL;
    1187 #else
    1188             bd_buf->avl.link[0] = NULL;
    1189             bd_buf->avl.link[1] = NULL;
    1190957#endif
    1191958            bd_buf->use_count = 1;
    … …  
    12421009        while (bd_buf->in_progress != 0)
    12431010        {
     1011            rtems_interrupt_disable(level);
    12441012            _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE,
    12451013                              WATCHDOG_NO_TIMEOUT, level);
    … …  
    14601228        else
    14611229        {
     1230            rtems_interrupt_disable(level);
    14621231            _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE,
    14631232                              WATCHDOG_NO_TIMEOUT, level);
    … …  
    16511420    if (rc == RTEMS_SUCCESSFUL)
    16521421    {
     1422        rtems_interrupt_disable(level);
    16531423        _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE,
    16541424                          WATCHDOG_NO_TIMEOUT, level);
    … …  
    16921462        if (bd_buf != NULL /* && bd_buf->modified */)
    16931463        {
     1464            rtems_interrupt_disable(level);
    16941465            _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE,
    16951466                              WATCHDOG_NO_TIMEOUT, level);
    … …  
    17641535            if (bd_buf->in_progress)
    17651536            {
     1537                rtems_interrupt_disable(level);
    17661538                _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE, 0, level);
    17671539            }

  • cpukit/libblock/ChangeLog

    rd7478774 rdf6348bb  
     12002-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
     82002-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
    1152002-02-28      Joel Sherrill <joel@OARcorp.com>
    216

  • cpukit/libblock/include/rtems/bdbuf.h

    rd7478774 rdf6348bb  
    3838    Chain_Node link; /* Link in the lru, mod or free chains */
    3939
    40 #ifdef BINARY_TREE
    4140    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 */
    5447    } avl;
    55 #endif
     48
    5649    dev_t       dev;     /* device number */
    5750    blkdev_bnum block;   /* block number on the device */

  • cpukit/libblock/src/bdbuf.c

    rd7478774 rdf6348bb  
    66 * Author: Andrey G. Ivanov <Andrey.Ivanov@oktet.ru>
    77 *         Victor V. Vengerov <vvv@oktet.ru>
     8 *         Alexander Kukuta <kam@oktet.ru>
    89 *
    910 * @(#) $Id$
    … …  
    2223#define BLKDEV_FATAL_BDBUF_CONSISTENCY BLKDEV_FATAL_ERROR(1)
    2324#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};
    2825
    2926
    … …  
    112109
    113110
    114 #ifdef BINARY_TREE
    115 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         else
    124             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         else
    148         {
    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 int
    160 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         else
    182         {
    183             r = &rr->avl.left;
    184         }
    185     }
    186 }
    187 
    188 static int
    189 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         else
    200             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 #else
    214 
    215111/* The default maximum height of 32 allows for AVL trees having
    216112   between 5,704,880 and 4,294,967,295 nodes, depending on order of
    … …  
    221117#endif
    222118
    223 
    224 
    225 /*
    226  * avl_cmp_node_node --
    227  *     Compares two avl nodes. Function compares dev/block pairs of
    228  *     the node1 and node2.
    229  *
    230  * PARAMETERS:
    231  *     node1 - Pointer to the first node to compare
    232  *     node2 - Pointer to the second node to compare
    233  *
    234  * RETURNS:
    235  *     0 - dev/block of the nodes are equal
    236  *     1 - dev/block of the second node are less
    237  *    -1 - dev/block of the first node are less
    238  */
    239 static inline int
    240 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     else
    252         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 compare
    261  *     dev/block - The pattern to compare with
    262  *
    263  * RETURNS:
    264  *     0 - dev/block of the node and specified are equal
    265  *     1 - dev/block specified are less
    266  *    -1 - dev/block of the first node are less
    267  *
    268  */
    269 static inline int
    270 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     else
    283         return 0;
    284 }
    285 
    286 
    287119/*
    288120 * avl_search --
    … …  
    300132avl_search(bdbuf_buffer **root, dev_t dev, blkdev_bnum block)
    301133{
    302 
    303134    bdbuf_buffer *p = *root;
     135
    304136    while ((p != NULL) && ((p->dev != dev) || (p->block != block)))
    305137    {
    306138        if ((p->dev < dev) || ((p->dev == dev) && (p->block < block)))
    307             p = p->avl.link[1];
     139        {
     140            p = p->avl.right;
     141        }
    308142        else
    309             p = p->avl.link[0];
    310     }
     143        {
     144            p = p->avl.left;
     145        }
     146    }
     147   
    311148    return p;
    312149}
     150
    313151
    314152/* avl_search_for_sync --
    … …  
    327165avl_search_for_sync(bdbuf_buffer **root, disk_device *dd)
    328166{
     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;
    329173    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
    336175    while (p != NULL)
    337176    {
    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        }
    342185        else if (p->modified)
     186        {
    343187            return p;
     188        }
    344189        else
    345190        {
    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
    353204    return p;
    354205}
    … …  
    360211 *
    361212 * PARAMETERS:
    362  *     root_addr - Pointer to pointer to the root node
     213 *     root - Pointer to pointer to the root node
    363214 *     node - Pointer to the node to add.
    364215 *
    … …  
    368219 */
    369220static 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;
     221avl_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;
    393239        return 0;
    394240    }
    395241
    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;
    406250            if (q == NULL)
    407251            {
    408                 p->avl.link[0] = q = node;
     252                q = node;
     253                p->avl.right = q = node;
    409254                break;
    410255            }
    411256        }
    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;
    421290                    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;
    423373            }
    424374            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            }
    480378        }
    481379        else
    482380        {
    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
    575386    return 0;
    576387}
    … …  
    589400 */
    590401static 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)
     402avl_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 */
    637433            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);
    659449    }
    660450    else
    661451    {
    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;
    669464    }
    670465    else
    671466    {
    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;
    681477        }
    682478        else
    683479        {
    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;
    690482           
    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 */
    760546                    {
    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)
    877551                        {
    878                             /* Andron */
    879                             root_avl.link[(int) a[k - 1]] = p;
     552                            p1->avl.bal = -1;
     553                            modified = FALSE;
    880554                        }
    881555                        else
    882556                        {
    883                             pa[k - 1]->avl.link[(int) a[k - 1]] = p;
     557                            p->avl.bal = 0;
     558                            p1->avl.bal = 0;
    884559                        }
     560                        p = p1;
    885561                    }
    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   
    890659    return 0;
    891660}
    892 
    893 #endif
    894661
    895662/* bdbuf_initialize_pool --
    … …  
    1182949            bd_buf->dev = device;
    1183950            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
    1185955            bd_buf->avl.left = NULL;
    1186956            bd_buf->avl.right = NULL;
    1187 #else
    1188             bd_buf->avl.link[0] = NULL;
    1189             bd_buf->avl.link[1] = NULL;
    1190957#endif
    1191958            bd_buf->use_count = 1;
    … …  
    12421009        while (bd_buf->in_progress != 0)
    12431010        {
     1011            rtems_interrupt_disable(level);
    12441012            _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE,
    12451013                              WATCHDOG_NO_TIMEOUT, level);
    … …  
    14601228        else
    14611229        {
     1230            rtems_interrupt_disable(level);
    14621231            _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE,
    14631232                              WATCHDOG_NO_TIMEOUT, level);
    … …  
    16511420    if (rc == RTEMS_SUCCESSFUL)
    16521421    {
     1422        rtems_interrupt_disable(level);
    16531423        _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE,
    16541424                          WATCHDOG_NO_TIMEOUT, level);
    … …  
    16921462        if (bd_buf != NULL /* && bd_buf->modified */)
    16931463        {
     1464            rtems_interrupt_disable(level);
    16941465            _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE,
    16951466                              WATCHDOG_NO_TIMEOUT, level);
    … …  
    17641535            if (bd_buf->in_progress)
    17651536            {
     1537                rtems_interrupt_disable(level);
    17661538                _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE, 0, level);
    17671539            }
Note: See TracChangeset for help on using the changeset viewer.