1 375b78fb 2009-08-23 rsc #include <u.h>
  2 375b78fb 2009-08-23 rsc #include <libc.h>
  3 375b78fb 2009-08-23 rsc #include <bio.h>
  4 375b78fb 2009-08-23 rsc #include <avl.h>
  5 375b78fb 2009-08-23 rsc 
  6 375b78fb 2009-08-23 rsc /*
  7 375b78fb 2009-08-23 rsc  * In-memory database stored as self-balancing AVL tree.
  8 375b78fb 2009-08-23 rsc  * See Lewis & Denenberg, Data Structures and Their Algorithms.
  9 375b78fb 2009-08-23 rsc  */
 10 375b78fb 2009-08-23 rsc 
 11 375b78fb 2009-08-23 rsc static void
 12 375b78fb 2009-08-23 rsc singleleft(Avl **tp, Avl *p)
 13 375b78fb 2009-08-23 rsc {
 14 375b78fb 2009-08-23 rsc 	int l, r2;
 15 375b78fb 2009-08-23 rsc 	Avl *a, *c;
 16 375b78fb 2009-08-23 rsc 
 17 375b78fb 2009-08-23 rsc 	a = *tp;
 18 375b78fb 2009-08-23 rsc 	c = a->n[1];
 19 375b78fb 2009-08-23 rsc 
 20 375b78fb 2009-08-23 rsc 	r2 = c->bal;
 21 375b78fb 2009-08-23 rsc 	l = (r2 > 0? r2: 0)+1 - a->bal;
 22 375b78fb 2009-08-23 rsc 
 23 375b78fb 2009-08-23 rsc 	if((a->n[1] = c->n[0]) != nil)
 24 375b78fb 2009-08-23 rsc 		a->n[1]->p = a;
 25 375b78fb 2009-08-23 rsc 
 26 375b78fb 2009-08-23 rsc 	if((c->n[0] = a) != nil)
 27 375b78fb 2009-08-23 rsc 		c->n[0]->p = c;
 28 375b78fb 2009-08-23 rsc 
 29 375b78fb 2009-08-23 rsc 	if((*tp = c) != nil)
 30 375b78fb 2009-08-23 rsc 		(*tp)->p = p;
 31 375b78fb 2009-08-23 rsc 
 32 375b78fb 2009-08-23 rsc 	a->bal = -l;
 33 375b78fb 2009-08-23 rsc 	c->bal = r2 - ((l > 0? l: 0)+1);
 34 375b78fb 2009-08-23 rsc 
 35 375b78fb 2009-08-23 rsc }
 36 375b78fb 2009-08-23 rsc 
 37 375b78fb 2009-08-23 rsc static void
 38 375b78fb 2009-08-23 rsc singleright(Avl **tp, Avl *p)
 39 375b78fb 2009-08-23 rsc {
 40 375b78fb 2009-08-23 rsc 	int l2, r;
 41 375b78fb 2009-08-23 rsc 	Avl *a, *c;
 42 375b78fb 2009-08-23 rsc 
 43 375b78fb 2009-08-23 rsc 	a = *tp;
 44 375b78fb 2009-08-23 rsc 	c = a->n[0];
 45 375b78fb 2009-08-23 rsc 	l2 = - c->bal;
 46 375b78fb 2009-08-23 rsc 	r = a->bal + ((l2 > 0? l2: 0)+1);
 47 375b78fb 2009-08-23 rsc 
 48 375b78fb 2009-08-23 rsc 	if((a->n[0] = c->n[1]) != nil)
 49 375b78fb 2009-08-23 rsc 		a->n[0]->p = a;
 50 375b78fb 2009-08-23 rsc 
 51 375b78fb 2009-08-23 rsc 	if((c->n[1] = a) != nil)
 52 375b78fb 2009-08-23 rsc 		c->n[1]->p = c;
 53 375b78fb 2009-08-23 rsc 
 54 375b78fb 2009-08-23 rsc 	if((*tp = c) != nil)
 55 375b78fb 2009-08-23 rsc 		(*tp)->p = p;
 56 375b78fb 2009-08-23 rsc 
 57 375b78fb 2009-08-23 rsc 	a->bal = r;
 58 375b78fb 2009-08-23 rsc 	c->bal = ((r > 0? r: 0)+1) - l2;
 59 375b78fb 2009-08-23 rsc }
 60 375b78fb 2009-08-23 rsc 
 61 375b78fb 2009-08-23 rsc static void
 62 375b78fb 2009-08-23 rsc doublerightleft(Avl **tp, Avl *p)
 63 375b78fb 2009-08-23 rsc {
 64 375b78fb 2009-08-23 rsc 	singleright(&(*tp)->n[1], *tp);
 65 375b78fb 2009-08-23 rsc 	singleleft(tp, p);
 66 375b78fb 2009-08-23 rsc }
 67 375b78fb 2009-08-23 rsc 
 68 375b78fb 2009-08-23 rsc static void
 69 375b78fb 2009-08-23 rsc doubleleftright(Avl **tp, Avl *p)
 70 375b78fb 2009-08-23 rsc {
 71 375b78fb 2009-08-23 rsc 	singleleft(&(*tp)->n[0], *tp);
 72 375b78fb 2009-08-23 rsc 	singleright(tp, p);
 73 375b78fb 2009-08-23 rsc }
 74 375b78fb 2009-08-23 rsc 
 75 375b78fb 2009-08-23 rsc static void
 76 375b78fb 2009-08-23 rsc balance(Avl **tp, Avl *p)
 77 375b78fb 2009-08-23 rsc {
 78 375b78fb 2009-08-23 rsc 	switch((*tp)->bal){
 79 375b78fb 2009-08-23 rsc 	case -2:
 80 375b78fb 2009-08-23 rsc 		if((*tp)->n[0]->bal <= 0)
 81 375b78fb 2009-08-23 rsc 			singleright(tp, p);
 82 375b78fb 2009-08-23 rsc 		else if((*tp)->n[0]->bal == 1)
 83 375b78fb 2009-08-23 rsc 			doubleleftright(tp, p);
 84 375b78fb 2009-08-23 rsc 		else
 85 375b78fb 2009-08-23 rsc 			assert(0);
 86 375b78fb 2009-08-23 rsc 		break;
 87 375b78fb 2009-08-23 rsc 
 88 375b78fb 2009-08-23 rsc 	case 2:
 89 375b78fb 2009-08-23 rsc 		if((*tp)->n[1]->bal >= 0)
 90 375b78fb 2009-08-23 rsc 			singleleft(tp, p);
 91 375b78fb 2009-08-23 rsc 		else if((*tp)->n[1]->bal == -1)
 92 375b78fb 2009-08-23 rsc 			doublerightleft(tp, p);
 93 375b78fb 2009-08-23 rsc 		else
 94 375b78fb 2009-08-23 rsc 			assert(0);
 95 375b78fb 2009-08-23 rsc 		break;
 96 375b78fb 2009-08-23 rsc 	}
 97 375b78fb 2009-08-23 rsc }
 98 375b78fb 2009-08-23 rsc 
 99 375b78fb 2009-08-23 rsc static int
