From owner-freebsd-current@FreeBSD.ORG Thu Dec 22 23:13:52 2005 Return-Path: X-Original-To: freebsd-current@freebsd.org Delivered-To: freebsd-current@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id C985716A41F for ; Thu, 22 Dec 2005 23:13:52 +0000 (GMT) (envelope-from jasone@freebsd.org) Received: from lh.synack.net (lh.synack.net [204.152.188.37]) by mx1.FreeBSD.org (Postfix) with ESMTP id 6153C43D55 for ; Thu, 22 Dec 2005 23:13:52 +0000 (GMT) (envelope-from jasone@freebsd.org) Received: by lh.synack.net (Postfix, from userid 100) id 3F6B55E48DC; Thu, 22 Dec 2005 15:13:52 -0800 (PST) Received: from [192.168.168.203] (moscow-cuda-gen2-68-64-60-20.losaca.adelphia.net [68.64.60.20]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (No client certificate requested) by lh.synack.net (Postfix) with ESMTP id 608D85E47EF for ; Thu, 22 Dec 2005 15:13:50 -0800 (PST) Mime-Version: 1.0 (Apple Message framework v746.2) Content-Transfer-Encoding: 7bit Message-Id: <36D83F22-D5E0-4525-841D-4A03C64C0A19@freebsd.org> Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: freebsd-current@freebsd.org From: Jason Evans Date: Thu, 22 Dec 2005 15:13:47 -0800 X-Mailer: Apple Mail (2.746.2) X-Spam-Checker-Version: SpamAssassin 3.0.4 (2005-06-05) on lh.synack.net X-Spam-Level: * X-Spam-Status: No, score=1.8 required=5.0 tests=RCVD_IN_NJABL_DUL, RCVD_IN_SORBS_DUL autolearn=no version=3.0.4 Subject: Adding RB_NFIND() to sys/tree.h X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 22 Dec 2005 23:13:53 -0000 I'd like to add RB_NFIND() to sys/tree.h, since I need it for the malloc implementation I've been working on. Mark Murray suggested that I ask for comments here before committing. sys/tree.h comes from NetBSD, and up to now, the only changes we've made have been for the purpose of avoiding compiler warnings. RB_NFIND() is like RB_FIND(), but if an exact match isn't found, RB_NFIND() returns the next object in the tree (if there is one). Emulating RB_NFIND() with the existing RB_*() API is possible, but certainly not ideal. I would claim that RB_PFIND() isn't necessary, since it could be easily (if not quite as efficiently) emulated with RB_NFIND(), followed by RB_PREV(). However, there is no RB_PREV(), even though there is RB_NEXT(). This seems to me like an API design oversight (as is the omission of RB_FOREACH_REVERSE()), but it doesn't cause me issues, so I haven't tackled it. A patch follows (manpage changes omitted). Are there any objections to committing this? Thanks, Jason Index: sys/sys/tree.h =================================================================== RCS file: /home/ncvs/src/sys/sys/tree.h,v retrieving revision 1.3 diff -u -r1.3 tree.h --- sys/sys/tree.h 10 Jun 2005 11:44:57 -0000 1.3 +++ sys/sys/tree.h 17 Dec 2005 03:00:01 -0000 @@ -382,6 +382,7 @@ struct type *name##_RB_REMOVE(struct name *, struct type *); \ struct type *name##_RB_INSERT(struct name *, struct type *); \ struct type *name##_RB_FIND(struct name *, struct type *); \ +struct type *name##_RB_NFIND(struct name *, struct type *); \ struct type *name##_RB_NEXT(struct type *); \ struct type *name##_RB_MINMAX(struct name *, int); \ \ @@ -628,6 +629,35 @@ return (NULL); \ } \ \ +/* Finds the first node greater than or equal to the search key */ \ +struct type * \ +name##_RB_NFIND(struct name *head, struct type *elm) \ +{ \ + struct type *ret = RB_ROOT(head); \ + struct type *tmp; \ + int comp; \ + while (ret && (comp = cmp(elm, ret)) != 0) { \ + 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; \ + } \ + } \ + return (ret); \ +} \ + \ /* ARGSUSED */ \ struct type * \ name##_RB_NEXT(struct type *elm) \ @@ -671,6 +701,7 @@ #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) #define RB_FIND(name, x, y) name##_RB_FIND(x, y) +#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) #define RB_NEXT(name, x, y) name##_RB_NEXT(y) #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)