Richard Harter’s World
Site map
Computer Science
September 2010
Email

Defining the storage heap

It isn’t easy to give a good definition of a heap (in the sense of a storage heap) but here is a shot at it.

A heap is a data structure consisting of a pair (H,B) of substructures, operations (split,join), and attribute A where:

H is a set of sequentially addressable elements. That is, the elements form a sequence, each element has an integer associated with it (its address) and the difference between the addresses of successive elements is a constant, w. Let h_i be the address of the initial element of H and h_f be the address of the final element of H.

B is a set of integers such that (1) each element b of B is an address of an element of H, and (2) h_i and h_f are elements of B. From this definition we can define the successor succ(b) of each element (h_f has no successor) and we can order B if we wish.

Given the construction of succ on B we can define block(b) as the set of elements in H such that their addresses a satisfy

    b <= a < succ(a)
It is trivial to prove that the blocks of B divide H into disjoint subsets that cover H.

The attribute A is defined for elements of B. A(b) may have either of two values – free and inuse. A block b is said to be free if A(b) = free and in use if A(b) = inuse.

An address, h, of H is said to be free if A(largest address b in B that is <= h) = free and in use otherwise.

Now for the two operations:

  • The join operator operates on all free elements of b except h_f. It removes the successor of an element of b. The effect is to set
       succ(b) := succ(succ(b))
    
  • The split operator operates on all free element addresses in H that are not element addresses in B. Let s be the argument for split. Split adds s to B. The effect of split is to find the largest address b in B that is smaller than s, and
        set succ(s) := succ(b) 
        and succ(b) := s.  
    
    Note that the successor changes implicitly follow from the definitions of H, B, split, and join.

The above definition covers defining a storage heap. It establishes what blocks are, what the sequence of blocks is, and how to alter the sequence of blocks.

The important thing here is that free lists/allocated lists are not basic abstractions; rather they are derived concepts based on the primitive concept of a block and the operations performed on a set of blocks.


This page was last updated August 22, 2010.

Richard Harter’s World
Site map
Computer Science
September 2010
Email