Subversion Repositories HelenOS

Rev

Rev 2431 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2416 mencl 1
/*
2
 * Copyright (c) 2007 Vojtech Mencl
3
 * All rights reserved.
4
 *
5
 * Redistribution and use in source and binary forms, with or without
6
 * modification, are permitted provided that the following conditions
7
 * are met:
8
 *
9
 * - Redistributions of source code must retain the above copyright
10
 *   notice, this list of conditions and the following disclaimer.
11
 * - Redistributions in binary form must reproduce the above copyright
12
 *   notice, this list of conditions and the following disclaimer in the
13
 *   documentation and/or other materials provided with the distribution.
14
 * - The name of the author may not be used to endorse or promote products
15
 *   derived from this software without specific prior written permission.
16
 *
17
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
 */
28
 
29
/** @addtogroup genericadt
30
 * @{
31
 */
32
 
33
/**
34
 * @file
35
 * @brief   Extended AVL tree implementation.
36
 *
37
 * This file implements Extended AVL tree type and operations.
38
 *
39
 * Extended AVL tree (ExtAvl tree) has the following properties:
40
 * @li it is binary search tree with unique keys
41
 * @li right subtree of every node is Avl tree
42
 * @li height of left subtree of every node is not greater then height of right subtree + 1
43
 * @li nodes with the same keys are linked to the tree nodes of the same key, they are not tree nodes
44
 * @li every node is part of doubly linked list with head
45
 * @li nodes are connected in the list ascendentaly according to their keys
46
 *
47
 * Be careful of using this tree because of base atribute, which is added to every inserted
48
 * node key.
49
 */
50
 
51
#include <adt/extavl.h>
52
#include <debug.h>
53
#include <panic.h>
54
 
55
#define AVLTREE_LEFT 0
56
#define AVLTREE_RIGHT 1
57
 
58
/* Returns height of tree -1 */
59
#define extavltree_tree_height(node) (((node) == NULL) ? (-1) : (((node)->lft_height>(node)->rgt_height)?(node)->lft_height:(node)->rgt_height))
60
 
61
/** Search first occurence (oldest node with this key) of given key in Extended AVL tree.
62
 *
63
 * @param t Extended AVL tree.
64
 * @param key Key to be searched.
65
 *
2421 mencl 66
 * @return Pointer to node or NULL if there is no such key.
2416 mencl 67
 */
68
extavltree_node_t *extavltree_search(extavltree_t *t, uint64_t key)
69
{
70
    extavltree_node_t *cur;
71
 
72
    cur = t->root;
73
    while (cur != NULL) {
74
        if (cur->key < key) {
75
            cur = cur->rgt;
76
        } else if (cur->key > key) {
77
            cur = cur->lft;
78
        } else {
79
            return cur;
80
        }
81
    }
82
    return NULL;
83
}
84
 
85
/** Insert new node into ExtAVL tree.
86
 *
2450 mencl 87
 * New node's key must be set - to that key will be added base (default 0).
2416 mencl 88
 *
89
 * @param t ExtAVL tree structure.
90
 * @param newnode New node to be inserted.
91
 */
