2.4.9.1 The bitmap allocator

The BmAllocator has a bitmap to maintain resource unit allocation status. Resource units are then taken from a simple array contained in the allocator.

<Off bitmap allocator. >= (U->)
// A bitmap based allocator. 
//
class off_BmAllocator : public off_KernAllocator {
private:
  Bitmap b_map;                 // TRUE allocated/ FALSE free
public:
  // To declare uninitialized allocators. 
  off_BmAllocator(natural_t len) : b_map(len) {;}

  // Creates a bitmap allocator.
  off_BmAllocator(off_Exhausted *r, const off_Indexable *idx, 
          void *first,  natural_t len) : 
    off_KernAllocator(r,idx,first,len),
    b_map(len)
 { do_debug(putchar('b')); }

  <Other public methods of off_BmAllocator. >

};

Defines off_BmAllocator (links are to index).

<Off bitmap allocator dependencies. >= (U->) [D->]
#include <flux/types.h>         // for boolean_t natural_t et al.
#include <flux/debug.h>         // for do_debug et al.
#include <klib/bmap.h>          // for Bitmap
#include <klib/KernAllocator.h> // for off_KernAllocator
#include <klib/Indexer.h>       // for off_Indexable

The bitmap allocator provides allocation of pre-specified resource units. If any resource unit (i.e. not an specific one) suffices to satisfy an allocation request, an allocator with a free-list is better (see the next section).

<Other public methods of off_BmAllocator. >= (<-U)
// Allocate (deallocate) units. 
// Return NULL when allocation failed. 
void *allocate(natural_t at);
void  deallocate(void *p);
void  deallocate(natural_t at);

<off_BmAllocator::allocate and deallocate implementation. >= (U->)
// Allocates units. 
// Return NULL when allocation failed. 
void *off_BmAllocator::allocate(natural_t at) 
{ 

  if (b_map.get_bit(at))
    return NULL;
  else {    
    off_BKAllocator::allocate();
    assert(!b_map.get_bit(at));
    b_map.set_bit(at);
    return k_idx->add(k_first,at);
  }
}

// Deallocates units. 
void  off_BmAllocator::deallocate(void *p) 
{
  natural_t pos=k_idx->sub(p,k_first);
  assert(ptr_valid(p));
  off_BKAllocator::deallocate();
  assert(b_map.get_bit(pos));
  b_map.clr_bit(pos);
}

// Deallocates units. 
void  off_BmAllocator::deallocate(natural_t at) 
{

  off_BKAllocator::deallocate();
  assert(b_map.get_bit(at));
  b_map.clr_bit(at);
}

<Off bitmap allocator dependencies. >+= (U->) [<-D]
#include <assert.h>             // for assert

When a type-safe bitmap allocator is needed this template can be instantiated. All instances will share a single copy of the real bitmap operator, though. Note how it simply wraps bitmap methods to provide type-safe operations.

<Off type safe bitmap allocator. >= (U->)
// A type safe bitmap based allocator. 
//
template <class T> 
class off_TBmAllocator : private off_BmAllocator {
public:
  off_TBmAllocator(natural_t len) : off_BmAllocator(len) {;}

  off_TBmAllocator(off_Exhausted *r, const off_Indexable *idx, 
          T *first,  natural_t len ) :
    off_BmAllocator(r, idx, (void*)first, len) {;}

  T * allocate(natural_t at)     { return (T*)off_BmAllocator::allocate(at); }
  void deallocate(T *p) { off_BmAllocator::deallocate((void*)p); }
  void deallocate(natural_t at) { off_BmAllocator::deallocate(at); }
  T *operator +(natural_t at) {
    return (T*)(this->off_KernAllocator::operator+(at));
  }

  natural_t pos(T *p) { return off_KernAllocator::pos((void*)p);  }
  off_BKAllocator::get_nfree;
  off_BKAllocator::get_nalloc;
  off_BKAllocator::get_maxalloc;
  off_BKAllocator::get_num_allocrq;
  off_BKAllocator::get_num_freerq;
  off_BKAllocator::get_length;

  <Other public methods of off_TBmAllocator. >

}; 

Defines off_TBmAllocator (links are to index).

To allow initialization of pre-allocated TBmAllocators an operator new is provided.

<Other public methods of off_TBmAllocator. >= (<-U)
void * operator new(size_t s, void *p) { (void)s; return p; }