Lines Matching refs:node
113 * Internal nodes are one byte for the node itself, and up to three
119 * if offlen == 0 (non-branching node)
120 * RIGHTPATH - 1 bit field - set if the following node is for the
122 * TRIENODE - 1 bit field - set if the following node is an internal
123 * node, otherwise it is a leaf node
124 * if offlen != 0 (branching node)
125 * LEFTNODE - 1 bit field - set if the left-hand node is internal
126 * RIGHTNODE - 1 bit field - set if the right-hand node is internal
361 struct node {
366 struct node *parent;
382 struct node *node;
385 node = tree->root;
386 while (!leaf && node) {
387 if (node->nextbyte)
389 if (*key & (1 << (node->bitnum & 7))) {
391 if (node->rightnode == NODE) {
392 node = node->right;
393 } else if (node->rightnode == LEAF) {
394 leaf = node->right;
396 node = NULL;
400 if (node->leftnode == NODE) {
401 node = node->left;
402 } else if (node->leftnode == LEAF) {
403 leaf = node->left;
405 node = NULL;
419 struct node *node;
435 node = tree->root;
437 while (node) {
440 indent, "", node,
441 node->bitnum, node->nextbyte,
442 node->left, node->right,
443 node->keymask, node->keybits);
445 if (!(node->left && node->right))
448 while (node) {
449 bitmask = 1 << node->bitnum;
452 if (node->leftnode == LEAF) {
453 assert(node->left);
454 tree->leaf_print(node->left,
457 } else if (node->left) {
458 assert(node->leftnode == NODE);
460 node = node->left;
466 if (node->rightnode == LEAF) {
467 assert(node->right);
468 tree->leaf_print(node->right,
471 } else if (node->right) {
472 assert(node->rightnode == NODE);
474 node = node->right;
480 node = node->parent;
490 * Allocate an initialize a new internal node.
492 static struct node *alloc_node(struct node *parent)
494 struct node *node;
497 node = malloc(sizeof(*node));
498 node->left = node->right = NULL;
499 node->parent = parent;
500 node->leftnode = NODE;
501 node->rightnode = NODE;
502 node->keybits = 0;
503 node->keymask = 0;
504 node->mark = 0;
505 node->index = 0;
506 node->offset = -1;
507 node->size = 4;
509 if (node->parent) {
512 node->bitnum = bitnum + 7 + 8;
513 node->nextbyte = 1;
515 node->bitnum = bitnum - 1;
516 node->nextbyte = 0;
519 node->bitnum = 7;
520 node->nextbyte = 0;
523 return node;
529 * internal node will not be removed to preserve the tree's integrity.
530 * Note that due to the structure of utf8, no nextbyte tagged node
535 struct node *node;
536 struct node *parent;
542 node = NULL;
549 *cursor = alloc_node(node);
550 node = *cursor;
551 if (node->nextbyte)
553 if (*key & (1 << (node->bitnum & 7)))
554 cursor = &node->right;
556 cursor = &node->left;
562 while (node) {
563 if (*key & (1 << (node->bitnum & 7)))
564 node->rightnode = LEAF;
566 node->leftnode = LEAF;
567 if (node->nextbyte)
569 if (node->leftnode == NODE || node->rightnode == NODE)
571 assert(node->left);
572 assert(node->right);
574 if (! tree->leaf_equal(node->left, node->right))
577 leaf = node->left;
579 parent = node->parent;
584 } else if (parent->left == node) {
591 parent->keymask |= (1 << node->bitnum);
593 } else if (parent->right == node) {
600 parent->keymask |= (1 << node->bitnum);
601 parent->keybits |= (1 << node->bitnum);
607 free(node);
608 node = parent;
612 while (node) {
613 parent = node->parent;
617 if (node->keymask == 0) {
624 assert((parent->keymask & node->keymask) == 0);
625 parent->keymask |= node->keymask;
627 parent->keybits |= node->keybits;
631 node = parent;
646 * branch of a node, and the two leaves comare identical, the node in
656 struct node *node;
657 struct node *left;
658 struct node *right;
659 struct node *parent;
677 node = tree->root;
678 while (node) {
679 if (node->nextbyte)
681 if (node->leftnode == LEAF)
683 if (node->rightnode == LEAF)
685 if (!node->left)
687 if (!node->right)
689 left = node->left;
690 right = node->right;
730 * This node has identical singleton-only subtrees.
733 parent = node->parent;
734 left = node->left;
735 right = node->right;
736 if (parent->left == node)
738 else if (parent->right == node)
743 left->keymask |= (1 << node->bitnum);
744 node->left = NULL;
745 while (node) {
746 bitmask = 1 << node->bitnum;
749 if (node->leftnode == NODE && node->left) {
750 left = node->left;
751 free(node);
753 node = left;
754 } else if (node->rightnode == NODE && node->right) {
755 right = node->right;
756 free(node);
758 node = right;
760 node = NULL;
764 node = parent;
766 bitmask = 1 << node->bitnum;
770 if (node->left && node->right)
772 if (node->left) {
773 left = node->left;
774 node->keymask |= left->keymask;
775 node->keybits |= left->keybits;
777 if (node->right) {
778 right = node->right;
779 node->keymask |= right->keymask;
780 node->keybits |= right->keybits;
782 node->keymask |= (1 << node->bitnum);
783 node = node->parent;
785 bitmask = 1 << node->bitnum;
790 bitmask = 1 << node->bitnum;
792 node->leftnode == NODE &&
793 node->left) {
795 node = node->left;
797 node->rightnode == NODE &&
798 node->right) {
800 node = node->right;
804 node = node->parent;
817 struct node *node;
818 struct node *n;
831 node = tree->root;
833 while (node) {
834 bitmask = 1 << node->bitnum;
837 if (node->leftnode == LEAF) {
838 assert(node->left);
839 if (tree->leaf_mark(node->left)) {
840 n = node;
847 } else if (node->left) {
848 assert(node->leftnode == NODE);
849 node = node->left;
855 if (node->rightnode == LEAF) {
856 assert(node->right);
857 if (tree->leaf_mark(node->right)) {
858 n = node;
865 } else if (node->right) {
866 assert(node->rightnode == NODE);
867 node = node->right;
873 node = node->parent;
879 node = tree->root;
881 while (node) {
882 bitmask = 1 << node->bitnum;
885 if (node->leftnode == LEAF) {
886 assert(node->left);
887 if (tree->leaf_mark(node->left)) {
888 n = node;
895 } else if (node->left) {
896 assert(node->leftnode == NODE);
897 node = node->left;
898 if (!node->mark && node->parent->mark) {
900 node->mark = 1;
907 if (node->rightnode == LEAF) {
908 assert(node->right);
909 if (tree->leaf_mark(node->right)) {
910 n = node;
917 } else if (node->right) {
918 assert(node->rightnode == NODE);
919 node = node->right;
920 if (!node->mark && node->parent->mark &&
921 !node->parent->left) {
923 node->mark = 1;
930 node = node->parent;
938 * Compute the index of each node and leaf, which is the offset in the
944 struct node *node;
966 node = tree->root;
968 while (node) {
969 if (!node->mark)
972 if (node->index != index)
973 node->index = index;
974 index += node->size;
976 while (node) {
977 bitmask = 1 << node->bitnum;
978 if (node->mark && (leftmask & bitmask) == 0) {
980 if (node->leftnode == LEAF) {
981 assert(node->left);
982 *tree->leaf_index(tree, node->left) =
984 index += tree->leaf_size(node->left);
986 } else if (node->left) {
987 assert(node->leftnode == NODE);
989 node = node->left;
993 if (node->mark && (rightmask & bitmask) == 0) {
995 if (node->rightnode == LEAF) {
996 assert(node->right);
997 *tree->leaf_index(tree, node->right) = index;
998 index += tree->leaf_size(node->right);
1000 } else if (node->right) {
1001 assert(node->rightnode == NODE);
1003 node = node->right;
1009 node = node->parent;
1025 static int mark_subtree(struct node *node)
1029 if (!node || node->mark)
1031 node->mark = 1;
1032 node->index = node->parent->index;
1034 if (node->leftnode == NODE)
1035 changed += mark_subtree(node->left);
1036 if (node->rightnode == NODE)
1037 changed += mark_subtree(node->right);
1043 * each node needs to store a three-byte offset. The indexes of the
1051 struct node *node;
1052 struct node *right;
1053 struct node *n;
1077 node = tree->root;
1079 while (node) {
1080 if (!node->mark)
1083 if (!node->left || !node->right) {
1086 if (node->rightnode == NODE) {
1088 * If the right node is not marked,
1089 * look for a corresponding node in
1090 * the next tree. Such a node need
1093 right = node->right;
1098 while (n->bitnum != node->bitnum) {
1112 if (n->bitnum != node->bitnum)
1118 /* Make sure the right node is marked. */
1121 offset = right->index - node->index;
1123 offset = *tree->leaf_index(tree, node->right);
1124 offset -= node->index;
1136 if (node->size != size || node->offset != offset) {
1137 node->size = size;
1138 node->offset = offset;
1142 while (node) {
1143 bitmask = 1 << node->bitnum;
1145 if (node->mark && (leftmask & bitmask) == 0) {
1147 if (node->leftnode == LEAF) {
1148 assert(node->left);
1149 } else if (node->left) {
1150 assert(node->leftnode == NODE);
1152 node = node->left;
1156 if (node->mark && (rightmask & bitmask) == 0) {
1159 if (node->rightnode == LEAF) {
1160 assert(node->right);
1161 } else if (node->right) {
1162 assert(node->rightnode == NODE);
1164 node = node->right;
1172 node = node->parent;
1187 struct node *node;
1219 node = tree->root;
1221 while (node) {
1222 if (!node->mark)
1224 assert(node->offset != -1);
1225 assert(node->index == index);
1228 if (node->nextbyte)
1230 byte |= (node->bitnum & BITNUM);
1231 if (node->left && node->right) {
1232 if (node->leftnode == NODE)
1234 if (node->rightnode == NODE)
1236 if (node->offset <= 0xff)
1238 else if (node->offset <= 0xffff)
1243 offset = node->offset;
1252 } else if (node->left) {
1253 if (node->leftnode == NODE)
1258 } else if (node->right) {
1260 if (node->rightnode == NODE)
1269 while (node) {
1270 bitmask = 1 << node->bitnum;
1271 if (node->mark && (leftmask & bitmask) == 0) {
1273 if (node->leftnode == LEAF) {
1274 assert(node->left);
1275 data = tree->leaf_emit(node->left,
1277 size = tree->leaf_size(node->left);
1281 } else if (node->left) {
1282 assert(node->leftnode == NODE);
1284 node = node->left;
1288 if (node->mark && (rightmask & bitmask) == 0) {
1290 if (node->rightnode == LEAF) {
1291 assert(node->right);
1292 data = tree->leaf_emit(node->right,
1294 size = tree->leaf_size(node->right);
1298 } else if (node->right) {
1299 assert(node->rightnode == NODE);
1301 node = node->right;
1307 node = node->parent;
2713 int node;
2719 node = 1;
2721 while (node) {
2732 /* Right node at offset of trie */
2733 node = (*trie & RIGHTNODE);
2741 /* Right node after this node */
2742 node = (*trie & TRIENODE);
2745 /* No right node. */
2751 /* Left node after this node. */
2752 node = (*trie & LEFTNODE);
2755 /* No left node. */
2758 /* Left node after this node */
2759 node = (*trie & TRIENODE);