source: trunk/include/helpers/tree.h@ 35

Last change on this file since 35 was 33, checked in by umoeller, 25 years ago

misc. changes
  • Property svn:eol-style set to CRLF
  • Property svn:keywords set to Author Date Id Revision
File size: 6.6 KB
Line 
1
2/*
3 *@@sourcefile tree.h:
4 * header file for tree.c (red-black balanced binary trees).
5 * See remarks there.
6 */
7
8/*
9 * Written: 97/11/18 Jonathan Schultz <jonathan@imatix.com>
10 * Revised: 98/12/08 Jonathan Schultz <jonathan@imatix.com>
11 *
12 * Copyright (C) 1991-99 iMatix Corporation.
13 * Copyright (C) 2000 Ulrich M”ller.
14 * This file is part of the "XWorkplace helpers" source package.
15 * This is free software; you can redistribute it and/or modify
16 * it under the terms of the GNU General Public License as published
17 * by the Free Software Foundation, in version 2 as it comes in the
18 * "COPYING" file of the XWorkplace main distribution.
19 * This program is distributed in the hope that it will be useful,
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 * GNU General Public License for more details.
23 */
24
25
26/* ----------------------------------------------------------------<Prolog>-
27 Name: sfltree.h
28 Title: Linked-list functions
29 Package: Standard Function Library (SFL)
30
31 Written: 97/11/18 Jonathan Schultz <jonathan@imatix.com>
32 Revised: 98/01/03 Jonathan Schultz <jonathan@imatix.com>
33
34 Synopsis: Provides functions to maintain 'Red-Black' balanced binary
35 trees. You can use these functions to work with trees of any
36 structure. To make this work, all structures must start with
37 the following: "void *left, *right, *parent; TREE_COLOUR
38 colour;". All trees need a pointer to the root of type TREE
39 which should be initialised with treeInit - you can test
40 whether a tree is empty by comparing its root with TREE_NULL.
41 The order of nodes in the tree is determined by calling a
42 node comparison function provided by the caller - this
43 accepts two node pointers and returns zero if the two nodes
44 are equal, -1 if the first is smaller and 1 if the first is
45 larger.
46
47 Copyright: Copyright (c) 1991-99 iMatix Corporation
48 License: This is free software; you can redistribute it and/or modify
49 it under the terms of the SFL License Agreement as provided
50 in the file LICENSE.TXT. This software is distributed in
51 the hope that it will be useful, but without any warranty.
52 ------------------------------------------------------------------</Prolog>-*/
53
54#if __cplusplus
55extern "C" {
56#endif
57
58#ifndef SFLTREE_INCLUDED // Allow multiple inclusions
59 #define SFLTREE_INCLUDED
60
61 #if (!defined OS2_INCLUDED) && (!defined _OS2_H) && (!defined __SIMPLES_DEFINED) // changed V0.9.0 (99-10-22) [umoeller]
62 typedef unsigned long BOOL;
63 #define TRUE (BOOL)1
64 #define FALSE (BOOL)0
65
66 #ifdef __IBMCPP__ // added V0.9.0 (99-10-22) [umoeller]
67 #define APIENTRY _System
68 #endif
69
70 #define __SIMPLES_DEFINED
71 #endif
72
73 // Red-Black tree description
74 typedef enum {BLACK, RED} TREE_COLOUR;
75
76 /*
77 *@@ TREE:
78 * tree node.
79 *
80 * To use the tree functions, all your structures
81 * must have a TREE structure as their first member.
82 *
83 * Example:
84 *
85 + typedef struct _MYTREENODE
86 + {
87 + TREE tree;
88 + char acMyData[1000];
89 + } MYTREENODE, *PMYTREENODE;
90 *
91 * See tree.c for an introduction to the tree functions.
92 */
93
94 typedef struct _TREE
95 {
96 struct _TREE *left,
97 *right,
98 *parent;
99 unsigned long id;
100 TREE_COLOUR colour;
101 } TREE, *PTREE;
102
103 // The tree algorithm needs to know how to sort the data.
104 // It does this using a functions provided by the calling program.
105 // This must return:
106 // -- 0: t1 == t2
107 // -- -1: t1 < t2
108 // -- +1: t1 > t2
109 typedef int (FNTREE_COMPARE_NODES) (TREE *t1, TREE *t2);
110 typedef int (FNTREE_COMPARE_DATA) (TREE *t1, void *pData);
111
112 // Define a function type for use with the tree traversal function
113 typedef void (TREE_PROCESS) (TREE *t, void *pUser);
114
115 // Global variables
116 extern TREE TREE_EMPTY;
117
118 // Function prototypes
119 void treeInit(TREE **root);
120
121 int treeInsertID(TREE **root,
122 TREE *tree,
123 BOOL fAllowDuplicates);
124
125 int treeInsertNode(TREE **root,
126 TREE *tree,
127 FNTREE_COMPARE_NODES *comp,
128 BOOL fAllowDuplicates);
129
130 int treeDelete(TREE **root,
131 TREE *tree);
132
133 void* treeFindEQNode(TREE **root,
134 TREE *nodeFind,
135 FNTREE_COMPARE_NODES *comp);
136 void* treeFindLTNode(TREE **root,
137 TREE *nodeFind,
138 FNTREE_COMPARE_NODES *comp);
139 void* treeFindLENode(TREE **root,
140 TREE *nodeFind,
141 FNTREE_COMPARE_NODES *comp);
142 void* treeFindGTNode(TREE **root,
143 TREE *nodeFind,
144 FNTREE_COMPARE_NODES *comp);
145 void* treeFindGENode(TREE **root,
146 TREE *nodeFind,
147 FNTREE_COMPARE_NODES *comp);
148
149 void* treeFindEQID(TREE **root,
150 unsigned long idFind);
151 void* treeFindLTID(TREE **root,
152 unsigned long idFind);
153 void* treeFindLEID(TREE **root,
154 unsigned long idFind);
155 void* treeFindGTID(TREE **root,
156 unsigned long idFind);
157 void* treeFindGEID(TREE **root,
158 unsigned long idFind);
159
160 void* treeFindEQData(TREE **root,
161 void *pData,
162 FNTREE_COMPARE_DATA *comp);
163
164 void treeTraverse (TREE *tree,
165 TREE_PROCESS *process,
166 void *pUser,
167 int method);
168 void *treeNext (TREE *tree);
169 void *treePrev (TREE *tree);
170 void *treeFirst (TREE *tree);
171 void *treeLast (TREE *tree);
172
173 // Return codes
174 #define TREE_OK 0
175 #define TREE_DUPLICATE 1
176 #define TREE_INVALID_NODE 2
177
178 // Macros
179 #define TREE_NULL &TREE_EMPTY
180
181#endif
182
183#if __cplusplus
184}
185#endif
186
Note: See TracBrowser for help on using the repository browser.