T2C.AR                           BALANCED TREES

The tree struct stores a collection of objects inside a balanced tree. The
syntax is:

   TREE : tree(KEY,DATA)
          access { ACCESS }
          compare { COMPARE };

The type DATA is the type of the objects to be stored. KEY is the type of
the key field in these objects. The ACCESS code shall store the key associated with the DATA typed value data in the variable key. For example:

   key= data -> employee_id;

The COMPARE code shall compare key1 to key2, which are of type KEY. For this example:

   result = key1 - key2;

The result of the comparision shall be stored in the variable result, which
is of int type. So, a full example would look like:

   employee_by_id: tree(int,employee_t)
     access { key= data->employee_id; }
     compare { result= key1-key2; }

The generated functions and types are as follows:

  typedef struct TREE_s TREE_t;
  TREE_t *TREE_new();
  int TREE_find(TREE_t *T, KEY key, DATA *value);
  int TREE_insert(TREE_t *T, DATA data) ;
  int TREE_remove(TREE_t *T, KEY key, DATA *value);
  int TREE_destroy(TREE_t *T,DATA *value);

Anyway, TREE_find finds the given key in the tree, if it's there 1 is returned
and the associated value is stored in *value if value is not null.

TREE_insert returns zero if a value with the same key is already in the tree. Otherwise it inserts the given value and returns one.

TREE_remove returns zero if the given key is not found in the tree. Otherwise,
one is returned and the removed value is stored in *value if value is not
null.

TREE_destroy returns zero if the tree is empty. Otherwise, the least element
is removed from the tree and stored in *value if value is not null. The
return value is 1 in this case. This is useful for deconstructing a tree:

  while(employee_by_id_destroy(employees, &person))
    free(person);
  free(employees);