From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([208.118.235.92]:39733) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TH4EO-00043p-8U for qemu-devel@nongnu.org; Wed, 26 Sep 2012 22:53:41 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1TH4EN-0002Hh-68 for qemu-devel@nongnu.org; Wed, 26 Sep 2012 22:53:40 -0400 Received: from mx1.redhat.com ([209.132.183.28]:31248) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TH4EM-0002Hc-Tp for qemu-devel@nongnu.org; Wed, 26 Sep 2012 22:53:39 -0400 Received: from int-mx12.intmail.prod.int.phx2.redhat.com (int-mx12.intmail.prod.int.phx2.redhat.com [10.5.11.25]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id q8R2rbvW001494 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Wed, 26 Sep 2012 22:53:38 -0400 Message-ID: <5063BFAE.20707@redhat.com> Date: Wed, 26 Sep 2012 20:53:34 -0600 From: Eric Blake MIME-Version: 1.0 References: <1348675011-8794-1-git-send-email-pbonzini@redhat.com> <1348675011-8794-36-git-send-email-pbonzini@redhat.com> In-Reply-To: <1348675011-8794-36-git-send-email-pbonzini@redhat.com> Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="------------enig89F98A505B6152EA02EE5C20" Subject: Re: [Qemu-devel] [PATCH v2 35/45] add hierarchical bitmap data type and test cases List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Paolo Bonzini Cc: kwolf@redhat.com, jcody@redhat.com, qemu-devel@nongnu.org This is an OpenPGP/MIME signed message (RFC 2440 and 3156) --------------enig89F98A505B6152EA02EE5C20 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable On 09/26/2012 09:56 AM, Paolo Bonzini wrote: > HBitmaps provides an array of bits. The bits are stored as usual in an= > array of unsigned longs, but HBitmap is also optimized to provide fast > iteration over set bits; going from one bit to the next is O(logB n) > worst case, with B =3D sizeof(long) * CHAR_BIT: the result is low enoug= h > that the number of levels is in fact fixed. > +++ b/hbitmap.c > @@ -0,0 +1,400 @@ > +/* > + * Hierarchical Bitmap Data Type > + * > + * Copyright Red Hat, Inc., 2012 vs. > +++ b/tests/test-hbitmap.c > @@ -0,0 +1,408 @@ > +/* > + * Hierarchical bitmap unit-tests. > + * > + * Copyright (C) 2012 Red Hat Inc. Is there a preferred form for the copyright line? > +++ b/hbitmap.h > @@ -0,0 +1,207 @@ > + > +/* We need to place a sentinel in level 0 to speed up iteration. Thus= , > + * we do this instead of HBITMAP_LOG_MAX_SIZE / BITS_PER_LEVEL. The > + * difference is that it allocates an extra level when HBITMAP_LOG_MAX= _SIZE > + * is an exact multiple of BITS_PER_LEVEL. > + */ > +#define HBITMAP_LEVELS ((HBITMAP_LOG_MAX_SIZE / BITS_PER_LEVEL= ) + 1) Comment is a bit misleading. Don't you mean: Thus, we do this instead of (HBITMAP_LOG_MAX_SIZE + BITS_PER_LEVEL - 1)/BITS_PER_LEVEL. (aka ceil(1.0*HBITMAP_LOG_MAX_SIZE / BITS_PER_LEVEL)) --=20 Eric Blake eblake@redhat.com +1-919-301-3266 Libvirt virtualization library http://libvirt.org --------------enig89F98A505B6152EA02EE5C20 Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.12 (GNU/Linux) Comment: Public key at http://people.redhat.com/eblake/eblake.gpg Comment: Using GnuPG with Mozilla - http://www.enigmail.net/ iQEcBAEBCAAGBQJQY7+vAAoJEKeha0olJ0NqHboIAI4tBfyI6p4sb5HUsEFDBPWz AQkJOSEyjcEcCmEVLcbYmBL0fFsETzE+OTE94RWi8I2yIiaiI9LqLnAqMMHGm736 lez+w9ulFjbVkZ/+6rM/KofpbCYUuE3AZWEcDdXQ1NbPk9BMcNq3OVRjaHa6OAS2 JpPya3Z9WWF8pZKNYv9WzUEYWQ7xtZwFtc1OmynHQX6U3gonR82X2ILWgsxuCo7J qWkup+IfiSKtgolsEELSoLoLZI+GRjkdyMpEyiqjiB3r7USZe/yO2yx4k4ofDOhV ELWvB5Cr27mHEf8wGNs7QNYrewTzrRVdyMQpcKSO4YKE42b7NCkfIwd6yqNh/cY= =fQP/ -----END PGP SIGNATURE----- --------------enig89F98A505B6152EA02EE5C20--