Sunday, July 31, 2016

Cyclicbarrier for C++ multi-threaded programs

Java has very good concurrency support and a very good library providing useful classes for multi-threaded programming. One such class is CyclicBarrier.
From Javadoc, CyclicBarrier is:
A synchronization aid that allows a set of threads to all wait for each other to reach a common barrier point. CyclicBarriers are useful in programs involving a fixed sized party of threads that must occasionally wait for each other. The barrier is called cyclic because it can be re-used after the waiting threads are released. 

C++ standard library lacks this utility. This is not a problem anyway as pthread_barrier routines (pthread_barrier_wait, pthread_barrier_init etc.) exactly do the same and we may always use pthread library for multi-threaded programming in C++ and Pthread library provides much more control on how we use the threads. But C++11 has multi-threading built into the language (and on Linux platform G++ internally uses Pthreads only) and so it would have been nice if a cyclicbarrier like construct was part of C++ library itself.

So, I spent some time building a library that provides silmilar functionality as the Java CyclicBarrier class. which is accessible at github. There is an example program demonstrating how to use it. May be you like to use it.

Wednesday, July 27, 2016

Bitset data structure in Golang

I have created a Library for bitset where each bit can be treated as a boolean value. The library is accessible here. It's a thread-safe library (or rather a goroutine safe library) and can be happily used from multiple goroutines concurrently. It has many features like get, set, xor, end, clone etc. The API documentation for the library is accessible here.

I have created this library as I need similar functionalities in the distributed cache (geetcache) project I am currently working on. It helps me to serialize-deserialize the hyperlogs data types in a compact manner. An example usage is given below:


package main

import (
 "fmt"
 "github.com/nipuntalukdar/bitset"
)

func main() {
 bs := bitset.NewBitset(8)
 if bs.IsAllZero() {
  fmt.Printf("All bits are set to zero\n")
 }
 bs.Flip(60)
 fmt.Printf("Number of ones %d\n", bs.GetSetbitCount())
 fmt.Printf("Number of zeros %d\n", bs.GetZerobitCount())
 bs = bitset.NewBitset(10000)
 fmt.Printf("Number of ones %d\n", bs.GetSetbitCount())
 fmt.Printf("Number of zeros %d\n", bs.GetZerobitCount())
}

A more detailed example is given below:


package main

import (
 "fmt"
 "github.com/nipuntalukdar/bitset"
)

func main() {
 bs := bitset.NewBitset(80)
 if bs.IsAllZero() {
  fmt.Printf("All bits are set to zero\n")
 }
 bs.Flip(60)
 fmt.Printf("Number of ones %d\n", bs.GetSetbitCount())
 fmt.Printf("Number of zeros %d\n", bs.GetZerobitCount())
 bs.SetBit(9)
 ret, err := bs.IsSet(9)
 if err != nil || !ret {
  fmt.Printf("Some issue\n")
 }

 bs.SetVal(1, 10, 511)
 recvd, err := bs.GetByte(0)
 if err == nil {
  fmt.Printf("First byte in the underlying array %d\n", recvd)
 }

 // set bytes 6,7,8 to zero and don't touch other bits
 bs.SetVal(6, 8, 0)

 // Clear all the bits, or make them all zero
 bs.ClearAll()

 // Set all the bits to 1
 bs.SetAll()

 // Flip 10th bit
 bs.Flip(10)
 recvd, _ = bs.GetByte(10)
 fmt.Printf("The 10 th byte %d\n", recvd)

 // Get a copy of underlying bytes of the bitset
 bytes := bs.GetBytes()
 fmt.Printf("The first four bytes in the bitset %v\n", bytes[0:4])

 // Flip all the bits
 bs.FlipRange(1, 639)

 // Set the bits 20,21,....,39,40 to 1
 bs.SetRange(20, 40)

 // Set the bits from 20,21,22,....,79,80 to zero
 bs.ClearRange(20, 80)

 other1 := bitset.NewBitset(4)
 other1.SetAll()
 bs.Xor(other1)

 other2 := bitset.NewBitset(10)
 other2.SetRange(40, 60)
 bs.And(other2)
 bs.ResetBit(80)

 // Get next zero bit position after index 0
 indx, _ := bs.GetNextZeroBit(0)
 fmt.Printf("Index of next zero bit %d\n", indx)

 // Get the zero bit before bit 80
 indx, _ = bs.GetPrevSetBit(80)

 // Get the bits from 10 to 28 packed in an uint32
 retuint32, _ := bs.GetVal(10, 28)
 fmt.Printf("The packed uint32 returned is %d\n", retuint32)
}