tree-utils.h File Reference

#include <cdcontainers/data-info.h>
#include <stddef.h>

Go to the source code of this file.

Macros
#define	CDC_MAKE_FIND_NODE_FN(T)
#define	CDC_MAKE_MIN_NODE_FN(T)
#define	CDC_MAKE_MAX_NODE_FN(T)
#define	CDC_MAKE_SUCCESSOR_FN(T)
#define	CDC_MAKE_PREDECESSOR_FN(T)
#define	CDC_MAKE_TREE_HEIGTH_FN(T)

Macro Definition Documentation

CDC_MAKE_FIND_NODE_FN

#define CDC_MAKE_FIND_NODE_FN

(

T

)

Value:

static T cdc_find_tree_node(T node, void *key, cdc_binary_pred_fn_t cmp) \
  {                                                                        \
    while (node != NULL && cdc_not_eq(cmp, node->key, key)) {              \
      if (cmp(key, node->key)) {                                           \
        node = node->left;                                                 \
      } else {                                                             \
        node = node->right;                                                \
      }                                                                    \
    }                                                                      \
    return node;                                                           \
  }

CDC_MAKE_MIN_NODE_FN

#define CDC_MAKE_MIN_NODE_FN

(

T

)

Value:

static T cdc_min_tree_node(T node) \
  {                                  \
    if (node == NULL) {              \
      return NULL;                   \
    }                                \
    while (node->left != NULL) {     \
      node = node->left;             \
    }                                \
    return node;                     \
  }

CDC_MAKE_MAX_NODE_FN

#define CDC_MAKE_MAX_NODE_FN

(

T

)

Value:

static T cdc_max_tree_node(T node) \
  {                                  \
    if (node == NULL) {              \
      return NULL;                   \
    }                                \
    while (node->right != NULL) {    \
      node = node->right;            \
    }                                \
    return node;                     \
  }

CDC_MAKE_SUCCESSOR_FN

#define CDC_MAKE_SUCCESSOR_FN

(

T

)

Value:

static T cdc_tree_successor(T node)        \
  {                                          \
    if (node->right) {                       \
      return cdc_min_tree_node(node->right); \
    }                                        \
    T p = node->parent;                      \
    while (p && node == p->right) {          \
      node = p;                              \
      p = p->parent;                         \
    }                                        \
    return p;                                \
  }

CDC_MAKE_PREDECESSOR_FN

#define CDC_MAKE_PREDECESSOR_FN

(

T

)

Value:

static T cdc_tree_predecessor(T node)     \
  {                                         \
    if (node->left) {                       \
      return cdc_max_tree_node(node->left); \
    }                                       \
    T p = node->parent;                     \
    while (p && node == p->left) {          \
      node = p;                             \
      p = p->parent;                        \
    }                                       \
    return p;                               \
  }

CDC_MAKE_TREE_HEIGTH_FN

#define CDC_MAKE_TREE_HEIGTH_FN

(

T

)

Value:

static size_t cdc_tree_height(T node)       \
  {                                           \
    if (node == NULL) {                       \
      return 0;                               \
    }                                         \
    size_t lh = cdc_tree_height(node->left);  \
    size_t rh = cdc_tree_height(node->right); \
    return CDC_MAX(lh, rh) + 1;               \
  }