00001
00017
00018
00019
00020
00021
00022
00023
00024 #include <sent/stddefs.h>
00025 #include <sent/ptree.h>
00026
00035 int
00036 testbit(char *str, int bitplace)
00037 {
00038 int maskptr;
00039 int bitshift;
00040 unsigned char maskbit;
00041
00042 maskptr = bitplace / 8;
00043 if ((bitshift = bitplace % 8) != 0) {
00044 maskbit = 0x80 >> bitshift;
00045 } else {
00046 maskbit = 0x80;
00047 }
00048 if (strlen(str)<maskptr) return 0;
00049 return(str[maskptr] & maskbit);
00050 }
00051
00060 int
00061 where_the_bit_differ(char *str1, char *str2)
00062 {
00063 int p = 0;
00064 int bitloc;
00065
00066
00067 while(str1[p] == str2[p]) p++;
00068 bitloc = p * 8;
00069 while(testbit(str1, bitloc) == testbit(str2, bitloc)) bitloc++;
00070
00071 return(bitloc);
00072 }
00073
00074
00081 static PATNODE *
00082 new_node()
00083 {
00084 PATNODE *tmp;
00085
00086 tmp = (PATNODE *)mymalloc(sizeof(PATNODE));
00087 tmp->left0 = NULL;
00088 tmp->right1 = NULL;
00089
00090 return(tmp);
00091 }
00092
00104 PATNODE *
00105 make_ptree(char **words, int *data, int wordsnum, int bitplace)
00106 {
00107 int i,j, tmp;
00108 char *p;
00109 int newnum;
00110 PATNODE *ntmp;
00111
00112 #if 0
00113 j_printf("%d:", wordsnum);
00114 for (i=0;i<wordsnum;i++) {
00115 j_printf(" %s",words[i]);
00116 }
00117 j_printf("\n");
00118 j_printf("test bit = %d\n", bitplace);
00119 #endif
00120
00121 if (wordsnum == 1) {
00122
00123 ntmp = new_node();
00124 ntmp->value.data = data[0];
00125 return(ntmp);
00126 }
00127
00128 newnum = 0;
00129 for (i=0;i<wordsnum;i++) {
00130 if (testbit(words[i], bitplace) != 0) {
00131 newnum++;
00132 }
00133 }
00134 if (newnum == 0 || newnum == wordsnum) {
00135
00136 return(make_ptree(words, data, wordsnum, bitplace + 1));
00137 } else {
00138
00139 j = wordsnum-1;
00140 for (i=0; i<newnum; i++) {
00141 if (testbit(words[i], bitplace) == 0) {
00142 for (; j>=newnum; j--) {
00143 if (testbit(words[j], bitplace) != 0) {
00144 p = words[i]; words[i] = words[j]; words[j] = p;
00145 tmp = data[i]; data[i] = data[j]; data[j] = tmp;
00146 break;
00147 }
00148 }
00149 }
00150 }
00151
00152 ntmp = new_node();
00153 ntmp->value.thres_bit = bitplace;
00154 ntmp->right1 = make_ptree(words, data, newnum, bitplace+1);
00155 ntmp->left0 = make_ptree(&(words[newnum]), &(data[newnum]), wordsnum-newnum, bitplace+1);
00156 return(ntmp);
00157 }
00158 }
00159
00160
00167 void
00168 disp_ptree(PATNODE *node, int level)
00169 {
00170 int i;
00171
00172 for (i=0;i<level;i++) {
00173 j_printf("-");
00174 }
00175 if (node->left0 == NULL && node->right1 == NULL) {
00176 j_printf("LEAF:%d\n", node->value.data);
00177 } else {
00178 j_printf("%d\n", node->value.thres_bit);
00179 if (node->left0 != NULL) {
00180 disp_ptree(node->left0, level+1);
00181 }
00182 if (node->right1 != NULL) {
00183 disp_ptree(node->right1, level+1);
00184 }
00185 }
00186 }
00187
00188
00189 static char *tmp_str;
00190 static int maxbitplace;
00191
00199 static int
00200 testbit_local(int bitplace)
00201 {
00202 int maskptr;
00203 int bitshift;
00204 unsigned char maskbit;
00205
00206 if (bitplace >= maxbitplace) return 0;
00207 maskptr = bitplace / 8;
00208 if ((bitshift = bitplace % 8) != 0) {
00209 maskbit = 0x80 >> bitshift;
00210 } else {
00211 maskbit = 0x80;
00212 }
00213 return(tmp_str[maskptr] & maskbit);
00214 }
00215
00223 static int
00224 ptree_search_data_r(PATNODE *node)
00225 {
00226 if (node->left0 == NULL && node->right1 == NULL) {
00227 return(node->value.data);
00228 } else {
00229 if (testbit_local(node->value.thres_bit) != 0) {
00230 return(ptree_search_data_r(node->right1));
00231 } else {
00232 return(ptree_search_data_r(node->left0));
00233 }
00234 }
00235 }
00236
00245 int
00246 ptree_search_data(char *str, PATNODE *node)
00247 {
00248 if (node == NULL) {
00249 j_error("Error: ptree_search_data: no node, search for \"%s\" failed\n", str);
00250 }
00251 tmp_str = str;
00252 maxbitplace = strlen(str) * 8 + 8;
00253 return(ptree_search_data_r(node));
00254 }
00255
00256
00257
00258
00259
00267 PATNODE *
00268 ptree_make_root_node(int data)
00269 {
00270 PATNODE *nnew;
00271
00272 nnew = new_node();
00273 nnew->value.data = data;
00274 return(nnew);
00275 }
00276
00285 static void
00286 ptree_add_entry_at(char *str, int bitloc, int data, PATNODE **parentlink)
00287 {
00288 PATNODE *node;
00289 node = *parentlink;
00290 if (node->value.thres_bit > bitloc ||
00291 (node->left0 == NULL && node->right1 == NULL)) {
00292 PATNODE *newleaf, *newbranch;
00293
00294 newleaf = new_node();
00295 newleaf->value.data = data;
00296 newbranch = new_node();
00297 newbranch->value.thres_bit = bitloc;
00298 *parentlink = newbranch;
00299 if (testbit(str, bitloc) ==0) {
00300 newbranch->left0 = newleaf;
00301 newbranch->right1 = node;
00302 } else {
00303 newbranch->left0 = node;
00304 newbranch->right1 = newleaf;
00305 }
00306 return;
00307 } else {
00308 if (testbit(str, node->value.thres_bit) != 0) {
00309 ptree_add_entry_at(str, bitloc, data, &(node->right1));
00310 } else {
00311 ptree_add_entry_at(str, bitloc, data, &(node->left0));
00312 }
00313 }
00314 }
00315
00325 void
00326 ptree_add_entry(char *str, int data, char *matchstr, PATNODE **rootnode)
00327 {
00328 int bitloc;
00329
00330 bitloc = where_the_bit_differ(str, matchstr);
00331 if (*rootnode == NULL) {
00332 *rootnode = ptree_make_root_node(data);
00333 } else {
00334 ptree_add_entry_at(str, bitloc, data, rootnode);
00335 }
00336
00337 }
00338
00344 void
00345 free_ptree(PATNODE *node)
00346 {
00347 if (node->left0 != NULL) free_ptree(node->left0);
00348 if (node->right1 != NULL) free_ptree(node->right1);
00349 free(node);
00350 }