OpenDDS::DCPS::FreeIndex Class Reference

#include <MemoryPool.h>

Collaboration diagram for OpenDDS::DCPS::FreeIndex:

Public Member Functions
	FreeIndex (FreeHeader *&largest_free)
void	init (FreeHeader *init_free_block)
void	add (FreeHeader *free_block)
void	remove (FreeHeader *free_block, FreeHeader *next_largest)
FreeHeader *	find (size_t size, unsigned char *base)

Static Public Member Functions
static unsigned int	node_index (size_t size)

Private Types
enum	{ min_index_pow = 3, max_index_pow = 12 }
enum	{ min_index = 8, max_index = 4096 }

Private Attributes
size_t	size_
	Number of index nodes. More...
FreeHeader *&	largest_free_
	Memory pool's pointer to largest free block. More...
FreeIndexNode	nodes_ [max_index_pow - min_index_pow+1]
	Index nodes. More...

Friends
class	Test::MemoryPoolTest
class	Test::FreeIndexTest

Detailed Description

Index of free nodes in memory pool. Allows for a faster search of free nodes

Definition at line 118 of file MemoryPool.h.

Member Enumeration Documentation

anonymous enum

anonymous enum

private

Enumerator
min_index_pow
max_index_pow

Definition at line 143 of file MemoryPool.h.

       {
    min_index_pow = 3,
    max_index_pow = 12
  };

anonymous enum

anonymous enum

private

Enumerator
min_index
max_index

Definition at line 147 of file MemoryPool.h.

       {
    min_index = 8,    // 2^^3
    max_index = 4096  // 2^^12
  };

Constructor & Destructor Documentation

FreeIndex()

OpenDDS::DCPS::FreeIndex::FreeIndex ( FreeHeader *&  largest_free )

explicit

Definition at line 161 of file MemoryPool.cpp.

: size_(0)
, largest_free_(largest_free)
{
}

Member Function Documentation

add()

void OpenDDS::DCPS::FreeIndex::add

(

FreeHeader *

free_block

)

Add free block to index

Definition at line 168 of file MemoryPool.cpp.

References node_index(), nodes_, OpenDDS::DCPS::FreeIndexNode::set_ptr(), and OpenDDS::DCPS::AllocHeader::size().

Referenced by init(), and OpenDDS::DCPS::MemoryPool::insert_free_alloc().

{
  unsigned int index = node_index(freed->size());
  FreeIndexNode* node = nodes_ + index;

  // If the node is empty, or if freed is smaller or equal to the node's alloc
  if ((node->ptr() == NULL) || (node->ptr()->size() >= freed->size())) {
    // Use this alloc in the index
    node->set_ptr(freed);
  }
}

find()

FreeHeader * OpenDDS::DCPS::FreeIndex::find	(	size_t	size,
		unsigned char *	base
	)

Find smallest free block of size or larger

Definition at line 209 of file MemoryPool.cpp.

References largest_free_, node_index(), nodes_, OpenDDS::DCPS::FreeIndexNode::ptr(), OpenDDS::DCPS::AllocHeader::size(), size_, and OpenDDS::DCPS::FreeHeader::smaller_free().

Referenced by OpenDDS::DCPS::MemoryPool::insert_free_alloc(), node_index(), and OpenDDS::DCPS::MemoryPool::pool_alloc().

{
  unsigned int index = node_index(search_size);
  FreeIndexNode* index_node = nodes_ + index;

  // Larger or equal to search_size
  FreeHeader* result = NULL;
  if (largest_free_ && (largest_free_->size() >= search_size)) {
    result = largest_free_;

    // Look from here and larger
    while (index_node < nodes_ + size_) {
      if (index_node->ptr() && index_node->ptr()->size() >= search_size) {
        result = index_node->ptr();
        break;
      }
      ++index_node;
    }
  }

  // Now traverse, searching for smaller than result
  while (result) {
    FreeHeader* smaller = result->smaller_free(pool_base);
    if (smaller && smaller->size() >= search_size) {
      result = smaller;
    } else {
      break;
    }
  }

  return result;
}

