1 /* This file is part of Jellyfish. 2 3 This work is dual-licensed under 3-Clause BSD License or GPL 3.0. 4 You can choose between one of them if you use this work. 5 6 `SPDX-License-Identifier: BSD-3-Clause OR GPL-3.0` 7 */ 8 9 #ifndef __JELLYFISH_ATOMIC_BITS_ARRAY_HPP__ 10 #define __JELLYFISH_ATOMIC_BITS_ARRAY_HPP__ 11 12 #include <stdexcept> 13 #include <iterator> 14 15 #include <jellyfish/allocators_mmap.hpp> 16 #include <jellyfish/atomic_gcc.hpp> 17 #include <jellyfish/divisor.hpp> 18 19 namespace jellyfish { 20 template<typename Value, typename T, typename Derived> 21 class atomic_bits_array_base { 22 static const int w_ = sizeof(T) * 8; 23 const int bits_; 24 const size_t size_; 25 const T mask_; 26 const jflib::divisor64 d_; 27 size_t size_bytes_; 28 T* data_; 29 30 friend class iterator; 31 class iterator : public std::iterator<std::input_iterator_tag, Value> { 32 friend class atomic_bits_array_base; 33 const atomic_bits_array_base& ary_; 34 T* word_; 35 T mask_; 36 int off_; 37 iterator(const atomic_bits_array_base & a,T * w,T m,int o)38 iterator(const atomic_bits_array_base& a, T* w, T m, int o) : ary_(a), word_(w), mask_(m), off_(o) { } 39 public: operator ==(const iterator & rhs) const40 bool operator==(const iterator& rhs) const { return word_ == rhs.word_ && off_ == rhs.off_; } operator !=(const iterator & rhs) const41 bool operator!=(const iterator& rhs) const { return word_ != rhs.word_ || off_ != rhs.off_; } operator *() const42 Value operator*() const { return static_cast<Value>((*word_ & mask_) >> off_); } operator ->() const43 Value* operator->() const { return 0; } operator ++()44 iterator& operator++() { 45 off_ += ary_.bits_; 46 if(off_ + ary_.bits_ < w_) { 47 mask_ <<= ary_.bits_; 48 } else { 49 ++word_; 50 mask_ = ary_.mask_; 51 off_ = 0; 52 } 53 return *this; 54 } operator ++(int)55 iterator operator++(int) { 56 iterator res(*this); 57 ++*this; 58 return res; 59 } 60 }; 61 62 class element_proxy { 63 T* word_; 64 const T mask_; 65 const int off_; 66 T prev_word_; 67 get_val(T v) const68 Value get_val(T v) const { 69 return static_cast<Value>((v & mask_) >> off_); 70 } 71 72 public: element_proxy(T * word,T mask,int off)73 element_proxy(T* word, T mask, int off) : 74 word_(word), mask_(mask), off_(off) 75 { } 76 operator Value() const77 operator Value() const { return get_val(*word_); } get()78 Value get() { 79 prev_word_ = *word_; 80 return get_val(prev_word_); 81 } 82 set(Value & nval)83 bool set(Value& nval) { 84 Value pval; 85 Value cval = get_val(prev_word_); 86 do { 87 pval = cval; 88 const T new_word = (prev_word_ & ~mask_) | ((static_cast<T>(nval) << off_) & mask_); 89 const T actual_word = atomic::gcc::cas(word_, prev_word_, new_word); 90 if(__builtin_expect(actual_word == prev_word_, 1)) 91 return true; 92 prev_word_ = actual_word; 93 cval = get_val(prev_word_); 94 } while(pval == cval); 95 nval = cval; 96 return false; 97 } 98 }; 99 100 public: atomic_bits_array_base(int bits,size_t size)101 atomic_bits_array_base(int bits, // Number of bits per entry 102 size_t size) : // Number of entries 103 bits_(bits), 104 size_(size), 105 mask_((T)-1 >> (w_ - bits)), // mask of one entry at the LSB of a word 106 d_(w_ / bits), // divisor of the number of entries per word 107 size_bytes_((size / d_ + (size % d_ != 0)) * sizeof(T)), 108 data_(static_cast<Derived*>(this)->alloc_data(size_bytes_)) 109 { 110 static_assert(sizeof(T) >= sizeof(Value), "Container type T must have at least as many bits as value type"); 111 if((size_t)bits > sizeof(Value) * 8) 112 throw std::runtime_error("The number of bits per entry must be less than the number of bits in the value type"); 113 if(!data_) 114 throw std::runtime_error("Can't allocate memory for atomic_bits_array"); 115 } 116 117 // Return the element at position pos. No check for out of bounds. operator [](size_t pos)118 element_proxy operator[](size_t pos) { 119 uint64_t q, r; 120 d_.division(pos, q, r); 121 const int off = r * bits_; 122 return element_proxy(data_ + q, mask_ << off, off); 123 } operator [](size_t pos) const124 const element_proxy operator[](size_t pos) const { 125 uint64_t q, r; 126 d_.division(pos, q, r); 127 const int off = r * bits_; 128 return element_proxy(data_ + q, mask_ << off, off); 129 } write(std::ostream & os) const130 void write(std::ostream& os) const { 131 os.write((const char*)data_, size_bytes_); 132 } size_bytes() const133 size_t size_bytes() const { return size_bytes_; } bits() const134 int bits() const { return bits_; } 135 begin() const136 iterator begin() const { return iterator(*this, data_, mask_, 0); } end() const137 iterator end() const { 138 uint64_t q, r; 139 d_.division(size_, q, r); 140 const int off = r * bits_; 141 return iterator(*this, data_ + q, mask_ << off, off); 142 } 143 }; 144 145 template<typename Value, typename T = uint64_t> 146 class atomic_bits_array : 147 protected allocators::mmap, 148 public atomic_bits_array_base<Value, T, atomic_bits_array<Value, T> > 149 { 150 typedef atomic_bits_array_base<Value, T, atomic_bits_array<Value, T> > super; 151 friend class atomic_bits_array_base<Value, T, atomic_bits_array<Value, T> >; 152 public: atomic_bits_array(int bits,size_t size)153 atomic_bits_array(int bits, size_t size) : 154 allocators::mmap(), 155 super(bits, size) 156 { } 157 158 protected: alloc_data(size_t s)159 T* alloc_data(size_t s) { 160 allocators::mmap::realloc(s); 161 return (T*)allocators::mmap::get_ptr(); 162 } 163 }; 164 165 struct mem_info { 166 void* ptr_; 167 size_t bytes_; mem_infojellyfish::mem_info168 mem_info(void* ptr, size_t bytes) : ptr_(ptr), bytes_(bytes) { } 169 }; 170 template<typename Value, typename T = uint64_t> 171 class atomic_bits_array_raw : 172 protected mem_info, 173 public atomic_bits_array_base<Value, T, atomic_bits_array_raw<Value, T> > 174 { 175 typedef atomic_bits_array_base<Value, T, atomic_bits_array_raw<Value, T> > super; 176 friend class atomic_bits_array_base<Value, T, atomic_bits_array_raw<Value, T> >; 177 public: atomic_bits_array_raw(void * ptr,size_t bytes,int bits,size_t size)178 atomic_bits_array_raw(void* ptr, size_t bytes, int bits, size_t size) : 179 mem_info(ptr, bytes), 180 super(bits, size) 181 { } 182 183 protected: alloc_data(size_t s)184 T* alloc_data(size_t s) { 185 assert(bytes_ == s); 186 return (T*)ptr_; 187 } 188 }; 189 190 } // namespace jellyfish 191 192 #endif /* __JELLYFISH_ATOMIC_BITS_ARRAY_HPP__ */ 193