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