comparison: rb.c
rb.c
- changeset 65
- 58e382ae97cd
- child 66
- 42085c134e29
equal
deleted
inserted
replaced
| 64:f20d97d852ce | 65:58e382ae97cd |
|---|---|
| 1 /* | |
| 2 Generic C code for red-black trees. | |
| 3 Copyright (C) 2000 James S. Plank | |
| 4 | |
| 5 This library is free software; you can redistribute it and/or | |
| 6 modify it under the terms of the GNU Lesser General Public | |
| 7 License as published by the Free Software Foundation; either | |
| 8 version 2.1 of the License, or (at your option) any later version. | |
| 9 | |
| 10 This library is distributed in the hope that it will be useful, | |
| 11 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
| 13 Lesser General Public License for more details. | |
| 14 | |
| 15 You should have received a copy of the GNU Lesser General Public | |
| 16 License along with this library; if not, write to the Free Software | |
| 17 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | |
| 18 */ | |
| 19 /* Revision 1.2. Jim Plank */ | |
| 20 | |
| 21 /* Original code by Jim Plank (plank@cs.utk.edu) */ | |
| 22 /* modified for THINK C 6.0 for Macintosh by Chris Bartley */ | |
| 23 | |
| 24 #include <string.h> | |
| 25 #include <stdio.h> | |
| 26 #include <stdlib.h> | |
| 27 #include <ctype.h> | |
| 28 #include "rb.h" | |
| 29 | |
| 30 static void mk_new_int(Rb_node l, Rb_node r, Rb_node p, int il); | |
| 31 static Rb_node lprev(Rb_node n); | |
| 32 static Rb_node rprev(Rb_node n); | |
| 33 static void recolor(Rb_node n); | |
| 34 static void single_rotate(Rb_node y, int l); | |
| 35 static void rb_print_tree(Rb_node t, int level); | |
| 36 static void rb_iprint_tree(Rb_node t, int level); | |
| 37 | |
| 38 | |
| 39 #define isred(n) (n->s.red) | |
| 40 #define isblack(n) (!isred(n)) | |
| 41 #define isleft(n) (n->s.left) | |
| 42 #define isright(n) (!isleft(n)) | |
| 43 #define isint(n) (n->s.internal) | |
| 44 #define isext(n) (!isint(n)) | |
| 45 #define ishead(n) (n->s.head) | |
| 46 #define isroot(n) (n->s.root) | |
| 47 #define setred(n) n->s.red = 1 | |
| 48 #define setblack(n) n->s.red = 0 | |
| 49 #define setleft(n) n->s.left = 1 | |
| 50 #define setright(n) n->s.left = 0 | |
| 51 #define sethead(n) n->s.head = 1 | |
| 52 #define setroot(n) n->s.root = 1 | |
| 53 #define setint(n) n->s.internal = 1 | |
| 54 #define setext(n) n->s.internal = 0 | |
| 55 #define setnormal(n) { n->s.root = 0; n ->s.head = 0; } | |
| 56 #define sibling(n) ((isleft(n)) ? n->p.parent->c.child.right \ | |
| 57 : n->p.parent->c.child.left) | |
| 58 | |
| 59 static void insert(Rb_node item, Rb_node list) /* Inserts to the end of a list */ | |
| 60 { | |
| 61 Rb_node last_node; | |
| 62 | |
| 63 last_node = list->c.list.blink; | |
| 64 | |
| 65 list->c.list.blink = item; | |
| 66 last_node->c.list.flink = item; | |
| 67 item->c.list.blink = last_node; | |
| 68 item->c.list.flink = list; | |
| 69 } | |
| 70 | |
| 71 static void delete_item(Rb_node item) /* Deletes an arbitrary iterm */ | |
| 72 { | |
| 73 item->c.list.flink->c.list.blink = item->c.list.blink; | |
| 74 item->c.list.blink->c.list.flink = item->c.list.flink; | |
| 75 } | |
| 76 | |
| 77 #define mk_new_ext(new, kkkey, vvval) {\ | |
| 78 new = (Rb_node) malloc(sizeof(struct rb_node));\ | |
| 79 new->v.val = vvval;\ | |
| 80 new->k.key = kkkey;\ | |
| 81 setext(new);\ | |
| 82 setblack(new);\ | |
| 83 setnormal(new);\ | |
| 84 } | |
| 85 | |
| 86 static void mk_new_int(Rb_node l, Rb_node r, Rb_node p, int il) | |
| 87 { | |
| 88 Rb_node newnode; | |
| 89 | |
| 90 newnode = (Rb_node) malloc(sizeof(struct rb_node)); | |
| 91 setint(newnode); | |
| 92 setred(newnode); | |
| 93 setnormal(newnode); | |
| 94 newnode->c.child.left = l; | |
| 95 newnode->c.child.right = r; | |
| 96 newnode->p.parent = p; | |
| 97 newnode->k.lext = l; | |
| 98 newnode->v.rext = r; | |
| 99 l->p.parent = newnode; | |
| 100 r->p.parent = newnode; | |
| 101 setleft(l); | |
| 102 setright(r); | |
| 103 if (ishead(p)) { | |
| 104 p->p.root = newnode; | |
| 105 setroot(newnode); | |
| 106 } else if (il) { | |
| 107 setleft(newnode); | |
| 108 p->c.child.left = newnode; | |
| 109 } else { | |
| 110 setright(newnode); | |
| 111 p->c.child.right = newnode; | |
| 112 } | |
| 113 recolor(newnode); | |
| 114 } | |
| 115 | |
| 116 | |
| 117 Rb_node lprev(Rb_node n) | |
| 118 { | |
| 119 if (ishead(n)) return n; | |
| 120 while (!isroot(n)) { | |
| 121 if (isright(n)) return n->p.parent; | |
| 122 n = n->p.parent; | |
| 123 } | |
| 124 return n->p.parent; | |
| 125 } | |
| 126 | |
| 127 Rb_node rprev(Rb_node n) | |
| 128 { | |
| 129 if (ishead(n)) return n; | |
| 130 while (!isroot(n)) { | |
| 131 if (isleft(n)) return n->p.parent; | |
| 132 n = n->p.parent; | |
| 133 } | |
| 134 return n->p.parent; | |
| 135 } | |
| 136 | |
| 137 Rb_node make_rb() | |
| 138 { | |
| 139 Rb_node head; | |
| 140 | |
| 141 head = (Rb_node) malloc (sizeof(struct rb_node)); | |
| 142 head->c.list.flink = head; | |
| 143 head->c.list.blink = head; | |
| 144 head->p.root = head; | |
| 145 head->k.key = ""; | |
| 146 sethead(head); | |
| 147 return head; | |
| 148 } | |
| 149 | |
| 150 Rb_node rb_find_key_n(Rb_node n, char *key, int *fnd) | |
| 151 { | |
| 152 int cmp; | |
| 153 | |
| 154 *fnd = 0; | |
| 155 if (!ishead(n)) { | |
| 156 fprintf(stderr, "rb_find_key_n called on non-head 0x%x\n", n); | |
| 157 exit(1); | |
| 158 } | |
| 159 if (n->p.root == n) return n; | |
| 160 cmp = strcmp(key, n->c.list.blink->k.key); | |
| 161 if (cmp == 0) { | |
| 162 *fnd = 1; | |
| 163 return n->c.list.blink; | |
| 164 } | |
| 165 if (cmp > 0) return n; | |
| 166 else n = n->p.root; | |
| 167 while (1) { | |
| 168 if (isext(n)) return n; | |
| 169 cmp = strcmp(key, n->k.lext->k.key); | |
| 170 if (cmp == 0) { | |
| 171 *fnd = 1; | |
| 172 return n->k.lext; | |
| 173 } | |
| 174 if (cmp < 0) n = n->c.child.left ; else n = n->c.child.right; | |
| 175 } | |
| 176 } | |
| 177 | |
| 178 Rb_node rb_find_key(Rb_node n, char *key) | |
| 179 { | |
| 180 int fnd; | |
| 181 return rb_find_key_n(n, key, &fnd); | |
| 182 } | |
| 183 | |
| 184 Rb_node rb_find_ikey_n(Rb_node n, int ikey, int *fnd) | |
| 185 { | |
| 186 *fnd = 0; | |
| 187 if (!ishead(n)) { | |
| 188 fprintf(stderr, "rb_find_ikey_n called on non-head 0x%x\n", n); | |
| 189 exit(1); | |
| 190 } | |
| 191 if (n->p.root == n) return n; | |
| 192 if (ikey == n->c.list.blink->k.ikey) { | |
| 193 *fnd = 1; | |
| 194 return n->c.list.blink; | |
| 195 } | |
| 196 if (ikey > n->c.list.blink->k.ikey) return n; | |
| 197 else n = n->p.root; | |
| 198 while (1) { | |
| 199 if (isext(n)) return n; | |
| 200 if (ikey == n->k.lext->k.ikey) { | |
| 201 *fnd = 1; | |
| 202 return n->k.lext; | |
| 203 } | |
| 204 n = (ikey < n->k.lext->k.ikey) ? n->c.child.left : n->c.child.right; | |
| 205 } | |
| 206 } | |
| 207 | |
| 208 Rb_node rb_find_ikey(Rb_node n, int ikey) | |
| 209 { | |
| 210 int fnd; | |
| 211 return rb_find_ikey_n(n, ikey, &fnd); | |
| 212 } | |
| 213 | |
| 214 Rb_node rb_find_gkey_n(Rb_node n, char *key,int (*fxn)(char *, char *), int *fnd) | |
| 215 { | |
| 216 int cmp; | |
| 217 | |
| 218 *fnd = 0; | |
| 219 if (!ishead(n)) { | |
| 220 fprintf(stderr, "rb_find_key_n called on non-head 0x%x\n", n); | |
| 221 exit(1); | |
| 222 } | |
| 223 if (n->p.root == n) return n; | |
| 224 cmp = (*fxn)(key, n->c.list.blink->k.key); | |
| 225 if (cmp == 0) { | |
| 226 *fnd = 1; | |
| 227 return n->c.list.blink; | |
| 228 } | |
| 229 if (cmp > 0) return n; | |
| 230 else n = n->p.root; | |
| 231 while (1) { | |
| 232 if (isext(n)) return n; | |
| 233 cmp = (*fxn)(key, n->k.lext->k.key); | |
| 234 if (cmp == 0) { | |
| 235 *fnd = 1; | |
| 236 return n->k.lext; | |
| 237 } | |
| 238 if (cmp < 0) n = n->c.child.left ; else n = n->c.child.right; | |
| 239 } | |
| 240 } | |
| 241 | |
| 242 Rb_node rb_find_gkey(Rb_node n, char *key, int (*fxn)(char *, char *)) | |
| 243 { | |
| 244 int fnd; | |
| 245 return rb_find_gkey_n(n, key, fxn, &fnd); | |
| 246 } | |
| 247 | |
| 248 Rb_node rb_insert_b(Rb_node n, char *key, char *val) | |
| 249 { | |
| 250 Rb_node newleft, newright, newnode, list, p; | |
| 251 | |
| 252 if (ishead(n)) { | |
| 253 if (n->p.root == n) { /* Tree is empty */ | |
| 254 mk_new_ext(newnode, key, val); | |
| 255 insert(newnode, n); | |
| 256 n->p.root = newnode; | |
| 257 newnode->p.parent = n; | |
| 258 setroot(newnode); | |
| 259 return newnode; | |
| 260 } else { | |
| 261 mk_new_ext(newright, key, val); | |
| 262 insert(newright, n); | |
| 263 newleft = newright->c.list.blink; | |
| 264 setnormal(newleft); | |
| 265 mk_new_int(newleft, newright, newleft->p.parent, isleft(newleft)); | |
| 266 p = rprev(newright); | |
| 267 if (!ishead(p)) p->k.lext = newright; | |
| 268 return newright; | |
| 269 } | |
| 270 } else { | |
| 271 mk_new_ext(newleft, key, val); | |
| 272 insert(newleft, n); | |
| 273 setnormal(n); | |
| 274 mk_new_int(newleft, n, n->p.parent, isleft(n)); | |
| 275 p = lprev(newleft); | |
| 276 if (!ishead(p)) p->v.rext = newleft; | |
| 277 return newleft; | |
| 278 } | |
| 279 } | |
| 280 | |
| 281 static void recolor(Rb_node n) | |
| 282 { | |
| 283 Rb_node p, gp, s; | |
| 284 int done = 0; | |
| 285 | |
| 286 while(!done) { | |
| 287 if (isroot(n)) { | |
| 288 setblack(n); | |
| 289 return; | |
| 290 } | |
| 291 | |
| 292 p = n->p.parent; | |
| 293 | |
| 294 if (isblack(p)) return; | |
| 295 | |
| 296 if (isroot(p)) { | |
| 297 setblack(p); | |
| 298 return; | |
| 299 } | |
| 300 | |
| 301 gp = p->p.parent; | |
| 302 s = sibling(p); | |
| 303 if (isred(s)) { | |
| 304 setblack(p); | |
| 305 setred(gp); | |
| 306 setblack(s); | |
| 307 n = gp; | |
| 308 } else { | |
| 309 done = 1; | |
| 310 } | |
| 311 } | |
| 312 /* p's sibling is black, p is red, gp is black */ | |
| 313 | |
| 314 if ((isleft(n) == 0) == (isleft(p) == 0)) { | |
| 315 single_rotate(gp, isleft(n)); | |
| 316 setblack(p); | |
| 317 setred(gp); | |
| 318 } else { | |
| 319 single_rotate(p, isleft(n)); | |
| 320 single_rotate(gp, isleft(n)); | |
| 321 setblack(n); | |
| 322 setred(gp); | |
| 323 } | |
| 324 } | |
| 325 | |
| 326 static void single_rotate(Rb_node y, int l) | |
| 327 { | |
| 328 int rl, ir; | |
| 329 Rb_node x, yp; | |
| 330 char *tmp; | |
| 331 | |
| 332 ir = isroot(y); | |
| 333 yp = y->p.parent; | |
| 334 if (!ir) { | |
| 335 rl = isleft(y); | |
| 336 } | |
| 337 | |
| 338 if (l) { | |
| 339 x = y->c.child.left; | |
| 340 y->c.child.left = x->c.child.right; | |
| 341 setleft(y->c.child.left); | |
| 342 y->c.child.left->p.parent = y; | |
| 343 x->c.child.right = y; | |
| 344 setright(y); | |
| 345 } else { | |
| 346 x = y->c.child.right; | |
| 347 y->c.child.right = x->c.child.left; | |
| 348 setright(y->c.child.right); | |
| 349 y->c.child.right->p.parent = y; | |
| 350 x->c.child.left = y; | |
| 351 setleft(y); | |
| 352 } | |
| 353 | |
| 354 x->p.parent = yp; | |
| 355 y->p.parent = x; | |
| 356 if (ir) { | |
| 357 yp->p.root = x; | |
| 358 setnormal(y); | |
| 359 setroot(x); | |
| 360 } else { | |
| 361 if (rl) { | |
| 362 yp->c.child.left = x; | |
| 363 setleft(x); | |
| 364 } else { | |
| 365 yp->c.child.right = x; | |
| 366 setright(x); | |
| 367 } | |
| 368 } | |
| 369 } | |
| 370 | |
| 371 void rb_delete_node(Rb_node n) | |
| 372 { | |
| 373 Rb_node s, p, gp; | |
| 374 char ir; | |
| 375 | |
| 376 if (isint(n)) { | |
| 377 fprintf(stderr, "Cannot delete an internal node: 0x%x\n", n); | |
| 378 exit(1); | |
| 379 } | |
| 380 if (ishead(n)) { | |
| 381 fprintf(stderr, "Cannot delete the head of an rb_tree: 0x%x\n", n); | |
| 382 exit(1); | |
| 383 } | |
| 384 delete_item(n); /* Delete it from the list */ | |
| 385 p = n->p.parent; /* The only node */ | |
| 386 if (isroot(n)) { | |
| 387 p->p.root = p; | |
| 388 free(n); | |
| 389 return; | |
| 390 } | |
| 391 s = sibling(n); /* The only node after deletion */ | |
| 392 if (isroot(p)) { | |
| 393 s->p.parent = p->p.parent; | |
| 394 s->p.parent->p.root = s; | |
| 395 setroot(s); | |
| 396 free(p); | |
| 397 free(n); | |
| 398 return; | |
| 399 } | |
| 400 gp = p->p.parent; /* Set parent to sibling */ | |
| 401 s->p.parent = gp; | |
| 402 if (isleft(p)) { | |
| 403 gp->c.child.left = s; | |
| 404 setleft(s); | |
| 405 } else { | |
| 406 gp->c.child.right = s; | |
| 407 setright(s); | |
| 408 } | |
| 409 ir = isred(p); | |
| 410 free(p); | |
| 411 free(n); | |
| 412 | |
| 413 if (isext(s)) { /* Update proper rext and lext values */ | |
| 414 p = lprev(s); | |
| 415 if (!ishead(p)) p->v.rext = s; | |
| 416 p = rprev(s); | |
| 417 if (!ishead(p)) p->k.lext = s; | |
| 418 } else if (isblack(s)) { | |
| 419 fprintf(stderr, "DELETION PROB -- sib is black, internal\n"); | |
| 420 exit(1); | |
| 421 } else { | |
| 422 p = lprev(s); | |
| 423 if (!ishead(p)) p->v.rext = s->c.child.left; | |
| 424 p = rprev(s); | |
| 425 if (!ishead(p)) p->k.lext = s->c.child.right; | |
| 426 setblack(s); | |
| 427 return; | |
| 428 } | |
| 429 | |
| 430 if (ir) return; | |
| 431 | |
| 432 /* Recolor */ | |
| 433 | |
| 434 n = s; | |
| 435 p = n->p.parent; | |
| 436 s = sibling(n); | |
| 437 while(isblack(p) && isblack(s) && isint(s) && | |
| 438 isblack(s->c.child.left) && isblack(s->c.child.right)) { | |
| 439 setred(s); | |
| 440 n = p; | |
| 441 if (isroot(n)) return; | |
| 442 p = n->p.parent; | |
| 443 s = sibling(n); | |
| 444 } | |
| 445 | |
| 446 if (isblack(p) && isred(s)) { /* Rotation 2.3b */ | |
| 447 single_rotate(p, isright(n)); | |
| 448 setred(p); | |
| 449 setblack(s); | |
| 450 s = sibling(n); | |
| 451 } | |
| 452 | |
| 453 { Rb_node x, z; char il; | |
| 454 | |
| 455 if (isext(s)) { | |
| 456 fprintf(stderr, "DELETION ERROR: sibling not internal\n"); | |
| 457 exit(1); | |
| 458 } | |
| 459 | |
| 460 il = isleft(n); | |
| 461 x = il ? s->c.child.left : s->c.child.right ; | |
| 462 z = sibling(x); | |
| 463 | |
| 464 if (isred(z)) { /* Rotation 2.3f */ | |
| 465 single_rotate(p, !il); | |
| 466 setblack(z); | |
| 467 if (isred(p)) setred(s); else setblack(s); | |
| 468 setblack(p); | |
| 469 } else if (isblack(x)) { /* Recoloring only (2.3c) */ | |
| 470 if (isred(s) || isblack(p)) { | |
| 471 fprintf(stderr, "DELETION ERROR: 2.3c not quite right\n"); | |
| 472 exit(1); | |
| 473 } | |
| 474 setblack(p); | |
| 475 setred(s); | |
| 476 return; | |
| 477 } else if (isred(p)) { /* 2.3d */ | |
| 478 single_rotate(s, il); | |
| 479 single_rotate(p, !il); | |
| 480 setblack(x); | |
| 481 setred(s); | |
| 482 return; | |
| 483 } else { /* 2.3e */ | |
| 484 single_rotate(s, il); | |
| 485 single_rotate(p, !il); | |
| 486 setblack(x); | |
| 487 return; | |
| 488 } | |
| 489 } | |
| 490 } | |
| 491 | |
| 492 | |
| 493 void rb_print_tree(Rb_node t, int level) | |
| 494 { | |
| 495 int i; | |
| 496 if (ishead(t) && t->p.parent == t) { | |
| 497 printf("tree 0x%x is empty\n", t); | |
| 498 } else if (ishead(t)) { | |
| 499 printf("Head: 0x%x. Root = 0x%x\n", t, t->p.root); | |
| 500 rb_print_tree(t->p.root, 0); | |
| 501 } else { | |
| 502 if (isext(t)) { | |
| 503 for (i = 0; i < level; i++) putchar(' '); | |
| 504 printf("Ext node 0x%x: %c,%c: p=0x%x, k=%s\n", | |
| 505 t, isred(t)?'R':'B', isleft(t)?'l':'r', t->p.parent, t->k.key); | |
| 506 } else { | |
| 507 rb_print_tree(t->c.child.left, level+2); | |
| 508 rb_print_tree(t->c.child.right, level+2); | |
| 509 for (i = 0; i < level; i++) putchar(' '); | |
| 510 printf("Int node 0x%x: %c,%c: l=0x%x, r=0x%x, p=0x%x, lr=(%s,%s)\n", | |
| 511 t, isred(t)?'R':'B', isleft(t)?'l':'r', t->c.child.left, | |
| 512 t->c.child.right, | |
| 513 t->p.parent, t->k.lext->k.key, t->v.rext->k.key); | |
| 514 } | |
| 515 } | |
| 516 } | |
| 517 | |
| 518 void rb_iprint_tree(Rb_node t, int level) | |
| 519 { | |
| 520 int i; | |
| 521 if (ishead(t) && t->p.parent == t) { | |
| 522 printf("tree 0x%x is empty\n", t); | |
| 523 } else if (ishead(t)) { | |
| 524 printf("Head: 0x%x. Root = 0x%x, < = 0x%x, > = 0x%x\n", | |
| 525 t, t->p.root, t->c.list.blink, t->c.list.flink); | |
| 526 rb_iprint_tree(t->p.root, 0); | |
| 527 } else { | |
| 528 if (isext(t)) { | |
| 529 for (i = 0; i < level; i++) putchar(' '); | |
| 530 printf("Ext node 0x%x: %c,%c: p=0x%x, <=0x%x, >=0x%x k=%d\n", | |
| 531 t, isred(t)?'R':'B', isleft(t)?'l':'r', t->p.parent, | |
| 532 t->c.list.blink, t->c.list.flink, t->k.ikey); | |
| 533 } else { | |
| 534 rb_iprint_tree(t->c.child.left, level+2); | |
| 535 rb_iprint_tree(t->c.child.right, level+2); | |
| 536 for (i = 0; i < level; i++) putchar(' '); | |
| 537 printf("Int node 0x%x: %c,%c: l=0x%x, r=0x%x, p=0x%x, lr=(%d,%d)\n", | |
| 538 t, isred(t)?'R':'B', isleft(t)?'l':'r', t->c.child.left, | |
| 539 t->c.child.right, | |
| 540 t->p.parent, t->k.lext->k.ikey, t->v.rext->k.ikey); | |
| 541 } | |
| 542 } | |
| 543 } | |
| 544 | |
| 545 int rb_nblack(Rb_node n) | |
| 546 { | |
| 547 int nb; | |
| 548 if (ishead(n) || isint(n)) { | |
| 549 fprintf(stderr, "ERROR: rb_nblack called on a non-external node 0x%x\n", | |
| 550 n); | |
| 551 exit(1); | |
| 552 } | |
| 553 nb = 0; | |
| 554 while(!ishead(n)) { | |
| 555 if (isblack(n)) nb++; | |
| 556 n = n->p.parent; | |
| 557 } | |
| 558 return nb; | |
| 559 } | |
| 560 | |
| 561 int rb_plength(Rb_node n) | |
| 562 { | |
| 563 int pl; | |
| 564 if (ishead(n) || isint(n)) { | |
| 565 fprintf(stderr, "ERROR: rb_plength called on a non-external node 0x%x\n", | |
| 566 n); | |
| 567 exit(1); | |
| 568 } | |
| 569 pl = 0; | |
| 570 while(!ishead(n)) { | |
| 571 pl++; | |
| 572 n = n->p.parent; | |
| 573 } | |
| 574 return pl; | |
| 575 } | |
| 576 | |
| 577 void rb_free_tree(Rb_node n) | |
| 578 { | |
| 579 if (!ishead(n)) { | |
| 580 fprintf(stderr, "ERROR: Rb_free_tree called on a non-head node\n"); | |
| 581 exit(1); | |
| 582 } | |
| 583 | |
| 584 while(rb_first(n) != rb_nil(n)) { | |
| 585 rb_delete_node(rb_first(n)); | |
| 586 } | |
| 587 free(n); | |
| 588 } | |
| 589 | |
| 590 char *rb_val(Rb_node n) | |
| 591 { | |
| 592 return n->v.val; | |
| 593 } | |
| 594 | |
| 595 Rb_node rb_insert_a(Rb_node nd, char *key, char *val) | |
| 596 { | |
| 597 rb_insert_b(nd->c.list.flink, key, val); | |
| 598 } | |
| 599 | |
| 600 Rb_node rb_insert(Rb_node tree, char *key, char *val) | |
| 601 { | |
| 602 rb_insert_b(rb_find_key(tree, key), key, val); | |
| 603 } | |
| 604 | |
| 605 Rb_node rb_inserti(Rb_node tree, int ikey, char *val) | |
| 606 { | |
| 607 rb_insert_b(rb_find_ikey(tree, ikey), (char *) ikey, val); | |
| 608 } | |
| 609 | |
| 610 Rb_node rb_insertg(Rb_node tree, char *key, char *val, | |
| 611 int (*func)(char *, char *)) | |
| 612 { | |
| 613 rb_insert_b(rb_find_gkey(tree, key, func), key, val); | |
| 614 } | |
| 615 | |
| 616 |
