vde-2/bitarray.h

   1 /* BITARRAY (C) 2005 Renzo Davoli
   2  * Licensed under the GPLv2
   3  * Modified by Ludovico Gardenghi 2005
   4  *
   5  * A bitarray is (a pointer to) an array of memory words, can be used as a set.
   6  * +--------------------------------+--------------------------------+----
   7  * |33222222222211111111110000000000|66665555555555444444444433333333|999...
   8  * |10987654321098765432109876543210|32109876543210987654321098765432|543...
   9  * +--------------------------------+--------------------------------+----
  10  *
  11  * e.g. bit number 33 is the second LSB of the second word (in a 32 bit machine)
  12  *
  13  * bitarrays must be allocated bu BA_ALLOC
  14  * BA_REALLOC must know the old and the new size of the bitarray
  15  * BA_CHECK checks a bit (returns 0 if cleared, some value != 0 it set)
  16  * BA_SET sets a bit
  17  * BA_CLR clears a bit
  18  * BA_FORALL computes an expression for each set bit,
  19  *           K is an integer var, must be defined in advance.
  20  *           it is the number of the set bit when the expression is evaluated
  21  * BA_FORALLFUN calls a function: first arg the index, second arg is ARG
  22  * BA_CARD counts how many bits are set
  23  *
  24  * BAC_ functions allocate one more trailing word to the bit array to store
  25  * the cardinality of the set (# of set bits).
  26  * This is useful when dealing with large sparse maybe empy sets.
  27  * BAC_SET/CLEAR are slightly more expensive but
  28  * all the FORALL functions shortcut as soon as no more elements can be found.
  29  * If the set is empty the BAC FORALL macros exit immediately.
  30  * *** warning in case of memory leak may loop or segfault if the cardinality is
  31  *     overwritten ***
  32  *
  33  * Macro summary
  34  *
  35  * #define BA_ALLOC(N)
  36  * #define BA_REALLOC(B,N,M)
  37  * #define BA_CHECK(X,I)
  38  * #define BA_SET(X,I)
  39  * #define BA_CLR(X,I)
  40  * #define BA_ZAP(X,N)
  41  * #define BA_FORALLFUN(X,N,F,ARG)
  42  * #define BA_FORALL(X,N,EXPR,K)
  43  * #define BA_CARD(X,N)
  44  * #define BA_EMPTY(X,N)
  45  * #define BA_COPY(DST,SRC,N)     *** MUST HAVE THE SAME SIZE
  46  * #define BA_ADD(DST,SRC,N)      *** MUST HAVE THE SAME SIZE
  47  * #define BA_REMOVE(DST,SRC,N)   *** MUST HAVE THE SAME SIZE
  48  * #define BA_NEGATE(X,N)   *** MUST HAVE THE SAME SIZE
  49  *
  50  * #define BAC_ALLOC(N)
  51  * #define BAC_REALLOC(B,N,M)
  52  * #define BAC_CHECK(X,I)
  53  * #define BAC_SET(X,N,I)
  54  * #define BAC_CLR(X,N,I)
  55  * #define BAC_ZAP(X,N)
  56  * #define BAC_FORALLFUN(X,N,F,ARG)
  57  * #define BAC_FORALL(X,N,EXPR,K)
  58  * #define BAC_CARD(X,N)
  59  * #define BAC_EMPTY(X,N)
  60  * #define BAC_COPY(DST,SRC,N)   *** MUST HAVE THE SAME SIZE
  61  */
  62
  63 #ifndef _BITARRAY_H
  64 #define _BITARRAY_H
  65 #include <stdlib.h>
  66 #include <limits.h>
  67
  68
  69 #if __LONG_MAX__ == 2147483647L                     /* 32 bits */
  70 # define __VDEWORDSIZE 32
  71 # define __LOG_WORDSIZE (5)
  72 # define __WORDSIZEMASK 0x1f
  73 #elif __LONG_MAX__ == 9223372036854775807L          /* 64 bits */
  74 # define __VDEWORDSIZE 64
  75 # define __LOG_WORDSIZE (6)
  76 # define __WORDSIZEMASK 0x3f
  77 #else
  78 # error sorry this program has been tested only on 32 or 64 bit machines
  79 #endif
  80
  81 #define __WORDSIZE_1 (__VDEWORDSIZE-1)
  82 #define __WORDSIZEROUND(VX) ((VX + __WORDSIZE_1) >> __LOG_WORDSIZE)
  83
  84 typedef unsigned long bitarrayelem;
  85 typedef bitarrayelem *bitarray;
  86
  87 /* Simple Bit Array */
  88
  89 #define BA_ALLOC(N) (calloc(__WORDSIZEROUND(N),sizeof(unsigned long)))
  90
  91 #define BA_REALLOC(B,N,M) \
  92         ({ register int __i;\
  93          bitarray nb=realloc((B),__WORDSIZEROUND(M)*sizeof(unsigned long)); \
  94          if(nb != NULL) \
  95          for(__i=__WORDSIZEROUND(N);__i<__WORDSIZEROUND(M);__i++) \
  96          nb[__i]=0; \
  97          nb[__WORDSIZEROUND(N)-1] &= (1<<(((((N)&__WORDSIZEMASK)-1)&0x1f)+1))-1; \
  98          nb;})
  99
 100 #define BA_CHECK(X,I) ((X) && ((X)[(I)>>__LOG_WORDSIZE] & (1 << ((I) & __WORDSIZEMASK))))
 101
 102 #define BA_SET(X,I) ((X)[(I)>>__LOG_WORDSIZE] |= (1 << ((I) & __WORDSIZEMASK)))
 103
 104 #define BA_CLR(X,I) ((X)[(I)>>__LOG_WORDSIZE] &= ~(1 << ((I) & __WORDSIZEMASK)))
 105
 106 #define BA_ZAP(X,N) \
 107         ({ register unsigned int __i; \
 108          int max=__WORDSIZEROUND(N); \
 109          for (__i=0; __i< max; __i++) \
 110          (X)[__i]=0; \
 111          0 ; })
 112
 113 #define BA_FORALLFUN(X,N,F,ARG) \
 114         ({ register unsigned int __i,__j; \
 115          register bitarrayelem __v; \
 116          int max=__WORDSIZEROUND(N); \
 117          for (__i=0; __i< max; __i++) \
 118          for (__v=(X)[__i],__j=0; __j < __VDEWORDSIZE; __v >>=1, __j++) \
 119          if (__v & 1) (F)(__i*__VDEWORDSIZE+__j,(ARG)); \
 120          0; })
 121
 122 #define BA_FORALL(X,N,EXPR,K) \
 123         ({ register unsigned int __i,__j; \
 124          register bitarrayelem __v; \
 125          int max=__WORDSIZEROUND(N); \
 126          for (__i=0; __i< max; __i++) \
 127          for (__v=(X)[__i],__j=0; __j < __VDEWORDSIZE; __v >>=1, __j++) \
 128          if (__v & 1) {(K)=__i*__VDEWORDSIZE+__j;(EXPR);} \
 129          0; })
 130
 131 #define BA_CARD(X,N) \
 132         ({ register unsigned int __i,__j,__n=0; \
 133          register bitarrayelem __v; \
 134          int max=__WORDSIZEROUND(N); \
 135          for (__i=0; __i< max; __i++) \
 136          for (__v=(X)[__i],__j=0; __j < __VDEWORDSIZE; __v >>=1, __j++) \
 137          if (__v & 1) __n++; \
 138          __n; })
 139
 140 #define BA_EMPTY(X,N) \
 141         ({ register unsigned int __i; \
 142          register bitarrayelem __v=0; \
 143          int max=__WORDSIZEROUND(N); \
 144          for (__i=0; __i< max; __i++) \
 145          __v |= (X)[__i]; \
 146          __v; })
 147
 148 #define BA_COPY(DST,SRC,N) memcpy(DST,SRC,sizeof(bitarrayelem) * __WORDSIZEROUND(N))
 149
 150 #define BA_ADD(DST,SRC,N) \
 151         ({ register unsigned int __i; \
 152          int max=__WORDSIZEROUND(N); \
 153          for (__i=0; __i< max; __i++) \
 154          (DST)[__i] |= (SRC)[__i]; \
 155          0; })
 156
 157 #define BA_REMOVE(DST,SRC,N) \
 158         ({ register unsigned int __i; \
 159          int max=__WORDSIZEROUND(N); \
 160          for (__i=0; __i< max; __i++) \
 161          (DST)[__i] &= ~((SRC)[__i]); \
 162          nb[max-1] &= (1<<(((((N)&__WORDSIZEMASK)-1)&0x1f)+1))-1; \
 163          0; })
 164
 165 #define BA_NEGATE(X,N) \
 166         ({ register unsigned int __i; \
 167          int max=__WORDSIZEROUND(N); \
 168          for (__i=0; __i< max; __i++) \
 169          (X)[__i] = ~((X)[__i]); \
 170          nb[max-1] &= (1<<(((((N)&__WORDSIZEMASK)-1)&0x1f)+1))-1; \
 171          0; })
 172
 173 /* Bit Array with Cardinality (Count of set bit) */
 174 /* it is stored after the last element */
 175
 176 #define BAC_ALLOC(N) (calloc(__WORDSIZEROUND(N)+1,sizeof(unsigned long)))
 177
 178 #define BAC_REALLOC(B,N,M) \
 179         ({ register int __i;\
 180          register int __size=(B)[__WORDSIZEROUND(N)]; \
 181          bitarray nb=realloc((B),(__WORDSIZEROUND(M)+1)*sizeof(unsigned long)); \
 182          if(nb != NULL) { \
 183          (B)[__WORDSIZEROUND(M)]=__size; \
 184          for(__i=__WORDSIZEROUND(N);__i<__WORDSIZEROUND(M);__i++) \
 185          nb[__i]=0; }\
 186          nb[__WORDSIZEROUND(N)-1] &= (1<<(((((N)&__WORDSIZEMASK)-1)&0x1f)+1))-1; \
 187          nb;})
 188
 189 /* BA_CHECK and BAC_CHECK are the same */
 190 #define BAC_CHECK(X,I) ((X) && ((X)[(I)>>__LOG_WORDSIZE] & (1 << ((I) & __WORDSIZEMASK))))
 191
 192 #define BAC_SET(X,N,I) \
 193         ({ register int __v=(X)[(I)>>__LOG_WORDSIZE]; \
 194                 register int __w=__v; \
 195                 __v |= (1 << ((I) & __WORDSIZEMASK)); \
 196                 if (__v != __w) (X)[(I)>>__LOG_WORDSIZE]=__v,((X)[__WORDSIZEROUND(N)]++); \
 197                 })
 198
 199 #define BAC_CLR(X,N,I) \
 200         ({ register int __v=(X)[(I)>>__LOG_WORDSIZE]; \
 201          register int __w=__v; \
 202          __v &= ~(1 << ((I) & __WORDSIZEMASK)); \
 203          if (__v != __w) (X)[(I)>>__LOG_WORDSIZE]=__v,((X)[__WORDSIZEROUND(N)]--); \
 204          })
 205
 206 #define BAC_ZAP(X,N) \
 207         ({ register unsigned int __i; \
 208          int max=__WORDSIZEROUND(N); \
 209          for (__i=0; __i< max; __i++) \
 210          (X)[__i]=0; \
 211          (X)[__i]=0; \
 212          0 ; })
 213
 214 #define BAC_FORALLFUN(X,N,F,ARG) \
 215         ({ register unsigned int __i,__j; \
 216          register bitarrayelem __v; \
 217          register int __n=(X)[__WORDSIZEROUND(N)]; \
 218          for (__i=0; __n > 0; __i++) \
 219          for (__v=(X)[__i],__j=0; __j < __VDEWORDSIZE; __v >>=1, __j++) \
 220          if (__v & 1) (F)(__i*__VDEWORDSIZE+__j,(ARG)),__n--; \
 221          0; })
 222
 223 #define BAC_FORALL(X,N,EXPR,K) \
 224         ({ register unsigned int __i,__j; \
 225          register bitarrayelem __v; \
 226          register int __n=(X)[__WORDSIZEROUND(N)]; \
 227          for (__i=0; __n > 0; __i++) \
 228          for (__v=(X)[__i],__j=0; __j < __VDEWORDSIZE; __v >>=1, __j++) \
 229          if (__v & 1) (K)=__i*__VDEWORDSIZE+__j,(EXPR),__n--; \
 230          0; })
 231
 232 #define BAC_CARD(X,N) ((X)[__WORDSIZEROUND(N)])
 233 #define BAC_EMPTY(X,N) ((X)[__WORDSIZEROUND(N)]==0)
 234
 235 #define BAC_COPY(DST,SRC,N) memcpy(DST,SRC,sizeof(bitarrayelem) * (__WORDSIZEROUND(N)+1))
 236
 237 #if 0
 238 /* usage example */
 239 int fun(int i,int arg)
 240 {
 241         printf("I %d\n",i);
 242 }
 243
 244 int main (int argc, char *argv[])
 245 {
 246         bitarray b;
 247         int k;
 248         if (argc != 2) return 0;
 249         int val=atoi(argv[1]);
 250         if (val < 34) return 0;
 251         printf("%d -round-> %d\n",val,__WORDSIZEROUND(val));
 252         b=BA_ALLOC(val);
 253         BA_SET(b,31);
 254         BA_SET(b,33);
 255         printf("%d -> %d\n",31,BA_CHECK(b,31));
 256         printf("%d -> %d\n",33,BA_CHECK(b,33));
 257         printf("CARD %d\n",BA_CARD(b,val));
 258         BA_FORALLFUN(b,val,fun,0);
 259         BA_FORALL(b,val,(printf("E1 %d\n",k)),k);
 260         printf("RE127\n");
 261         b=BA_REALLOC(b,val,127);
 262         BA_FORALL(b,127,(printf("E2 %d\n",k)),k);
 263         printf("RE42\n");
 264         b=BA_REALLOC(b,127,42);
 265         BA_FORALL(b,127,(printf("E3 %d\n",k)),k);
 266         BA_CLR(b,31);
 267         printf("%d -> %d\n",31,BA_CHECK(b,31));
 268         printf("CARD %d\n",BA_CARD(b,42));
 269         BA_CLR(b,33);
 270         printf("%d -> %d\n",33,BA_CHECK(b,33));
 271         printf("CARD %d\n",BA_CARD(b,42));
 272         b=BAC_ALLOC(val);
 273         if (argc != 2) return 0;
 274         printf("%d -> %d\n",val,__WORDSIZEROUND(val));
 275         BAC_SET(b,val,31);
 276         BAC_SET(b,val,33);
 277         printf("%d -> %d\n",31,BAC_CHECK(b,31));
 278         printf("%d -> %d\n",33,BAC_CHECK(b,33));
 279         printf("CARD %d\n",BAC_CARD(b,val));
 280         BAC_FORALLFUN(b,val,fun,0);
 281         BAC_FORALL(b,val,(printf("E1 %d\n",k)),k);
 282         printf("RE127\n");
 283         printf("CARD %d\n",BAC_CARD(b,val));
 284         b=BAC_REALLOC(b,val,127);
 285         BAC_FORALL(b,127,(printf("E2 %d\n",k)),k);
 286         printf("RE42\n");
 287         b=BAC_REALLOC(b,127,42);
 288         BAC_FORALL(b,42,(printf("E3 %d\n",k)),k);
 289         BAC_CLR(b,42,31);
 290         printf("%d -> %d\n",31,BAC_CHECK(b,31));
 291         printf("CARD %d\n",BAC_CARD(b,42));
 292         BAC_CLR(b,42,33);
 293         printf("%d -> %d\n",33,BAC_CHECK(b,33));
 294         printf("CARD %d\n",BAC_CARD(b,val));
 295 }
 296 #endif
 297 #endif