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

Last change on this file since 54 was 54, checked in by umoeller, 24 years ago

Misc changes.
  • Property svn:eol-style set to CRLF
  • Property svn:keywords set to Author Date Id Revision
File size: 6.8 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 #if defined(__IBMC__) || defined(__IBMCPP__)
104 #define TREEENTRY _Optlink
105 #else
106 // EMX or whatever: doesn't know calling conventions
107 #define TREENTRY
108 #endif
109
110 // The tree algorithm needs to know how to sort the data.
111 // It does this using a functions provided by the calling program.
112 // This must return:
113 // -- 0: t1 == t2
114 // -- -1: t1 < t2
115 // -- +1: t1 > t2
116 typedef int TREEENTRY FNTREE_COMPARE_NODES(TREE *t1, TREE *t2);
117 typedef int TREEENTRY FNTREE_COMPARE_DATA(TREE *t1, void *pData);
118
119 // Define a function type for use with the tree traversal function
120 typedef void TREEENTRY TREE_PROCESS(TREE *t, void *pUser);
121
122 // Global variables
123 extern TREE TREE_EMPTY;
124
125 // Function prototypes
126 void treeInit(TREE **root);
127
128 int treeInsertID(TREE **root,
129 TREE *tree,
130 BOOL fAllowDuplicates);
131
132 int treeInsertNode(TREE **root,
133 TREE *tree,
134 FNTREE_COMPARE_NODES *comp,
135 BOOL fAllowDuplicates);
136
137 int treeDelete(TREE **root,
138 TREE *tree);
139
140 void* treeFindEQNode(TREE **root,
141 TREE *nodeFind,
142 FNTREE_COMPARE_NODES *comp);
143 void* treeFindLTNode(TREE **root,
144 TREE *nodeFind,
145 FNTREE_COMPARE_NODES *comp);
146 void* treeFindLENode(TREE **root,
147 TREE *nodeFind,
148 FNTREE_COMPARE_NODES *comp);
149 void* treeFindGTNode(TREE **root,
150 TREE *nodeFind,
151 FNTREE_COMPARE_NODES *comp);
152 void* treeFindGENode(TREE **root,
153 TREE *nodeFind,
154 FNTREE_COMPARE_NODES *comp);
155
156 void* treeFindEQID(TREE **root,
157 unsigned long idFind);
158 void* treeFindLTID(TREE **root,
159 unsigned long idFind);
160 void* treeFindLEID(TREE **root,
161 unsigned long idFind);
162 void* treeFindGTID(TREE **root,
163 unsigned long idFind);
164 void* treeFindGEID(TREE **root,
165 unsigned long idFind);
166
167 void* treeFindEQData(TREE **root,
168 void *pData,
169 FNTREE_COMPARE_DATA *comp);
170
171 void treeTraverse (TREE *tree,
172 TREE_PROCESS *process,
173 void *pUser,
174 int method);
175 void *treeNext (TREE *tree);
176 void *treePrev (TREE *tree);
177 void *treeFirst (TREE *tree);
178 void *treeLast (TREE *tree);
179
180 // Return codes
181 #define TREE_OK 0
182 #define TREE_DUPLICATE 1
183 #define TREE_INVALID_NODE 2
184
185 // Macros
186 #define TREE_NULL &TREE_EMPTY
187
188#endif
189
190#if __cplusplus
191}
192#endif
193
Note: See TracBrowser for help on using the repository browser.