epoc32/include/stdapis/boost/detail/dynamic_bitset.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
parent 3 e1b950c65cb4
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
     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