Contents : Demystifying dynamic dispatch : A binary tree node in C

3.1 A binary tree node in C

A node in a binary tree has at most two children, referred to as the left and right nodes. In object-oriented programming, a tree node is naturally modeled as an object.

Implementing such a node in Java is straight-forward, as the Java language and platform come with support for object-oriented programming, automatic memory management and structured error handling (in the form of exceptions). A concise sample implementation, which allows arbitrary data to be associated with a node, is shown in Listing 3.1.

Listing 3.1: BinaryTreeNode.java 
/**
 * Instances of this class represent immutable nodes in a binary
 * tree. Arbitrary data may be associated with a node.
 *
 * @param <D> 
 *   the type of data objects maintained by this node and its
 *   children.
 */
public final class BinaryTreeNode<D>
{
  /**
   * The client-defined data associated with this node, or {@code
   * null} if there is no such data.
   */
  private final D data;

  /**
   * The left node of this node, or {@code null} if there is no such
   * node.
   */
  private final BinaryTreeNode<D> leftNode;

  /**
   * The right node of this node, or {@code null} if there is no such
   * node.
   */
  private final BinaryTreeNode<D> rightNode;

  /**
   * Creates an instance of this class.
   *
   * @param data
   *   the client-defined data of this node, or {@code null}.
   * @param leftNode
   *   the left node of this node, or {@code null}.
   * @param rightNode
   *   the right node of this node, or {@code null}.
   */
  public BinaryTreeNode(D data,
                        BinaryTreeNode<D> leftNode,
                        BinaryTreeNode<D> rightNode)
  {
    this.data = data;
    this.leftNode = leftNode;
    this.rightNode = rightNode;
  }

  /**
   * Returns the client-defined data associated with this node, or
   * {@code null} if there is no such data.
   *
   * @return
   *   the data associated with this node, or {@code null}.
   */
  public D data()
  {
    return data;
  }

  /**
   * Returns the left node of this node, or {@code null} if there is
   * no such node.
   *
   * @return
   *   the left node of this node, or {@code null}.
   */
  public BinaryTreeNode<D> leftNode()
  {
    return leftNode;
  }

  /**
   * Returns the right node of this node, or {@code null} if there is
   * no such node.
   *
   * @return
   *   the right node of this node, or {@code null}.
   */
  public BinaryTreeNode<D> rightNode()
  {
    return rightNode;
  }
}

Implementing the same class in C is more involved, as the object-oriented facets need to be handled explicitly. One facet that is not relevant to this example, however, is dynamic dispatch. As the BinaryTreeNode class does not implement any interfaces, it must be referenced directly (through its class interface). Also, as it is declared final, it may not be extended, and as a result, there is no ambiguity as to what implementation is referred to when the BinaryTreeNode type is referenced. This lack of polymorphic behavior allows the compiler to bind a client statically to the implementation.

Listing 3.2 shows the header file for a C implementation of this class, and Listing 3.3 the implementation.

Listing 3.2: BinaryTreeNode.h 
/**
 * @file
 *
 * This file contains function prototypes for the operations of the
 * <code>BinaryTreeNode</code> class.
 */

#ifndef INCLUSION_GUARD_BINARY_TREE_NODE
#define INCLUSION_GUARD_BINARY_TREE_NODE

#include <stdbool.h>

/**
 * This type represents the <code>BinaryTreeNode</code>
 * class. Instances of this class represent immutable nodes in a
 * binary tree. Arbitrary data may be associated with a node.
 */
typedef struct BinaryTreeNode_s BinaryTreeNode_t;

/**
 * Creates an instance of the <code>BinaryTreeNode</code> class.
 *
 * @param[in] pData
 *   the client-defined data of this node, or <code>NULL</code>.
 * @param[in] pLeftNode
 *   the left node of this node, or <code>NULL</code>.
 * @param[in] pRightNode
 *   the right node of this node, or <code>NULL</code>.
 * @param[out] ppThis
 *   a pointer to the variable which shall hold the instance of the
 *   <code>BinaryTreeNode</code> class. Must not be <code>NULL</code>.
 * @return
 *   <code>true</code> if the operation completes successfully,
 *   <code>false</code> otherwise.
 */
bool BinaryTreeNode_Create(void* pData,
                           BinaryTreeNode_t* pLeftNode,
                           BinaryTreeNode_t* pRightNode,
                           BinaryTreeNode_t** ppThis);


/**
 * Destroys this instance of the <code>BinaryTreeNode</code>
 * class. The children of this node will not be recursively destroyed
 * as a result of calling this operation. If the client-defined data
 * associated with this node has been initialized to point to memory
 * allocated at runtime, this memory must be manually deallocated
 * before calling this operation. This operation always succeeds.
 *
 * @param[in] pThis
 *   an instance of the <code>BinaryTreeNode</code> class. May be
 *   <code>NULL</code>.
 */
void BinaryTreeNode_Destroy(BinaryTreeNode_t* pThis);

