00001 /* 00002 * IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. By 00003 * downloading, copying, installing or using the software you agree to 00004 * this license. If you do not agree to this license, do not download, 00005 * install, copy or use the software. 00006 * 00007 * Intel Open Source License 00008 * 00009 * Copyright (c) 2006 Intel Corporation. All rights reserved. 00010 * 00011 * Redistribution and use in source and binary forms, with or without 00012 * modification, are permitted provided that the following conditions are 00013 * met: 00014 * 00015 * Redistributions of source code must retain the above copyright 00016 * notice, this list of conditions and the following disclaimer. 00017 * 00018 * Redistributions in binary form must reproduce the above copyright 00019 * notice, this list of conditions and the following disclaimer in the 00020 * documentation and/or other materials provided with the distribution. 00021 * 00022 * Neither the name of the Intel Corporation nor the names of its 00023 * contributors may be used to endorse or promote products derived from 00024 * this software without specific prior written permission. 00025 * 00026 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 00027 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 00028 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 00029 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE INTEL OR 00030 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 00031 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 00032 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 00033 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 00034 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 00035 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 00036 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00037 */ 00038 #ifndef _OASYS_SPARSE_BITMAP_H_ 00039 #define _OASYS_SPARSE_BITMAP_H_ 00040 00041 #include <vector> 00042 #include "config.h" 00043 #include "../debug/DebugUtils.h" 00044 #include "../debug/Formatter.h" 00045 00046 namespace oasys { 00047 00057 template <typename _inttype_t> 00058 class SparseBitmap : public Formatter { 00059 public: 00063 SparseBitmap(); 00064 00068 void set(_inttype_t start, _inttype_t len = 1); 00069 00073 void clear(_inttype_t start, _inttype_t len = 1); 00074 00078 bool is_set(_inttype_t start, _inttype_t len = 1); 00079 00083 bool operator[](_inttype_t val) 00084 { 00085 return is_set(val, 1); 00086 } 00087 00091 _inttype_t num_set(); 00092 00096 bool empty() { return bitmap_.empty(); } 00097 00101 size_t num_entries() { return bitmap_.size(); } 00102 00106 void clear() { bitmap_.clear(); } 00107 00112 _inttype_t num_contiguous(); 00113 00117 int format(char* bp, size_t len) const; 00118 00119 protected: 00120 struct Range { 00121 Range(_inttype_t start, _inttype_t end) 00122 : start_(start), end_(end) {} 00123 00124 _inttype_t start_; 00125 _inttype_t end_; 00126 }; 00127 00128 typedef std::vector<Range> RangeVector; 00129 RangeVector bitmap_; 00130 00131 void validate(); 00132 00133 public: 00144 class iterator { 00145 public: 00149 iterator(); 00150 00154 _inttype_t operator*(); 00155 00159 iterator& operator++(); 00160 00164 iterator operator++(int); 00165 00169 iterator operator+(int diff); 00170 00174 iterator& operator--(); 00175 00179 iterator operator--(int); 00180 00184 iterator operator-(int diff); 00185 00189 bool operator==(const iterator& other); 00190 00194 bool operator!=(const iterator& other); 00195 00201 iterator& skip_contiguous(); 00202 00203 private: 00204 friend class SparseBitmap<_inttype_t>; 00205 00207 iterator(typename RangeVector::iterator iter, 00208 _inttype_t offset); 00209 00211 typename RangeVector::iterator iter_; 00212 00214 _inttype_t offset_; 00215 }; 00216 00220 iterator begin(); 00221 00225 iterator end(); 00226 00230 _inttype_t first() { return *begin(); } 00231 00235 _inttype_t last() { return *--end(); } 00236 }; 00237 00238 #include "SparseBitmap.tcc" 00239 00240 } // namespace oasys 00241 00242 #endif /* _OASYS_SPARSE_BITMAP_H_ */