init()

void OpenDDS::DCPS::FreeIndex::init

(

FreeHeader *

init_free_block

)

Initialize index with initial free block

Definition at line 198 of file MemoryPool.cpp.

References add(), max_index, min_index, nodes_, OpenDDS::DCPS::FreeIndexNode::set_sizes(), and size_.

Referenced by OpenDDS::DCPS::MemoryPool::MemoryPool().

{
  size_t max = std::numeric_limits<size_t>::max();
  for (size_t size = min_index; size <= max_index; size *= 2) {
    nodes_[size_].set_sizes(size, (size == max_index) ? max  :  size*2);
    ++size_;
  }
  add(init_free_block);
}

node_index()

unsigned int OpenDDS::DCPS::FreeIndex::node_index ( size_t  size )

static

Calculate index of node corresponding to a size

Definition at line 243 of file MemoryPool.cpp.

References find(), max_index, max_index_pow, min_index, min_index_pow, nodes_, ACE_OS::printf(), OpenDDS::DCPS::AllocHeader::ptr(), OpenDDS::DCPS::FreeIndexNode::ptr(), OpenDDS::DCPS::AllocHeader::size(), OpenDDS::DCPS::FreeIndexNode::size(), size_, OpenDDS::DCPS::FreeHeader::smaller_free(), and TEST_CHECK.

Referenced by add(), find(), and remove().

{
  // Use shifting to perform log base 2 of size
  //   start by using min + 1 (+1 because min is a power of 2 whch is already
  //   one bit)
  size_t size_copy = size >> (min_index_pow + 1);
  unsigned int index = 0;
  unsigned int max_idx = max_index_pow - min_index_pow;
  while (size_copy && (index < max_idx)) {
    ++index;
    size_copy = size_copy >> 1;
  }
  return index;
}

remove()

void OpenDDS::DCPS::FreeIndex::remove	(	FreeHeader *	free_block,
		FreeHeader *	next_largest
	)

Remove free block from index

Definition at line 181 of file MemoryPool.cpp.

References node_index(), nodes_, OpenDDS::DCPS::FreeIndexNode::set_ptr(), and OpenDDS::DCPS::AllocHeader::size().

Referenced by OpenDDS::DCPS::MemoryPool::remove_free_alloc().

{
  unsigned int index = node_index(free_block->size());
  FreeIndexNode* node = nodes_ + index;

  // If the node points to the free block
  if (node->ptr() == free_block) {
    // If the larger can be used by this node
    if (larger && node->contains(larger->size())) {
      node->set_ptr(larger);
    } else {
      node->set_ptr(NULL);
    }
  }
}

Friends And Related Function Documentation

Test::FreeIndexTest

friend class Test::FreeIndexTest

friend

Definition at line 120 of file MemoryPool.h.

Test::MemoryPoolTest

friend class Test::MemoryPoolTest

friend

Definition at line 119 of file MemoryPool.h.

Member Data Documentation

largest_free_

FreeHeader*& OpenDDS::DCPS::FreeIndex::largest_free_

private

Memory pool's pointer to largest free block.

Definition at line 153 of file MemoryPool.h.

Referenced by find().

nodes_

FreeIndexNode OpenDDS::DCPS::FreeIndex::nodes_[max_index_pow - min_index_pow+1]

private

Index nodes.

Definition at line 154 of file MemoryPool.h.

Referenced by add(), find(), init(), node_index(), and remove().

size_

size_t OpenDDS::DCPS::FreeIndex::size_

private

Number of index nodes.

Definition at line 152 of file MemoryPool.h.

Referenced by find(), init(), and node_index().

---

The documentation for this class was generated from the following files:

• MemoryPool.h
• MemoryPool.cpp