Subversion Repositories HelenOS

Rev

Rev 2501 | Rev 2504 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 2501 Rev 2503
Line 105... Line 105...
105 
        p = p->lft;
 105 
        p = p->lft;
106 
   
 106 
   
107 
    return p;
 107 
    return p;
108 
}
 108 
}
109 
 
 109 
 
- 
 
 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 
   
110 
/** Insert new node into AVL tree.
 154 
/** Insert new node into AVL tree.
111 
 *
 155 
 *
112 
 * @param t AVL tree.
 156 
 * @param t AVL tree.
113 
 * @param newnode New node to be inserted.
 157 
 * @param newnode New node to be inserted.
114 
 */
 158 
 */
Line 143... Line 187...
143 
        gpa = par;
 187 
        gpa = par;
144 
        dpc = par->key > key ? &par->lft: &par->rgt;
 188 
        dpc = par->key > key ? &par->lft: &par->rgt;
145 
    }
 189 
    }
146 
 
 190 
 
147 
    /*
 191 
    /*
148 
     * Initialize new node.
 192 
     * Initialize the new node.
149 
     */
 193 
     */
150 
    newnode->key = key;
 194 
    newnode->key = key;
151 
    newnode->lft = NULL;
 195 
    newnode->lft = NULL;
152 
    newnode->rgt = NULL;
 196 
    newnode->rgt = NULL;
153 
    newnode->par = gpa;
 197 
    newnode->par = gpa;
Line 160... Line 204...
160 
        *dpc = newnode;
 204 
        *dpc = newnode;
161 
        return;
 205 
        return;
162 
    }
 206 
    }
163 
 
 207 
 
164 
    /*
 208 
    /*
165 
     * Insert new node into previously found leaf place.
 209 
     * Insert the new node into the previously found leaf position.
166 
     */
 210 
     */
167 
    *dpc = newnode;
 211 
    *dpc = newnode;
168 
 
 212 
 
169 
    /*
 213 
    /*
170 
     * If the tree contains one node - end.
 214 
     * If the tree contains one node - end.
Line 207... Line 251...
207 
        par = top->lft;
 251 
        par = top->lft;
208 
        if (par->balance == -1) {
 252 
        if (par->balance == -1) {
209 
            /*
 253 
            /*
210 
             * LL rotation.
 254 
             * LL rotation.
211 
             */
 255 
             */
212 
            top->lft = par->rgt;
 - 
 
213 
            if (top->lft != NULL)
 256 
            REBALANCE_INSERT_LL();
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;
 - 
 
221 
        } else {
 257 
        } else {
222 
            /*
 258 
            /*
223 
             * LR rotation.
 259 
             * LR rotation.
224 
             */
 260 
             */
225 
            ASSERT(par->balance == 1);
 261 
            ASSERT(par->balance == 1);
226 
           
 262 
           
227 
            gpa = par->rgt;
 - 
 
228 
            par->rgt = gpa->lft;
 - 
 
229 
            if (gpa->lft != NULL)
 - 
 
230 
                gpa->lft->par = par;
 263 
            REBALANCE_INSERT_LR();
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;
 - 
 
252 
        }
 264 
        }
253 
    } else if (top->balance == 2) {
 265 
    } else if (top->balance == 2) {
254 
        par = top->rgt;
 266 
        par = top->rgt;
255 
        if (par->balance == 1) {
 267 
        if (par->balance == 1) {
256 
            /*
 268 
            /*
257 
             * RR rotation.
 269 
             * RR rotation.
258 
             */
 270 
             */
259 
            top->rgt = par->lft;
 - 
 
260 
            if (top->rgt != NULL)
 - 
 
261 
                top->rgt->par = top;
 271 
            REBALANCE_INSERT_RR();
262 
            par->par = top->par;
 - 
 
263 
            top->par = par;
 - 
 
264 
            par->lft = top;
 - 
 
265 
            par->balance = 0;
 - 
 
266 
            top->balance = 0;
 - 
 
267 
            *dpc = par;
 - 
 
268 
        } else {
 272 
        } else {
269 
            /*
 273 
            /*
270 
             * RL rotation.
 274 
             * RL rotation.
271 
             */
 275 
             */
272 
            ASSERT(par->balance == -1);
 276 
            ASSERT(par->balance == -1);
273 
           
 277 
       
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)
 278 
            REBALANCE_INSERT_RL();
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;
 - 
 
299 
        }
 279 
        }
