Python code coverage for Modules/rotatingtree.c

#	count	content
1	n/a	#include "rotatingtree.h"
2	n/a
3	n/a	#define KEY_LOWER_THAN(key1, key2) ((char)(key1) < (char)(key2))
4	n/a
5	n/a	/* The randombits() function below is a fast-and-dirty generator that
6	n/a	* is probably irregular enough for our purposes. Note that it's biased:
7	n/a	* I think that ones are slightly more probable than zeroes. It's not
8	n/a	* important here, though.
9	n/a	*/
10	n/a
11	n/a	static unsigned int random_value = 1;
12	n/a	static unsigned int random_stream = 0;
13	n/a
14	n/a	static int
15	n/a	randombits(int bits)
16	n/a	{
17	n/a	int result;
18	n/a	if (random_stream < (1U << bits)) {
19	n/a	random_value *= 1082527;
20	n/a	random_stream = random_value;
21	n/a	}
22	n/a	result = random_stream & ((1<<bits)-1);
23	n/a	random_stream >>= bits;
24	n/a	return result;
25	n/a	}
26	n/a
27	n/a
28	n/a	/* Insert a new node into the tree.
29	n/a	(root) is modified to point to the new root. /
30	n/a	void
31	n/a	RotatingTree_Add(rotating_node_t *root, rotating_node_t node)
32	n/a	{
33	n/a	while (*root != NULL) {
34	n/a	if (KEY_LOWER_THAN(node->key, (*root)->key))
35	n/a	root = &((*root)->left);
36	n/a	else
37	n/a	root = &((*root)->right);
38	n/a	}
39	n/a	node->left = NULL;
40	n/a	node->right = NULL;
41	n/a	*root = node;
42	n/a	}
43	n/a
44	n/a	/* Locate the node with the given key. This is the most complicated
45	n/a	function because it occasionally rebalances the tree to move the
46	n/a	resulting node closer to the root. */
47	n/a	rotating_node_t *
48	n/a	RotatingTree_Get(rotating_node_t *root, void key)
49	n/a	{
50	n/a	if (randombits(3) != 4) {
51	n/a	/* Fast path, no rebalancing */
52	n/a	rotating_node_t node = root;
53	n/a	while (node != NULL) {
54	n/a	if (node->key == key)
55	n/a	return node;
56	n/a	if (KEY_LOWER_THAN(key, node->key))
57	n/a	node = node->left;
58	n/a	else
59	n/a	node = node->right;
60	n/a	}
61	n/a	return NULL;
62	n/a	}
63	n/a	else {
64	n/a	rotating_node_t **pnode = root;
65	n/a	rotating_node_t node = pnode;
66	n/a	rotating_node_t *next;
67	n/a	int rotate;
68	n/a	if (node == NULL)
69	n/a	return NULL;
70	n/a	while (1) {
71	n/a	if (node->key == key)
72	n/a	return node;
73	n/a	rotate = !randombits(1);
74	n/a	if (KEY_LOWER_THAN(key, node->key)) {
75	n/a	next = node->left;
76	n/a	if (next == NULL)
77	n/a	return NULL;
78	n/a	if (rotate) {
79	n/a	node->left = next->right;
80	n/a	next->right = node;
81	n/a	*pnode = next;
82	n/a	}
83	n/a	else
84	n/a	pnode = &(node->left);
85	n/a	}
86	n/a	else {
87	n/a	next = node->right;
88	n/a	if (next == NULL)
89	n/a	return NULL;
90	n/a	if (rotate) {
91	n/a	node->right = next->left;
92	n/a	next->left = node;
93	n/a	*pnode = next;
94	n/a	}
95	n/a	else
96	n/a	pnode = &(node->right);
97	n/a	}
98	n/a	node = next;
99	n/a	}
100	n/a	}
101	n/a	}
102	n/a
103	n/a	/* Enumerate all nodes in the tree. The callback enumfn() should return
104	n/a	zero to continue the enumeration, or non-zero to interrupt it.
105	n/a	A non-zero value is directly returned by RotatingTree_Enum(). */
106	n/a	int
107	n/a	RotatingTree_Enum(rotating_node_t *root, rotating_tree_enum_fn enumfn,
108	n/a	void *arg)
109	n/a	{
110	n/a	int result;
111	n/a	rotating_node_t *node;
112	n/a	while (root != NULL) {
113	n/a	result = RotatingTree_Enum(root->left, enumfn, arg);
114	n/a	if (result != 0) return result;
115	n/a	node = root->right;
116	n/a	result = enumfn(root, arg);
117	n/a	if (result != 0) return result;
118	n/a	root = node;
119	n/a	}
120	n/a	return 0;
121	n/a	}