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!
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;
+}