src/basic_buffer.hpp

   1 // Copyright Leandro Lucarella 2008 - 2010.
   2 // Distributed under the Boost Software License, Version 1.0.
   3 // (See accompanying file COPYING or copy at
   4 // http://www.boost.org/LICENSE_1_0.txt)
   5
   6
   7 #ifndef POSIXX_BASIC_BUFFER_HPP_
   8 #define POSIXX_BASIC_BUFFER_HPP_
   9
  10 #include <stdexcept> // std::bad_alloc, std::out_of_range
  11 #include <limits> // std::numeric_limits
  12 #include <tr1/type_traits> // std::tr1::is_integral, true_type, false_type
  13 #include <cstdlib> // std::realloc()
  14 #include <cstring> // std::memcpy(), memset(), memcmp()
  15 #include <cassert> // assert()
  16 #include <cstddef> // std::size_t, ptrdiff_t
  17
  18 namespace posixx {
  19
  20 /**
  21  * A low-level buffer.
  22  *
  23  * This is pretty much like using a plain C-style array using dynamic memory,
  24  * with a STL-ish interface. Only POD should be stored, since no constructors
  25  * or destructors are called.
  26  *
  27  * The buffer will use Allocator (which should be a function with realloc(3)
  28  * semantics) for all storage management.
  29  */
  30 template< typename T, void* (*Allocator)(void*, size_t) = &std::realloc >
  31 struct basic_buffer {
  32
  33         // Types
  34         //////////////////////////////////////////////////////////////////////
  35
  36         ///
  37         typedef T value_type;
  38
  39         ///
  40         typedef value_type& reference;
  41
  42         ///
  43         typedef const value_type& const_reference;
  44
  45         ///
  46         typedef value_type* iterator;
  47
  48         ///
  49         typedef const value_type* const_iterator;
  50
  51         ///
  52         typedef std::size_t size_type;
  53
  54         ///
  55         typedef std::ptrdiff_t difference_type;
  56
  57         ///
  58         typedef value_type* pointer;
  59
  60         ///
  61         typedef const pointer const_pointer;
  62
  63         ///
  64         typedef std::reverse_iterator< iterator > reverse_iterator;
  65
  66         ///
  67         typedef std::reverse_iterator< const_iterator > const_reverse_iterator;
  68
  69
  70         // Construct/Copy/Destroy
  71         //////////////////////////////////////////////////////////////////////
  72
  73         /**
  74          * Creates a buffer of length zero (the default constructor).
  75          */
  76         explicit basic_buffer(): _data(NULL), _size(0) {}
  77
  78         /**
  79          * Creates a buffer with a capacity() of n (uninitialized) elements.
  80          *
  81          * @throw std::bad_alloc
  82          */
  83         explicit basic_buffer(size_type n):
  84                 _data(_allocate(NULL, n * sizeof(value_type))), _size(n)
  85         {
  86         }
  87
  88         /**
  89          * Creates a buffer of length n, containing n copies of value.
  90          *
  91          * @throw std::bad_alloc
  92          */
  93         basic_buffer(size_type n, const_reference value):
  94                 _data(NULL), _size(0)
  95         {
  96                 assign(n, value);
  97                 std::memset(_data, value, n);
  98         }
  99
 100         /**
 101          * Creates a copy of x.
 102          *
 103          * @throw std::bad_alloc
 104          */
 105         basic_buffer(const basic_buffer< T, Allocator >& x):
 106                         _data(_allocate(NULL, x.size() * sizeof(value_type))),
 107                         _size(x.size())
 108         {
 109                 std::memcpy(_data, x.c_array(), x.size());
 110         }
 111
 112         /**
 113          * Creates a buffer of length finish - start, filled with all values
 114          * obtained by dereferencing the InputIterators on the range [start,
 115          * finish).
 116          *
 117          * @throw std::bad_alloc
 118          */
 119         template < typename InputIterator >
 120         basic_buffer(InputIterator start, InputIterator finish):
 121                         _data(NULL), _size(0)
 122         {
 123                 assign(start, finish);
 124         }
 125
 126         /**
 127          * Erases all elements in self then inserts into self a copy of each
 128          * element in x.
 129          *
 130          * Invalidates all references and iterators.
 131          *
 132          * @returns a reference to self.
 133          *
 134          * @throw std::bad_alloc
 135          */
 136         basic_buffer< T, Allocator >& operator = (
 137                         const basic_buffer< T, Allocator >& x)
 138         {
 139                 if (this != &x) {
 140                         resize(x.size());
 141                         std::memcpy(_data, x.c_array(), x.size());
 142                 }
 143                 return *this;
 144         }
 145
 146         /**
 147          * Frees the memory holded by the buffer
 148          */
 149         ~basic_buffer()
 150         { clear(); }
 151
 152
 153         // Iterators
 154         //////////////////////////////////////////////////////////////////////
 155
 156         /**
 157          * Returns a random access iterator that points to the first element.
 158          */
 159         iterator begin()
 160         { return _data; }
 161
 162         /**
 163          * Returns a random access const_iterator that points to the first
 164          * element.
 165          */
 166         const_iterator begin() const
 167         { return _data; }
 168
 169         /**
 170          * Returns a random access iterator that points to the past-the-end
 171          * value.
 172          */
 173         iterator end()
 174         { return _data ? _data + _size : NULL; }
 175
 176         /**
 177          * Returns a random access const_iterator that points to the
 178          * past-the-end value.
 179          */
 180         const_iterator end() const
 181         { return _data ? _data + _size : NULL; }
 182
 183         /**
 184          * Returns a random access reverse_iterator that points to the
 185          * past-the-end value.
 186          */
 187         reverse_iterator rbegin()
 188         { return reverse_iterator(end()); }
 189
 190         /**
 191          * Returns a random access const_reverse_iterator that points to the
 192          * past-the-end value.
 193          */
 194         const_reverse_iterator rbegin() const
 195         { return const_reverse_iterator(end()); }
 196
 197         /**
 198          * Returns a random access reverse_iterator that points to the first
 199          * element.
 200          */
 201         reverse_iterator rend()
 202         { return reverse_iterator(begin()); }
 203
 204         /**
 205          * Returns a random access const_reverse_iterator that points to the
 206          * first element.
 207          */
 208         const_reverse_iterator rend() const
 209         { return const_reverse_iterator(begin()); }
 210
 211
 212         // Capacity
 213         //////////////////////////////////////////////////////////////////////
 214
 215         /**
 216          * Returns the number of elements.
 217          */
 218         size_type size() const
 219         { return _size; }
 220
 221         /**
 222          * Returns size() of the largest possible buffer.
 223          */
 224         size_type max_size() const
 225         { return std::numeric_limits< size_type >::max(); }
 226
 227         /**
 228          * Alters the size of self.
 229          *
 230          * If the new size (sz) is greater than the current size, then
 231          * sz-size() (uninitialized) elements are inserted at the end of the
 232          * buffer. If the new size is smaller than the current capacity, then
 233          * the buffer is truncated by erasing size()-sz elements off the end.
 234          * If sz is equal to capacity then no action is taken.
 235          *
 236          * Invalidates all references and iterators.
 237          *
 238          * @throw std::bad_alloc
 239          */
 240         void resize(size_type sz)
 241         {
 242                 pointer n_data = _allocate(_data, sz * sizeof(value_type));
 243                 _data = n_data;
 244                 _size = sz;
 245         }
 246
 247         /**
 248          * Alters the size of self.
 249          *
 250          * If the new size (sz) is greater than the current size, then
 251          * sz-size() copies of value are inserted at the end of the buffer. If
 252          * the new size is smaller than the current capacity, then the buffer
 253          * is truncated by erasing size()-sz elements off the end.  If sz is
 254          * equal to capacity then no action is taken.
 255          *
 256          * Invalidates all references and iterators.
 257          *
 258          * @throw std::bad_alloc
 259          */
 260         void resize(size_type sz, value_type value)
 261         {
 262                 size_type old_size = size();
 263                 resize(sz);
 264                 if (old_size < sz)
 265                         std::memset(_data + old_size, value, sz - old_size);
 266         }
 267
 268         /**
 269          * Same as size().
 270          */
 271         size_type capacity() const
 272         { return _size; }
 273
 274         /**
 275          * Returns true if the size is zero.
 276          */
 277         bool empty() const
 278         { return !_size; }
 279
 280         /**
 281          * If sz > size() call resize(sz), otherwise do nothing.
 282          *
 283          * Invalidates all references and iterators in the first case.
 284          *
 285          * @throw std::bad_alloc
 286          */
 287         void reserve(size_type sz)
 288         {
 289                 if (sz > size())
 290                         resize(sz);
 291         }
 292
 293
 294         // Element Access
 295         //////////////////////////////////////////////////////////////////////
 296
 297         /**
 298          * Returns a reference to element n of self.
 299          *
 300          * The result can be used as an lvalue. The index n must be between
 301          * 0 and the size less one.
 302          */
 303         reference operator[](size_type n)
 304         { assert(n < _size); return _data[n]; }
 305
 306         /**
 307          * Returns a constant reference to element n of self.
 308          *
 309          * The index n must be between 0 and the size less one.
 310          */
 311         const_reference operator[](size_type n) const
 312         { assert(n < _size); return _data[n]; }
 313
 314         /**
 315          * Returns a reference to element n of self.
 316          *
 317          * The result can be used as an lvalue. If index n is not between
 318          * 0 and the size less one, a std::out_of_range exception.
 319          */
 320         reference at(size_type n)
 321         {
 322                 if (n >= _size)
 323                         throw std::out_of_range("posixx::basic_buffer::at(n)");
 324                 return _data[n];
 325         }
 326
 327         /**
 328          * Returns a constant reference to element n of self.
 329          *
 330          * If index n is not between 0 and the size less one,
 331          * a std::out_of_range exception.
 332          */
 333         const_reference at(size_type n) const
 334         {
 335                 if (n >= _size)
 336                         throw std::out_of_range("posixx::basic_buffer::at(n)");
 337                 return _data[n];
 338         }
 339
 340         /**
 341          * Returns a reference to the first element.
 342          */
 343         reference front()
 344         { assert(_size); return _data[0]; }
 345
 346         /**
 347          * Returns a constant reference to the first element.
 348          */
 349         const_reference front() const
 350         { assert(_size); return _data[0]; }
 351
 352         /**
 353          * Returns a reference to the last element.
 354          */
 355         reference back()
 356         { assert(_size); return _data[_size - 1]; }
 357
 358         /**
 359          * Returns a constant reference to the last element.
 360          */
 361         const_reference back() const
 362         { assert(_size); return _data[_size - 1]; }
 363
 364         /**
 365          * Returns a pointer to a C-style array.
 366          */
 367         pointer c_array()
 368         { return _data; }
 369
 370         /**
 371          * Returns a pointer to a read-only C-style array.
 372          */
 373         const_pointer c_array() const
 374         { return _data; }
 375
 376
 377         // Modifiers
 378         //////////////////////////////////////////////////////////////////////
 379
 380         /**
 381          * Replaces elements with copies of those in the range [start, finish).
 382          *
 383          * The function invalidates all iterators and references to elements in
 384          * *this.
 385          *
 386          * Invalidates all references and iterators.
 387          */
 388         template < typename InputIterator >
 389         void assign(InputIterator start, InputIterator finish)
 390         {
 391                 // Check whether it's an integral type.  If so, it's not an
 392                 // iterator.
 393                 typename std::tr1::is_integral< InputIterator >::type is_int;
 394                 _assign_dispatch(start, finish, is_int);
 395         }
 396
 397         /**
 398          * Replaces elements in *this with n copies of value.
 399          *
 400          * The function invalidates all iterators and references to elements in
 401          * *this.
 402          *
 403          * Invalidates all references and iterators.
 404          */
 405         void assign(size_type n, const_reference value)
 406         {
 407                 resize(n);
 408                 std::memset(_data, value, n);
 409         }
 410
 411         /**
 412          * Efficiently swaps the contents of x and y.
 413          *
 414          * Invalidates all references and iterators.
 415          */
 416         void swap(basic_buffer< T, Allocator >& x)
 417         {
 418                 pointer tmp_data = x._data;
 419                 size_type tmp_size = x._size;
 420                 x._data = _data;
 421                 x._size = _size;
 422                 _data = tmp_data;
 423                 _size = tmp_size;
 424         }
 425
 426         /**
 427          * Deletes all elements from the buffer.
 428          *
 429          * Invalidates all references and iterators.
 430          */
 431         void clear()
 432         {
 433                 _data = _allocate(_data, 0);
 434                 _size = 0;
 435         }
 436
 437 protected:
 438
 439         // The underlying data
 440         pointer _data;
 441
 442         // Size in number of items
 443         std::size_t _size;
 444
 445         // Allocator wrapper for automatic casting
 446         static pointer _allocate(void* ptr, std::size_t sz)
 447         {
 448                 if (ptr == NULL && sz == 0)
 449                         return NULL;
 450                 void* new_ptr = Allocator(ptr, sz);
 451                 if (sz != 0 && new_ptr == NULL)
 452                         throw std::bad_alloc();
 453                 return static_cast< pointer >(new_ptr);
 454         }
 455
 456
 457         /*
 458          * Helper assign functions to disambiguate the Iterator based and the
 459          * N-value copy assign() methods. The last arguments indicates if
 460          * InputIterator is an integral type.
 461          */
 462
 463         // This is the version for the integral types, we should use the
 464         // "regular" N-value copy assign().
 465         template < typename InputIterator >
 466         void _assign_dispatch(InputIterator start, InputIterator finish,
 467                         std::tr1::true_type)
 468         {
 469                 assign(static_cast< size_type >(start),
 470                                 static_cast< value_type >(finish));
 471         }
 472
 473         // This is the version for the real iterators.
 474         template < typename InputIterator >
 475         void _assign_dispatch(InputIterator start, InputIterator finish,
 476                         std::tr1::false_type)
 477         {
 478                 // TODO: provide an efficient version for random iterators
 479                 while (start != finish) {
 480                         resize(size() + 1);
 481                         (*this)[size() - 1] = *start;
 482                         ++start;
 483                 }
 484         }
 485
 486 };
 487
 488 // Nonmember Operators
 489 //////////////////////////////////////////////////////////////////////
 490
 491 /**
 492  * Returns true if x hass the same contents as y.
 493  */
 494 template < typename T, void* (*Allocator)(void*, std::size_t) >
 495 bool operator == (const basic_buffer< T, Allocator >& x,
 496                 const basic_buffer < T, Allocator >& y)
 497 {
 498         if (&x == &y)
 499                 return true;
 500         if (x.size() != y.size())
 501                 return false;
 502         if (x.empty() && y.empty())
 503                 return true;
 504         if (x.empty() || y.empty())
 505                 return false;
 506         int r = std::memcmp(x.c_array(), y.c_array(),
 507                         (x.size() < y.size()) ? x.size() : y.size());
 508         if (r == 0)
 509                 return x.size() == y.size();
 510         return r == 0;
 511 }
 512
 513 /**
 514  * Returns !(x==y).
 515  */
 516 template < typename T, void* (*Allocator)(void*, std::size_t) >
 517 bool operator != (const basic_buffer< T, Allocator >& x,
 518                 const basic_buffer < T, Allocator >& y)
 519 {
 520         return !(x == y);
 521 }
 522
 523 /**
 524  * Returns true if the elements contained in x are lexicographically less than
 525  * the elements contained in y.
 526  */
 527 template < typename T, void* (*Allocator)(void*, std::size_t) >
 528 bool operator < (const basic_buffer< T, Allocator >& x,
 529                 const basic_buffer< T, Allocator >& y)
 530 {
 531         if (&x == &y)
 532                 return false;
 533         if (x.empty() && y.empty())
 534                 return false;
 535         if (x.empty())
 536                 return true;
 537         if (y.empty())
 538                 return false;
 539         int r = std::memcmp(x.c_array(), y.c_array(),
 540                         (x.size() < y.size()) ? x.size() : y.size());
 541         if (r == 0)
 542                 return x.size() < y.size();
 543         return r < 0;
 544 }
 545
 546 /**
 547  * Returns y < x.
 548  */
 549 template < typename T, void* (*Allocator)(void*, std::size_t) >
 550 bool operator > (const basic_buffer< T, Allocator >& x,
 551                 const basic_buffer< T, Allocator >& y)
 552 {
 553         return y < x;
 554 }
 555
 556 /**
 557  * Returns !(y < x).
 558  */
 559 template < typename T, void* (*Allocator)(void*, std::size_t) >
 560 bool operator <= (const basic_buffer< T, Allocator >& x,
 561                 const basic_buffer< T, Allocator >& y)
 562 {
 563         return !(y < x);
 564 }
 565
 566 /**
 567  * Returns !(x < y).
 568  */
 569 template < typename T, void* (*Allocator)(void*, std::size_t) >
 570 bool operator >= (const basic_buffer< T, Allocator >& x,
 571                 const basic_buffer< T, Allocator >& y)
 572 {
 573         return !(x < y);
 574 }
 575
 576
 577 // Specialized Algorithms
 578 //////////////////////////////////////////////////////////////////////
 579
 580 /**
 581  * Exchanges self with x, by swapping all elements.
 582  *
 583  * Invalidates all references and iterators.
 584  */
 585 template < typename T, void* (*Allocator)(void*, std::size_t) >
 586 void swap(basic_buffer< T, Allocator >& x, basic_buffer< T, Allocator >& y)
 587 {
 588         x.swap(y);
 589 }
 590
 591 } // namespace posixx
 592
 593 #endif // POSIXX_BASIC_BUFFER_HPP_