the header used by each segment
Each free segment is a node in a binary tree. Each allocated segment is a node in a binary tree. There are two trees: the free tree and the allocated tree. In particular they are both AVL Trees. See http://www.5trees.com/trees/source/Trees.html, http://en.wikipedia.org/wiki/AVL_tree, and http://www.nist.gov/dads/HTML/avltree.html.
We wish to minimize the size of this structure hence we have the defined types in it which may be changed if need arises.
struct arena *a; struct seg_header *h; char *left_addr;
code to setup a and h
. . . left_addr = ((char *) a->start[h->left_mapnum]) + h->left_offset*CHUNK;
mapping numbers start at 0 and increase.
pairs with left_mapnum and left_offset form the a pointer to the left node in the tree. pairs with right_mapnum and right_offset form the a pointer to the right node in the tree. The value of left_mapnum should be ignored if there is no left node. The value of right_mapnum should be ignored if there is no right node.