1 | /* Updated: 2006-04-07 to deal with duplicate inserts */ |
---|
2 | #include <stdio.h> |
---|
3 | #include <inttypes.h> |
---|
4 | #include <lt_inttypes.h> |
---|
5 | #include <stdlib.h> |
---|
6 | #include "contain.h" |
---|
7 | |
---|
8 | splay *splay_search_tree(splay *tree, splay_cmp_t cmp, splay *node) { |
---|
9 | splay N, *l, *r, *y; |
---|
10 | |
---|
11 | if (tree == NULL) { |
---|
12 | return NULL; |
---|
13 | } |
---|
14 | |
---|
15 | N.left = N.right = 0; |
---|
16 | l = r = &N; |
---|
17 | |
---|
18 | for (;;) { |
---|
19 | int cmpres = cmp(node,tree); |
---|
20 | if (cmpres<0) { |
---|
21 | if (tree->left == NULL) |
---|
22 | break; |
---|
23 | if (cmp(node,tree->left)<0) { |
---|
24 | y = tree->left; |
---|
25 | tree->left = y->right; |
---|
26 | y->right = tree; |
---|
27 | tree = y; |
---|
28 | if (tree->left == NULL) |
---|
29 | break; |
---|
30 | } |
---|
31 | r->left = tree; |
---|
32 | r = tree; |
---|
33 | tree = tree->left; |
---|
34 | } else if (cmpres>0) { |
---|
35 | if (tree->right == NULL) |
---|
36 | break; |
---|
37 | if (cmp(node,tree->right)>0) { |
---|
38 | y = tree->right; |
---|
39 | tree->right = y->left; |
---|
40 | y->left = tree; |
---|
41 | tree = y; |
---|
42 | if (tree->right == NULL) |
---|
43 | break; |
---|
44 | } |
---|
45 | l->right = tree; |
---|
46 | l = tree; |
---|
47 | tree = tree->right; |
---|
48 | } else { |
---|
49 | break; |
---|
50 | } |
---|
51 | } |
---|
52 | l->right = tree->left; |
---|
53 | r->left = tree->right; |
---|
54 | tree->left = N.right; |
---|
55 | tree->right = N.left; |
---|
56 | return tree; |
---|
57 | } |
---|
58 | |
---|
59 | splay *splay_delete(splay *tree, splay_cmp_t cmp, splay *node) { |
---|
60 | splay *s; |
---|
61 | |
---|
62 | if (!tree) |
---|
63 | return 0; |
---|
64 | |
---|
65 | tree = splay_search_tree(tree, cmp, node); |
---|
66 | if (cmp(tree,node)==0) { |
---|
67 | if (tree->left == NULL) { |
---|
68 | s = tree->right; |
---|
69 | } else { |
---|
70 | s = splay_search_tree(tree->left, cmp, node); |
---|
71 | s->right = tree->right; |
---|
72 | } |
---|
73 | free(tree); |
---|
74 | return s; |
---|
75 | } |
---|
76 | return tree; |
---|
77 | } |
---|
78 | |
---|
79 | void splay_purge(splay *tree) { |
---|
80 | |
---|
81 | if (!tree) |
---|
82 | return; |
---|
83 | |
---|
84 | if (tree->left) |
---|
85 | splay_purge(tree->left); |
---|
86 | if (tree->right) |
---|
87 | splay_purge(tree->right); |
---|
88 | free(tree); |
---|
89 | } |
---|
90 | |
---|
91 | |
---|
92 | |
---|
93 | splay *splay_insert(splay *tree, splay_cmp_t cmp, splay *node) |
---|
94 | { |
---|
95 | if (tree == NULL) { |
---|
96 | tree = node; |
---|
97 | node->left = NULL; |
---|
98 | node->right = NULL; |
---|
99 | return tree; |
---|
100 | } |
---|
101 | tree=splay_search_tree(tree,cmp,node); |
---|
102 | if (cmp(node,tree)<0) { |
---|
103 | node->left = tree->left; |
---|
104 | node->right = tree; |
---|
105 | tree->left = NULL; |
---|
106 | } else if (cmp(node,tree)>0) { |
---|
107 | node->right = tree->right; |
---|
108 | node->left = tree; |
---|
109 | tree->right = NULL; |
---|
110 | } else { |
---|
111 | /* Replace the root node with the current node */ |
---|
112 | node->left = tree->left; |
---|
113 | node->right = tree->right; |
---|
114 | free(tree); |
---|
115 | tree=node; |
---|
116 | } |
---|
117 | |
---|
118 | return tree; |
---|
119 | } |
---|
120 | |
---|
121 | void splay_visit(const splay *tree, visitor_t pre,visitor_t inorder,visitor_t post,void *userdata) |
---|
122 | { |
---|
123 | if (!tree) return; |
---|
124 | if (pre) pre(tree,userdata); |
---|
125 | splay_visit(tree->left,pre,inorder,post,userdata); |
---|
126 | if (inorder) inorder(tree,userdata); |
---|
127 | splay_visit(tree->right,pre,inorder,post,userdata); |
---|
128 | if (post) post(tree,userdata); |
---|
129 | } |
---|
130 | |
---|
131 | |
---|
132 | #ifdef TEST |
---|
133 | #include <string.h> |
---|
134 | struct foo_t { |
---|
135 | splay tree; |
---|
136 | char *key; |
---|
137 | char *value; |
---|
138 | }; |
---|
139 | |
---|
140 | |
---|
141 | void visitor_pre(const struct foo_t *a) |
---|
142 | { |
---|
143 | printf("{\n"); |
---|
144 | } |
---|
145 | void visitor_inorder(const struct foo_t *a) |
---|
146 | { |
---|
147 | printf("%s: %s\n",a->key,a->value); |
---|
148 | } |
---|
149 | void visitor_post(const struct foo_t *a) |
---|
150 | { |
---|
151 | printf("}\n"); |
---|
152 | } |
---|
153 | |
---|
154 | int cmp(const struct foo_t *a,const struct foo_t *b) |
---|
155 | { |
---|
156 | int ret= strcmp(a->key,b->key); |
---|
157 | printf("cmp(%s,%s)==%i\n",a->key,b->key,ret); |
---|
158 | return ret; |
---|
159 | } |
---|
160 | |
---|
161 | int main(int argc, char *argv[]) |
---|
162 | { |
---|
163 | struct foo_t *tree = NULL; |
---|
164 | struct foo_t a = { { NULL, NULL }, "a","apple" }; |
---|
165 | struct foo_t b = { { NULL, NULL }, "b","bear" }; |
---|
166 | struct foo_t q = { { NULL, NULL }, "a", NULL }; |
---|
167 | struct foo_t *node; |
---|
168 | |
---|
169 | tree=(struct foo_t *)splay_insert((splay*)tree,(splay_cmp_t)cmp,(splay*)&a); |
---|
170 | splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post); |
---|
171 | tree=(struct foo_t *)splay_insert((splay*)tree,(splay_cmp_t)cmp,(splay*)&b); |
---|
172 | splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post); |
---|
173 | tree=(struct foo_t*)splay_search_tree((splay*)tree,(splay_cmp_t)cmp,(splay *)&q); |
---|
174 | printf("%s is for %s\n",q.key,tree->value); |
---|
175 | splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post); |
---|
176 | tree=(struct foo_t*)splay_search_tree((splay*)tree,(splay_cmp_t)cmp,(splay *)&q); |
---|
177 | printf("%s is for %s\n",q.key,tree->value); |
---|
178 | splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post); |
---|
179 | q.key="b"; |
---|
180 | tree=(struct foo_t*)splay_search_tree((splay*)tree,(splay_cmp_t)cmp,(splay *)&q); |
---|
181 | printf("%s is for %s\n",q.key,tree->value); |
---|
182 | splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post); |
---|
183 | tree=(struct foo_t*)splay_search_tree((splay*)tree,(splay_cmp_t)cmp,(splay *)&q); |
---|
184 | printf("%s is for %s\n",q.key,tree->value); |
---|
185 | splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post); |
---|
186 | |
---|
187 | return 0; |
---|
188 | } |
---|
189 | |
---|
190 | #endif |
---|