utree/detail/utree_detail1.hpp

0001 /*=============================================================================
0002     Copyright (c) 2001-2011 Joel de Guzman
0003     Copyright (c) 2001-2011 Hartmut Kaiser
0004     Copyright (c)      2011 Bryce Lelbach
0005
0006     Distributed under the Boost Software License, Version 1.0. (See accompanying
0007     file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0008 =============================================================================*/
0009 #if !defined(BOOST_SPIRIT_UTREE_DETAIL1)
0010 #define BOOST_SPIRIT_UTREE_DETAIL1
0011
0012 #include <boost/type_traits/alignment_of.hpp>
0013
0014 namespace boost { namespace spirit { namespace detail
0015 {
0016     template <typename UTreeX, typename UTreeY>
0017     struct visit_impl;
0018
0019     struct index_impl;
0020
0021     ///////////////////////////////////////////////////////////////////////////
0022     // Our POD double linked list. Straightforward implementation.
0023     // This implementation is very primitive and is not meant to be
0024     // used stand-alone. This is the internal data representation
0025     // of lists in our utree.
0026     ///////////////////////////////////////////////////////////////////////////
0027     struct list // keep this a POD!
0028     {
0029         struct node;
0030
0031         template <typename Value>
0032         class node_iterator;
0033
0034         void free();
0035         void copy(list const& other);
0036         void default_construct();
0037
0038         template <typename T, typename Iterator>
0039         void insert(T const& val, Iterator pos);
0040
0041         template <typename T>
0042         void push_front(T const& val);
0043
0044         template <typename T>
0045         void push_back(T const& val);
0046
0047         void pop_front();
0048         void pop_back();
0049         node* erase(node* pos);
0050
0051         node* first;
0052         node* last;
0053         std::size_t size;
0054     };
0055
0056     ///////////////////////////////////////////////////////////////////////////
0057     // A range of utree(s) using an iterator range (begin/end) of node(s)
0058     ///////////////////////////////////////////////////////////////////////////
0059     struct range
0060     {
0061         list::node* first;
0062         list::node* last;
0063     };
0064
0065     ///////////////////////////////////////////////////////////////////////////
0066     // A range of char*s
0067     ///////////////////////////////////////////////////////////////////////////
0068     struct string_range
0069     {
0070         char const* first;
0071         char const* last;
0072     };
0073
0074     ///////////////////////////////////////////////////////////////////////////
0075     // A void* plus type_info
0076     ///////////////////////////////////////////////////////////////////////////
0077     struct void_ptr
0078     {
0079         void* p;
0080         std::type_info const* i;
0081     };
0082
0083     ///////////////////////////////////////////////////////////////////////////
0084     // Our POD fast string. This implementation is very primitive and is not
0085     // meant to be used stand-alone. This is the internal data representation
0086     // of strings in our utree. This is deliberately a POD to allow it to be
0087     // placed in a union. This POD fast string specifically utilizes
0088     // (sizeof(list) * alignment_of(list)) - (2 * sizeof(char)). In a 32 bit
0089     // system, this is 14 bytes. The two extra bytes are used by utree to store
0090     // management info.
0091     //
0092     // It is a const string (i.e. immutable). It stores the characters directly
0093     // if possible and only uses the heap if the string does not fit. Null
0094     // characters are allowed, making it suitable to encode raw binary. The
0095     // string length is encoded in the first byte if the string is placed in-situ,
0096     // else, the length plus a pointer to the string in the heap are stored.
0097     ///////////////////////////////////////////////////////////////////////////
0098     struct fast_string // Keep this a POD!
0099     {
0100         static std::size_t const
0101             buff_size = (sizeof(list) + boost::alignment_of<list>::value)
0102                 / sizeof(char);
0103
0104         static std::size_t const
0105             small_string_size = buff_size-sizeof(char);
0106
0107         static std::size_t const
0108             max_string_len = small_string_size - 3;
0109
0110         struct heap_store
0111         {
0112             char* str;
0113             std::size_t size;
0114         };
0115
0116         union
0117         {
0118             char buff[buff_size];
0119             long lbuff[buff_size / (sizeof(long)/sizeof(char))];   // for initialize
0120             heap_store heap;
0121         };
0122
0123         int get_type() const;
0124         void set_type(int t);
0125         bool is_heap_allocated() const;
0126
0127         std::size_t size() const;
0128         char const* str() const;
0129
0130         template <typename Iterator>
0131         void construct(Iterator f, Iterator l);
0132
0133         void swap(fast_string& other);
0134         void free();
0135         void copy(fast_string const& other);
0136         void initialize();
0137
0138         char& info();
0139         char info() const;
0140
0141         short tag() const;
0142         void tag(short tag);
0143     };
0144 }}}
0145
0146 #endif