Lines Matching refs:tree
189 struct tree;
190 static utf8leaf_t *utf8nlookup(struct tree *, unsigned char *,
192 static utf8leaf_t *utf8lookup(struct tree *, unsigned char *, const char *);
345 struct tree { struct
350 struct tree *next; argument
355 int *(*leaf_index)(struct tree *, void *); argument
380 static void *lookup(struct tree *tree, const char *key) in lookup() argument
385 node = tree->root; in lookup()
417 static void tree_walk(struct tree *tree) in tree_walk() argument
428 printf("%s_%x root %p\n", tree->type, tree->maxage, tree->root); in tree_walk()
429 if (tree->childnode == LEAF) { in tree_walk()
430 assert(tree->root); in tree_walk()
431 tree->leaf_print(tree->root, indent); in tree_walk()
434 assert(tree->childnode == NODE); in tree_walk()
435 node = tree->root; in tree_walk()
454 tree->leaf_print(node->left, in tree_walk()
468 tree->leaf_print(node->right, in tree_walk()
533 static int insert(struct tree *tree, char *key, int keylen, void *leaf) in insert() argument
543 cursor = &tree->root; in insert()
574 if (! tree->leaf_equal(node->left, node->right)) in insert()
582 tree->root = leaf; in insert()
583 tree->childnode = LEAF; in insert()
654 static void prune(struct tree *tree) in prune() argument
668 printf("Pruning %s_%x\n", tree->type, tree->maxage); in prune()
671 if (tree->childnode == LEAF) in prune()
673 if (!tree->root) in prune()
677 node = tree->root; in prune()
727 if (! tree->leaf_equal(leftleaf, rightleaf)) in prune()
815 static void mark_nodes(struct tree *tree) in mark_nodes() argument
826 printf("Marking %s_%x\n", tree->type, tree->maxage); in mark_nodes()
827 if (tree->childnode == LEAF) in mark_nodes()
830 assert(tree->childnode == NODE); in mark_nodes()
831 node = tree->root; in mark_nodes()
839 if (tree->leaf_mark(node->left)) { in mark_nodes()
857 if (tree->leaf_mark(node->right)) { in mark_nodes()
878 assert(tree->childnode == NODE); in mark_nodes()
879 node = tree->root; in mark_nodes()
887 if (tree->leaf_mark(node->left)) { in mark_nodes()
909 if (tree->leaf_mark(node->right)) { in mark_nodes()
942 static int index_nodes(struct tree *tree, int index) in index_nodes() argument
954 tree->index = index; in index_nodes()
959 printf("Indexing %s_%x: %d\n", tree->type, tree->maxage, index); in index_nodes()
960 if (tree->childnode == LEAF) { in index_nodes()
961 index += tree->leaf_size(tree->root); in index_nodes()
965 assert(tree->childnode == NODE); in index_nodes()
966 node = tree->root; in index_nodes()
982 *tree->leaf_index(tree, node->left) = in index_nodes()
984 index += tree->leaf_size(node->left); in index_nodes()
997 *tree->leaf_index(tree, node->right) = index; in index_nodes()
998 index += tree->leaf_size(node->right); in index_nodes()
1048 static int size_nodes(struct tree *tree) in size_nodes() argument
1050 struct tree *next; in size_nodes()
1070 printf("Sizing %s_%x\n", tree->type, tree->maxage); in size_nodes()
1071 if (tree->childnode == LEAF) in size_nodes()
1074 assert(tree->childnode == NODE); in size_nodes()
1077 node = tree->root; in size_nodes()
1094 next = tree->next; in size_nodes()
1123 offset = *tree->leaf_index(tree, node->right); in size_nodes()
1185 static void emit(struct tree *tree, unsigned char *data) in emit() argument
1204 index = tree->index; in emit()
1208 printf("Emitting %s_%x\n", tree->type, tree->maxage); in emit()
1209 if (tree->childnode == LEAF) { in emit()
1210 assert(tree->root); in emit()
1211 tree->leaf_emit(tree->root, data); in emit()
1212 size = tree->leaf_size(tree->root); in emit()
1218 assert(tree->childnode == NODE); in emit()
1219 node = tree->root; in emit()
1275 data = tree->leaf_emit(node->left, in emit()
1277 size = tree->leaf_size(node->left); in emit()
1292 data = tree->leaf_emit(node->right, in emit()
1294 size = tree->leaf_size(node->right); in emit()
1318 printf(" %d total\n", index - tree->index); in emit()
1354 struct tree *nfdi_tree;
1355 struct tree *nfdicf_tree;
1357 struct tree *trees;
1493 static int *nfdi_index(struct tree *tree, void *l) in nfdi_index() argument
1497 return &tree->leafindex[leaf->code]; in nfdi_index()
1500 static int *nfdicf_index(struct tree *tree, void *l) in nfdicf_index() argument
1504 return &tree->leafindex[leaf->code]; in nfdicf_index()
1623 trees = calloc(trees_count, sizeof(struct tree)); in trees_init()
1745 static void verify(struct tree *tree) in verify() argument
1756 printf("Verifying %s_%x\n", tree->type, tree->maxage); in verify()
1757 nocf = strcmp(tree->type, "nfdicf"); in verify()
1762 if (data->correction <= tree->maxage) in verify()
1765 leaf = utf8lookup(tree, hangul, key); in verify()
2594 int utf8agemax(struct tree *, const char *);
2595 int utf8nagemax(struct tree *, const char *, size_t);
2596 int utf8agemin(struct tree *, const char *);
2597 int utf8nagemin(struct tree *, const char *, size_t);
2598 ssize_t utf8len(struct tree *, const char *);
2599 ssize_t utf8nlen(struct tree *, const char *, size_t);
2601 int utf8cursor(struct utf8cursor *, struct tree *, const char *);
2602 int utf8ncursor(struct utf8cursor *, struct tree *, const char *, size_t);
2706 static utf8leaf_t *utf8nlookup(struct tree *tree, unsigned char *hangul, in utf8nlookup() argument
2715 if (!tree) in utf8nlookup()
2720 trie = utf8data + tree->index; in utf8nlookup()
2781 static utf8leaf_t *utf8lookup(struct tree *tree, unsigned char *hangul, in utf8lookup() argument
2784 return utf8nlookup(tree, hangul, s, (size_t)-1); in utf8lookup()
2803 int utf8agemax(struct tree *tree, const char *s) in utf8agemax() argument
2810 if (!tree) in utf8agemax()
2814 leaf = utf8lookup(tree, hangul, s); in utf8agemax()
2818 if (leaf_age <= tree->maxage && leaf_age > age) in utf8agemax()
2830 int utf8agemin(struct tree *tree, const char *s) in utf8agemin() argument
2837 if (!tree) in utf8agemin()
2839 age = tree->maxage; in utf8agemin()
2841 leaf = utf8lookup(tree, hangul, s); in utf8agemin()
2845 if (leaf_age <= tree->maxage && leaf_age < age) in utf8agemin()
2856 int utf8nagemax(struct tree *tree, const char *s, size_t len) in utf8nagemax() argument
2863 if (!tree) in utf8nagemax()
2867 leaf = utf8nlookup(tree, hangul, s, len); in utf8nagemax()
2871 if (leaf_age <= tree->maxage && leaf_age > age) in utf8nagemax()
2883 int utf8nagemin(struct tree *tree, const char *s, size_t len) in utf8nagemin() argument
2890 if (!tree) in utf8nagemin()
2892 age = tree->maxage; in utf8nagemin()
2894 leaf = utf8nlookup(tree, hangul, s, len); in utf8nagemin()
2898 if (leaf_age <= tree->maxage && leaf_age < age) in utf8nagemin()
2912 ssize_t utf8len(struct tree *tree, const char *s) in utf8len() argument
2918 if (!tree) in utf8len()
2921 leaf = utf8lookup(tree, hangul, s); in utf8len()
2924 if (ages[LEAF_GEN(leaf)] > tree->maxage) in utf8len()
2939 ssize_t utf8nlen(struct tree *tree, const char *s, size_t len) in utf8nlen() argument
2945 if (!tree) in utf8nlen()
2948 leaf = utf8nlookup(tree, hangul, s, len); in utf8nlen()
2951 if (ages[LEAF_GEN(leaf)] > tree->maxage) in utf8nlen()
2967 struct tree *tree; member
2990 int utf8ncursor(struct utf8cursor *u8c, struct tree *tree, const char *s, in utf8ncursor() argument
2993 if (!tree) in utf8ncursor()
2997 u8c->tree = tree; in utf8ncursor()
3025 int utf8cursor(struct utf8cursor *u8c, struct tree *tree, const char *s) in utf8cursor() argument
3027 return utf8ncursor(u8c, tree, s, (unsigned int)-1); in utf8cursor()
3086 leaf = utf8lookup(u8c->tree, u8c->hangul, u8c->s); in utf8byte()
3088 leaf = utf8nlookup(u8c->tree, u8c->hangul, in utf8byte()
3097 if (ages[LEAF_GEN(leaf)] > u8c->tree->maxage) { in utf8byte()
3110 leaf = utf8lookup(u8c->tree, u8c->hangul, u8c->s); in utf8byte()
3174 static int normalize_line(struct tree *tree) in normalize_line() argument
3184 if (utf8cursor(&u8c, tree, s)) in normalize_line()
3199 if (utf8cursor(&u8c, tree, s)) in normalize_line()