vde-2/src/vde_switch/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)
  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 #include <string.h>
  68
  69
  70 #if __LONG_MAX__ == 2147483647L                     /* 32 bits */
  71 # define __VDEWORDSIZE 32
  72 # define __LOG_WORDSIZE (5)
  73 # define __WORDSIZEMASK 0x1f
  74 #elif __LONG_MAX__ == 9223372036854775807L          /* 64 bits */
  75 # define __VDEWORDSIZE 64
  76 # define __LOG_WORDSIZE (6)
  77 # define __WORDSIZEMASK 0x3f
  78 #else
  79 # error sorry this program has been tested only on 32 or 64 bit machines
  80 #endif
  81
  82 #define __WORDSIZE_1 (__VDEWORDSIZE-1)
  83 #define __WORDSIZEROUND(VX) ((VX + __WORDSIZE_1) >> __LOG_WORDSIZE)
  84
  85 typedef unsigned long bitarrayelem;
  86 typedef bitarrayelem *bitarray;
  87
  88 /* Simple Bit Array */
  89
  90 static inline bitarray ba_alloc(int n)
  91 {
  92         return calloc(__WORDSIZEROUND(n),sizeof(unsigned long));
  93 }
  94
  95 static inline bitarray ba_realloc(bitarray b,int n,int m)
  96 {
  97         int __i;
  98         bitarray nb=realloc(b,__WORDSIZEROUND(m)*sizeof(unsigned long));
  99         if(nb != NULL)
 100                 for(__i=__WORDSIZEROUND(n);__i<__WORDSIZEROUND(m);__i++)
 101                         nb[__i]=0;
 102         nb[__WORDSIZEROUND(n)-1] &= (-1UL) >>((0U-(n))%__VDEWORDSIZE);
 103         return nb;
 104 }
 105
 106 static inline int ba_check(bitarray x,int i)
 107 {
 108         return (x && (x[i>>__LOG_WORDSIZE] & (1L << (i & __WORDSIZEMASK))));
 109 }
 110
 111 static inline void ba_set(bitarray x,int i)
 112 {
 113         x[i>>__LOG_WORDSIZE] |= (1L << (i & __WORDSIZEMASK));
 114 }
 115
 116 static inline void ba_clr(bitarray x,int i)
 117 {
 118         x[i>>__LOG_WORDSIZE] &= ~(1L << (i & __WORDSIZEMASK));
 119 }
 120
 121 static inline void ba_zap(bitarray x,int n)
 122 {
 123         unsigned int __i;
 124         int max=__WORDSIZEROUND(n);
 125         for (__i=0; __i< max; __i++)
 126                 x[__i]=0;
 127 }
 128
 129 #define ba_FORALLFUN(X,N,F,ARG) \
 130         ({ unsigned int __i,__j; \
 131          bitarrayelem __v; \
 132          int max=__WORDSIZEROUND(N); \
 133          for (__i=0; __i< max; __i++) \
 134          for (__v=(X)[__i],__j=0; __j < __VDEWORDSIZE; __v >>=1, __j++) \
 135          if (__v & 1) (F)(__i*__VDEWORDSIZE+__j,(ARG)); \
 136          0; })
 137
 138 #define ba_FORALL(X,N,EXPR,K) \
 139         ({ unsigned int __i,__j; \
 140          bitarrayelem __v; \
 141          int max=__WORDSIZEROUND(N); \
 142          for (__i=0; __i< max; __i++) \
 143          for (__v=(X)[__i],__j=0; __j < __VDEWORDSIZE; __v >>=1, __j++) \
 144          if (__v & 1) {(K)=__i*__VDEWORDSIZE+__j;(EXPR);} \
 145          (K); })
 146
 147 static inline int ba_card(bitarray x,int n)
 148 {
 149         unsigned int __i,__j,__n=0;
 150         bitarrayelem __v;
 151         int max=__WORDSIZEROUND(n);
 152         for (__i=0; __i< max; __i++)
 153                 for (__v=(x)[__i],__j=0; __j < __VDEWORDSIZE; __v >>=1, __j++)
 154                         if (__v & 1) __n++;
 155          return __n;
 156 }
 157
 158 static inline void ba_empty(bitarray x,int n)
 159 {
 160         unsigned int __i;
 161         bitarrayelem __v=0;
 162         int max=__WORDSIZEROUND(n);
 163         for (__i=0; __i< max; __i++)
 164                 __v |= (x)[__i]; \
 165 }
 166
 167 static inline void ba_copy(bitarray dst, bitarray src, int n)
 168 {
 169         memcpy(dst,src,sizeof(bitarrayelem) * __WORDSIZEROUND(n));
 170 }
 171
 172 static inline void ba_add(bitarray dst, bitarray src, int n)
 173 {
 174         unsigned int __i;
 175         int max=__WORDSIZEROUND(n);
 176         for (__i=0; __i< max; __i++)
 177                 dst[__i] |= src[__i];
 178 }
 179
 180 static inline void ba_remove(bitarray dst, bitarray src, int n)
 181 {
 182         unsigned int __i;
 183         int max=__WORDSIZEROUND(n);
 184         for (__i=0; __i< max; __i++)
 185                 dst[__i] &= ~(src[__i]);
 186 }
 187
 188 static inline void ba_negate(bitarray x, int n)
 189 {
 190         unsigned int __i;
 191         int max=__WORDSIZEROUND(n);
 192         for (__i=0; __i< max; __i++)
 193                 x[__i] = ~(x[__i]);
 194 }
 195
 196 /* Bit Array with Cardinality (Count of set bits) */
 197 /* it is stored after the last element */
 198
 199 static inline bitarray bac_alloc(int n)
 200 {
 201         return calloc(__WORDSIZEROUND(n)+1,sizeof(unsigned long));
 202 }
 203
 204 static inline bitarray bac_realloc(bitarray b,int n,int m)
 205 {
 206         int __i;
 207         int __size=b[__WORDSIZEROUND(n)];
 208         bitarray nb=realloc(b,(__WORDSIZEROUND(m)+1)*sizeof(unsigned long));
 209         if(nb != NULL) {
 210                 b[__WORDSIZEROUND(m)]=__size;
 211                 for(__i=__WORDSIZEROUND(n);__i<__WORDSIZEROUND(n);__i++)
 212                         nb[__i]=0;
 213         }
 214         nb[__WORDSIZEROUND(n)-1] &= (-1UL) >>((0U-n)%__VDEWORDSIZE);
 215         return nb;
 216 }
 217
 218 /* ba_check and bac_check are the same */
 219 static inline int bac_check(bitarray x,int i)
 220 {
 221         return (x && (x[i>>__LOG_WORDSIZE] & (1L << (i & __WORDSIZEMASK))));
 222 }
 223
 224 static inline void bac_set(bitarray x,int n,int i)
 225 {
 226         bitarrayelem __v=x[i>>__LOG_WORDSIZE];
 227         bitarrayelem __w=__v;
 228         __v |= (1L << (i & __WORDSIZEMASK));
 229         if (__v != __w) x[i>>__LOG_WORDSIZE]=__v,(x[__WORDSIZEROUND(n)]++);
 230 }
 231
 232 static inline void bac_clr(bitarray x,int n,int i)
 233 {
 234         bitarrayelem __v=x[i>>__LOG_WORDSIZE];
 235         bitarrayelem __w=__v;
 236         __v &= ~(1L << (i & __WORDSIZEMASK));
 237         if (__v != __w) x[i>>__LOG_WORDSIZE]=__v,(x[__WORDSIZEROUND(n)]--);
 238 }
 239
 240 static inline void bac_zap(bitarray x,int n)
 241 {
 242         unsigned int __i;
 243                 int max=__WORDSIZEROUND(n);
 244          for (__i=0; __i< max; __i++)
 245                  x[__i]=0;
 246          x[__i]=0;
 247 }
 248
 249 #define bac_FORALLFUN(X,N,F,ARG) \
 250         ({ unsigned int __i,__j; \
 251          bitarrayelem __v; \
 252          int __n=(X)[__WORDSIZEROUND(N)]; \
 253          for (__i=0; __n > 0; __i++) \
 254          for (__v=(X)[__i],__j=0; __j < __VDEWORDSIZE; __v >>=1, __j++) \
 255          if (__v & 1) (F)(__i*__VDEWORDSIZE+__j,(ARG)),__n--; \
 256          0; })
 257
 258 #define bac_FORALL(X,N,EXPR,K) \
 259         ({ unsigned int __i,__j; \
 260          bitarrayelem __v; \
 261          int __n=(X)[__WORDSIZEROUND(N)]; \
 262          for (__i=0; __n > 0; __i++) \
 263          for (__v=(X)[__i],__j=0; __j < __VDEWORDSIZE; __v >>=1, __j++) \
 264          if (__v & 1) (K)=__i*__VDEWORDSIZE+__j,(EXPR),__n--; \
 265          0; })
 266
 267 static inline int bac_card(bitarray x,int n)
 268 {
 269         return(x[__WORDSIZEROUND(n)]);
 270 }
 271
 272 static inline int bac_empty(bitarray x,int n)
 273 {
 274         return(x[__WORDSIZEROUND(n)]==0);
 275 }
 276
 277 static inline void bac_copy(bitarray dst, bitarray src, int n)
 278 {
 279         memcpy(dst,src,sizeof(bitarrayelem) * (__WORDSIZEROUND(n)+1));
 280 }
 281
 282 #if 0
 283 #include <stdio.h>
 284 /* usage example */
 285 int fun(int i,int arg)
 286 {
 287         printf("I %d\n",i);
 288 }
 289
 290 int main (int argc, char *argv[])
 291 {
 292         bitarray b;
 293         int k;
 294         if (argc != 2) return 0;
 295         int val=atoi(argv[1]);
 296         if (val < 34) return 0;
 297         printf("%d -round-> %d\n",val,__WORDSIZEROUND(val));
 298         b=ba_alloc(val);
 299         ba_set(b,31);
 300         ba_set(b,33);
 301         printf("%d -> %d\n",31,ba_check(b,31));
 302         printf("%d -> %d\n",33,ba_check(b,33));
 303         printf("CARD %d\n",ba_card(b,val));
 304         ba_FORALLFUN(b,val,fun,0);
 305         ba_FORALL(b,val,(printf("E1 %d\n",k)),k);
 306         printf("RE127\n");
 307         b=ba_realloc(b,val,127);
 308         ba_FORALL(b,127,(printf("E2 %d\n",k)),k);
 309         printf("RE42\n");
 310         b=ba_realloc(b,127,42);
 311         ba_FORALL(b,127,(printf("E3 %d\n",k)),k);
 312         ba_clr(b,31);
 313         printf("%d -> %d\n",31,ba_check(b,31));
 314         printf("CARD %d\n",ba_card(b,42));
 315         ba_clr(b,33);
 316         printf("%d -> %d\n",33,ba_check(b,33));
 317         printf("CARD %d\n",ba_card(b,42));
 318         b=bac_alloc(val);
 319         if (argc != 2) return 0;
 320         printf("%d -> %d\n",val,__WORDSIZEROUND(val));
 321         bac_set(b,val,31);
 322         bac_set(b,val,33);
 323         printf("%d -> %d\n",31,bac_check(b,31));
 324         printf("%d -> %d\n",33,bac_check(b,33));
 325         printf("CARD %d\n",bac_card(b,val));
 326         bac_FORALLFUN(b,val,fun,0);
 327         bac_FORALL(b,val,(printf("E1 %d\n",k)),k);
 328         printf("RE127\n");
 329         printf("CARD %d\n",bac_card(b,val));
 330         b=bac_realloc(b,val,127);
 331         bac_FORALL(b,127,(printf("E2 %d\n",k)),k);
 332         printf("RE42\n");
 333         b=bac_realloc(b,127,42);
 334         bac_FORALL(b,42,(printf("E3 %d\n",k)),k);
 335         bac_clr(b,42,31);
 336         printf("%d -> %d\n",31,bac_check(b,31));
 337         printf("CARD %d\n",bac_card(b,42));
 338         bac_clr(b,42,33);
 339         printf("%d -> %d\n",33,bac_check(b,33));
 340         printf("CARD %d\n",bac_card(b,val));
 341 }
 342 #endif
 343 #endif