Skip to content

Instantly share code, notes, and snippets.

@mratsim

mratsim/FenwickTreeBitmap32.cs

Forked from anonymous/FenwickTreeBitmap32.cs
Created January 2, 2020 23:46
Show Gist options
  • Save mratsim/33fba87db796951e3c35fa7e7aeb78b6 to your computer and use it in GitHub Desktop.
Save mratsim/33fba87db796951e3c35fa7e7aeb78b6 to your computer and use it in GitHub Desktop.
Download ZIP
A Fenwick tree for slot usage tracking of 32 slots in a 64 bit bitmap
Raw
FenwickTreeBitmap32.cs
namespace TryOuts
{
using System;
using System.Diagnostics;
using System.Runtime.CompilerServices;
/// <summary>
/// Tracker for usage of a block of 32 consecutive slots. Implemented as a
/// Fenwick tree with indexing optimized for queries. Encodes this
/// information into a long (64 bit) value, while leaving the high bit
/// unused, so that this bit may be used as a marker.
/// </summary>
class FenwickTreeBitmap32
{
public static long CreateFrom(int bitMap)
{
var usageMap = 0L;
var i = 0;
var bmp = (uint)bitMap;
while (bmp != 0)
{
if ((bmp & 1) == 1)
{
AddValueAtIndex(ref usageMap, i, 1);
int j = i + ((i + 1) & -(i + 1));
for (; j < 32; j += ((j + 1) & -(j + 1)))
AddValueAtIndex(ref usageMap, j, 1);
}
bmp >>= 1;
i++;
}
return usageMap;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int TotalUsedSlots(long usageMap)
{
return GetValueAtIndex(usageMap, 63);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void MarkUsed(ref long usageMap, int slotIndex)
{
Debug.Assert(slotIndex >= 0 && slotIndex < 32);
for (; slotIndex < 32; slotIndex += (slotIndex + 1) & -(slotIndex + 1))
AddValueAtIndex(ref usageMap, slotIndex, 1);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void MarkFree(ref long usageMap, int slotIndex)
{
Debug.Assert(slotIndex >= 0 && slotIndex < 32);
for (; slotIndex < 32; slotIndex += (slotIndex + 1) & -(slotIndex + 1))
AddValueAtIndex(ref usageMap, slotIndex, -1);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int NumberOfSlotsUsedUpTo(long usageMap, int slotIndex)
{
Debug.Assert(slotIndex < 32);
var sum = 0;
for (; slotIndex >= 0; slotIndex -= (slotIndex + 1) & -(slotIndex + 1))
sum += GetValueAtIndex(usageMap, slotIndex);
return sum;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int NumberOfSlotsFreeUpTo(long usageMap, int slotIndex)
{
Debug.Assert(slotIndex < 32);
var sum = 0;
for (; slotIndex >= 0; slotIndex -= (slotIndex + 1) & -(slotIndex + 1))
sum += GetComplementValueAtIndex(usageMap, slotIndex);
return sum;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int NumberOfSlotsUsedInRange(long usageMap, int firstSlotIndex, int lastSlotIndex)
{
return NumberOfSlotsUsedUpTo(usageMap, lastSlotIndex) - NumberOfSlotsUsedUpTo(usageMap, firstSlotIndex - 1);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int NumberOfSlotsFreeInRange(long usageMap, int firstSlotIndex, int lastSlotIndex)
{
return NumberOfSlotsFreeUpTo(usageMap, lastSlotIndex) - NumberOfSlotsFreeUpTo(usageMap, firstSlotIndex - 1);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static bool IsUsed(long usageMap, int slotIndex)
{
Debug.Assert(slotIndex < 32);
return NumberOfSlotsUsedUpTo(usageMap, slotIndex) - NumberOfSlotsUsedUpTo(usageMap, slotIndex - 1) == 1;
}
static void AddValueAtIndex(ref long usageMap, int index, int value)
{
Debug.Assert(Math.Abs(value) <= 32);
Debug.Assert(index >= 0 && index < 32);
// Switch is bit faster than table lookup for
// offset & mask, thus this long switch statement.
// compiler will make this a jump table
switch (index)
{
case 0:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, 1);
usageMap += value; // must be 1 or -1;
break;
case 1:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, (3 + 1) >> 1);
usageMap = (usageMap & ~(3L << 1)) | ((((usageMap >> 1) & 3) + value) << 1);
break;
case 2:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, 1);
usageMap = (usageMap & ~(1L << 3)) | ((((usageMap >> 3) & 1) + value) << 3);
break;
case 3:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, (7 + 1) >> 1);
usageMap = (usageMap & ~(7L << 4)) | ((((usageMap >> 4) & 7) + value) << 4);
break;
case 4:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, 1);
usageMap = (usageMap & ~(1L << 7)) | ((((usageMap >> 7) & 1) + value) << 7);
break;
case 5:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, (3 + 1) >> 1);
usageMap = (usageMap & ~(3L << 8)) | ((((usageMap >> 8) & 3) + value) << 8);
break;
case 6:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, 1);
usageMap = (usageMap & ~(1L << 10)) | ((((usageMap >> 10) & 1) + value) << 10);
break;
case 7:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, (15 + 1) >> 1);
usageMap = (usageMap & ~(15L << 11)) | ((((usageMap >> 11) & 15) + value) << 11);
break;
case 8:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, 1);
usageMap = (usageMap & ~(1L << 15)) | ((((usageMap >> 15) & 1) + value) << 15);
break;
case 9:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, (3 + 1) >> 1);
usageMap = (usageMap & ~(3L << 16)) | ((((usageMap >> 16) & 3) + value) << 16);
break;
case 10:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, 1);
usageMap = (usageMap & ~(1L << 18)) | ((((usageMap >> 18) & 1) + value) << 18);
break;
case 11:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, (7 + 1) >> 1);
usageMap = (usageMap & ~(7L << 19)) | ((((usageMap >> 19) & 7) + value) << 19);
break;
case 12:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, 1);
usageMap = (usageMap & ~(1L << 22)) | ((((usageMap >> 22) & 1) + value) << 22);
break;
case 13:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, (3 + 1) >> 1);
usageMap = (usageMap & ~(3L << 23)) | ((((usageMap >> 23) & 3) + value) << 23);
break;
case 14:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, 1);
usageMap = (usageMap & ~(1L << 25)) | ((((usageMap >> 25) & 1) + value) << 25);
break;
case 15:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, (31 + 1) >> 1);
usageMap = (usageMap & ~(31L << 26)) | ((((usageMap >> 26) & 31) + value) << 26);
break;
case 16:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, 1);
usageMap = (usageMap & ~(1L << 31)) | ((((usageMap >> 31) & 1) + value) << 31);
break;
case 17:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, (3 + 1) >> 1);
usageMap = (usageMap & ~(3L << 32)) | ((((usageMap >> 32) & 3) + value) << 32);
break;
case 18:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, 1);
usageMap = (usageMap & ~(1L << 34)) | ((((usageMap >> 34) & 1) + value) << 34);
break;
case 19:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, (7 + 1) >> 1);
usageMap = (usageMap & ~(7L << 35)) | ((((usageMap >> 35) & 7) + value) << 35);
break;
case 20:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, 1);
usageMap = (usageMap & ~(1L << 38)) | ((((usageMap >> 38) & 1) + value) << 38);
break;
case 21:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, (3 + 1) >> 1);
usageMap = (usageMap & ~(3L << 39)) | ((((usageMap >> 39) & 3) + value) << 39);
break;
case 22:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, 1);
usageMap = (usageMap & ~(1L << 41)) | ((((usageMap >> 41) & 1) + value) << 41);
break;
case 23:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, (15 + 1) >> 1);
usageMap = (usageMap & ~(15L << 42)) | ((((usageMap >> 42) & 15) + value) << 42);
break;
case 24:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, 1);
usageMap = (usageMap & ~(1L << 46)) | ((((usageMap >> 46) & 1) + value) << 46);
break;
case 25:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, (3 + 1) >> 1);
usageMap = (usageMap & ~(3L << 47)) | ((((usageMap >> 47) & 3) + value) << 47);
break;
case 26:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, 1);
usageMap = (usageMap & ~(1L << 49)) | ((((usageMap >> 49) & 1) + value) << 49);
break;
case 27:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, (7 + 1) >> 1);
usageMap = (usageMap & ~(7L << 50)) | ((((usageMap >> 50) & 7) + value) << 50);
break;
case 28:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, 1);
usageMap = (usageMap & ~(1L << 53)) | ((((usageMap >> 53) & 1) + value) << 53);
break;
case 29:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, (3 + 1) >> 1);
usageMap = (usageMap & ~(3L << 54)) | ((((usageMap >> 54) & 3) + value) << 54);
break;
case 30:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, 1);
usageMap = (usageMap & ~(1L << 56)) | ((((usageMap >> 56) & 1) + value) << 56);
break;
case 31:
AssertNewValueInRange(GetValueAtIndex(usageMap, index) + value, (63 + 1) >> 1);
usageMap = (usageMap & ~(63L << 57)) | ((((usageMap >> 57) & 63) + value) << 57);
break;
default:
throw new ArgumentOutOfRangeException("index", "Index must be in the range [0-31]");
}
}
private static int GetValueAtIndex(long usageMap, int index)
{
Debug.Assert(index >= 0 && index < 32);
// Switch is bit faster than table lookup for
// offset & mask, thus this long switch statement.
// compiler will make this a jump table
switch (index)
{
case 0:
return unchecked((int)(usageMap & 1));
case 1:
return unchecked((int)((usageMap >> 1) & 3));
case 2:
return unchecked((int)((usageMap >> 3) & 1));
case 3:
return unchecked((int)((usageMap >> 4) & 7));
case 4:
return unchecked((int)((usageMap >> 7) & 1));
case 5:
return unchecked((int)((usageMap >> 8) & 3));
case 6:
return unchecked((int)((usageMap >> 10) & 1));
case 7:
return unchecked((int)((usageMap >> 11) & 15));
case 8:
return unchecked((int)((usageMap >> 15) & 1));
case 9:
return unchecked((int)((usageMap >> 16) & 3));
case 10:
return unchecked((int)((usageMap >> 18) & 1));
case 11:
return unchecked((int)((usageMap >> 19) & 7));
case 12:
return unchecked((int)((usageMap >> 22) & 1));
case 13:
return unchecked((int)((usageMap >> 23) & 3));
case 14:
return unchecked((int)((usageMap >> 25) & 1));
case 15:
return unchecked((int)((usageMap >> 26) & 31));
case 16:
return unchecked((int)((usageMap >> 31) & 1));
case 17:
return unchecked((int)((usageMap >> 32) & 3));
case 18:
return unchecked((int)((usageMap >> 34) & 1));
case 19:
return unchecked((int)((usageMap >> 35) & 7));
case 20:
return unchecked((int)((usageMap >> 38) & 1));
case 21:
return unchecked((int)((usageMap >> 39) & 3));
case 22:
return unchecked((int)((usageMap >> 41) & 1));
case 23:
return unchecked((int)((usageMap >> 42) & 15));
case 24:
return unchecked((int)((usageMap >> 46) & 1));
case 25:
return unchecked((int)((usageMap >> 47) & 3));
case 26:
return unchecked((int)((usageMap >> 49) & 1));
case 27:
return unchecked((int)((usageMap >> 50) & 7));
case 28:
return unchecked((int)((usageMap >> 53) & 1));
case 29:
return unchecked((int)((usageMap >> 54) & 3));
case 30:
return unchecked((int)((usageMap >> 56) & 1));
case 31:
return unchecked((int)((usageMap >> 57) & 63));
default:
throw new ArgumentOutOfRangeException("index", "Index must be in the range [0-31]");
}
}
private static int GetComplementValueAtIndex(long usageMap, int index)
{
Debug.Assert(index >= 0 && index < 32);
// Switch is bit faster than table lookup for
// offset & mask, thus this long switch statement.
// compiler will make this a jump table
switch (index)
{
case 0:
return (1 << 0) - unchecked((int)(usageMap & 1));
case 1:
return (1 << 1) - unchecked((int)((usageMap >> 1) & 3));
case 2:
return (1 << 0) - unchecked((int)((usageMap >> 3) & 1));
case 3:
return (1 << 2) - unchecked((int)((usageMap >> 4) & 7));
case 4:
return (1 << 0) - unchecked((int)((usageMap >> 7) & 1));
case 5:
return (1 << 1) - unchecked((int)((usageMap >> 8) & 3));
case 6:
return (1 << 0) - unchecked((int)((usageMap >> 10) & 1));
case 7:
return (1 << 3) - unchecked((int)((usageMap >> 11) & 15));
case 8:
return (1 << 0) - unchecked((int)((usageMap >> 15) & 1));
case 9:
return (1 << 1) - unchecked((int)((usageMap >> 16) & 3));
case 10:
return (1 << 0) - unchecked((int)((usageMap >> 18) & 1));
case 11:
return (1 << 2) - unchecked((int)((usageMap >> 19) & 7));
case 12:
return (1 << 0) - unchecked((int)((usageMap >> 22) & 1));
case 13:
return (1 << 1) - unchecked((int)((usageMap >> 23) & 3));
case 14:
return (1 << 0) - unchecked((int)((usageMap >> 25) & 1));
case 15:
return (1 << 4) - unchecked((int)((usageMap >> 26) & 31));
case 16:
return (1 << 0) - unchecked((int)((usageMap >> 31) & 1));
case 17:
return (1 << 1) - unchecked((int)((usageMap >> 32) & 3));
case 18:
return (1 << 0) - unchecked((int)((usageMap >> 34) & 1));
case 19:
return (1 << 2) - unchecked((int)((usageMap >> 35) & 7));
case 20:
return (1 << 0) - unchecked((int)((usageMap >> 38) & 1));
case 21:
return (1 << 1) - unchecked((int)((usageMap >> 39) & 3));
case 22:
return (1 << 0) - unchecked((int)((usageMap >> 41) & 1));
case 23:
return (1 << 3) - unchecked((int)((usageMap >> 42) & 15));
case 24:
return (1 << 0) - unchecked((int)((usageMap >> 46) & 1));
case 25:
return (1 << 1) - unchecked((int)((usageMap >> 47) & 3));
case 26:
return (1 << 0) - unchecked((int)((usageMap >> 49) & 1));
case 27:
return (1 << 2) - unchecked((int)((usageMap >> 50) & 7));
case 28:
return (1 << 0) - unchecked((int)((usageMap >> 53) & 1));
case 29:
return (1 << 1) - unchecked((int)((usageMap >> 54) & 3));
case 30:
return (1 << 0) - unchecked((int)((usageMap >> 56) & 1));
case 31:
return (1 << 5) - unchecked((int)((usageMap >> 57) & 63));
default:
throw new ArgumentOutOfRangeException("index", "Index must be in the range [0-31]");
}
}
[Conditional("DEBUG")]
private static void AssertNewValueInRange(int newValue, int maxValue)
{
Debug.Assert(newValue >= 0);
Debug.Assert(newValue <= maxValue);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment