Release 990613.
[wine.git] / ipc / bit_array.c
blob0f9a5aaa15c55d2f7ae43ce9b65b6462f1771230
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 ***************************************************************************
17 #ifdef CONFIG_IPC
20 ** uncoment the following line to disable assertions,
21 ** this may boost performance by up to 50%
23 /* #define NDEBUG */
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
32 #include <stdio.h>
34 #include <assert.h>
36 #include "bit_array.h"
37 #ifdef HAS_BITOPS
38 #include <asm/bitops.h>
39 #else
40 static inline int clear_bit(int bit, int *mem);
41 static inline int set_bit(int bit, int *mem);
42 #endif /* HAS_BITOPS */
45 #define INT_NR(bit_nr) ((bit_nr) >> INT_LOG2)
46 #define INT_COUNT(bit_count) INT_NR( bit_count + BITS_PER_INT - 1 )
47 #define BIT_IN_INT(bit_nr) ((bit_nr) & (BITS_PER_INT - 1))
49 #if !defined(HAS_BITOPS)
51 /* first_zero maps bytes value to the index of first zero bit */
52 static char first_zero[256];
53 static int arrays_initialized=0;
57 ** initialize static arrays used for bit operations speedup.
58 ** Currently initialized: first_zero[256]
59 ** set "arrays_initialized" to inidate that arrays where initialized
62 static void initialize_arrays()
64 int i;
65 int bit;
67 for (i=0 ; i<256 ; i++) {
68 /* find the first zero bit in `i' */
69 for (bit=0 ; bit < BITS_PER_BYTE ; bit++)
70 /* break if the bit is zero */
71 if ( ( (1 << bit) & i )
72 == 0)
73 break;
74 first_zero[i]= bit;
76 arrays_initialized=1;
80 ** Find first zero bit in the integer.
81 ** Assume there is at least one zero.
83 static inline int find_zbit_in_integer(unsigned int integer)
85 int i;
87 /* find the zero bit */
88 for (i=0 ; i < sizeof(int) ; i++, integer>>=8) {
89 int byte= integer & 0xff;
91 if (byte != 0xff)
92 return ( first_zero[ byte ]
93 + (i << BYTE_LOG2) );
95 assert(0); /* never reached */
96 return 0;
99 /* return -1 on failure */
100 static inline int find_first_zero_bit(unsigned *array, int bits)
102 unsigned int integer;
103 int i;
104 int bytes=INT_COUNT(bits);
106 if (!arrays_initialized)
107 initialize_arrays();
109 for ( i=bytes ; i ; i--, array++) {
110 integer= *array;
112 /* test if integer contains a zero bit */
113 if (integer != ~0U)
114 return ( find_zbit_in_integer(integer)
115 + ((bytes-i) << INT_LOG2) );
118 /* indicate failure */
119 return -1;
122 static inline int test_bit(int pos, unsigned *array)
124 unsigned int integer;
125 int bit = BIT_IN_INT(pos);
127 integer= array[ pos >> INT_LOG2 ];
129 return ( (integer & (1 << bit)) != 0
131 : 0 ) ;
135 ** The following two functions are x86 specific ,
136 ** other processors will need porting
139 /* inputs: bit number and memory address (32 bit) */
140 /* output: Value of the bit before modification */
141 static inline int clear_bit(int bit, int *mem)
143 int ret;
145 __asm__("xor %1,%1\n"
146 "btrl %2,%0\n"
147 "adcl %1,%1\n"
148 :"=m" (*mem), "=&r" (ret)
149 :"r" (bit));
150 return (ret);
153 static inline int set_bit(int bit, int *mem)
155 int ret;
156 __asm__("xor %1,%1\n"
157 "btsl %2,%0\n"
158 "adcl %1,%1\n"
159 :"=m" (*mem), "=&r" (ret)
160 :"r" (bit));
161 return (ret);
164 #endif /* !deined(HAS_BITOPS) */
167 /* AssembleArray: assemble an array object using existing data */
168 bit_array *AssembleArray(bit_array *new_array, unsigned int *buff, int bits)
170 assert(new_array!=NULL);
171 assert(buff!=NULL);
172 assert(bits>0);
173 assert((1 << INT_LOG2) == BITS_PER_INT); /* if fails, redefine INT_LOG2 */
175 new_array->bits=bits;
176 new_array->array=buff;
177 return new_array;
180 /* ResetArray: reset the bit array to zeros */
181 int ResetArray(bit_array *bits)
183 int i;
184 int *p;
186 assert(bits!=NULL);
187 assert(bits->array!=NULL);
189 for(i= INT_COUNT(bits->bits), p=bits->array; i ; p++, i--)
190 *p=0;
191 return 1;
195 /* VacantBit: find a vacant (zero) bit in the array,
196 * Return: Bit index on success, -1 on failure.
198 int VacantBit(bit_array *bits)
200 int bit;
202 assert(bits!=NULL);
203 assert(bits->array!=NULL);
205 bit= find_first_zero_bit(bits->array, bits->bits);
207 if (bit >= bits->bits) /* failed? */
208 return -1;
210 return bit;
213 int SampleBit(bit_array *bits, int i)
215 assert(bits != NULL);
216 assert(bits->array != NULL);
217 assert(i >= 0 && i < bits->bits);
219 return ( test_bit(i,bits->array) != 0
227 ** Use "compare and exchange" mechanism to make sure
228 ** that bits are not modified while "integer" value
229 ** is calculated.
231 ** This may be the slowest technique, but it is the most portable
232 ** (Since most architectures have compare and exchange command)
234 int AssignBit(bit_array *bits, int bit_nr, int val)
236 int ret;
238 assert(bits != NULL);
239 assert(bits->array != NULL);
240 assert(val==0 || val==1);
241 assert(bit_nr >= 0 && bit_nr < bits->bits);
243 if (val==0)
244 ret= clear_bit(BIT_IN_INT(bit_nr), &bits->array[ INT_NR(bit_nr) ]);
245 else
246 ret= set_bit(BIT_IN_INT(bit_nr), &bits->array[ INT_NR(bit_nr) ]);
248 return ( (ret!=0) ? 1 : 0);
252 ** Allocate a free bit (==0) and make it used (==1).
253 ** This operation is guaranteed to resemble an atomic instruction.
255 ** Return: allocated bit index, or -1 on failure.
257 ** There is a crack between locating free bit, and allocating it.
258 ** We assign 1 to the bit, test it was not '1' before the assignment.
259 ** If it was, restart the seek and assign cycle.
263 int AllocateBit(bit_array *bits)
265 int bit_nr;
266 int orig_bit;
268 assert(bits != NULL);
269 assert(bits->array != NULL);
271 do {
272 bit_nr= VacantBit(bits);
274 if (bit_nr == -1) /* No vacant bit ? */
275 return -1;
277 orig_bit = AssignBit(bits, bit_nr, 1);
278 } while (orig_bit != 0); /* it got assigned before we tried */
280 return bit_nr;
283 #endif /* CONFIG_IPC */