root/tags/rel_1-0-1/ext/http11/tst_delete.c

Revision 4, 3.7 kB (checked in by zedshaw, 3 years ago)

initial import into trunk

Line 
1
2 #include "tst.h"
3 #include <stdio.h>
4 #include <stdlib.h>
5
6 void *tst_delete(unsigned char *key, struct tst *tst)
7 {
8    struct node *current_node;
9    struct node *current_node_parent;
10    struct node *last_branch;
11    struct node *last_branch_parent;
12    struct node *next_node;
13    struct node *last_branch_replacement;
14    struct node *last_branch_dangling_child;
15    int key_index;
16
17    
18    if(key[0] == 0)
19       return NULL;
20    if(tst->head[(int)key[0]] == NULL)
21       return NULL;
22    
23    last_branch = NULL;
24    last_branch_parent = NULL;
25    current_node = tst->head[(int)key[0]];
26    current_node_parent = NULL;
27    key_index = 1;
28    while(current_node != NULL)
29    {
30       if(key[key_index] == current_node->value)
31       {
32          
33          if( (current_node->left != NULL) || (current_node->right != NULL) )
34          {
35             last_branch = current_node;
36             last_branch_parent = current_node_parent;
37          }
38          if(key[key_index] == 0)
39             break;
40          else
41          {
42             current_node_parent = current_node;
43             current_node = current_node->middle;
44             key_index++;
45             continue;
46          }
47       }
48       else if( ((current_node->value == 0) && (key[key_index] < 64)) ||
49          ((current_node->value != 0) && (key[key_index] <
50          current_node->value)) )
51       {
52          last_branch_parent = current_node;
53          current_node_parent = current_node;
54          current_node = current_node->left;
55          last_branch = current_node;
56          continue;
57       }
58       else
59       {
60          last_branch_parent = current_node;
61          current_node_parent = current_node;
62          current_node = current_node->right;
63          last_branch = current_node;
64          continue;
65       }
66    
67    }
68    if(current_node == NULL)
69       return NULL;
70    
71    if(last_branch == NULL)
72    {
73      
74          next_node = tst->head[(int)key[0]];
75          tst->head[(int)key[0]] = NULL;
76    }
77    else if( (last_branch->left == NULL) && (last_branch->right == NULL) )
78    {
79      
80       if(last_branch_parent->left == last_branch)
81          last_branch_parent->left = NULL;
82       else
83          last_branch_parent->right = NULL;
84      
85       next_node = last_branch;
86    }
87    else
88    {
89      
90       if( (last_branch->left != NULL) && (last_branch->right != NULL) )
91       {
92          last_branch_replacement = last_branch->right;
93          last_branch_dangling_child = last_branch->left;
94       }
95       else if(last_branch->right != NULL)
96       {
97          last_branch_replacement = last_branch->right;
98          last_branch_dangling_child = NULL;
99       }
100       else
101       {
102          last_branch_replacement = last_branch->left;
103          last_branch_dangling_child = NULL;
104       }
105      
106       if(last_branch_parent == NULL)
107          tst->head[(int)key[0]]=last_branch_replacement;
108       else
109       {
110          if (last_branch_parent->left == last_branch)
111             last_branch_parent->left = last_branch_replacement;
112          else if (last_branch_parent->right == last_branch)
113             last_branch_parent->right = last_branch_replacement;
114          else
115             last_branch_parent->middle = last_branch_replacement;
116       }
117      
118       if(last_branch_dangling_child != NULL)
119       {
120          current_node = last_branch_replacement;
121      
122          while (current_node->left != NULL)
123             current_node = current_node->left;
124      
125          current_node->left = last_branch_dangling_child;
126       }
127      
128       next_node = last_branch;
129    }
130    
131    do
132    {
133       current_node = next_node;
134       next_node = current_node->middle;
135      
136       current_node->left = NULL;
137       current_node->right = NULL;
138       current_node->middle = tst->free_list;
139       tst->free_list = current_node;
140    }
141    while(current_node->value != 0);
142    
143    return next_node;
144    
145 }
146
Note: See TracBrowser for help on using the browser.