activemq-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From tab...@apache.org
Subject svn commit: r1152374 - in /activemq/activemq-dotnet/Apache.NMS.ActiveMQ/trunk/src: main/csharp/Util/BitArray.cs main/csharp/Util/BitArrayBin.cs test/csharp/Util/BitArrayBinTest.cs
Date Fri, 29 Jul 2011 21:12:48 GMT
Author: tabish
Date: Fri Jul 29 21:12:47 2011
New Revision: 1152374

URL: http://svn.apache.org/viewvc?rev=1152374&view=rev
Log:
https://issues.apache.org/jira/browse/AMQNET-329

Adds some BitArray classes for use in Message Audit.

Added:
    activemq/activemq-dotnet/Apache.NMS.ActiveMQ/trunk/src/main/csharp/Util/BitArray.cs  
(with props)
    activemq/activemq-dotnet/Apache.NMS.ActiveMQ/trunk/src/main/csharp/Util/BitArrayBin.cs
  (with props)
    activemq/activemq-dotnet/Apache.NMS.ActiveMQ/trunk/src/test/csharp/Util/BitArrayBinTest.cs
  (with props)

Added: activemq/activemq-dotnet/Apache.NMS.ActiveMQ/trunk/src/main/csharp/Util/BitArray.cs
URL: http://svn.apache.org/viewvc/activemq/activemq-dotnet/Apache.NMS.ActiveMQ/trunk/src/main/csharp/Util/BitArray.cs?rev=1152374&view=auto
==============================================================================
--- activemq/activemq-dotnet/Apache.NMS.ActiveMQ/trunk/src/main/csharp/Util/BitArray.cs (added)
+++ activemq/activemq-dotnet/Apache.NMS.ActiveMQ/trunk/src/main/csharp/Util/BitArray.cs Fri
Jul 29 21:12:47 2011
@@ -0,0 +1,129 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+using System;
+
+namespace Apache.NMS.ActiveMQ.Util
+{
+    /// <summary>
+    /// A specialized BitArray implementation that provides the smallest set
+    /// of functionality needed for Message Auditing.  This implementation is
+    /// used over the .NET bit array to provide a small and more efficient
+    /// BitArray that performs only the operations needed for Message Audit.
+    /// </summary>
+    public class BitArray
+    {
+        public const int LONG_SIZE = 64;
+        public const int INT_SIZE = 32;
+        public const int SHORT_SIZE = 16;
+        public const int BYTE_SIZE = 8;
+        private static readonly ulong[] BIT_VALUES = {0x0000000000000001UL, 0x0000000000000002UL,
0x0000000000000004UL,
+                                                      0x0000000000000008UL, 0x0000000000000010UL,
0x0000000000000020UL,
+                                                      0x0000000000000040UL, 0x0000000000000080UL,
0x0000000000000100UL,
+                                                      0x0000000000000200UL, 0x0000000000000400UL,
0x0000000000000800UL,
+                                                      0x0000000000001000UL, 0x0000000000002000UL,
0x0000000000004000UL,
+                                                      0x0000000000008000UL, 0x0000000000010000UL,
0x0000000000020000UL,
+                                                      0x0000000000040000UL, 0x0000000000080000UL,
0x0000000000100000UL,
+                                                      0x0000000000200000UL, 0x0000000000400000UL,
0x0000000000800000UL,
+                                                      0x0000000001000000UL, 0x0000000002000000UL,
0x0000000004000000UL,
+                                                      0x0000000008000000UL, 0x0000000010000000UL,
0x0000000020000000UL,
+                                                      0x0000000040000000UL, 0x0000000080000000UL,
0x0000000100000000UL,
+                                                      0x0000000200000000UL, 0x0000000400000000UL,
0x0000000800000000UL,
+                                                      0x0000001000000000UL, 0x0000002000000000UL,
0x0000004000000000UL,
+                                                      0x0000008000000000UL, 0x0000010000000000UL,
0x0000020000000000UL,
+                                                      0x0000040000000000UL, 0x0000080000000000UL,
0x0000100000000000UL,
+                                                      0x0000200000000000UL, 0x0000400000000000UL,
0x0000800000000000UL,
+                                                      0x0001000000000000UL, 0x0002000000000000UL,
0x0004000000000000UL,
+                                                      0x0008000000000000UL, 0x0010000000000000UL,
0x0020000000000000UL,
+                                                      0x0040000000000000UL, 0x0080000000000000UL,
0x0100000000000000UL,
+                                                      0x0200000000000000UL, 0x0400000000000000UL,
0x0800000000000000UL,
+                                                      0x1000000000000000UL, 0x2000000000000000UL,
0x4000000000000000UL,
+                                                      0x8000000000000000UL};
+        private ulong bits = 0;
+        private int length = 0;
+
+        public BitArray()
+        {
+        }
+
+        public BitArray(long bits)
+        {
+            this.bits = (ulong)bits;
+        }
+
+        /// <summary>
+        /// Returns the current length of the bits that have been
+        /// set so far in this BitArray.
+        /// </summary>
+        public int Length
+        {
+           get { return length; }
+        }
+    
+        /// <summary>
+        /// Returns the actual long value containing all the set bits.
+        /// </summary>
+        public long Bits
+        {
+            get { return (long)bits; }
+        }
+    
+        /// <summary>
+        /// Sets the boolean value of the given bit in the array at the specified index.
+        /// </summary>
+        public bool Set(int index, bool flag)
+        {
+            length = Math.Max(length, index + 1);
+            bool oldValue = (bits & BIT_VALUES[index]) != 0;
+            if (flag)
+            {
+                bits |= BIT_VALUES[index];
+            }
+            else if (oldValue)
+            {
+                bits &= ~(BIT_VALUES[index]);
+            }
+            return oldValue;
+        }
+    
+        /// <summary>
+        /// Get the boolean value contains in the BitArray at the given index
+        /// </summary>
+        public bool Get(int index)
+        {
+            return (bits & BIT_VALUES[index]) != 0;
+        }
+    
+        /// <summary>
+        /// Reset all the bits to zero or false.
+        /// </summary>
+        public void Reset()
+        {
+            bits = 0;
+        }
+
+        /// <summary>
+        /// Reset all the bits to the given value
+        /// </summary>
+        public void Reset(long bits)
+        {
+            this.bits = (ulong)bits;
+        }
+
+    }
+}
+

