4.2.2 Tree Structure [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

The struct bst_table structure ties together all of the data needed to keep track of a table implemented as a binary search tree:

27. <BST table structure 27> =
/* Tree data structure. */
struct bst_table 
  { struct bst_node *bst_root; /* Tree's root. */ bst_comparison_func *bst_compare; /* Comparison function. */ void *bst_param; /* Extra argument to bst_compare. */ struct libavl_allocator *bst_alloc; /* Memory allocator. */ size_t bst_count; /* Number of items in tree. */ unsigned long bst_generation; /* Generation number. */ };

This code is included in 24, 142, and 192.

Most of struct bst_table's members should be familiar. Member bst_root points to the root node of the BST. Together, bst_compare and bst_param specify how items are compared (see Item and Copy Functions). The members of bst_alloc specify how to allocate memory for the BST (see Memory Allocation). The number of items in the BST is stored in bst_count (see Count).

The final member, bst_generation, is a generation number. When a tree is created, it starts out at zero. After that, it is incremented every time the tree is modified in a way that might disturb a traverser. We'll talk more about the generation number later (see Better Iterative Traversal).

Exercises:

*1. Why is it a good idea to include bst_count in struct bst_table? Under what circumstances would it be better to omit it? [answer]