// Copyright (C) 2000, 2001 Stephen Cleary | |
// | |
// Distributed under the Boost Software License, Version 1.0. (See | |
// accompanying file LICENSE_1_0.txt or copy at | |
// http://www.boost.org/LICENSE_1_0.txt) | |
// | |
// See http://www.boost.org for updates, documentation, and revision history. | |
#ifndef BOOST_SIMPLE_SEGREGATED_STORAGE_HPP | |
#define BOOST_SIMPLE_SEGREGATED_STORAGE_HPP | |
// std::greater | |
#include <functional> | |
#include <boost/pool/poolfwd.hpp> | |
namespace boost { | |
template <typename SizeType> | |
class simple_segregated_storage | |
{ | |
public: | |
typedef SizeType size_type; | |
private: | |
simple_segregated_storage(const simple_segregated_storage &); | |
void operator=(const simple_segregated_storage &); | |
// pre: (n > 0), (start != 0), (nextof(start) != 0) | |
// post: (start != 0) | |
static void * try_malloc_n(void * & start, size_type n, | |
size_type partition_size); | |
protected: | |
void * first; | |
// Traverses the free list referred to by "first", | |
// and returns the iterator previous to where | |
// "ptr" would go if it was in the free list. | |
// Returns 0 if "ptr" would go at the beginning | |
// of the free list (i.e., before "first") | |
void * find_prev(void * ptr); | |
// for the sake of code readability :) | |
static void * & nextof(void * const ptr) | |
{ return *(static_cast<void **>(ptr)); } | |
public: | |
// Post: empty() | |
simple_segregated_storage() | |
:first(0) { } | |
// pre: npartition_sz >= sizeof(void *) | |
// npartition_sz = sizeof(void *) * i, for some integer i | |
// nsz >= npartition_sz | |
// block is properly aligned for an array of object of | |
// size npartition_sz and array of void * | |
// The requirements above guarantee that any pointer to a chunk | |
// (which is a pointer to an element in an array of npartition_sz) | |
// may be cast to void **. | |
static void * segregate(void * block, | |
size_type nsz, size_type npartition_sz, | |
void * end = 0); | |
// Same preconditions as 'segregate' | |
// Post: !empty() | |
void add_block(void * const block, | |
const size_type nsz, const size_type npartition_sz) | |
{ | |
// Segregate this block and merge its free list into the | |
// free list referred to by "first" | |
first = segregate(block, nsz, npartition_sz, first); | |
} | |
// Same preconditions as 'segregate' | |
// Post: !empty() | |
void add_ordered_block(void * const block, | |
const size_type nsz, const size_type npartition_sz) | |
{ | |
// This (slower) version of add_block segregates the | |
// block and merges its free list into our free list | |
// in the proper order | |
// Find where "block" would go in the free list | |
void * const loc = find_prev(block); | |
// Place either at beginning or in middle/end | |
if (loc == 0) | |
add_block(block, nsz, npartition_sz); | |
else | |
nextof(loc) = segregate(block, nsz, npartition_sz, nextof(loc)); | |
} | |
// default destructor | |
bool empty() const { return (first == 0); } | |
// pre: !empty() | |
void * malloc BOOST_PREVENT_MACRO_SUBSTITUTION() | |
{ | |
void * const ret = first; | |
// Increment the "first" pointer to point to the next chunk | |
first = nextof(first); | |
return ret; | |
} | |
// pre: chunk was previously returned from a malloc() referring to the | |
// same free list | |
// post: !empty() | |
void free BOOST_PREVENT_MACRO_SUBSTITUTION(void * const chunk) | |
{ | |
nextof(chunk) = first; | |
first = chunk; | |
} | |
// pre: chunk was previously returned from a malloc() referring to the | |
// same free list | |
// post: !empty() | |
void ordered_free(void * const chunk) | |
{ | |
// This (slower) implementation of 'free' places the memory | |
// back in the list in its proper order. | |
// Find where "chunk" goes in the free list | |
void * const loc = find_prev(chunk); | |
// Place either at beginning or in middle/end | |
if (loc == 0) | |
(free)(chunk); | |
else | |
{ | |
nextof(chunk) = nextof(loc); | |
nextof(loc) = chunk; | |
} | |
} | |
// Note: if you're allocating/deallocating n a lot, you should | |
// be using an ordered pool. | |
void * malloc_n(size_type n, size_type partition_size); | |
// pre: chunks was previously allocated from *this with the same | |
// values for n and partition_size | |
// post: !empty() | |
// Note: if you're allocating/deallocating n a lot, you should | |
// be using an ordered pool. | |
void free_n(void * const chunks, const size_type n, | |
const size_type partition_size) | |
{ | |
if(n != 0) | |
add_block(chunks, n * partition_size, partition_size); | |
} | |
// pre: chunks was previously allocated from *this with the same | |
// values for n and partition_size | |
// post: !empty() | |
void ordered_free_n(void * const chunks, const size_type n, | |
const size_type partition_size) | |
{ | |
if(n != 0) | |
add_ordered_block(chunks, n * partition_size, partition_size); | |
} | |
}; | |
template <typename SizeType> | |
void * simple_segregated_storage<SizeType>::find_prev(void * const ptr) | |
{ | |
// Handle border case | |
if (first == 0 || std::greater<void *>()(first, ptr)) | |
return 0; | |
void * iter = first; | |
while (true) | |
{ | |
// if we're about to hit the end or | |
// if we've found where "ptr" goes | |
if (nextof(iter) == 0 || std::greater<void *>()(nextof(iter), ptr)) | |
return iter; | |
iter = nextof(iter); | |
} | |
} | |
template <typename SizeType> | |
void * simple_segregated_storage<SizeType>::segregate( | |
void * const block, | |
const size_type sz, | |
const size_type partition_sz, | |
void * const end) | |
{ | |
// Get pointer to last valid chunk, preventing overflow on size calculations | |
// The division followed by the multiplication just makes sure that | |
// old == block + partition_sz * i, for some integer i, even if the | |
// block size (sz) is not a multiple of the partition size. | |
char * old = static_cast<char *>(block) | |
+ ((sz - partition_sz) / partition_sz) * partition_sz; | |
// Set it to point to the end | |
nextof(old) = end; | |
// Handle border case where sz == partition_sz (i.e., we're handling an array | |
// of 1 element) | |
if (old == block) | |
return block; | |
// Iterate backwards, building a singly-linked list of pointers | |
for (char * iter = old - partition_sz; iter != block; | |
old = iter, iter -= partition_sz) | |
nextof(iter) = old; | |
// Point the first pointer, too | |
nextof(block) = old; | |
return block; | |
} | |
// The following function attempts to find n contiguous chunks | |
// of size partition_size in the free list, starting at start. | |
// If it succeds, it returns the last chunk in that contiguous | |
// sequence, so that the sequence is known by [start, {retval}] | |
// If it fails, it does do either because it's at the end of the | |
// free list or hits a non-contiguous chunk. In either case, | |
// it will return 0, and set start to the last considered | |
// chunk. You are at the end of the free list if | |
// nextof(start) == 0. Otherwise, start points to the last | |
// chunk in the contiguous sequence, and nextof(start) points | |
// to the first chunk in the next contiguous sequence (assuming | |
// an ordered free list) | |
template <typename SizeType> | |
void * simple_segregated_storage<SizeType>::try_malloc_n( | |
void * & start, size_type n, const size_type partition_size) | |
{ | |
void * iter = nextof(start); | |
while (--n != 0) | |
{ | |
void * next = nextof(iter); | |
if (next != static_cast<char *>(iter) + partition_size) | |
{ | |
// next == 0 (end-of-list) or non-contiguous chunk found | |
start = iter; | |
return 0; | |
} | |
iter = next; | |
} | |
return iter; | |
} | |
template <typename SizeType> | |
void * simple_segregated_storage<SizeType>::malloc_n(const size_type n, | |
const size_type partition_size) | |
{ | |
if(n == 0) | |
return 0; | |
void * start = &first; | |
void * iter; | |
do | |
{ | |
if (nextof(start) == 0) | |
return 0; | |
iter = try_malloc_n(start, n, partition_size); | |
} while (iter == 0); | |
void * const ret = nextof(start); | |
nextof(start) = nextof(iter); | |
return ret; | |
} | |
} // namespace boost | |
#endif |