summaryrefslogtreecommitdiffstats
path: root/Modules/rotatingtree.h
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.h
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.h')
-rw-r--r--Modules/rotatingtree.h27
1 files changed, 27 insertions, 0 deletions
diff --git a/Modules/rotatingtree.h b/Modules/rotatingtree.h
new file mode 100644
index 0000000..97cc8e8
--- /dev/null
+++ b/Modules/rotatingtree.h
@@ -0,0 +1,27 @@
+/* "Rotating trees" (Armin Rigo)
+ *
+ * Google "splay trees" for the general idea.
+ *
+ * It's a dict-like data structure that works best when accesses are not
+ * random, but follow a strong pattern. The one implemented here is for
+ * accesses patterns where the same small set of keys is looked up over
+ * and over again, and this set of keys evolves slowly over time.
+ */
+
+#include <stdlib.h>
+
+#define EMPTY_ROTATING_TREE ((rotating_node_t *)NULL)
+
+typedef struct rotating_node_s rotating_node_t;
+typedef int (*rotating_tree_enum_fn) (rotating_node_t *node, void *arg);
+
+struct rotating_node_s {
+ void *key;
+ rotating_node_t *left;
+ rotating_node_t *right;
+};
+
+void RotatingTree_Add(rotating_node_t **root, rotating_node_t *node);
+rotating_node_t* RotatingTree_Get(rotating_node_t **root, void *key);
+int RotatingTree_Enum(rotating_node_t *root, rotating_tree_enum_fn enumfn,
+ void *arg);