diff options
author | David du Colombier <0intro@gmail.com> | 2011-06-02 09:33:56 -0400 |
---|---|---|
committer | Russ Cox <rsc@swtch.com> | 2011-06-02 09:33:56 -0400 |
commit | f5a8ea6fd8908c6f42670b8546239fdbc7fdbf03 (patch) | |
tree | f9e6abdcd5c651adf191f8a9b2dd9655404313a9 /src/libavl/avl.c | |
parent | 7fb06adf54aa6e47974673dcdeb328780927b8e6 (diff) | |
download | plan9port-f5a8ea6fd8908c6f42670b8546239fdbc7fdbf03.tar.gz plan9port-f5a8ea6fd8908c6f42670b8546239fdbc7fdbf03.tar.bz2 plan9port-f5a8ea6fd8908c6f42670b8546239fdbc7fdbf03.zip |
venti: import changes from plan 9
R=rsc
CC=plan9port.codebot
http://codereview.appspot.com/4523057
Diffstat (limited to 'src/libavl/avl.c')
-rw-r--r-- | src/libavl/avl.c | 72 |
1 files changed, 47 insertions, 25 deletions
diff --git a/src/libavl/avl.c b/src/libavl/avl.c index b2c2f7d9..ab8e81d2 100644 --- a/src/libavl/avl.c +++ b/src/libavl/avl.c @@ -97,6 +97,16 @@ balance(Avl **tp, Avl *p) } static int +canoncmp(int cmp) +{ + if(cmp < 0) + return -1; + else if(cmp > 0) + return 1; + return 0; +} + +static int _insertavl(Avl **tp, Avl *p, Avl *r, int (*cmp)(Avl*,Avl*), Avl **rfree) { int i, ob; @@ -110,7 +120,7 @@ _insertavl(Avl **tp, Avl *p, Avl *r, int (*cmp)(Avl*,Avl*), Avl **rfree) return 1; } ob = (*tp)->bal; - if((i = cmp(r, *tp)) != 0){ + if((i = canoncmp(cmp(r, *tp))) != 0){ (*tp)->bal += i * _insertavl(&(*tp)->n[(i+1)/2], *tp, r, cmp, rfree); balance(tp, p); @@ -129,23 +139,6 @@ _insertavl(Avl **tp, Avl *p, Avl *r, int (*cmp)(Avl*,Avl*), Avl **rfree) return 0; } -static Avl* -_lookupavl(Avl *t, Avl *r, int (*cmp)(Avl*,Avl*)) -{ - int i; - Avl *p; - - p = nil; - while(t != nil){ - assert(t->p == p); - if((i = cmp(r, t)) == 0) - return t; - p = t; - t = t->n[(i+1)/2]; - } - return nil; -} - static int successor(Avl **tp, Avl *p, Avl **r) { @@ -175,7 +168,7 @@ _deleteavl(Avl **tp, Avl *p, Avl *rx, int(*cmp)(Avl*,Avl*), Avl **del, return 0; ob = (*tp)->bal; - if((i=cmp(rx, *tp)) != 0){ + if((i=canoncmp(cmp(rx, *tp))) != 0){ (*tp)->bal += i * _deleteavl(&(*tp)->n[(i+1)/2], *tp, rx, cmp, del, predel, arg); balance(tp, p); @@ -259,12 +252,6 @@ insertavl(Avltree *t, Avl *new, Avl **oldp) _insertavl(&t->root, nil, new, t->cmp, oldp); } -Avl* -lookupavl(Avltree *t, Avl *key) -{ - return _lookupavl(t->root, key, t->cmp); -} - static Avl* findpredecessor(Avl *a) { @@ -303,6 +290,41 @@ findsuccessor(Avl *a) } } +static Avl* +_lookupavl(Avl *t, Avl *r, int (*cmp)(Avl*,Avl*), int neighbor) +{ + int i; + Avl *p; + + p = nil; + if(t == nil) + return nil; + do{ + assert(t->p == p); + if((i = canoncmp(cmp(r, t))) == 0) + return t; + p = t; + t = t->n[(i+1)/2]; + }while(t); + if(neighbor == 0) + return nil; + if(neighbor < 0) + return i > 0 ? p : findpredecessor(p); + return i < 0 ? p : findsuccessor(p); +} + +Avl* +searchavl(Avltree *t, Avl *key, int neighbor) +{ + return _lookupavl(t->root, key, t->cmp, neighbor); +} + +Avl* +lookupavl(Avltree *t, Avl *key) +{ + return _lookupavl(t->root, key, t->cmp, 0); +} + static void walkdel(Avl *a, void *v) { |