whalloc  Update of "whalloc_bt"

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.


Artifact ID: 31bf8afc4e8fc5b0b4bb7f08de8f24b3790dca69
Page Name:whalloc_bt
Date: 2011-09-21 20:37:00
Original User: stephan
Parent: 6d73ec21ab19327a4b55b36cd221ae231fe7bd05

The whalloc_bt Allocator

Header: whalloc.h
Implementation: whalloc_bt.c

The "bt" (bit-table) allocator is this library's primary almost-general-purpose allocator class. (i say "almost" general purposes because it is intended for relatively small applications.)

The class is described and demonstrated in the WhallocBasics page.

Its main features are:

  • Very little overhead required for managing memory: only 2 bytes (fixed) + 2 bits per memory block. Those bits are stored within the same managed memory area from which it allocates memory to the client (as opposed to being dynamically allocated).
  • Fully configurable memory block size (down to 1 byte). The larger the block size, the less overhead (in percent) it needs to reserve for its management.
  • Supports a realloc operation (whalloc_ht does not).
  • Provided it is initialized with alignment in mind, it can guaranty that memory it "allocates" is properly aligned. See the docs for whalloc_bt_init() for details. (Note that not all platforms care about alignment (e.g. x86).)
  • Optionally supports a logging callback function (if not built with NDEBUG defined), allowing the client to trace exactly what memory goes to which allocations. This useful for debuggering and for getting an insight into how the allocator works.

Its main misfeatures are:

  • De/re/allocation of more than a single block has a linear component. Reallocation, in particular, may have multiple N's in its O(N) (as it has to scan for free blocks when growing).
  • Each allocator instance can manage, at most, 2^(WHALLOC_BITNESS) memory, and no single allocation can be larger than 2^(WHALLOC_BITNESS-1). The reason is a side effect of how the managed memory addresses are hashed (but to be honest i've forgotten the specifics).