sumom****@users*****
sumom****@users*****
2008年 9月 30日 (火) 12:58:18 JST
Index: julius4/libsent/src/util/aptree.c
diff -u julius4/libsent/src/util/aptree.c:1.2 julius4/libsent/src/util/aptree.c:1.3
--- julius4/libsent/src/util/aptree.c:1.2 Tue Dec 18 17:45:54 2007
+++ julius4/libsent/src/util/aptree.c Tue Sep 30 12:58:18 2008
@@ -12,7 +12,7 @@
* @author Akinobu LEE
* @date Thu Feb 17 15:21:53 2005
*
- * $Revision: 1.2 $
+ * $Revision: 1.3 $
*
*/
/*
@@ -32,11 +32,11 @@
* @return pointer to the new node.
*/
static APATNODE *
-new_node()
+new_node(BMALLOC_BASE **mroot)
{
APATNODE *tmp;
- tmp = (APATNODE *)mymalloc(sizeof(APATNODE));
+ tmp = (APATNODE *)mybmalloc2(sizeof(APATNODE), mroot);
tmp->left0 = NULL;
tmp->right1 = NULL;
@@ -53,6 +53,21 @@
static void *
aptree_search_data_r(APATNODE *node, char *str, int maxbitplace)
{
+#if 1
+ /* non-recursive */
+ APATNODE *n;
+ APATNODE *branch = NULL;
+ n = node;
+ while(n->left0 != NULL || n->right1 != NULL) {
+ branch = n;
+ if (testbit_max(str, n->value.thres_bit, maxbitplace) != 0) {
+ n = n->right1;
+ } else {
+ n = n->left0;
+ }
+ }
+ return(n->value.data);
+#else
if (node->left0 == NULL && node->right1 == NULL) {
return(node->value.data);
} else {
@@ -62,6 +77,7 @@
return(aptree_search_data_r(node->left0, str, maxbitplace));
}
}
+#endif
}
/**
@@ -94,11 +110,11 @@
* @return the newly allocated root node.
*/
APATNODE *
-aptree_make_root_node(void *data)
+aptree_make_root_node(void *data, BMALLOC_BASE **mroot)
{
APATNODE *nnew;
/* make new leaf node for newstr */
- nnew = new_node();
+ nnew = new_node(mroot);
nnew->value.data = data;
return(nnew);
}
@@ -112,20 +128,54 @@
* @param parentlink [i/o] the parent node to which this node will be added
*/
static void
-aptree_add_entry_at(char *str, int bitloc, void *data, APATNODE **parentlink)
+aptree_add_entry_at(char *str, int slen, int bitloc, void *data, APATNODE **parentlink, BMALLOC_BASE **mroot)
{
+#if 1
+ /* non-recursive */
+ APATNODE **p;
+ APATNODE *newleaf, *newbranch, *node;
+
+ p = parentlink;
+ node = *p;
+ while(node->value.thres_bit <= bitloc &&
+ (node->left0 != NULL || node->right1 != NULL)) {
+ if (testbit(str, slen, node->value.thres_bit) != 0) {
+ p = &(node->right1);
+ } else {
+ p = &(node->left0);
+ }
+ node = *p;
+ }
+
+ /* insert between [parent] and [node] */
+ newleaf = new_node(mroot);
+ newleaf->value.data = data;
+ newbranch = new_node(mroot);
+ newbranch->value.thres_bit = bitloc;
+ *p = newbranch;
+ if (testbit(str, slen, bitloc) ==0) {
+ newbranch->left0 = newleaf;
+ newbranch->right1 = node;
+ } else {
+ newbranch->left0 = node;
+ newbranch->right1 = newleaf;
+ }
+
+#else
+
APATNODE *node;
+ APATNODE *newleaf, *newbranch;
+
node = *parentlink;
if (node->value.thres_bit > bitloc ||
(node->left0 == NULL && node->right1 == NULL)) {
- APATNODE *newleaf, *newbranch;
/* insert between [parent] and [node] */
- newleaf = new_node();
+ newleaf = new_node(mroot);
newleaf->value.data = data;
- newbranch = new_node();
+ newbranch = new_node(mroot);
newbranch->value.thres_bit = bitloc;
*parentlink = newbranch;
- if (testbit(str, bitloc) ==0) {
+ if (testbit(str, slen, bitloc) ==0) {
newbranch->left0 = newleaf;
newbranch->right1 = node;
} else {
@@ -134,12 +184,13 @@
}
return;
} else {
- if (testbit(str, node->value.thres_bit) != 0) {
- aptree_add_entry_at(str, bitloc, data, &(node->right1));
+ if (testbit(str, slen, node->value.thres_bit) != 0) {
+ aptree_add_entry_at(str, slen, bitloc, data, &(node->right1), mroot);
} else {
- aptree_add_entry_at(str, bitloc, data, &(node->left0));
+ aptree_add_entry_at(str, slen, bitloc, data, &(node->left0), mroot);
}
}
+#endif
}
/**
@@ -152,15 +203,15 @@
* @param rootnode [i/o] pointer to root index node
*/
void
-aptree_add_entry(char *str, void *data, char *matchstr, APATNODE **rootnode)
+aptree_add_entry(char *str, void *data, char *matchstr, APATNODE **rootnode, BMALLOC_BASE **mroot)
{
int bitloc;
bitloc = where_the_bit_differ(str, matchstr);
if (*rootnode == NULL) {
- *rootnode = aptree_make_root_node(data);
+ *rootnode = aptree_make_root_node(data, mroot);
} else {
- aptree_add_entry_at(str, bitloc, data, rootnode);
+ aptree_add_entry_at(str, strlen(str), bitloc, data, rootnode, mroot);
}
}
@@ -184,14 +235,14 @@
/* make sure the data of your removal request already exists before call this */
/* execute removal */
if (up == NULL) {
- free(now);
+ //free(now);
*root = NULL;
return;
}
b = (up->right1 == now) ? up->left0 : up->right1;
if (up2 == NULL) {
- free(now);
- free(up);
+ //free(now);
+ //free(up);
*root = b;
return;
}
@@ -200,8 +251,8 @@
} else {
up2->right1 = b;
}
- free(now);
- free(up);
+ //free(now);
+ //free(up);
return;
} else {
/* traverse */
@@ -254,16 +305,219 @@
}
}
-/**
- * Free all the sub nodes from specified node.
- *
- * @param node [in] current node.
- */
-void
-free_aptree(APATNODE *node)
+/*************************************************************/
+
+static void
+aptree_count(APATNODE *node, int *count_branch, int *count_data, int *maxbit)
+{
+ if (node->left0 == NULL && node->right1 == NULL) {
+ (*count_data)++;
+ } else {
+ if (node->value.thres_bit > *maxbit) {
+ *maxbit = node->value.thres_bit;
+ }
+ (*count_branch)++;
+ if (node->left0 != NULL) {
+ aptree_count(node->left0, count_branch, count_data, maxbit);
+ }
+ if (node->right1 != NULL) {
+ aptree_count(node->right1, count_branch, count_data, maxbit);
+ }
+ }
+}
+
+static int
+aptree_build_index(APATNODE *node, int *num, int *data_id, int *left, int *right, int *data)
+{
+ int id;
+
+ id = *num;
+ (*num)++;
+ if (node->left0 == NULL && node->right1 == NULL) {
+ left[id] = -1;
+ right[id] = -1;
+ data[id] = *data_id;
+ /* node->value.data を保存 */
+ (*data_id)++;
+ } else {
+ data[id] = node->value.thres_bit;
+ if (node->left0 != NULL) {
+ left[id] = aptree_build_index(node->left0, num, data_id, left, right, data);
+ } else {
+ left[id] = -1;
+ }
+ if (node->right1 != NULL) {
+ right[id] = aptree_build_index(node->right1, num, data_id, left, right, data);
+ } else {
+ right[id] = -1;
+ }
+ }
+ return id;
+}
+
+static void
+aptree_write_leaf(FILE *fp, APATNODE *node, boolean (*callback)(void *, FILE *fp), boolean *error_p)
+{
+ if (node->left0 == NULL && node->right1 == NULL) {
+ if ((*callback)(node->value.data, fp) == FALSE) {
+ *error_p = TRUE;
+ }
+ } else {
+ if (node->left0 != NULL) {
+ aptree_write_leaf(fp, node->left0, callback, error_p);
+ }
+ if (node->right1 != NULL) {
+ aptree_write_leaf(fp, node->right1, callback, error_p);
+ }
+ }
+}
+
+
+boolean
+aptree_write(FILE *fp, APATNODE *root, boolean (*save_data_func)(void *, FILE *fp))
+{
+ int count_node, count_branch, count_data, maxbit;
+ int *left, *right, *value;
+ int num, did;
+ boolean err;
+
+ if (root == NULL) return TRUE;
+
+ /* count statistics */
+ count_branch = count_data = 0;
+ maxbit = 0;
+ aptree_count(root, &count_branch, &count_data, &maxbit);
+ count_node = count_branch + count_data;
+ jlog("Stat: aptree_write: %d nodes (%d branch + %d data), maxbit=%d\n", count_node, count_branch, count_data, maxbit);
+ /* allocate */
+ left = (int *)mymalloc(sizeof(int) * count_node);
+ right = (int *)mymalloc(sizeof(int) * count_node);
+ value = (int *)mymalloc(sizeof(int) * count_node);
+ /* make index */
+ did = num = 0;
+ aptree_build_index(root, &num, &did, left, right, value);
+#if 0
+ {
+ int i;
+ for(i=0;i<count_node;i++) {
+ printf("%d: %d %d %d\n", i, left[i], right[i], value[i]);
+ }
+ }
+#endif
+ /* write tree to file */
+ if (myfwrite(&count_node, sizeof(int), 1, fp) < 1) {
+ jlog("Error: aptree_write: fail to write header\n");
+ return FALSE;
+ }
+ if (myfwrite(&count_data, sizeof(int), 1, fp) < 1) {
+ jlog("Error: aptree_write: fail to write header\n");
+ return FALSE;
+ }
+ if (myfwrite(left, sizeof(int), count_node, fp) < count_node) {
+ jlog("Error: aptree_write: fail to write %d bytes\n", sizeof(int) * count_node);
+ return FALSE;
+ }
+ if (myfwrite(right, sizeof(int), count_node, fp) < count_node) {
+ jlog("Error: aptree_write: fail to write %d bytes\n", sizeof(int) * count_node);
+ return FALSE;
+ }
+ if (myfwrite(value, sizeof(int), count_node, fp) < count_node) {
+ jlog("Error: aptree_write: fail to write %d bytes\n", sizeof(int) * count_node);
+ return FALSE;
+ }
+ if (save_data_func != NULL) {
+ /* write leaf node data */
+ err = FALSE;
+ aptree_write_leaf(fp, root, save_data_func, &err);
+ }
+ if (err) {
+ jlog("Error: aptree_write: error occured when writing tree leaf data\n");
+ return FALSE;
+ }
+
+ free(value);
+ free(right);
+ free(left);
+
+ return TRUE;
+}
+
+
+boolean
+aptree_read(FILE *fp, APATNODE **root, BMALLOC_BASE **mroot, void *data, boolean (*load_data_func)(void **, void *, FILE *))
{
- if (node == NULL) return;
- if (node->left0 != NULL) free_aptree(node->left0);
- if (node->right1 != NULL) free_aptree(node->right1);
- free(node);
+ int count_node, count_branch, count_data, maxbit;
+ int *left, *right, *value;
+ int num, did;
+ boolean err;
+ APATNODE *nodelist;
+ APATNODE *node;
+ int i;
+
+ if (*root != NULL) {
+ jlog("Error: aptree_read: root node != NULL!\n");
+ return FALSE;
+ }
+
+ /* read header */
+ if (myfread(&count_node, sizeof(int), 1, fp) < 1) {
+ jlog("Error: aptree_read: fail to read header\n");
+ return FALSE;
+ }
+ if (myfread(&count_data, sizeof(int), 1, fp) < 1) {
+ jlog("Error: aptree_read: fail to read header\n");
+ return FALSE;
+ }
+ jlog("Stat: aptree_read: %d nodes (%d branch + %d data)\n",
+ count_node, count_node - count_data, count_data);
+ /* prepare buffer */
+ left = (int *)mymalloc(sizeof(int) * count_node);
+ right = (int *)mymalloc(sizeof(int) * count_node);
+ value = (int *)mymalloc(sizeof(int) * count_node);
+ /* read data */
+ if (myfread(left, sizeof(int), count_node, fp) < count_node) {
+ jlog("Error: aptree_read: fail to read %d bytes\n", sizeof(int) * count_node);
+ return FALSE;
+ }
+ if (myfread(right, sizeof(int), count_node, fp) < count_node) {
+ jlog("Error: aptree_read: fail to read %d bytes\n", sizeof(int) * count_node);
+ return FALSE;
+ }
+ if (myfread(value, sizeof(int), count_node, fp) < count_node) {
+ jlog("Error: aptree_read: fail to read %d bytes\n", sizeof(int) * count_node);
+ return FALSE;
+ }
+ /* allocate nodes */
+ nodelist = (APATNODE *)mybmalloc2(sizeof(APATNODE) * count_node, mroot);
+ for(i=0;i<count_node;i++) {
+ node = &(nodelist[i]);
+ if (left[i] == -1) {
+ node->left0 = NULL;
+ } else {
+ node->left0 = &(nodelist[left[i]]);
+ }
+ if (right[i] == -1) {
+ node->right1 = NULL;
+ } else {
+ node->right1 = &(nodelist[right[i]]);
+ }
+ if (left[i] == -1 && right[i] == -1) {
+ /* load leaf data node */
+ if ((*load_data_func)(&(node->value.data), data, fp) == FALSE) {
+ jlog("Error: aptree_read: failed to load leaf data entity\n");
+ return FALSE;
+ }
+ } else {
+ /* set thres bit */
+ node->value.thres_bit = value[i];
+ }
+ }
+ /* set root node */
+ *root = &(nodelist[0]);
+
+ free(value);
+ free(right);
+ free(left);
+
+ return TRUE;
}
Index: julius4/libsent/src/util/ptree.c
diff -u julius4/libsent/src/util/ptree.c:1.2 julius4/libsent/src/util/ptree.c:1.3
--- julius4/libsent/src/util/ptree.c:1.2 Tue Dec 18 17:45:54 2007
+++ julius4/libsent/src/util/ptree.c Tue Sep 30 12:58:18 2008
@@ -12,7 +12,7 @@
* @author Akinobu LEE
* @date Thu Feb 17 15:34:39 2005
*
- * $Revision: 1.2 $
+ * $Revision: 1.3 $
*
*/
/*
@@ -37,11 +37,11 @@
* @return the content of tested bit in @a tmp_str, either 0 or 1.
*/
int
-testbit(char *str, int bitplace)
+testbit(char *str, int slen, int bitplace)
{
int maskptr;
- if ((maskptr = bitplace >> 3) > strlen(str)) return 0;
+ if ((maskptr = bitplace >> 3) > slen) return 0;
return(str[maskptr] & mbit[bitplace & 7]);
}
@@ -74,11 +74,14 @@
{
int p = 0;
int bitloc;
+ int slen1, slen2;
/* step: char, bit */
while(str1[p] == str2[p]) p++;
bitloc = p * 8;
- while(testbit(str1, bitloc) == testbit(str2, bitloc)) bitloc++;
+ slen1 = strlen(str1);
+ slen2 = strlen(str2);
+ while(testbit(str1, slen1, bitloc) == testbit(str2, slen2, bitloc)) bitloc++;
return(bitloc);
}
@@ -138,7 +141,7 @@
newnum = 0;
for (i=0;i<wordsnum;i++) {
- if (testbit(words[i], bitplace) != 0) {
+ if (testbit(words[i], strlen(words[i]), bitplace) != 0) {
newnum++;
}
}
@@ -149,9 +152,9 @@
/* sort word pointers by tested bit */
j = wordsnum-1;
for (i=0; i<newnum; i++) {
- if (testbit(words[i], bitplace) == 0) {
+ if (testbit(words[i], strlen(words[i]), bitplace) == 0) {
for (; j>=newnum; j--) {
- if (testbit(words[j], bitplace) != 0) {
+ if (testbit(words[j], strlen(words[j]), bitplace) != 0) {
p = words[i]; words[i] = words[j]; words[j] = p;
tmp = data[i]; data[i] = data[j]; data[j] = tmp;
break;
@@ -267,7 +270,7 @@
* @param parentlink [i/o] the parent node to which this node will be added
*/
static void
-ptree_add_entry_at(char *str, int bitloc, int data, PATNODE **parentlink)
+ptree_add_entry_at(char *str, int slen, int bitloc, int data, PATNODE **parentlink)
{
PATNODE *node;
node = *parentlink;
@@ -280,7 +283,7 @@
newbranch = new_node();
newbranch->value.thres_bit = bitloc;
*parentlink = newbranch;
- if (testbit(str, bitloc) ==0) {
+ if (testbit(str, slen, bitloc) ==0) {
newbranch->left0 = newleaf;
newbranch->right1 = node;
} else {
@@ -289,10 +292,10 @@
}
return;
} else {
- if (testbit(str, node->value.thres_bit) != 0) {
- ptree_add_entry_at(str, bitloc, data, &(node->right1));
+ if (testbit(str, slen, node->value.thres_bit) != 0) {
+ ptree_add_entry_at(str, slen, bitloc, data, &(node->right1));
} else {
- ptree_add_entry_at(str, bitloc, data, &(node->left0));
+ ptree_add_entry_at(str, slen, bitloc, data, &(node->left0));
}
}
}
@@ -315,7 +318,7 @@
if (*rootnode == NULL) {
*rootnode = ptree_make_root_node(data);
} else {
- ptree_add_entry_at(str, bitloc, data, rootnode);
+ ptree_add_entry_at(str, strlen(str), bitloc, data, rootnode);
}
}