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 #define BA_ALLOC(N) (calloc(__WORDSIZEROUND(N),sizeof(unsigned long)))
  89
  90 #define BA_REALLOC(B,N,M) \
  91         ({ register int __i;\
  92          bitarray nb=realloc((B),__WORDSIZEROUND(M)*sizeof(unsigned long)); \
  93          if(nb != NULL) \
  94          for(__i=__WORDSIZEROUND(N);__i<__WORDSIZEROUND(M);__i++) \
  95          nb[__i]=0; \
  96          nb[__WORDSIZEROUND(N)-1] &= (1<<(((((N)&__WORDSIZEMASK)-1)&0x1f)+1))-1; \
  97          (B)=nb;})
  98
  99 #define BA_CHECK(X,I) ((X) && ((X)[(I)>>__LOG_WORDSIZE] & (1 << ((I) & __WORDSIZEMASK))))
 100
 101 #define BA_SET(X,I) ((X)[(I)>>__LOG_WORDSIZE] |= (1 << ((I) & __WORDSIZEMASK)))
 102
 103 #define BA_CLR(X,I) ((X)[(I)>>__LOG_WORDSIZE] &= ~(1 << ((I) & __WORDSIZEMASK)))
 104
 105 #define BA_ZAP(X,N) \
 106         ({ register unsigned int __i; \
 107          int max=__WORDSIZEROUND(N); \
 108          for (__i=0; __i< max; __i++) \
 109          (X)[__i]=0; \
 110          0 ; })
 111
 112 #define BA_FORALLFUN(X,N,F,ARG) \
 113         ({ register unsigned int __i,__j; \
 114          register bitarrayelem __v; \
 115          int max=__WORDSIZEROUND(N); \
 116          for (__i=0; __i< max; __i++) \
 117          for (__v=(X)[__i],__j=0; __j < __VDEWORDSIZE; __v >>=1, __j++) \
 118          if (__v & 1) (F)(__i*__VDEWORDSIZE+__j,(ARG)); \
 119          0; })
 120
 121 #define BA_FORALL(X,N,EXPR,K) \
 122         ({ register unsigned int __i,__j; \
 123          register bitarrayelem __v; \
 124          int max=__WORDSIZEROUND(N); \
 125          for (__i=0; __i< max; __i++) \
 126          for (__v=(X)[__i],__j=0; __j < __VDEWORDSIZE; __v >>=1, __j++) \
 127          if (__v & 1) {(K)=__i*__VDEWORDSIZE+__j;(EXPR);} \
 128          0; })
 129
 130 #define BA_CARD(X,N) \
 131         ({ register unsigned int __i,__j,__n=0; \
 132          register bitarrayelem __v; \
 133          int max=__WORDSIZEROUND(N); \
 134          for (__i=0; __i< max; __i++) \
 135          for (__v=(X)[__i],__j=0; __j < __VDEWORDSIZE; __v >>=1, __j++) \
 136          if (__v & 1) __n++; \
 137          __n; })
 138
 139 #define BA_EMPTY(X,N) \
 140         ({ register unsigned int __i; \
 141          register bitarrayelem __v=0; \
 142          int max=__WORDSIZEROUND(N); \
 143          for (__i=0; __i< max; __i++) \
 144          __v |= (X)[__i]; \
 145          __v; })
 146
 147 #define BA_COPY(DST,SRC,N) memcpy(DST,SRC,sizeof(bitarrayelem) * __WORDSIZEROUND(N))
 148
 149 #define BA_ADD(DST,SRC,N) \
 150         ({ register unsigned int __i; \
 151          int max=__WORDSIZEROUND(N); \
 152          for (__i=0; __i< max; __i++) \
 153          (DST)[__i] |= (SRC)[__i]; \
 154          0; })
 155
 156 #define BA_REMOVE(DST,SRC,N) \
 157         ({ register unsigned int __i; \
 158          int max=__WORDSIZEROUND(N); \
 159          for (__i=0; __i< max; __i++) \
 160          (DST)[__i] &= ~((SRC)[__i]); \
 161          nb[max-1] &= (1<<(((((N)&__WORDSIZEMASK)-1)&0x1f)+1))-1; \
 162          0; })
 163
 164 #define BA_NEGATE(X,N) \
 165         ({ register unsigned int __i; \
 166          int max=__WORDSIZEROUND(N); \
 167          for (__i=0; __i< max; __i++) \
 168          (X)[__i] = ~((X)[__i]); \
 169          nb[max-1] &= (1<<(((((N)&__WORDSIZEMASK)-1)&0x1f)+1))-1; \
 170          0; })
 171
 172 /* Bit Array with Cardinality (Count of set bit) */
 173 /* it is stored after the last element */
 174
 175 #define BAC_ALLOC(N) (calloc(__WORDSIZEROUND(N)+1,sizeof(unsigned long)))
 176
 177 #define BAC_REALLOC(B,N,M) \
 178         ({ register int __i;\
 179          register int __size=(B)[__WORDSIZEROUND(N)]; \
 180          bitarray nb=realloc((B),(__WORDSIZEROUND(M)+1)*sizeof(unsigned long)); \
 181          if(nb != NULL) { \
 182          (B)[__WORDSIZEROUND(M)]=__size; \
 183          for(__i=__WORDSIZEROUND(N);__i<__WORDSIZEROUND(M);__i++) \
 184          nb[__i]=0; }\
 185          nb[__WORDSIZEROUND(N)-1] &= (1<<(((((N)&__WORDSIZEMASK)-1)&0x1f)+1))-1; \
 186          (B)=nb;})
 187
 188 /* BA_CHECK and BAC_CHECK are the same */
 189 #define BAC_CHECK(X,I) ((X) && ((X)[(I)>>__LOG_WORDSIZE] & (1 << ((I) & __WORDSIZEMASK))))
 190
 191 #define BAC_SET(X,N,I) \
 192         ({ register int __v=(X)[(I)>>__LOG_WORDSIZE]; \
 193                 register int __w=__v; \
 194                 __v |= (1 << ((I) & __WORDSIZEMASK)); \
 195                 if (__v != __w) (X)[(I)>>__LOG_WORDSIZE]=__v,((X)[__WORDSIZEROUND(N)]++); \
 196                 })
 197
 198 #define BAC_CLR(X,N,I) \
 199         ({ register int __v=(X)[(I)>>__LOG_WORDSIZE]; \
 200          register int __w=__v; \
 201          __v &= ~(1 << ((I) & __WORDSIZEMASK)); \
 202          if (__v != __w) (X)[(I)>>__LOG_WORDSIZE]=__v,((X)[__WORDSIZEROUND(N)]--); \
 203          })
 204
 205 #define BAC_ZAP(X,N) \
 206         ({ register unsigned int __i; \
 207          int max=__WORDSIZEROUND(N); \
 208          for (__i=0; __i< max; __i++) \
 209          (X)[__i]=0; \
 210          (X)[__i]=0; \
 211          0 ; })
 212
 213 #define BAC_FORALLFUN(X,N,F,ARG) \
 214         ({ register unsigned int __i,__j; \
 215          register bitarrayelem __v; \
 216          register int __n=(X)[__WORDSIZEROUND(N)]; \
 217          for (__i=0; __n > 0; __i++) \
 218          for (__v=(X)[__i],__j=0; __j < __VDEWORDSIZE; __v >>=1, __j++) \
 219          if (__v & 1) (F)(__i*__VDEWORDSIZE+__j,(ARG)),__n--; \
 220          0; })
 221
 222 #define BAC_FORALL(X,N,EXPR,K) \
 223         ({ register unsigned int __i,__j; \
 224          register bitarrayelem __v; \
 225          register int __n=(X)[__WORDSIZEROUND(N)]; \
 226          for (__i=0; __n > 0; __i++) \
 227          for (__v=(X)[__i],__j=0; __j < __VDEWORDSIZE; __v >>=1, __j++) \
 228          if (__v & 1) (K)=__i*__VDEWORDSIZE+__j,(EXPR),__n--; \
 229          0; })
 230
 231 #define BAC_CARD(X,N) ((X)[__WORDSIZEROUND(N)])
 232 #define BAC_EMPTY(X,N) ((X)[__WORDSIZEROUND(N)]==0)
 233
 234 #define BAC_COPY(DST,SRC,N) memcpy(DST,SRC,sizeof(bitarrayelem) * __WORDSIZEROUND(N))
 235
 236 #if 0
 237 /* usage example */
 238 int fun(int i,int arg)
 239 {
 240         printf("I %d\n",i);
 241 }
 242
 243 int main (int argc, char *argv[])
 244 {
 245         bitarray b;
 246         int k;
 247         if (argc != 2) return 0;
 248         int val=atoi(argv[1]);
 249         if (val < 34) return 0;
 250         printf("%d -round-> %d\n",val,__WORDSIZEROUND(val));
 251         b=BA_ALLOC(val);
 252         BA_SET(b,31);
 253         BA_SET(b,33);
 254         printf("%d -> %d\n",31,BA_CHECK(b,31));
 255         printf("%d -> %d\n",33,BA_CHECK(b,33));
 256         printf("CARD %d\n",BA_CARD(b,val));
 257         BA_FORALLFUN(b,val,fun,0);
 258         BA_FORALL(b,val,(printf("E1 %d\n",k)),k);
 259         printf("RE127\n");
 260         b=BA_REALLOC(b,val,127);
 261         BA_FORALL(b,127,(printf("E2 %d\n",k)),k);
 262         printf("RE42\n");
 263         b=BA_REALLOC(b,127,42);
 264         BA_FORALL(b,127,(printf("E3 %d\n",k)),k);
 265         BA_CLR(b,31);
 266         printf("%d -> %d\n",31,BA_CHECK(b,31));
 267         printf("CARD %d\n",BA_CARD(b,42));
 268         BA_CLR(b,33);
 269         printf("%d -> %d\n",33,BA_CHECK(b,33));
 270         printf("CARD %d\n",BA_CARD(b,42));
 271         b=BAC_ALLOC(val);
 272         if (argc != 2) return 0;
 273         printf("%d -> %d\n",val,__WORDSIZEROUND(val));
 274         BAC_SET(b,val,31);
 275         BAC_SET(b,val,33);
 276         printf("%d -> %d\n",31,BAC_CHECK(b,31));
 277         printf("%d -> %d\n",33,BAC_CHECK(b,33));
 278         printf("CARD %d\n",BAC_CARD(b,val));
 279         BAC_FORALLFUN(b,val,fun,0);
 280         BAC_FORALL(b,val,(printf("E1 %d\n",k)),k);
 281         printf("RE127\n");
 282         printf("CARD %d\n",BAC_CARD(b,val));
 283         b=BAC_REALLOC(b,val,127);
 284         BAC_FORALL(b,127,(printf("E2 %d\n",k)),k);
 285         printf("RE42\n");
 286         b=BAC_REALLOC(b,127,42);
 287         BAC_FORALL(b,42,(printf("E3 %d\n",k)),k);
 288         BAC_CLR(b,42,31);
 289         printf("%d -> %d\n",31,BAC_CHECK(b,31));
 290         printf("CARD %d\n",BAC_CARD(b,42));
 291         BAC_CLR(b,42,33);
 292         printf("%d -> %d\n",33,BAC_CHECK(b,33));
 293         printf("CARD %d\n",BAC_CARD(b,val));
 294 }
 295 #endif
 296 #endif