bdlma_buffermanager Component

Provide a memory manager that manages an external buffer. More...

Namespaces
namespace	bdlma

Detailed Description

Outline

Purpose
Classes
Description
- Usage

Purpose:: Provide a memory manager that manages an external buffer.

Classes:

bdlma::BufferManager

memory manager that manages an external buffer

See also:: Component bdlma_bufferimputil, Component 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.

Component bdlma_buffermanager [Package bdlma]

Namespaces

Detailed Description

Component bdlma_buffermanager
[Package bdlma]