00001
00018
00019
00020
00021
00022
00023
00024
00025 #include <sent/stddefs.h>
00026 #include <sent/ptree.h>
00027
00034 static APATNODE *
00035 new_node()
00036 {
00037 APATNODE *tmp;
00038
00039 tmp = (APATNODE *)mymalloc(sizeof(APATNODE));
00040 tmp->left0 = NULL;
00041 tmp->right1 = NULL;
00042
00043 return(tmp);
00044 }
00045
00053 static void *
00054 aptree_search_data_r(APATNODE *node, char *str, int maxbitplace)
00055 {
00056 if (node->left0 == NULL && node->right1 == NULL) {
00057 return(node->value.data);
00058 } else {
00059 if (testbit_max(str, node->value.thres_bit, maxbitplace) != 0) {
00060 return(aptree_search_data_r(node->right1, str, maxbitplace));
00061 } else {
00062 return(aptree_search_data_r(node->left0, str, maxbitplace));
00063 }
00064 }
00065 }
00066
00075 void *
00076 aptree_search_data(char *str, APATNODE *node)
00077 {
00078 if (node == NULL) {
00079
00080 return NULL;
00081 }
00082 return(aptree_search_data_r(node, str, strlen(str) * 8 + 8));
00083 }
00084
00085
00086
00087
00088
00096 APATNODE *
00097 aptree_make_root_node(void *data)
00098 {
00099 APATNODE *nnew;
00100
00101 nnew = new_node();
00102 nnew->value.data = data;
00103 return(nnew);
00104 }
00105
00114 static void
00115 aptree_add_entry_at(char *str, int bitloc, void *data, APATNODE **parentlink)
00116 {
00117 APATNODE *node;
00118 node = *parentlink;
00119 if (node->value.thres_bit > bitloc ||
00120 (node->left0 == NULL && node->right1 == NULL)) {
00121 APATNODE *newleaf, *newbranch;
00122
00123 newleaf = new_node();
00124 newleaf->value.data = data;
00125 newbranch = new_node();
00126 newbranch->value.thres_bit = bitloc;
00127 *parentlink = newbranch;
00128 if (testbit(str, bitloc) ==0) {
00129 newbranch->left0 = newleaf;
00130 newbranch->right1 = node;
00131 } else {
00132 newbranch->left0 = node;
00133 newbranch->right1 = newleaf;
00134 }
00135 return;
00136 } else {
00137 if (testbit(str, node->value.thres_bit) != 0) {
00138 aptree_add_entry_at(str, bitloc, data, &(node->right1));
00139 } else {
00140 aptree_add_entry_at(str, bitloc, data, &(node->left0));
00141 }
00142 }
00143 }
00144
00154 void
00155 aptree_add_entry(char *str, void *data, char *matchstr, APATNODE **rootnode)
00156 {
00157 int bitloc;
00158
00159 bitloc = where_the_bit_differ(str, matchstr);
00160 if (*rootnode == NULL) {
00161 *rootnode = aptree_make_root_node(data);
00162 } else {
00163 aptree_add_entry_at(str, bitloc, data, rootnode);
00164 }
00165
00166 }
00167
00168
00169
00177 static void
00178 aptree_remove_entry_r(APATNODE *now, APATNODE *up, APATNODE *up2, char *str, int maxbitplace, APATNODE **root)
00179 {
00180 APATNODE *b;
00181
00182 if (now->left0 == NULL && now->right1 == NULL) {
00183
00184
00185
00186 if (up == NULL) {
00187 free(now);
00188 *root = NULL;
00189 return;
00190 }
00191 b = (up->right1 == now) ? up->left0 : up->right1;
00192 if (up2 == NULL) {
00193 free(now);
00194 free(up);
00195 *root = b;
00196 return;
00197 }
00198 if (up2->left0 == up) {
00199 up2->left0 = b;
00200 } else {
00201 up2->right1 = b;
00202 }
00203 free(now);
00204 free(up);
00205 return;
00206 } else {
00207
00208 if (testbit_max(str, now->value.thres_bit, maxbitplace) != 0) {
00209 aptree_remove_entry_r(now->right1, now, up, str, maxbitplace, root);
00210 } else {
00211 aptree_remove_entry_r(now->left0, now, up, str, maxbitplace, root);
00212 }
00213 }
00214 }
00215
00223 void
00224 aptree_remove_entry(char *str, APATNODE **rootnode)
00225 {
00226 if (*rootnode == NULL) {
00227 jlog("Warning: aptree: no node, deletion for \"%s\" failed\n", str);
00228 return;
00229 }
00230 aptree_remove_entry_r(*rootnode, NULL, NULL, str, strlen(str)*8+8, rootnode);
00231 }
00232
00233
00234
00242 void
00243 aptree_traverse_and_do(APATNODE *node, void (*callback)(void *))
00244 {
00245 if (node->left0 == NULL && node->right1 == NULL) {
00246 (*callback)(node->value.data);
00247 } else {
00248 if (node->left0 != NULL) {
00249 aptree_traverse_and_do(node->left0, callback);
00250 }
00251 if (node->right1 != NULL) {
00252 aptree_traverse_and_do(node->right1, callback);
00253 }
00254 }
00255 }
00256
00262 void
00263 free_aptree(APATNODE *node)
00264 {
00265 if (node == NULL) return;
00266 if (node->left0 != NULL) free_aptree(node->left0);
00267 if (node->right1 != NULL) free_aptree(node->right1);
00268 free(node);
00269 }