comparison: rb.c
rb.c
- changeset 67
- b53529762874
- parent 66
- 42085c134e29
- child 68
- 7a97a1769840
equal
deleted
inserted
replaced
| 66:42085c134e29 | 67:b53529762874 |
|---|---|
| 181 { | 181 { |
| 182 int fnd; | 182 int fnd; |
| 183 return rb_find_ikey_n(n, ikey, &fnd); | 183 return rb_find_ikey_n(n, ikey, &fnd); |
| 184 } | 184 } |
| 185 | 185 |
| 186 Rb_node rb_find_gkey_n(Rb_node n, void *key, Rb_compfn *fxn, int *fnd) | 186 Rb_node rb_find_gkey_n(Rb_node n, const void *key, Rb_compfn *fxn, int *fnd) |
| 187 { | 187 { |
| 188 int cmp; | 188 int cmp; |
| 189 | 189 |
| 190 *fnd = 0; | 190 *fnd = 0; |
| 191 if (!ishead(n)) { | 191 if (!ishead(n)) { |
| 192 fprintf(stderr, "rb_find_key_n called on non-head %p\n", | 192 fprintf(stderr, "rb_find_gkey_n called on non-head %p\n", |
| 193 DONT_COMPLAIN n); | 193 DONT_COMPLAIN n); |
| 194 exit(1); | 194 exit(1); |
| 195 } | 195 } |
| 196 if (n->p.root == n) return n; | 196 if (n->p.root == n) return n; |
| 197 cmp = (*fxn)(key, n->c.list.blink->k.key); | 197 cmp = (*fxn)(key, n->c.list.blink->k.key); |
| 210 } | 210 } |
| 211 if (cmp < 0) n = n->c.child.left ; else n = n->c.child.right; | 211 if (cmp < 0) n = n->c.child.left ; else n = n->c.child.right; |
| 212 } | 212 } |
| 213 } | 213 } |
| 214 | 214 |
| 215 Rb_node rb_find_gkey(Rb_node n, void *key, Rb_compfn *fxn) | 215 Rb_node rb_find_gkey(Rb_node n, const void *key, Rb_compfn *fxn) |
| 216 { | 216 { |
| 217 int fnd; | 217 int fnd; |
| 218 return rb_find_gkey_n(n, key, fxn, &fnd); | 218 return rb_find_gkey_n(n, key, fxn, &fnd); |
| 219 } | 219 } |
| 220 | 220 |
| 221 Rb_node rb_find_key_n(Rb_node n, char *key, int *fnd) | 221 Rb_node rb_find_key_n(Rb_node n, const char *key, int *fnd) |
| 222 { | 222 { |
| 223 return rb_find_gkey_n(n, key, (Rb_compfn*)strcmp, fnd); | 223 return rb_find_gkey_n(n, key, (Rb_compfn*)strcmp, fnd); |
| 224 } | 224 } |
| 225 | 225 |
| 226 Rb_node rb_find_key(Rb_node n, char *key) | 226 Rb_node rb_find_key(Rb_node n, const char *key) |
| 227 { | 227 { |
| 228 int fnd; | 228 int fnd; |
| 229 return rb_find_gkey_n(n, key, (Rb_compfn*)strcmp, &fnd); | 229 return rb_find_gkey_n(n, key, (Rb_compfn*)strcmp, &fnd); |
| 230 } | 230 } |
| 231 | 231 |
| 232 Rb_node rb_insert_b(Rb_node n, void *key, void *val) | 232 static int ptrcmp(const void *a, const void *b) |
| 233 { | |
| 234 return (a<b ? -1 : ((a==b) ? 0 : 1)); | |
| 235 } | |
| 236 | |
| 237 Rb_node rb_find_pkey_n(Rb_node n, const void *key, int *fnd) | |
| 238 { | |
| 239 return rb_find_gkey_n(n, key, ptrcmp, fnd); | |
| 240 } | |
| 241 | |
| 242 Rb_node rb_find_pkey(Rb_node n, const void *key) | |
| 243 { | |
| 244 int fnd; | |
| 245 return rb_find_gkey_n(n, key, ptrcmp, &fnd); | |
| 246 } | |
| 247 | |
| 248 Rb_node rb_insert_b(Rb_node n, const void *key, void *val) | |
| 233 { | 249 { |
| 234 Rb_node newleft, newright, newnode, list, p; | 250 Rb_node newleft, newright, newnode, list, p; |
| 235 | 251 |
| 236 if (ishead(n)) { | 252 if (ishead(n)) { |
| 237 if (n->p.root == n) { /* Tree is empty */ | 253 if (n->p.root == n) { /* Tree is empty */ |
| 579 void *rb_val(Rb_node n) | 595 void *rb_val(Rb_node n) |
| 580 { | 596 { |
| 581 return n->v.val; | 597 return n->v.val; |
| 582 } | 598 } |
| 583 | 599 |
| 584 Rb_node rb_insert_a(Rb_node nd, void *key, void *val) | 600 Rb_node rb_insert_a(Rb_node nd, const void *key, void *val) |
| 585 { | 601 { |
| 586 return rb_insert_b(nd->c.list.flink, key, val); | 602 return rb_insert_b(nd->c.list.flink, key, val); |
| 587 } | 603 } |
| 588 | 604 |
| 589 Rb_node rb_insert(Rb_node tree, char *key, void *val) | 605 Rb_node rb_insert(Rb_node tree, const char *key, void *val) |
| 590 { | 606 { |
| 591 return rb_insert_b(rb_find_key(tree, key), key, val); | 607 return rb_insert_b(rb_find_key(tree, key), key, val); |
| 592 } | 608 } |
| 593 | 609 |
| 594 Rb_node rb_inserti(Rb_node tree, int ikey, void *val) | 610 Rb_node rb_inserti(Rb_node tree, int ikey, void *val) |
| 595 { | 611 { |
| 596 return rb_insert_b(rb_find_ikey(tree, ikey), (void *) ikey, val); | 612 return rb_insert_b(rb_find_ikey(tree, ikey), (void *) ikey, val); |
| 597 } | 613 } |
| 598 | 614 |
| 599 Rb_node rb_insertg(Rb_node tree, void *key, void *val, Rb_compfn *func) | 615 Rb_node rb_insertg(Rb_node tree, const void *key, void *val, Rb_compfn *func) |
| 600 { | 616 { |
| 601 return rb_insert_b(rb_find_gkey(tree, key, func), key, val); | 617 return rb_insert_b(rb_find_gkey(tree, key, func), key, val); |
| 602 } | 618 } |
| 603 | 619 |
| 604 | 620 Rb_node rb_insertp(Rb_node tree, const void *key, void *val) |
| 621 { | |
| 622 return rb_insertg(tree, key, val, ptrcmp); | |
| 623 } | |
| 624 | |
| 625 |
