File Allocators.h

↰ Parent directory (ADS/memory)

The dynamic storage allocation of Knuth, beyond the book, on a memory of N words simulated by a vector, so that the blocks and their headers can be inspected:

Definition (ADS/memory/Allocators.h)

Detailed Description

  • BoundaryTagAllocator keeps the free blocks on a doubly linked list and gives a request the first block large enough (first fit, Algorithm 2.5A), the smallest one (best fit), or the first one after the last block given (next fit, the roving pointer of Knuth); a block is split if the rest is not too small. Each block has a tag at both ends, its size and whether it is free (the boundary tags of Algorithm 2.5C), so that a freed block merges in O( 1 ) time with its neighbours if they are free: two free blocks are never adjacent;

  • BuddyAllocator (Knowlton, Algorithms 2.5R and 2.5S) splits a memory of :math:` 2^m ` words into blocks of powers of 2, a request taking the smallest power not below it, split from a larger free block by halves; the buddy of the block of size :math:` 2^k ` at the address a is at :math:` a oplus 2^k `, so that a freed block merges with its buddy, if free, and so on upwards, each in O( m ) time; the internal waste is at most half of a block, and two free buddies are never both on the lists.

Both return the address of the first word of the block given, or -1 if no block fits. The contracts [see File Contract.h]: a request is positive, and free() gets an address that allocate() gave and that is in use; the invariants (the free blocks tile the free memory, never adjacent ones for the boundary tags, never two free buddies) are audits. The operations are defined in Allocators.tpp.

    1. Knuth, The Art of Computer Programming, vol. 1, 3rd ed., Addison-Wesley, 1997, section 2.5

    1. Knowlton, A fast storage allocator, Communications of the ACM 8(10), 623-624, 1965, doi:10.1145/365628.365655

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes