bdlma_buffermanager

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Usage
    • Example 1: Basic Usage

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

This section illustrates intended use of this component.

Example 1: Basic 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.