probabilistic splay tree
[rxpd] / psplay.h
1 /*
2     psplay.h - probabilistic splay tree
3
4   Copyright (C)
5     2004, 2005, 2006,   Christian Thaeter <chth@gmx.net>
6   Copyright (C)         CinelerraCV
7     2007,               Christian Thaeter <ct@pipapo.org>
8
9   This program is free software; you can redistribute it and/or
10   modify it under the terms of the GNU General Public License as
11   published by the Free Software Foundation; either version 2 of the
12   License, or (at your option) any later version.
13
14   This program is distributed in the hope that it will be useful,
15   but WITHOUT ANY WARRANTY; without even the implied warranty of
16   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17   GNU General Public License for more details.
18
19   You should have received a copy of the GNU General Public License
20   along with this program; if not, write to the Free Software
21   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
22 */
23
24 #ifndef PSPLAY_H
25 #define PSPLAY_H
26
27 #include <stdint.h>
28 #include <stdio.h>
29
30 typedef struct psplay_struct psplay;
31 typedef psplay* PSplay;
32 typedef PSplay* PSplay_ref;
33
34 struct psplay_struct
35 {
36   void* key;
37   PSplay up;
38   PSplay left;
39   PSplay right;
40 };
41
42 typedef int (*psplay_cmp_t)(const void*, const void*);
43
44 PSplay
45 psplay_new (void * key);
46
47 PSplay
48 psplay_init (PSplay self, void* key);
49
50 void
51 psplay_delete (PSplay node);
52
53 PSplay
54 psplay_insert (PSplay_ref root, PSplay node, psplay_cmp_t cmp);
55
56 PSplay
57 psplay_find (PSplay_ref root, void* key, psplay_cmp_t cmp);
58
59 PSplay
60 psplay_remove (PSplay_ref root, PSplay node);
61
62 /*
63 void
64 psplay_dump (PSplay root, FILE* dest, unsigned level);
65 */
66
67 #endif