Lines Matching refs:tree
111 * A compact binary tree, used to decode UTF-8 characters.
114 * bytes for an offset into the tree. The first byte contains the
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 {
350 struct tree *next;
355 int *(*leaf_index)(struct tree *, void *);
378 * Example lookup function for a tree.
380 static void *lookup(struct tree *tree, const char *key)
385 node = tree->root;
414 * A simple non-recursive tree walker: keep track of visits to the
417 static void tree_walk(struct tree *tree)
428 printf("%s_%x root %p\n", tree->type, tree->maxage, tree->root);
429 if (tree->childnode == LEAF) {
430 assert(tree->root);
431 tree->leaf_print(tree->root, indent);
434 assert(tree->childnode == NODE);
435 node = tree->root;
454 tree->leaf_print(node->left,
468 tree->leaf_print(node->right,
527 * Insert a new leaf into the tree, and collapse any subtrees that are
529 * internal node will not be removed to preserve the tree's integrity.
533 static int insert(struct tree *tree, char *key, int keylen, void *leaf)
543 cursor = &tree->root;
574 if (! tree->leaf_equal(node->left, node->right))
581 /* root of tree! */
582 tree->root = leaf;
583 tree->childnode = LEAF;
604 /* internal tree error */
650 * this to ensure tree integrity. Note as well that the structure of
654 static void prune(struct tree *tree)
668 printf("Pruning %s_%x\n", tree->type, tree->maxage);
671 if (tree->childnode == LEAF)
673 if (!tree->root)
677 node = tree->root;
727 if (! tree->leaf_equal(leftleaf, rightleaf))
812 * Mark the nodes in the tree that lead to leaves that must be
815 static void mark_nodes(struct tree *tree)
826 printf("Marking %s_%x\n", tree->type, tree->maxage);
827 if (tree->childnode == LEAF)
830 assert(tree->childnode == NODE);
831 node = tree->root;
839 if (tree->leaf_mark(node->left)) {
857 if (tree->leaf_mark(node->right)) {
878 assert(tree->childnode == NODE);
879 node = tree->root;
887 if (tree->leaf_mark(node->left)) {
909 if (tree->leaf_mark(node->right)) {
940 * offsets between nodes are used to navigate the tree.
942 static int index_nodes(struct tree *tree, int index)
954 tree->index = index;
959 printf("Indexing %s_%x: %d\n", tree->type, tree->maxage, index);
960 if (tree->childnode == LEAF) {
961 index += tree->leaf_size(tree->root);
965 assert(tree->childnode == NODE);
966 node = tree->root;
982 *tree->leaf_index(tree, node->left) =
984 index += tree->leaf_size(node->left);
997 *tree->leaf_index(tree, node->right) = index;
998 index += tree->leaf_size(node->right);
1048 static int size_nodes(struct tree *tree)
1050 struct tree *next;
1070 printf("Sizing %s_%x\n", tree->type, tree->maxage);
1071 if (tree->childnode == LEAF)
1074 assert(tree->childnode == NODE);
1077 node = tree->root;
1090 * the next tree. Such a node need
1094 next = tree->next;
1123 offset = *tree->leaf_index(tree, node->right);
1183 * Emit a trie for the given tree into the data array.
1185 static void emit(struct tree *tree, unsigned char *data)
1204 index = tree->index;
1208 printf("Emitting %s_%x\n", tree->type, tree->maxage);
1209 if (tree->childnode == LEAF) {
1210 assert(tree->root);
1211 tree->leaf_emit(tree->root, data);
1212 size = tree->leaf_size(tree->root);
1218 assert(tree->childnode == NODE);
1219 node = tree->root;
1275 data = tree->leaf_emit(node->left,
1277 size = tree->leaf_size(node->left);
1292 data = tree->leaf_emit(node->right,
1294 size = tree->leaf_size(node->right);
1318 printf(" %d total\n", index - tree->index);
1354 struct tree *nfdi_tree;
1355 struct tree *nfdicf_tree;
1357 struct tree *trees;
1493 static int *nfdi_index(struct tree *tree, void *l)
1497 return &tree->leafindex[leaf->code];
1500 static int *nfdicf_index(struct tree *tree, void *l)
1504 return &tree->leafindex[leaf->code];
1623 trees = calloc(trees_count, sizeof(struct tree));
1745 static void verify(struct tree *tree)
1756 printf("Verifying %s_%x\n", tree->type, tree->maxage);
1757 nocf = strcmp(tree->type, "nfdicf");
1762 if (data->correction <= tree->maxage)
1765 leaf = utf8lookup(tree, hangul, key);
1845 printf("The generated tree supports two normalization forms:\n");
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,
2715 if (!tree)
2720 trie = utf8data + tree->index;
2781 static utf8leaf_t *utf8lookup(struct tree *tree, unsigned char *hangul,
2784 return utf8nlookup(tree, hangul, s, (size_t)-1);
2803 int utf8agemax(struct tree *tree, const char *s)
2810 if (!tree)
2814 leaf = utf8lookup(tree, hangul, s);
2818 if (leaf_age <= tree->maxage && leaf_age > age)
2830 int utf8agemin(struct tree *tree, const char *s)
2837 if (!tree)
2839 age = tree->maxage;
2841 leaf = utf8lookup(tree, hangul, s);
2845 if (leaf_age <= tree->maxage && leaf_age < age)
2856 int utf8nagemax(struct tree *tree, const char *s, size_t len)
2863 if (!tree)
2867 leaf = utf8nlookup(tree, hangul, s, len);
2871 if (leaf_age <= tree->maxage && leaf_age > age)
2883 int utf8nagemin(struct tree *tree, const char *s, size_t len)
2890 if (!tree)
2892 age = tree->maxage;
2894 leaf = utf8nlookup(tree, hangul, s, len);
2898 if (leaf_age <= tree->maxage && leaf_age < age)
2912 ssize_t utf8len(struct tree *tree, const char *s)
2918 if (!tree)
2921 leaf = utf8lookup(tree, hangul, s);
2924 if (ages[LEAF_GEN(leaf)] > tree->maxage)
2939 ssize_t utf8nlen(struct tree *tree, const char *s, size_t len)
2945 if (!tree)
2948 leaf = utf8nlookup(tree, hangul, s, len);
2951 if (ages[LEAF_GEN(leaf)] > tree->maxage)
2967 struct tree *tree;
2990 int utf8ncursor(struct utf8cursor *u8c, struct tree *tree, const char *s,
2993 if (!tree)
2997 u8c->tree = tree;
3025 int utf8cursor(struct utf8cursor *u8c, struct tree *tree, const char *s)
3027 return utf8ncursor(u8c, tree, s, (unsigned int)-1);
3086 leaf = utf8lookup(u8c->tree, u8c->hangul, u8c->s);
3088 leaf = utf8nlookup(u8c->tree, u8c->hangul,
3097 if (ages[LEAF_GEN(leaf)] > u8c->tree->maxage) {
3110 leaf = utf8lookup(u8c->tree, u8c->hangul, u8c->s);
3174 static int normalize_line(struct tree *tree)
3184 if (utf8cursor(&u8c, tree, s))
3199 if (utf8cursor(&u8c, tree, s))