92
void extavltree_insert(extavltree_t *t, extavltree_node_t *newnode)
93
{  
94
    extavltree_node_t *cur;
95
    extavltree_node_t *son;
96
    extavltree_node_t *gpa;
97
    extavltree_node_t *par;
98
    uint64_t key;
99
 
100
    ASSERT(t);
101
    ASSERT(newnode);
102
 
103
    /*
104
     * Creating absolute key.
105
     */
106
    newnode->key = key = newnode->key + t->base;
107
 
108
 
109
    /*
110
     * Insert first node into empty tree.
111
     */
112
    if (t->root == NULL) {
113
        newnode->lft = NULL;
114
        newnode->rgt = NULL;
115
        newnode->lft_height = 0;
116
        newnode->rgt_height = 0;
117
        newnode->par = NULL;
118
        newnode->next = &t->head;
119
        newnode->prev = &t->head;
120
 
121
        t->head.prev = newnode;
122
        t->head.next = newnode;
123
        t->root = newnode;
124
        return;
125
    }
126
 
127
    /*
128
     * Tree is not empty - search for the right place for new node.
129
     */
130
    cur = t->root;
131
    while(true) {
132
        if (cur->key < key) {
133
            if (!cur->rgt) {
134
                        /*
135
                 * We have reach leaf. New node will be right son.
136
                 */
137
                cur->rgt = newnode;
138
 
139
                newnode->lft = NULL;
140
                newnode->rgt = NULL;
141
                newnode->lft_height = 0;
142
                newnode->rgt_height = 0;
143
                        newnode->par = cur;
144
 
145
                newnode->prev = cur;
146
                newnode->next = cur->next;
147
                cur->next->prev = newnode;
148
                cur->next = newnode;
149
                        break;
150
                    }
151
            cur = cur->rgt;
152
        } else if (cur->key > key) {
153
            if (!cur->lft) {
154
                        /*
155
                 * We have reach leaf. New node will be left son.
156
                 */
157
                cur->lft = newnode;
158
 
159
                newnode->lft = NULL;
160
                newnode->rgt = NULL;
161
                newnode->lft_height = 0;
162
                newnode->rgt_height = 0;
163
                newnode->par = cur;
164
 
165
                gpa = cur;
2431 mencl 166
                while ((gpa != &t->head) && (gpa->key == cur->key))
2416 mencl 167
                    gpa = gpa->prev;
168
                newnode->next = gpa->next;
169
                newnode->prev = gpa;
170
                gpa->next->prev = newnode;
171
                gpa->next = newnode;
172
                break;
173
                    }
174
            cur = cur->lft;
175
        } else {
176
            /*
177
             * Key has been previously inserted into tree. Make new node as a tree node
178
             * and old tree node move to the prev. Old tree node will be list node.
179
             */
180
 
181
            newnode->prev = cur;
182
            newnode->next = cur->next;
183
            cur->next->prev = newnode;
184
            cur->next = newnode;
185
 
186
            newnode->par = cur->par;
187
            cur->par = NULL;
188
            newnode->lft = cur->lft;
189
            cur->lft = NULL;
190
            newnode->rgt = cur->rgt;
191
            cur->rgt = NULL;
192
            newnode->lft_height = cur->lft_height;
193
            cur->lft_height = 0;
194
            newnode->rgt_height = cur->rgt_height;
195
            cur->rgt_height = 0;
196
 
197
            if (newnode->lft) newnode->lft->par = newnode;
198
            if (newnode->rgt) newnode->rgt->par = newnode;
199
            if (newnode->par) {
200
                if (newnode->par->lft == cur)
201
                    newnode->par->lft = newnode;
202
                else
203
                    newnode->par->rgt = newnode;
204
            } else {
205
                t->root = newnode;
206
            }
207
            return;
208
        }
209
    }
210
 
211
    /*
212
     * Balancing all nodes from newnode's parent down to root. All nodes must be checked
213
     * because delete min operation can corrupt heights and only insert operation can
214
     * repair it.
215
     */
216
    cur = newnode->par;
217
    while (cur) {
218
        if (cur->key > key) {
219
            /*
220
             * Insertion was made in the left subtree - repair left height
221
             * and check balance of current node.
222
             */
223
            cur->lft_height = extavltree_tree_height(cur->lft) + 1;
224
 
225
            if ((cur->rgt_height - cur->lft_height) <= -2) {
226
                /*
227
                 * Balance was corrupted, must be repaired through LL or LR rotation.
228
                 */
229
                par = cur->par;
230
                son = cur->lft;
231
                if ((son->rgt_height - son->lft_height) != 1) {
232
                    /*
233
                     * LL rotation
234
                     */
235
 
236
                    gpa = son;
237
                    cur->lft = son->rgt;
238
                    if (cur->lft != NULL) cur->lft->par = cur;
239
                    cur->par = son;
240
                    son->rgt = cur;
241
                    /*
242
                     * Repair heights.
243
                     */
244
                    cur->lft_height = son->rgt_height;
245
                    son->rgt_height = extavltree_tree_height(cur) + 1;
246
                } else {
247
                    /*
248
                     * LR rotation
249
                     */
250
 
251
                    gpa = son->rgt;
252
                    son->rgt = gpa->lft;
253
                    if (gpa->lft != NULL) gpa->lft->par = son;
254
                    gpa->lft = son;
255
                    son->par = gpa;
256
                    cur->lft = gpa->rgt;
257
                    if (gpa->rgt != NULL) gpa->rgt->par = cur;
258
                    gpa->rgt = cur;
259
                    cur->par = gpa;
260
                    /*
261
                     * Repair heights.
262
                     */
263
                    cur->lft_height = gpa->rgt_height;
264
                    son->rgt_height = gpa->lft_height;
265
                    gpa->rgt_height = extavltree_tree_height(cur) + 1;
266
                    gpa->lft_height = extavltree_tree_height(son) + 1;
267
                }
268
 
269
                /*
270
                 * Change parent pointers or if current node is root then
271
                 * change root atribute pointer.
272
                 */
273
                gpa->par = par;
274
                if (par) {
275
                    if (par->lft == cur)
276
                        par->lft = gpa;
277
                    else
278
                        par->rgt = gpa;
279
                } else {
280
                    t->root = gpa;
281
                }
282
                cur = par;
283
            } else {
284
                /*
285
                 * Current node is balanced, continue balancing of its parent.
286
                 */
287
                cur = cur->par;
288
            }
289
        } else {
290
            /*
291
             * Insertion was made in the right subtree - repair right height
292
             * and check balance of current node.
293
             */
294
            cur->rgt_height = extavltree_tree_height(cur->rgt) + 1;
295
 
296
            if ((cur->rgt_height - cur->lft_height) >= 2) {
297
                /*
298
                 * Balance was corrupted, must be repaired through LL or LR rotation.
299
                 */
300
                par = cur->par;
301
                son = cur->rgt;
302
                if ((son->rgt_height - son->lft_height) != -1) {
303
                    /*
304
                     * RR rotation
305
                     */
306
                    gpa = son;
307
                    cur->rgt = son->lft;
308
                    if (cur->rgt != NULL) cur->rgt->par = cur;
309
                    cur->par = son;
310
                    son->lft = cur;
311
                    /*
312
                     * Repair heights.
313
                     */
314
                    cur->rgt_height = son->lft_height;
315
                    son->lft_height = extavltree_tree_height(cur) + 1;
316
                } else {
317
                    /*
318
                     * RL rotation
319
                     */
320
                    gpa = son->lft;
321
                    son->lft = gpa->rgt;
322
                    if (gpa->rgt != NULL) gpa->rgt->par = son;
323
                    gpa->rgt = son;
324
                    son->par = gpa;
325
                    cur->rgt = gpa->lft;
326
                    if (gpa->lft != NULL) gpa->lft->par = cur;
327
                    gpa->lft = cur;
328
                    cur->par = gpa;
329
                    /*
330
                     * Repair heights.
331
                     */
332
                    cur->rgt_height = gpa->lft_height;
333
                    son->lft_height = gpa->rgt_height;
334
                    gpa->lft_height = extavltree_tree_height(cur) + 1;
335
                    gpa->rgt_height = extavltree_tree_height(son) + 1;
336
                }
337
 
338
                /*
339
                 * Change parent pointers or if current node is root then
340
                 * change root atribute pointer.
341
                 */            
342
                gpa->par = par;
343
                if (par) {
344
                    if (par->lft == cur)
345
                        par->lft = gpa;
346
                    else
347
                        par->rgt = gpa;
348
                } else {
349
                    t->root = gpa;
350
                }
351
                cur = par;
352
            } else {
353
                /*
354
                 * Current node is balanced, continue balancing of its parent.
355
                 */
356
                cur = cur->par;
357
            }
358
        }
359
    }
360
}
361
 
