Werner's Miscellanea
Sign in or create your account | Project List | Help
Werner's Miscellanea Commit Details
Date: | 2010-11-20 00:18:59 (13 years 4 months ago) |
---|---|
Author: | Werner Almesberger |
Commit: | 009f56c927dba844c30a628a670ac92a2ff04f19 |
Message: | qpkg/jrb.c: major whitespace readjustment (converted from GNU to
K&R style) |
Files: |
qpkg/jrb.c (1 diff) |
Change Details
qpkg/jrb.c | ||
---|---|---|
51 | 51 | static void recolor(JRB n); |
52 | 52 | static void single_rotate(JRB y, int l); |
53 | 53 | |
54 | #define isred(n) (n->red) | |
55 | #define isblack(n) (!isred(n)) | |
56 | #define isleft(n) (n->left) | |
57 | #define isright(n) (!isleft(n)) | |
58 | #define isint(n) (n->internal) | |
59 | #define isext(n) (!isint(n)) | |
60 | #define ishead(n) (n->roothead & 2) | |
61 | #define isroot(n) (n->roothead & 1) | |
62 | #define getlext(n) ((struct jrb_node *)(n->key)) | |
54 | #define isred(n) (n->red) | |
55 | #define isblack(n) (!isred(n)) | |
56 | #define isleft(n) (n->left) | |
57 | #define isright(n) (!isleft(n)) | |
58 | #define isint(n) (n->internal) | |
59 | #define isext(n) (!isint(n)) | |
60 | #define ishead(n) (n->roothead & 2) | |
61 | #define isroot(n) (n->roothead & 1) | |
62 | #define getlext(n) ((struct jrb_node *) (n->key)) | |
63 | 63 | #define setlext(node, val) node->key = (void *) (val) |
64 | #define getrext(n) ((struct jrb_node *)(n->val)) | |
64 | #define getrext(n) ((struct jrb_node *) (n->val)) | |
65 | 65 | #define setrext(node, value) node->val = (void *) (value) |
66 | #define setred(n) n->red = 1 | |
67 | #define setblack(n) n->red = 0 | |
68 | #define setleft(n) n->left = 1 | |
69 | #define setright(n) n->left = 0 | |
70 | #define sethead(n) (n->roothead |= 2) | |
71 | #define setroot(n) (n->roothead |= 1) | |
72 | #define setint(n) n->internal = 1 | |
73 | #define setext(n) n->internal = 0 | |
74 | #define setnormal(n) n->roothead = 0 | |
75 | #define sibling(n) ((isleft(n)) ? n->parent->blink : n->parent->flink) | |
66 | #define setred(n) n->red = 1 | |
67 | #define setblack(n) n->red = 0 | |
68 | #define setleft(n) n->left = 1 | |
69 | #define setright(n) n->left = 0 | |
70 | #define sethead(n) (n->roothead |= 2) | |
71 | #define setroot(n) (n->roothead |= 1) | |
72 | #define setint(n) n->internal = 1 | |
73 | #define setext(n) n->internal = 0 | |
74 | #define setnormal(n) n->roothead = 0 | |
75 | #define sibling(n) (isleft(n) ? n->parent->blink : n->parent->flink) | |
76 | 76 | |
77 | ||
77 | 78 | static void insert(JRB item, JRB list) /* Inserts to the end of a list */ |
78 | 79 | { |
79 | JRB last_node; | |
80 | JRB last_node; | |
80 | 81 | |
81 | last_node = list->blink; | |
82 | last_node = list->blink; | |
82 | 83 | |
83 | list->blink = item; | |
84 | last_node->flink = item; | |
85 | item->blink = last_node; | |
86 | item->flink = list; | |
84 | list->blink = item; | |
85 | last_node->flink = item; | |
86 | item->blink = last_node; | |
87 | item->flink = list; | |
87 | 88 | } |
89 | ||
88 | 90 | |
89 | 91 | static void delete_item(JRB item) /* Deletes an arbitrary iterm */ |
90 | 92 | { |
91 | item->flink->blink = item->blink; | |
92 | item->blink->flink = item->flink; | |
93 | item->flink->blink = item->blink; | |
94 | item->blink->flink = item->flink; | |
93 | 95 | } |
94 | 96 | |
95 | #define mk_new_ext(new, kkkey, vvval) {\ | |
96 | new = (JRB) malloc(sizeof(struct jrb_node));\ | |
97 | new->val = vvval;\ | |
98 | new->key = kkkey;\ | |
99 | setext(new);\ | |
100 | setblack(new);\ | |
101 | setnormal(new);\ | |
97 | #define mk_new_ext(new, kkkey, vvval) { \ | |
98 | new = (JRB) malloc(sizeof(struct jrb_node)); \ | |
99 | new->val = vvval; \ | |
100 | new->key = kkkey; \ | |
101 | setext(new); \ | |
102 | setblack(new); \ | |
103 | setnormal(new); \ | |
102 | 104 | } |
103 | 105 | |
104 | 106 | static void mk_new_int(JRB l, JRB r, JRB p, int il) |
105 | 107 | { |
106 | JRB newnode; | |
107 | ||
108 | newnode = (JRB) malloc(sizeof(struct jrb_node)); | |
109 | setint(newnode); | |
110 | setred(newnode); | |
111 | setnormal(newnode); | |
112 | newnode->flink = l; | |
113 | newnode->blink = r; | |
114 | newnode->parent = p; | |
115 | setlext(newnode, l); | |
116 | setrext(newnode, r); | |
117 | l->parent = newnode; | |
118 | r->parent = newnode; | |
119 | setleft(l); | |
120 | setright(r); | |
121 | if (ishead(p)) { | |
122 | p->parent = newnode; | |
123 | setroot(newnode); | |
124 | } else if (il) { | |
125 | setleft(newnode); | |
126 | p->flink = newnode; | |
127 | } else { | |
128 | setright(newnode); | |
129 | p->blink = newnode; | |
130 | } | |
131 | recolor(newnode); | |
108 | JRB newnode; | |
109 | ||
110 | newnode = (JRB) malloc(sizeof(struct jrb_node)); | |
111 | setint(newnode); | |
112 | setred(newnode); | |
113 | setnormal(newnode); | |
114 | newnode->flink = l; | |
115 | newnode->blink = r; | |
116 | newnode->parent = p; | |
117 | setlext(newnode, l); | |
118 | setrext(newnode, r); | |
119 | l->parent = newnode; | |
120 | r->parent = newnode; | |
121 | setleft(l); | |
122 | setright(r); | |
123 | if (ishead(p)) { | |
124 | p->parent = newnode; | |
125 | setroot(newnode); | |
126 | } else if (il) { | |
127 | setleft(newnode); | |
128 | p->flink = newnode; | |
129 | } else { | |
130 | setright(newnode); | |
131 | p->blink = newnode; | |
132 | } | |
133 | recolor(newnode); | |
132 | 134 | } |
133 | 135 | |
134 | 136 | |
135 | 137 | JRB lprev(JRB n) |
136 | 138 | { |
137 | if (ishead(n)) return n; | |
138 | while (!isroot(n)) { | |
139 | if (isright(n)) return n->parent; | |
140 | n = n->parent; | |
141 | } | |
142 | return n->parent; | |
139 | if (ishead(n)) | |
140 | return n; | |
141 | while (!isroot(n)) { | |
142 | if (isright(n)) | |
143 | return n->parent; | |
144 | n = n->parent; | |
145 | } | |
146 | return n->parent; | |
143 | 147 | } |
148 | ||
144 | 149 | |
145 | 150 | JRB rprev(JRB n) |
146 | 151 | { |
147 | if (ishead(n)) return n; | |
148 | while (!isroot(n)) { | |
149 | if (isleft(n)) return n->parent; | |
150 | n = n->parent; | |
151 | } | |
152 | return n->parent; | |
152 | if (ishead(n)) | |
153 | return n; | |
154 | while (!isroot(n)) { | |
155 | if (isleft(n)) | |
156 | return n->parent; | |
157 | n = n->parent; | |
158 | } | |
159 | return n->parent; | |
153 | 160 | } |
154 | 161 | |
162 | ||
155 | 163 | JRB make_jrb(void) |
156 | 164 | { |
157 | JRB head; | |
158 | ||
159 | head = (JRB) malloc (sizeof(struct jrb_node)); | |
160 | head->flink = head; | |
161 | head->blink = head; | |
162 | head->parent = head; | |
163 | head->key = NULL; | |
164 | sethead(head); | |
165 | return head; | |
165 | JRB head; | |
166 | ||
167 | head = (JRB) malloc(sizeof(struct jrb_node)); | |
168 | head->flink = head; | |
169 | head->blink = head; | |
170 | head->parent = head; | |
171 | head->key = NULL; | |
172 | sethead(head); | |
173 | return head; | |
166 | 174 | } |
167 | 175 | |
176 | ||
168 | 177 | JRB jrb_find_gte(JRB n, const void *key, |
169 | 178 | int (*fxn)(const void *, const void *), int *fnd) |
170 | 179 | { |
171 | int cmp; | |
172 | ||
173 | *fnd = 0; | |
174 | if (!ishead(n)) { | |
175 | fprintf(stderr, "jrb_find_gte_str called on non-head %p\n", n); | |
176 | exit(1); | |
177 | } | |
178 | if (n->parent == n) return n; | |
179 | cmp = (*fxn)(key, n->blink->key); | |
180 | if (cmp == 0) { | |
181 | *fnd = 1; | |
182 | return n->blink; | |
183 | } | |
184 | if (cmp > 0) return n; | |
185 | else n = n->parent; | |
186 | while (1) { | |
187 | if (isext(n)) return n; | |
188 | cmp = (*fxn)(key, getlext(n)->key); | |
189 | if (cmp == 0) { | |
190 | *fnd = 1; | |
191 | return getlext(n); | |
192 | } | |
193 | if (cmp < 0) n = n->flink ; else n = n->blink; | |
194 | } | |
180 | int cmp; | |
181 | ||
182 | *fnd = 0; | |
183 | if (!ishead(n)) { | |
184 | fprintf(stderr, "jrb_find_gte_str called on non-head %p\n", n); | |
185 | exit(1); | |
186 | } | |
187 | if (n->parent == n) | |
188 | return n; | |
189 | cmp = (*fxn)(key, n->blink->key); | |
190 | if (cmp == 0) { | |
191 | *fnd = 1; | |
192 | return n->blink; | |
193 | } | |
194 | if (cmp > 0) | |
195 | return n; | |
196 | else | |
197 | n = n->parent; | |
198 | while (1) { | |
199 | if (isext(n)) | |
200 | return n; | |
201 | cmp = (*fxn)(key, getlext(n)->key); | |
202 | if (cmp == 0) { | |
203 | *fnd = 1; | |
204 | return getlext(n); | |
205 | } | |
206 | if (cmp < 0) | |
207 | n = n->flink; | |
208 | else | |
209 | n = n->blink; | |
210 | } | |
195 | 211 | } |
212 | ||
196 | 213 | |
197 | 214 | JRB jrb_find(JRB n, const void *key, int (*fxn)(const void *, const void *)) |
198 | 215 | { |
199 | int fnd; | |
200 | JRB j; | |
216 | int fnd; | |
217 | JRB j; | |
201 | 218 | |
202 | j = jrb_find_gte(n, key, fxn, &fnd); | |
203 | if (fnd) return j; else return NULL; | |
219 | j = jrb_find_gte(n, key, fxn, &fnd); | |
220 | if (fnd) | |
221 | return j; | |
222 | else | |
223 | return NULL; | |
204 | 224 | } |
225 | ||
205 | 226 | |
206 | 227 | static JRB jrb_insert_b(JRB n, void *key, void *val) |
207 | 228 | { |
208 | JRB newleft, newright, newnode, p; | |
209 | ||
210 | if (ishead(n)) { | |
211 | if (n->parent == n) { /* Tree is empty */ | |
212 | mk_new_ext(newnode, key, val); | |
213 | insert(newnode, n); | |
214 | n->parent = newnode; | |
215 | newnode->parent = n; | |
216 | setroot(newnode); | |
217 | return newnode; | |
218 | } else { | |
219 | mk_new_ext(newright, key, val); | |
220 | insert(newright, n); | |
221 | newleft = newright->blink; | |
222 | setnormal(newleft); | |
223 | mk_new_int(newleft, newright, newleft->parent, isleft(newleft)); | |
224 | p = rprev(newright); | |
225 | if (!ishead(p)) setlext(p, newright); | |
226 | return newright; | |
227 | } | |
228 | } else { | |
229 | mk_new_ext(newleft, key, val); | |
230 | insert(newleft, n); | |
231 | setnormal(n); | |
232 | mk_new_int(newleft, n, n->parent, isleft(n)); | |
233 | p = lprev(newleft); | |
234 | if (!ishead(p)) setrext(p, newleft); | |
235 | return newleft; | |
236 | } | |
229 | JRB newleft, newright, newnode, p; | |
230 | ||
231 | if (ishead(n)) { | |
232 | if (n->parent == n) { /* Tree is empty */ | |
233 | mk_new_ext(newnode, key, val); | |
234 | insert(newnode, n); | |
235 | n->parent = newnode; | |
236 | newnode->parent = n; | |
237 | setroot(newnode); | |
238 | return newnode; | |
239 | } else { | |
240 | mk_new_ext(newright, key, val); | |
241 | insert(newright, n); | |
242 | newleft = newright->blink; | |
243 | setnormal(newleft); | |
244 | mk_new_int(newleft, newright, newleft->parent, | |
245 | isleft(newleft)); | |
246 | p = rprev(newright); | |
247 | if (!ishead(p)) | |
248 | setlext(p, newright); | |
249 | return newright; | |
250 | } | |
251 | } else { | |
252 | mk_new_ext(newleft, key, val); | |
253 | insert(newleft, n); | |
254 | setnormal(n); | |
255 | mk_new_int(newleft, n, n->parent, isleft(n)); | |
256 | p = lprev(newleft); | |
257 | if (!ishead(p)) | |
258 | setrext(p, newleft); | |
259 | return newleft; | |
260 | } | |
237 | 261 | } |
262 | ||
238 | 263 | |
239 | 264 | static void recolor(JRB n) |
240 | 265 | { |
241 | JRB p, gp, s; | |
242 | int done = 0; | |
266 | JRB p, gp, s; | |
267 | int done = 0; | |
243 | 268 | |
244 | while(!done) { | |
245 | if (isroot(n)) { | |
246 | setblack(n); | |
247 | return; | |
248 | } | |
269 | while(!done) { | |
270 | if (isroot(n)) { | |
271 | setblack(n); | |
272 | return; | |
273 | } | |
249 | 274 | |
250 | p = n->parent; | |
275 | p = n->parent; | |
251 | 276 | |
252 | if (isblack(p)) return; | |
277 | if (isblack(p)) | |
278 | return; | |
253 | 279 | |
254 | if (isroot(p)) { | |
255 | setblack(p); | |
256 | return; | |
257 | } | |
258 | ||
259 | gp = p->parent; | |
260 | s = sibling(p); | |
261 | if (isred(s)) { | |
262 | setblack(p); | |
263 | setred(gp); | |
264 | setblack(s); | |
265 | n = gp; | |
266 | } else { | |
267 | done = 1; | |
268 | } | |
269 | } | |
270 | /* p's sibling is black, p is red, gp is black */ | |
280 | if (isroot(p)) { | |
281 | setblack(p); | |
282 | return; | |
283 | } | |
284 | ||
285 | gp = p->parent; | |
286 | s = sibling(p); | |
287 | if (isred(s)) { | |
288 | setblack(p); | |
289 | setred(gp); | |
290 | setblack(s); | |
291 | n = gp; | |
292 | } else { | |
293 | done = 1; | |
294 | } | |
295 | } | |
296 | /* p's sibling is black, p is red, gp is black */ | |
271 | 297 | |
272 | if ((isleft(n) == 0) == (isleft(p) == 0)) { | |
273 | single_rotate(gp, isleft(n)); | |
274 | setblack(p); | |
275 | setred(gp); | |
276 | } else { | |
277 | single_rotate(p, isleft(n)); | |
278 | single_rotate(gp, isleft(n)); | |
279 | setblack(n); | |
280 | setred(gp); | |
281 | } | |
298 | if ((isleft(n) == 0) == (isleft(p) == 0)) { | |
299 | single_rotate(gp, isleft(n)); | |
300 | setblack(p); | |
301 | setred(gp); | |
302 | } else { | |
303 | single_rotate(p, isleft(n)); | |
304 | single_rotate(gp, isleft(n)); | |
305 | setblack(n); | |
306 | setred(gp); | |
307 | } | |
282 | 308 | } |
309 | ||
283 | 310 | |
284 | 311 | static void single_rotate(JRB y, int l) |
285 | 312 | { |
286 | int rl = 0 /* for gcc */, ir; | |
287 | JRB x, yp; | |
288 | ||
289 | ir = isroot(y); | |
290 | yp = y->parent; | |
291 | if (!ir) { | |
292 | rl = isleft(y); | |
293 | } | |
313 | int rl = 0 /* for gcc */, ir; | |
314 | JRB x, yp; | |
315 | ||
316 | ir = isroot(y); | |
317 | yp = y->parent; | |
318 | if (!ir) | |
319 | rl = isleft(y); | |
294 | 320 | |
295 | if (l) { | |
296 | x = y->flink; | |
297 | y->flink = x->blink; | |
298 | setleft(y->flink); | |
299 | y->flink->parent = y; | |
300 | x->blink = y; | |
301 | setright(y); | |
302 | } else { | |
303 | x = y->blink; | |
304 | y->blink = x->flink; | |
305 | setright(y->blink); | |
306 | y->blink->parent = y; | |
307 | x->flink = y; | |
308 | setleft(y); | |
309 | } | |
310 | ||
311 | x->parent = yp; | |
312 | y->parent = x; | |
313 | if (ir) { | |
314 | yp->parent = x; | |
315 | setnormal(y); | |
316 | setroot(x); | |
317 | } else { | |
318 | if (rl) { | |
319 | yp->flink = x; | |
320 | setleft(x); | |
321 | } else { | |
322 | yp->blink = x; | |
323 | setright(x); | |
324 | } | |
325 | } | |
321 | if (l) { | |
322 | x = y->flink; | |
323 | y->flink = x->blink; | |
324 | setleft(y->flink); | |
325 | y->flink->parent = y; | |
326 | x->blink = y; | |
327 | setright(y); | |
328 | } else { | |
329 | x = y->blink; | |
330 | y->blink = x->flink; | |
331 | setright(y->blink); | |
332 | y->blink->parent = y; | |
333 | x->flink = y; | |
334 | setleft(y); | |
335 | } | |
336 | ||
337 | x->parent = yp; | |
338 | y->parent = x; | |
339 | if (ir) { | |
340 | yp->parent = x; | |
341 | setnormal(y); | |
342 | setroot(x); | |
343 | } else { | |
344 | if (rl) { | |
345 | yp->flink = x; | |
346 | setleft(x); | |
347 | } else { | |
348 | yp->blink = x; | |
349 | setright(x); | |
350 | } | |
351 | } | |
326 | 352 | } |
327 | ||
353 | ||
354 | ||
328 | 355 | void jrb_delete_node(JRB n) |
329 | 356 | { |
330 | JRB s, p, gp; | |
331 | char ir; | |
332 | ||
333 | if (isint(n)) { | |
334 | fprintf(stderr, "Cannot delete an internal node: %p\n", n); | |
335 | exit(1); | |
336 | } | |
337 | if (ishead(n)) { | |
338 | fprintf(stderr, "Cannot delete the head of an jrb_tree: %p\n", n); | |
339 | exit(1); | |
340 | } | |
341 | delete_item(n); /* Delete it from the list */ | |
342 | p = n->parent; /* The only node */ | |
343 | if (isroot(n)) { | |
344 | p->parent = p; | |
345 | free(n); | |
346 | return; | |
347 | } | |
348 | s = sibling(n); /* The only node after deletion */ | |
349 | if (isroot(p)) { | |
350 | s->parent = p->parent; | |
351 | s->parent->parent = s; | |
352 | setroot(s); | |
353 | free(p); | |
354 | free(n); | |
355 | return; | |
356 | } | |
357 | gp = p->parent; /* Set parent to sibling */ | |
358 | s->parent = gp; | |
359 | if (isleft(p)) { | |
360 | gp->flink = s; | |
361 | setleft(s); | |
362 | } else { | |
363 | gp->blink = s; | |
364 | setright(s); | |
365 | } | |
366 | ir = isred(p); | |
367 | free(p); | |
368 | free(n); | |
357 | JRB s, p, gp; | |
358 | char ir; | |
359 | ||
360 | if (isint(n)) { | |
361 | fprintf(stderr, "Cannot delete an internal node: %p\n", n); | |
362 | exit(1); | |
363 | } | |
364 | if (ishead(n)) { | |
365 | fprintf(stderr, | |
366 | "Cannot delete the head of an jrb_tree: %p\n", n); | |
367 | exit(1); | |
368 | } | |
369 | delete_item(n); /* Delete it from the list */ | |
370 | p = n->parent; /* The only node */ | |
371 | if (isroot(n)) { | |
372 | p->parent = p; | |
373 | free(n); | |
374 | return; | |
375 | } | |
376 | s = sibling(n); /* The only node after deletion */ | |
377 | if (isroot(p)) { | |
378 | s->parent = p->parent; | |
379 | s->parent->parent = s; | |
380 | setroot(s); | |
381 | free(p); | |
382 | free(n); | |
383 | return; | |
384 | } | |
385 | gp = p->parent; /* Set parent to sibling */ | |
386 | s->parent = gp; | |
387 | if (isleft(p)) { | |
388 | gp->flink = s; | |
389 | setleft(s); | |
390 | } else { | |
391 | gp->blink = s; | |
392 | setright(s); | |
393 | } | |
394 | ir = isred(p); | |
395 | free(p); | |
396 | free(n); | |
369 | 397 | |
370 | if (isext(s)) { /* Update proper rext and lext values */ | |
371 | p = lprev(s); | |
372 | if (!ishead(p)) setrext(p, s); | |
373 | p = rprev(s); | |
374 | if (!ishead(p)) setlext(p, s); | |
375 | } else if (isblack(s)) { | |
376 | fprintf(stderr, "DELETION PROB -- sib is black, internal\n"); | |
377 | exit(1); | |
378 | } else { | |
379 | p = lprev(s); | |
380 | if (!ishead(p)) setrext(p, s->flink); | |
381 | p = rprev(s); | |
382 | if (!ishead(p)) setlext(p, s->blink); | |
383 | setblack(s); | |
384 | return; | |
385 | } | |
386 | ||
387 | if (ir) return; | |
388 | ||
389 | /* Recolor */ | |
398 | if (isext(s)) { /* Update proper rext and lext values */ | |
399 | p = lprev(s); | |
400 | if (!ishead(p)) | |
401 | setrext(p, s); | |
402 | p = rprev(s); | |
403 | if (!ishead(p)) | |
404 | setlext(p, s); | |
405 | } else if (isblack(s)) { | |
406 | fprintf(stderr, "DELETION PROB -- sib is black, internal\n"); | |
407 | exit(1); | |
408 | } else { | |
409 | p = lprev(s); | |
410 | if (!ishead(p)) | |
411 | setrext(p, s->flink); | |
412 | p = rprev(s); | |
413 | if (!ishead(p)) | |
414 | setlext(p, s->blink); | |
415 | setblack(s); | |
416 | return; | |
417 | } | |
418 | ||
419 | if (ir) | |
420 | return; | |
421 | ||
422 | /* Recolor */ | |
390 | 423 | |
391 | n = s; | |
392 | p = n->parent; | |
393 | s = sibling(n); | |
394 | while(isblack(p) && isblack(s) && isint(s) && | |
395 | isblack(s->flink) && isblack(s->blink)) { | |
396 | setred(s); | |
397 | n = p; | |
398 | if (isroot(n)) return; | |
399 | p = n->parent; | |
400 | s = sibling(n); | |
401 | } | |
424 | n = s; | |
425 | p = n->parent; | |
426 | s = sibling(n); | |
427 | while(isblack(p) && isblack(s) && isint(s) && | |
428 | isblack(s->flink) && isblack(s->blink)) { | |
429 | setred(s); | |
430 | n = p; | |
431 | if (isroot(n)) | |
432 | return; | |
433 | p = n->parent; | |
434 | s = sibling(n); | |
435 | } | |
402 | 436 | |
403 | if (isblack(p) && isred(s)) { /* Rotation 2.3b */ | |
404 | single_rotate(p, isright(n)); | |
405 | setred(p); | |
406 | setblack(s); | |
407 | s = sibling(n); | |
408 | } | |
437 | if (isblack(p) && isred(s)) { /* Rotation 2.3b */ | |
438 | single_rotate(p, isright(n)); | |
439 | setred(p); | |
440 | setblack(s); | |
441 | s = sibling(n); | |
442 | } | |
409 | 443 | |
410 | { JRB x, z; char il; | |
444 | { | |
445 | JRB x, z; char il; | |
411 | 446 | |
412 | if (isext(s)) { | |
413 | fprintf(stderr, "DELETION ERROR: sibling not internal\n"); | |
414 | exit(1); | |
415 | } | |
416 | ||
417 | il = isleft(n); | |
418 | x = il ? s->flink : s->blink ; | |
419 | z = sibling(x); | |
420 | ||
421 | if (isred(z)) { /* Rotation 2.3f */ | |
422 | single_rotate(p, !il); | |
423 | setblack(z); | |
424 | if (isred(p)) setred(s); else setblack(s); | |
425 | setblack(p); | |
426 | } else if (isblack(x)) { /* Recoloring only (2.3c) */ | |
427 | if (isred(s) || isblack(p)) { | |
428 | fprintf(stderr, "DELETION ERROR: 2.3c not quite right\n"); | |
429 | exit(1); | |
430 | } | |
431 | setblack(p); | |
432 | setred(s); | |
433 | return; | |
434 | } else if (isred(p)) { /* 2.3d */ | |
435 | single_rotate(s, il); | |
436 | single_rotate(p, !il); | |
437 | setblack(x); | |
438 | setred(s); | |
439 | return; | |
440 | } else { /* 2.3e */ | |
441 | single_rotate(s, il); | |
442 | single_rotate(p, !il); | |
443 | setblack(x); | |
444 | return; | |
445 | } | |
446 | } | |
447 | if (isext(s)) { | |
448 | fprintf(stderr, | |
449 | "DELETION ERROR: sibling not internal\n"); | |
450 | exit(1); | |
451 | } | |
452 | ||
453 | il = isleft(n); | |
454 | x = il ? s->flink : s->blink; | |
455 | z = sibling(x); | |
456 | ||
457 | if (isred(z)) { /* Rotation 2.3f */ | |
458 | single_rotate(p, !il); | |
459 | setblack(z); | |
460 | if (isred(p)) | |
461 | setred(s); | |
462 | else | |
463 | setblack(s); | |
464 | setblack(p); | |
465 | } else if (isblack(x)) { /* Recoloring only (2.3c) */ | |
466 | if (isred(s) || isblack(p)) { | |
467 | fprintf(stderr, | |
468 | "DELETION ERROR: 2.3c not quite right\n"); | |
469 | exit(1); | |
470 | } | |
471 | setblack(p); | |
472 | setred(s); | |
473 | return; | |
474 | } else if (isred(p)) { /* 2.3d */ | |
475 | single_rotate(s, il); | |
476 | single_rotate(p, !il); | |
477 | setblack(x); | |
478 | setred(s); | |
479 | return; | |
480 | } else { /* 2.3e */ | |
481 | single_rotate(s, il); | |
482 | single_rotate(p, !il); | |
483 | setblack(x); | |
484 | return; | |
485 | } | |
486 | } | |
447 | 487 | } |
488 | ||
448 | 489 | |
449 | 490 | int jrb_nblack(JRB n) |
450 | 491 | { |
451 | int nb; | |
452 | if (ishead(n) || isint(n)) { | |
453 | fprintf(stderr, "ERROR: jrb_nblack called on a non-external node %p\n", n); | |
454 | exit(1); | |
455 | } | |
456 | nb = 0; | |
457 | while(!ishead(n)) { | |
458 | if (isblack(n)) nb++; | |
459 | n = n->parent; | |
460 | } | |
461 | return nb; | |
492 | int nb; | |
493 | ||
494 | if (ishead(n) || isint(n)) { | |
495 | fprintf(stderr, | |
496 | "ERROR: jrb_nblack called on a non-external node %p\n", n); | |
497 | exit(1); | |
498 | } | |
499 | nb = 0; | |
500 | while(!ishead(n)) { | |
501 | if (isblack(n)) nb++; | |
502 | n = n->parent; | |
503 | } | |
504 | return nb; | |
462 | 505 | } |
506 | ||
463 | 507 | |
464 | 508 | int jrb_plength(JRB n) |
465 | 509 | { |
466 | int pl; | |
467 | if (ishead(n) || isint(n)) { | |
468 | fprintf(stderr, "ERROR: jrb_plength called on a non-external node %p\n", n); | |
469 | exit(1); | |
470 | } | |
471 | pl = 0; | |
472 | while(!ishead(n)) { | |
473 | pl++; | |
474 | n = n->parent; | |
475 | } | |
476 | return pl; | |
510 | int pl; | |
511 | ||
512 | if (ishead(n) || isint(n)) { | |
513 | fprintf(stderr, | |
514 | "ERROR: jrb_plength called on a non-external node %p\n", n); | |
515 | exit(1); | |
516 | } | |
517 | pl = 0; | |
518 | while (!ishead(n)) { | |
519 | pl++; | |
520 | n = n->parent; | |
521 | } | |
522 | return pl; | |
477 | 523 | } |
524 | ||
478 | 525 | |
479 | 526 | void jrb_free_tree(JRB n) |
480 | 527 | { |
481 | if (!ishead(n)) { | |
482 | fprintf(stderr, "ERROR: Rb_free_tree called on a non-head node\n"); | |
483 | exit(1); | |
484 | } | |
485 | ||
486 | while(jrb_first(n) != jrb_nil(n)) { | |
487 | jrb_delete_node(jrb_first(n)); | |
488 | } | |
489 | free(n); | |
528 | if (!ishead(n)) { | |
529 | fprintf(stderr, | |
530 | "ERROR: Rb_free_tree called on a non-head node\n"); | |
531 | exit(1); | |
532 | } | |
533 | ||
534 | while(jrb_first(n) != jrb_nil(n)) | |
535 | jrb_delete_node(jrb_first(n)); | |
536 | ||
537 | free(n); | |
490 | 538 | } |
539 | ||
491 | 540 | |
492 | 541 | void *jrb_val(JRB n) |
493 | 542 | { |
494 | return n->val; | |
543 | return n->val; | |
495 | 544 | } |
545 | ||
496 | 546 | |
497 | 547 | JRB jrb_insert(JRB tree, void *key, void *val, |
498 | int (*func)(const void *, const void *)) | |
548 | int (*func)(const void *a, const void *b)) | |
499 | 549 | { |
500 | int fnd; | |
550 | int fnd; | |
501 | 551 | |
502 | return jrb_insert_b(jrb_find_gte(tree, key, func, &fnd), key, val); | |
552 | return jrb_insert_b(jrb_find_gte(tree, key, func, &fnd), key, val); | |
503 | 553 | } |
Branches:
master