pool.hpp

CGAL is a collaborative effort of several sites in Europe and Israel. The goal is to make the most i

  // This is a current & previous iterator pair over the memory block list
  details::PODptr<size_type> ptr = list;
  details::PODptr<size_type> prev;

  // This is a current & previous iterator pair over the free memory chunk list
  //  Note that "prev_free" in this case does NOT point to the previous memory
  //  chunk in the free list, but rather the last free memory chunk before the
  //  current block.
  void * free = this->first;
  void * prev_free = 0;

  const size_type partition_size = alloc_size();

  // Search through all the all the allocated memory blocks
  while (ptr.valid())
  {
    // At this point:
    //  ptr points to a valid memory block
    //  free points to either:
    //    0 if there are no more free chunks
    //    the first free chunk in this or some next memory block
    //  prev_free points to either:
    //    the last free chunk in some previous memory block
    //    0 if there is no such free chunk

    // If there are no more free memory chunks, then every remaining
    //  block is allocated out to its fullest capacity, and we can't
    //  release any more memory
    if (free == 0)
      return ret;

    // We have to check all the chunks.  If they are *all* free (i.e., present
    //  in the free list), then we can free the block.
    bool all_chunks_free = true;

    // Iterate 'i' through all chunks in the memory block
    for (char * i = ptr.begin(); i != ptr.end(); i += partition_size)
    {
      // If this chunk is not free
      if (i != free)
      {
        // We won't be able to free this block
        all_chunks_free = false;

        // Abort searching the chunks; we won't be able to free this
        //  block because a chunk is not free.
        break;
      }

      // We do not increment prev_free because we are in the same block
      free = nextof(free);
    }

    const details::PODptr<size_type> next = ptr.next();

    if (!all_chunks_free)
    {
      // Rush through all free chunks from this block
      std::less<void *> lt;
      void * const last = ptr.end() - partition_size;
      do
      {
        free = nextof(free);
      } while (lt(free, last));

      // Increment free one more time and set prev_free to maintain the
      //  invariants:
      //     free points to the first free chunk in some next memory block, or
      //       0 if there is no such chunk.
      //     prev_free points to the last free chunk in this memory block.
      prev_free = free;
      free = nextof(free);
    }
    else
    {
      // All chunks from this block are free

      // Remove block from list
      if (prev.valid())
        prev.next(next);
      else
        list = next;

      // Remove all entries in the free list from this block
      if (prev_free != 0)
        nextof(prev_free) = free;
      else
        this->first = free;

      // And release memory
      UserAllocator::free(ptr.begin());
      ret = true;
    }

    // Increment ptr
    ptr = next;
  }

  return ret;
}

template <typename UserAllocator>
bool pool<UserAllocator>::purge_memory()
{
  details::PODptr<size_type> iter = list;

  if (!iter.valid())
    return false;

  do
  {
    // hold "next" pointer
    const details::PODptr<size_type> next = iter.next();

    // delete the storage
    UserAllocator::free(iter.begin());

    // increment iter
    iter = next;
  } while (iter.valid());

  list.invalidate();
  this->first = 0;

  return true;
}

template <typename UserAllocator>
void * pool<UserAllocator>::malloc_need_resize()
{
  // No memory in any of our storages; make a new storage,
  const size_type partition_size = alloc_size();
  const size_type POD_size = next_size * partition_size +
      details::pool::ct_lcm<sizeof(size_type), sizeof(void *)>::value + sizeof(size_type);
  char * const ptr = UserAllocator::malloc(POD_size);
  if (ptr == 0)
    return 0;
  const details::PODptr<size_type> node(ptr, POD_size);
  next_size <<= 1;

  //  initialize it,
  store().add_block(node.begin(), node.element_size(), partition_size);

  //  insert it into the list,
  node.next(list);
  list = node;

  //  and return a chunk from it.
  return store().malloc();
}

template <typename UserAllocator>
void * pool<UserAllocator>::ordered_malloc_need_resize()
{
  // No memory in any of our storages; make a new storage,
  const size_type partition_size = alloc_size();
  const size_type POD_size = next_size * partition_size +
      details::pool::ct_lcm<sizeof(size_type), sizeof(void *)>::value + sizeof(size_type);
  char * const ptr = UserAllocator::malloc(POD_size);
  if (ptr == 0)
    return 0;
  const details::PODptr<size_type> node(ptr, POD_size);
  next_size <<= 1;

  //  initialize it,
  //  (we can use "add_block" here because we know that
  //  the free list is empty, so we don't have to use
  //  the slower ordered version)
  store().add_block(node.begin(), node.element_size(), partition_size);

  //  insert it into the list,
  //   handle border case
  if (!list.valid() || std::greater<void *>()(list.begin(), node.begin()))
  {
    node.next(list);
    list = node;
  }
  else
  {
    details::PODptr<size_type> prev = list;

    while (true)
    {
      // if we're about to hit the end or
      //  if we've found where "node" goes
      if (prev.next_ptr() == 0
          || std::greater<void *>()(prev.next_ptr(), node.begin()))
        break;

      prev = prev.next();
    }

    node.next(prev.next());
    prev.next(node);
  }

  //  and return a chunk from it.
  return store().malloc();
}

template <typename UserAllocator>
void * pool<UserAllocator>::ordered_malloc(const size_type n)
{
  const size_type partition_size = alloc_size();
  const size_type total_req_size = n * requested_size;
  const size_type num_chunks = total_req_size / partition_size +
      static_cast<bool>(total_req_size % partition_size);

  void * ret = store().malloc_n(num_chunks, partition_size);

  if (ret != 0)
    return ret;

  // Not enougn memory in our storages; make a new storage,
  BOOST_USING_STD_MAX();
  next_size = max BOOST_PREVENT_MACRO_SUBSTITUTION(next_size, num_chunks);
  const size_type POD_size = next_size * partition_size +
      details::pool::ct_lcm<sizeof(size_type), sizeof(void *)>::value + sizeof(size_type);
  char * const ptr = UserAllocator::malloc(POD_size);
  if (ptr == 0)
    return 0;
  const details::PODptr<size_type> node(ptr, POD_size);

  // Split up block so we can use what wasn't requested
  //  (we can use "add_block" here because we know that
  //  the free list is empty, so we don't have to use
  //  the slower ordered version)
  if (next_size > num_chunks)
    store().add_block(node.begin() + num_chunks * partition_size,
        node.element_size() - num_chunks * partition_size, partition_size);

  next_size <<= 1;

  //  insert it into the list,
  //   handle border case
  if (!list.valid() || std::greater<void *>()(list.begin(), node.begin()))
  {
    node.next(list);
    list = node;
  }
  else
  {
    details::PODptr<size_type> prev = list;

    while (true)
    {
      // if we're about to hit the end or
      //  if we've found where "node" goes
      if (prev.next_ptr() == 0
          || std::greater<void *>()(prev.next_ptr(), node.begin()))
        break;

      prev = prev.next();
    }

    node.next(prev.next());
    prev.next(node);
  }

  //  and return it.
  return node.begin();
}

template <typename UserAllocator>
details::PODptr<typename pool<UserAllocator>::size_type>
pool<UserAllocator>::find_POD(void * const chunk) const
{
  // We have to find which storage this chunk is from.
  details::PODptr<size_type> iter = list;
  while (iter.valid())
  {
    if (is_from(chunk, iter.begin(), iter.element_size()))
      return iter;
    iter = iter.next();
  }

  return iter;
}

} // namespace boost

#endif