362
/** Delete node from ExtAVL tree.
363
 *
364
 * @param t ExtAVL tree structure.
365
 * @param node Address of node which will be deleted.
366
 */
367
void extavltree_delete(extavltree_t *t, extavltree_node_t *node)
368
{
369
    extavltree_node_t **gpapar;
370
    extavltree_node_t *cur;
371
    extavltree_node_t *par;
372
    extavltree_node_t *gpa;
373
    int8_t dir;
374
    int8_t dir2=0;
375
    int16_t balance;
376
 
377
    ASSERT(t);
378
    ASSERT(node);
379
 
380
    /*
381
     * Delete node from list.
382
     */
383
    node->next->prev = node->prev;
384
    node->prev->next = node->next;
385
 
386
    if (!node->par) {
387
        if (t->root != node) {
388
            /*
389
             * It is list node (not a tree node). Needn't repair tree or anything else.
390
             */
391
            return;
392
        }
393
        gpapar = &(t->root);
394
    } else {
395
        /*
396
         * Find tree pointer which points to node.
397
         */
398
        if (node->par->lft == node) {
399
            gpapar = &(node->par->lft);
400
        } else {
401
            gpapar = &(node->par->rgt);
402
        }
403
    }
404
 
405
 
2431 mencl 406
    if ((&t->head != node->prev) && (node->prev->key == node->key)) {
2416 mencl 407
        /*
408
         * Deleted node has at least one node node with the same key which is closest previous
409
         * neighbor in the list, copy node atributes into previous node and end.
410
         */
411
        cur = node->prev;
412
        cur->lft = node->lft;
413
        cur->rgt = node->rgt;
414
        cur->par = node->par;
415
        cur->lft_height = node->lft_height;
416
        cur->rgt_height = node->rgt_height;
417
        *gpapar = cur;
418
 
419
        if (node->lft) node->lft->par = cur;
420
        if (node->rgt) node->rgt->par = cur;
421
        return;
422
    }
423
 
424
    /*
425
     * Check situation in the tree around deleted node.
426
     */
427
    if (!node->lft) {
428
        /*
429
         * Deleted node has not left son. Right son will take deleted node's place.
430
         */
431
        gpa = node->par;
432
        if (node->rgt) node->rgt->par = gpa;
433
        if (!gpa) {
434
            /*
435
             * Deleted node is root node. Balancing is finished, change only
436
             * root pointer in extavltree structure.
437
             */
438
            *gpapar = node->rgt;   
439
            return;
440
        }
441
        dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT;
442
        *gpapar = node->rgt;
443
    } else {
444
        /*
445
         * Node has left son.
446
         */
447
        cur = node->lft;
448
        if (!cur->rgt) {
449
            /*
450
             * Left son of node hasn't got right son. Left son will take deleted node's place.
451
             */
452
            *gpapar = cur;
453
            cur->par = node->par;
454
            dir = AVLTREE_LEFT;
455
            cur->rgt = node->rgt;
456
            if (node->rgt) node->rgt->par = cur;
457
            gpa = cur;
458
            cur->rgt_height = node->rgt_height;
459
            cur->lft_height = node->lft_height;
460
            /*
461
             * cur->lft_height will be decreased in repair cycle.
462
             */
463
        } else {
464
            /*
465
             * Node has left and right son. Find a node with smallest key in left subtree
466
             * and change that node with deleted node.
467
             */
468
            while (cur->rgt != NULL)
469
                cur = cur->rgt;
470
 
471
            *gpapar = cur;
472
            cur->rgt = node->rgt;
473
            if (node->rgt) node->rgt->par = cur;
474
            gpa = cur->par;
475
            gpa->rgt = cur->lft;
476
            if (cur->lft) cur->lft->par = gpa;
477
            cur->lft = node->lft;
478
            cur->lft->par = cur;
479
            cur->par = node->par;
480
            dir = AVLTREE_RIGHT;
481
            cur->lft_height = node->lft_height;
482
            cur->rgt_height = node->rgt_height;
483
            /*
484
             * gpa->rgt_height and cur->lft_height will be repaired in repair cycle.
485
             */
486
        }
487
        /*
488
         * Deleted node is root node. Balancing is finished.
489
         */
490
        if (!gpa) return;
491
    }
492
 
493
    /*
494
     * Repair cycle which goes from gpa node down to root.
495
     */
496
    for(;;) {
497
        /*
498
         * Find tree pointer which points to the currently balanced node. When balanced
499
         * node is root, root pointer from extavltree structure is taken.
500
         */
501
        if (!gpa->par)
502
            gpapar = &(t->root);
503
        else {
504
            if (gpa->par->lft == gpa) {
505
                gpapar = &(gpa->par->lft);
506
                dir2 = AVLTREE_LEFT;
507
            } else {
508
                gpapar = &(gpa->par->rgt);
509
                dir2 = AVLTREE_RIGHT;
510
            }
511
        }
512
 
513
        if (dir == AVLTREE_LEFT) {
514
            /*
515
             * Deletition was made in left subtree.
516
             */
517
            gpa->lft_height--;
518
            balance = gpa->rgt_height - gpa->lft_height;
519
            if (balance == 1) {
520
                /*
521
                 * Stop balancing, tree is balanced.
522
                 */
523
                break;
524
            } else if (balance == 2) {
525
                /*
526
                 * Bad balance, heights of left and right subtrees differs more then is allowed.
527
                 */
528
                par = gpa->rgt;
529
 
530
                if ((par->rgt_height - par->lft_height) == -1) {
531
                    /*
532
                     * RL rotation
533
                     */
534
 
535
                    cur = par->lft;
536
                    par->lft = cur->rgt;
537
                    cur->rgt = par;
538
                    gpa->rgt = cur->lft;
539
                    cur->lft = gpa;
540
 
541
                    /*
542
                     * Repair balances.
543
                     */
544
                    par->lft_height = cur->rgt_height;
545
                    gpa->rgt_height = cur->lft_height;
546
                    cur->lft_height = extavltree_tree_height(gpa) + 1; //POZOR nelze: cur->lft_height = gpa->lft_height + 1; - vyska cur je diky timeoutu nesttabilni
547
                    cur->rgt_height = par->rgt_height + 1; //POZOR zmena: cur->rgt_height = extavltree_tree_height(par) + 1;
548
 
549
                    /*
550
                     * Repair paternity.
551
                     */
552
                    if (gpa->rgt) gpa->rgt->par = gpa;
553
                    if (par->lft) par->lft->par = par;
554
                    cur->par = gpa->par;
555
                    gpa->par = cur;
556
                    par->par = cur;
557
 
558
                    /*
559
                     * Repair tree pointer which points to the current node and do the next step.
560
                     */
561
                    *gpapar = cur;
562
                    gpa = cur->par;
563
                } else {
564
                    /*
565
                     * RR rotation
566
                     */
567
 
568
                    gpa->rgt = par->lft;
569
                    gpa->rgt_height = par->lft_height;
570
                    if (par->lft) par->lft->par = gpa;
571
                    par->lft = gpa;
572
 
573
                    /*
574
                     * Repair paternity.
575
                     */
576
                    par->par = gpa->par;
577
                    gpa->par = par;
578
 
579
                    /*
580
                     * Repair balances.
581
                     */
582
                    balance = par->rgt_height - par->lft_height;
583
                    par->lft_height++;
584
 
585
                    /*
586
                     * Repair tree pointer which points to the current node, ends when tree is balanced
587
                     * or do the next step.
588
                     */
589
                    *gpapar = par;
590
                    if (balance == 0) break;
591
                    gpa = par->par;
592
                }
593
            } else {
594
                /*
595
                 * Current node is balanced - perform balance check of its parent.
596
                 */
597
                gpa = gpa->par;
598
            }
599
        } else {
600
            /*
601
             * Balance right son.
602
             */
603
            gpa->rgt_height--;
604
            balance = gpa->rgt_height - gpa->lft_height;
605
            if (balance == -1) {
606
                /*
607
                 * Stop balancing, tree might be balanced or not, whole tree is repaired only during insertion.
608
                 */
609
                break;
610
            } else if (balance == -2) {
611
                /*
612
                 * Balance was corrupted - must be repaired.
613
                 */
614
                par = gpa->lft;
615
 
616
                if ((par->rgt_height - par->lft_height) >= +1) {
617
                    /*
618
                     * If balance is -2 then par node always exists.
619
                     */
620
                    if ((gpa->lft_height - (extavltree_tree_height(par))) == 1) {
621
                        /*
622
                         * LR rotation. Height of par subtree is not decreased due to timeout operation.
623
                         */
624
 
625
                        cur = par->rgt;
626
                        par->rgt = cur->lft;
627
                        cur->lft = par;
628
                        gpa->lft = cur->rgt;
629
                        cur->rgt = gpa;
630
 
631
                        /*
632
                         * Repair balances.
633
                         */                    
634
                        par->rgt_height = cur->lft_height;
635
                        gpa->lft_height = cur->rgt_height;
636
                        cur->rgt_height = gpa->rgt_height + 1;
637
                        cur->lft_height = extavltree_tree_height(par) + 1;
638
 
639
                        /*
640
                         * Repair paternity.
641
                         */
642
                        if (gpa->lft) gpa->lft->par = gpa;
643
                        if (par->rgt) par->rgt->par = par;
644
                        cur->par = gpa->par;
645
                        gpa->par = cur;
646
                        par->par = cur;
647
 
648
                        /*
649
                         * Repair tree pointer which points to the current node and do the next step.
650
                         */
651
                        *gpapar = cur;
652
                        gpa = cur->par;
653
                    } else {
654
                            /*
655
                         * Left subtree of cur has been already decreased by timeout operation.
656
                         */
657
                        gpa = gpa->par;
658
                    }
659
                } else {
660
                    /*
661
                     * LL rotation.
662
                     */
663
 
664
                    int prevlftheight = gpa->lft_height;
665
                    gpa->lft = par->rgt;
666
                    gpa->lft_height = par->rgt_height;
667
                    if (par->rgt) par->rgt->par = gpa;
668
                    par->rgt = gpa;
669
 
670
                    /*
671
                     * Repair paternity.
672
                     */
673
                    par->par = gpa->par;
674
                    gpa->par = par;
675
 
676
                    /*
677
                     * Repair height.
678
                     */
679
                    balance = par->rgt_height - par->lft_height;
680
                    par->rgt_height = extavltree_tree_height(gpa) + 1;
681
 
682
                    /*
683
                     * Repair tree pointer which points to the current node, ends when heights in par nodes are
684
                     * balanced and height of par subtree wasn't decreased due to timeout operation orr do
685
                     * the next step.
686
                     */
687
                    *gpapar = par; 
688
                    if (balance == 0 && par->rgt_height == prevlftheight) return;
689
                    gpa = par->par;
690
                }
691
            } else {
692
                /*
693
                 * Current node is balanced - perform balance check of its parent.
694
                 */
695
                gpa = gpa->par;
696
            }
697
        }
698
        /*
699
         * When root is reached then end balancing.
700
         */
701
        if (!gpa) return;
702
 
703
        dir = dir2;
704
    }
705
}
706
 
