Class template simple_segregated

Class template simple_segregated_storage

boost::simple_segregated_storage — Simple Segregated Storage is the simplest, and probably the fastest, memory allocation/deallocation algorithm. It is responsible for partitioning a memory block into fixed-size chunks: where the block comes from is determined by the client of the class.

Synopsis

// In header: <boost/pool/simple_segregated_storage.hpp>

template<typename SizeType> 
class simple_segregated_storage {
public:
  // types
  typedef SizeType size_type;

  // construct/copy/destruct
  simple_segregated_storage(const simple_segregated_storage &);
  simple_segregated_storage();
  simple_segregated_storage& operator=(const simple_segregated_storage &);

  // private static functions
  static void * try_malloc_n(void *&, size_type, size_type);

  // protected member functions
  void * find_prev(void *);

  // protected static functions
  static void *& nextof(void *const);

  // public member functions
  void add_block(void *const, const size_type, const size_type);
  void add_ordered_block(void *const, const size_type, const size_type);
  bool empty() const;
  void * malloc();
  void free(void *const);
  void ordered_free(void *const);
  void * malloc_n(size_type, size_type);
  void free_n(void *const, const size_type, const size_type);
  void ordered_free_n(void *const, const size_type, const size_type);

  // public static functions
  static void * segregate(void *, size_type, size_type, void * = 0);
};

Description

Template class simple_segregated_storage controls access to a free list of memory chunks. Please note that this is a very simple class, with preconditions on almost all its functions. It is intended to be the fastest and smallest possible quick memory allocator - e.g., something to use in embedded systems. This class delegates many difficult preconditions to the user (i.e., alignment issues).

An object of type simple_segregated_storage<SizeType> is empty if its free list is empty. If it is not empty, then it is ordered if its free list is ordered. A free list is ordered if repeated calls to malloc() will result in a constantly-increasing sequence of values, as determined by std::less<void *>. A member function is order-preserving if the free list maintains its order orientation (that is, an ordered free list is still ordered after the member function call).

`simple_segregated_storage` public construct/copy/destruct

simple_segregated_storage(const simple_segregated_storage &);

```
simple_segregated_storage();
```
Construct empty storage area.

Postconditions:

empty()

simple_segregated_storage& operator=(const simple_segregated_storage &);

`simple_segregated_storage` private static functions

static void * 
try_malloc_n(void *& start, size_type n, size_type partition_size);

Requires:

(n > 0), (start != 0), (nextof(start) != 0)

Postconditions:

(start != 0) The 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).

`simple_segregated_storage` protected member functions

void * find_prev(void * ptr);

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

	Note
	Note that this function finds the location previous to where ptr would go if it was in the free list. It does not find the entry in the free list before ptr (unless ptr is already in the free list). Specifically, find_prev(0) will return 0, not the last entry in the free list.

Returns:

location previous to where ptr would go if it was in the free list.

`simple_segregated_storage` protected static functions

```
static void *& nextof(void *const ptr);
```
The return value is just *ptr cast to the appropriate type. ptr must not be 0. (For the sake of code readability :)

As an example, let us assume that we want to truncate the free list after the first chunk. That is, we want to set *first to 0; this will result in a free list with only one entry. The normal way to do this is to first cast first to a pointer to a pointer to void, and then dereference and assign (*static_cast<void **>(first) = 0;). This can be done more easily through the use of this convenience function (nextof(first) = 0;).

Returns:

dereferenced pointer.

`simple_segregated_storage` public member functions

```
void add_block(void *const block, const size_type nsz, 
               const size_type npartition_sz);
```
Add block Segregate this block and merge its free list into the free list referred to by "first".

Requires:

Same as segregate.

Postconditions:

!empty()

void add_ordered_block(void *const block, const size_type nsz, 
                       const size_type npartition_sz);

add block (ordered into list) This (slower) version of add_block segregates the block and merges its free list into our free list in the proper order.

```
bool empty() const;
```
Returns:

true only if simple_segregated_storage is empty.
```
void * malloc();
```
Create a chunk.

Requires:

!empty() Increment the "first" pointer to point to the next chunk.
```
void free(void *const chunk);
```
Free a chunk.

Requires:

chunk was previously returned from a malloc() referring to the same free list.

Postconditions:

!empty()
```
void ordered_free(void *const chunk);
```
This (slower) implementation of 'free' places the memory back in the list in its proper order.

Requires:

chunk was previously returned from a malloc() referring to the same free list

Postconditions:

!empty().
```
void * malloc_n(size_type n, size_type partition_size);
```
Attempts to find a contiguous sequence of n partition_sz-sized chunks. If found, removes them all from the free list and returns a pointer to the first. If not found, returns 0. It is strongly recommended (but not required) that the free list be ordered, as this algorithm will fail to find a contiguous sequence unless it is contiguous in the free list as well. Order-preserving. O(N) with respect to the size of the free list.
```
void free_n(void *const chunks, const size_type n, 
            const size_type partition_size);
```
Note

If you're allocating/deallocating n a lot, you should be using an ordered pool.

Requires:

chunks was previously allocated from *this with the same values for n and partition_size.

Postconditions:

!empty()
```
void ordered_free_n(void *const chunks, const size_type n, 
                    const size_type partition_size);
```
Free n chunks from order list.

Requires:

chunks was previously allocated from *this with the same values for n and partition_size.

n should not be zero (n == 0 has no effect).

`simple_segregated_storage` public static functions

static void * 
segregate(void * block, size_type nsz, size_type npartition_sz, 
          void * end = 0);

Segregate block into chunks.

Requires:

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 **.

Requires:	chunk was previously returned from a malloc() referring to the same free list.
Postconditions:	!empty()

	Note
	If you're allocating/deallocating n a lot, you should be using an ordered pool.

Requires:	chunks was previously allocated from *this with the same values for n and partition_size.
Postconditions:	!empty()