/* BITARRAY (C) 2005 Renzo Davoli
* Licensed under the GPLv2
* Modified by Ludovico Gardenghi 2005
*
* A bitarray is (a pointer to) an array of memory words, can be used as a set.
* +--------------------------------+--------------------------------+----
* |33222222222211111111110000000000|66665555555555444444444433333333|999...
* |10987654321098765432109876543210|32109876543210987654321098765432|543...
* +--------------------------------+--------------------------------+----
*
* e.g. bit number 33 is the second LSB of the second word (in a 32 bit machine)
*
* bitarrays must be allocated bu BA_ALLOC
* BA_REALLOC must know the old and the new size of the bitarray
* BA_CHECK checks a bit (returns 0 if cleared, some value != 0 it set)
* BA_SET sets a bit
* BA_CLR clears a bit
* BA_FORALL computes an expression for each set bit,
* K is an integer var, must be defined in advance.
* it is the number of the set bit when the expression is evaluated
* BA_FORALLFUN calls a function: first arg the index, second arg is ARG
* BA_CARD counts how many bits are set
*
* BAC_ functions allocate one more trailing word to the bit array to store
* the cardinality of the set (# of set bits).
* This is useful when dealing with large sparse maybe empy sets.
* BAC_SET/CLEAR are slightly more expensive but
* all the FORALL functions shortcut as soon as no more elements can be found.
* If the set is empty the BAC FORALL macros exit immediately.
* *** warning in case of memory leak may loop or segfault if the cardinality is
* overwritten ***
*
* Macro summary
*
* #define BA_ALLOC(N)
* #define BA_REALLOC(B,N,M)
* #define BA_CHECK(X,I)
* #define BA_SET(X,I)
* #define BA_CLR(X,I)
* #define BA_ZAP(X,N)
* #define BA_FORALLFUN(X,N,F,ARG)
* #define BA_FORALL(X,N,EXPR,K)
* #define BA_CARD(X,N)
* #define BA_EMPTY(X,N)
* #define BA_COPY(DST,SRC,N) *** MUST HAVE THE SAME SIZE
* #define BA_ADD(DST,SRC,N) *** MUST HAVE THE SAME SIZE
* #define BA_REMOVE(DST,SRC,N) *** MUST HAVE THE SAME SIZE
* #define BA_NEGATE(X,N) *** MUST HAVE THE SAME SIZE
*
* #define BAC_ALLOC(N)
* #define BAC_REALLOC(B,N,M)
* #define BAC_CHECK(X,I)
* #define BAC_SET(X,N,I)
* #define BAC_CLR(X,N,I)
* #define BAC_ZAP(X,N)
* #define BAC_FORALLFUN(X,N,F,ARG)
* #define BAC_FORALL(X,N,EXPR,K)
* #define BAC_CARD(X,N)
* #define BAC_EMPTY(X,N)
* #define BAC_COPY(DST,SRC,N) *** MUST HAVE THE SAME SIZE
*/
#ifndef _BITARRAY_H
#define _BITARRAY_H
#include <stdlib.h>
#include <limits.h>
#if __LONG_MAX__ == 2147483647L /* 32 bits */
# define __VDEWORDSIZE 32
# define __LOG_WORDSIZE (5)
# define __WORDSIZEMASK 0x1f
#elif __LONG_MAX__ == 9223372036854775807L /* 64 bits */
# define __VDEWORDSIZE 64
# define __LOG_WORDSIZE (6)
# define __WORDSIZEMASK 0x3f
#else
# error sorry this program has been tested only on 32 or 64 bit machines
#endif
#define __WORDSIZE_1 (__VDEWORDSIZE-1)
#define __WORDSIZEROUND(VX) ((VX + __WORDSIZE_1) >> __LOG_WORDSIZE)
typedef unsigned long bitarrayelem;
typedef bitarrayelem *bitarray;
/* Simple Bit Array */
#define BA_ALLOC(N) (calloc(__WORDSIZEROUND(N),sizeof(unsigned long)))
#define BA_REALLOC(B,N,M) \
({ register int __i;\
bitarray nb=realloc((B),__WORDSIZEROUND(M)*sizeof(unsigned long)); \
if(nb != NULL) \
for(__i=__WORDSIZEROUND(N);__i<__WORDSIZEROUND(M);__i++) \
nb[__i]=0; \
nb[__WORDSIZEROUND(N)-1] &= (1<<(((((N)&__WORDSIZEMASK)-1)&0x1f)+1))-1; \
(B)=nb;})
#define BA_CHECK(X,I) ((X) && ((X)[(I)>>__LOG_WORDSIZE] & (1 << ((I) & __WORDSIZEMASK))))
#define BA_SET(X,I) ((X)[(I)>>__LOG_WORDSIZE] |= (1 << ((I) & __WORDSIZEMASK)))
#define BA_CLR(X,I) ((X)[(I)>>__LOG_WORDSIZE] &= ~(1 << ((I) & __WORDSIZEMASK)))
#define BA_ZAP(X,N) \
({ register unsigned int __i; \
int max=__WORDSIZEROUND(N); \
for (__i=0; __i< max; __i++) \
(X)[__i]=0; \
0 ; })
#define BA_FORALLFUN(X,N,F,ARG) \
({ register unsigned int __i,__j; \
register bitarrayelem __v; \
int max=__WORDSIZEROUND(N); \
for (__i=0; __i< max; __i++) \
for (__v=(X)[__i],__j=0; __j < __VDEWORDSIZE; __v >>=1, __j++) \
if (__v & 1) (F)(__i*__VDEWORDSIZE+__j,(ARG)); \
0; })
#define BA_FORALL(X,N,EXPR,K) \
({ register unsigned int __i,__j; \
register bitarrayelem __v; \
int max=__WORDSIZEROUND(N); \
for (__i=0; __i< max; __i++) \
for (__v=(X)[__i],__j=0; __j < __VDEWORDSIZE; __v >>=1, __j++) \
if (__v & 1) {(K)=__i*__VDEWORDSIZE+__j;(EXPR);} \
0; })
#define BA_CARD(X,N) \
({ register unsigned int __i,__j,__n=0; \
register bitarrayelem __v; \
int max=__WORDSIZEROUND(N); \
for (__i=0; __i< max; __i++) \
for (__v=(X)[__i],__j=0; __j < __VDEWORDSIZE; __v >>=1, __j++) \
if (__v & 1) __n++; \
__n; })
#define BA_EMPTY(X,N) \
({ register unsigned int __i; \
register bitarrayelem __v=0; \
int max=__WORDSIZEROUND(N); \
for (__i=0; __i< max; __i++) \
__v |= (X)[__i]; \
__v; })
#define BA_COPY(DST,SRC,N) memcpy(DST,SRC,sizeof(bitarrayelem) * __WORDSIZEROUND(N))
#define BA_ADD(DST,SRC,N) \
({ register unsigned int __i; \
int max=__WORDSIZEROUND(N); \
for (__i=0; __i< max; __i++) \
(DST)[__i] |= (SRC)[__i]; \
0; })
#define BA_REMOVE(DST,SRC,N) \
({ register unsigned int __i; \
int max=__WORDSIZEROUND(N); \
for (__i=0; __i< max; __i++) \
(DST)[__i] &= ~((SRC)[__i]); \
nb[max-1] &= (1<<(((((N)&__WORDSIZEMASK)-1)&0x1f)+1))-1; \
0; })
#define BA_NEGATE(X,N) \
({ register unsigned int __i; \
int max=__WORDSIZEROUND(N); \
for (__i=0; __i< max; __i++) \
(X)[__i] = ~((X)[__i]); \
nb[max-1] &= (1<<(((((N)&__WORDSIZEMASK)-1)&0x1f)+1))-1; \
0; })
/* Bit Array with Cardinality (Count of set bit) */
/* it is stored after the last element */
#define BAC_ALLOC(N) (calloc(__WORDSIZEROUND(N)+1,sizeof(unsigned long)))
#define BAC_REALLOC(B,N,M) \
({ register int __i;\
register int __size=(B)[__WORDSIZEROUND(N)]; \
bitarray nb=realloc((B),(__WORDSIZEROUND(M)+1)*sizeof(unsigned long)); \
if(nb != NULL) { \
(B)[__WORDSIZEROUND(M)]=__size; \
for(__i=__WORDSIZEROUND(N);__i<__WORDSIZEROUND(M);__i++) \
nb[__i]=0; }\
nb[__WORDSIZEROUND(N)-1] &= (1<<(((((N)&__WORDSIZEMASK)-1)&0x1f)+1))-1; \
(B)=nb;})
/* BA_CHECK and BAC_CHECK are the same */
#define BAC_CHECK(X,I) ((X) && ((X)[(I)>>__LOG_WORDSIZE] & (1 << ((I) & __WORDSIZEMASK))))
#define BAC_SET(X,N,I) \
({ register int __v=(X)[(I)>>__LOG_WORDSIZE]; \
register int __w=__v; \
__v |= (1 << ((I) & __WORDSIZEMASK)); \
if (__v != __w) (X)[(I)>>__LOG_WORDSIZE]=__v,((X)[__WORDSIZEROUND(N)]++); \
})
#define BAC_CLR(X,N,I) \
({ register int __v=(X)[(I)>>__LOG_WORDSIZE]; \
register int __w=__v; \
__v &= ~(1 << ((I) & __WORDSIZEMASK)); \
if (__v != __w) (X)[(I)>>__LOG_WORDSIZE]=__v,((X)[__WORDSIZEROUND(N)]--); \
})
#define BAC_ZAP(X,N) \
({ register unsigned int __i; \
int max=__WORDSIZEROUND(N); \
for (__i=0; __i< max; __i++) \
(X)[__i]=0; \
(X)[__i]=0; \
0 ; })
#define BAC_FORALLFUN(X,N,F,ARG) \
({ register unsigned int __i,__j; \
register bitarrayelem __v; \
register int __n=(X)[__WORDSIZEROUND(N)]; \
for (__i=0; __n > 0; __i++) \
for (__v=(X)[__i],__j=0; __j < __VDEWORDSIZE; __v >>=1, __j++) \
if (__v & 1) (F)(__i*__VDEWORDSIZE+__j,(ARG)),__n--; \
0; })
#define BAC_FORALL(X,N,EXPR,K) \
({ register unsigned int __i,__j; \
register bitarrayelem __v; \
register int __n=(X)[__WORDSIZEROUND(N)]; \
for (__i=0; __n > 0; __i++) \
for (__v=(X)[__i],__j=0; __j < __VDEWORDSIZE; __v >>=1, __j++) \
if (__v & 1) (K)=__i*__VDEWORDSIZE+__j,(EXPR),__n--; \
0; })
#define BAC_CARD(X,N) ((X)[__WORDSIZEROUND(N)])
#define BAC_EMPTY(X,N) ((X)[__WORDSIZEROUND(N)]==0)
#define BAC_COPY(DST,SRC,N) memcpy(DST,SRC,sizeof(bitarrayelem) * __WORDSIZEROUND(N))
#if 0
/* usage example */
int fun(int i,int arg)
{
printf("I %d\n",i);
}
int main (int argc, char *argv[])
{
bitarray b;
int k;
if (argc != 2) return 0;
int val=atoi(argv[1]);
if (val < 34) return 0;
printf("%d -round-> %d\n",val,__WORDSIZEROUND(val));
b=BA_ALLOC(val);
BA_SET(b,31);
BA_SET(b,33);
printf("%d -> %d\n",31,BA_CHECK(b,31));
printf("%d -> %d\n",33,BA_CHECK(b,33));
printf("CARD %d\n",BA_CARD(b,val));
BA_FORALLFUN(b,val,fun,0);
BA_FORALL(b,val,(printf("E1 %d\n",k)),k);
printf("RE127\n");
b=BA_REALLOC(b,val,127);
BA_FORALL(b,127,(printf("E2 %d\n",k)),k);
printf("RE42\n");
b=BA_REALLOC(b,127,42);
BA_FORALL(b,127,(printf("E3 %d\n",k)),k);
BA_CLR(b,31);
printf("%d -> %d\n",31,BA_CHECK(b,31));
printf("CARD %d\n",BA_CARD(b,42));
BA_CLR(b,33);
printf("%d -> %d\n",33,BA_CHECK(b,33));
printf("CARD %d\n",BA_CARD(b,42));
b=BAC_ALLOC(val);
if (argc != 2) return 0;
printf("%d -> %d\n",val,__WORDSIZEROUND(val));
BAC_SET(b,val,31);
BAC_SET(b,val,33);
printf("%d -> %d\n",31,BAC_CHECK(b,31));
printf("%d -> %d\n",33,BAC_CHECK(b,33));
printf("CARD %d\n",BAC_CARD(b,val));
BAC_FORALLFUN(b,val,fun,0);
BAC_FORALL(b,val,(printf("E1 %d\n",k)),k);
printf("RE127\n");
printf("CARD %d\n",BAC_CARD(b,val));
b=BAC_REALLOC(b,val,127);
BAC_FORALL(b,127,(printf("E2 %d\n",k)),k);
printf("RE42\n");
b=BAC_REALLOC(b,127,42);
BAC_FORALL(b,42,(printf("E3 %d\n",k)),k);
BAC_CLR(b,42,31);
printf("%d -> %d\n",31,BAC_CHECK(b,31));
printf("CARD %d\n",BAC_CARD(b,42));
BAC_CLR(b,42,33);
printf("%d -> %d\n",33,BAC_CHECK(b,33));
printf("CARD %d\n",BAC_CARD(b,val));
}
#endif
#endif
syntax highlighted by Code2HTML, v. 0.9.1