cde/programs/dtcm/server/tree.h

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /* $XConsortium: tree.h /main/4 1995/11/09 12:53:31 rswiston $ */
  24 /*
  25  *  (c) Copyright 1993, 1994 Hewlett-Packard Company
  26  *  (c) Copyright 1993, 1994 International Business Machines Corp.
  27  *  (c) Copyright 1993, 1994 Novell, Inc.
  28  *  (c) Copyright 1993, 1994 Sun Microsystems, Inc.
  29  */
  30
  31 #ifndef _TREE_H
  32 #define _TREE_H
  33
  34 #include "ansi_c.h"
  35 #include "data.h"
  36
  37 /*
  38 **  2-3-4 tree, a.k.a. red-black tree
  39 */
  40
  41 typedef enum {red=0, black=1} Color;
  42
  43 typedef struct node {
  44         struct node *llink;
  45         struct node *rlink;
  46         Color   color;
  47         caddr_t data;
  48 } Tree_node;
  49
  50 typedef struct {
  51         Tree_node *root;
  52         caddr_t private;        /* for internal tool state */
  53 } Rb_tree;
  54
  55 extern Rb_tree* rb_create P((_DtCmsGetKeyProc, _DtCmsCompareProc));
  56
  57 extern void rb_destroy P((Rb_tree*, _DtCmsEnumerateProc));
  58
  59 extern int rb_size P((Rb_tree*t));
  60
  61 extern Rb_Status rb_insert P((Rb_tree*, caddr_t data, caddr_t key));
  62
  63 extern Rb_Status rb_insert_node P((Rb_tree*, Tree_node*, caddr_t key));
  64
  65 extern Tree_node * rb_delete P((Rb_tree*, caddr_t key));
  66
  67 extern caddr_t rb_lookup P((Rb_tree*, caddr_t key));
  68
  69 extern caddr_t rb_lookup_next_larger P((Rb_tree*, caddr_t key));
  70
  71 extern caddr_t rb_lookup_next_smaller P((Rb_tree*, caddr_t key));
  72
  73 extern caddr_t rb_lookup_smallest P((Rb_tree*));
  74
  75 extern caddr_t rb_lookup_largest P((Rb_tree*));
  76
  77 extern Rb_Status rb_enumerate_up P((Rb_tree*, _DtCmsEnumerateProc));
  78
  79 extern void rb_enumerate_down P((Rb_tree*, _DtCmsEnumerateProc));
  80
  81 extern Rb_Status rb_check_tree P((Rb_tree *));
  82
  83 #endif