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)

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.