source: NonGTP/Boost/boost/detail/dynamic_bitset.hpp @ 857

Revision 857, 5.0 KB checked in by igarcia, 19 years ago (diff)
Line 
1// --------------------------------------------------
2//
3// (C) Copyright Chuck Allison and Jeremy Siek 2001 - 2002.
4// (C) Copyright Gennaro Prota                 2003 - 2004.
5//
6// Distributed under the Boost Software License, Version 1.0.
7//    (See accompanying file LICENSE_1_0.txt or copy at
8//          http://www.boost.org/LICENSE_1_0.txt)
9//
10// -----------------------------------------------------------
11
12//  See http://www.boost.org/libs/dynamic_bitset for documentation.
13
14
15#ifndef BOOST_DETAIL_DYNAMIC_BITSET_HPP
16#define BOOST_DETAIL_DYNAMIC_BITSET_HPP
17
18#include <cstddef> // for std::size_t
19#include "boost/config.hpp"
20#include "boost/detail/workaround.hpp"
21//#include "boost/static_assert.hpp" // gps
22
23
24namespace boost {
25
26  namespace detail {
27
28    // Gives (read-)access to the object representation
29    // of an object of type T (3.9p4). CANNOT be used
30    // on a base sub-object
31    //
32    template <typename T>
33    inline const unsigned char * object_representation (T* p)
34    {
35        return static_cast<const unsigned char *>(static_cast<const void *>(p));
36    }
37
38
39    // ------- count function implementation --------------
40
41    namespace dynamic_bitset_count_impl {
42
43    typedef unsigned char byte_type;
44
45    enum mode { access_by_bytes, access_by_blocks };
46
47    template <mode> struct mode_to_type {};
48
49    // the table: wrapped in a class template, so
50    // that it is only instantiated if/when needed
51    //
52    template <bool dummy_name = true>
53    struct count_table { static const byte_type table[]; };
54
55    template <>
56    struct count_table<false> { /* no table */ };
57
58
59     const unsigned int table_width = 8;
60     template <bool b>
61     const byte_type count_table<b>::table[] =
62     {
63       // Automatically generated by GPTableGen.exe v.1.0
64       //
65     0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
66     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
67     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
68     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
69     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
70     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
71     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
72     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
73     };
74
75
76     // overload for access by bytes
77     //
78
79     template <typename Iterator>
80     inline std::size_t do_count(Iterator first, std::size_t length,
81                                 int /*dummy param*/,
82                                 mode_to_type<access_by_bytes>* )
83     {
84         std::size_t num = 0;
85         if (length)
86         {
87             const byte_type * p = object_representation(&*first);
88             length *= sizeof(*first);
89
90              do {
91                 num += count_table<>::table[*p];
92                 ++p;
93                 --length;
94
95             } while (length);
96         }
97
98         return num;
99     }
100
101
102     // overload for access by blocks
103     //
104     template <typename Iterator, typename ValueType>
105     inline std::size_t do_count(Iterator first, std::size_t length, ValueType,
106                                 mode_to_type<access_by_blocks>*)
107     {
108         std::size_t num = 0;
109         while (length){
110
111             ValueType value = *first;
112             while (value) {
113                 num += count_table<>::table[value & ((1u<<table_width) - 1)];
114                 value >>= table_width;
115             }
116
117             ++first;
118             --length;
119         }
120
121         return num;
122     }
123
124
125    } // dynamic_bitset_count_impl
126    // -------------------------------------------------------
127
128
129    // Some library implementations simply return a dummy
130    // value such as
131    //
132    //   size_type(-1) / sizeof(T)
133    //
134    // from vector<>::max_size. This tries to get out more
135    // meaningful info.
136    //
137    template <typename T>
138    typename T::size_type vector_max_size_workaround(const T & v) {
139
140      typedef typename T::allocator_type allocator_type;
141
142      const typename allocator_type::size_type alloc_max =
143                                                  v.get_allocator().max_size();
144      const typename T::size_type container_max = v.max_size();
145
146      return alloc_max < container_max?
147                    alloc_max :
148                    container_max;
149    }
150
151    // for static_asserts
152    template <typename T>
153    struct dynamic_bitset_allowed_block_type {
154        enum { value = T(-1) > 0 }; // ensure T has no sign
155    };
156
157    template <>
158    struct dynamic_bitset_allowed_block_type<bool> {
159        enum { value = false };
160    };
161
162
163  } // namespace detail
164
165} // namespace boost
166
167#endif // include guard
168
Note: See TracBrowser for help on using the repository browser.