make psplay key const
[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 psplayroot_struct psplayroot;
31 typedef psplayroot* PSplayroot;
32
33 typedef struct psplay_struct psplay;
34 typedef psplay* PSplay;
35
36 typedef int (*psplay_cmp_t)(const void*, const void*);
37 typedef void (*psplay_delete_t)(PSplay);
38
39 //
40 struct psplayroot_struct
41 {
42   PSplay tree;
43   psplay_cmp_t cmp;
44   psplay_delete_t delete;
45   /* amount of elements will some day adjust the probability fucntions, further research necessary */
46   size_t elem_cnt;
47   /* PSplay history[64]; ringbuffer storing the path of a search, optimize 'up' pointer out */
48 };
49
50 PSplayroot
51 psplay_init_root (PSplayroot self, psplay_cmp_t cmp, psplay_delete_t delete);
52
53 PSplayroot
54 psplay_destroy_root (PSplayroot self);
55
56 #define PSPLAYROOT_INITIALIZER(cmp, delete) {NULL, cmp, delete, 0}
57
58 //
59 struct psplay_struct
60 {
61   const void* key;
62   PSplay up;
63   PSplay left;
64   PSplay right;
65 };
66
67
68 PSplay
69 psplay_new (void * key);
70
71 PSplay
72 psplay_init (PSplay self, const void* key);
73
74 void
75 psplay_delete (PSplay node);
76
77 PSplay
78 psplay_insert (PSplayroot root, PSplay node);
79
80 PSplay
81 psplay_find (PSplayroot root, void* key);
82
83 PSplay
84 psplay_remove (PSplayroot root, PSplay node);
85
86 void
87 psplay_dump (PSplay root, FILE* dest, unsigned level);
88
89 #endif