Propchange: activemq/activemq-dotnet/Apache.NMS.ActiveMQ/trunk/src/main/csharp/Util/BitArray.cs
------------------------------------------------------------------------------
    svn:eol-style = native

Added: activemq/activemq-dotnet/Apache.NMS.ActiveMQ/trunk/src/main/csharp/Util/BitArrayBin.cs
URL: http://svn.apache.org/viewvc/activemq/activemq-dotnet/Apache.NMS.ActiveMQ/trunk/src/main/csharp/Util/BitArrayBin.cs?rev=1152374&view=auto
==============================================================================
--- activemq/activemq-dotnet/Apache.NMS.ActiveMQ/trunk/src/main/csharp/Util/BitArrayBin.cs
(added)
+++ activemq/activemq-dotnet/Apache.NMS.ActiveMQ/trunk/src/main/csharp/Util/BitArrayBin.cs
Fri Jul 29 21:12:47 2011
@@ -0,0 +1,200 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+using System;
+using System.Collections.Generic;
+
+namespace Apache.NMS.ActiveMQ.Util
+{
+    /// <summary>
+    /// Class used to hold BitArray objects for use in Message Audits.
+    /// </summary>
+    public class BitArrayBin
+    {
+        private List<BitArray> list;
+        private int maxNumberOfArrays;
+        private int firstIndex = -1;
+        private long lastInOrderBit = -1;
+
+        public BitArrayBin(int windowSize)
+        {
+            maxNumberOfArrays = ((windowSize + 1) / BitArray.LONG_SIZE) + 1;
+            maxNumberOfArrays = Math.Max(maxNumberOfArrays, 1);
+            list = new List<BitArray>();
+            for (int i = 0; i < maxNumberOfArrays; i++)
+            {
+                list.Add((BitArray)null);
+            }
+        }
+
+        public bool SetBit(long index, bool val)
+        {
+            bool answer = false;
+            BitArray ba = GetBitArray(index);
+            if (ba != null)
+            {
+                int offset = GetOffset(index);
+                if (offset >= 0)
+                {
+                    answer = ba.Get(offset);
+                    ba.Set(offset, val);
+                }
+            }
+            return answer;
+        }
+
+        /// <summary>
+        /// Test if the next message is in order.
+        /// </summary>
+        public bool IsInOrder(long index)
+        {
+            bool result = false;
+            if (lastInOrderBit == -1)
+            {
+                result = true;
+            }
+            else
+            {
+                result = lastInOrderBit + 1 == index;
+            }
+            lastInOrderBit = index;
+            return result;
+    
+        }
+    
+        /**
+         * Get the boolean value at the index
+         * 
+         * @param index
+         * @return true/false
+         */
+        public bool GetBit(long index)
+        {
+            bool answer = index >= firstIndex;
+            BitArray ba = GetBitArray(index);
+            if (ba != null)
+            {
+                int offset = GetOffset(index);
+                if (offset >= 0)
+                {
+                    answer = ba.Get(offset);
+                    return answer;
+                }
+            }
+            else
+            {
+                // gone passed range for previous bins so assume set
+                answer = true;
+            }
+            return answer;
+        }
+    
+        /**
+         * Get the BitArray for the index
+         * 
+         * @param index
+         * @return BitArray
+         */
+        private BitArray GetBitArray(long index)
+        {
+            int bin = GetBin(index);
+            BitArray answer = null;
+            if (bin >= 0)
+            {
+                if (bin >= maxNumberOfArrays)
+                {
+                    int overShoot = bin - maxNumberOfArrays + 1;
+                    while (overShoot > 0)
+                    {
+                        list.RemoveAt(0);
+                        firstIndex += BitArray.LONG_SIZE;
+                        list.Add(new BitArray());
+                        overShoot--;
+                    }
+
+                    bin = maxNumberOfArrays - 1;
+                }
+                answer = list[bin];
+                if (answer == null)
+                {
+                    answer = new BitArray();
+                    list[bin] = answer;
+                }
+            }
+            return answer;
+        }
+
+        /**
+         * Get the index of the bin from the total index
+         * 
+         * @param index
+         * @return the index of the bin
+         */
+        private int GetBin(long index)
+        {
+            int answer = 0;
+            if (firstIndex < 0)
+            {
+                firstIndex = (int) (index - (index % BitArray.LONG_SIZE));
+            }
+            else if (firstIndex >= 0)
+            {
+                answer = (int)((index - firstIndex) / BitArray.LONG_SIZE);
+            }
+            return answer;
+        }
+    
+        /**
+         * Get the offset into a bin from the total index
+         * 
+         * @param index
+         * @return the relative offset into a bin
+         */
+        private int GetOffset(long index)
+        {
+            int answer = 0;
+            if (firstIndex >= 0)
+            {
+                answer = (int)((index - firstIndex) - (BitArray.LONG_SIZE * GetBin(index)));
+            }
+            return answer;
+        }
+    
+        public long GetLastSetIndex()
+        {
+            long result = -1;
+            
+            if (firstIndex >= 0)
+            {
+                result = firstIndex;   
+                BitArray last = null;
+                for (int lastBitArrayIndex = maxNumberOfArrays - 1; lastBitArrayIndex >=
0; lastBitArrayIndex--)
+                {
+                    last = list[lastBitArrayIndex];
+                    if (last != null)
+                    {
+                        result += last.Length - 1;
+                        result += lastBitArrayIndex * BitArray.LONG_SIZE;
+                        break;
+                    }
+                }
+            }
+            return result;
+        }
+    }
+}
+

