cpython-lru_cache-weakref: Modules/rotatingtree.c annotate

annotate Modules/rotatingtree.c @ 80661:94de77bd0b4b 2.7

Issue #16194: document imp.load_dynamic problems when read several extension modules from the same binary object file.

author	Andrew Svetlov <andrew.svetlov@gmail.com>
date	Thu, 29 Nov 2012 19:51:28 +0200
parents	fd25030223b0
children

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

Mercurial > cpython-lru_cache-weakref

annotate Modules/rotatingtree.c @ 80661:94de77bd0b4b 2.7