From owner-svn-src-all@freebsd.org Wed Aug 26 02:07:48 2020 Return-Path: Delivered-To: svn-src-all@mailman.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.nyi.freebsd.org (Postfix) with ESMTP id 0EE4A3C5C94; Wed, 26 Aug 2020 02:07:48 +0000 (UTC) (envelope-from scottph@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "Let's Encrypt Authority X3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4Bbq4z546Sz4W2v; Wed, 26 Aug 2020 02:07:47 +0000 (UTC) (envelope-from scottph@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 91A95BD9A; Wed, 26 Aug 2020 02:07:47 +0000 (UTC) (envelope-from scottph@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id 07Q27lvX027823; Wed, 26 Aug 2020 02:07:47 GMT (envelope-from scottph@FreeBSD.org) Received: (from scottph@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id 07Q27lDH027822; Wed, 26 Aug 2020 02:07:47 GMT (envelope-from scottph@FreeBSD.org) Message-Id: <202008260207.07Q27lDH027822@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: scottph set sender to scottph@FreeBSD.org using -f From: D Scott Phillips Date: Wed, 26 Aug 2020 02:07:47 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r364796 - in head: share/man/man9 sys/sys X-SVN-Group: head X-SVN-Commit-Author: scottph X-SVN-Commit-Paths: in head: share/man/man9 sys/sys X-SVN-Commit-Revision: 364796 X-SVN-Commit-Repository: base MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.33 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: Wed, 26 Aug 2020 02:07:48 -0000 Author: scottph Date: Wed Aug 26 02:07:46 2020 New Revision: 364796 URL: https://svnweb.freebsd.org/changeset/base/364796 Log: bitset: add BIT_FFS_AT() for finding the first bit set greater than a start bit Reviewed by: kib Approved by: scottl (implicit) MFC after: 1 week Sponsored by: Ampere Computing, Inc. Differential Revision: https://reviews.freebsd.org/D26128 Modified: head/share/man/man9/bitset.9 head/sys/sys/bitset.h Modified: head/share/man/man9/bitset.9 ============================================================================== --- head/share/man/man9/bitset.9 Wed Aug 26 02:05:58 2020 (r364795) +++ head/share/man/man9/bitset.9 Wed Aug 26 02:07:46 2020 (r364796) @@ -24,7 +24,7 @@ .\" .\" $FreeBSD$ .\" -.Dd December 12, 2019 +.Dd August 25, 2020 .Dt BITSET 9 .Os .Sh NAME @@ -43,6 +43,7 @@ .Nm BIT_EMPTY , .Nm BIT_ISFULLSET , .Nm BIT_FFS , +.Nm BIT_FFS_AT , .Nm BIT_FLS , .Nm BIT_COUNT , .Nm BIT_SUBSET , @@ -86,6 +87,8 @@ .Ft int .Fn BIT_FFS "const SETSIZE" "struct STRUCTNAME *bitset" .Ft int +.Fn BIT_FFS_AT "const SETSIZE" "struct STRUCTNAME *bitset" "int start" +.Ft int .Fn BIT_FLS "const SETSIZE" "struct STRUCTNAME *bitset" .Ft int .Fn BIT_COUNT "const SETSIZE" "struct STRUCTNAME *bitset" @@ -285,6 +288,18 @@ index parameter to any other macro, you must subtract one from the result. .Pp The +.Fn BIT_FFS_AT +macro returns the 1-index of the first (lowest) set bit in +.Fa bitset , +which is greater than the given 1-indexed +.Fa start , +or zero if no bits in +.Fa bitset +greater than +.Fa start +are set. +.Pp +The .Fn BIT_FLS macro returns the 1-index of the last (highest) set bit in .Fa bitset , @@ -518,7 +533,8 @@ argument to all of these macros must match the value g .Fn BITSET_DEFINE . .Pp Unlike every other reference to individual set members, which are zero-indexed, -.Fn BIT_FFS +.Fn BIT_FFS , +.Fn BIT_FFS_AT and .Fn BIT_FLS return a one-indexed result (or zero if the set is empty). Modified: head/sys/sys/bitset.h ============================================================================== --- head/sys/sys/bitset.h Wed Aug 26 02:05:58 2020 (r364795) +++ head/sys/sys/bitset.h Wed Aug 26 02:07:46 2020 (r364796) @@ -207,20 +207,31 @@ (f)->__bits[__i]); \ } while (0) -#define BIT_FFS(_s, p) __extension__ ({ \ +/* + * Note that `start` and the returned value from BIT_FFS_AT are + * 1-based bit indices. + */ +#define BIT_FFS_AT(_s, p, start) __extension__ ({ \ __size_t __i; \ + long __mask; \ int __bit; \ \ + __mask = ~0UL << ((start) % _BITSET_BITS); \ __bit = 0; \ - for (__i = 0; __i < __bitset_words((_s)); __i++) { \ - if ((p)->__bits[__i] != 0) { \ - __bit = ffsl((p)->__bits[__i]); \ + for (__i = __bitset_word((_s), (start)); \ + __i < __bitset_words((_s)); \ + __i++) { \ + if (((p)->__bits[__i] & __mask) != 0) { \ + __bit = ffsl((p)->__bits[__i] & __mask); \ __bit += __i * _BITSET_BITS; \ break; \ } \ + __mask = ~0UL; \ } \ __bit; \ }) + +#define BIT_FFS(_s, p) BIT_FFS_AT((_s), (p), 0) #define BIT_FLS(_s, p) __extension__ ({ \ __size_t __i; \