00001
00018
00019
00020
00021
00022
00023
00024
00025 #include <sent/stddefs.h>
00026 #include <sent/ptree.h>
00027
00028 static unsigned char mbit[] = {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01};
00029
00030
00039 int
00040 testbit(char *str, int bitplace)
00041 {
00042 int maskptr;
00043
00044 if ((maskptr = bitplace >> 3) > strlen(str)) return 0;
00045 return(str[maskptr] & mbit[bitplace & 7]);
00046 }
00047
00057 int
00058 testbit_max(char *str, int bitplace, int maxbitplace)
00059 {
00060 if (bitplace >= maxbitplace) return 0;
00061 return(str[bitplace >> 3] & mbit[bitplace & 7]);
00062 }
00063
00072 int
00073 where_the_bit_differ(char *str1, char *str2)
00074 {
00075 int p = 0;
00076 int bitloc;
00077
00078
00079 while(str1[p] == str2[p]) p++;
00080 bitloc = p * 8;
00081 while(testbit(str1, bitloc) == testbit(str2, bitloc)) bitloc++;
00082
00083 return(bitloc);
00084 }
00085
00092 static PATNODE *
00093 new_node()
00094 {
00095 PATNODE *tmp;
00096
00097 tmp = (PATNODE *)mymalloc(sizeof(PATNODE));
00098 tmp->left0 = NULL;
00099 tmp->right1 = NULL;
00100
00101 return(tmp);
00102 }
00103
00115 PATNODE *
00116 make_ptree(char **words, int *data, int wordsnum, int bitplace)
00117 {
00118 int i,j, tmp;
00119 char *p;
00120 int newnum;
00121 PATNODE *ntmp;
00122
00123 #if 0
00124 printf("%d:", wordsnum);
00125 for (i=0;i<wordsnum;i++) {
00126 printf(" %s",words[i]);
00127 }
00128 printf("\n");
00129 printf("test bit = %d\n", bitplace);
00130 #endif
00131
00132 if (wordsnum == 1) {
00133
00134 ntmp = new_node();
00135 ntmp->value.data = data[0];
00136 return(ntmp);
00137 }
00138
00139 newnum = 0;
00140 for (i=0;i<wordsnum;i++) {
00141 if (testbit(words[i], bitplace) != 0) {
00142 newnum++;
00143 }
00144 }
00145 if (newnum == 0 || newnum == wordsnum) {
00146
00147 return(make_ptree(words, data, wordsnum, bitplace + 1));
00148 } else {
00149
00150 j = wordsnum-1;
00151 for (i=0; i<newnum; i++) {
00152 if (testbit(words[i], bitplace) == 0) {
00153 for (; j>=newnum; j--) {
00154 if (testbit(words[j], bitplace) != 0) {
00155 p = words[i]; words[i] = words[j]; words[j] = p;
00156 tmp = data[i]; data[i] = data[j]; data[j] = tmp;
00157 break;
00158 }
00159 }
00160 }
00161 }
00162
00163 ntmp = new_node();
00164 ntmp->value.thres_bit = bitplace;
00165 ntmp->right1 = make_ptree(words, data, newnum, bitplace+1);
00166 ntmp->left0 = make_ptree(&(words[newnum]), &(data[newnum]), wordsnum-newnum, bitplace+1);
00167 return(ntmp);
00168 }
00169 }
00170
00171
00178 void
00179 disp_ptree(PATNODE *node, int level)
00180 {
00181 int i;
00182
00183 for (i=0;i<level;i++) {
00184 printf("-");
00185 }
00186 if (node->left0 == NULL && node->right1 == NULL) {
00187 printf("LEAF:%d\n", node->value.data);
00188 } else {
00189 printf("%d\n", node->value.thres_bit);
00190 if (node->left0 != NULL) {
00191 disp_ptree(node->left0, level+1);
00192 }
00193 if (node->right1 != NULL) {
00194 disp_ptree(node->right1, level+1);
00195 }
00196 }
00197 }
00198
00208 static int
00209 ptree_search_data_r(PATNODE *node, char *str, int maxbitplace)
00210 {
00211 if (node->left0 == NULL && node->right1 == NULL) {
00212 return(node->value.data);
00213 } else {
00214 if (testbit_max(str, node->value.thres_bit, maxbitplace) != 0) {
00215 return(ptree_search_data_r(node->right1, str, maxbitplace));
00216 } else {
00217 return(ptree_search_data_r(node->left0, str, maxbitplace));
00218 }
00219 }
00220 }
00221
00230 int
00231 ptree_search_data(char *str, PATNODE *node)
00232 {
00233 if (node == NULL) {
00234
00235 return -1;
00236 }
00237 return(ptree_search_data_r(node, str, strlen(str) * 8 + 8));
00238 }
00239
00240
00241
00242
00243
00251 PATNODE *
00252 ptree_make_root_node(int data)
00253 {
00254 PATNODE *nnew;
00255
00256 nnew = new_node();
00257 nnew->value.data = data;
00258 return(nnew);
00259 }
00260
00269 static void
00270 ptree_add_entry_at(char *str, int bitloc, int data, PATNODE **parentlink)
00271 {
00272 PATNODE *node;
00273 node = *parentlink;
00274 if (node->value.thres_bit > bitloc ||
00275 (node->left0 == NULL && node->right1 == NULL)) {
00276 PATNODE *newleaf, *newbranch;
00277
00278 newleaf = new_node();
00279 newleaf->value.data = data;
00280 newbranch = new_node();
00281 newbranch->value.thres_bit = bitloc;
00282 *parentlink = newbranch;
00283 if (testbit(str, bitloc) ==0) {
00284 newbranch->left0 = newleaf;
00285 newbranch->right1 = node;
00286 } else {
00287 newbranch->left0 = node;
00288 newbranch->right1 = newleaf;
00289 }
00290 return;
00291 } else {
00292 if (testbit(str, node->value.thres_bit) != 0) {
00293 ptree_add_entry_at(str, bitloc, data, &(node->right1));
00294 } else {
00295 ptree_add_entry_at(str, bitloc, data, &(node->left0));
00296 }
00297 }
00298 }
00299
00309 void
00310 ptree_add_entry(char *str, int data, char *matchstr, PATNODE **rootnode)
00311 {
00312 int bitloc;
00313
00314 bitloc = where_the_bit_differ(str, matchstr);
00315 if (*rootnode == NULL) {
00316 *rootnode = ptree_make_root_node(data);
00317 } else {
00318 ptree_add_entry_at(str, bitloc, data, rootnode);
00319 }
00320
00321 }
00322
00328 void
00329 free_ptree(PATNODE *node)
00330 {
00331 if (node == NULL) return;
00332 if (node->left0 != NULL) free_ptree(node->left0);
00333 if (node->right1 != NULL) free_ptree(node->right1);
00334 free(node);
00335 }