Changeset 83a5cba in mainline


Ignore:
Timestamp:
2007-07-29T18:18:37Z (18 years ago)
Author:
Jakub Jermar <jakub@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
b76a2217
Parents:
5dcee525
Message:

Get rid of code duplicities in the insert path into an AVL tree.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • kernel/generic/src/adt/avl.c

    r5dcee525 r83a5cba  
    108108}
    109109
     110#define REBALANCE_INSERT_XX(DIR1, DIR2)         \
     111        top->DIR1 = par->DIR2;                  \
     112        if (top->DIR1 != NULL)                  \
     113                top->DIR1->par = top;           \
     114        par->par = top->par;                    \
     115        top->par = par;                         \
     116        par->DIR2 = top;                        \
     117        par->balance = 0;                       \
     118        top->balance = 0;                       \
     119        *dpc = par;
     120
     121#define REBALANCE_INSERT_LL()           REBALANCE_INSERT_XX(lft, rgt)
     122#define REBALANCE_INSERT_RR()           REBALANCE_INSERT_XX(rgt, lft)
     123
     124#define REBALANCE_INSERT_XY(DIR1, DIR2, SGN)    \
     125        gpa = par->DIR2;                        \
     126        par->DIR2 = gpa->DIR1;                  \
     127        if (gpa->DIR1 != NULL)                  \
     128                gpa->DIR1->par = par;           \
     129        gpa->DIR1 = par;                        \
     130        par->par = gpa;                         \
     131        top->DIR1 = gpa->DIR2;                  \
     132        if (gpa->DIR2 != NULL)                  \
     133                gpa->DIR2->par = top;           \
     134        gpa->DIR2 = top;                        \
     135        gpa->par = top->par;                    \
     136        top->par = gpa;                         \
     137                                                \
     138        if (gpa->balance == -1 * SGN) {         \
     139                par->balance = 0;               \
     140                top->balance = 1 * SGN;         \
     141        } else if (gpa->balance == 0) {         \
     142                par->balance = 0;               \
     143                top->balance = 0;               \
     144        } else {                                \
     145                par->balance = -1 * SGN;        \
     146                top->balance = 0;               \
     147        }                                       \
     148        gpa->balance = 0;                       \
     149        *dpc = gpa;
     150
     151#define REBALANCE_INSERT_LR()           REBALANCE_INSERT_XY(lft, rgt, 1)
     152#define REBALANCE_INSERT_RL()           REBALANCE_INSERT_XY(rgt, lft, -1)
     153       
    110154/** Insert new node into AVL tree.
    111155 *
    … …  
    146190
    147191        /*
    148          * Initialize new node.
     192         * Initialize the new node.
    149193         */
    150194        newnode->key = key;
    … …  
    163207
    164208        /*
    165          * Insert new node into previously found leaf place.
     209         * Insert the new node into the previously found leaf position.
    166210         */
    167211        *dpc = newnode;
    … …  
    210254                         * LL rotation.
    211255                         */
    212                         top->lft = par->rgt;
    213                         if (top->lft != NULL)
    214                                 top->lft->par = top;
    215                         par->par = top->par;
    216                         top->par = par;
    217                         par->rgt = top;
    218                         par->balance = 0;
    219                         top->balance = 0;
    220                         *dpc = par;
     256                        REBALANCE_INSERT_LL();
    221257                } else {
    222258                        /*
    … …  
    225261                        ASSERT(par->balance == 1);
    226262                       
    227                         gpa = par->rgt;
    228                         par->rgt = gpa->lft;
    229                         if (gpa->lft != NULL)
    230                                 gpa->lft->par = par;
    231                         gpa->lft = par;
    232                         par->par = gpa;
    233                         top->lft = gpa->rgt;
    234                         if (gpa->rgt != NULL)
    235                                 gpa->rgt->par = top;
    236                         gpa->rgt = top;
    237                         gpa->par = top->par;
    238                         top->par = gpa;
    239                        
    240                         if (gpa->balance == -1) {
    241                                 par->balance = 0;
    242                                 top->balance = 1;
    243                         } else if (gpa->balance == 0) {
    244                                 par->balance = 0;
    245                                 top->balance = 0;
    246                         } else {
    247                                 par->balance = -1;
    248                                 top->balance = 0;
    249                         }
    250                         gpa->balance = 0;
    251                         *dpc = gpa;
     263                        REBALANCE_INSERT_LR();
    252264                }
    253265        } else if (top->balance == 2) {
    … …  
    257269                         * RR rotation.
    258270                         */
    259                         top->rgt = par->lft;
    260                         if (top->rgt != NULL)
    261                                 top->rgt->par = top;
    262                         par->par = top->par;
    263                         top->par = par;
    264                         par->lft = top;
    265                         par->balance = 0;
    266                         top->balance = 0;
    267                         *dpc = par;
     271                        REBALANCE_INSERT_RR();
    268272                } else {
    269273                        /*
    … …  
    271275                         */
    272276                        ASSERT(par->balance == -1);
    273                        
    274                         gpa = par->lft;
    275                         par->lft = gpa->rgt;
    276                         if (gpa->rgt != NULL)
    277                                 gpa->rgt->par = par;
    278                         gpa->rgt = par;
    279                         par->par = gpa;
    280                         top->rgt = gpa->lft;
    281                         if (gpa->lft != NULL)
    282                                 gpa->lft->par = top;
    283                         gpa->lft = top;
    284                         gpa->par = top->par;
    285                         top->par = gpa;
    286 
    287                         if (gpa->balance == 1) {
    288                                 par->balance = 0;
    289                                 top->balance = -1;
    290                         } else if (gpa->balance == 0) {
    291                                 par->balance = 0;
    292                                 top->balance = 0;
    293                         } else {
    294                                 par->balance = 1;
    295                                 top->balance = 0;
    296                         }
    297                         gpa->balance = 0;
    298                         *dpc = gpa;
     277               
     278                        REBALANCE_INSERT_RL();
    299279                }
    300280        } else {
    … …  
    352332}
    353333
    354 #define REBALANCE(DIR1, DIR2, SIGN)             \
     334#define REBALANCE_DELETE(DIR1, DIR2, SIGN)      \
    355335        if (cur->balance == -1 * SIGN) {        \
    356336                par->balance = 0;               \
    … …  
    375355        cur->balance = 0;
    376356
    377 #define REBALANCE_LR()          REBALANCE(lft, rgt, 1)
    378 #define REBALANCE_RL()          REBALANCE(rgt, lft, -1)
     357#define REBALANCE_DELETE_LR()           REBALANCE_DELETE(lft, rgt, 1)
     358#define REBALANCE_DELETE_RL()           REBALANCE_DELETE(rgt, lft, -1)
    379359
    380360/** Delete a node from the AVL tree.
    … …  
    516496                                         * factor of the grand child (cur).
    517497                                         */
    518                                         REBALANCE_RL();
     498                                        REBALANCE_DELETE_RL();
    519499                                       
    520500                                        /*
    … …  
    612592                                         * factor of the grand child (cur).
    613593                                         */
    614                                         REBALANCE_LR();
     594                                        REBALANCE_DELETE_LR();
    615595
    616596                                        /*
Note: See TracChangeset for help on using the changeset viewer.