// bdlma_buffermanager.h -*-C++-*-
// ----------------------------------------------------------------------------
// NOTICE
//
// This component is not up to date with current BDE coding standards, and
// should not be used as an example for new development.
// ----------------------------------------------------------------------------
#ifndef INCLUDED_BDLMA_BUFFERMANAGER
#define INCLUDED_BDLMA_BUFFERMANAGER
#include <bsls_ident.h>
BSLS_IDENT("$Id: $")
//@PURPOSE: Provide a memory manager that manages an external buffer.
//
//@CLASSES:
// bdlma::BufferManager: memory manager that manages an external buffer
//
//@SEE_ALSO: bdlma_bufferimputil, bdlma_bufferedsequentialallocator
//
//@DESCRIPTION: This component provides a memory manager ("buffer manager"),
// 'bdlma::BufferManager', that dispenses heterogeneous memory blocks (of
// varying, user-specified sizes) from an external buffer. A 'BufferManager'
// has a similar interface to a sequential pool in that the two methods
// 'allocate' and 'release' are provided.
//
// In addition to the 'allocate' method, a less safe but faster variation,
// 'allocateRaw', is provided to support memory allocation: If there is
// insufficient memory remaining in the buffer to satisfy an allocation
// request, 'allocate' will return 0 while 'allocateRaw' will result in
// undefined behavior.
//
// The behavior of 'allocate' and 'allocateRaw' illustrates the main difference
// between this buffer manager and a sequential pool. Once the external buffer
// runs out of memory, the buffer manager does not self-replenish, whereas a
// sequential pool will do so.
//
// The 'release' method resets the buffer manager such that the memory within
// the entire external buffer will be made available for subsequent
// allocations. Note that individually allocated memory blocks cannot be
// separately deallocated.
//
// 'bdlma::BufferManager' is typically used for fast and efficient memory
// allocation, when the user knows in advance the maximum amount of memory
// needed.
//
///Usage
///-----
// Suppose that we need to detect whether there are at least 'n' duplicates
// within an array of integers. Furthermore, suppose that speed is a concern
// and we need the fastest possible implementation. A natural solution will be
// to use a hash table. To further optimize for speed, we can use a custom
// memory manager, such as 'bdlma::BufferManager', to speed up memory
// allocations.
//
// First, let's define the structure of a node inside our custom hash table
// structure:
//..
// struct my_Node {
// // This struct represents a node within a hash table.
//
// // DATA
// int d_value; // integer value this node holds
// int d_count; // number of occurrences of this integer value
// my_Node *d_next_p; // pointer to the next node
//
// // CREATORS
// my_Node(int value, my_Node *next);
// // Create a node having the specified 'value' that refers to the
// // specified 'next' node.
// };
//
// // CREATORS
// my_Node::my_Node(int value, my_Node *next)
// : d_value(value)
// , d_count(1)
// , d_next_p(next)
// {
// }
//..
// Note that 'sizeof(my_Node) == 12' when compiled in 32-bit mode, and
// 'sizeof(my_Node) == 16' when compiled in 64-bit mode. This difference
// affects the amount of memory used under different alignment strategies (see
// 'bsls_alignment' for more details on alignment strategies).
//
// We can then define the structure of our specialized hash table used for
// integer counting:
//..
// class my_IntegerCountingHashTable {
// // This class represents a hash table that is used to keep track of the
// // number of occurrences of various integers. Note that this is a
// // highly specialized class that uses a 'bdlma::BufferManager' with
// // sufficient memory for memory allocations.
//
// // DATA
// my_Node **d_nodeArray; // array of 'my_Node' pointers
//
// int d_size; // size of the node array
//
// bdlma::BufferManager *d_buffer; // buffer manager (held, not
// // owned)
//
// public:
// // CLASS METHODS
// static int calculateBufferSize(int tableLength, int numNodes);
// // Return the memory required by a 'my_IntegerCountingHashTable'
// // that has the specified 'tableLength' and 'numNodes'.
//
// // CREATORS
// my_IntegerCountingHashTable(int size, bdlma::BufferManager *buffer);
// // Create a hash table of the specified 'size', using the specified
// // 'buffer' to supply memory. The behavior is undefined unless
// // '0 < size', 'buffer' is non-zero, and 'buffer' has sufficient
// // memory to support all memory allocations required.
//
// // ...
//
// // MANIPULATORS
// int insert(int value);
// // Insert the specified 'value' with a count of 1 into this hash
// // table if 'value' does not currently exist in the hash table, and
// // increment the count for 'value' otherwise. Return the number of
// // occurrences of 'value' in this hash table.
//
// // ...
// };
//..
// The implementation of the rest of 'my_IntegerCountingHashTable' is elided as
// the class method 'calculateBufferSize', constructor, and the 'insert' method
// alone are sufficient to illustrate the use of 'bdlma::BufferManager':
//..
// // CLASS METHODS
// int my_IntegerCountingHashTable::calculateBufferSize(int tableLength,
// int numNodes)
// {
// return static_cast<int>(tableLength * sizeof(my_Node *)
// + numNodes * sizeof(my_Node)
// + bsls::AlignmentUtil::BSLS_MAX_ALIGNMENT);
// }
//..
// Note that, in case the allocated buffer is not aligned, the size calculation
// includes a "fudge" factor equivalent to the maximum alignment requirement of
// the platform.
//..
// // CREATORS
// my_IntegerCountingHashTable::my_IntegerCountingHashTable(
// int size,
// bdlma::BufferManager *buffer)
// : d_size(size)
// , d_buffer(buffer)
// {
// // 'd_buffer' must have sufficient memory to satisfy the allocation
// // request (as specified by the constructor's contract).
//
// d_nodeArray = static_cast<my_Node **>(
// d_buffer->allocate(d_size * sizeof(my_Node *)));
//
// bsl::memset(d_nodeArray, 0, d_size * sizeof(my_Node *));
// }
//
// // MANIPULATORS
// int my_IntegerCountingHashTable::insert(int value)
// {
// // Naive hash function using only mod.
//
// const int hashValue = value % d_size;
// my_Node **tmp = &d_nodeArray[hashValue];
//
// while (*tmp) {
// if ((*tmp)->d_value != value) {
// tmp = &((*tmp)->d_next_p);
// }
// else {
// return ++((*tmp)->d_count); // RETURN
// }
// }
//
// // 'allocate' does not trigger dynamic memory allocation. Therefore,
// // we don't have to worry about exceptions and can use placement 'new'
// // directly with 'allocate'. 'd_buffer' must have sufficient memory to
// // satisfy the allocation request (as specified by the constructor's
// // contract).
//
// *tmp = new(d_buffer->allocate(sizeof(my_Node))) my_Node(value, *tmp);
//
// return 1;
// }
//..
// Note that 'bdlma::BufferManager' is used to allocate memory blocks of
// heterogeneous sizes. In the constructor, memory is allocated for the node
// array. In 'insert', memory is allocated for the nodes.
//
// Finally, in the following 'detectNOccurrences' function, we can use the hash
// table class to detect whether any integer value occurs at least 'n' times
// within a specified array:
//..
// bool detectNOccurrences(int n, const int *array, int length)
// // Return 'true' if any integer value in the specified 'array' having
// // the specified 'length' appears at least the specified 'n' times, and
// // 'false' otherwise.
// {
// const int MAX_SIZE = my_IntegerCountingHashTable::
// calculateBufferSize(length, length);
//..
// We then allocate an external buffer to be used by 'bdlma::BufferManager'.
// Normally, this buffer will be created on the program stack if we know the
// length in advance (for example, if we specify in the contract of this
// function that we only handle arrays having a length of up to 10,000
// integers). However, to make this function more general, we decide to
// allocate the memory dynamically. This approach is still much more efficient
// than using the default allocator, say, to allocate memory for individual
// nodes within 'insert', since we need only a single dynamic allocation,
// versus separate dynamic allocations for every single node:
//..
// bslma::Allocator *allocator = bslma::Default::defaultAllocator();
// char *buffer = static_cast<char *>(allocator->allocate(MAX_SIZE));
//..
// We use a 'bslma::DeallocatorGuard' to automatically deallocate the buffer
// when the function ends:
//..
// bslma::DeallocatorGuard<bslma::Allocator> guard(buffer, allocator);
//
// bdlma::BufferManager bufferManager(buffer, MAX_SIZE);
// my_IntegerCountingHashTable table(length, &bufferManager);
//
// while (--length >= 0) {
// if (n == table.insert(array[length])) {
// return true; // RETURN
// }
// }
//
// return false;
// }
//..
// Note that the calculation of 'MAX_SIZE' assumes natural alignment. If
// maximum alignment is used instead, a larger buffer is needed since each node
// object will then be maximally aligned, which takes up 16 bytes each instead
// of 12 bytes on a 32-bit architecture. On a 64-bit architecture, there will
// be no savings using natural alignment since the size of a node will be 16
// bytes regardless.
#include <bdlscm_version.h>
#include <bsls_alignment.h>
#include <bsls_alignmentutil.h>
#include <bsls_assert.h>
#include <bsls_performancehint.h>
#include <bsls_platform.h>
#include <bsls_review.h>
#include <bsls_types.h>
namespace BloombergLP {
namespace bdlma {
// ===================
// class BufferManager
// ===================
class BufferManager {
// This class implements a buffer manager that dispenses heterogeneous
// blocks of memory (of varying, user-specified sizes) from an external
// buffer whose address and size are optionally supplied at construction.
// If an allocation request exceeds the remaining free memory space in the
// external buffer, the allocation request returns 0 if 'allocate' is used,
// or results in undefined behavior if 'allocateRaw' is used. Note that in
// no event will the buffer manager attempt to deallocate the external
// buffer.
// DATA
char *d_buffer_p; // external buffer (held, not
// owned)
bsls::Types::size_type d_bufferSize; // size (in bytes) of external
// buffer
bsls::Types::IntPtr d_cursor; // offset to next available
// byte in buffer
unsigned char d_alignmentAndMask; // a mask used during the
// alignment calculation
unsigned char d_alignmentOrMask; // a mask used during the
// alignment calculation
private:
// NOT IMPLEMENTED
BufferManager(const BufferManager&);
BufferManager& operator=(const BufferManager&);
public:
// CREATORS
explicit
BufferManager(
bsls::Alignment::Strategy strategy = bsls::Alignment::BSLS_NATURAL);
// Create a buffer manager for allocating memory blocks. Optionally
// specify an alignment 'strategy' used to align allocated memory
// blocks. If 'strategy' is not specified, natural alignment is used.
// A default constructed buffer manager is unable to allocate any
// memory until an external buffer is provided by calling the
// 'replaceBuffer' method.
BufferManager(
char *buffer,
bsls::Types::size_type bufferSize,
bsls::Alignment::Strategy strategy = bsls::Alignment::BSLS_NATURAL);
// Create a buffer manager for allocating memory blocks from the
// specified external 'buffer' having the specified 'bufferSize' (in
// bytes). Optionally specify an alignment 'strategy' used to align
// allocated memory blocks. If 'strategy' is not specified, natural
// alignment is used. The behavior is undefined unless
// '0 < bufferSize' and 'buffer' has at least 'bufferSize' bytes.
~BufferManager();
// Destroy this buffer manager.
// MANIPULATORS
void *allocate(bsls::Types::size_type size);
// Return the address of a contiguous block of memory of the specified
// 'size' (in bytes) on success, according to the alignment strategy
// specified at construction. If 'size' is 0 or the allocation request
// exceeds the remaining free memory space in the external buffer, no
// memory is allocated and 0 is returned.
void *allocateRaw(bsls::Types::size_type size);
// Return the address of a contiguous block of memory of the specified
// 'size' (in bytes) according to the alignment strategy specified at
// construction. The behavior is undefined unless the allocation
// request does not exceed the remaining free memory space in the
// external buffer, '0 < size', and this object is currently managing a
// buffer.
template <class TYPE>
void deleteObjectRaw(const TYPE *object);
// Destroy the specified 'object'. Note that memory associated with
// 'object' is not deallocated because there is no 'deallocate' method
// in 'BufferManager'.
template <class TYPE>
void deleteObject(const TYPE *object);
// Destroy the specified 'object'. Note that this method has the same
// effect as the 'deleteObjectRaw' method (since no deallocation is
// involved), and exists for consistency with a pool interface.
bsls::Types::size_type expand(void *address, bsls::Types::size_type size);
// Increase the amount of memory allocated at the specified 'address'
// from the original 'size' (in bytes) to also include the maximum
// amount remaining in the buffer. Return the amount of memory
// available at 'address' after expanding, or 'size' if the memory at
// 'address' cannot be expanded. This method can only 'expand' the
// memory block returned by the most recent 'allocate' or 'allocateRaw'
// request from this buffer manager, and otherwise has no effect. The
// behavior is undefined unless the memory at 'address' was originally
// allocated by this buffer manager, the size of the memory at
// 'address' is 'size', and 'release' was not called after allocating
// the memory at 'address'.
char *replaceBuffer(char *newBuffer, bsls::Types::size_type newBufferSize);
// Replace the buffer currently managed by this object with the
// specified 'newBuffer' of the specified 'newBufferSize' (in bytes);
// return the address of the previously held buffer, or 0 if this
// object currently manages no buffer. The replaced buffer (if any) is
// removed from the management of this object with no effect on the
// outstanding allocated memory blocks. Subsequent allocations will
// allocate memory from the beginning of the new external buffer. The
// behavior is undefined unless '0 < newBufferSize' and 'newBuffer' has
// at least 'newBufferSize' bytes.
void release();
// Release all memory currently allocated through this buffer manager.
// After this call, the external buffer managed by this object is
// retained. Subsequent allocations will allocate memory from the
// beginning of the external buffer (if any).
void reset();
// Reset this buffer manager to its default constructed state, except
// retain the alignment strategy in effect at the time of construction.
// The currently managed buffer (if any) is removed from the management
// of this object with no effect on the outstanding allocated memory
// blocks.
bsls::Types::size_type truncate(void *address,
bsls::Types::size_type originalSize,
bsls::Types::size_type newSize);
// Reduce the amount of memory allocated at the specified 'address' of
// the specified 'originalSize' (in bytes) to the specified 'newSize'
// (in bytes). Return 'newSize' after truncating, or 'originalSize' if
// the memory at 'address' cannot be truncated. This method can only
// 'truncate' the memory block returned by the most recent 'allocate'
// or 'allocateRaw' request from this object, and otherwise has no
// effect. The behavior is undefined unless the memory at 'address'
// was originally allocated by this buffer manager, the size of the
// memory at 'address' is 'originalSize', 'newSize <= originalSize',
// '0 <= newSize', and 'release' was not called after allocating the
// memory at 'address'.
// ACCESSORS
bsls::Alignment::Strategy alignmentStrategy() const;
// Return the alignment strategy passed to this object at
// construction.
char *buffer() const;
// Return an address providing modifiable access to the buffer
// currently managed by this object, or 0 if this object currently
// manages no buffer.
bsls::Types::size_type bufferSize() const;
// Return the size (in bytes) of the buffer currently managed by this
// object, or 0 if this object currently manages no buffer.
int calculateAlignmentOffsetFromSize(const void *address,
bsls::Types::size_type size) const;
// Return the minimum non-negative integer that, when added to the
// numerical value of the specified 'address', yields the alignment as
// per the 'alignmentStrategy' provided at construction for an
// allocation of the specified 'size'. Note that if '0 == size' and
// natural alignment was provided at construction, the result of this
// method is identical to the result for '0 == size' and maximal
// alignment.
bool hasSufficientCapacity(bsls::Types::size_type size) const;
// Return 'true' if there is sufficient memory space in the buffer to
// allocate a contiguous memory block of the specified 'size' (in
// bytes) after taking the alignment strategy into consideration, and
// 'false' otherwise. The behavior is undefined unless '0 < size', and
// this object is currently managing a buffer.
};
// ============================================================================
// INLINE DEFINITIONS
// ============================================================================
// -------------------
// class BufferManager
// -------------------
// CREATORS
inline
BufferManager::BufferManager(bsls::Alignment::Strategy strategy)
: d_buffer_p(0)
, d_bufferSize(0)
, d_cursor(0)
, d_alignmentAndMask( strategy != bsls::Alignment::BSLS_MAXIMUM
? bsls::AlignmentUtil::BSLS_MAX_ALIGNMENT - 1
: 0)
, d_alignmentOrMask( strategy != bsls::Alignment::BSLS_BYTEALIGNED
? bsls::AlignmentUtil::BSLS_MAX_ALIGNMENT
: 1)
{
}
inline
BufferManager::BufferManager(char *buffer,
bsls::Types::size_type bufferSize,
bsls::Alignment::Strategy strategy)
: d_buffer_p(buffer)
, d_bufferSize(bufferSize)
, d_cursor(0)
, d_alignmentAndMask( strategy != bsls::Alignment::BSLS_MAXIMUM
? bsls::AlignmentUtil::BSLS_MAX_ALIGNMENT - 1
: 0)
, d_alignmentOrMask( strategy != bsls::Alignment::BSLS_BYTEALIGNED
? bsls::AlignmentUtil::BSLS_MAX_ALIGNMENT
: 1)
{
BSLS_ASSERT(buffer);
BSLS_ASSERT(0 < bufferSize);
}
inline
BufferManager::~BufferManager()
{
BSLS_ASSERT(0 <= d_cursor);
BSLS_ASSERT(static_cast<bsls::Types::size_type>(d_cursor) <= d_bufferSize);
BSLS_ASSERT( (0 != d_buffer_p && 0 < d_bufferSize)
|| (0 == d_buffer_p && 0 == d_bufferSize));
}
// MANIPULATORS
inline
void *BufferManager::allocate(bsls::Types::size_type size)
{
BSLS_ASSERT_SAFE(0 <= d_cursor);
BSLS_ASSERT_SAFE(static_cast<bsls::Types::size_type>(d_cursor)
<= d_bufferSize);
char *address = d_buffer_p + d_cursor;
int offset = calculateAlignmentOffsetFromSize(address, size);
bsls::Types::IntPtr cursor = d_cursor + offset + size;
if ( BSLS_PERFORMANCEHINT_PREDICT_LIKELY(
static_cast<bsls::Types::size_type>(cursor) <= d_bufferSize)
&& BSLS_PERFORMANCEHINT_PREDICT_LIKELY(0 < size)) {
d_cursor = cursor;
return address + offset; // RETURN
}
return 0;
}
inline
void *BufferManager::allocateRaw(bsls::Types::size_type size)
{
BSLS_ASSERT_SAFE(0 < size);
BSLS_ASSERT_SAFE(0 <= d_cursor);
BSLS_ASSERT_SAFE(static_cast<bsls::Types::size_type>(d_cursor)
<= d_bufferSize);
BSLS_ASSERT_SAFE(d_buffer_p);
char *address = d_buffer_p + d_cursor;
int offset = calculateAlignmentOffsetFromSize(address, size);
d_cursor = d_cursor + offset + size;
return address + offset;
}
template <class TYPE>
inline
void BufferManager::deleteObjectRaw(const TYPE *object)
{
if (0 != object) {
#ifndef BSLS_PLATFORM_CMP_SUN
object->~TYPE();
#else
const_cast<TYPE *>(object)->~TYPE();
#endif
}
}
template <class TYPE>
inline
void BufferManager::deleteObject(const TYPE *object)
{
deleteObjectRaw(object);
}
inline
char *BufferManager::replaceBuffer(char *newBuffer,
bsls::Types::size_type newBufferSize)
{
BSLS_ASSERT(newBuffer);
BSLS_ASSERT(0 < newBufferSize);
char *oldBuffer = d_buffer_p;
d_buffer_p = newBuffer;
d_bufferSize = newBufferSize;
d_cursor = 0;
return oldBuffer;
}
inline
void BufferManager::release()
{
d_cursor = 0;
}
inline
void BufferManager::reset()
{
d_buffer_p = 0;
d_bufferSize = 0;
d_cursor = 0;
}
// ACCESSORS
inline
bsls::Alignment::Strategy BufferManager::alignmentStrategy() const
{
return 0 == d_alignmentAndMask ? bsls::Alignment::BSLS_MAXIMUM
: 1 == d_alignmentOrMask
? bsls::Alignment::BSLS_BYTEALIGNED
: bsls::Alignment::BSLS_NATURAL;
}
inline
char *BufferManager::buffer() const
{
return d_buffer_p;
}
inline
bsls::Types::size_type BufferManager::bufferSize() const
{
return d_bufferSize;
}
inline
int BufferManager::calculateAlignmentOffsetFromSize(
const void *address,
bsls::Types::size_type size) const
{
bsls::Types::size_type alignment =
(size & static_cast<bsls::Types::size_type>(d_alignmentAndMask)) |
d_alignmentOrMask;
// Clear all but lowest order set bit (note the cast avoids a MSVC warning
// related to negating an unsigned type).
alignment &= -static_cast<bsls::Types::IntPtr>(alignment);
return static_cast<int>(
(alignment - reinterpret_cast<bsls::Types::size_type>(address))
& (alignment - 1));
}
inline
bool BufferManager::hasSufficientCapacity(bsls::Types::size_type size) const
{
BSLS_ASSERT(0 < size);
BSLS_ASSERT(d_buffer_p);
BSLS_ASSERT(0 <= d_cursor);
BSLS_ASSERT(static_cast<bsls::Types::size_type>(d_cursor)
<= d_bufferSize);
char *address = d_buffer_p + d_cursor;
int offset = calculateAlignmentOffsetFromSize(address, size);
return d_cursor + offset + size <= d_bufferSize;
}
} // close package namespace
} // close enterprise namespace
#endif
// ----------------------------------------------------------------------------
// Copyright 2016 Bloomberg Finance L.P.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// ----------------------------- END-OF-FILE ----------------------------------