/**
 * Returns the client-defined data associated with this node, or
 * <code>NULL</code> if there is no such data.
 *
 * @param[in] pThis
 *   a pointer to the instance data of this
 *   <code>BinaryTreeNode</code> object. Must not be
 *   <code>NULL</code>.
 * @param[out] ppData
 *   a pointer to the variable which shall hold the client-defined
 *   data. Must not be <code>NULL</code>.
 * @return
 *   <code>true</code> if the operation completes successfully,
 *   <code>false</code> otherwise.
 */
bool BinaryTreeNode_Data(BinaryTreeNode_t* pThis,
                         void** ppData);

/**
 * Returns the left node of this node, or <code>NULL</code> if there
 * is no such node.
 *
 * @param[in] pThis
 *   a pointer to the instance data of this
 *   <code>BinaryTreeNode</code> object. Must not be
 *   <code>NULL</code>.
 * @param[out] ppLeftNode
 *   a pointer to the variable which shall hold the reference to the
 *   left node. Must not be <code>NULL</code>.
 * @return
 *   <code>true</code> if the operation completes successfully,
 *   <code>false</code> otherwise.
 */
bool BinaryTreeNode_LeftNode(BinaryTreeNode_t* pThis,
                             BinaryTreeNode_t** ppLeftNode);

/**
 * Returns the right node of this node, or <code>NULL</code> if there
 * is no such node.
 *
 * @param[in] pThis
 *   a pointer to the instance data of this
 *   <code>BinaryTreeNode</code> object. Must not be
 *   <code>NULL</code>.
 * @param[out] ppRightNode
 *   a pointer to the variable which shall hold the reference to the
 *   right node. Must not be <code>NULL</code>.
 * @return
 *   <code>true</code> if the operation completes successfully,
 *   <code>false</code> otherwise.
 */
bool BinaryTreeNode_RightNode(BinaryTreeNode_t* pThis,
                              BinaryTreeNode_t** ppRightNode);

#endif // INCLUSION_GUARD_BINARY_TREE_NODE

Listing 3.3: BinaryTreeNode.c 
/**
 * @file
 *
 * This file contains a class, <code>BinaryTreeNode</code>, instances
 * of which represent immutable nodes in a binary tree. Arbitrary data
 * may be associated with a node.
 */

#include <stdlib.h>
#include <stdbool.h>
#include "BinaryTreeNode.h"

/**
 * This structure represents the instance data of
 * <code>BinaryTreeNode</code> objects.
 */
struct BinaryTreeNode_s
{
  /**
   * Arbitrary data associated with this instance. May be
   * <code>NULL</code>.
   */
  void* pData;

  /**
   * A pointer to the left node pointed to by this node. May be
   * <code>NULL</code>.
   */
  BinaryTreeNode_t* pLeftNode;

  /**
   * A pointer to the right node pointed to by this node. May be
   * <code>NULL</code>.
   */
  BinaryTreeNode_t* pRightNode;
};

bool BinaryTreeNode_Create(void* pData,
                           BinaryTreeNode_t* pLeftNode,
                           BinaryTreeNode_t* pRightNode,
                           BinaryTreeNode_t** ppThis)
{
  BinaryTreeNode_t* pBinaryTreeNodeInstance = NULL;
  bool result = ppThis != NULL;

  if (result)
  {
    pBinaryTreeNodeInstance = malloc(sizeof(BinaryTreeNode_t));
    result = pBinaryTreeNodeInstance != NULL;
  }

  if (result)
  {
    pBinaryTreeNodeInstance->pData = pData;
    pBinaryTreeNodeInstance->pLeftNode = pLeftNode;
    pBinaryTreeNodeInstance->pRightNode = pRightNode;
    *ppThis = pBinaryTreeNodeInstance;
  }
  else if (ppThis != NULL)
  {
    *ppThis = NULL;
  }

  return result;
}

void BinaryTreeNode_Destroy(BinaryTreeNode_t* pThis)
{
  if (pThis != NULL)
  {
    free(pThis);
  }
}

bool BinaryTreeNode_Data(BinaryTreeNode_t* pThis,
                         void** ppData)
{
  bool result = (pThis != NULL) && (ppData != NULL);

  if (result)
  {
    *ppData = pThis->pData;
  }
  else if (ppData != NULL)
  {
    *ppData = NULL;
  }

  return result;
}

bool BinaryTreeNode_LeftNode(BinaryTreeNode_t* pThis,
                             BinaryTreeNode_t** ppLeftNode)
{
  bool result = (pThis != NULL) && (ppLeftNode != NULL);

  if (result)
  {
    *ppLeftNode = pThis->pLeftNode;
  }
  else if (ppLeftNode != NULL)
  {
    *ppLeftNode = NULL;
  }

  return result;
}

bool BinaryTreeNode_RightNode(BinaryTreeNode_t* pThis,
                              BinaryTreeNode_t** ppRightNode)
{
  bool result = (pThis != NULL) && (ppRightNode != NULL);

  if (result)
  {
    *ppRightNode = pThis->pRightNode;
  }
  else if (ppRightNode != NULL)
  {
    *ppRightNode = NULL;
  }

  return result;
}