diff options
author | Jason Evans <jasone@FreeBSD.org> | 2007-06-15 16:09:47 +0000 |
---|---|---|
committer | Jason Evans <jasone@FreeBSD.org> | 2007-06-15 16:09:47 +0000 |
commit | 5a0d489f5ab6d7f0f365169e0752344a6b2673db (patch) | |
tree | 54cf7425c7a8495f1304e8ddc501258851bb8646 /sys/sys/tree.h | |
parent | 3fa4da3d2a6c9af0f3a4d38fb197d526d46b84a9 (diff) | |
download | src-5a0d489f5ab6d7f0f365169e0752344a6b2673db.tar.gz src-5a0d489f5ab6d7f0f365169e0752344a6b2673db.zip |
Simplify/optimize RB_NFIND().
Submitted by: Andriy Gapon <avg@icyb.net.ua>
Notes
Notes:
svn path=/head/; revision=170779
Diffstat (limited to 'sys/sys/tree.h')
-rw-r--r-- | sys/sys/tree.h | 30 |
1 files changed, 11 insertions, 19 deletions
diff --git a/sys/sys/tree.h b/sys/sys/tree.h index c2157eea488a..3af9a2b14406 100644 --- a/sys/sys/tree.h +++ b/sys/sys/tree.h @@ -643,29 +643,21 @@ name##_RB_FIND(struct name *head, struct type *elm) \ attr struct type * \ name##_RB_NFIND(struct name *head, struct type *elm) \ { \ - struct type *ret = RB_ROOT(head); \ - struct type *tmp; \ + struct type *tmp = RB_ROOT(head); \ + struct type *res = NULL; \ int comp; \ - while (ret && (comp = cmp(elm, ret)) != 0) { \ + while (tmp) { \ + comp = cmp(elm, tmp); \ if (comp < 0) { \ - if ((tmp = RB_LEFT(ret, field)) == NULL) \ - break; \ - ret = tmp; \ - } else { \ - if ((tmp = RB_RIGHT(ret, field)) == NULL) { \ - tmp = ret; \ - ret = RB_PARENT(ret, field); \ - while (ret && tmp == RB_RIGHT(ret, \ - field)) { \ - tmp = ret; \ - ret = RB_PARENT(ret, field); \ - } \ - break; \ - } \ - ret = tmp; \ + res = tmp; \ + tmp = RB_LEFT(tmp, field); \ } \ + else if (comp > 0) \ + tmp = RB_RIGHT(tmp, field); \ + else \ + return (tmp); \ } \ - return (ret); \ + return (res); \ } \ \ /* ARGSUSED */ \ |