Attached is my implementation. It is not very well tested yet so be
careful.
On Tue, 4 Mar 2003, Brian Gray wrote:
> Since we don't know what's stored in the memory buffer (image/audio
> data, chars from an input stream, serialized structs, etc.), it would
> be useful to be able to parameterize the iterators to the increment
> size. And to be able to get multiple input iterators of different size
> on the same buffer. For example, I might want to read in a couple
> structures describing the audio format of a WAV file, then use that
> data to determine the number of bytes in each sample, get that size
> iterator from the end of the header data, and read in the samples.
> This could be enormously helpful, as right now I'm using a union hack
> that allows me to access various pointer sizes on the same data. This
> would be cleaner.
Well I have a special method which allows reinterpreting the memory into an
arbitrary pointer. Which provided some of what you are looking for.
Suggestions for how to do better welcome.
> We'd have to work out failure methods for lack of space if the user
> supplies memory, as we can't grow it. Users are not necessarily
> prepared for push_back to fail with an out_of_memory exception that's
> not a bad_alloc. It's just documentation, but it breaks the
> transparency of the interface and substitutability of the container.
> I'm almost ready to say that it shouldn't use user memory and insist on
> holding its own, but I'd have to think about it more. For example, the
> interface is fundamentally different if reserve() performs a nop or an
> actual reserve depending on which constructor was called. On the other
> hand, with sockets and other input methods reading into a char*, an
> extra data copy is often unacceptable in performance-critical
> applications such as network servers.
That is true. However if a user passes in a memory buffer it is expected
that there is enough room to hold the data. If an arbitrary amount of space
is needed than the memory should not be user defined. Currently my Buffer
aborts if an operations exceeds the available memory. Maybe an exception
is better but I prefer aborts when a precondition or the like is violated.
> Perhaps use of a publicly-inherited policy could accommodate the
> discrepancy by providing reserve() and other methods where they make
> sense and withholding them when they don't. We'll have to look into
> what limits these changes could impose when using the buffer in generic
> algorithms.
That may work if it can be determined at compile time when a fixed amount
of memory is acceptable. Sometimes this can not be determined at compile
time however.
Generic algorithms will work just fine as look as the available memory
isn't being exceeded. When it doesn't, my Buffer as is, will abort.
---
http://kevin.atkinson.dhs.org
// File: buffer.hpp
//
// Copyright (c) 2003
// Kevin Atkinson
//
// Permission to use, copy, modify, distribute and sell this software
// and its documentation for any purpose is hereby granted without
// fee, provided that the above copyright notice appear in all copies
// and that both that copyright notice and this permission notice
// appear in supporting documentation. Kevin Atkinson makes no
// representations about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.
#ifndef DISTRIBNET_BUFFER__HPP
#define DISTRIBNET_BUFFER__HPP
#include <cstring>
namespace distribnet
{
typedef unsigned char byte;
class Buffer
{
public:
typedef byte value;
typedef byte & reference;
typedef const byte & const_reference;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
// Unlike a vector iterators are guaranteed to be pointers. This
// is to make using vector with C functions convenient
typedef byte * iterator;
typedef const byte * const_iterator;
size_type size() const {return end_ - begin_;}
bool empty() const {return begin_ == end_;}
size_type capacity() const {return capacity_ & own_mask_;}
bool own() const {return ~capacity_ & ~own_mask_;}
size_type max_size() const {return own() ? own_mask_ : capacity();}
private:
// The bit to store if the memory is user owned is
// in the high bit of capacity_ to avoid making sizeof(Buffer)
// just over a even power of 2. The performace impact is
// minimial since capacity_ is not used that often.
// Setting capacity_ will reset own() to true.
static const size_type own_mask_ = ~(1ul << (sizeof(size_type)*8-1));
// FIXME: ^ This is unportable for odd ball machines in a
// byte of memory is not 8 bits.
byte * storage_begin() {return storage_end_ - capacity();}
byte * storage_end () {return storage_end_;}
void own(bool v)
{capacity_ = v ? capacity_ & own_mask_ : capacity_ | ~own_mask_;}
public:
void clear() {begin_ = end_ = storage_begin();}
void reset(); // erase all elements and release memory
void swap(Buffer & other);
void assign(const Buffer & other);
Buffer() : begin_(0), end_(0), storage_end_(0), capacity_(0) {}
Buffer(const Buffer &);
Buffer & operator= (const Buffer & other) {assign(other); return *this;}
~Buffer() {reset();}
byte * begin() {return begin_;}
byte * end() {return end_;}
const byte * begin() const {return begin_;}
const byte * end() const {return end_;}
byte * data(size_type pos = 0) {return begin_ + pos;}
byte * data_end() {return end_;}
const byte * data(size_type pos = 0) const {return begin_ + pos;}
const byte * data_end() const {return end_;}
byte & operator[] (size_type n) {return begin_[n];}
const byte & operator[] (size_type n) const {return begin_[n];}
byte & at (size_type n) {return begin_[n];}
const byte & at (size_type n) const {return begin_[n];}
byte & front() {return *begin_;}
byte & back() {return *end_;}
const byte & front() const {return *begin_;}
const byte & back() const {return *end_;}
template <typename U>
U * datap(size_type pos = 0) {return reinterpret_cast<U *>(begin_) + pos;}
template <typename U>
const U * datap(size_type pos = 0) const {return reinterpret_cast<U *>(begin_) +
pos;}
size_type alloc(size_type s) {
size_type old_size = size();
resize(old_size + s);
return old_size;}
void resize(size_type s);
void resize(size_type s, byte v) {
difference_type diff = s - size();
resize(s);
if (s > 0) memset(end_ - diff, v, diff);}
void reserve(size_type s);
void reserve_towards_back(size_type s);
// Shrink the allocated memory so that no space is wasted
bool shrink();
// Set the buffer to point to a specific area of memory
void set(byte * new_begin, byte * new_end);
void set(void * d, size_type s)
{set(static_cast<byte *>(d), static_cast<byte *>(d) + s);}
// Set up the buffer to use a specific region of memory for its
// storage. The results are undefined if a buffer operation needs
// more memory than is provided.
void set_storage(byte * new_begin, byte * new_end);
void set_storage(void * d, size_type s)
{set_storage(static_cast<byte *>(d), static_cast<byte *>(d) + s);}
void align_front();
void align_back();
void prepend (byte d) {
if (storage_begin() < begin_) {begin_ -= 1;}
else {adj_range(begin_, begin_, 1);}
*begin_ = d;}
void prepend (const byte * start, const byte * stop)
{prepend(start, stop - start);}
void prepend (const void * d, size_type s) {
if (storage_begin() + s <= begin_) {begin_ -= s;}
else {adj_range(begin_, begin_, s);}
std::memcpy(begin_, d, s);}
void prepend (size_type s, byte v) {
if (storage_begin() + s <= begin_) {begin_ -= s;}
else {adj_range(begin_, begin_, s);}
std::memset(begin_, v, s);}
void append (byte d) {
if (end_ < storage_end()) {end_ += 1;}
else {adj_range(end_, end_, 1);}
end_[-1] = d;}
void append (size_type s, byte v) {
if (end_ + s <= storage_end()) {end_ += s;}
else {adj_range(end_, end_, s);}
std::memset(end_ - s, v, s);}
void append (const byte * start, const byte * stop)
{append(start, stop - start);}
void append (const void * d, size_type s) {
if (end_ + s <= storage_end()) {end_ += s;}
else {adj_range(end_, end_, s);}
std::memcpy(end_ - s, d, s);}
void assign (const void * d, size_type s) {
reserve(s);
begin_ = storage_begin();
end_ = begin_ + s;
std::memcpy(begin_, d, s);}
void assign (const byte * start, const byte * stop)
{assign(start, stop - start);}
void assign (size_type n, byte v) {
reserve(n);
begin_ = storage_begin();
end_ = begin_ + n;
std::memset(begin_, v, n);}
void push_front (byte d)
{prepend(d);}
void push_back (byte d)
{append(d);}
void pop_front(size_type s = 1)
{begin_ += s;}
void pop_back(size_type s = 1)
{end_ -= s;}
void insert (size_type pos, byte val) {
adj_range(begin_ + pos, begin_ + pos, 1);
begin_[pos] = val;}
void insert (byte * pos, byte val)
{insert(pos - begin_, val);}
void insert (size_type pos, const void * d, size_type s) {
adj_range(begin_ + pos, begin_ + pos, s);
std::memcpy(begin_ + pos, d, s);}
void insert (size_type pos, const byte * start, const byte * stop)
{insert(pos, start, stop - start);}
void insert (byte * pos, const byte * start, const byte * stop)
{insert(pos - begin_, start, stop - start);}
void insert (size_type pos, size_type s, byte val) {
adj_range(begin_ + pos, begin_ + pos, s);
std::memset(begin_ + pos, val, s);}
void insert (byte * pos, size_type s, byte val)
{insert(pos - begin_, s, val);}
// TODO generic template insert
void erase (void * d, size_type s = 1)
{adj_range(static_cast<byte *>(d), static_cast<byte *>(d) + s, 0);}
void erase (byte * start, byte * stop)
{adj_range(start, stop, 0);}
void replace(size_type pos, size_type s, const void * d, size_type ds) {
adj_range(begin_ + pos, begin_ + pos + s, ds);
std::memcpy(begin_ + pos, d, ds);}
void replace(byte * start, byte * stop,
const byte * rstart, const byte * rstop)
{replace(start - begin_, stop - start, rstart, rstop - rstart);}
void replace(byte * start, byte * stop, const void * d, size_type ds)
{replace(start - begin_, stop - start, d, ds);}
private:
// adj_range:
// change the size of the range from start to stop to new_size
// precond: begin() <= start <= stop <= end()
// size() + (intv_size - (stop - start)) <= max_size()
// (ie the new size after the adjustment <= max_size())
void adj_range(byte * start, byte * stop, size_type intv_size);
byte * begin_;
byte * end_;
byte * storage_end_;
size_type capacity_;
};
template <typename T>
class TypedBuffer : public Buffer
{
public:
typedef T Type;
T * operator-> () {return datap<T>();}
const T * operator-> () const {return datap<T>();}
T * ptr () {return datap<T>();}
const T * ptr () const {return datap<T>();}
void * data_block() {return static_cast<void *>(data(sizeof(T)));}
void * data_block() const {return static_cast<const void *>(data(sizeof(T)));}
unsigned int data_block_size() const
{int s = size() - sizeof(T); return s < 0 ? 0 : s;}
int construct() {alloc(sizeof(T)); new(data()) T(); return sizeof(T);}
};
}
#endif
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <algorithm>
#include "buffer.hpp"
namespace distribnet {
using namespace std;
void Buffer::reset() {
if (own() && capacity_) delete[] storage_begin();
begin_ = end_ = 0;
storage_end_ = 0;
capacity_ = 0;
}
void Buffer::swap(Buffer & other) {
std::swap(begin_, other.begin_);
std::swap(end_, other.end_);
std::swap(storage_end_, other.storage_end_);
std::swap(capacity_, other.capacity_);
}
void Buffer::assign(const Buffer & other) {
size_type other_size = other.size();
assert(other_size <= max_size());
if (capacity() < other_size) {
delete[] storage_begin();
begin_ = new byte[other_size];
storage_end_ = begin_ + other_size;
capacity_ = other_size;
}
begin_ = storage_begin();
memcpy(begin_, other.begin_, other_size);
end_ = begin_ + other_size;
}
Buffer::Buffer(const Buffer & other) {
size_type other_size = other.size();
begin_ = new byte[other_size];
storage_end_ = begin_ + other_size;
capacity_ = other_size;
memcpy(begin_, other.begin_, other_size);
end_ = begin_ + other_size;
}
void Buffer::set(byte * new_begin, byte * new_end) {
if (own() && capacity_) delete[] storage_begin();
begin_ = new_begin;
end_ = new_end;
capacity_ = new_end - new_begin;
storage_end_ = new_end;
own(false);
}
void Buffer::set_storage(byte * new_begin, byte * new_end) {
if (own() && capacity_) delete[] storage_begin();
capacity_ = new_end - new_begin;
storage_end_ = new_end;
begin_ = new_begin;
end_ = begin_;
own(false);
}
void Buffer::align_front() {
if (storage_begin() != begin_) {
size_type s = size();
if (s) memmove(storage_begin(), begin_, s);
begin_ = storage_begin();
end_ = begin_ + s;
}
}
void Buffer::align_back() {
if (storage_end() != end_) {
size_type s = size();
if (s) memmove(storage_end() - s, begin_, s);
begin_ = storage_end() - s;
end_ = begin_ + s;
}
}
void Buffer::resize(size_type s) {
assert(s <= max_size());
if (s > capacity())
{
reserve(s);
} else if (begin_ + s > storage_end()) {
memmove(storage_begin(), begin_, size());
begin_ = storage_begin();
}
end_ = begin_ + s;
}
void Buffer::reserve(size_type s)
{
assert(s <= max_size());
if (s > capacity())
{
size_type old_size = size();
byte * new_block = new byte[s];
if (!empty()) memcpy(new_block, begin_, old_size);
if (capacity_) delete[] storage_begin();
capacity_ = s;
begin_ = new_block;
end_ = begin_ + old_size;
storage_end_ = new_block + s;
}
}
void Buffer::reserve_towards_back(size_type s)
{
assert(s <= max_size());
if (s > capacity())
{
size_type old_size = size();
size_type diff = s - old_size;
byte * new_block = new byte[s];
if (!empty()) memcpy(new_block + diff, begin_, old_size);
if (capacity_) delete[] storage_begin();
capacity_ = s;
begin_ = new_block + diff;
end_ = begin_ + old_size;
storage_end_ = new_block + s;
} else {
align_back();
}
}
bool Buffer::shrink()
{
size_type s = size();
if (s == capacity()) return true;
if (!own()) return false;
byte * new_block = new byte[s];
memcpy(new_block, begin_, s);
begin_ = new_block;
end_ = new_block + s;
capacity_ = s;
storage_end_ = end_;
return true;
}
void Buffer::adj_range(byte * start, byte * stop, size_type intv_size) {
assert(begin_ <= start && start <= stop && stop <= end_);
difference_type diff = intv_size - (stop - start);
if (diff == 0) return;
size_type beg_size = start - begin_;
size_type end_size = end_ - stop;
size_type new_size = size() + diff;
assert(new_size <= max_size());
if (diff < 0) {
if (beg_size == 0) {
begin_ -= diff;
} else if (end_size == 0) {
end_ += diff;
} else {
if (beg_size < end_size) {
memmove(begin_ - diff, begin_, beg_size);
begin_ -= diff;
} else {
memmove(stop + diff, stop, end_size);
end_ += diff;
}
}
}
else // diff > 0
{
if (size() + diff <= capacity())
{
difference_type beg_buf = begin_ - storage_begin();
difference_type end_buf = storage_end() - end_;
// Possibilities
// b/e b e action possibilities
// ------------------------
// x F F << 4
// B F T << 1
// E T F << 1
// B T x B 2
// E x T E 2
// M T F B 2
// < T T B 1
// M F T E 2
// > T T E 1
// ------------------- 16
// b/e: Insert in Beginning/Middle/End
// <,>: Beginning Part ? Ending Part (Middle = <|>)
// b: Beggining buffer > size diffrence
// e: Ending buffer > size diffrence
// action: <<: Move Beg Part to Beg of storage, Move End as needed
// B: Move Beg Part Needed amount
// E: Move End Part Needed amount
if ((beg_buf < diff && end_buf < diff)
|| (beg_size == 0 && beg_buf < diff)
|| (end_size == 0 && end_buf < diff))
{
if (beg_size) memmove(storage_begin(), begin_, beg_size);
diff -= beg_size;
if (end_size) memmove(stop + diff, stop, end_size);
begin_ = storage_begin();
end_ = begin_ + new_size;
} else if (beg_size == 0) {
begin_ -= diff;
} else if (end_size == 0) {
end_ += diff;
} else if (diff <= beg_buf && (end_buf < diff || beg_size < end_size)) {
memmove(begin_ - diff, begin_, beg_size);
begin_ = begin_ - diff;
} else if (diff <= end_buf && (beg_buf < diff || beg_size >= end_size)) {
memmove(stop + diff, stop, end_size);
end_ += diff;
} else {
abort(); // this should never happen
}
}
else // size() + diff > capacity
{
size_type alloc_size = size() * 2;
if (alloc_size < 16) alloc_size = 16;
if (alloc_size < new_size) alloc_size = new_size;
byte * new_block = new byte[alloc_size];
if (beg_size)
memcpy(new_block, begin_, beg_size);
if (end_size)
memcpy(new_block + beg_size + intv_size, stop, end_size);
delete[] storage_begin();
capacity_ = alloc_size;
begin_ = new_block;
end_ = begin_ + new_size;
storage_end_ = new_block + alloc_size;
}
}
}
}
#include <iostream>
using namespace std;
using namespace distribnet;
void print_buffer(Buffer & buf)
{
cout << "S=" << buf.size() << " "
<< "C=" << buf.capacity() << " "
<< "M=" << buf.max_size() << " "
<< "D=";
for (size_t i = 0; i != buf.size(); ++i)
cout.put(buf[i]);
cout << endl;
}
int main()
{
Buffer buf, buf2;
for (int i = 0; i != 10; ++i)
{
buf.push_back('a');
}
print_buffer(buf);
buf.swap(buf2);
print_buffer(buf);
print_buffer(buf2);
buf.reset();
print_buffer(buf);
buf.alloc(10);
memcpy(buf.data(), "0123456789", 10);
print_buffer(buf);
int pos = buf.alloc(6);
print_buffer(buf);
memcpy(buf.data(pos), "ABCDEF", 6);
print_buffer(buf);
buf.append("!!!", 3);
buf.prepend("!!!", 3);
print_buffer(buf);
buf.insert(3, "....", 4);
buf.insert(12, "....", 4);
print_buffer(buf);
buf.replace(3, 4, "abcdef", 6);
print_buffer(buf);
buf.pop_front(3);
buf.replace(6, 0, "...", 3);
print_buffer(buf);
buf.replace(6, 3, "??????", 6);
print_buffer(buf);
buf2 = buf;
print_buffer(buf2);
buf.shrink();
print_buffer(buf);
}
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