300 
    } else {
 280 
    } else {
301 
        /*
 281 
        /*
302 
         * Balance is not broken, insertion is finised.
 282 
         * Balance is not broken, insertion is finised.
303 
         */
 283 
         */
Line 349... Line 329...
349 
        }
 329 
        }
350 
    }
 330 
    }
351 
    return 1;
 331 
    return 1;
352 
}
 332 
}
353 
 
 333 
 
354 
#define REBALANCE(DIR1, DIR2, SIGN)     \
 334 
#define REBALANCE_DELETE(DIR1, DIR2, SIGN)  \
355 
    if (cur->balance == -1 * SIGN) {    \
 335 
    if (cur->balance == -1 * SIGN) {    \
356 
        par->balance = 0;       \
 336 
        par->balance = 0;       \
357 
        gpa->balance = 1 * SIGN;    \
 337 
        gpa->balance = 1 * SIGN;    \
358 
        if (gpa->DIR1)          \
 338 
        if (gpa->DIR1)          \
359 
            gpa->DIR1->par = gpa;   \
 339 
            gpa->DIR1->par = gpa;   \
Line 372... Line 352...
372 
            par->DIR2->par = par;   \
 352 
            par->DIR2->par = par;   \
373 
        gpa->DIR1->par = gpa;       \
 353 
        gpa->DIR1->par = gpa;       \
374 
    }                   \
 354 
    }                   \
375 
    cur->balance = 0;
 355 
    cur->balance = 0;
376 
 
 356 
 
377 
#define REBALANCE_LR()      REBALANCE(lft, rgt, 1)
 357 
#define REBALANCE_DELETE_LR()       REBALANCE_DELETE(lft, rgt, 1)
378 
#define REBALANCE_RL()      REBALANCE(rgt, lft, -1)
 358 
#define REBALANCE_DELETE_RL()       REBALANCE_DELETE(rgt, lft, -1)
379 
 
 359 
 
380 
/** Delete a node from the AVL tree.
 360 
/** Delete a node from the AVL tree.
381 
 *
 361 
 *
382 
 * Because multiple identical keys are allowed, the parent pointers are
 362 
 * Because multiple identical keys are allowed, the parent pointers are
383 
 * essential during deletion.
 363 
 * essential during deletion.
Line 513... Line 493...
513 
                    /*
 493 
                    /*
514 
                     * Repair balances and paternity of
 494 
                     * Repair balances and paternity of
515 
                     * children, depending on the balance
 495 
                     * children, depending on the balance
516 
                     * factor of the grand child (cur).
 496 
                     * factor of the grand child (cur).
517 
                     */
 497 
                     */
518 
                    REBALANCE_RL();
 498 
                    REBALANCE_DELETE_RL();
519 
                   
 499 
                   
520 
                    /*
 500 
                    /*
521 
                     * Repair paternity.
 501 
                     * Repair paternity.
522 
                     */
 502 
                     */
523 
                    cur->par = gpa->par;
 503 
                    cur->par = gpa->par;
Line 609... Line 589...
609 
                    /*
 589 
                    /*
610 
                     * Repair balances and paternity of
 590 
                     * Repair balances and paternity of
611 
                     * children, depending on the balance
 591 
                     * children, depending on the balance
612 
                     * factor of the grand child (cur).
 592 
                     * factor of the grand child (cur).
613 
                     */
 593 
                     */
614 
                    REBALANCE_LR();
 594 
                    REBALANCE_DELETE_LR();
615 
 
 595 
 
616 
                    /*
 596 
                    /*
617 
                     * Repair paternity.
 597 
                     * Repair paternity.
618 
                     */
 598 
                     */
619 
                    cur->par = gpa->par;
 599 
                    cur->par = gpa->par;