707
 
2450 mencl 708
/** Delete node from ExtAVL tree with the smallest key.
2416 mencl 709
 *
710
 * @param t ExtAVL tree structure.
711
 */
712
bool extavltree_delete_min(extavltree_t *t)
713
{
714
    extavltree_node_t *expnode;
715
 
716
    ASSERT(t);
717
 
718
    expnode = t->head.next;
719
 
720
    if (&t->head == expnode) return false;
721
 
722
    if (expnode->key != expnode->next->key) {
723
        /*
724
         * Repair tree data structure.
725
         */
726
        if (!expnode->par) {
727
            /*
728
             * Delete root node which musn't have left son.
729
             */
730
 
731
            ASSERT(!expnode->lft);
732
            t->root = expnode->rgt;
733
            if (expnode->rgt) expnode->rgt->par = NULL;
734
        } else if (expnode->rgt) {
735
            /*
736
             * Always delete parent of left son.
737
             */
738
 
739
            expnode->rgt->par = expnode->par;
740
            expnode->par->lft = expnode->rgt;
741
            expnode->par->lft_height = expnode->rgt_height;
742
        } else {
743
            /*
744
             * Deleted node doesn't have right son.
745
             */
746
 
747
            expnode->par->lft = NULL;
748
            expnode->par->lft_height = 0;
749
        }
2431 mencl 750
    } else if (expnode->next == &t->head) {
751
        /*
752
         * Special case of deleting last node with key equal 0.
753
         */
754
        t->root = NULL;
2416 mencl 755
    }
2450 mencl 756
 
2416 mencl 757
    /*
758
     * Delete node from the list.
759
     */
760
    t->head.next = expnode->next;
761
    expnode->next->prev = &t->head;
762
 
763
    return true;
764
}