SparseBitmap.h

Go to the documentation of this file.
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_ */

Generated on Fri Dec 22 14:48:00 2006 for DTN Reference Implementation by  doxygen 1.5.1