100 f5a8ea6f 2011-06-02 rsc canoncmp(int cmp)
101 f5a8ea6f 2011-06-02 rsc {
102 f5a8ea6f 2011-06-02 rsc 	if(cmp < 0)
103 f5a8ea6f 2011-06-02 rsc 		return -1;
104 f5a8ea6f 2011-06-02 rsc 	else if(cmp > 0)
105 f5a8ea6f 2011-06-02 rsc 		return 1;
106 f5a8ea6f 2011-06-02 rsc 	return 0;
107 f5a8ea6f 2011-06-02 rsc }
108 f5a8ea6f 2011-06-02 rsc 
109 f5a8ea6f 2011-06-02 rsc static int
110 375b78fb 2009-08-23 rsc _insertavl(Avl **tp, Avl *p, Avl *r, int (*cmp)(Avl*,Avl*), Avl **rfree)
111 375b78fb 2009-08-23 rsc {
112 375b78fb 2009-08-23 rsc 	int i, ob;
113 375b78fb 2009-08-23 rsc 
114 375b78fb 2009-08-23 rsc 	if(*tp == nil){
115 375b78fb 2009-08-23 rsc 		r->bal = 0;
116 375b78fb 2009-08-23 rsc 		r->n[0] = nil;
117 375b78fb 2009-08-23 rsc 		r->n[1] = nil;
118 375b78fb 2009-08-23 rsc 		r->p = p;
119 375b78fb 2009-08-23 rsc 		*tp = r;
120 375b78fb 2009-08-23 rsc 		return 1;
121 375b78fb 2009-08-23 rsc 	}
122 375b78fb 2009-08-23 rsc 	ob = (*tp)->bal;
123 f5a8ea6f 2011-06-02 rsc 	if((i = canoncmp(cmp(r, *tp))) != 0){
124 375b78fb 2009-08-23 rsc 		(*tp)->bal += i * _insertavl(&(*tp)->n[(i+1)/2], *tp, r, cmp,
125 375b78fb 2009-08-23 rsc 			rfree);
126 375b78fb 2009-08-23 rsc 		balance(tp, p);
127 375b78fb 2009-08-23 rsc 		return ob == 0 && (*tp)->bal != 0;
128 375b78fb 2009-08-23 rsc 	}
129 375b78fb 2009-08-23 rsc 
130 375b78fb 2009-08-23 rsc 	/* install new entry */
131 375b78fb 2009-08-23 rsc 	*rfree = *tp;		/* save old node for freeing */
132 375b78fb 2009-08-23 rsc 	*tp = r;		/* insert new node */
133 375b78fb 2009-08-23 rsc 	**tp = **rfree;		/* copy old node's Avl contents */
134 375b78fb 2009-08-23 rsc 	if(r->n[0])		/* fix node's children's parent pointers */
135 375b78fb 2009-08-23 rsc 		r->n[0]->p = r;
136 375b78fb 2009-08-23 rsc 	if(r->n[1])
137 375b78fb 2009-08-23 rsc 		r->n[1]->p = r;
138 375b78fb 2009-08-23 rsc 
139 375b78fb 2009-08-23 rsc 	return 0;
140 375b78fb 2009-08-23 rsc }
141 375b78fb 2009-08-23 rsc 
142 375b78fb 2009-08-23 rsc static int
143 375b78fb 2009-08-23 rsc successor(Avl **tp, Avl *p, Avl **r)
144 375b78fb 2009-08-23 rsc {
145 375b78fb 2009-08-23 rsc 	int ob;
146 375b78fb 2009-08-23 rsc 
147 375b78fb 2009-08-23 rsc 	if((*tp)->n[0] == nil){
148 375b78fb 2009-08-23 rsc 		*r = *tp;
149 375b78fb 2009-08-23 rsc 		*tp = (*r)->n[1];
150 375b78fb 2009-08-23 rsc 		if(*tp)
151 375b78fb 2009-08-23 rsc 			(*tp)->p = p;
152 375b78fb 2009-08-23 rsc 		return -1;
153 375b78fb 2009-08-23 rsc 	}
154 375b78fb 2009-08-23 rsc 	ob = (*tp)->bal;
155 375b78fb 2009-08-23 rsc 	(*tp)->bal -= successor(&(*tp)->n[0], *tp, r);
156 375b78fb 2009-08-23 rsc 	balance(tp, p);
157 375b78fb 2009-08-23 rsc 	return -(ob != 0 && (*tp)->bal == 0);
158 375b78fb 2009-08-23 rsc }
159 375b78fb 2009-08-23 rsc 
160 375b78fb 2009-08-23 rsc static int
161 375b78fb 2009-08-23 rsc _deleteavl(Avl **tp, Avl *p, Avl *rx, int(*cmp)(Avl*,Avl*), Avl **del,
162 375b78fb 2009-08-23 rsc 	void (*predel)(Avl*, void*), void *arg)
163 375b78fb 2009-08-23 rsc {
164 375b78fb 2009-08-23 rsc 	int i, ob;
165 375b78fb 2009-08-23 rsc 	Avl *r, *or;
166 375b78fb 2009-08-23 rsc 
167 375b78fb 2009-08-23 rsc 	if(*tp == nil)
168 375b78fb 2009-08-23 rsc 		return 0;
169 375b78fb 2009-08-23 rsc 
170 375b78fb 2009-08-23 rsc 	ob = (*tp)->bal;
171 f5a8ea6f 2011-06-02 rsc 	if((i=canoncmp(cmp(rx, *tp))) != 0){
172 375b78fb 2009-08-23 rsc 		(*tp)->bal += i * _deleteavl(&(*tp)->n[(i+1)/2], *tp, rx, cmp,
173 375b78fb 2009-08-23 rsc 			del, predel, arg);
174 375b78fb 2009-08-23 rsc 		balance(tp, p);
175 375b78fb 2009-08-23 rsc 		return -(ob != 0 && (*tp)->bal == 0);
176 375b78fb 2009-08-23 rsc 	}
177 375b78fb 2009-08-23 rsc 
178 375b78fb 2009-08-23 rsc 	if(predel)
179 375b78fb 2009-08-23 rsc 		(*predel)(*tp, arg);
180 375b78fb 2009-08-23 rsc 
181 375b78fb 2009-08-23 rsc 	or = *tp;
182 375b78fb 2009-08-23 rsc 	if(or->n[i=0] == nil || or->n[i=1] == nil){
183 375b78fb 2009-08-23 rsc 		*tp = or->n[1-i];
184 375b78fb 2009-08-23 rsc 		if(*tp)
185 375b78fb 2009-08-23 rsc 			(*tp)->p = p;
186 375b78fb 2009-08-23 rsc 		*del = or;
187 375b78fb 2009-08-23 rsc 		return -1;
188 375b78fb 2009-08-23 rsc 	}
189 375b78fb 2009-08-23 rsc 
190 375b78fb 2009-08-23 rsc 	/* deleting node with two kids, find successor */
191 375b78fb 2009-08-23 rsc 	or->bal += successor(&or->n[1], or, &r);
192 375b78fb 2009-08-23 rsc 	r->bal = or->bal;
193 375b78fb 2009-08-23 rsc 	r->n[0] = or->n[0];
194 375b78fb 2009-08-23 rsc 	r->n[1] = or->n[1];
195 375b78fb 2009-08-23 rsc 	*tp = r;
196 375b78fb 2009-08-23 rsc 	(*tp)->p = p;
197 375b78fb 2009-08-23 rsc 	/* node has changed; fix children's parent pointers */
198 375b78fb 2009-08-23 rsc 	if(r->n[0])
199 375b78fb 2009-08-23 rsc 		r->n[0]->p = r;
200 375b78fb 2009-08-23 rsc 	if(r->n[1])
201 375b78fb 2009-08-23 rsc 		r->n[1]->p = r;
202 375b78fb 2009-08-23 rsc 	*del = or;
203 375b78fb 2009-08-23 rsc 	balance(tp, p);
204 375b78fb 2009-08-23 rsc 	return -(ob != 0 && (*tp)->bal == 0);
205 375b78fb 2009-08-23 rsc }
206 375b78fb 2009-08-23 rsc 
207 0c9c620f 2010-03-10 rsc /*
208 375b78fb 2009-08-23 rsc static void
209 375b78fb 2009-08-23 rsc checkparents(Avl *a, Avl *p)
210 375b78fb 2009-08-23 rsc {
211 375b78fb 2009-08-23 rsc 	if(a == nil)
212 375b78fb 2009-08-23 rsc 		return;
213 375b78fb 2009-08-23 rsc 	if(a->p != p)
214 375b78fb 2009-08-23 rsc 		print("bad parent\n");
215 375b78fb 2009-08-23 rsc 	checkparents(a->n[0], a);
216 375b78fb 2009-08-23 rsc 	checkparents(a->n[1], a);
217 375b78fb 2009-08-23 rsc }
218 0c9c620f 2010-03-10 rsc */
219 375b78fb 2009-08-23 rsc 
220 375b78fb 2009-08-23 rsc struct Avltree
221 375b78fb 2009-08-23 rsc {
222 375b78fb 2009-08-23 rsc 	Avl	*root;
223 375b78fb 2009-08-23 rsc 	int	(*cmp)(Avl*, Avl*);
224 375b78fb 2009-08-23 rsc 	Avlwalk	*walks;
225 375b78fb 2009-08-23 rsc };
226 375b78fb 2009-08-23 rsc struct Avlwalk
227 375b78fb 2009-08-23 rsc {
228 375b78fb 2009-08-23 rsc 	int	started;
229 375b78fb 2009-08-23 rsc 	int	moved;
230 375b78fb 2009-08-23 rsc 	Avlwalk	*next;
231 375b78fb 2009-08-23 rsc 	Avltree	*tree;
232 375b78fb 2009-08-23 rsc 	Avl	*node;
233 375b78fb 2009-08-23 rsc };
234 375b78fb 2009-08-23 rsc 
235 375b78fb 2009-08-23 rsc Avltree*
236 375b78fb 2009-08-23 rsc mkavltree(int (*cmp)(Avl*, Avl*))
237 375b78fb 2009-08-23 rsc {
238 375b78fb 2009-08-23 rsc 	Avltree *t;
239 375b78fb 2009-08-23 rsc 
240 375b78fb 2009-08-23 rsc 	t = malloc(sizeof *t);
241 375b78fb 2009-08-23 rsc 	if(t == nil)
242 375b78fb 2009-08-23 rsc 		return nil;
243 375b78fb 2009-08-23 rsc 	memset(t, 0, sizeof *t);
244 375b78fb 2009-08-23 rsc 	t->cmp = cmp;
245 375b78fb 2009-08-23 rsc 	return t;
246 375b78fb 2009-08-23 rsc }
247 375b78fb 2009-08-23 rsc 
248 375b78fb 2009-08-23 rsc void
249 375b78fb 2009-08-23 rsc insertavl(Avltree *t, Avl *new, Avl **oldp)
250 375b78fb 2009-08-23 rsc {
251 375b78fb 2009-08-23 rsc 	*oldp = nil;
252 375b78fb 2009-08-23 rsc 	_insertavl(&t->root, nil, new, t->cmp, oldp);
253 375b78fb 2009-08-23 rsc }
254 375b78fb 2009-08-23 rsc 
255 375b78fb 2009-08-23 rsc static Avl*
256 375b78fb 2009-08-23 rsc findpredecessor(Avl *a)
257 375b78fb 2009-08-23 rsc {
258 375b78fb 2009-08-23 rsc 	if(a == nil)
259 375b78fb 2009-08-23 rsc 		return nil;
260 375b78fb 2009-08-23 rsc 
261 375b78fb 2009-08-23 rsc 	if(a->n[0] != nil){
262 375b78fb 2009-08-23 rsc 		/* predecessor is rightmost descendant of left child */
263 375b78fb 2009-08-23 rsc 		for(a = a->n[0]; a->n[1]; a = a->n[1])
264 375b78fb 2009-08-23 rsc 			;
265 375b78fb 2009-08-23 rsc 		return a;
266 375b78fb 2009-08-23 rsc 	}else{
267 375b78fb 2009-08-23 rsc 		/* we're at a leaf, successor is a parent we enter from the right */
268 375b78fb 2009-08-23 rsc 		while(a->p && a->p->n[0] == a)
269 375b78fb 2009-08-23 rsc 			a = a->p;
270 375b78fb 2009-08-23 rsc 		return a->p;
271 375b78fb 2009-08-23 rsc 	}
272 375b78fb 2009-08-23 rsc }
273 375b78fb 2009-08-23 rsc 
274 375b78fb 2009-08-23 rsc static Avl*
275 375b78fb 2009-08-23 rsc findsuccessor(Avl *a)
276 375b78fb 2009-08-23 rsc {
277 375b78fb 2009-08-23 rsc 	if(a == nil)
278 375b78fb 2009-08-23 rsc 		return nil;
279 375b78fb 2009-08-23 rsc 
280 375b78fb 2009-08-23 rsc 	if(a->n[1] != nil){
281 375b78fb 2009-08-23 rsc 		/* successor is leftmost descendant of right child */
282 375b78fb 2009-08-23 rsc 		for(a = a->n[1]; a->n[0]; a = a->n[0])
283 375b78fb 2009-08-23 rsc 			;
284 375b78fb 2009-08-23 rsc 		return a;
285 375b78fb 2009-08-23 rsc 	}else{
286 375b78fb 2009-08-23 rsc 		/* we're at a leaf, successor is a parent we enter from the left going up */
287 375b78fb 2009-08-23 rsc 		while(a->p && a->p->n[1] == a)
288 375b78fb 2009-08-23 rsc 			a = a->p;
289 375b78fb 2009-08-23 rsc 		return a->p;
290 375b78fb 2009-08-23 rsc 	}
291 375b78fb 2009-08-23 rsc }
292 375b78fb 2009-08-23 rsc 
293 f5a8ea6f 2011-06-02 rsc static Avl*
294 f5a8ea6f 2011-06-02 rsc _lookupavl(Avl *t, Avl *r, int (*cmp)(Avl*,Avl*), int neighbor)
295 f5a8ea6f 2011-06-02 rsc {
296 f5a8ea6f 2011-06-02 rsc 	int i;
297 f5a8ea6f 2011-06-02 rsc 	Avl *p;
298 f5a8ea6f 2011-06-02 rsc 
299 f5a8ea6f 2011-06-02 rsc 	p = nil;
300 f5a8ea6f 2011-06-02 rsc 	if(t == nil)
301 f5a8ea6f 2011-06-02 rsc 		return nil;
302 f5a8ea6f 2011-06-02 rsc 	do{
303 f5a8ea6f 2011-06-02 rsc 		assert(t->p == p);
304 f5a8ea6f 2011-06-02 rsc 		if((i = canoncmp(cmp(r, t))) == 0)
305 f5a8ea6f 2011-06-02 rsc 			return t;
306 f5a8ea6f 2011-06-02 rsc 		p = t;
307 f5a8ea6f 2011-06-02 rsc 		t = t->n[(i+1)/2];
308 f5a8ea6f 2011-06-02 rsc 	}while(t);
309 f5a8ea6f 2011-06-02 rsc 	if(neighbor == 0)
310 f5a8ea6f 2011-06-02 rsc 		return nil;
311 f5a8ea6f 2011-06-02 rsc 	if(neighbor < 0)
312 f5a8ea6f 2011-06-02 rsc 		return i > 0 ? p : findpredecessor(p);
313 f5a8ea6f 2011-06-02 rsc 	return i < 0 ? p : findsuccessor(p);
314 f5a8ea6f 2011-06-02 rsc }
315 f5a8ea6f 2011-06-02 rsc 
316 f5a8ea6f 2011-06-02 rsc Avl*
317 f5a8ea6f 2011-06-02 rsc searchavl(Avltree *t, Avl *key, int neighbor)
318 f5a8ea6f 2011-06-02 rsc {
319 f5a8ea6f 2011-06-02 rsc 	return _lookupavl(t->root, key, t->cmp, neighbor);
320 f5a8ea6f 2011-06-02 rsc }
321 f5a8ea6f 2011-06-02 rsc 
322 f5a8ea6f 2011-06-02 rsc Avl*
323 f5a8ea6f 2011-06-02 rsc lookupavl(Avltree *t, Avl *key)
324 f5a8ea6f 2011-06-02 rsc {
325 f5a8ea6f 2011-06-02 rsc 	return _lookupavl(t->root, key, t->cmp, 0);
326 f5a8ea6f 2011-06-02 rsc }
327 f5a8ea6f 2011-06-02 rsc 
328 375b78fb 2009-08-23 rsc static void
329 375b78fb 2009-08-23 rsc walkdel(Avl *a, void *v)
330 375b78fb 2009-08-23 rsc {
331 375b78fb 2009-08-23 rsc 	Avl *p;
332 375b78fb 2009-08-23 rsc 	Avlwalk *w;
333 375b78fb 2009-08-23 rsc 	Avltree *t;
334 375b78fb 2009-08-23 rsc 
335 375b78fb 2009-08-23 rsc 	if(a == nil)
336 375b78fb 2009-08-23 rsc 		return;
337 375b78fb 2009-08-23 rsc 
338 375b78fb 2009-08-23 rsc 	p = findpredecessor(a);
339 375b78fb 2009-08-23 rsc 	t = v;
340 375b78fb 2009-08-23 rsc 	for(w = t->walks; w; w = w->next){
341 375b78fb 2009-08-23 rsc 		if(w->node == a){
342 375b78fb 2009-08-23 rsc 			/* back pointer to predecessor; not perfect but adequate */
343 375b78fb 2009-08-23 rsc 			w->moved = 1;
344 375b78fb 2009-08-23 rsc 			w->node = p;
345 375b78fb 2009-08-23 rsc 			if(p == nil)
346 375b78fb 2009-08-23 rsc 				w->started = 0;
347 375b78fb 2009-08-23 rsc 		}
348 375b78fb 2009-08-23 rsc 	}
349 375b78fb 2009-08-23 rsc }
350 375b78fb 2009-08-23 rsc 
351 375b78fb 2009-08-23 rsc void
352 375b78fb 2009-08-23 rsc deleteavl(Avltree *t, Avl *key, Avl **oldp)
353 375b78fb 2009-08-23 rsc {
354 375b78fb 2009-08-23 rsc 	*oldp = nil;
355 375b78fb 2009-08-23 rsc 	_deleteavl(&t->root, nil, key, t->cmp, oldp, walkdel, t);
356 375b78fb 2009-08-23 rsc }
357 375b78fb 2009-08-23 rsc 
358 375b78fb 2009-08-23 rsc Avlwalk*
359 375b78fb 2009-08-23 rsc avlwalk(Avltree *t)
360 375b78fb 2009-08-23 rsc {
361 375b78fb 2009-08-23 rsc 	Avlwalk *w;
362 375b78fb 2009-08-23 rsc 
363 375b78fb 2009-08-23 rsc 	w = malloc(sizeof *w);
364 375b78fb 2009-08-23 rsc 	if(w == nil)
365 375b78fb 2009-08-23 rsc 		return nil;
366 375b78fb 2009-08-23 rsc 	memset(w, 0, sizeof *w);
367 375b78fb 2009-08-23 rsc 	w->tree = t;
368 375b78fb 2009-08-23 rsc 	w->next = t->walks;
369 375b78fb 2009-08-23 rsc 	t->walks = w;
370 375b78fb 2009-08-23 rsc 	return w;
371 375b78fb 2009-08-23 rsc }
372 375b78fb 2009-08-23 rsc 
373 375b78fb 2009-08-23 rsc Avl*
374 375b78fb 2009-08-23 rsc avlnext(Avlwalk *w)
375 375b78fb 2009-08-23 rsc {
376 375b78fb 2009-08-23 rsc 	Avl *a;
377 375b78fb 2009-08-23 rsc 
378 375b78fb 2009-08-23 rsc 	if(w->started==0){
379 375b78fb 2009-08-23 rsc 		for(a = w->tree->root; a && a->n[0]; a = a->n[0])
380 375b78fb 2009-08-23 rsc 			;
381 375b78fb 2009-08-23 rsc 		w->node = a;
382 375b78fb 2009-08-23 rsc 		w->started = 1;
383 375b78fb 2009-08-23 rsc 	}else{
384 375b78fb 2009-08-23 rsc 		a = findsuccessor(w->node);
385 375b78fb 2009-08-23 rsc 		if(a == w->node)
386 375b78fb 2009-08-23 rsc 			abort();
387 375b78fb 2009-08-23 rsc 		w->node = a;
388 375b78fb 2009-08-23 rsc 	}
389 375b78fb 2009-08-23 rsc 	return w->node;
390 375b78fb 2009-08-23 rsc }
391 375b78fb 2009-08-23 rsc 
392 375b78fb 2009-08-23 rsc Avl*
393 375b78fb 2009-08-23 rsc avlprev(Avlwalk *w)
394 375b78fb 2009-08-23 rsc {
395 375b78fb 2009-08-23 rsc 	Avl *a;
396 375b78fb 2009-08-23 rsc 
397 375b78fb 2009-08-23 rsc 	if(w->started == 0){
398 375b78fb 2009-08-23 rsc 		for(a = w->tree->root; a && a->n[1]; a = a->n[1])
399 375b78fb 2009-08-23 rsc 			;
400 375b78fb 2009-08-23 rsc 		w->node = a;
401 375b78fb 2009-08-23 rsc 		w->started = 1;
402 375b78fb 2009-08-23 rsc 	}else if(w->moved){
403 375b78fb 2009-08-23 rsc 		w->moved = 0;
404 375b78fb 2009-08-23 rsc 		return w->node;
405 375b78fb 2009-08-23 rsc 	}else{
406 375b78fb 2009-08-23 rsc 		a = findpredecessor(w->node);
407 375b78fb 2009-08-23 rsc 		if(a == w->node)
408 375b78fb 2009-08-23 rsc 			abort();
409 375b78fb 2009-08-23 rsc 		w->node = a;
410 375b78fb 2009-08-23 rsc 	}
411 375b78fb 2009-08-23 rsc 	return w->node;
412 375b78fb 2009-08-23 rsc }
413 375b78fb 2009-08-23 rsc 
414 375b78fb 2009-08-23 rsc void
415 375b78fb 2009-08-23 rsc endwalk(Avlwalk *w)
416 375b78fb 2009-08-23 rsc {
417 375b78fb 2009-08-23 rsc 	Avltree *t;
418 375b78fb 2009-08-23 rsc 	Avlwalk **l;
419 375b78fb 2009-08-23 rsc 
420 375b78fb 2009-08-23 rsc 	t = w->tree;
421 375b78fb 2009-08-23 rsc 	for(l = &t->walks; *l; l = &(*l)->next){
422 375b78fb 2009-08-23 rsc 		if(*l == w){
423 375b78fb 2009-08-23 rsc 			*l = w->next;
424 375b78fb 2009-08-23 rsc 			break;
425 375b78fb 2009-08-23 rsc 		}
426 375b78fb 2009-08-23 rsc 	}
427 375b78fb 2009-08-23 rsc 	free(w);
428 375b78fb 2009-08-23 rsc }
429 375b78fb 2009-08-23 rsc 
430 0c9c620f 2010-03-10 rsc /*
431 375b78fb 2009-08-23 rsc static void
432 375b78fb 2009-08-23 rsc walkavl(Avl *t, void (*f)(Avl*, void*), void *v)
433 375b78fb 2009-08-23 rsc {
434 375b78fb 2009-08-23 rsc 	if(t == nil)
435 375b78fb 2009-08-23 rsc 		return;
436 375b78fb 2009-08-23 rsc 	walkavl(t->n[0], f, v);
437 375b78fb 2009-08-23 rsc 	f(t, v);
438 375b78fb 2009-08-23 rsc 	walkavl(t->n[1], f, v);
439 375b78fb 2009-08-23 rsc }
440 0c9c620f 2010-03-10 rsc */