Mercurial > cpython-lru_cache-weakref

annotate Modules/rotatingtree.h @ 78069:a8aa77458e12 3.2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add c_size_t and c_ssize_t to the ctypes summary table.
author Antoine Pitrou <solipsis@pitrou.net>
date Thu, 12 Jul 2012 20:31:50 +0200
parents 29ae5e0fc348
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
36459
3abf33264146 Added the cProfile module.
Armin Rigo <arigo@tunes.org>
parents:
diff changeset
1 /* "Rotating trees" (Armin Rigo)
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 * Google "splay trees" for the general idea.
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 * It's a dict-like data structure that works best when accesses are not
3abf33264146 Added the cProfile module.
Armin Rigo <arigo@tunes.org>
parents:
diff changeset
6 * random, but follow a strong pattern. The one implemented here is for
38453
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents: 36459
diff changeset
7 * access patterns where the same small set of keys is looked up over
36459
3abf33264146 Added the cProfile module.
Armin Rigo <arigo@tunes.org>
parents:
diff changeset
8 * and over again, and this set of keys evolves slowly over time.
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 #include <stdlib.h>
3abf33264146 Added the cProfile module.
Armin Rigo <arigo@tunes.org>
parents:
diff changeset
12
3abf33264146 Added the cProfile module.
Armin Rigo <arigo@tunes.org>
parents:
diff changeset
13 #define EMPTY_ROTATING_TREE ((rotating_node_t *)NULL)
3abf33264146 Added the cProfile module.
Armin Rigo <arigo@tunes.org>
parents:
diff changeset
14
3abf33264146 Added the cProfile module.
Armin Rigo <arigo@tunes.org>
parents:
diff changeset
15 typedef struct rotating_node_s rotating_node_t;
3abf33264146 Added the cProfile module.
Armin Rigo <arigo@tunes.org>
parents:
diff changeset
16 typedef int (*rotating_tree_enum_fn) (rotating_node_t *node, void *arg);
3abf33264146 Added the cProfile module.
Armin Rigo <arigo@tunes.org>
parents:
diff changeset
17
3abf33264146 Added the cProfile module.
Armin Rigo <arigo@tunes.org>
parents:
diff changeset
18 struct rotating_node_s {
3abf33264146 Added the cProfile module.
Armin Rigo <arigo@tunes.org>
parents:
diff changeset
19 void *key;
3abf33264146 Added the cProfile module.
Armin Rigo <arigo@tunes.org>
parents:
diff changeset
20 rotating_node_t *left;
3abf33264146 Added the cProfile module.
Armin Rigo <arigo@tunes.org>
parents:
diff changeset
21 rotating_node_t *right;
3abf33264146 Added the cProfile module.
Armin Rigo <arigo@tunes.org>
parents:
diff changeset
22 };
3abf33264146 Added the cProfile module.
Armin Rigo <arigo@tunes.org>
parents:
diff changeset
23
3abf33264146 Added the cProfile module.
Armin Rigo <arigo@tunes.org>
parents:
diff changeset
24 void RotatingTree_Add(rotating_node_t **root, rotating_node_t *node);
3abf33264146 Added the cProfile module.
Armin Rigo <arigo@tunes.org>
parents:
diff changeset
25 rotating_node_t* RotatingTree_Get(rotating_node_t **root, void *key);
3abf33264146 Added the cProfile module.
Armin Rigo <arigo@tunes.org>
parents:
diff changeset
26 int RotatingTree_Enum(rotating_node_t *root, rotating_tree_enum_fn enumfn,
3abf33264146 Added the cProfile module.
Armin Rigo <arigo@tunes.org>
parents:
diff changeset
27 void *arg);