OSDN Git Service

264e862e96ae9a3953c37b2b61229526e170992e
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / ext / sso_string_base.h
1 // Short-string-optimized versatile string base -*- C++ -*-
2
3 // Copyright (C) 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library.  This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
9 // any later version.
10
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 // GNU General Public License for more details.
15
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23 // <http://www.gnu.org/licenses/>.
24
25 /** @file ext/sso_string_base.h
26  *  This file is a GNU extension to the Standard C++ Library.
27  *  This is an internal header file, included by other library headers.
28  *  You should not attempt to use it directly.
29  */
30
31 #ifndef _SSO_STRING_BASE_H
32 #define _SSO_STRING_BASE_H 1
33
34 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
35
36   template<typename _CharT, typename _Traits, typename _Alloc>
37     class __sso_string_base
38     : protected __vstring_utility<_CharT, _Traits, _Alloc>
39     {
40     public:
41       typedef _Traits                                       traits_type;
42       typedef typename _Traits::char_type                   value_type;
43
44       typedef __vstring_utility<_CharT, _Traits, _Alloc>    _Util_Base;
45       typedef typename _Util_Base::_CharT_alloc_type        _CharT_alloc_type;
46       typedef typename _CharT_alloc_type::size_type         size_type;
47       
48     private:
49       // Data Members:
50       typename _Util_Base::template _Alloc_hider<_CharT_alloc_type>
51                                                             _M_dataplus;
52       size_type                                             _M_string_length;
53
54       enum { _S_local_capacity = 15 };
55       
56       union
57       {
58         _CharT           _M_local_data[_S_local_capacity + 1];
59         size_type        _M_allocated_capacity;
60       };
61
62       void
63       _M_data(_CharT* __p)
64       { _M_dataplus._M_p = __p; }
65
66       void
67       _M_length(size_type __length)
68       { _M_string_length = __length; }
69
70       void
71       _M_capacity(size_type __capacity)
72       { _M_allocated_capacity = __capacity; }
73
74       bool
75       _M_is_local() const
76       { return _M_data() == _M_local_data; }
77
78       // Create & Destroy
79       _CharT*
80       _M_create(size_type&, size_type);
81       
82       void
83       _M_dispose()
84       {
85         if (!_M_is_local())
86           _M_destroy(_M_allocated_capacity);
87       }
88
89       void
90       _M_destroy(size_type __size) throw()
91       { _M_get_allocator().deallocate(_M_data(), __size + 1); }
92
93       // _M_construct_aux is used to implement the 21.3.1 para 15 which
94       // requires special behaviour if _InIterator is an integral type
95       template<typename _InIterator>
96         void
97         _M_construct_aux(_InIterator __beg, _InIterator __end, 
98                          std::__false_type)
99         {
100           typedef typename iterator_traits<_InIterator>::iterator_category _Tag;
101           _M_construct(__beg, __end, _Tag());
102         }
103
104       // _GLIBCXX_RESOLVE_LIB_DEFECTS
105       // 438. Ambiguity in the "do the right thing" clause
106       template<typename _Integer>
107         void
108         _M_construct_aux(_Integer __beg, _Integer __end, std::__true_type)
109       { _M_construct(static_cast<size_type>(__beg),
110                      static_cast<value_type>(__end)); }
111
112       template<typename _InIterator>
113         void
114         _M_construct(_InIterator __beg, _InIterator __end)
115         {
116           typedef typename std::__is_integer<_InIterator>::__type _Integral;
117           _M_construct_aux(__beg, __end, _Integral());
118         }
119
120       // For Input Iterators, used in istreambuf_iterators, etc.
121       template<typename _InIterator>
122         void
123         _M_construct(_InIterator __beg, _InIterator __end,
124                      std::input_iterator_tag);
125       
126       // For forward_iterators up to random_access_iterators, used for
127       // string::iterator, _CharT*, etc.
128       template<typename _FwdIterator>
129         void
130         _M_construct(_FwdIterator __beg, _FwdIterator __end,
131                      std::forward_iterator_tag);
132
133       void
134       _M_construct(size_type __req, _CharT __c);
135
136     public:
137       size_type
138       _M_max_size() const
139       { return (_M_get_allocator().max_size() - 1) / 2; }
140
141       _CharT*
142       _M_data() const
143       { return _M_dataplus._M_p; }
144
145       size_type
146       _M_length() const
147       { return _M_string_length; }
148
149       size_type
150       _M_capacity() const
151       {
152         return _M_is_local() ? size_type(_S_local_capacity)
153                              : _M_allocated_capacity; 
154       }
155
156       bool
157       _M_is_shared() const
158       { return false; }
159
160       void
161       _M_set_leaked() { }
162
163       void
164       _M_leak() { }
165
166       void
167       _M_set_length(size_type __n)
168       {
169         _M_length(__n);
170         traits_type::assign(_M_data()[__n], _CharT());
171       }
172
173       __sso_string_base()
174       : _M_dataplus(_M_local_data)
175       { _M_set_length(0); }
176
177       __sso_string_base(const _Alloc& __a);
178
179       __sso_string_base(const __sso_string_base& __rcs);
180
181 #ifdef __GXX_EXPERIMENTAL_CXX0X__
182       __sso_string_base(__sso_string_base&& __rcs);
183 #endif
184
185       __sso_string_base(size_type __n, _CharT __c, const _Alloc& __a);
186
187       template<typename _InputIterator>
188         __sso_string_base(_InputIterator __beg, _InputIterator __end,
189                           const _Alloc& __a);
190
191       ~__sso_string_base()
192       { _M_dispose(); }
193
194       _CharT_alloc_type&
195       _M_get_allocator()
196       { return _M_dataplus; }
197
198       const _CharT_alloc_type&
199       _M_get_allocator() const
200       { return _M_dataplus; }
201
202       void
203       _M_swap(__sso_string_base& __rcs);
204
205       void
206       _M_assign(const __sso_string_base& __rcs);
207
208       void
209       _M_reserve(size_type __res);
210
211       void
212       _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
213                 size_type __len2);
214
215       void
216       _M_erase(size_type __pos, size_type __n);
217
218       void
219       _M_clear()
220       { _M_set_length(0); }
221
222       bool
223       _M_compare(const __sso_string_base&) const
224       { return false; }
225     };
226
227   template<typename _CharT, typename _Traits, typename _Alloc>
228     void
229     __sso_string_base<_CharT, _Traits, _Alloc>::
230     _M_swap(__sso_string_base& __rcs)
231     {
232       // _GLIBCXX_RESOLVE_LIB_DEFECTS
233       // 431. Swapping containers with unequal allocators.
234       std::__alloc_swap<_CharT_alloc_type>::_S_do_it(_M_get_allocator(),
235                                                      __rcs._M_get_allocator());
236
237       if (_M_is_local())
238         if (__rcs._M_is_local())
239           {
240             if (_M_length() && __rcs._M_length())
241               {
242                 _CharT __tmp_data[_S_local_capacity + 1];
243                 traits_type::copy(__tmp_data, __rcs._M_local_data,
244                                   _S_local_capacity + 1);
245                 traits_type::copy(__rcs._M_local_data, _M_local_data,
246                                   _S_local_capacity + 1);
247                 traits_type::copy(_M_local_data, __tmp_data,
248                                   _S_local_capacity + 1);
249               }
250             else if (__rcs._M_length())
251               {
252                 traits_type::copy(_M_local_data, __rcs._M_local_data,
253                                   _S_local_capacity + 1);
254                 _M_length(__rcs._M_length());
255                 __rcs._M_set_length(0);
256                 return;
257               }
258             else if (_M_length())
259               {
260                 traits_type::copy(__rcs._M_local_data, _M_local_data,
261                                   _S_local_capacity + 1);
262                 __rcs._M_length(_M_length());
263                 _M_set_length(0);
264                 return;
265               }
266           }
267         else
268           {
269             const size_type __tmp_capacity = __rcs._M_allocated_capacity;
270             traits_type::copy(__rcs._M_local_data, _M_local_data,
271                               _S_local_capacity + 1);
272             _M_data(__rcs._M_data());
273             __rcs._M_data(__rcs._M_local_data);
274             _M_capacity(__tmp_capacity);
275           }
276       else
277         {
278           const size_type __tmp_capacity = _M_allocated_capacity;
279           if (__rcs._M_is_local())
280             {
281               traits_type::copy(_M_local_data, __rcs._M_local_data,
282                                 _S_local_capacity + 1);
283               __rcs._M_data(_M_data());
284               _M_data(_M_local_data);
285             }
286           else
287             {
288               _CharT* __tmp_ptr = _M_data();
289               _M_data(__rcs._M_data());
290               __rcs._M_data(__tmp_ptr);
291               _M_capacity(__rcs._M_allocated_capacity);
292             }
293           __rcs._M_capacity(__tmp_capacity);
294         }
295
296       const size_type __tmp_length = _M_length();
297       _M_length(__rcs._M_length());
298       __rcs._M_length(__tmp_length);
299     }
300
301   template<typename _CharT, typename _Traits, typename _Alloc>
302     _CharT*
303     __sso_string_base<_CharT, _Traits, _Alloc>::
304     _M_create(size_type& __capacity, size_type __old_capacity)
305     {
306       // _GLIBCXX_RESOLVE_LIB_DEFECTS
307       // 83.  String::npos vs. string::max_size()
308       if (__capacity > _M_max_size())
309         std::__throw_length_error(__N("__sso_string_base::_M_create"));
310
311       // The below implements an exponential growth policy, necessary to
312       // meet amortized linear time requirements of the library: see
313       // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
314       if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
315         {
316           __capacity = 2 * __old_capacity;
317           // Never allocate a string bigger than max_size.
318           if (__capacity > _M_max_size())
319             __capacity = _M_max_size();
320         }
321
322       // NB: Need an array of char_type[__capacity], plus a terminating
323       // null char_type() element.
324       return _M_get_allocator().allocate(__capacity + 1);
325     }
326
327   template<typename _CharT, typename _Traits, typename _Alloc>
328     __sso_string_base<_CharT, _Traits, _Alloc>::
329     __sso_string_base(const _Alloc& __a)
330     : _M_dataplus(__a, _M_local_data)
331     { _M_set_length(0); }
332
333   template<typename _CharT, typename _Traits, typename _Alloc>
334     __sso_string_base<_CharT, _Traits, _Alloc>::
335     __sso_string_base(const __sso_string_base& __rcs)
336     : _M_dataplus(__rcs._M_get_allocator(), _M_local_data)
337     { _M_construct(__rcs._M_data(), __rcs._M_data() + __rcs._M_length()); }
338
339 #ifdef __GXX_EXPERIMENTAL_CXX0X__
340   template<typename _CharT, typename _Traits, typename _Alloc>
341     __sso_string_base<_CharT, _Traits, _Alloc>::
342     __sso_string_base(__sso_string_base&& __rcs)
343     : _M_dataplus(__rcs._M_get_allocator(), _M_local_data)
344     {
345       if (__rcs._M_is_local())
346         {
347           if (__rcs._M_length())
348             traits_type::copy(_M_local_data, __rcs._M_local_data,
349                               _S_local_capacity + 1);
350         }
351       else
352         {
353           _M_data(__rcs._M_data());
354           _M_capacity(__rcs._M_allocated_capacity);
355         }
356
357       _M_length(__rcs._M_length());
358       __rcs._M_length(0);
359       __rcs._M_data(__rcs._M_local_data);
360     }
361 #endif
362
363   template<typename _CharT, typename _Traits, typename _Alloc>
364     __sso_string_base<_CharT, _Traits, _Alloc>::
365     __sso_string_base(size_type __n, _CharT __c, const _Alloc& __a)
366     : _M_dataplus(__a, _M_local_data)
367     { _M_construct(__n, __c); }
368
369   template<typename _CharT, typename _Traits, typename _Alloc>
370     template<typename _InputIterator>
371     __sso_string_base<_CharT, _Traits, _Alloc>::
372     __sso_string_base(_InputIterator __beg, _InputIterator __end,
373                       const _Alloc& __a)
374     : _M_dataplus(__a, _M_local_data)
375     { _M_construct(__beg, __end); }
376
377   // NB: This is the special case for Input Iterators, used in
378   // istreambuf_iterators, etc.
379   // Input Iterators have a cost structure very different from
380   // pointers, calling for a different coding style.
381   template<typename _CharT, typename _Traits, typename _Alloc>
382     template<typename _InIterator>
383       void
384       __sso_string_base<_CharT, _Traits, _Alloc>::
385       _M_construct(_InIterator __beg, _InIterator __end,
386                    std::input_iterator_tag)
387       {
388         size_type __len = 0;
389         size_type __capacity = size_type(_S_local_capacity);
390
391         while (__beg != __end && __len < __capacity)
392           {
393             _M_data()[__len++] = *__beg;
394             ++__beg;
395           }
396         
397         __try
398           {
399             while (__beg != __end)
400               {
401                 if (__len == __capacity)
402                   {
403                     // Allocate more space.
404                     __capacity = __len + 1;
405                     _CharT* __another = _M_create(__capacity, __len);
406                     _S_copy(__another, _M_data(), __len);
407                     _M_dispose();
408                     _M_data(__another);
409                     _M_capacity(__capacity);
410                   }
411                 _M_data()[__len++] = *__beg;
412                 ++__beg;
413               }
414           }
415         __catch(...)
416           {
417             _M_dispose();
418             __throw_exception_again;
419           }
420
421         _M_set_length(__len);
422       }
423
424   template<typename _CharT, typename _Traits, typename _Alloc>
425     template<typename _InIterator>
426       void
427       __sso_string_base<_CharT, _Traits, _Alloc>::
428       _M_construct(_InIterator __beg, _InIterator __end,
429                    std::forward_iterator_tag)
430       {
431         // NB: Not required, but considered best practice.
432         if (__is_null_pointer(__beg) && __beg != __end)
433           std::__throw_logic_error(__N("__sso_string_base::"
434                                        "_M_construct NULL not valid"));
435
436         size_type __dnew = static_cast<size_type>(std::distance(__beg, __end));
437
438         if (__dnew > size_type(_S_local_capacity))
439           {
440             _M_data(_M_create(__dnew, size_type(0)));
441             _M_capacity(__dnew);
442           }
443
444         // Check for out_of_range and length_error exceptions.
445         __try
446           { _S_copy_chars(_M_data(), __beg, __end); }
447         __catch(...)
448           {
449             _M_dispose();
450             __throw_exception_again;
451           }
452
453         _M_set_length(__dnew);
454       }
455
456   template<typename _CharT, typename _Traits, typename _Alloc>
457     void
458     __sso_string_base<_CharT, _Traits, _Alloc>::
459     _M_construct(size_type __n, _CharT __c)
460     {
461       if (__n > size_type(_S_local_capacity))
462         {
463           _M_data(_M_create(__n, size_type(0)));
464           _M_capacity(__n);
465         }
466
467       if (__n)
468         _S_assign(_M_data(), __n, __c);
469
470       _M_set_length(__n);
471     }
472
473   template<typename _CharT, typename _Traits, typename _Alloc>
474     void
475     __sso_string_base<_CharT, _Traits, _Alloc>::
476     _M_assign(const __sso_string_base& __rcs)
477     {
478       if (this != &__rcs)
479         {
480           const size_type __rsize = __rcs._M_length();
481           const size_type __capacity = _M_capacity();
482
483           if (__rsize > __capacity)
484             {
485               size_type __new_capacity = __rsize;
486               _CharT* __tmp = _M_create(__new_capacity, __capacity);
487               _M_dispose();
488               _M_data(__tmp);
489               _M_capacity(__new_capacity);
490             }
491
492           if (__rsize)
493             _S_copy(_M_data(), __rcs._M_data(), __rsize);
494
495           _M_set_length(__rsize);
496         }
497     }
498
499   template<typename _CharT, typename _Traits, typename _Alloc>
500     void
501     __sso_string_base<_CharT, _Traits, _Alloc>::
502     _M_reserve(size_type __res)
503     {
504       // Make sure we don't shrink below the current size.
505       if (__res < _M_length())
506         __res = _M_length();
507
508       const size_type __capacity = _M_capacity();
509       if (__res != __capacity)
510         {
511           if (__res > __capacity
512               || __res > size_type(_S_local_capacity))
513             {
514               _CharT* __tmp = _M_create(__res, __capacity);
515               _S_copy(__tmp, _M_data(), _M_length() + 1);
516               _M_dispose();
517               _M_data(__tmp);
518               _M_capacity(__res);
519             }
520           else if (!_M_is_local())
521             {
522               _S_copy(_M_local_data, _M_data(), _M_length() + 1);
523               _M_destroy(__capacity);
524               _M_data(_M_local_data);
525             }
526         }
527     }
528
529   template<typename _CharT, typename _Traits, typename _Alloc>
530     void
531     __sso_string_base<_CharT, _Traits, _Alloc>::
532     _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
533               size_type __len2)
534     {
535       const size_type __how_much = _M_length() - __pos - __len1;
536       
537       size_type __new_capacity = _M_length() + __len2 - __len1;
538       _CharT* __r = _M_create(__new_capacity, _M_capacity());
539
540       if (__pos)
541         _S_copy(__r, _M_data(), __pos);
542       if (__s && __len2)
543         _S_copy(__r + __pos, __s, __len2);
544       if (__how_much)
545         _S_copy(__r + __pos + __len2,
546                 _M_data() + __pos + __len1, __how_much);
547       
548       _M_dispose();
549       _M_data(__r);
550       _M_capacity(__new_capacity);
551     }
552
553   template<typename _CharT, typename _Traits, typename _Alloc>
554     void
555     __sso_string_base<_CharT, _Traits, _Alloc>::
556     _M_erase(size_type __pos, size_type __n)
557     {
558       const size_type __how_much = _M_length() - __pos - __n;
559
560       if (__how_much && __n)
561         _S_move(_M_data() + __pos, _M_data() + __pos + __n,
562                 __how_much);
563
564       _M_set_length(_M_length() - __n);
565     }
566
567 _GLIBCXX_END_NAMESPACE
568
569 #endif /* _SSO_STRING_BASE_H */