Data Fields
mapnum_t	left_mapnum

mapnum_t	right_mapnum

offset_t	left_offset

offset_t	right_offset

height_t	height

offset_t	length

size_t	user_length

Detailed Description

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.

left_mapnum and left_offset is used to compute the address of the left node as in

   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;

Definition at line 131 of file arena.h.

Field Documentation

height_t seg_header::height

height of this node in the AVL tree. Used to balance the tree. height is zero at a leaf node and -1 at a NULL node.

Definition at line 150 of file arena.h.

mapnum_t seg_header::left_mapnum

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.

Definition at line 142 of file arena.h.

offset_t seg_header::left_offset

address offsets from the top of the mapping to the left and right nodes in the AVL tree in units of CHUNKS. left_offset will be zero if there is no left node, and right_offset will be zero if there is no right node.

Definition at line 147 of file arena.h.

offset_t seg_header::length

total length in units of CHUNKS of the segment including all structs and all padding. Length in bytes = length * CHUNK.

Definition at line 153 of file arena.h.

Referenced by shm_arena_print_list(), and shm_name().

mapnum_t seg_header::right_mapnum

as already explained

Definition at line 142 of file arena.h.

offset_t seg_header::right_offset

as already explained

Definition at line 147 of file arena.h.

size_t seg_header::user_length