ipc/bit_array.c

   1 /***************************************************************************
   2  * Copyright 1995, Technion, Israel Institute of Technology
   3  * Electrical Eng, Software Lab.
   4  * Author:    Michael Veksler.
   5  ***************************************************************************
   6  * File:      bit_array.c
   7  * Purpose :  manipulate array of bits
   8  * Portability: This is not completely portable, non CISC arcitectures
   9  *              Might not have atomic Clear/Set/Toggle bit. On those
  10  *              architectures semaphores should be used.
  11  * Big Endian Concerns: This code is big endian compatible,
  12  *              but the byte order will be different (i.e. bit 0 will be
  13  *              located in byte 3).
  14  ***************************************************************************
  15  */
  16
  17 /*
  18 ** uncoment the following line to disable assertions,
  19 ** this may boost performance by up to 50%
  20 */
  21 /* #define NDEBUG */
  22
  23 #ifndef NO_ASM
  24 #define HAS_BITOPS
  25 #endif
  26
  27 #include <stdio.h>
  28
  29 #include <assert.h>
  30
  31 #include "bit_array.h"
  32 #if defined(HAS_BITOPS)
  33 #  include <asm/bitops.h>
  34 #else
  35 static __inline__ int clear_bit(int bit, int *mem);
  36 static __inline__ int set_bit(int bit, int *mem);
  37 #endif /* HAS_BITOPS */
  38
  39
  40 #define INT_NR(bit_nr)       ((bit_nr) >> INT_LOG2)
  41 #define INT_COUNT(bit_count) INT_NR( bit_count + BITS_PER_INT - 1 )
  42 #define BIT_IN_INT(bit_nr)   ((bit_nr) & (BITS_PER_INT - 1))
  43
  44 #if !defined(HAS_BITOPS)
  45
  46 /* first_zero maps bytes value to the index of first zero bit */
  47 static char first_zero[256];
  48 static int arrays_initialized=0;
  49
  50
  51 /*
  52 ** initialize static arrays used for bit operations speedup.
  53 ** Currently initialized: first_zero[256]
  54 ** set "arrays_initialized" to inidate that arrays where initialized
  55 */
  56
  57 static void initialize_arrays()
  58 {
  59   int i;
  60   int bit;
  61
  62   for (i=0 ; i<256 ; i++) {
  63      /* find the first zero bit in `i' */
  64      for (bit=0 ; bit < BITS_PER_BYTE ; bit++)
  65         /* break if the bit is zero */
  66         if ( ( (1 << bit) & i )
  67              == 0)
  68            break;
  69      first_zero[i]= bit;
  70   }
  71   arrays_initialized=1;
  72 }
  73
  74 /*
  75 ** Find first zero bit in the integer.
  76 ** Assume there is at least one zero.
  77 */
  78 static __inline__ int find_zbit_in_integer(unsigned int integer)
  79 {
  80   int i;
  81
  82   /* find the zero bit */
  83   for (i=0 ; i < sizeof(int) ; i++, integer>>=8) {
  84      int byte= integer & 0xff;
  85
  86      if (byte != 0xff)
  87         return ( first_zero[ byte ]
  88                  + (i << BYTE_LOG2) );
  89   }
  90   assert(0);                       /* never reached */
  91   return 0;
  92 }
  93
  94 /* return -1 on failure */
  95 static __inline__ int find_first_zero_bit(unsigned *array, int bits)
  96 {
  97   unsigned int  integer;
  98   int i;
  99   int bytes=INT_COUNT(bits);
 100
 101   if (!arrays_initialized)
 102      initialize_arrays();
 103
 104   for ( i=bytes ; i ; i--, array++) {
 105      integer= *array;
 106
 107      /* test if integer contains a zero bit */
 108      if (integer != ~0U)
 109         return ( find_zbit_in_integer(integer)
 110                  + ((bytes-i) << INT_LOG2) );
 111   }
 112
 113   /* indicate failure */
 114   return -1;
 115 }
 116
 117 static __inline__ int test_bit(int pos, unsigned *array)
 118 {
 119   unsigned int integer;
 120   int bit = BIT_IN_INT(pos);
 121
 122   integer= array[ pos >> INT_LOG2 ];
 123
 124   return (  (integer & (1 << bit)) != 0
 125             ? 1
 126             : 0 ) ;
 127 }
 128
 129 /*
 130 ** The following two functions are x86 specific ,
 131 ** other processors will need porting
 132 */
 133
 134 /* inputs: bit number and memory address (32 bit) */
 135 /* output: Value of the bit before modification */
 136 static __inline__ int clear_bit(int bit, int *mem)
 137 {
 138   int ret;
 139
 140   __asm__("xor %1,%1
 141            btrl %2,%0
 142            adcl %1,%1"
 143           :"=m" (*mem), "=&r" (ret)
 144           :"r" (bit));
 145   return (ret);
 146 }
 147
 148 static __inline__ int set_bit(int bit, int *mem)
 149 {
 150   int ret;
 151   __asm__("xor %1,%1
 152            btsl %2,%0
 153            adcl %1,%1"
 154           :"=m" (*mem), "=&r" (ret)
 155           :"r" (bit));
 156   return (ret);
 157 }
 158
 159 #endif /* !deined(HAS_BITOPS) */
 160
 161
 162 /* AssembleArray: assemble an array object using existing data */
 163 bit_array *AssembleArray(bit_array *new_array, unsigned int *buff, int bits)
 164 {
 165   assert(new_array!=NULL);
 166   assert(buff!=NULL);
 167   assert(bits>0);
 168   assert((1 << INT_LOG2) == BITS_PER_INT); /* if fails, redefine INT_LOG2 */
 169
 170   new_array->bits=bits;
 171   new_array->array=buff;
 172   return new_array;
 173 }
 174
 175 /* ResetArray: reset the bit array to zeros */
 176 int ResetArray(bit_array *bits)
 177 {
 178   int i;
 179   int *p;
 180
 181   assert(bits!=NULL);
 182   assert(bits->array!=NULL);
 183
 184   for(i= INT_COUNT(bits->bits), p=bits->array; i ; p++, i--)
 185      *p=0;
 186   return 1;
 187 }
 188
 189
 190 /* VacantBit: find a vacant (zero) bit in the array,
 191  * Return: Bit index on success, -1 on failure.
 192  */
 193 int VacantBit(bit_array *bits)
 194 {
 195   int bit;
 196
 197   assert(bits!=NULL);
 198   assert(bits->array!=NULL);
 199
 200   bit= find_first_zero_bit(bits->array, bits->bits);
 201
 202   if (bit >= bits->bits)           /* failed? */
 203      return -1;
 204
 205   return bit;
 206 }
 207
 208 int SampleBit(bit_array *bits, int i)
 209 {
 210   assert(bits != NULL);
 211   assert(bits->array != NULL);
 212   assert(i >= 0  &&  i < bits->bits);
 213
 214   return ( test_bit(i,bits->array) != 0
 215            ? 1
 216            : 0
 217            );
 218 }
 219
 220
 221 /*
 222 ** Use "compare and exchange" mechanism to make sure
 223 ** that bits are not modified while "integer" value
 224 ** is calculated.
 225 **
 226 ** This may be the slowest technique, but it is the most portable
 227 ** (Since most architectures have compare and exchange command)
 228 */
 229 int AssignBit(bit_array *bits, int bit_nr, int val)
 230 {
 231   int ret;
 232
 233   assert(bits != NULL);
 234   assert(bits->array != NULL);
 235   assert(val==0 || val==1);
 236   assert(bit_nr >= 0  &&  bit_nr < bits->bits);
 237
 238   if (val==0)
 239      ret= clear_bit(BIT_IN_INT(bit_nr), &bits->array[ INT_NR(bit_nr) ]);
 240   else
 241      ret= set_bit(BIT_IN_INT(bit_nr), &bits->array[ INT_NR(bit_nr) ]);
 242
 243   return ( (ret!=0) ? 1 : 0);
 244 }
 245
 246 /*
 247 ** Allocate a free bit (==0) and make it used (==1).
 248 ** This operation is guaranteed to resemble an atomic instruction.
 249 **
 250 ** Return: allocated bit index, or -1 on failure.
 251 **
 252 ** There is a crack between locating free bit, and allocating it.
 253 ** We assign 1 to the bit, test it was not '1' before the assignment.
 254 ** If it was, restart the seek and assign cycle.
 255 **
 256 */
 257
 258 int AllocateBit(bit_array *bits)
 259 {
 260   int bit_nr;
 261   int orig_bit;
 262
 263   assert(bits != NULL);
 264   assert(bits->array != NULL);
 265
 266   do {
 267      bit_nr= VacantBit(bits);
 268
 269      if (bit_nr == -1)             /* No vacant bit ? */
 270         return -1;
 271
 272      orig_bit = AssignBit(bits, bit_nr, 1);
 273   } while (orig_bit != 0);         /* it got assigned before we tried */
 274
 275   return bit_nr;
 276 }