Propchange: activemq/activemq-dotnet/Apache.NMS.ActiveMQ/trunk/src/main/csharp/Util/BitArrayBin.cs
------------------------------------------------------------------------------
    svn:eol-style = native

Added: activemq/activemq-dotnet/Apache.NMS.ActiveMQ/trunk/src/test/csharp/Util/BitArrayBinTest.cs
URL: http://svn.apache.org/viewvc/activemq/activemq-dotnet/Apache.NMS.ActiveMQ/trunk/src/test/csharp/Util/BitArrayBinTest.cs?rev=1152374&view=auto
==============================================================================
--- activemq/activemq-dotnet/Apache.NMS.ActiveMQ/trunk/src/test/csharp/Util/BitArrayBinTest.cs
(added)
+++ activemq/activemq-dotnet/Apache.NMS.ActiveMQ/trunk/src/test/csharp/Util/BitArrayBinTest.cs
Fri Jul 29 21:12:47 2011
@@ -0,0 +1,188 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+using System;
+using Apache.NMS;
+using Apache.NMS.ActiveMQ;
+using Apache.NMS.ActiveMQ.Util;
+using NUnit.Framework;
+
+namespace Apache.NMS.ActiveMQ.Test
+{
+    [TestFixture]
+    public class BitArrayBinTest
+    {
+        [Test]
+        public void TestSetAroundWindow()
+        {
+            DoTestSetAroundWindow(500, 2000);
+            DoTestSetAroundWindow(512, 2000);
+            DoTestSetAroundWindow(128, 512);
+        }
+
+        [Test]
+        public void TestSetHiLo()
+        {
+            BitArrayBin toTest = new BitArrayBin(50);
+            toTest.SetBit(0, true);
+            toTest.SetBit(100, true);
+            toTest.SetBit(150, true);
+            Assert.IsTrue(toTest.GetBit(0));
+
+            toTest.SetBit(0, true);
+            Assert.IsTrue(toTest.GetBit(0));
+        }
+        
+        private void DoTestSetAroundWindow(int window, int dataSize)
+        {
+            BitArrayBin toTest = new BitArrayBin(window);
+            
+            for (int ix=0; ix <= dataSize; ix++)
+            {
+                Assert.IsTrue(!toTest.SetBit(ix, true), "not already set");
+                Assert.AreEqual(ix, toTest.GetLastSetIndex(), "current is max");
+            }
+    
+            Assert.AreEqual(dataSize, toTest.GetLastSetIndex(), "last is max");
+            
+            int windowOfValidData = RoundWindow(dataSize, window);
+            int i=dataSize;
+            for (; i >= dataSize -windowOfValidData; i--)
+            {
+                Assert.IsTrue(toTest.SetBit(i, true), "was already set, id=" + i);
+            }
+
+            Assert.AreEqual(dataSize, toTest.GetLastSetIndex(), "last is still max");
+            
+            for (; i >= 0; i--)
+            {
+                Assert.IsTrue(!toTest.SetBit(i, true), "was not already set, id=" + i);
+            }
+
+            for (int j= dataSize +1; j<=(2*dataSize); j++)
+            {
+                Assert.IsTrue(!toTest.SetBit(j, true), "not already set: id=" + j);
+            }
+            
+            Assert.AreEqual(2*dataSize, toTest.GetLastSetIndex(), "last still max*2");
+        }
+
+        [Test]
+        public void TestSetUnsetAroundWindow()
+        {
+            DoTestSetUnSetAroundWindow(500, 2000);
+            DoTestSetUnSetAroundWindow(512, 2000);
+            DoTestSetUnSetAroundWindow(128, 512);
+        }
+
+        private void DoTestSetUnSetAroundWindow(int dataSize, int window)
+        {
+            BitArrayBin toTest = new BitArrayBin(window);
+            
+            for (int i=0; i <=dataSize; i++)
+            {
+                Assert.IsTrue(!toTest.SetBit(i, true), "not already set");
+            }
+
+            int windowOfValidData = RoundWindow(dataSize, window);
+            for (int i=dataSize; i >= 0 && i >=dataSize -windowOfValidData;
i--)
+            {
+                Assert.IsTrue(toTest.SetBit(i, false), "was already set, id=" + i);
+            }
+    
+            for (int i=0; i <=dataSize; i++)
+            {
+                Assert.IsTrue(!toTest.SetBit(i, false), "not already set, id:" + i);
+            }
+
+            for (int j= 2*dataSize; j< 4*dataSize; j++)
+            {
+                Assert.IsTrue(!toTest.SetBit(j, true), "not already set: id=" + j);
+            }
+        }
+        
+        [Test]
+        public void TestSetAroundLongSizeMultiplier()
+        {
+            int window = 512;
+            int dataSize = 1000;
+            for (int muliplier=1; muliplier < 8; muliplier++)
+            {
+                for (int i=0; i < dataSize; i++)
+                {
+                    BitArrayBin toTest = new BitArrayBin(window);
+
+                    int instance = i + muliplier * BitArray.LONG_SIZE;
+                    Assert.IsTrue(!toTest.SetBit(instance, true), "not already set: id="
+ instance);
+                    Assert.IsTrue(!toTest.SetBit(i, true), "not already set: id=" + i);
+                    Assert.AreEqual(instance, toTest.GetLastSetIndex(), "max set correct");
+                }
+            }
+        }
+        
+        [Test]
+        public void TestLargeGapInData()
+        {
+            DoTestLargeGapInData(128);
+            DoTestLargeGapInData(500);
+        }
+        
+        private void DoTestLargeGapInData(int window)
+        {
+            BitArrayBin toTest = new BitArrayBin(window);
+            
+            int instance = BitArray.LONG_SIZE;
+            Assert.IsTrue(!toTest.SetBit(instance, true), "not already set: id=" + instance);
+
+            instance = 12 * BitArray.LONG_SIZE;
+            Assert.IsTrue(!toTest.SetBit(instance, true), "not already set: id=" + instance);
+
+            instance = 9 * BitArray.LONG_SIZE;
+            Assert.IsTrue(!toTest.SetBit(instance, true), "not already set: id=" + instance);
+        }
+
+        [Test]
+        public void TestLastSeq()
+        {
+            BitArrayBin toTest = new BitArrayBin(512);
+            Assert.AreEqual(-1, toTest.GetLastSetIndex(), "last not set");
+
+            toTest.SetBit(1, true);
+            Assert.AreEqual(1, toTest.GetLastSetIndex(), "last not correct");
+
+            toTest.SetBit(64, true);
+            Assert.AreEqual(64, toTest.GetLastSetIndex(), "last not correct");
+
+            toTest.SetBit(68, true);
+            Assert.AreEqual(68, toTest.GetLastSetIndex(), "last not correct");
+        }
+    
+        // window moves in increments of BitArrayBin.LONG_SIZE.
+        // valid data window on low end can be larger than window
+        private int RoundWindow(int dataSetEnd, int windowSize)
+        {
+            int validData = dataSetEnd - windowSize;
+            int validDataBin = validData / BitArray.LONG_SIZE;
+            validDataBin += (windowSize % BitArray.LONG_SIZE > 0? 1:0);
+            int startOfValid = validDataBin * BitArray.LONG_SIZE;
+    
+            return dataSetEnd - startOfValid;
+        }
+
+    }
+}
+

Propchange: activemq/activemq-dotnet/Apache.NMS.ActiveMQ/trunk/src/test/csharp/Util/BitArrayBinTest.cs
------------------------------------------------------------------------------
    svn:eol-style = native



Mime
View raw message