From 9cf519814591413493be10cfaa00853cb15e7a0b Mon Sep 17 00:00:00 2001 From: spew Date: Sat, 22 Apr 2017 13:59:37 -0500 Subject: [PATCH] libavl: lookup can return the closest match --- sys/include/avl.h | 5 +++-- sys/man/2/avl | 14 ++++++++------ sys/src/cmd/upas/fs/mtree.c | 6 +++--- sys/src/cmd/upas/imap4d/fstree.c | 2 +- sys/src/cmd/upas/imap4d/imp.c | 2 +- sys/src/cmd/venti/copy.c | 2 +- sys/src/games/galaxy/simulate.c | 6 +++--- sys/src/games/mix/mix.c | 2 +- sys/src/libavl/avl.c | 20 +++++++++++++------- 9 files changed, 34 insertions(+), 25 deletions(-) diff --git a/sys/include/avl.h b/sys/include/avl.h index 49b61fbb6..be7b18a5c 100644 --- a/sys/include/avl.h +++ b/sys/include/avl.h @@ -15,8 +15,9 @@ struct Avltree { Avl *root; }; -Avltree *avlcreate(int(*cmp)(Avl*, Avl*)); -Avl *avllookup(Avltree*, Avl*); +Avltree *avlinit(Avltree*, int(*)(Avl*, Avl*)); +Avltree *avlcreate(int(*)(Avl*, Avl*)); +Avl *avllookup(Avltree*, Avl*, int); Avl *avldelete(Avltree*, Avl*); Avl *avlinsert(Avltree*, Avl*); Avl *avlnext(Avl*); diff --git a/sys/man/2/avl b/sys/man/2/avl index 388b8b3f4..41a4e93ed 100644 --- a/sys/man/2/avl +++ b/sys/man/2/avl @@ -30,7 +30,7 @@ struct Avltree { Avltree *avlcreate(int(*cmp)(Avl*, Avl*)); Avl *avlinsert(Avltree *tree, Avl *new); Avl *avldelete(Avltree *tree, Avl *key); -Avl *avllookup(Avltree *tree, Avl *key); +Avl *avllookup(Avltree *tree, Avl *key, int dir); Avl *avlnext(Avl *n); Avl *avlprev(Avl *n); @@ -55,13 +55,15 @@ node into the tree and returns an existing node with the same key that has been removed from the tree and may be freed. .I Avllookup -returns the -node that matches the key or -.B nil -if no node matches. +searches for a given key and returns +the closest node less than the given key, +.BR nil , +or the closest node greater than the key depending on whether +.I dir +is less than, equal to, or greater than zero, respectively. .I Avldelete removes the node matching the key from the tree and returns -it. It returns nil of no matching key is found. +it. It returns nil if no matching key is found. .PP .I Avlnext returns the next diff --git a/sys/src/cmd/upas/fs/mtree.c b/sys/src/cmd/upas/fs/mtree.c index 4f2af5655..d50deaef5 100644 --- a/sys/src/cmd/upas/fs/mtree.c +++ b/sys/src/cmd/upas/fs/mtree.c @@ -22,7 +22,7 @@ mtreeisdup(Mailbox *mb, Message *m) return 0; memset(&t, 0, sizeof t); t.m = m; - if(avllookup(mb->mtree, &t)) + if(avllookup(mb->mtree, &t, 0)) return 1; return 0; } @@ -36,7 +36,7 @@ mtreefind(Mailbox *mb, uchar *digest) m0.digest = digest; memset(&t, 0, sizeof t); t.m = &m0; - if(p = (Mtree*)avllookup(mb->mtree, &t)) + if(p = (Mtree*)avllookup(mb->mtree, &t, 0)) return p->m; return nil; } @@ -65,7 +65,7 @@ mtreedelete(Mailbox *mb, Message *m) if(m->deleted & ~Deleted){ if(m->digest == nil) return; - p = (Mtree*)avllookup(mb->mtree, &t); + p = (Mtree*)avllookup(mb->mtree, &t, 0); if(p == nil || p->m != m) return; p = (Mtree*)avldelete(mb->mtree, &t); diff --git a/sys/src/cmd/upas/imap4d/fstree.c b/sys/src/cmd/upas/imap4d/fstree.c index 13ef32b7c..ee491c3fc 100644 --- a/sys/src/cmd/upas/imap4d/fstree.c +++ b/sys/src/cmd/upas/imap4d/fstree.c @@ -25,7 +25,7 @@ fstreefind(Box *mb, int id) memset(&t, 0, sizeof t); m0.id = id; t.m = &m0; - if(p = (Fstree*)avllookup(mb->fstree, &t)) + if(p = (Fstree*)avllookup(mb->fstree, &t, 0)) return p->m; return nil; } diff --git a/sys/src/cmd/upas/imap4d/imp.c b/sys/src/cmd/upas/imap4d/imp.c index c5542eab7..a8a96fb28 100644 --- a/sys/src/cmd/upas/imap4d/imp.c +++ b/sys/src/cmd/upas/imap4d/imp.c @@ -100,7 +100,7 @@ rdimp(Biobuf *b, Box *box) memset(&t, 0, sizeof t); m0.info[Idigest] = f[0]; t.m = &m0; - p = (Mtree*)avllookup(mtree, &t); + p = (Mtree*)avllookup(mtree, &t, 0); if(p){ m = p->m; if(m->uid && m->uid != u){ diff --git a/sys/src/cmd/venti/copy.c b/sys/src/cmd/venti/copy.c index 436ce418a..c9364fc4b 100644 --- a/sys/src/cmd/venti/copy.c +++ b/sys/src/cmd/venti/copy.c @@ -51,7 +51,7 @@ havevisited(uchar score[VtScoreSize], int type) return 0; memmove(a.score, score, VtScoreSize); a.type = type; - return avllookup(scoretree, &a) != nil; + return avllookup(scoretree, &a, 0) != nil; } static void diff --git a/sys/src/games/galaxy/simulate.c b/sys/src/games/galaxy/simulate.c index 4622b6421..9fbf135ac 100644 --- a/sys/src/games/galaxy/simulate.c +++ b/sys/src/games/galaxy/simulate.c @@ -6,9 +6,9 @@ int extraproc = -1, throttle; -static QLock* golock; -static Rendez* gorend; -static int* go; +static QLock *golock; +static Rendez *gorend; +static int *go; static QLock runninglock; static Rendez runningrend; diff --git a/sys/src/games/mix/mix.c b/sys/src/games/mix/mix.c index 1672afaaf..2eb993fca 100644 --- a/sys/src/games/mix/mix.c +++ b/sys/src/games/mix/mix.c @@ -413,7 +413,7 @@ sym(char *name) Sym *s, l; l.name = name; - s = (Sym*)avllookup(syms, &l); + s = (Sym*)avllookup(syms, &l, 0); if(s != nil) return s; diff --git a/sys/src/libavl/avl.c b/sys/src/libavl/avl.c index 615de4957..8f1c8b075 100644 --- a/sys/src/libavl/avl.c +++ b/sys/src/libavl/avl.c @@ -4,10 +4,6 @@ /* See Knuth Volume 3, 6.2.3 */ -Avl *avllookup(Avltree*, Avl*); -Avl *avldelete(Avltree*, Avl*); -Avl *avlinsert(Avltree*, Avl*); - Avltree* avlcreate(int (*cmp)(Avl*, Avl*)) { @@ -16,32 +12,42 @@ avlcreate(int (*cmp)(Avl*, Avl*)) t = malloc(sizeof(*t)); if(t == nil) return nil; + return avlinit(t, cmp); +} +Avltree* +avlinit(Avltree *t, int (*cmp)(Avl*, Avl*)) +{ t->cmp = cmp; t->root = nil; return t; } Avl* -avllookup(Avltree *t, Avl *k) +avllookup(Avltree *t, Avl *k, int d) { - Avl *h; + Avl *h, *n; int c; + n = nil; h = t->root; while(h != nil){ c = (t->cmp)(k, h); if(c < 0){ + if(d > 0) + n = h; h = h->c[0]; continue; } if(c > 0){ + if(d < 0) + n = h; h = h->c[1]; continue; } return h; } - return nil; + return n; } static int insert(int (*)(Avl*, Avl*), Avl*, Avl**, Avl*, Avl**); -- 2.44.0