1 /*============================================================================= 2 Copyright (c) 2001-2011 Joel de Guzman 3 Copyright (c) 2001-2011 Hartmut Kaiser 4 Copyright (c) 2011 Bryce Lelbach 5 6 Distributed under the Boost Software License, Version 1.0. (See accompanying 7 file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 8 =============================================================================*/ 9 #if !defined(BOOST_SPIRIT_UTREE_DETAIL1) 10 #define BOOST_SPIRIT_UTREE_DETAIL1 11 12 #include <boost/type_traits/alignment_of.hpp> 13 14 namespace boost { namespace spirit { namespace detail 15 { 16 template <typename UTreeX, typename UTreeY> 17 struct visit_impl; 18 19 struct index_impl; 20 21 /////////////////////////////////////////////////////////////////////////// 22 // Our POD double linked list. Straightforward implementation. 23 // This implementation is very primitive and is not meant to be 24 // used stand-alone. This is the internal data representation 25 // of lists in our utree. 26 /////////////////////////////////////////////////////////////////////////// 27 struct list // keep this a POD! 28 { 29 struct node; 30 31 template <typename Value> 32 class node_iterator; 33 34 void free(); 35 void copy(list const& other); 36 void default_construct(); 37 38 template <typename T, typename Iterator> 39 void insert(T const& val, Iterator pos); 40 41 template <typename T> 42 void push_front(T const& val); 43 44 template <typename T> 45 void push_back(T const& val); 46 47 void pop_front(); 48 void pop_back(); 49 node* erase(node* pos); 50 51 node* first; 52 node* last; 53 std::size_t size; 54 }; 55 56 /////////////////////////////////////////////////////////////////////////// 57 // A range of utree(s) using an iterator range (begin/end) of node(s) 58 /////////////////////////////////////////////////////////////////////////// 59 struct range 60 { 61 list::node* first; 62 list::node* last; 63 }; 64 65 /////////////////////////////////////////////////////////////////////////// 66 // A range of char*s 67 /////////////////////////////////////////////////////////////////////////// 68 struct string_range 69 { 70 char const* first; 71 char const* last; 72 }; 73 74 /////////////////////////////////////////////////////////////////////////// 75 // A void* plus type_info 76 /////////////////////////////////////////////////////////////////////////// 77 struct void_ptr 78 { 79 void* p; 80 std::type_info const* i; 81 }; 82 83 /////////////////////////////////////////////////////////////////////////// 84 // Our POD fast string. This implementation is very primitive and is not 85 // meant to be used stand-alone. This is the internal data representation 86 // of strings in our utree. This is deliberately a POD to allow it to be 87 // placed in a union. This POD fast string specifically utilizes 88 // (sizeof(list) * alignment_of(list)) - (2 * sizeof(char)). In a 32 bit 89 // system, this is 14 bytes. The two extra bytes are used by utree to store 90 // management info. 91 // 92 // It is a const string (i.e. immutable). It stores the characters directly 93 // if possible and only uses the heap if the string does not fit. Null 94 // characters are allowed, making it suitable to encode raw binary. The 95 // string length is encoded in the first byte if the string is placed in-situ, 96 // else, the length plus a pointer to the string in the heap are stored. 97 /////////////////////////////////////////////////////////////////////////// 98 struct fast_string // Keep this a POD! 99 { 100 static std::size_t const 101 buff_size = (sizeof(list) + boost::alignment_of<list>::value) 102 / sizeof(char); 103 104 static std::size_t const 105 small_string_size = buff_size-sizeof(char); 106 107 static std::size_t const 108 max_string_len = small_string_size - 3; 109 110 struct heap_store 111 { 112 char* str; 113 std::size_t size; 114 }; 115 116 union 117 { 118 char buff[buff_size]; 119 long lbuff[buff_size / (sizeof(long)/sizeof(char))]; // for initialize 120 heap_store heap; 121 }; 122 123 int get_type() const; 124 void set_type(int t); 125 bool is_heap_allocated() const; 126 127 std::size_t size() const; 128 char const* str() const; 129 130 template <typename Iterator> 131 void construct(Iterator f, Iterator l); 132 133 void swap(fast_string& other); 134 void free(); 135 void copy(fast_string const& other); 136 void initialize(); 137 138 char& info(); 139 char info() const; 140 141 short tag() const; 142 void tag(short tag); 143 }; 144 }}} 145 146 #endif 147