Lines Matching refs:node
15 #define KEY(node) (node->key)
16 #define VALUE(node) (node->value)
17 #define LEFT_NODE(node) (node->link[LEFT])
18 #define RIGHT_NODE(node) (node->link[RIGHT])
19 #define LINK(node, dir) (node->link[dir])
20 #define XDATA(node) (node->xdata)
21 #define RED(node) (node->xdata)
22 #define BALANCE(node) (node->xdata)
41 ct_delete_node(node_t *node)
43 if (node != NULL) {
44 Py_XDECREF(KEY(node));
45 Py_XDECREF(VALUE(node));
46 LEFT_NODE(node) = NULL;
47 RIGHT_NODE(node) = NULL;
48 PyMem_Free(node);
116 node_t *node;
119 node = ct_find_node(root, key);
120 if (node != NULL) {
122 PyTuple_SET_ITEM(tuple, 0, KEY(node));
123 PyTuple_SET_ITEM(tuple, 1, VALUE(node));
131 /* get node with largest key */
142 // get node with smallest key
155 node_t *node, *parent, *replacement;
158 node = *rootaddr;
160 if (node == NULL)
166 cmp_res = ct_compare(key, KEY(node));
167 if (cmp_res == 0) /* key found, remove node */
169 if ((LEFT_NODE(node) != NULL) && (RIGHT_NODE(node) != NULL)) {
170 /* find replacement node: smallest key in right-subtree */
171 parent = node;
173 replacement = RIGHT_NODE(node);
181 ct_swap_data(node, replacement);
182 node = replacement; /* delete replacement node */
185 down_dir = (LEFT_NODE(node) == NULL) ? RIGHT : LEFT;
188 *rootaddr = LINK(node, down_dir);
191 LINK(parent, direction) = LINK(node, down_dir);
194 ct_delete_node(node);
199 parent = node;
200 node = LINK(node, direction);
201 if (node == NULL)
211 node_t *parent, *node;
213 node = *rootaddr;
214 if (node == NULL) {
215 node = ct_new_node(key, value, 0); /* new node is also the root */
216 if (node == NULL)
218 *rootaddr = node;
224 if (node == NULL) {
225 node = ct_new_node(key, value, 0);
226 if (node == NULL)
228 LINK(parent, direction) = node;
231 cval = ct_compare(key, KEY(node));
234 Py_XDECREF(VALUE(node)); /* release old value object */
235 VALUE(node) = value; /* set new value object */
240 parent = node;
242 node = LINK(node, direction);
250 is_red (node_t *node)
252 return (node != NULL) && (RED(node) == 1);
287 new node directly to the root
313 /* Insert a new node at the first null link */
337 /* Stop working if we inserted a new node. */
388 Search and push a red node down
404 Save the node with matching data and keep
410 /* Push the red node down with rotations and color flips */
443 /* Replace and remove the saved node */
511 /* Push direction and node onto stack */
528 /* Insert a new node at the bottom of the tree */
592 /* Push direction and node onto stack */
598 /* Remove the node */
669 node_t *node = root;
672 while (node != NULL) {
673 cval = ct_compare(key, KEY(node));
678 (ct_compare(KEY(node), KEY(succ)) < 0))
679 succ = node;
680 node = LEFT_NODE(node);
682 node = RIGHT_NODE(node);
684 if (node == NULL)
686 /* found node of key */
687 if (RIGHT_NODE(node) != NULL) {
688 /* find smallest node of right subtree */
689 node = RIGHT_NODE(node);
690 while (LEFT_NODE(node) != NULL)
691 node = LEFT_NODE(node);
693 succ = node;
694 else if (ct_compare(KEY(node), KEY(succ)) < 0)
695 succ = node;
704 node_t *node = root;
707 while (node != NULL) {
708 cval = ct_compare(key, KEY(node));
712 node = LEFT_NODE(node);
714 if ((prev == NULL) || (ct_compare(KEY(node), KEY(prev)) > 0))
715 prev = node;
716 node = RIGHT_NODE(node);
719 if (node == NULL) /* stay at dead end (None) */
721 /* found node of key */
722 if (LEFT_NODE(node) != NULL) {
723 /* find biggest node of left subtree */
724 node = LEFT_NODE(node);
725 while (RIGHT_NODE(node) != NULL)
726 node = RIGHT_NODE(node);
728 prev = node;
729 else if (ct_compare(KEY(node), KEY(prev)) > 0)
730 prev = node;
739 node_t *node = root;
742 while (node != NULL) {
743 cval = ct_compare(key, KEY(node));
745 return node;
747 node = LEFT_NODE(node);
749 if ((prev == NULL) || (ct_compare(KEY(node), KEY(prev)) > 0))
750 prev = node;
751 node = RIGHT_NODE(node);
761 node_t *node = root;
764 while (node != NULL) {
765 cval = ct_compare(key, KEY(node));
767 return node;
770 (ct_compare(KEY(node), KEY(succ)) < 0))
771 succ = node;
772 node = LEFT_NODE(node);
774 node = RIGHT_NODE(node);
785 node_t *node = root;
792 if ((LEFT_NODE(node) != NULL) && go_down) {
793 stack_push(stack, node);
794 node = LEFT_NODE(node);
797 if (ct_compare(KEY(node), key) == 0) {
802 if (RIGHT_NODE(node) != NULL) {
803 node = RIGHT_NODE(node);
811 node = stack_pop(stack);
822 root -- root node of tree
823 index -- index of wanted node
827 node_t *node = root;
837 if ((LEFT_NODE(node) != NULL) && go_down) {
838 stack_push(stack, node);
839 node = LEFT_NODE(node);
845 return node;
848 if (RIGHT_NODE(node) != NULL) {
849 node = RIGHT_NODE(node);
857 node = stack_pop(stack);