/home/tom/src/ogc-dev/trunk/nm/frameworks/src/include/nm/nm_rbt.h

/*
 * Copyright (c) 2008 Open Grid Computing, Inc.
 * All rights reserved.
 *
 * Confidential and Proprietary
 */
#ifndef _NM_RBT_T
#define _NM_RBT_T

#ifdef __cplusplus
extern "C" {
#endif

/*
 * Red/Black tree implementation. See
 * http://www.nist.gov/dads/HTML/redblack.html for a definition of
 * this algorithm.
 */

#define NM_RBN_RED      0
#define NM_RBN_BLACK    1

/* Red/Black Node */
struct nm_rbn {
    struct nm_rbn       *left;
    struct nm_rbn       *right;
    struct nm_rbn       *parent;
    int                 color;
    void                *key;
};

/* Comparator callback provided for insert and search operations */
typedef int (*nm_rbn_comparator_t)(void *, void *);

/* Processor for each node during traversal. */
typedef void (*nm_rbn_node_fn)(struct nm_rbn *, void *, int);

struct nm_rbt {
    struct nm_rbn       *root;
    nm_rbn_comparator_t comparator;
};

void nm_rbt_init(struct nm_rbt *t, nm_rbn_comparator_t c);
struct nm_rbn *nm_rbt_find(struct nm_rbt *t, void *k);
struct nm_rbn *nm_rbt_find_min(struct nm_rbt *t);
struct nm_rbn *nm_rbt_find_max(struct nm_rbt *t);
void nm_rbt_ins(struct nm_rbt *t, struct nm_rbn *n);
void nm_rbt_del(struct nm_rbt *t, struct nm_rbn *n);
void nm_rbt_traverse(struct nm_rbt *t, nm_rbn_node_fn f, void *fn_data);
int nm_rbt_is_leaf(struct nm_rbn *n);

#ifdef __cplusplus
}
#endif

#endif

---