minor fix for bitvector compare
[charm.git] / src / util / ckbitvector.C
1 #include <string.h> // for memset
2 #include "charm++.h"
3 #include "ckbitvector.h"
4
5 /* ************************************************************************
6  * CkBitVector
7  *
8  * The CkBitVector class implements a bit vector in the same order that
9  * charm expects it for the message priorities. The way that works is:
10  *
11  * Highest bit of the bit vector goes in the first integer's highest bit.
12  * The next goes in the next, so on and so fourth until it hits the first
13  * integer's lowest bit. The next bit in order is the highest bit of
14  * the next integer. So you get a pattern like:
15  *
16  *  xx xx xx xx  xx xx xx xx  xx xx xx xx 
17  *     Int 0        Int 1        Int 2
18  *  0        32  0        32  0        32
19  *            ^
20  *   <<<<<<<<<
21  *  v______________________
22  *                         ^
23  *                <<<<<<<<<
24  *               v______________________
25  *                                      ^
26  *                             <<<<<<<<<
27  *                            v
28  *
29  * Where you follow the path down reading bits where there is a ^, v, or <.
30  *
31  * ************************************************************************ */
32 // Construct an empty bit vector
33 CkBitVector::CkBitVector() : usedBits(0), data(NULL) {
34 }
35
36 // Construct a copy of a bit vector
37 CkBitVector::CkBitVector(const CkBitVector &b) : usedBits(b.usedBits) {
38   if ( b.data ) {
39     data = new prio_t[chunks(usedBits)];
40     memcpy(data, b.data, chunks(usedBits)*chunkSize());
41   } else {
42     data = NULL;
43   }
44 }
45
46 // Construct a bit vector of the specified size.
47 CkBitVector::CkBitVector(prio_t bits) : usedBits(bits) {
48   if ( bits != 0 ) {
49     data = new prio_t[chunks(usedBits)];
50     memset(data, 0, chunks(usedBits)*chunkSize());
51   } else {
52     data = NULL;
53   }
54 }
55
56 // Construct a bit vector that's set to the given value out of the number
57 // of choices specified
58 CkBitVector::CkBitVector(prio_t value, prio_t choices) {
59   // If the user gave me a higher value than the choices, whine at them.
60   if ( value >= choices ) {
61     CkAbort("User asked for a bit vector too large for the number of choices specified!");
62   }
63
64   // Okay they didn't. Figure out how many bits I need to represent the
65   // choices
66   usedBits = ilog2(choices);
67   if ( usedBits != 0 ) {
68     data = new prio_t[chunks(usedBits)];
69     data[0] = value << (chunkBits() - usedBits);
70   } else {
71     data = NULL;
72   }
73 }
74
75 // Nuke the memory occupied by a CkBitVector
76 CkBitVector::~CkBitVector() {
77   wipeData();
78 }
79
80 // Clean out any memory I'm using.
81 void CkBitVector::wipeData() {
82   if ( data ) {
83     delete [] data;
84     data = NULL;
85   }
86
87   usedBits = 0;
88 }
89
90
91 // Copy a CkBitVector into this one.
92 CkBitVector & CkBitVector::operator=(const CkBitVector &b) {
93   // Clean out any old cruft
94   wipeData();
95
96   // Was the other vector null?
97   if ( b.usedBits == 0 || b.data == NULL ) {
98     usedBits = 0;
99     data = NULL;
100   } else {
101     // Put in the new cruft
102     usedBits = b.usedBits;
103     data = new prio_t[chunks(usedBits)];
104     memcpy(data, b.data, chunks(usedBits)*chunkSize());
105   }
106
107   // Return the resultant bitvector
108   return *this;
109 }
110
111
112 // Zero all the bits in a vector
113 CkBitVector & CkBitVector::Zero() {
114   // This won't work real well if the vector is empty
115   if ( data == NULL ) { return *this; }
116
117   // Zero out all the bits
118   memset(data, 0, chunkSize()*chunks(usedBits));
119
120   return *this;
121 }
122
123 // Invert the bit vector
124 CkBitVector & CkBitVector::Invert() {
125   // As usual, do nothing if I'm null.
126   if ( data == NULL ) { return *this; }
127
128   // Invert all my bits. Only tricky one is the last block I need to mask
129   // those bits beyond the end of the vector to make sure they don't get
130   // set and corrupt an operation like shifting later.
131   int i;
132   for ( i = 0 ; i < chunks(usedBits) ; i++ ) {
133     data[i] = ~(data[i]);
134   }
135   if ( usedBits % chunkBits() != 0 ) {
136     i = chunks(usedBits) - 1;
137     data[i] = data[i] & ((~(unsigned int)0)<<(chunkBits()-(usedBits%chunkBits())));
138   }
139
140   return *this;
141 }
142
143 // Clear the given bit in the bitvector
144 CkBitVector & CkBitVector::Clear(prio_t bit) {
145   // If it is out of range, grow yourself and that much. You don't need to
146   // Clear the bit because it comes cleared already
147   if ( bit+1 > usedBits ) {
148     Resize(bit+1);
149     return *this;
150   }
151
152   // The bit exists, compute where we'll find it.
153   prio_t index = offset(bit);
154   prio_t bitMask = ~(mask(bit));
155
156   // Twiddle that bit to clear
157   data[index] = data[index] & bitMask;
158
159   // Return the modified bitvector
160   return *this;
161 }
162
163 // Set a bit
164 CkBitVector & CkBitVector::Set(prio_t bit) {
165   // If it is out of range, grow yourself and that much then set as normal.
166   if ( bit+1 > usedBits ) {
167     Resize(bit+1);
168   }
169
170   // The bit exists, compute where we'll find it.
171   prio_t index = offset(bit);
172   prio_t bitMask = mask(bit);
173
174   // Twiddle that bit to set
175   data[index] = data[index] | bitMask;
176
177   // Return the modified bitvector
178   return *this;
179 }
180
181 // Is the bit given set?
182 bool CkBitVector::Test(prio_t bit) const {
183   // If it is out of range it's obviously false
184   if ( bit+1 > usedBits ) { return false; }
185
186   // If it's in range, calculate it's chunk and offset
187   prio_t index = offset(bit);
188   prio_t bitMask = mask(bit);
189
190 //ckerr << bit << ": at offset " << index << " mask " << bitMask << endl;
191
192   // Access that bit, check it versus the mask and return the result
193   return ((data[index]&bitMask) != 0);
194 }
195
196
197
198 // ShiftDown and ShiftUp
199 CkBitVector & CkBitVector::ShiftUp(prio_t bits) {
200   // If data is null then we have nothing to work on
201   // Also abort if we got a dud shift (0)
202   if ( ! data || bits == 0 ) { return *this; }
203
204   // Shift by the whole and by the remainder at the same time
205   prio_t whole = bits / chunkBits();
206   prio_t rem = bits % chunkBits();
207   for ( int i = 0 ; i < chunks(usedBits) ; i++ ) {
208      if ( i+whole < chunks(usedBits) ) {
209        data[i] = data[i+whole] << rem;
210
211        if ( i+whole+1 < chunks(usedBits) ) {
212          data[i] = data[i] | (data[i+whole+1] >> (chunkBits()-rem));
213        }
214      } else {
215        data[i] = 0;
216      }
217   }
218
219   return *this;
220 }
221
222 CkBitVector & CkBitVector::ShiftDown(prio_t bits) {
223   // If data is null then we have nothing to work on
224   // Also abort if we got a dud shift (0)
225   if ( ! data || bits == 0 ) { return *this; }
226
227   // Shift by the whole and by the remainder at the same time
228   int whole = bits / chunkBits();
229   int rem = bits % chunkBits();
230   for ( int i = chunks(usedBits)-1 ; i >= 0 ; i-- ) {
231      if ( i-whole >= 0 ) {
232        data[i] = data[i-whole] >> rem;
233
234        if ( i-whole-1 < chunks(usedBits) ) {
235          data[i] = data[i] | (data[i-whole-1] << (chunkBits()-rem));
236        }
237      } else {
238        data[i] = 0;
239      }
240   }
241
242   return *this;
243 }
244
245
246
247 // Resize
248 // For growth, resize will copy the bits back where they were (into the lowest
249 // bits of the new larger bit vector).
250 // For shrinking, resize will copy the highest bits back into the vector.
251 CkBitVector & CkBitVector::Resize(prio_t bits) {
252   // If we got asked to size ourself to our current size, just chunk out
253   if ( bits == usedBits ) { return *this; }
254
255   // If we're empty and got asked to resize, just set our size and allocate
256   // that much memory (remember to zero it!)
257   if ( ! data ) {
258     usedBits = bits;
259     data = new prio_t[chunks(usedBits)];
260     memset(data, 0, chunks(usedBits)*chunkSize());
261     return *this;
262   }
263
264   // Asked to empty ourselves?
265   if ( bits == 0 ) {
266     wipeData();
267     return *this;
268   }
269
270   // Asked to grow?
271   if ( bits > usedBits ) {
272     prio_t shift = bits - usedBits;
273     prio_t *oldData = data;
274     data = new prio_t[chunks(bits)];
275     memset(data, 0, chunks(bits)*chunkSize());
276     memcpy(data, oldData, chunks(usedBits)*chunkSize());
277     delete [] oldData;
278     usedBits = bits;
279     return ShiftDown(shift);
280   }
281
282   // Shrink?
283   if ( bits < usedBits ) {
284     ShiftUp(usedBits - bits);
285     prio_t *oldData = data;
286     data = new prio_t[chunks(bits)];
287     memset(data, 0, chunks(bits)*chunkSize());
288     memcpy(data, oldData, chunks(bits)*chunkSize());
289     delete [] oldData;
290     usedBits = bits;
291     return *this;
292   }
293
294   // This shouldn't ever be reached
295   CkAbort("What in heck did you do!!?!?! CkBitVector error in Resize()!");
296   return *this;
297 }
298
299
300
301 // Union this bit vector with another.
302 CkBitVector & CkBitVector::Union(CkBitVector const &b) {
303   // CkBitVectors must be of the same size.
304   if ( usedBits != b.usedBits ) {
305     CkAbort("CkBitVector Union operands must be of the same length!");
306   }
307
308   // As usual, do nothing if I'm null. Or if the other is null
309   if ( data == NULL || b.data == NULL ) { return *this; }
310
311   // Union them into me
312   for ( int i = 0 ; i < chunks(usedBits) ; i++ ) {
313     data[i] = data[i] | b.data[i];
314   }
315
316   return *this;
317 }
318
319 // Intersect this bit vector with another.
320 CkBitVector & CkBitVector::Intersection(CkBitVector const &b) {
321   // CkBitVectors must be of the same size.
322   if ( usedBits != b.usedBits ) {
323     CkAbort("CkBitVector Intersection operands must be of the same length!");
324   }
325
326   // As usual, do nothing if I'm null. Or if the other is null
327   if ( data == NULL || b.data == NULL ) { return *this; }
328
329   // Intersect them into me
330   for ( int i = 0 ; i < chunks(usedBits) ; i++ ) {
331     data[i] = data[i] & b.data[i];
332   }
333
334   return *this;
335 }
336
337 // Take the difference of this bit vector with another.
338 CkBitVector & CkBitVector::Difference(CkBitVector const &b) {
339   // CkBitVectors must be of the same size.
340   if ( usedBits != b.usedBits ) {
341     CkAbort("CkBitVector Difference operands must be of the same length!");
342   }
343
344   // As usual, do nothing if I'm null. Or if the other is null
345   if ( data == NULL || b.data == NULL ) { return *this; }
346
347   // Take any bits they have set out of me
348   for ( int i = 0 ; i < chunks(usedBits) ; i++ ) {
349     data[i] = data[i] & ~(b.data[i]);
350   }
351
352   return *this;
353 }
354
355
356
357 // Concat two bitvectors together. To do this, we'll need to clone the
358 // one that is being copied into this, and shift it left/right a bit.
359 CkBitVector & CkBitVector::Concat(CkBitVector const &b) {
360   // If I'm null, just copy b into me.
361   if ( ! data ) {
362     *this = b;
363     return *this;
364   }
365
366   // I exist. Create a clone of b I can shift around.
367   CkBitVector tmp(b);
368
369   // Grow b to match me, then move it's bits down to where they need to be
370   tmp.Resize(usedBits + b.usedBits);
371
372   // Grow to hold me and b.
373   unsigned int shiftBy = b.usedBits;
374   Resize(usedBits + b.usedBits);
375   ShiftUp(shiftBy);
376
377   // Now I can union us and get the result of the concatenation.
378   Union(tmp);
379
380   return *this;
381 }
382
383
384
385 // Spit out the bit vector in chunk-sized chunks
386 CkOutStream& operator<< (CkOutStream& ckos, CkBitVector const b ) {
387   if ( b.data ) {
388     char *buff = new char[b.usedBits+1];
389     for ( int i = b.usedBits-1 ; i >= 0 ; i-- ) {
390       buff[(b.usedBits-1)-i] = (b.Test(i) ? '1' : '0');
391     }
392     buff[b.usedBits] = '\0';
393     ckos << buff;
394     delete[] buff;
395   }
396
397   return ckos;
398 }
399
400 CkErrStream& operator<< (CkErrStream& ckes, CkBitVector const b ) {
401   if ( b.data ) {
402     char *buff = new char[b.usedBits+1];
403     for ( int i = b.usedBits-1 ; i >= 0 ; i-- ) {
404       buff[(b.usedBits-1)-i] = (b.Test(i) ? '1' : '0');
405     }
406     buff[b.usedBits] = '\0';
407     ckes << buff;
408     delete[] buff;
409   }
410
411   return ckes;
412 }
413
414 int CkBitVector::Compare(const CkBitVector &b) const
415 {
416     int result = 0;
417     int length, i;
418     if(usedBits > b.usedBits)
419         result = 1;
420     else if (usedBits < b.usedBits)
421         result = -1;
422     else {
423         length = chunks(usedBits);
424         for(i=0; i<length; i++)
425         {
426             if(data[i] > b.data[i])
427             {
428                 result = 1;
429                 break;
430             }else if (data[i] < b.data[i])
431             {
432                 result = -1;
433                 break;
434             }
435         }
436     }
437     return result;
438 }
439
440 // Pack and unpack this bugger!
441 void CkBitVector::pup(PUP::er &p) {
442   p|usedBits;
443
444   if ( usedBits == 0 ) {
445     data = NULL;
446   } else {
447     if ( p.isUnpacking() ) {
448       delete [] data;
449       data = new prio_t[chunks(usedBits)];
450       memset(data, 0, chunks(usedBits)*chunkSize());
451     }
452     p(data, chunks(usedBits));
453   }
454 }