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