Lines Matching refs:node
361 struct node { struct
366 struct node *parent; argument
382 struct node *node; in lookup() argument
385 node = tree->root; in lookup()
386 while (!leaf && node) { in lookup()
387 if (node->nextbyte) in lookup()
389 if (*key & (1 << (node->bitnum & 7))) { in lookup()
391 if (node->rightnode == NODE) { in lookup()
392 node = node->right; in lookup()
393 } else if (node->rightnode == LEAF) { in lookup()
394 leaf = node->right; in lookup()
396 node = NULL; in lookup()
400 if (node->leftnode == NODE) { in lookup()
401 node = node->left; in lookup()
402 } else if (node->leftnode == LEAF) { in lookup()
403 leaf = node->left; in lookup()
405 node = NULL; in lookup()
419 struct node *node; in tree_walk() local
435 node = tree->root; in tree_walk()
437 while (node) { in tree_walk()
440 indent, "", node, in tree_walk()
441 node->bitnum, node->nextbyte, in tree_walk()
442 node->left, node->right, in tree_walk()
443 node->keymask, node->keybits); in tree_walk()
445 if (!(node->left && node->right)) in tree_walk()
448 while (node) { in tree_walk()
449 bitmask = 1 << node->bitnum; in tree_walk()
452 if (node->leftnode == LEAF) { in tree_walk()
453 assert(node->left); in tree_walk()
454 tree->leaf_print(node->left, in tree_walk()
457 } else if (node->left) { in tree_walk()
458 assert(node->leftnode == NODE); in tree_walk()
460 node = node->left; in tree_walk()
466 if (node->rightnode == LEAF) { in tree_walk()
467 assert(node->right); in tree_walk()
468 tree->leaf_print(node->right, in tree_walk()
471 } else if (node->right) { in tree_walk()
472 assert(node->rightnode == NODE); in tree_walk()
474 node = node->right; in tree_walk()
480 node = node->parent; in tree_walk()
492 static struct node *alloc_node(struct node *parent) in alloc_node()
494 struct node *node; in alloc_node() local
497 node = malloc(sizeof(*node)); in alloc_node()
498 node->left = node->right = NULL; in alloc_node()
499 node->parent = parent; in alloc_node()
500 node->leftnode = NODE; in alloc_node()
501 node->rightnode = NODE; in alloc_node()
502 node->keybits = 0; in alloc_node()
503 node->keymask = 0; in alloc_node()
504 node->mark = 0; in alloc_node()
505 node->index = 0; in alloc_node()
506 node->offset = -1; in alloc_node()
507 node->size = 4; in alloc_node()
509 if (node->parent) { in alloc_node()
512 node->bitnum = bitnum + 7 + 8; in alloc_node()
513 node->nextbyte = 1; in alloc_node()
515 node->bitnum = bitnum - 1; in alloc_node()
516 node->nextbyte = 0; in alloc_node()
519 node->bitnum = 7; in alloc_node()
520 node->nextbyte = 0; in alloc_node()
523 return node; in alloc_node()
535 struct node *node; in insert() local
536 struct node *parent; in insert()
542 node = NULL; in insert()
549 *cursor = alloc_node(node); in insert()
550 node = *cursor; in insert()
551 if (node->nextbyte) in insert()
553 if (*key & (1 << (node->bitnum & 7))) in insert()
554 cursor = &node->right; in insert()
556 cursor = &node->left; in insert()
562 while (node) { in insert()
563 if (*key & (1 << (node->bitnum & 7))) in insert()
564 node->rightnode = LEAF; in insert()
566 node->leftnode = LEAF; in insert()
567 if (node->nextbyte) in insert()
569 if (node->leftnode == NODE || node->rightnode == NODE) in insert()
571 assert(node->left); in insert()
572 assert(node->right); in insert()
574 if (! tree->leaf_equal(node->left, node->right)) in insert()
577 leaf = node->left; in insert()
579 parent = node->parent; in insert()
584 } else if (parent->left == node) { in insert()
591 parent->keymask |= (1 << node->bitnum); in insert()
593 } else if (parent->right == node) { in insert()
600 parent->keymask |= (1 << node->bitnum); in insert()
601 parent->keybits |= (1 << node->bitnum); in insert()
607 free(node); in insert()
608 node = parent; in insert()
612 while (node) { in insert()
613 parent = node->parent; in insert()
617 if (node->keymask == 0) { in insert()
624 assert((parent->keymask & node->keymask) == 0); in insert()
625 parent->keymask |= node->keymask; in insert()
627 parent->keybits |= node->keybits; in insert()
631 node = parent; in insert()
656 struct node *node; in prune() local
657 struct node *left; in prune()
658 struct node *right; in prune()
659 struct node *parent; in prune()
677 node = tree->root; in prune()
678 while (node) { in prune()
679 if (node->nextbyte) in prune()
681 if (node->leftnode == LEAF) in prune()
683 if (node->rightnode == LEAF) in prune()
685 if (!node->left) in prune()
687 if (!node->right) in prune()
689 left = node->left; in prune()
690 right = node->right; in prune()
733 parent = node->parent; in prune()
734 left = node->left; in prune()
735 right = node->right; in prune()
736 if (parent->left == node) in prune()
738 else if (parent->right == node) in prune()
743 left->keymask |= (1 << node->bitnum); in prune()
744 node->left = NULL; in prune()
745 while (node) { in prune()
746 bitmask = 1 << node->bitnum; in prune()
749 if (node->leftnode == NODE && node->left) { in prune()
750 left = node->left; in prune()
751 free(node); in prune()
753 node = left; in prune()
754 } else if (node->rightnode == NODE && node->right) { in prune()
755 right = node->right; in prune()
756 free(node); in prune()
758 node = right; in prune()
760 node = NULL; in prune()
764 node = parent; in prune()
766 bitmask = 1 << node->bitnum; in prune()
770 if (node->left && node->right) in prune()
772 if (node->left) { in prune()
773 left = node->left; in prune()
774 node->keymask |= left->keymask; in prune()
775 node->keybits |= left->keybits; in prune()
777 if (node->right) { in prune()
778 right = node->right; in prune()
779 node->keymask |= right->keymask; in prune()
780 node->keybits |= right->keybits; in prune()
782 node->keymask |= (1 << node->bitnum); in prune()
783 node = node->parent; in prune()
785 bitmask = 1 << node->bitnum; in prune()
790 bitmask = 1 << node->bitnum; in prune()
792 node->leftnode == NODE && in prune()
793 node->left) { in prune()
795 node = node->left; in prune()
797 node->rightnode == NODE && in prune()
798 node->right) { in prune()
800 node = node->right; in prune()
804 node = node->parent; in prune()
817 struct node *node; in mark_nodes() local
818 struct node *n; in mark_nodes()
831 node = tree->root; in mark_nodes()
833 while (node) { in mark_nodes()
834 bitmask = 1 << node->bitnum; in mark_nodes()
837 if (node->leftnode == LEAF) { in mark_nodes()
838 assert(node->left); in mark_nodes()
839 if (tree->leaf_mark(node->left)) { in mark_nodes()
840 n = node; in mark_nodes()
847 } else if (node->left) { in mark_nodes()
848 assert(node->leftnode == NODE); in mark_nodes()
849 node = node->left; in mark_nodes()
855 if (node->rightnode == LEAF) { in mark_nodes()
856 assert(node->right); in mark_nodes()
857 if (tree->leaf_mark(node->right)) { in mark_nodes()
858 n = node; in mark_nodes()
865 } else if (node->right) { in mark_nodes()
866 assert(node->rightnode == NODE); in mark_nodes()
867 node = node->right; in mark_nodes()
873 node = node->parent; in mark_nodes()
879 node = tree->root; in mark_nodes()
881 while (node) { in mark_nodes()
882 bitmask = 1 << node->bitnum; in mark_nodes()
885 if (node->leftnode == LEAF) { in mark_nodes()
886 assert(node->left); in mark_nodes()
887 if (tree->leaf_mark(node->left)) { in mark_nodes()
888 n = node; in mark_nodes()
895 } else if (node->left) { in mark_nodes()
896 assert(node->leftnode == NODE); in mark_nodes()
897 node = node->left; in mark_nodes()
898 if (!node->mark && node->parent->mark) { in mark_nodes()
900 node->mark = 1; in mark_nodes()
907 if (node->rightnode == LEAF) { in mark_nodes()
908 assert(node->right); in mark_nodes()
909 if (tree->leaf_mark(node->right)) { in mark_nodes()
910 n = node; in mark_nodes()
917 } else if (node->right) { in mark_nodes()
918 assert(node->rightnode == NODE); in mark_nodes()
919 node = node->right; in mark_nodes()
920 if (!node->mark && node->parent->mark && in mark_nodes()
921 !node->parent->left) { in mark_nodes()
923 node->mark = 1; in mark_nodes()
930 node = node->parent; in mark_nodes()
944 struct node *node; in index_nodes() local
966 node = tree->root; in index_nodes()
968 while (node) { in index_nodes()
969 if (!node->mark) in index_nodes()
972 if (node->index != index) in index_nodes()
973 node->index = index; in index_nodes()
974 index += node->size; in index_nodes()
976 while (node) { in index_nodes()
977 bitmask = 1 << node->bitnum; in index_nodes()
978 if (node->mark && (leftmask & bitmask) == 0) { in index_nodes()
980 if (node->leftnode == LEAF) { in index_nodes()
981 assert(node->left); in index_nodes()
982 *tree->leaf_index(tree, node->left) = in index_nodes()
984 index += tree->leaf_size(node->left); in index_nodes()
986 } else if (node->left) { in index_nodes()
987 assert(node->leftnode == NODE); in index_nodes()
989 node = node->left; in index_nodes()
993 if (node->mark && (rightmask & bitmask) == 0) { in index_nodes()
995 if (node->rightnode == LEAF) { in index_nodes()
996 assert(node->right); in index_nodes()
997 *tree->leaf_index(tree, node->right) = index; in index_nodes()
998 index += tree->leaf_size(node->right); in index_nodes()
1000 } else if (node->right) { in index_nodes()
1001 assert(node->rightnode == NODE); in index_nodes()
1003 node = node->right; in index_nodes()
1009 node = node->parent; in index_nodes()
1025 static int mark_subtree(struct node *node) in mark_subtree() argument
1029 if (!node || node->mark) in mark_subtree()
1031 node->mark = 1; in mark_subtree()
1032 node->index = node->parent->index; in mark_subtree()
1034 if (node->leftnode == NODE) in mark_subtree()
1035 changed += mark_subtree(node->left); in mark_subtree()
1036 if (node->rightnode == NODE) in mark_subtree()
1037 changed += mark_subtree(node->right); in mark_subtree()
1051 struct node *node; in size_nodes() local
1052 struct node *right; in size_nodes()
1053 struct node *n; in size_nodes()
1077 node = tree->root; in size_nodes()
1079 while (node) { in size_nodes()
1080 if (!node->mark) in size_nodes()
1083 if (!node->left || !node->right) { in size_nodes()
1086 if (node->rightnode == NODE) { in size_nodes()
1093 right = node->right; in size_nodes()
1098 while (n->bitnum != node->bitnum) { in size_nodes()
1112 if (n->bitnum != node->bitnum) in size_nodes()
1121 offset = right->index - node->index; in size_nodes()
1123 offset = *tree->leaf_index(tree, node->right); in size_nodes()
1124 offset -= node->index; in size_nodes()
1136 if (node->size != size || node->offset != offset) { in size_nodes()
1137 node->size = size; in size_nodes()
1138 node->offset = offset; in size_nodes()
1142 while (node) { in size_nodes()
1143 bitmask = 1 << node->bitnum; in size_nodes()
1145 if (node->mark && (leftmask & bitmask) == 0) { in size_nodes()
1147 if (node->leftnode == LEAF) { in size_nodes()
1148 assert(node->left); in size_nodes()
1149 } else if (node->left) { in size_nodes()
1150 assert(node->leftnode == NODE); in size_nodes()
1152 node = node->left; in size_nodes()
1156 if (node->mark && (rightmask & bitmask) == 0) { in size_nodes()
1159 if (node->rightnode == LEAF) { in size_nodes()
1160 assert(node->right); in size_nodes()
1161 } else if (node->right) { in size_nodes()
1162 assert(node->rightnode == NODE); in size_nodes()
1164 node = node->right; in size_nodes()
1172 node = node->parent; in size_nodes()
1187 struct node *node; in emit() local
1219 node = tree->root; in emit()
1221 while (node) { in emit()
1222 if (!node->mark) in emit()
1224 assert(node->offset != -1); in emit()
1225 assert(node->index == index); in emit()
1228 if (node->nextbyte) in emit()
1230 byte |= (node->bitnum & BITNUM); in emit()
1231 if (node->left && node->right) { in emit()
1232 if (node->leftnode == NODE) in emit()
1234 if (node->rightnode == NODE) in emit()
1236 if (node->offset <= 0xff) in emit()
1238 else if (node->offset <= 0xffff) in emit()
1243 offset = node->offset; in emit()
1252 } else if (node->left) { in emit()
1253 if (node->leftnode == NODE) in emit()
1258 } else if (node->right) { in emit()
1260 if (node->rightnode == NODE) in emit()
1269 while (node) { in emit()
1270 bitmask = 1 << node->bitnum; in emit()
1271 if (node->mark && (leftmask & bitmask) == 0) { in emit()
1273 if (node->leftnode == LEAF) { in emit()
1274 assert(node->left); in emit()
1275 data = tree->leaf_emit(node->left, in emit()
1277 size = tree->leaf_size(node->left); in emit()
1281 } else if (node->left) { in emit()
1282 assert(node->leftnode == NODE); in emit()
1284 node = node->left; in emit()
1288 if (node->mark && (rightmask & bitmask) == 0) { in emit()
1290 if (node->rightnode == LEAF) { in emit()
1291 assert(node->right); in emit()
1292 data = tree->leaf_emit(node->right, in emit()
1294 size = tree->leaf_size(node->right); in emit()
1298 } else if (node->right) { in emit()
1299 assert(node->rightnode == NODE); in emit()
1301 node = node->right; in emit()
1307 node = node->parent; in emit()
2713 int node; in utf8nlookup() local
2719 node = 1; in utf8nlookup()
2721 while (node) { in utf8nlookup()
2733 node = (*trie & RIGHTNODE); in utf8nlookup()
2742 node = (*trie & TRIENODE); in utf8nlookup()
2752 node = (*trie & LEFTNODE); in utf8nlookup()
2759 node = (*trie & TRIENODE); in utf8nlookup()