Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / detail / dynamic_bitset.hpp
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
24 namespace 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