cde/programs/dtcm/server/tree.h

   1 /* $XConsortium: tree.h /main/4 1995/11/09 12:53:31 rswiston $ */
   2 /*
   3  *  (c) Copyright 1993, 1994 Hewlett-Packard Company
   4  *  (c) Copyright 1993, 1994 International Business Machines Corp.
   5  *  (c) Copyright 1993, 1994 Novell, Inc.
   6  *  (c) Copyright 1993, 1994 Sun Microsystems, Inc.
   7  */
   8
   9 #ifndef _TREE_H
  10 #define _TREE_H
  11
  12 #include "ansi_c.h"
  13 #include "data.h"
  14
  15 /*
  16 **  2-3-4 tree, a.k.a. red-black tree
  17 */
  18
  19 typedef enum {red=0, black=1} Color;
  20
  21 typedef struct node {
  22         struct node *llink;
  23         struct node *rlink;
  24         Color   color;
  25         caddr_t data;
  26 } Tree_node;
  27
  28 typedef struct {
  29         Tree_node *root;
  30         caddr_t private;        /* for internal tool state */
  31 } Rb_tree;
  32
  33 extern Rb_tree* rb_create P((_DtCmsGetKeyProc, _DtCmsCompareProc));
  34
  35 extern void rb_destroy P((Rb_tree*, _DtCmsEnumerateProc));
  36
  37 extern int rb_size P((Rb_tree*t));
  38
  39 extern Rb_Status rb_insert P((Rb_tree*, caddr_t data, caddr_t key));
  40
  41 extern Rb_Status rb_insert_node P((Rb_tree*, Tree_node*, caddr_t key));
  42
  43 extern Tree_node * rb_delete P((Rb_tree*, caddr_t key));
  44
  45 extern caddr_t rb_lookup P((Rb_tree*, caddr_t key));
  46
  47 extern caddr_t rb_lookup_next_larger P((Rb_tree*, caddr_t key));
  48
  49 extern caddr_t rb_lookup_next_smaller P((Rb_tree*, caddr_t key));
  50
  51 extern caddr_t rb_lookup_smallest P((Rb_tree*));
  52
  53 extern caddr_t rb_lookup_largest P((Rb_tree*));
  54
  55 extern Rb_Status rb_enumerate_up P((Rb_tree*, _DtCmsEnumerateProc));
  56
  57 extern void rb_enumerate_down P((Rb_tree*, _DtCmsEnumerateProc));
  58
  59 extern Rb_Status rb_check_tree P((Rb_tree *));
  60
  61 #endif