OpenDDS::DCPS::FreeIndex Class Reference

#include <MemoryPool.h>

Collaboration diagram for OpenDDS::DCPS::FreeIndex:

[legend]List of all members.

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
	min_index_pow = 3
	max_index_pow = 12
	min_index = 8
	max_index = 4096
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 115 of file MemoryPool.h.

---

Member Enumeration Documentation

anonymous enum [private]

Enumerator:

min_index_pow
max_index_pow

Definition at line 140 of file MemoryPool.h.

       {
    min_index_pow = 3,
    max_index_pow = 12
  };

anonymous enum [private]

Enumerator:

min_index
max_index

Definition at line 144 of file MemoryPool.h.

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

---

Constructor & Destructor Documentation

OpenDDS::DCPS::FreeIndex::FreeIndex

(

FreeHeader *&

largest_free

)

[explicit]

Definition at line 159 of file MemoryPool.cpp.

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

---

Member Function Documentation

void OpenDDS::DCPS::FreeIndex::add

(

FreeHeader *

free_block

)

Add free block to index

Definition at line 166 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);
  }
}

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

Find smallest free block of size or larger

Definition at line 207 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().

{
  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;
}

void OpenDDS::DCPS::FreeIndex::init

(

FreeHeader *

init_free_block

)

Initialize index with initial free block

Definition at line 196 of file MemoryPool.cpp.

References add(), max_index, min_index, nodes_, 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);
}

unsigned int OpenDDS::DCPS::FreeIndex::node_index

(

size_t

size

)

[static]

Calculate index of node corresponding to a size

Definition at line 241 of file MemoryPool.cpp.

References max_index_pow, and min_index_pow.

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;
}

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

Remove free block from index

Definition at line 179 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

friend class ::FreeIndexTest [friend]

Definition at line 117 of file MemoryPool.h.

friend class ::MemoryPoolTest [friend]

Definition at line 116 of file MemoryPool.h.

---

Member Data Documentation

FreeHeader*& OpenDDS::DCPS::FreeIndex::largest_free_ [private]

Memory pool's pointer to largest free block.

Definition at line 150 of file MemoryPool.h.

Referenced by find().

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

Index nodes.

Definition at line 151 of file MemoryPool.h.

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

size_t OpenDDS::DCPS::FreeIndex::size_ [private]

Number of index nodes.

Definition at line 149 of file MemoryPool.h.

Referenced by find(), and init().

---

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

• MemoryPool.h
• MemoryPool.cpp

---