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.
FreeHeader *&	largest_free_
	Memory pool's pointer to largest free block.
FreeIndexNode	nodes_ [max_index_pow-min_index_pow+1]
	Index nodes.
Friends
class	::MemoryPoolTest
class	::FreeIndexTest

Detailed Description

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

Definition at line 117 of file MemoryPool.h.

Member Enumeration Documentation

anonymous enum [private]

Enumerator:

min_index_pow
max_index_pow

Definition at line 142 of file MemoryPool.h.

00142        {
00143     min_index_pow = 3,
00144     max_index_pow = 12
00145   };

anonymous enum [private]

Enumerator:

min_index
max_index

Definition at line 146 of file MemoryPool.h.

00146        {
00147     min_index = 8,    // 2^^3
00148     max_index = 4096  // 2^^12
00149   };

Constructor & Destructor Documentation

OpenDDS::DCPS::FreeIndex::FreeIndex ( FreeHeader *& largest_free ) [explicit]

Definition at line 161 of file MemoryPool.cpp.

00162 : size_(0)
00163 , largest_free_(largest_free)
00164 {
00165 }

Member Function Documentation

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().

00169 {
00170   unsigned int index = node_index(freed->size());
00171   FreeIndexNode* node = nodes_ + index;
00172 
00173   // If the node is empty, or if freed is smaller or equal to the node's alloc
00174   if ((node->ptr() == NULL) || (node->ptr()->size() >= freed->size())) {
00175     // Use this alloc in the index
00176     node->set_ptr(freed);
00177   }
00178 }

Here is the call graph for this function:

Here is the caller graph for this function:

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(), and OpenDDS::DCPS::MemoryPool::pool_alloc().

00210 {
00211   unsigned int index = node_index(search_size);
00212   FreeIndexNode* index_node = nodes_ + index;
00213 
00214   // Larger or equal to search_size
00215   FreeHeader* result = NULL;
00216   if (largest_free_ && (largest_free_->size() >= search_size)) {
00217     result = largest_free_;
00218 
00219     // Look from here and larger
00220     while (index_node < nodes_ + size_) {
00221       if (index_node->ptr() && index_node->ptr()->size() >= search_size) {
00222         result = index_node->ptr();
00223         break;
00224       }
00225       ++index_node;
00226     }
00227   }
00228 
00229   // Now traverse, searching for smaller than result
00230   while (result) {
00231     FreeHeader* smaller = result->smaller_free(pool_base);
00232     if (smaller && smaller->size() >= search_size) {
00233       result = smaller;
00234     } else {
00235       break;
00236     }
00237   }
00238 
00239   return result;
00240 }

Here is the call graph for this function:

Here is the caller graph for this function:

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(), size, and size_.

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

00199 {
00200   size_t max = std::numeric_limits<size_t>::max();
00201   for (size_t size = min_index; size <= max_index; size *= 2) {
00202     nodes_[size_].set_sizes(size, (size == max_index) ? max  :  size*2);
00203     ++size_;
00204   }
00205   add(init_free_block);
00206 }

Here is the call graph for this function:

Here is the caller graph for this function:

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 max_index_pow, and min_index_pow.

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

00244 {
00245   // Use shifting to perform log base 2 of size
00246   //   start by using min + 1 (+1 because min is a power of 2 whch is already
00247   //   one bit)
00248   size_t size_copy = size >> (min_index_pow + 1);
00249   unsigned int index = 0;
00250   unsigned int max_idx = max_index_pow - min_index_pow;
00251   while (size_copy && (index < max_idx)) {
00252     ++index;
00253     size_copy = size_copy >> 1;
00254   }
00255   return index;
00256 }

Here is the caller graph for this function:

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().

00182 {
00183   unsigned int index = node_index(free_block->size());
00184   FreeIndexNode* node = nodes_ + index;
00185 
00186   // If the node points to the free block
00187   if (node->ptr() == free_block) {
00188     // If the larger can be used by this node
00189     if (larger && node->contains(larger->size())) {
00190       node->set_ptr(larger);
00191     } else {
00192       node->set_ptr(NULL);
00193     }
00194   }
00195 }