4.2.2 Tree Structure

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

28. <BST table structure 28> =
/* 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 25, 143, and 194.

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]