src/basic_buffer.hpp

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