summaryrefslogtreecommitdiffstats
path: root/Modules/rotatingtree.c
diff options
context:
space:
mode:
authorArmin Rigo <arigo@tunes.org>2006-02-08 12:53:56 (GMT)
committerArmin Rigo <arigo@tunes.org>2006-02-08 12:53:56 (GMT)
commita871ef2b3e924f058ec1b0aed7d4c83a546414b7 (patch)
tree0f214529cc5f93d06b28e56569d36c1d1ee80996 /Modules/rotatingtree.c
parent5eefdca65477bd8d3a408c380323d4af3228a667 (diff)
downloadcpython-a871ef2b3e924f058ec1b0aed7d4c83a546414b7.zip
cpython-a871ef2b3e924f058ec1b0aed7d4c83a546414b7.tar.gz
cpython-a871ef2b3e924f058ec1b0aed7d4c83a546414b7.tar.bz2
Added the cProfile module.
Based on lsprof (patch #1212837) by Brett Rosen and Ted Czotter. With further editing by Michael Hudson and myself. History in svn repo: http://codespeak.net/svn/user/arigo/hack/misc/lsprof * Module/_lsprof.c is the internal C module, Lib/cProfile.py a wrapper. * pstats.py updated to display cProfile's caller/callee timings if available. * setup.py and NEWS updated. * documentation updates in the profiler section: - explain the differences between the three profilers that we have now - profile and cProfile can use a unified documentation, like (c)Pickle - mention that hotshot is "for specialized usage" now - removed references to the "old profiler" that no longer exists * test updates: - extended test_profile to cover delicate cases like recursion - added tests for the caller/callee displays - added test_cProfile, performing the same tests for cProfile * TO-DO: - cProfile gives a nicer name to built-in, particularly built-in methods, which could be backported to profile. - not tested on Windows recently!
Diffstat (limited to 'Modules/rotatingtree.c')
-rw-r--r--Modules/rotatingtree.c121
1 files changed, 121 insertions, 0 deletions
diff --git a/Modules/rotatingtree.c b/Modules/rotatingtree.c
new file mode 100644
index 0000000..952725b
--- /dev/null
+++ b/Modules/rotatingtree.c
@@ -0,0 +1,121 @@
+#include "rotatingtree.h"
+
+#define KEY_LOWER_THAN(key1, key2) ((char*)(key1) < (char*)(key2))
+
+/* The randombits() function below is a fast-and-dirty generator that
+ * is probably irregular enough for our purposes. Note that it's biased:
+ * I think that ones are slightly more probable than zeroes. It's not
+ * important here, though.
+ */
+
+static unsigned int random_value = 1;
+static unsigned int random_stream = 0;
+
+static int
+randombits(int bits)
+{
+ int result;
+ if (random_stream < (1<<bits)) {
+ random_value *= 1082527;
+ random_stream = random_value;
+ }
+ result = random_stream & ((1<<bits)-1);
+ random_stream >>= bits;
+ return result;
+}
+
+
+/* Insert a new node into the tree.
+ (*root) is modified to point to the new root. */
+void
+RotatingTree_Add(rotating_node_t **root, rotating_node_t *node)
+{
+ while (*root != NULL) {
+ if (KEY_LOWER_THAN(node->key, (*root)->key))
+ root = &((*root)->left);
+ else
+ root = &((*root)->right);
+ }
+ node->left = NULL;
+ node->right = NULL;
+ *root = node;
+}
+
+/* Locate the node with the given key. This is the most complicated
+ function because it occasionally rebalances the tree to move the
+ resulting node closer to the root. */
+rotating_node_t *
+RotatingTree_Get(rotating_node_t **root, void *key)
+{
+ if (randombits(3) != 4) {
+ /* Fast path, no rebalancing */
+ rotating_node_t *node = *root;
+ while (node != NULL) {
+ if (node->key == key)
+ return node;
+ if (KEY_LOWER_THAN(key, node->key))
+ node = node->left;
+ else
+ node = node->right;
+ }
+ return NULL;
+ }
+ else {
+ rotating_node_t **pnode = root;
+ rotating_node_t *node = *pnode;
+ rotating_node_t *next;
+ int rotate;
+ if (node == NULL)
+ return NULL;
+ while (1) {
+ if (node->key == key)
+ return node;
+ rotate = !randombits(1);
+ if (KEY_LOWER_THAN(key, node->key)) {
+ next = node->left;
+ if (next == NULL)
+ return NULL;
+ if (rotate) {
+ node->left = next->right;
+ next->right = node;
+ *pnode = next;
+ }
+ else
+ pnode = &(node->left);
+ }
+ else {
+ next = node->right;
+ if (next == NULL)
+ return NULL;
+ if (rotate) {
+ node->right = next->left;
+ next->left = node;
+ *pnode = next;
+ }
+ else
+ pnode = &(node->right);
+ }
+ node = next;
+ }
+ }
+}
+
+/* Enumerate all nodes in the tree. The callback enumfn() should return
+ zero to continue the enumeration, or non-zero to interrupt it.
+ A non-zero value is directly returned by RotatingTree_Enum(). */
+int
+RotatingTree_Enum(rotating_node_t *root, rotating_tree_enum_fn enumfn,
+ void *arg)
+{
+ int result;
+ rotating_node_t *node;
+ while (root != NULL) {
+ result = RotatingTree_Enum(root->left, enumfn, arg);
+ if (result != 0) return result;
+ node = root->right;
+ result = enumfn(root, arg);
+ if (result != 0) return result;
+ root = node;
+ }
+ return 0;
+}