From owner-svn-src-all@FreeBSD.ORG Sun Mar 1 04:57:24 2009 Return-Path: Delivered-To: svn-src-all@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 5DEBE106566B; Sun, 1 Mar 2009 04:57:24 +0000 (UTC) (envelope-from bms@FreeBSD.org) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:4f8:fff6::2c]) by mx1.freebsd.org (Postfix) with ESMTP id 30E328FC12; Sun, 1 Mar 2009 04:57:24 +0000 (UTC) (envelope-from bms@FreeBSD.org) Received: from svn.freebsd.org (localhost [127.0.0.1]) by svn.freebsd.org (8.14.3/8.14.3) with ESMTP id n214vO18030950; Sun, 1 Mar 2009 04:57:24 GMT (envelope-from bms@svn.freebsd.org) Received: (from bms@localhost) by svn.freebsd.org (8.14.3/8.14.3/Submit) id n214vODg030949; Sun, 1 Mar 2009 04:57:24 GMT (envelope-from bms@svn.freebsd.org) Message-Id: <200903010457.n214vODg030949@svn.freebsd.org> From: Bruce M Simpson Date: Sun, 1 Mar 2009 04:57:24 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org X-SVN-Group: head MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Cc: Subject: svn commit: r189204 - head/sys/sys X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 01 Mar 2009 04:57:24 -0000 Author: bms Date: Sun Mar 1 04:57:23 2009 New Revision: 189204 URL: http://svn.freebsd.org/changeset/base/189204 Log: In sys/tree.h: * Add RB_FOREACH_FROM() which continues traversal *at* the y-node provided. There is no pre-increment. * Nuke RB_FOREACH_SAFE as it was buggy; it would omit the final node. * Replace RB_FOREACH_SAFE() with a working implementation derived from RB_FOREACH_FROM(). The key observation is that we now only check the loop-control variable, but still cache the next member pointer. * Add RB_FOREACH_REVERSE_FROM() which continues backwards traversal *at* the y-node provided. There is no pre-increment. Typically this is used to back out of allocations made whilst walking an RB-tree. * Add RB_FOREACH_REVERSE_SAFE() which performs insertion and deletion safe backwards traversal. Modified: head/sys/sys/tree.h Modified: head/sys/sys/tree.h ============================================================================== --- head/sys/sys/tree.h Sun Mar 1 04:49:42 2009 (r189203) +++ head/sys/sys/tree.h Sun Mar 1 04:57:23 2009 (r189204) @@ -737,9 +737,14 @@ name##_RB_MINMAX(struct name *head, int (x) != NULL; \ (x) = name##_RB_NEXT(x)) +#define RB_FOREACH_FROM(x, name, y) \ + for ((x) = (y); \ + ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ + (x) = (y)) + #define RB_FOREACH_SAFE(x, name, head, y) \ for ((x) = RB_MIN(name, head); \ - (x) != NULL && ((y) = name##_RB_NEXT(x)); \ + ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ (x) = (y)) #define RB_FOREACH_REVERSE(x, name, head) \ @@ -747,4 +752,14 @@ name##_RB_MINMAX(struct name *head, int (x) != NULL; \ (x) = name##_RB_PREV(x)) +#define RB_FOREACH_REVERSE_FROM(x, name, y) \ + for ((x) = (y); \ + ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ + (x) = (y)) + +#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ + for ((x) = RB_MAX(name, head); \ + ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ + (x) = (y)) + #endif /* _SYS_TREE_H_ */