Changeset 804

Show
Ignore:
Timestamp:
07/11/07 00:56:14 (1 year ago)
Author:
alo
Message:

--

Files:

Legend:

Unmodified
Added
Removed
Modified
Copied
Moved

  • cherokee/trunk/ChangeLog

    r803 r804  
     12007-07-11  Alvaro Lopez Ortega  <alvaro@alobbs.com> 
     2 
     3        * cherokee/table.c: Adapted to use the new AVL class. There are a 
     4        few temporal methods that need to be improved. I'll work on it in 
     5        the next days. 
     6 
     7        * cherokee/avl.c, cherokee/avl.h: Rewritten from scratch. It uses 
     8        cherokee_buffer_t's as the index of the nodes, so it should be 
     9        slightly faster than the previous implementation. 
     10 
     11        * cherokee/connection.c (cherokee_connection_setup_error_handler): 
     12        It is safer to return ret_ok instead of ret in this case. Fixed. 
     13 
    1142007-07-10  A.D.F  <adefacc@tin.it> 
    215 

  • cherokee/trunk/cherokee/avl.c

    r745 r804  
    11/* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */ 
    22 
    3 /* 
    4  * Copyright (C) 1995-1997 by Sam Rushing <rushing@nightmare.com> 
    5  * Copyright (C) 2005 by Germanischer Lloyd AG 
    6  * Copyright (C) 2001-2005 by IronPort Systems, Inc. 
    7  * Copyright (C) 2006 Alvaro Lopez Ortega <alvaro@alobbs.com> 
     3/* Cherokee 
    84 * 
    9  *                         All Rights Reserved 
     5 * Authors: 
     6 *      Alvaro Lopez Ortega <alvaro@alobbs.com> 
    107 * 
    11  * Permission to use, copy, modify, and distribute this software and 
    12  * its documentation for any purpose and without fee is hereby 
    13  * granted, provided that the above copyright notice appear in all 
    14  * copies and that both that copyright notice and this permission 
    15  * notice appear in supporting documentation, and that the name of Sam 
    16  * Rushing not be used in advertising or publicity pertaining to 
    17  * distribution of the software without specific, written prior 
    18  * permission. 
     8 * Copyright (C) 2001-2007 Alvaro Lopez Ortega 
    199 * 
    20  * SAM RUSHING DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, 
    21  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN 
    22  * NO EVENT SHALL SAM RUSHING BE LIABLE FOR ANY SPECIAL, INDIRECT OR 
    23  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS 
    24  * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, 
    25  * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN 
    26  * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 
     10 * This program is free software; you can redistribute it and/or 
     11 * modify it under the terms of version 2 of the GNU General Public 
     12 * License as published by the Free Software Foundation. 
    2713 * 
    28  */ 
    29  
    30 /* 
    31  * This is a fairly straightfoward translation of a prototype 
    32  * written in python, 'avl_tree.py'. Read that file first. 
     14 * This program is distributed in the hope that it will be useful, 
     15 * but WITHOUT ANY WARRANTY; without even the implied warranty of 
     16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the 
     17 * GNU General Public License for more details. 
     18 * 
     19 * You should have received a copy of the GNU General Public License 
     20 * along with this program; if not, write to the Free Software 
     21 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 
     22 * USA 
    3323 */ 
    3424 
    …… 
    3626#include "avl.h" 
    3727 
    38 avl_node * 
    39 avl_new_avl_node (void *key, void *value, avl_node *parent) 
    40 { 
    41         avl_node * node; 
    42  
    43         node = (avl_node *) malloc (sizeof (avl_node)); 
    44         if (unlikely (node == NULL)) return NULL; 
    45  
    46         node->parent = parent; 
    47         node->key = key; 
    48         node->value = value; 
    49         node->left = NULL; 
    50         node->right = NULL; 
    51  
    52         AVL_SET_BALANCE (node, 0); 
    53         AVL_SET_RANK (node, 1); 
    54  
    55         return node; 
    56 } 
    57  
    58  
    59 avl_tree * 
    60 avl_new_avl_tree (avl_key_compare_fun_type compare_fun, void *compare_arg) 
    61 { 
    62         avl_tree *t; 
    63         avl_node *root; 
    64  
    65         t = (avl_tree *) malloc (sizeof (avl_tree)); 
    66         if (unlikely (t == NULL)) return NULL; 
    67  
    68         root = avl_new_avl_node(NULL, NULL, NULL); 
    69         if (root == NULL) return NULL; 
    70          
    71         t->root = root; 
    72         t->length = 0; 
    73         t->compare_fun = compare_fun; 
    74         t->compare_arg = compare_arg; 
    75  
    76         return t; 
     28struct cherokee_avl_node {          
     29           /* Tree */ 
     30           short                     balance; 
     31           struct cherokee_avl_node *left; 
     32           struct cherokee_avl_node *right; 
     33 
     34           /* Info */ 
     35           cherokee_buffer_t         id; 
     36           void                     *value; 
     37}; 
     38 
     39 
     40/* Nodes 
     41 */ 
     42static ret_t  
     43cherokee_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; 
     49 
     50           cherokee_buffer_init (&node->id); 
     51           return ret_ok; 
     52} 
     53 
     54static ret_t  
     55cherokee_avl_node_mrproper (cherokee_avl_node_t *node) 
     56{ 
     57           cherokee_buffer_mrproper (&node->id); 
     58           return ret_ok; 
     59} 
     60 
     61 
     62/* Tree 
     63 */ 
     64ret_t  
     65cherokee_avl_init (cherokee_avl_t *avl) 
     66{ 
     67           avl->root = NULL; 
     68           return ret_ok; 
     69} 
     70 
     71 
     72ret_t  
     73cherokee_avl_mrproper (cherokee_avl_t *avl) 
     74{ 
     75           return ret_ok; 
     76} 
     77 
     78 
     79static int  
     80compare_buffers (cherokee_buffer_t *A, 
     81                          cherokee_buffer_t *B) 
     82{ 
     83           if (A->len > B->len) 
     84                         return A->len - B->len; 
     85           else if (B->len > A->len) 
     86                         return - (B->len - A->len); 
     87           else 
     88                         return strcmp (A->buf, B->buf); 
     89} 
     90 
     91ret_t 
     92find_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 
     108ret_t 
     109find_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 
     126ret_t  
     127find_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 
     165ret_t  
     166find_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 
     173ret_t  
     174cherokee_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; 
    77187} 
    78188 
    79189 
    80190static void 
    81 free_avl_tree_helper (avl_node * node,  
    82                       avl_free_key_fun_type free_key_fun, 
    83                       avl_free_key_fun_type free_val_fun) 
    84 { 
    85         if (node->left)  
    86                 free_avl_tree_helper (node->left, free_key_fun, free_val_fun); 
    87          
    88         if (free_val_fun != NULL) 
    89                 free_val_fun (node->value); 
    90         free_key_fun (node->key); 
    91  
    92         if (node->right)  
    93                 free_avl_tree_helper (node->right, free_key_fun, free_val_fun); 
    94  
    95         free (node); 
    96 } 
    97  
    98 void 
    99 avl_free_avl_mrproper (avl_tree * tree,  
    100                        avl_free_key_fun_type free_key_fun, 
    101                        avl_free_key_fun_type free_val_fun) 
    102  
    103 { 
    104         if (tree->length) { 
    105                 free_avl_tree_helper (tree->root->right, free_key_fun, free_val_fun); 
    106         } 
    107         if (tree->root) { 
    108                 free (tree->root); 
    109         } 
    110 } 
    111  
    112 void 
    113 avl_free_avl_tree (avl_tree * tree, avl_free_key_fun_type free_key_fun, avl_free_key_fun_type free_val_fun) 
    114 { 
    115         avl_free_avl_mrproper (tree, free_key_fun, free_val_fun); 
    116         free (tree); 
    117 } 
    118  
    119 int 
    120 avl_insert_by_key (avl_tree *ob, void *key, void *value, unsigned int *index) 
    121 { 
    122         if (!(ob->root->right)) { 
    123                 avl_node * node = avl_new_avl_node (key, value, ob->root); 
    124                 if (!node) { 
    125                         return -1; 
    126                 } else { 
    127                         ob->root->right = node; 
    128                         ob->length = ob->length + 1; 
    129                         return 0; 
    130                 } 
    131         } else { /* not self.right == None */ 
    132                 avl_node *t, *p, *s, *q, *r; 
    133                 int a; 
    134                 int cmpa; 
    135                 *index = 0; 
    136  
    137                 t = ob->root; 
    138                 s = p = t->right; 
    139  
    140                 while (1) { 
    141                         cmpa = ob->compare_fun (ob->compare_arg, key, p->key); 
    142  
    143                         if (cmpa < 0) { 
    144                                 /* move left */ 
    145                                 AVL_SET_RANK (p, (AVL_GET_RANK (p) + 1)); 
    146                                 q = p->left; 
    147                                 if (!q) { 
    148                                         /* insert */ 
    149                                         avl_node * q_node = avl_new_avl_node (key, value, p); 
    150                                         if (!q_node) { 
    151                                                 return -1; 
    152                                         } else { 
    153                                                 q = q_node; 
    154                                                 p->left = q; 
    155                                                 break; 
    156                                         } 
    157                                 } else if (AVL_GET_BALANCE(q)) { 
    158                                         t = p; 
    159                                         s = q; 
    160                                 } 
    161                                 p = q; 
    162                         } else if (cmpa > 0) { 
    163                                 /* move right */ 
    164                                 q = p->right; 
    165                                 *index += AVL_GET_RANK(p); 
    166                                 if (!q) { 
    167                                         /* insert */ 
    168                                         avl_node * q_node = avl_new_avl_node (key, value, p); 
    169                                         if (!q_node) { 
    170                                                 return -1; 
    171                                         } else { 
    172                                                 q = q_node; 
    173                                                 p->right = q; 
    174                                                 break; 
    175                                         } 
    176                                 } else if (AVL_GET_BALANCE(q)) { 
    177                                         t = p; 
    178                                         s = q; 
    179                                 } 
    180                                 p = q; 
    181                         } else { 
    182                                 /* The element is already in the tree 
    183                                  */ 
    184                                 return -2; 
    185                         } 
    186                 } 
    187  
    188                 ob->length = ob->length + 1; 
    189  
    190                 /* adjust balance factors */ 
    191                 if (ob->compare_fun (ob->compare_arg, key, s->key) < 1) { 
    192                         r = p = s->left; 
    193                 } else { 
    194                         r = p = s->right; 
    195                 } 
    196                 while (p != q) { 
    197                         if (ob->compare_fun (ob->compare_arg, key, p->key) < 1) { 
    198                                 AVL_SET_BALANCE (p, -1); 
    199                                 p = p->left; 
    200                         } else { 
    201                                 AVL_SET_BALANCE (p, +1); 
    202                                 p = p->right; 
    203                         } 
    204                 } 
    205  
    206                 /* balancing act */ 
    207  
    208                 if (ob->compare_fun (ob->compare_arg, key, s->key) < 1) { 
    209                         a = -1; 
    210                 } else { 
    211                         a = +1; 
    212                 } 
    213  
    214                 if (AVL_GET_BALANCE (s) == 0) { 
    215                         AVL_SET_BALANCE (s, a); 
    216                         return 0; 
    217                 } else if (AVL_GET_BALANCE (s) == -a) { 
    218                         AVL_SET_BALANCE (s, 0); 
    219                         return 0; 
    220                 } else if (AVL_GET_BALANCE(s) == a) { 
    221                         if (AVL_GET_BALANCE (r) == a) { 
    222                                 /* single rotation */ 
    223                                 p = r; 
    224                                 if (a == -1) { 
    225                                         s->left = r->right; 
    226                                         if (r->right) { 
    227                                                 r->right->parent = s; 
    228                                         } 
    229                                         r->right = s; 
    230                                         s->parent = r; 
    231                                         AVL_SET_RANK (s, (AVL_GET_RANK (s) - AVL_GET_RANK (r))); 
    232                                 } else { 
    233                                         s->right = r->left; 
    234                                         if (r->left) { 
    235                                                 r->left->parent = s; 
    236                                         } 
    237                                         r->left = s; 
    238                                         s->parent = r; 
    239                                         AVL_SET_RANK (r, (AVL_GET_RANK (r) + AVL_GET_RANK (s))); 
    240                                 } 
    241                                 AVL_SET_BALANCE (s, 0); 
    242                                 AVL_SET_BALANCE (r, 0); 
    243                         } else if (AVL_GET_BALANCE (r) == -a) { 
    244                                 /* double rotation */ 
    245                                 if (a == -1) { 
    246                                         p = r->right; 
    247                                         r->right = p->left; 
    248                                         if (p->left) { 
    249                                                 p->left->parent = r; 
    250                                         } 
    251                                         p->left = r; 
    252                                         r->parent = p; 
    253                                         s->left = p->right; 
    254                                         if (p->right) { 
    255                                                 p->right->parent = s; 
    256                                         } 
    257                                         p->right = s; 
    258                                         s->parent = p; 
    259                                         AVL_SET_RANK (p, (AVL_GET_RANK (p) + AVL_GET_RANK (r))); 
    260                                         AVL_SET_RANK (s, (AVL_GET_RANK (s) - AVL_GET_RANK (p))); 
    261                                 } else { 
    262                                         p = r->left; 
    263                                         r->left = p->right; 
    264                                         if (p->right) { 
    265                                                 p->right->parent = r; 
    266                                         } 
    267                                         p->right = r; 
    268                                         r->parent = p; 
    269                                         s->right = p->left; 
    270                                         if (p->left) { 
    271                                                 p->left->parent = s; 
    272                                         } 
    273                                         p->left = s; 
    274                                         s->parent = p; 
    275                                         AVL_SET_RANK (r, (AVL_GET_RANK (r) - AVL_GET_RANK (p))); 
    276                                         AVL_SET_RANK (p, (AVL_GET_RANK (p) + AVL_GET_RANK (s))); 
    277                                 } 
    278                                 if (AVL_GET_BALANCE (p) == a) { 
    279                                         AVL_SET_BALANCE (s, -a); 
    280                                         AVL_SET_BALANCE (r, 0); 
    281                                 } else if (AVL_GET_BALANCE (p) == -a) { 
    282                                         AVL_SET_BALANCE (s, 0); 
    283                                         AVL_SET_BALANCE (r, a); 
    284                                 } else { 
    285                                         AVL_SET_BALANCE (s, 0); 
    286                                         AVL_SET_BALANCE (r, 0); 
    287                                 } 
    288                                 AVL_SET_BALANCE (p, 0); 
    289                         } 
    290                         /* finishing touch */ 
    291                         if (s == t->right) { 
    292                                 t->right = p; 
    293                         } else { 
    294                                 t->left = p; 
    295                         } 
    296                         p->parent = t; 
    297                 } 
    298         } 
    299         return 0; 
    300 } 
    301  
    302 int 
    303 avl_get_item_by_index (avl_tree *tree, unsigned int index, void **value_address) 
    304 { 
    305         avl_node     *p = tree->root->right; 
    306         unsigned int  m = index + 1; 
    307  
    308         for (;;) { 
    309                 if (!p) { 
    310                         return -1; 
    311                 } 
    312                 if (m < AVL_GET_RANK(p)) { 
    313                         p = p->left; 
    314                 } else if (m > AVL_GET_RANK(p)) { 
    315                         m = m - AVL_GET_RANK(p); 
    316                         p = p->right; 
    317                 } else { 
    318                         *value_address = p->key; 
    319                         return 0; 
    320                 } 
    321         } 
    322 } 
    323  
    324 int 
    325 avl_get_item_by_key (avl_tree * tree, 
    326                      void * key, 
    327                      void **value_address) 
    328 { 
    329         avl_node * x = tree->root->right; 
    330         if (!x) { 
    331                 return -1; 
    332         } 
    333         for (;;) { 
    334                 int compare_result = tree->compare_fun (tree->compare_arg, key, x->key); 
    335                 if (compare_result < 0) { 
    336                         if (x->left) { 
    337                                 x = x->left; 
    338                         } else { 
    339                                 return -1; 
    340                         } 
    341                 } else if (compare_result > 0) { 
    342                         if (x->right) { 
    343                                 x = x->right; 
    344                         } else { 
    345                                 return -1; 
    346                         } 
    347                 } else { 
    348                         *value_address = x->value; 
    349                         return 0; 
    350                 } 
    351         } 
    352 } 
    353  
    354 int 
    355 avl_remove_by_key (avl_tree *tree, void *key,  
    356                    avl_free_key_fun_type free_key_fun, void **ret_val) 
    357 { 
    358         avl_node *x, *y, *p, *q, *r, *top, *x_child; 
    359         int shortened_side, shorter; 
    360  
    361         x = tree->root->right; 
    362         if (!x) { 
    363                 return -1; 
    364         } 
    365  
    366         /* find the node to remove */ 
    367         for (;;) { 
    368                 int compare_result = tree->compare_fun (tree->compare_arg, key, x->key); 
    369                 if (compare_result < 0) { 
    370                         /* move left 
    371                          * We will be deleting from the left, adjust this node's 
    372                          * rank accordingly 
    373                          */ 
    374                         AVL_SET_RANK (x, (AVL_GET_RANK(x) - 1)); 
    375                         if (x->left) { 
    376                                 x = x->left; 
    377                         } else { 
    378                                 /* Oops! now we have to undo the rank changes 
    379                                  * all the way up the tree 
    380                                  */ 
    381                                 AVL_SET_RANK(x, (AVL_GET_RANK (x) + 1)); 
    382                                 while (x != tree->root->right) { 
    383                                         if (x->parent->left == x) { 
    384                                                 AVL_SET_RANK(x->parent, (AVL_GET_RANK (x->parent) + 1)); 
    385                                         } 
    386                                         x = x->parent; 
    387                                 } 
    388                                 return -1;              /* key not in tree */ 
    389                         } 
    390                 } else if (compare_result > 0) { 
    391                         /* move right */ 
    392                         if (x->right) { 
    393                                 x = x->right; 
    394                         } else { 
    395                                 while (x != tree->root->right) { 
    396                                         if (x->parent->left == x) { 
    397                                                 AVL_SET_RANK(x->parent, (AVL_GET_RANK (x->parent) + 1)); 
    398                                         } 
    399                                         x = x->parent; 
    400                                 } 
    401                                 return -1;              /* key not in tree */ 
    402                         } 
    403                 } else { 
    404                         break; 
    405                 } 
    406         } 
    407  
    408         if (x->left && x->right) { 
    409                 void * temp_key; 
    410  
    411                 /* The complicated case. 
    412                  * reduce this to the simple case where we are deleting 
    413                  * a node with at most one child. 
    414                  */ 
    415  
    416                 /* find the immediate predecessor <y> */ 
    417                 y = x->left; 
    418                 while (y->right) { 
    419                         y = y->right; 
    420                 } 
    421                 /* swap <x> with <y> */ 
    422                 temp_key = x->key; 
    423                 x->key = y->key; 
    424                 y->key = temp_key; 
    425                 /* we know <x>'s left subtree lost a node because that's 
    426                  * where we took it from 
    427                  */ 
    428                 AVL_SET_RANK (x, (AVL_GET_RANK (x) - 1)); 
    429                 x = y; 
    430         } 
    431         /* now <x> has at most one child 
    432          * scoot this child into the place of <x> 
    433          */ 
    434         if (x->left) { 
    435                 x_child = x->left; 
    436                 x_child->parent = x->parent; 
    437         } else if (x->right) { 
    438                 x_child = x->right; 
    439                 x_child->parent = x->parent; 
    440         } else { 
    441                 x_child = NULL; 
    442         } 
    443  
    444         /* now tell <x>'s parent that a grandchild became a child */ 
    445         if (x == x->parent->left) { 
    446                 x->parent->left = x_child; 
    447                 shortened_side = -1; 
    448         } else { 
    449                 x->parent->right = x_child; 
    450                 shortened_side = +1; 
    451         } 
    452  
    453         /* 
    454          * the height of the subtree <x> 
    455          * has now been shortened.  climb back up 
    456          * the tree, rotating when necessary to adjust 
    457          * for the change. 
    458          */ 
    459         shorter = 1; 
    460         p = x->parent; 
    461  
    462         /* return the key and node to storage */ 
    463         if (ret_val) *ret_val = x->value; 
    464         free_key_fun (x->key); 
    465         free (x); 
    466  
    467         while (shorter && p->parent) { 
    468  
    469                 /* case 1: height unchanged */ 
    470                 if (AVL_GET_BALANCE(p) == 0) { 
    471                         if (shortened_side == -1) { 
    472                                 /* we removed a left child, the tree is now heavier 
    473                                  * on the right 
    474                                  */ 
    475                                 AVL_SET_BALANCE (p, +1); 
    476                         } else { 
    477                                 /* we removed a right child, the tree is now heavier 
    478                                  * on the left 
    479                                  */ 
    480                                 AVL_SET_BALANCE (p, -1); 
    481                         } 
    482                         shorter = 0; 
    483  
    484                 } else if (AVL_GET_BALANCE (p) == shortened_side) { 
    485                         /* case 2: taller subtree shortened, height reduced */ 
    486                         AVL_SET_BALANCE (p, 0); 
    487                 } else { 
    488                         /* case 3: shorter subtree shortened */ 
    489                         top = p->parent; 
    490                         /* set <q> to the taller of the two subtrees of <p> */ 
    491                         if (shortened_side == 1) { 
    492                                 q = p->left; 
    493                         } else { 
    494                                 q = p->right; 
    495                         } 
    496                         if (AVL_GET_BALANCE (q) == 0) { 
    497                                 /* case 3a: height unchanged */ 
    498                                 if (shortened_side == -1) { 
    499                                         /* single rotate left */ 
    500                                         q->parent = p->parent; 
    501                                         p->right = q->left; 
    502                                         if (q->left) { 
    503                                                 q->left->parent = p; 
    504                                         } 
    505                                         q->left = p; 
    506                                         p->parent = q; 
    507                                         AVL_SET_RANK (q, (AVL_GET_RANK (q) + AVL_GET_RANK (p))); 
    508                                 } else { 
    509                                         /* single rotate right */ 
    510                                         q->parent = p->parent; 
    511                                         p->left = q->right; 
    512                                         if (q->right) { 
    513                                                 q->right->parent = p; 
    514                                         } 
    515                                         q->right = p; 
    516                                         p->parent = q; 
    517                                         AVL_SET_RANK (p, (AVL_GET_RANK (p) - AVL_GET_RANK (q))); 
    518                                 } 
    519                                 shorter = 0; 
    520                                 AVL_SET_BALANCE (q, shortened_side); 
    521                                 AVL_SET_BALANCE (p, (- shortened_side)); 
    522                         } else if (AVL_GET_BALANCE (q) == AVL_GET_BALANCE (p)) { 
    523                                 /* case 3b: height reduced */ 
    524                                 if (shortened_side == -1) { 
    525                                         /* single rotate left */ 
    526                                         q->parent = p->parent; 
    527                                         p->right = q->left; 
    528                                         if (q->left) { 
    529                                                 q->left->parent = p; 
    530                                         } 
    531                                         q->left = p; 
    532                                         p->parent = q; 
    533                                         AVL_SET_RANK (q, (AVL_GET_RANK (q) + AVL_GET_RANK (p))); 
    534                                 } else { 
    535                                         /* single rotate right */ 
    536                                         q->parent = p->parent; 
    537                                         p->left = q->right; 
    538                                         if (q->right) { 
    539                                                 q->right->parent = p; 
    540                                         } 
    541                                         q->right = p; 
    542                                         p->parent = q; 
    543                                         AVL_SET_RANK (p, (AVL_GET_RANK (p) - AVL_GET_RANK (q))); 
    544                                 } 
    545                                 shorter = 1; 
    546                                 AVL_SET_BALANCE (q, 0); 
    547                                 AVL_SET_BALANCE (p, 0); 
    548                         } else { 
    549                                 /* case 3c: height reduced, balance factors opposite */ 
    550                                 if (shortened_side == 1) { 
    551                                         /* double rotate right */ 
    552                                         /* first, a left rotation around q */ 
    553                                         r = q->right; 
    554                                         r->parent = p->parent; 
    555                                         q->right = r->left; 
    556                                         if (r->left) { 
    557                                                 r->left->parent = q; 
    558                                         } 
    559                                         r->left = q; 
    560                                         q->parent = r; 
    561                                         /* now, a right rotation around p */ 
    562                                         p->left = r->right; 
    563                                         if (r->right) { 
    564                                                 r->right->parent = p; 
    565                                         } 
    566                                         r->right = p; 
    567                                         p->parent = r; 
    568                                         AVL_SET_RANK (r, (AVL_GET_RANK (r) + AVL_GET_RANK (q))); 
    569                                         AVL_SET_RANK (p, (AVL_GET_RANK (p) - AVL_GET_RANK (r))); 
    570                                 } else { 
    571                                         /* double rotate left */ 
    572                                         /* first, a right rotation around q */ 
    573                                         r = q->left; 
    574                                         r->parent = p->parent; 
    575                                         q->left = r->right; 
    576                                         if (r->right) { 
    577                                                 r->right->parent = q; 
    578                                         } 
    579                                         r->right = q; 
    580                                         q->parent = r; 
    581                                         /* now a left rotation around p */ 
    582                                         p->right = r->left; 
    583                                         if (r->left) { 
    584                                                 r->left->parent = p; 
    585                                         } 
    586                                         r->left = p; 
    587                                         p->parent = r; 
    588                                         AVL_SET_RANK (q, (AVL_GET_RANK (q) - AVL_GET_RANK (r))); 
    589                                         AVL_SET_RANK (r, (AVL_GET_RANK (r) + AVL_GET_RANK (p))); 
    590                                 } 
    591                                 if (AVL_GET_BALANCE (r) == shortened_side) { 
    592                                         AVL_SET_BALANCE (q, (- shortened_side)); 
    593                                         AVL_SET_BALANCE (p, 0); 
    594                                 } else if (AVL_GET_BALANCE (r) == (- shortened_side)) { 
    595                                         AVL_SET_BALANCE (q, 0); 
    596                                         AVL_SET_BALANCE (p, shortened_side); 
    597                                 } else { 
    598                                         AVL_SET_BALANCE (q, 0); 
    599                                         AVL_SET_BALANCE (p, 0); 
    600                                 } 
    601                                 AVL_SET_BALANCE (r, 0); 
    602                                 q = r; 
    603                         } 
    604                         /* a rotation has caused <q> (or <r> in case 3c) to become 
    605                          * the root.  let <p>'s former parent know this. 
    606                          */ 
    607                         if (top->left == p) { 
    608                                 top->left = q; 
    609                         } else { 
    610                                 top->right = q; 
    611                         } 
    612                         /* end case 3 */ 
    613                         p = q;