/**
  * Copyright (c): Uwe Schmidt, FH Wedel
  *
  * You may study, modify and distribute this source code
  * FOR NON-COMMERCIAL PURPOSES ONLY.
  * This copyright message has to remain unchanged.
  *
  * Note that this document is provided 'as is',
  * WITHOUT WARRANTY of any kind either expressed or implied.
  */

/* Macros and functions for bitstring processing */

/* these are the basic operations for
   implementing "big-endian patricia trees"
   for efficient maps with unsigned int's as keys
*/

#include <limits.h>

typedef unsigned long int BitString;

/* a Prefix of a BitString is represented
   by a BitString where the least significant
   bits are cleared
*/
typedef BitString Prefix;

/* a Mask (in this context) is a BitString
   with a single bit set. A Mask will be used
   to specify the length of a Prefix. The bit
   position of the mask determined the 1. bit
   not included in the prefix
*/
typedef BitString Mask;

#define LEN_BITSTRING (CHAR_BIT * sizeof (BitString))


#define check(i)         ( (BitString)(i) < LEN_BITSTRING )

#define emptyBitString   ( (BitString)0 )

#define singleton(i)     ( ((BitString)1) << (i) )

/* in a Mask a single bit is set */

#define invMask(m)        ( (m) != emptyBitString \
			    && \
			    ((m) ^ ((m) & (~(m) + 1))) \
                              == emptyBitString \
			  )

/*----------------------------------------*/

extern void printBitString (BitString bs);

extern void printPrefix(Prefix p, Mask m);

/* mask for longest 0-prefix
   basic operation, needed by commonPrefixMask
 */
extern Mask zeroPrefix(BitString bs);

/* faster version of zeroPrefix */
extern Mask zeroPrefixFast(BitString bs);

/* compute common prefix length represented by a mask*/
extern Mask commonPrefixMask(BitString bs1, BitString bs2);

/* get a prefix of a given length (represented by a mask) */
extern Prefix getPrefix(BitString bs, Mask m);

/* compare a prefix of a bitstring with a given prefix */
extern int matchPrefix(BitString bs, Prefix p, Mask m);