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

Last change on this file since 10 was 7, checked in by umoeller, 25 years ago

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