1 /****************************************************************/ 2 /* Parallel Combinatorial BLAS Library (for Graph Computations) */ 3 /* version 1.4 -------------------------------------------------*/ 4 /* date: 1/17/2014 ---------------------------------------------*/ 5 /* authors: Aydin Buluc (abuluc@lbl.gov), Adam Lugowski --------*/ 6 /* this file contributed by Scott Beamer of UC Berkeley --------*/ 7 /****************************************************************/ 8 /* 9 Copyright (c) 2010-2014, The Regents of the University of California 10 11 Permission is hereby granted, free of charge, to any person obtaining a copy 12 of this software and associated documentation files (the "Software"), to deal 13 in the Software without restriction, including without limitation the rights 14 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 15 copies of the Software, and to permit persons to whom the Software is 16 furnished to do so, subject to the following conditions: 17 18 The above copyright notice and this permission notice shall be included in 19 all copies or substantial portions of the Software. 20 21 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 22 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 23 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 24 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 25 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 26 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 27 THE SOFTWARE. 28 */ 29 30 #ifndef BITMAP_H 31 #define BITMAP_H 32 33 #include <stdint.h> 34 35 #define WORD_OFFSET(n) (n/64) 36 #define BIT_OFFSET(n) (n & 0x3f) 37 38 namespace combblas { 39 40 class BitMap { 41 public: 42 // actually always rounds up BitMap()43 BitMap() { start = NULL; end = NULL;}; // default constructor 44 BitMap(uint64_t size)45 BitMap(uint64_t size) { 46 uint64_t num_longs = (size + 63) / 64; 47 // VS9: warning C4244: 'initializing' : conversion from 'uint64_t' to 'unsigned int', possible loss of data 48 start = new uint64_t[num_longs](); // zero initialized by default 49 end = start + num_longs; 50 } 51 ~BitMap()52 ~BitMap() { 53 delete[] start; 54 } BitMap(const BitMap & rhs)55 BitMap(const BitMap & rhs) 56 { 57 uint64_t num_longs = rhs.end - rhs.start; 58 // VS9: warning C4244: 'initializing' : conversion from 'uint64_t' to 'unsigned int', possible loss of data 59 start = new uint64_t[num_longs]; 60 end = start + num_longs; 61 std::copy(rhs.start, rhs.end, start); 62 } 63 BitMap & operator= (const BitMap & rhs) 64 { 65 if(this != &rhs) 66 { 67 delete [] start; 68 uint64_t num_longs = rhs.end - rhs.start; 69 // VS9: warning C4244: 'initializing' : conversion from 'uint64_t' to 'unsigned int', possible loss of data 70 start = new uint64_t[num_longs]; 71 end = start + num_longs; 72 std::copy(rhs.start, rhs.end, start); 73 } 74 return *this; 75 } 76 77 78 inline reset()79 void reset() { 80 for(uint64_t *it=start; it!=end; it++) 81 *it = 0; 82 } 83 84 inline set_bit(uint64_t pos)85 void set_bit(uint64_t pos) { 86 start[WORD_OFFSET(pos)] |= ( static_cast<uint64_t>(1l)<<BIT_OFFSET(pos)); 87 } 88 89 inline reset_bit(uint64_t pos)90 void reset_bit(uint64_t pos) { 91 start[WORD_OFFSET(pos)] &= ~( static_cast<uint64_t>(1l)<<BIT_OFFSET(pos)); 92 } 93 94 inline set_bit_atomic(long pos)95 void set_bit_atomic(long pos) { 96 set_bit(pos); 97 // uint64_t old_val, new_val; 98 // uint64_t *loc = start + WORD_OFFSET(pos); 99 // do { 100 // old_val = *loc; 101 // new_val = old_val | ((uint64_t) 1l<<BIT_OFFSET(pos)); 102 // } while(!__sync_bool_compare_and_swap(loc, old_val, new_val)); 103 } 104 105 inline get_bit(uint64_t pos)106 bool get_bit(uint64_t pos) { 107 // VS9: warning C4334: '<<' : result of 32-bit shift implicitly converted to 64 bits (was 64-bit shift intended?) 108 if (start[WORD_OFFSET(pos)] & ( static_cast<uint64_t>(1l) <<BIT_OFFSET(pos))) 109 return true; 110 else 111 return false; 112 } 113 114 inline get_next_bit(uint64_t pos)115 long get_next_bit(uint64_t pos) { 116 uint64_t next = pos; 117 int bit_offset = BIT_OFFSET(pos); 118 uint64_t *it = start + WORD_OFFSET(pos); 119 uint64_t temp = (*it); 120 if (bit_offset != 63) { 121 temp = temp >> (bit_offset+1); 122 } else { 123 temp = 0; 124 } 125 if (!temp) { 126 next = (next & 0xffffffc0); 127 while (!temp) { 128 it++; 129 if (it >= end) 130 return -1; 131 temp = *it; 132 next += 64; 133 } 134 } else { 135 next++; 136 } 137 while(!(temp&1)) { 138 temp = temp >> 1; 139 next++; 140 } 141 return next; 142 } 143 144 inline data()145 uint64_t* data() { 146 return start; 147 } 148 copy_from(const BitMap * other)149 void copy_from(const BitMap* other) { 150 std::copy(other->start, other->end, start); 151 } 152 print_ones()153 void print_ones() { 154 uint64_t max_size = (end-start)*64; 155 for (uint64_t i=0; i<max_size; i++) 156 if (get_bit(i)) 157 std::cout << " " << i; 158 std::cout << std::endl; 159 } 160 161 private: 162 uint64_t *start; 163 uint64_t *end; 164 }; 165 166 } 167 168 #endif // BITMAP_H 169