You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@activemq.apache.org by ta...@apache.org on 2011/07/29 23:12:48 UTC
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
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