APPEND/PREPEND commands
[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 enum psplay_order_e
31   {
32     PSPLAY_PREORDER,
33     PSPLAY_INORDER,
34     PSPLAY_POSTORDER
35   };
36
37 typedef struct psplayroot_struct psplayroot;
38 typedef psplayroot* PSplayroot;
39
40 typedef struct psplay_struct psplay;
41 typedef psplay* PSplay;
42
43 typedef int (*psplay_cmp_t)(const void*, const void*);
44 typedef void (*psplay_delete_t)(PSplay);
45 typedef psplay_delete_t (*psplay_action_t)(PSplay node, const enum psplay_order_e which, int level, void* data);
46
47 //
48 struct psplayroot_struct
49 {
50   PSplay tree;
51   psplay_cmp_t cmp;
52   psplay_delete_t delete;
53   /* amount of elements will some day adjust the probability fucntions, further research necessary */
54   size_t elem_cnt;
55   /* PSplay history[64]; ringbuffer storing the path of a search, optimize 'up' pointer out */
56 };
57
58 PSplayroot
59 psplay_init_root (PSplayroot self, psplay_cmp_t cmp, psplay_delete_t delete);
60
61 PSplayroot
62 psplay_destroy_root (PSplayroot self);
63
64 static inline int
65 psplay_isempty_root (PSplayroot root)
66 {
67   return !root->tree;
68 }
69
70 #define PSPLAYROOT_INITIALIZER(cmp, delete) {NULL, cmp, delete, 0}
71
72 //
73 struct psplay_struct
74 {
75   const void* key;
76   PSplay up;
77   PSplay left;
78   PSplay right;
79 };
80
81
82 PSplay
83 psplay_new (void * key);
84
85 PSplay
86 psplay_init (PSplay self, const void* key);
87
88 void
89 psplay_delete (PSplay node);
90
91 PSplay
92 psplay_insert (PSplayroot root, PSplay node);
93
94 PSplay
95 psplay_find (PSplayroot root, void* key);
96
97 PSplay
98 psplay_remove (PSplayroot root, PSplay node);
99
100 extern const psplay_delete_t PSPLAY_CONT;
101 extern const psplay_delete_t PSPLAY_STOP;
102 extern const psplay_delete_t PSPLAY_REMOVE;
103
104 int
105 psplay_walk (PSplayroot root, PSplay node, psplay_action_t action, int level, void* data);
106
107
108 void
109 psplay_dump (PSplayroot root, FILE* dest);
110
111
112 #endif