Changeset 813

Show
Ignore:
Timestamp:
07/13/07 13:14:28 (1 year ago)
Author:
alo
Message:

--

Files:

Legend:

Unmodified
Added
Removed
Modified
Copied
Moved

  • cherokee/trunk/ChangeLog

    r812 r813  
     12007-07-13  Alvaro Lopez Ortega  <alvaro@alobbs.com> 
     2 
     3        * cherokee/avl.c: Many changes. It should be working much better 
     4        now. For instance, it's no longer recursive. 
    15 
    262007-07-12  A.D.F  <adefacc@tin.it> 

  • cherokee/trunk/cherokee/avl.c

    r808 r813  
    2626#include "avl.h" 
    2727 
     28#define MAX_HEIGHT 45 
     29 
     30 
    2831struct cherokee_avl_node {          
    2932        /* Tree */ 
    …… 
    3134        struct cherokee_avl_node *left; 
    3235        struct cherokee_avl_node *right; 
     36        cherokee_boolean_t        left_child; 
     37        cherokee_boolean_t        right_child; 
    3338 
    3439        /* Info */ 
    …… 
    4146 */ 
    4247static ret_t  
    43 cherokee_avl_node_init (cherokee_avl_node_t *node) 
    44 { 
    45         node->balance = 0; 
    46         node->left    = NULL; 
    47         node->right   = NULL; 
    48         node->value   = NULL; 
     48cherokee_avl_node_init (cherokee_avl_node_t *node, cherokee_buffer_t *key, void *value) 
     49{ 
     50        node->balance     = 0; 
     51        node->left        = NULL; 
     52        node->right       = NULL; 
     53        node->left_child  = false; 
     54        node->right_child = false; 
     55        node->value       = value; 
    4956 
    5057        cherokee_buffer_init (&node->id); 
     58        cherokee_buffer_add_buffer (&node->id, key); 
    5159        return ret_ok; 
    5260} 
    …… 
    8997} 
    9098 
    91 ret_t 
    92 find_smallest_child (cherokee_avl_node_t *root, cherokee_avl_node_t **ret_parent_node, cherokee_avl_node_t **ret_node) 
    93 { 
    94         cherokee_avl_node_t *node   = root; 
    95         cherokee_avl_node_t *parent = NULL; 
    96  
    97         while (node->left != NULL) { 
    98                 parent = node; 
    99                 node = node->left; 
    100         } 
    101             
    102         *ret_node        = node; 
    103         *ret_parent_node = parent; 
    104  
    105         return ret_ok; 
    106 } 
    107  
    108 ret_t 
    109 find_biggest_child (cherokee_avl_node_t *root, cherokee_avl_node_t **ret_parent_node, cherokee_avl_node_t **ret_node) 
    110 { 
    111         cherokee_avl_node_t *node   = root; 
    112         cherokee_avl_node_t *parent = NULL; 
    113  
    114         while (node->right != NULL) { 
    115                 parent = node; 
    116                 node = node->right; 
    117         } 
    118             
    119         *ret_node        = node; 
    120         *ret_parent_node = parent; 
    121  
    122         return ret_ok; 
    123 } 
    124  
    125  
    126 ret_t  
    127 find_parent_node (cherokee_avl_t *avl, cherokee_buffer_t *key, cherokee_avl_node_t **ret_parent_node, cherokee_avl_node_t **ret_node) 
    128 { 
    129         int                  re; 
    130         cherokee_avl_node_t *node        = avl->root; 
    131         cherokee_avl_node_t *parent_node = NULL; 
    132  
    133         /* It is empty 
    134          */ 
    135         if (node == NULL) 
    136                 return ret_not_found; 
    137             
    138         /* If it's the top node 
    139          */ 
    140         if (compare_buffers (&node->id, key) == 0) { 
    141                 *ret_parent_node = NULL; 
    142                 *ret_node = node; 
    143                 return ret_ok; 
    144         } 
    145  
    146         while (node != NULL) { 
    147                 re = compare_buffers (&node->id, key); 
    148                           
    149                 if (re < 0) { 
    150                         parent_node = node; 
    151                         node = node->left; 
    152                 } else if (re > 0) { 
    153                         parent_node = node; 
    154                         node = node->right; 
    155                 } else { 
    156                         *ret_node = node; 
    157                         *ret_parent_node = parent_node; 
    158                         return ret_ok; 
    159                 } 
    160         } 
    161         return ret_not_found; 
    162 } 
    163  
    164  
    165 ret_t  
    166 find_node (cherokee_avl_t *avl, cherokee_buffer_t *key, cherokee_avl_node_t **ret_node) 
    167 { 
    168         cherokee_avl_node_t *ignored_parent; 
    169         return find_parent_node (avl, key, &ignored_parent, ret_node); 
    170 } 
    171  
    172  
    173 ret_t  
    174 cherokee_avl_get (cherokee_avl_t *avl, cherokee_buffer_t *key, void **value) 
    175 { 
    176         ret_t                ret; 
    177         cherokee_avl_node_t *ret_node = NULL; 
    178  
    179         ret = find_node (avl, key, &ret_node); 
    180         if (ret != ret_ok)  
    181                 return ret; 
    182         if (ret_node == NULL) 
    183                 return ret_error; 
    184  
    185         *value = ret_node->value; 
    186         return ret_ok; 
    187 } 
     99 
     100static cherokee_avl_node_t * 
     101node_prev (cherokee_avl_node_t *node) 
     102{ 
     103        cherokee_avl_node_t *tmp = node->left; 
     104 
     105        if (node->left_child) 
     106                while (tmp->right_child) 
     107                        tmp = tmp->right; 
     108        return tmp; 
     109} 
     110 
     111static cherokee_avl_node_t * 
     112node_first (cherokee_avl_t *avl) 
     113{ 
     114        cherokee_avl_node_t *tmp; 
     115 
     116        if (!avl->root) 
     117                return NULL; 
     118 
     119        tmp = avl->root; 
     120 
     121        while (tmp->left_child) 
     122                tmp = tmp->left; 
     123 
     124        return tmp; 
     125} 
     126 
     127static cherokee_avl_node_t * 
     128node_next (cherokee_avl_node_t *node) 
     129{ 
     130        cherokee_avl_node_t *tmp = node->right; 
     131 
     132        if (node->right_child) 
     133                while (tmp->left_child) 
     134                        tmp = tmp->left; 
     135        return tmp; 
     136} 
     137 
     138static cherokee_avl_node_t * 
     139node_rotate_left (cherokee_avl_node_t *node) 
     140{ 
     141        cherokee_avl_node_t *right; 
     142        cint_t               a_bal; 
     143        cint_t               b_bal; 
     144   
     145        right = node->right; 
     146 
     147        if (right->left_child) 
     148                node->right = right->left; 
     149        else { 
     150                node->right_child = FALSE; 
     151                node->right = right; 
     152                right->left_child = TRUE; 
     153        } 
     154        right->left = node; 
     155 
     156        a_bal = node->balance; 
     157        b_bal = right->balance; 
     158 
     159        if (b_bal <= 0) { 
     160                if (a_bal >= 1) 
     161                        right->balance = b_bal - 1; 
     162                else 
     163                        right->balance = a_bal + b_bal - 2; 
     164                node->balance = a_bal - 1; 
     165        } else { 
     166                if (a_bal <= b_bal) 
     167                        right->balance = a_bal - 2; 
     168                else 
     169                        right->balance = b_bal - 1; 
     170                node->balance = a_bal - b_bal - 1; 
     171        } 
     172 
     173        return right; 
     174} 
     175 
     176static cherokee_avl_node_t * 
     177node_rotate_right (cherokee_avl_node_t *node) 
     178{ 
     179        cherokee_avl_node_t *left; 
     180        cint_t               a_bal; 
     181        cint_t               b_bal; 
     182 
     183        left = node->left; 
     184         
     185        if (left->right_child) 
     186                node->left = left->right; 
     187        else { 
     188                node->left_child = FALSE; 
     189                node->left = left; 
     190                left->right_child = TRUE; 
     191        } 
     192        left->right = node; 
     193 
     194        a_bal = node->balance; 
     195        b_bal = left->balance; 
     196 
     197        if (b_bal <= 0) { 
     198                if (b_bal > a_bal) 
     199                        left->balance = b_bal + 1; 
     200                else 
     201                        left->balance = a_bal + 2; 
     202                node->balance = a_bal - b_bal + 1; 
     203        } else { 
     204                if (a_bal <= -1) 
     205                        left->balance = b_bal + 1; 
     206                else 
     207                        left->balance = a_bal + b_bal + 2; 
     208                node->balance = a_bal + 1; 
     209        } 
     210 
     211        return left; 
     212} 
     213 
     214 
     215static cherokee_avl_node_t * 
     216node_balance (cherokee_avl_node_t *node) 
     217{ 
     218        if (node->balance < -1) { 
     219                if (node->left->balance > 0) 
     220                        node->left = node_rotate_left (node->left); 
     221                node = node_rotate_right (node); 
     222 
     223        } else if (node->balance > 1) { 
     224                if (node->right->balance < 0) 
     225                        node->right = node_rotate_right (node->right); 
     226                node = node_rotate_left (node); 
     227        } 
     228 
     229        return node; 
     230} 
     231 
    188232 
    189233 
    190234static void 
    191 rotate_right_once (cherokee_avl_node_t **root) 
    192 { 
    193         cherokee_avl_node_t *A = *root; 
    194         cherokee_avl_node_t *B = (*root)->left; 
    195  
    196         A->left = B->right; 
    197         B->right = A; 
    198         *root = B; 
    199         A->balance = 0; 
    200         B->balance = 0; 
    201 } 
    202  
    203 static void 
    204 rotate_left_once (cherokee_avl_node_t **root) 
    205 { 
    206         cherokee_avl_node_t *A = *root; 
    207         cherokee_avl_node_t *B = (*root)->right; 
    208  
    209         A->right = B->left; 
    210         B->left = A; 
    211         *root = B; 
    212         A->balance = 0; 
    213         B->balance = 0; 
    214 } 
    215  
    216 static void 
    217 rotate_right_twice (cherokee_avl_node_t **root) 
    218 { 
    219         cherokee_avl_node_t *A = *root; 
    220         cherokee_avl_node_t *B = (*root)->left; 
    221  
    222         *root = B->right; 
    223         B->right = (*root)->left; 
    224         A->left = (*root)->right; 
    225         (*root)->left = B; 
    226         (*root)->right = A; 
    227  
    228         switch ((*root)->balance) { 
    229         case -1: 
    230                 A->balance = 1; 
    231                 B->balance = 0; 
    232                 break; 
    233         case  0: 
    234                 A->balance = 0; 
    235                 B->balance = 0; 
    236                 break; 
    237         case  1: 
    238                 A->balance = 0; 
    239                 B->balance = -1; 
    240                 break; 
    241         } 
    242         (*root)->balance = 0; 
    243 } 
    244  
    245 static void 
    246 rotate_left_twice (cherokee_avl_node_t **root) 
    247 { 
    248         cherokee_avl_node_t *A = *root; 
    249         cherokee_avl_node_t *B = (*root)->right; 
    250  
    251         *root = B->left; 
    252         B->left = (*root)->right; 
    253         A->right = (*root)->left; 
    254         (*root)->left = A; 
    255         (*root)->right = B; 
    256  
    257         switch ((*root)->balance) { 
    258         case -1: 
    259                 A->balance = 0; 
    260                 B->balance = 1; 
    261                 break; 
    262         case  0: 
    263                 A->balance = 0; 
    264                 B->balance = 0; 
    265                 break; 
    266         case  1: 
    267                 A->balance = -1; 
    268                 B->balance = 0; 
    269                 break; 
    270         } 
    271         (*root)->balance = 0; 
    272 } 
    273  
    274  
    275 static cherokee_boolean_t 
    276 balance (cherokee_avl_node_t **root) 
    277 { 
    278         switch ((*root)->balance) { 
    279         case 0:  /* no height increase */ 
    280                 return false; 
    281         case  1: 
    282         case -1: /* height increase */ 
    283                 return true; 
    284  
    285         case -2: 
    286                 if ((*root)->left->balance <= 0)  
    287                         rotate_right_once (root); 
    288                 else 
    289                         rotate_right_twice (root); 
    290                 break; 
    291  
    292         case 2: 
    293                 if ((*root)->right->balance >= 0) 
    294                         rotate_left_once (root); 
    295                 else  
    296                         rotate_left_twice (root); 
    297                 break; 
    298  
    299         default: 
    300                 SHOULDNT_HAPPEN; 
    301         } 
    302  
    303         return false; 
    304 } 
    305  
    306  
    307 /* Return:  
    308  *  TRUE  - if the tree height has increased 
    309  *  FALSE - otherwise 
    310  *     -1 - error 
    311  */ 
    312 static int 
    313 add_node (cherokee_avl_node_t **root, cherokee_avl_node_t *node) 
    314 { 
    315         int                re; 
    316         cherokee_boolean_t grew; 
     235node_add (cherokee_avl_t *tree, cherokee_avl_node_t *child) 
     236{ 
     237        short                re;                  
     238        cherokee_boolean_t   is_left; 
     239        cherokee_avl_node_t *path[MAX_HEIGHT]; 
     240        cherokee_avl_node_t *node   = tree->root; 
     241        cherokee_avl_node_t *parent = NULL;; 
     242        cint_t               idx    = 1; 
     243 
     244        path[0] = NULL; 
    317245 
    318246        /* If the tree is empty.. 
    319247         */ 
    320         if (*root == NULL) { 
    321                 *root = node; 
    322                 return true; 
    323         } 
    324  
    325         /* Comparet the key 
     248        if (tree->root == NULL) { 
     249                tree->root = child; 
     250                return; 
     251        } 
     252 
     253        /* Insert the node 
    326254         */ 
    327         re = compare_buffers (&(*root)->id, &node->id); 
    328         if (re < 0) { 
    329                 /* Insert it on the left */ 
    330                 grew = add_node (&(*root)->left, node); 
    331                 if (grew) { 
    332                         (*root)->balance--; 
    333                         return balance (root); 
    334                 } 
    335         } else if (re > 0) { 
    336                 /* Insert it on the right */ 
    337                 grew = add_node (&(*root)->right, node); 
    338                 if (grew) { 
    339                         (*root)->balance++; 
    340                         return balance (root); 
    341                 } 
    342         } else { 
    343                 return -1; 
    344         } 
    345  
    346         return false; 
     255        while (true) { 
     256                re = compare_buffers (&child->id, &node->id); 
     257 
     258                if (re < 0) { 
     259                        /* Insert it on the left */ 
     260                        if (node->left_child) { 
     261                                path[idx++] = node; 
     262                                node        = node->left; 
     263                        } else { 
     264                                child->left      = node->left; 
     265                                child->right     = node; 
     266                                node->left       = child; 
     267                                node->left_child = true; 
     268                                node->balance   -= 1; 
     269                                break; 
     270                        } 
     271 
     272                } else if (re > 0) { 
     273                        /* Insert it on the left */ 
     274                        if (node->right_child) { 
     275                                path[idx++] = node; 
     276                                node        = node->right; 
     277                        } else { 
     278                                child->right      = node->right; 
     279                                child->left       = node; 
     280                                node->right       = child; 
     281                                node->right_child = true; 
     282                                node->balance    += 1; 
     283                                break; 
     284                        } 
     285 
     286                } else { 
     287                        cherokee_avl_node_mrproper (child); 
     288                        free (child); 
     289                        return; 
     290                } 
     291        } 
     292 
     293        /* Rebalance the tree 
     294         */ 
     295        while (true) { 
     296                parent = path[--idx]; 
     297                is_left = (parent && (parent->left == node)); 
     298                 
     299                if ((node->balance < -1) || 
     300                    (node->balance >  1))  
     301                { 
     302                        node = node_balance (node); 
     303                        if (parent == NULL)  
     304                                tree->root = node; 
     305                        else if (is_left)  
     306                                parent->left = node; 
     307                        else 
     308                                parent->right = node; 
     309                } 
     310 
     311                if ((node->balance == 0) || (parent == NULL)) 
     312                        break; 
     313                 
     314                if (is_left) 
     315                        parent->balance -= 1; 
     316                else 
     317                        parent->balance += 1; 
     318                 
     319                node = parent; 
     320        } 
    347321} 
    348322 
    …… 
    351325cherokee_avl_add (cherokee_avl_t *avl, cherokee_buffer_t *key, void *value) 
    352326{ 
    353         int   re; 
    354327        ret_t ret; 
    355328        CHEROKEE_NEW_STRUCT (n, avl_node); 
    …… 
    357330        /* Create the new AVL node 
    358331         */ 
    359         ret = cherokee_avl_node_init (n); 
     332        ret = cherokee_avl_node_init (n, key, value); 
    360333        if (unlikely (ret != ret_ok)) return ret; 
    361  
    362         n->value = value; 
    363         cherokee_buffer_add_buffer (&n->id, key); 
    364334 
    365335        /* Add th node to the tree 
    366336         */ 
    367         re = add_node (&avl->root, n); 
    368         if (re == -1) { 
    369                 cherokee_avl_node_mrproper (n); 
    370                 free (n); 
    371                 return ret_deny; 
    372         } 
    373  
     337        node_add (avl, n); 
    374338        return ret_ok; 
    375339} 
    …… 
    379343cherokee_avl_del (cherokee_avl_t *avl, cherokee_buffer_t *key, void **value) 
    380344{ 
    381         ret_t                 ret; 
    382         cherokee_avl_node_t  *node   = NULL; 
    383         cherokee_avl_node_t  *parent = NULL; 
    384         cherokee_avl_node_t  *tmp    = NULL; 
    385         cherokee_avl_node_t  *tmp_pa = NULL; 
    386  
    387         /* Find the node and its parent 
    388          */ 
    389         ret = find_parent_node (avl, key, &parent, &node); 
    390         if (ret != ret_ok) return ret; 
    391  
    392         /* We've got the node, read the returning value 
    393          */ 
    394         if (value) 
    395                 *value = node->value; 
    396  
    397         /* Leaf: simply elimitate it  
    398          */ 
    399         if (!node->left && !node->right) { 
    400                 if (parent == NULL) { 
    401                         avl->root = NULL; 
     345        short                re; 
     346        cherokee_boolean_t   is_left; 
     347        cherokee_avl_node_t *path[MAX_HEIGHT]; 
     348        cherokee_avl_node_t *parent; 
     349        cherokee_avl_node_t *pbalance; 
     350        cherokee_avl_node_t *node     = avl->root; 
     351        cint_t               idx      = 1; 
     352         
     353        if (avl->root == NULL) 
     354                return ret_not_found; 
     355 
     356        path[idx] = NULL; 
     357 
     358        while (true) { 
     359                re = compare_buffers (key, &node->id); 
     360                if (re == 0) 
     361                        break; 
     362                else if (re < 0) { 
     363                        if (!node->left_child) 
     364                                return ret_not_found; 
     365                        path[idx++] = node; 
     366                        node = node->left; 
     367                } else { 
     368                        if (!node->right_child) 
     369                                return ret_not_found; 
     370                        path[idx++] = node; 
     371                        node = node->right; 
     372                } 
     373        } 
     374 
     375        pbalance = path[idx-1]; 
     376        parent   = pbalance; 
     377        idx     -= 1; 
     378        is_left  = (parent && (node == parent->left)); 
     379 
     380        if (!node->left_child) { 
     381                if (!node->right_child) { 
     382                        if (!parent) 
     383                                avl->root = NULL; 
     384                        else if (is_left) { 
     385                                parent->left_child  = false; 
     386                                parent->left        = node->left; 
     387                                parent->balance   += 1; 
     388                        } else { 
     389                                parent->right_child = false; 
     390                                parent->right       = node->right; 
     391                                parent->balance     -= 1; 
     392                        } 
     393 
     394                } else { /* right child */ 
     395                        cherokee_avl_node_t *tmp = node_next (node); 
     396                        tmp->left = node->left; 
     397 
     398                        if (!parent) 
     399                                avl->root = node->right; 
     400                        else if (is_left) { 
     401                                parent->left     = node->right; 
     402                                parent->balance += 1; 
     403                        } else { 
     404                                parent->right    = node->right; 
     405                                parent->balance -= 1; 
     406                        } 
     407                } 
     408 
     409        } else { /* left child */ 
     410                if (!node->right_child) { 
     411                        cherokee_avl_node_t *tmp = node_prev(node); 
     412                        tmp->right = node->right; 
     413 
     414                        if (parent == NULL) 
     415                                avl->root = node->left; 
     416                        else if (is_left) { 
     417                                parent->left     = node->left; 
     418                                parent->balance += 1; 
     419                        } else { 
     420                                parent->right    = node->left; 
     421                                parent->balance -= 1; 
     422                        } 
     423                } else { /* both children */ 
     424                        cherokee_avl_node_t *prev    = node->left; 
     425                        cherokee_avl_node_t *next    = node->right; 
     426                        cherokee_avl_node_t *nextp   = node; 
     427                        cint_t               old_idx = idx + 1; 
     428                        idx++; 
     429 
     430                        /* find the immediately next node (and its parent) */ 
     431                        while (next->left_child) { 
     432                                path[++idx] = nextp = next; 
     433                                next = next->left; 
     434                        } 
     435           
     436                        path[old_idx] = next; 
     437                        pbalance      = path[idx]; 
     438           
     439                        /* remove 'next' from the tree */ 
     440                        if (nextp != node) { 
     441                                if (next->right_child) 
     442                                        nextp->left = next->right; 
     443                                else 
     444                                        nextp->left_child = FALSE; 
     445 
     446                                nextp->balance    += 1; 
     447                                next->right_child  = TRUE; 
     448                                next->right        = node->right; 
     449 
     450                        } else { 
     451                                node->balance -= 1; 
     452                        } 
     453             
     454                        /* set the prev to point to the right place */ 
     455                        while (prev->right_child) 
     456                                prev = prev->right; 
     457                        prev->right = next; 
     458             
     459                        /* prepare 'next' to replace 'node' */ 
     460                        next->left_child = TRUE; 
     461                        next->left = node->left; 
     462                        next->balance = node->balance; 
     463           
     464                        if (!parent) 
     465                                avl->root = next; 
     466                        else if (is_left) 
     467                                parent->left = next; 
     468                        else 
     469                                parent->right = next; 
     470                } 
     471        }  
     472         
     473        /* restore balance */ 
     474        if (pbalance) { 
     475                while (true) { 
     476                        cherokee_avl_node_t *bparent = path[--idx]; 
     477                        is_left = (bparent && (pbalance == bparent->left)); 
     478                               
     479                        if(pbalance->balance < -1 || pbalance->balance > 1) { 
     480                                pbalance = node_balance (pbalance);  
     481                                if (!bparent) 
     482                                        avl->root = pbalance; 
     483                                else if (is_left) 
     484                                        bparent->left = pbalance; 
     485                                else 
     486                                        bparent->right = pbalance; 
     487                        } 
     488         
     489                        if (pbalance->balance != 0 || !bparent) 
     490                                break; 
     491         
     492                        if (is_left) 
     493                                bparent->balance += 1; 
     494                        else 
     495                                bparent->balance -= 1; 
     496                         
     497                        pbalance = bparent; 
     498                } 
     499        } 
     500         
     501        return ret_ok; 
     502} 
     503 
     504 
     505ret_t  
     506cherokee_avl_get (cherokee_avl_t *avl, cherokee_buffer_t *key, void **value) 
     507{ 
     508        short                re; 
     509        cherokee_avl_node_t *node; 
     510         
     511        node = avl->root; 
     512        if (!node) 
     513                return ret_not_found; 
     514 
     515        while (true) { 
     516                re = compare_buffers (key, &node->id); 
     517                if (re == 0) { 
     518                        if (value) 
     519                                *value = node->value; 
    402520                        return ret_ok; 
    403                 } 
    404  
    405                 if (parent->left == node) { 
    406                         parent->left = NULL; 
    407                         parent->balance++; 
    408  
    409                 } else if (parent->right == node) { 
    410                         parent->right = NULL; 
    411                         parent->balance--; 
    412                 } 
    413  
    414                 return ret_ok; 
    415         } 
    416  
    417         /* If it has only one child 
    418          */ 
    419         if (node->left && !node->right) { 
    420                 tmp = node->left; 
    421  
    422         } else if (!node->left && node->right) { 
    423                 tmp = node->right; 
    424         } 
    425  
    426         if (tmp) { 
    427  
    428                 if (parent->left == node) { 
    429                         parent->left = tmp; 
    430                 } else if (parent->right == node) { 
    431                         parent->right = tmp; 
    432                 } 
    433  
    434                 return ret_ok; 
    435         } 
    436  
    437         /* In the case it has more two child 
    438          */ 
    439         if (node->balance < 0) { 
    440                 ret = find_smallest_child (node, &tmp, &tmp_pa); 
    441         } else { 
    442                 ret = find_biggest_child (node, &tmp, &tmp_pa); 
    443         } 
    444         if (ret != ret_ok) { 
    445                 SHOULDNT_HAPPEN; 
    446                 return ret; 
    447         } 
    448  
    449         /* Remove the node */ 
    450         if (tmp_pa->left == tmp) { 
    451                 tmp_pa->left = NULL; 
    452                 parent->balance++; 
    453         } else { 
    454                 tmp_pa->right = NULL; 
    455                 parent->balance--; 
    456         } 
    457  
    458         /* Put it in place */ 
    459         if (parent->left == node) { 
    460                 parent->left = tmp; 
    461         } else { 
    462                 parent->right = tmp; 
    463         } 
    464  
    465         return ret_ok; 
     521 
     522                } else if (re < 0) { 
     523                        if (!node->left_child) 
     524                                return ret_not_found; 
     525                        node = node->left; 
     526 
     527                } else { 
     528                        if (!node->right_child) 
     529                                return ret_not_found; 
     530                        node = node->right; 
     531                } 
     532        } 
     533 
     534        SHOULDNT_HAPPEN; 
     535        return ret_error; 
    466536} 
    467537 
    …… 
    471541 
    472542ret_t  
    473 while_node (cherokee_avl_node_t *node, cherokee_avl_while_func_t func, void *param, cherokee_buffer_t **key, void **value) 
    474 { 
    475         ret_t ret; 
    476  
    477         if (node == NULL)  
     543cherokee_avl_while (cherokee_avl_t *avl, cherokee_avl_while_func_t func, void *param, cherokee_buffer_t **key, void **value) 
     544{ 
     545        ret_t                ret; 
     546        cherokee_avl_node_t *node = avl->root; 
     547 
     548        if (avl->root == NULL)  
    478549                return ret_ok; 
    479550 
    480         /* Returning values 
    481          */ 
    482         if (key)  
    483                 *key = &node->id; 
    484         if (value) 
    485                 *value = &node->value; 
    486  
    487         /* Walk the children 
    488          */ 
    489         if (node->right)  { 
    490                 ret = while_node (node->right, func, param, key, value); 
     551        node = node_first (avl); 
     552        while (node) { 
     553                if (key)  
     554                        *key = &node->id; 
     555                if (value) 
     556                        *value = &node->value; 
     557 
     558                ret = func (&node->id, node->value, param); 
    491559                if (ret != ret_ok) return ret; 
    492         } 
    493  
    494         ret = func (&node->id, node->value, param); 
    495         if (ret != ret_ok) return ret; 
    496  
    497         if (node->left)  { 
    498                 ret = while_node (node->left, func, param, key, value); 
    499                 if (ret != ret_ok) return ret; 
    500         } 
    501             
    502         return ret_ok; 
    503 } 
    504  
    505 ret_t  
    506 cherokee_avl_while (cherokee_avl_t *avl, cherokee_avl_while_func_t func, void *param, cherokee_buffer_t **key, void **value) 
    507 { 
    508         return while_node (avl->root, func, param, key, value); 
     560       
     561                node = node_next (node); 
     562        } 
     563 
     564        return ret_ok; 
    509565} 
    510566 
    …… 
    522578        return cherokee_avl_while (avl, cherokee_avl_len_each, len, NULL, NULL); 
    523579} 
    524  
    525  
    526580 
    527581 
    …… 
    538592 
    539593        printf ("<node key=\"%s\" value=\"%p\">\n", node->id.buf, node->value); 
    540         print_node (node->left);   
    541         print_node (node->right);  
     594        if (node->left_child) 
     595                print_node (node->left);   
     596        if (node->left_child) 
     597                print_node (node->right);  
    542598        printf ("</node>\n"); 
    543599} 
    544600 
    545  
    546601ret_t  
    547602cherokee_avl_print (cherokee_avl_t *avl) 
    548603{ 
    549         /* TIP: Pipe the output of this method through Tidy to 
    550          * reindent the tree. Eg: ./whatever | tidy -i -xml -q 
    551          */ 
    552604        print_node (avl->root); 
    553605        return ret_ok; 
    …… 
    555607 
    556608 
     609static cint_t 
     610node_height (cherokee_avl_node_t *node) 
     611{ 
     612        cint_t left_height; 
     613        cint_t right_height; 
     614 
     615        if (node) { 
     616                left_height = 0; 
     617                right_height = 0; 
     618 
     619                if (node->left_child) 
     620                        left_height = node_height (node->left); 
     621 
     622                if (node->right_child) 
     623                        right_height = node_height (node->right); 
     624 
     625                return MAX (left_height, right_height) + 1; 
     626        } 
     627        return 0; 
     628} 
     629 
     630 
    557631static ret_t 
    558 check_node (cherokee_avl_node_t *node)  
    559 { 
    560         int re; 
    561  
    562         /* Empty */ 
    563         if (node == NULL) 
    564                 return ret_ok; 
    565  
    566         /* No child */ 
    567         if ((node->left == NULL) && 
    568             (node->right == NULL)) 
    569                 return ret_ok; 
    570  
    571         /* Check order */ 
    572         if (node->left) { 
    573                 re = compare_buffers (&node->id, &node->left->id); 
    574                 if (re >= 0) { 
    575                         PRINT_ERROR ("Invalid link: node('%s') -> node('%s')\n", 
    576                                      node->id.buf, node->left->id.buf); 
    577                 } 
    578         } 
    579  
    580         if (node->right) { 
    581                 re = compare_buffers (&node->id, &node->left->id); 
    582                 if (re <= 0) { 
    583                         PRINT_ERROR ("Invalid link: node('%s') -> node('%s')\n", 
    584                                      node->id.buf, node->right->id.buf); 
    585                 } 
    586         } 
    587  
    588         /* Check balance */ 
    589         if (( node->left &&  node->right && (node->balance !=  0)) || 
    590             (!node->left &&  node->right && (node->balance !=  1)) || 
    591             ( node->left && !node->right && (node->balance != -1))) 
    592         { 
    593                 PRINT_ERROR ("Wrong balance=%d at '%s'\n", node->balance, node->id.buf); 
    594         } 
    595  
     632node_check (cherokee_avl_node_t *node)  
     633{ 
     634        cint_t               left_height; 
     635        cint_t               right_height; 
     636        cint_t               balance; 
     637        cherokee_avl_node_t *tmp; 
     638 
     639        if (node) { 
     640                if (node->left_child) { 
     641                        tmp = node_prev (node); 
     642                        if (tmp->right != node) { 
     643                                PRINT_ERROR_S ("previous"); 
     644                                return ret_error; 
     645                        } 
     646