12a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/* 22a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * ctrees.c 32a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * 42a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * Author: mozman 52a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * Copyright (c) 2010-2013 by Manfred Moitzi 62a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * License: MIT-License 72a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) */ 82a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 92a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "ctrees.h" 102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "stack.h" 112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include <Python.h> 122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define LEFT 0 142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define RIGHT 1 152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define KEY(node) (node->key) 162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define VALUE(node) (node->value) 172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define LEFT_NODE(node) (node->link[LEFT]) 182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define RIGHT_NODE(node) (node->link[RIGHT]) 192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define LINK(node, dir) (node->link[dir]) 202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define XDATA(node) (node->xdata) 212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define RED(node) (node->xdata) 222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define BALANCE(node) (node->xdata) 232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)static node_t * 252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ct_new_node(PyObject *key, PyObject *value, int xdata) 262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){ 272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *new_node = PyMem_Malloc(sizeof(node_t)); 282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (new_node != NULL) { 292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) KEY(new_node) = key; 302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Py_INCREF(key); 312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) VALUE(new_node) = value; 322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Py_INCREF(value); 332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) LEFT_NODE(new_node) = NULL; 342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) RIGHT_NODE(new_node) = NULL; 352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) XDATA(new_node) = xdata; 362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return new_node; 382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)static void 412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ct_delete_node(node_t *node) 422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){ 432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (node != NULL) { 442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Py_XDECREF(KEY(node)); 452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Py_XDECREF(VALUE(node)); 462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) LEFT_NODE(node) = NULL; 472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) RIGHT_NODE(node) = NULL; 482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) PyMem_Free(node); 492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)extern void 532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ct_delete_tree(node_t *root) 542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){ 552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (root == NULL) 562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return; 572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (LEFT_NODE(root) != NULL) { 582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ct_delete_tree(LEFT_NODE(root)); 592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (RIGHT_NODE(root) != NULL) { 612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ct_delete_tree(RIGHT_NODE(root)); 622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ct_delete_node(root); 642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)static void 672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ct_swap_data(node_t *node1, node_t *node2) 682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){ 692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) PyObject *tmp; 702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) tmp = KEY(node1); 712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) KEY(node1) = KEY(node2); 722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) KEY(node2) = tmp; 732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) tmp = VALUE(node1); 742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) VALUE(node1) = VALUE(node2); 752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) VALUE(node2) = tmp; 762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)int 792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ct_compare(PyObject *key1, PyObject *key2) 802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){ 812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int res; 822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) res = PyObject_RichCompareBool(key1, key2, Py_LT); 842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (res > 0) 852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return -1; 862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else if (res < 0) { 872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) PyErr_SetString(PyExc_TypeError, "invalid type for key"); 882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return 0; 892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* second compare: 912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) +1 if key1 > key2 922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 0 if not -> equal 932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) -1 means error, if error, it should happend at the first compare 942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) */ 952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return PyObject_RichCompareBool(key1, key2, Py_GT); 962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)extern node_t * 992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ct_find_node(node_t *root, PyObject *key) 1002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){ 1012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int res; 1022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) while (root != NULL) { 1032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) res = ct_compare(key, KEY(root)); 1042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (res == 0) /* key found */ 1052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return root; 1062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else { 1072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) root = LINK(root, (res > 0)); 1082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return NULL; /* key not found */ 1112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)extern PyObject * 1142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ct_get_item(node_t *root, PyObject *key) 1152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){ 1162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *node; 1172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) PyObject *tuple; 1182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = ct_find_node(root, key); 1202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (node != NULL) { 1212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) tuple = PyTuple_New(2); 1222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) PyTuple_SET_ITEM(tuple, 0, KEY(node)); 1232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) PyTuple_SET_ITEM(tuple, 1, VALUE(node)); 1242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return tuple; 1252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Py_RETURN_NONE; 1272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)extern node_t * 1302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ct_max_node(node_t *root) 1312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/* get node with largest key */ 1322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){ 1332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (root == NULL) 1342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return NULL; 1352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) while (RIGHT_NODE(root) != NULL) 1362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) root = RIGHT_NODE(root); 1372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return root; 1382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)extern node_t * 1412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ct_min_node(node_t *root) 1422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// get node with smallest key 1432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){ 1442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (root == NULL) 1452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return NULL; 1462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) while (LEFT_NODE(root) != NULL) 1472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) root = LEFT_NODE(root); 1482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return root; 1492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)extern int 1522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ct_bintree_remove(node_t **rootaddr, PyObject *key) 1532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/* attention: rootaddr is the address of the root pointer */ 1542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){ 1552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *node, *parent, *replacement; 1562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int direction, cmp_res, down_dir; 1572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = *rootaddr; 1592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (node == NULL) 1612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return 0; /* root is NULL */ 1622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) parent = NULL; 1632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) direction = 0; 1642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) while (1) { 1662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) cmp_res = ct_compare(key, KEY(node)); 1672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (cmp_res == 0) /* key found, remove node */ 1682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) { 1692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if ((LEFT_NODE(node) != NULL) && (RIGHT_NODE(node) != NULL)) { 1702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* find replacement node: smallest key in right-subtree */ 1712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) parent = node; 1722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) direction = RIGHT; 1732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) replacement = RIGHT_NODE(node); 1742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) while (LEFT_NODE(replacement) != NULL) { 1752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) parent = replacement; 1762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) direction = LEFT; 1772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) replacement = LEFT_NODE(replacement); 1782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) LINK(parent, direction) = RIGHT_NODE(replacement); 1802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* swap places */ 1812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ct_swap_data(node, replacement); 1822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = replacement; /* delete replacement node */ 1832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else { 1852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) down_dir = (LEFT_NODE(node) == NULL) ? RIGHT : LEFT; 1862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (parent == NULL) /* root */ 1872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) { 1882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) *rootaddr = LINK(node, down_dir); 1892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else { 1912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) LINK(parent, direction) = LINK(node, down_dir); 1922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ct_delete_node(node); 1952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return 1; /* remove was success full */ 1962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else { 1982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) direction = (cmp_res < 0) ? LEFT : RIGHT; 1992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) parent = node; 2002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = LINK(node, direction); 2012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (node == NULL) 2022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return 0; /* error key not found */ 2032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 2062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)extern int 2082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ct_bintree_insert(node_t **rootaddr, PyObject *key, PyObject *value) 2092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/* attention: rootaddr is the address of the root pointer */ 2102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){ 2112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *parent, *node; 2122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int direction, cval; 2132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = *rootaddr; 2142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (node == NULL) { 2152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = ct_new_node(key, value, 0); /* new node is also the root */ 2162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (node == NULL) 2172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return -1; /* got no memory */ 2182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) *rootaddr = node; 2192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else { 2212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) direction = LEFT; 2222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) parent = NULL; 2232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) while (1) { 2242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (node == NULL) { 2252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = ct_new_node(key, value, 0); 2262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (node == NULL) 2272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return -1; /* get no memory */ 2282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) LINK(parent, direction) = node; 2292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return 1; 2302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) cval = ct_compare(key, KEY(node)); 2322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (cval == 0) { 2332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* key exists, replace value object */ 2342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Py_XDECREF(VALUE(node)); /* release old value object */ 2352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) VALUE(node) = value; /* set new value object */ 2362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Py_INCREF(value); /* take new value object */ 2372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return 0; 2382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else { 2402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) parent = node; 2412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) direction = (cval < 0) ? LEFT : RIGHT; 2422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = LINK(node, direction); 2432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return 1; 2472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 2482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)static int 2502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)is_red (node_t *node) 2512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){ 2522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return (node != NULL) && (RED(node) == 1); 2532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 2542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define rb_new_node(key, value) ct_new_node(key, value, 1) 2562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)static node_t * 2582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)rb_single(node_t *root, int dir) 2592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){ 2602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *save = root->link[!dir]; 2612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) root->link[!dir] = save->link[dir]; 2632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) save->link[dir] = root; 2642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) RED(root) = 1; 2662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) RED(save) = 0; 2672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return save; 2682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 2692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)static node_t * 2712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)rb_double(node_t *root, int dir) 2722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){ 2732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) root->link[!dir] = rb_single(root->link[!dir], !dir); 2742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return rb_single(root, dir); 2752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 2762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define rb_new_node(key, value) ct_new_node(key, value, 1) 2782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)extern int 2802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)rb_insert(node_t **rootaddr, PyObject *key, PyObject *value) 2812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){ 2822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *root = *rootaddr; 2832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (root == NULL) { 2852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* 2862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) We have an empty tree; attach the 2872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) new node directly to the root 2882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) */ 2892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) root = rb_new_node(key, value); 2902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (root == NULL) 2912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return -1; // got no memory 2922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else { 2942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t head; /* False tree root */ 2952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *g, *t; /* Grandparent & parent */ 2962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *p, *q; /* Iterator & parent */ 2972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int dir = 0; 2982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int last = 0; 2992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int new_node = 0; 3002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Set up our helpers */ 3022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) t = &head; 3032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) g = NULL; 3042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) p = NULL; 3052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) RIGHT_NODE(t) = root; 3062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) LEFT_NODE(t) = NULL; 3072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) q = RIGHT_NODE(t); 3082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Search down the tree for a place to insert */ 3102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (;;) { 3112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int cmp_res; 3122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (q == NULL) { 3132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Insert a new node at the first null link */ 3142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) q = rb_new_node(key, value); 3152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) p->link[dir] = q; 3162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) new_node = 1; 3172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (q == NULL) 3182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return -1; // get no memory 3192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 3202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else if (is_red(q->link[0]) && is_red(q->link[1])) { 3212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Simple red violation: color flip */ 3222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) RED(q) = 1; 3232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) RED(q->link[0]) = 0; 3242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) RED(q->link[1]) = 0; 3252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 3262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (is_red(q) && is_red(p)) { 3282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Hard red violation: rotations necessary */ 3292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int dir2 = (t->link[1] == g); 3302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (q == p->link[last]) 3322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) t->link[dir2] = rb_single(g, !last); 3332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else 3342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) t->link[dir2] = rb_double(g, !last); 3352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 3362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Stop working if we inserted a new node. */ 3382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (new_node) 3392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) break; 3402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) cmp_res = ct_compare(KEY(q), key); 3422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (cmp_res == 0) { /* key exists? */ 3432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Py_XDECREF(VALUE(q)); /* release old value object */ 3442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) VALUE(q) = value; /* set new value object */ 3452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Py_INCREF(value); /* take new value object */ 3462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return 0; 3472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 3482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) last = dir; 3492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) dir = (cmp_res < 0); 3502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Move the helpers down */ 3522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (g != NULL) 3532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) t = g; 3542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) g = p; 3562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) p = q; 3572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) q = q->link[dir]; 3582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 3592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Update the root (it may be different) */ 3602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) root = head.link[1]; 3612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 3622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Make the root black for simplified logic */ 3642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) RED(root) = 0; 3652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) (*rootaddr) = root; 3662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return 1; 3672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 3682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)extern int 3702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)rb_remove(node_t **rootaddr, PyObject *key) 3712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){ 3722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *root = *rootaddr; 3732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t head = { { NULL } }; /* False tree root */ 3752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *q, *p, *g; /* Helpers */ 3762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *f = NULL; /* Found item */ 3772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int dir = 1; 3782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (root == NULL) 3802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return 0; 3812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Set up our helpers */ 3832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) q = &head; 3842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) g = p = NULL; 3852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) RIGHT_NODE(q) = root; 3862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* 3882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Search and push a red node down 3892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) to fix red violations as we go 3902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) */ 3912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) while (q->link[dir] != NULL) { 3922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int last = dir; 3932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int cmp_res; 3942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Move the helpers down */ 3962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) g = p, p = q; 3972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) q = q->link[dir]; 3982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) cmp_res = ct_compare(KEY(q), key); 4002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) dir = cmp_res < 0; 4022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* 4042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Save the node with matching data and keep 4052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) going; we'll do removal tasks at the end 4062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) */ 4072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (cmp_res == 0) 4082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) f = q; 4092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Push the red node down with rotations and color flips */ 4112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (!is_red(q) && !is_red(q->link[dir])) { 4122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (is_red(q->link[!dir])) 4132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) p = p->link[last] = rb_single(q, dir); 4142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else if (!is_red(q->link[!dir])) { 4152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *s = p->link[!last]; 4162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (s != NULL) { 4182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (!is_red(s->link[!last]) && 4192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) !is_red(s->link[last])) { 4202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Color flip */ 4212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) RED(p) = 0; 4222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) RED(s) = 1; 4232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) RED(q) = 1; 4242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 4252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else { 4262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int dir2 = g->link[1] == p; 4272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (is_red(s->link[last])) 4292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) g->link[dir2] = rb_double(p, last); 4302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else if (is_red(s->link[!last])) 4312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) g->link[dir2] = rb_single(p, last); 4322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Ensure correct coloring */ 4342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) RED(q) = RED(g->link[dir2]) = 1; 4352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) RED(g->link[dir2]->link[0]) = 0; 4362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) RED(g->link[dir2]->link[1]) = 0; 4372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 4382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 4392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 4402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 4412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 4422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Replace and remove the saved node */ 4442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (f != NULL) { 4452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ct_swap_data(f, q); 4462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) p->link[p->link[1] == q] = q->link[q->link[0] == NULL]; 4472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ct_delete_node(q); 4482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 4492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Update the root (it may be different) */ 4512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) root = head.link[1]; 4522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Make the root black for simplified logic */ 4542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (root != NULL) 4552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) RED(root) = 0; 4562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) *rootaddr = root; 4572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return (f != NULL); 4582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 4592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define avl_new_node(key, value) ct_new_node(key, value, 0) 4612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define height(p) ((p) == NULL ? -1 : (p)->xdata) 4622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define avl_max(a, b) ((a) > (b) ? (a) : (b)) 4632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)static node_t * 4652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)avl_single(node_t *root, int dir) 4662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){ 4672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *save = root->link[!dir]; 4682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int rlh, rrh, slh; 4692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Rotate */ 4712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) root->link[!dir] = save->link[dir]; 4722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) save->link[dir] = root; 4732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Update balance factors */ 4752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) rlh = height(root->link[0]); 4762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) rrh = height(root->link[1]); 4772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) slh = height(save->link[!dir]); 4782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) BALANCE(root) = avl_max(rlh, rrh) + 1; 4802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) BALANCE(save) = avl_max(slh, BALANCE(root)) + 1; 4812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return save; 4832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 4842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)static node_t * 4862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)avl_double(node_t *root, int dir) 4872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){ 4882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) root->link[!dir] = avl_single(root->link[!dir], !dir); 4892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return avl_single(root, dir); 4902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 4912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)extern int 4932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)avl_insert(node_t **rootaddr, PyObject *key, PyObject *value) 4942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){ 4952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *root = *rootaddr; 4962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (root == NULL) { 4982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) root = avl_new_node(key, value); 4992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (root == NULL) 5002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return -1; // got no memory 5012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 5022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else { 5032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *it, *up[32]; 5042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int upd[32], top = 0; 5052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int done = 0; 5062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int cmp_res; 5072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) it = root; 5092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Search for an empty link, save the path */ 5102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (;;) { 5112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Push direction and node onto stack */ 5122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) cmp_res = ct_compare(KEY(it), key); 5132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (cmp_res == 0) { 5142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Py_XDECREF(VALUE(it)); // release old value object 5152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) VALUE(it) = value; // set new value object 5162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Py_INCREF(value); // take new value object 5172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return 0; 5182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 5192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // upd[top] = it->data < data; 5202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) upd[top] = (cmp_res < 0); 5212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) up[top++] = it; 5222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (it->link[upd[top - 1]] == NULL) 5242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) break; 5252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) it = it->link[upd[top - 1]]; 5262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 5272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Insert a new node at the bottom of the tree */ 5292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) it->link[upd[top - 1]] = avl_new_node(key, value); 5302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (it->link[upd[top - 1]] == NULL) 5312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return -1; // got no memory 5322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Walk back up the search path */ 5342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) while (--top >= 0 && !done) { 5352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // int dir = (cmp_res < 0); 5362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int lh, rh, max; 5372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) cmp_res = ct_compare(KEY(up[top]), key); 5392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) lh = height(up[top]->link[upd[top]]); 5412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) rh = height(up[top]->link[!upd[top]]); 5422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Terminate or rebalance as necessary */ 5442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (lh - rh == 0) 5452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) done = 1; 5462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (lh - rh >= 2) { 5472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *a = up[top]->link[upd[top]]->link[upd[top]]; 5482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *b = up[top]->link[upd[top]]->link[!upd[top]]; 5492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (height( a ) >= height( b )) 5512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) up[top] = avl_single(up[top], !upd[top]); 5522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else 5532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) up[top] = avl_double(up[top], !upd[top]); 5542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Fix parent */ 5562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (top != 0) 5572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) up[top - 1]->link[upd[top - 1]] = up[top]; 5582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else 5592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) root = up[0]; 5602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) done = 1; 5612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 5622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Update balance factors */ 5632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) lh = height(up[top]->link[upd[top]]); 5642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) rh = height(up[top]->link[!upd[top]]); 5652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) max = avl_max(lh, rh); 5662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) BALANCE(up[top]) = max + 1; 5672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 5682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 5692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) (*rootaddr) = root; 5702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return 1; 5712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 5722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)extern int 5742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)avl_remove(node_t **rootaddr, PyObject *key) 5752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){ 5762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *root = *rootaddr; 5772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int cmp_res; 5782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (root != NULL) { 5802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *it, *up[32]; 5812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int upd[32], top = 0; 5822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) it = root; 5842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (;;) { 5852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Terminate if not found */ 5862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (it == NULL) 5872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return 0; 5882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) cmp_res = ct_compare(KEY(it), key); 5892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (cmp_res == 0) 5902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) break; 5912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Push direction and node onto stack */ 5932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) upd[top] = (cmp_res < 0); 5942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) up[top++] = it; 5952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) it = it->link[upd[top - 1]]; 5962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 5972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Remove the node */ 5992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (it->link[0] == NULL || 6002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) it->link[1] == NULL) { 6012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Which child is not null? */ 6022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int dir = it->link[0] == NULL; 6032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 6042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Fix parent */ 6052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (top != 0) 6062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) up[top - 1]->link[upd[top - 1]] = it->link[dir]; 6072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else 6082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) root = it->link[dir]; 6092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 6102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ct_delete_node(it); 6112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 6122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else { 6132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Find the inorder successor */ 6142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *heir = it->link[1]; 6152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 6162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Save the path */ 6172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) upd[top] = 1; 6182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) up[top++] = it; 6192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 6202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) while ( heir->link[0] != NULL ) { 6212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) upd[top] = 0; 6222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) up[top++] = heir; 6232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) heir = heir->link[0]; 6242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 6252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Swap data */ 6262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ct_swap_data(it, heir); 6272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Unlink successor and fix parent */ 6282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) up[top - 1]->link[up[top - 1] == it] = heir->link[1]; 6292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ct_delete_node(heir); 6302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 6312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 6322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Walk back up the search path */ 6332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) while (--top >= 0) { 6342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int lh = height(up[top]->link[upd[top]]); 6352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int rh = height(up[top]->link[!upd[top]]); 6362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int max = avl_max(lh, rh); 6372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 6382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Update balance factors */ 6392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) BALANCE(up[top]) = max + 1; 6402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 6412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Terminate or rebalance as necessary */ 6422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (lh - rh == -1) 6432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) break; 6442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (lh - rh <= -2) { 6452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *a = up[top]->link[!upd[top]]->link[upd[top]]; 6462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *b = up[top]->link[!upd[top]]->link[!upd[top]]; 6472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 6482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (height(a) <= height(b)) 6492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) up[top] = avl_single(up[top], upd[top]); 6502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else 6512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) up[top] = avl_double(up[top], upd[top]); 6522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 6532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* Fix parent */ 6542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (top != 0) 6552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) up[top - 1]->link[upd[top - 1]] = up[top]; 6562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else 6572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) root = up[0]; 6582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 6592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 6602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 6612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) (*rootaddr) = root; 6622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return 1; 6632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 6642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 6652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)extern node_t * 6662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ct_succ_node(node_t *root, PyObject *key) 6672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){ 6682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *succ = NULL; 6692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *node = root; 6702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int cval; 6712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 6722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) while (node != NULL) { 6732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) cval = ct_compare(key, KEY(node)); 6742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (cval == 0) 6752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) break; 6762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else if (cval < 0) { 6772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if ((succ == NULL) || 6782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) (ct_compare(KEY(node), KEY(succ)) < 0)) 6792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) succ = node; 6802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = LEFT_NODE(node); 6812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } else 6822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = RIGHT_NODE(node); 6832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 6842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (node == NULL) 6852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return NULL; 6862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* found node of key */ 6872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (RIGHT_NODE(node) != NULL) { 6882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* find smallest node of right subtree */ 6892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = RIGHT_NODE(node); 6902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) while (LEFT_NODE(node) != NULL) 6912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = LEFT_NODE(node); 6922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (succ == NULL) 6932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) succ = node; 6942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else if (ct_compare(KEY(node), KEY(succ)) < 0) 6952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) succ = node; 6962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 6972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return succ; 6982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 6992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 7002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)extern node_t * 7012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ct_prev_node(node_t *root, PyObject *key) 7022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){ 7032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *prev = NULL; 7042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *node = root; 7052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int cval; 7062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 7072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) while (node != NULL) { 7082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) cval = ct_compare(key, KEY(node)); 7092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (cval == 0) 7102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) break; 7112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else if (cval < 0) 7122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = LEFT_NODE(node); 7132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else { 7142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if ((prev == NULL) || (ct_compare(KEY(node), KEY(prev)) > 0)) 7152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) prev = node; 7162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = RIGHT_NODE(node); 7172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 7182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 7192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (node == NULL) /* stay at dead end (None) */ 7202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return NULL; 7212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* found node of key */ 7222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (LEFT_NODE(node) != NULL) { 7232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* find biggest node of left subtree */ 7242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = LEFT_NODE(node); 7252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) while (RIGHT_NODE(node) != NULL) 7262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = RIGHT_NODE(node); 7272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (prev == NULL) 7282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) prev = node; 7292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else if (ct_compare(KEY(node), KEY(prev)) > 0) 7302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) prev = node; 7312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 7322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return prev; 7332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 7342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 7352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)extern node_t * 7362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ct_floor_node(node_t *root, PyObject *key) 7372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){ 7382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *prev = NULL; 7392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *node = root; 7402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int cval; 7412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 7422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) while (node != NULL) { 7432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) cval = ct_compare(key, KEY(node)); 7442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (cval == 0) 7452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return node; 7462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else if (cval < 0) 7472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = LEFT_NODE(node); 7482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else { 7492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if ((prev == NULL) || (ct_compare(KEY(node), KEY(prev)) > 0)) 7502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) prev = node; 7512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = RIGHT_NODE(node); 7522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 7532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 7542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return prev; 7552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 7562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 7572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)extern node_t * 7582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ct_ceiling_node(node_t *root, PyObject *key) 7592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){ 7602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *succ = NULL; 7612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *node = root; 7622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int cval; 7632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 7642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) while (node != NULL) { 7652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) cval = ct_compare(key, KEY(node)); 7662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (cval == 0) 7672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return node; 7682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else if (cval < 0) { 7692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if ((succ == NULL) || 7702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) (ct_compare(KEY(node), KEY(succ)) < 0)) 7712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) succ = node; 7722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = LEFT_NODE(node); 7732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } else 7742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = RIGHT_NODE(node); 7752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 7762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return succ; 7772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 7782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 7792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)extern int 7802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ct_index_of(node_t *root, PyObject *key) 7812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/* 7822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)get index of item <key>, returns -1 if key not found. 7832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)*/ 7842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){ 7852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *node = root; 7862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int index = 0; 7872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int go_down = 1; 7882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_stack_t *stack; 7892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) stack = stack_init(32); 7902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 7912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (;;) { 7922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if ((LEFT_NODE(node) != NULL) && go_down) { 7932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) stack_push(stack, node); 7942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = LEFT_NODE(node); 7952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 7962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else { 7972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (ct_compare(KEY(node), key) == 0) { 7982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) stack_delete(stack); 7992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return index; 8002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 8012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) index++; 8022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (RIGHT_NODE(node) != NULL) { 8032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = RIGHT_NODE(node); 8042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) go_down = 1; 8052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 8062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else { 8072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (stack_is_empty(stack)) { 8082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) stack_delete(stack); 8092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return -1; 8102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 8112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = stack_pop(stack); 8122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) go_down = 0; 8132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 8142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 8152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 8162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 8172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 8182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)extern node_t * 8192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ct_node_at(node_t *root, int index) 8202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){ 8212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/* 8222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)root -- root node of tree 8232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)index -- index of wanted node 8242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 8252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)return NULL if index out of range 8262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)*/ 8272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *node = root; 8282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int counter = 0; 8292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int go_down = 1; 8302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_stack_t *stack; 8312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 8322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (index < 0) return NULL; 8332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 8342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) stack = stack_init(32); 8352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 8362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for(;;) { 8372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if ((LEFT_NODE(node) != NULL) && go_down) { 8382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) stack_push(stack, node); 8392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = LEFT_NODE(node); 8402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 8412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else { 8422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (counter == index) { 8432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /* reached wanted index */ 8442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) stack_delete(stack); 8452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return node; 8462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 8472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) counter++; 8482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (RIGHT_NODE(node) != NULL) { 8492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = RIGHT_NODE(node); 8502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) go_down = 1; 8512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 8522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else { 8532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (stack_is_empty(stack)) { /* index out of range */ 8542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) stack_delete(stack); 8552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return NULL; 8562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 8572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = stack_pop(stack); 8582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) go_down = 0; 8592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 8602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 8612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 8622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 863