[Mono-dev] BitVector32 patch

[Scott Peterson]

I happened across a mention of the BitVector32 class the yesterday and it
piqued my interest. I thought I'd take a look at Mono's implementation and
ended up spending some time giving the type a once-over. I made several
minor changes (style issues, removing duplicate code between the
Section.ToString overrides, simplified Section.GetHashCode, code sharing
between the BitVector32 constructors, &c.), I got rid of the NumberOfSetBits
since it is only every being used on bit masks which are always one less
than a power of two so HighestSetBit can be used instead, and lastly I
changed the HighestSetBit algorithm to something simpler. Patch is attached
and inline. Notes are welcome.

Index: class/System/System.Collections.Specialized/ChangeLog
===================================================================
--- class/System/System.Collections.Specialized/ChangeLog    (revision
109665)
+++ class/System/System.Collections.Specialized/ChangeLog    (working copy)
@@ -1,3 +1,9 @@
+2008-08-06  Scott Peterson  <lunchtimemama at gmail.com>
+
+    * BitVector32.cs: Cleanup and improved a number of things. Simpler
+    HighestSetBit algorithm, got rid of NumberOfSetBits (using
+    HighestSetBit works just fine) and some misc. other stuff.
+
 2008-07-31  Jb Evain  <jbevain at novell.com>

     * StringDictionary.cs: remove ComponentModel bits for NET_2_1.
Index: class/System/System.Collections.Specialized/BitVector32.cs
===================================================================
--- class/System/System.Collections.Specialized/BitVector32.cs    (revision
109665)
+++ class/System/System.Collections.Specialized/BitVector32.cs    (working
copy)
@@ -34,10 +34,10 @@

 namespace System.Collections.Specialized {

-    public struct BitVector32 {
-        int bits;
-
-        public struct Section {
+    public struct BitVector32
+    {
+        public struct Section
+        {
             private short mask;
             private short offset;

@@ -74,7 +74,7 @@
 #endif
             public override bool Equals (object o)
             {
-                if (! (o is Section))
+                if (!(o is Section))
                     return false;

                 Section section = (Section) o;
@@ -84,14 +84,12 @@

             public override int GetHashCode ()
             {
-                return (((Int16) mask).GetHashCode () << 16) +
-                       ((Int16) offset).GetHashCode ();
+                return mask << offset;
             }

             public override string ToString ()
             {
-                return "Section{0x" + Convert.ToString(mask, 16) +
-                       ", 0x" + Convert.ToString(offset, 16) + "}";
+                return ToString(this);
             }

             public static string ToString (Section value)
@@ -106,12 +104,14 @@
                 return b.ToString ();
             }
         }
+
+        int bits;

         // Constructors

         public BitVector32 (BitVector32 source)
+            : this (source.bits)
         {
-            bits = source.bits;
         }

         public BitVector32 (int init)
@@ -184,9 +184,8 @@
             if (maxValue < 1)
                 throw new ArgumentException ("maxValue");

-            int bit = HighestSetBit(maxValue) + 1;
-            int mask = (1 << bit) - 1;
-            int offset = previous.Offset + NumberOfSetBits (previous.Mask);
+            int mask = (1 << HighestSetBit(maxValue)) - 1;
+            int offset = previous.Offset + HighestSetBit(previous.Mask);

             if (offset > 32) {
                 throw new ArgumentException ("Sections cannot exceed 32
bits in total");
@@ -197,10 +196,7 @@

         public override bool Equals (object o)
         {
-            if (!(o is BitVector32))
-                return false;
-
-            return bits == ((BitVector32) o).bits;
+            return (o is BitVector32) && bits == ((BitVector32) o).bits;
         }

         public override int GetHashCode ()
@@ -218,7 +214,7 @@
             StringBuilder b = new StringBuilder ();
             b.Append ("BitVector32{");
             long mask = (long) 0x80000000;
-            while (mask > 0) {
+            while (mask != 0) {
                 b.Append (((value.bits & mask) == 0) ? '0' : '1');
                 mask >>= 1;
             }
@@ -227,27 +223,12 @@
         }

         // Private utilities
-        private static int NumberOfSetBits (int i)
+        private static int HighestSetBit (int i)
         {
             int count = 0;
-            for (int bit = 0; bit < 32; bit++) {
-                int mask = 1 << bit;
-                if ((i & mask) != 0)
-                    count++;
-            }
+            while(i >> count != 0)
+                count++;
             return count;
         }
-
-        private static int HighestSetBit (int i)
-        {
-            for (int bit = 31; bit >= 0; bit--) {
-                int mask = 1 << bit;
-                if ((mask & i) != 0) {
-                    return bit;
-                }
-            }
-
-            return -1;
-        }
     }
 }
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.ximian.com/pipermail/mono-devel-list/attachments/20080806/3dbe2a2c/attachment-0001.html 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: bitvector32.patch
Type: text/x-diff
Size: 3622 bytes
Desc: not available
Url : http://lists.ximian.com/pipermail/mono-devel-list/attachments/20080806/3dbe2a2c/attachment-0001.bin