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
  10 namespace posixx {
  11
  12 /**
  13  * A low-level buffer.
  14  *
  15  * This is pretty much like using a plain C-style array using dynamic memory,
  16  * with a STL-ish interface.
  17  *
  18  * The buffer will use Allocator (which should be a function with realloc(3)
  19  * semantics) for all storage management.
  20  */
  21 template< void* (*Allocator)(void*, size_t) >
  22 struct basic_buffer {
  23
  24         // Types
  25         //////////////////////////////////////////////////////////////////////
  26
  27         ///
  28         typedef unsigned char value_type; // TODO: use char to be more
  29                                           //       std::string-friendly?
  30
  31         ///
  32         typedef value_type& reference;
  33
  34         ///
  35         typedef const value_type& const_reference;
  36
  37         ///
  38         typedef value_type* iterator; // TODO: make a real iterator
  39
  40         ///
  41         typedef const value_type* const_iterator;
  42
  43         ///
  44         typedef size_t size_type;
  45
  46         ///
  47         typedef ptrdiff_t difference_type;
  48
  49         ///
  50         typedef value_type* pointer;
  51
  52         ///
  53         typedef const pointer const_pointer;
  54
  55         ///
  56         // TODO: reverse iterator
  57         //typedef typename std::reverse_iterator< iterator > reverse_iterator;
  58
  59         ///
  60         //typedef typename std::reverse_iterator< const iterator >
  61         //              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< 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< Allocator >& operator = (
 131                         const basic_buffer< 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 std::reverse_iterator< 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 std::reverse_iterator< const 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 std::reverse_iterator< 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 std::reverse_iterator< const 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< 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         size_t _size;
 438
 439         // Allocator wrapper for automatic casting
 440         static pointer _allocate(void* ptr, 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 < void* (*Allocator)(void*, size_t) >
 489 bool operator == (const basic_buffer< Allocator >& x, 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*, size_t) >
 510 bool operator != (const basic_buffer<Allocator>& x, const basic_buffer <Allocator>& y)
 511 {
 512         return !(x == y);
 513 }
 514
 515 /**
 516  * Returns true if the elements contained in x are lexicographically less than
 517  * the elements contained in y.
 518  */
 519 template < void* (*Allocator)(void*, size_t) >
 520 bool operator < (const basic_buffer< Allocator >& x, const basic_buffer< Allocator >& y)
 521 {
 522         if (&x == &y)
 523                 return false;
 524         if (x.empty() && y.empty())
 525                 return false;
 526         if (x.empty())
 527                 return true;
 528         if (y.empty())
 529                 return false;
 530         int r = std::memcmp(x.c_array(), y.c_array(),
 531                         (x.size() < y.size()) ? x.size() : y.size());
 532         if (r == 0)
 533                 return x.size() < y.size();
 534         return r < 0;
 535 }
 536
 537 /**
 538  * Returns y < x.
 539  */
 540 template < void* (*Allocator)(void*, size_t) >
 541 bool operator > (const basic_buffer< Allocator >& x, const basic_buffer< Allocator >& y)
 542 {
 543         return y < x;
 544 }
 545
 546 /**
 547  * Returns !(y < x).
 548  */
 549 template < void* (*Allocator)(void*, size_t) >
 550 bool operator <= (const basic_buffer< Allocator >& x, const basic_buffer< Allocator >& y)
 551 {
 552         return !(y < x);
 553 }
 554
 555 /**
 556  * Returns !(x < y).
 557  */
 558 template < void* (*Allocator)(void*, size_t) >
 559 bool operator >= (const basic_buffer< Allocator >& x, const basic_buffer< Allocator >& y)
 560 {
 561         return !(x < y);
 562 }
 563
 564
 565 // Specialized Algorithms
 566 //////////////////////////////////////////////////////////////////////
 567
 568 /**
 569  * Exchanges self with x, by swapping all elements.
 570  *
 571  * Invalidates all references and iterators.
 572  */
 573 template < void* (*Allocator)(void*, size_t) >
 574 void swap(basic_buffer< Allocator >& x, basic_buffer< Allocator >& y)
 575 {
 576         x.swap(y);
 577 }
 578
 579 } // namespace posixx
 580
 581 #endif // POSIXX_BASIC_BUFFER_HPP_