]>
Commit | Line | Data |
---|---|---|
52e90c55 MM |
1 | /* A splay-tree datatype. |
2 | Copyright (C) 1998 Free Software Foundation, Inc. | |
3 | Contributed by Mark Mitchell (mark@markmitchell.com). | |
4 | ||
5 | This file is part of GNU CC. | |
6 | ||
7 | GNU CC is free software; you can redistribute it and/or modify it | |
8 | under the terms of the GNU General Public License as published by | |
9 | the Free Software Foundation; either version 2, or (at your option) | |
10 | any later version. | |
11 | ||
12 | GNU CC is distributed in the hope that it will be useful, but | |
13 | WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
15 | General Public License for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
18 | along with GNU CC; see the file COPYING. If not, write to the Free | |
19 | Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. | |
20 | ||
21 | For an easily readable description of splay-trees, see: | |
22 | ||
23 | Lewis, Harry R. and Denenberg, Larry. Data Structures and Their | |
24 | Algorithms. Harper-Collins, Inc. 1991. | |
25 | ||
26 | The major feature of splay trees is that all basic tree operations | |
27 | are amortized O(log n) time for a tree with n nodes. */ | |
28 | ||
29 | #ifndef _SPLAY_TREE_H | |
30 | #define _SPLAY_TREE_H | |
31 | ||
32 | #ifdef __cplusplus | |
33 | extern "C" { | |
34 | #endif /* __cplusplus */ | |
35 | ||
de5809b9 | 36 | #ifndef IN_GCC |
52e90c55 | 37 | #include <ansidecl.h> |
de5809b9 | 38 | #endif /* ! IN_GCC */ |
52e90c55 MM |
39 | |
40 | /* Use typedefs for the key and data types to facilitate changing | |
41 | these types, if necessary. These types should be sufficiently wide | |
42 | that any pointer or scalar can be cast to these types, and then | |
43 | cast back, without loss of precision. */ | |
44 | typedef unsigned long int splay_tree_key; | |
45 | typedef unsigned long int splay_tree_value; | |
46 | ||
47 | /* Forward declaration for a node in the tree. */ | |
48 | typedef struct splay_tree_node *splay_tree_node; | |
49 | ||
50 | /* The type of a function which compares two splay-tree keys. The | |
51 | function should return values as for qsort. */ | |
da61b7d5 | 52 | typedef int (*splay_tree_compare_fn) PARAMS((splay_tree_key, splay_tree_key)); |
52e90c55 MM |
53 | |
54 | /* The type of a function used to deallocate any resources associated | |
55 | with the key. */ | |
da61b7d5 | 56 | typedef void (*splay_tree_delete_key_fn) PARAMS((splay_tree_key)); |
52e90c55 MM |
57 | |
58 | /* The type of a function used to deallocate any resources associated | |
59 | with the value. */ | |
da61b7d5 | 60 | typedef void (*splay_tree_delete_value_fn) PARAMS((splay_tree_value)); |
52e90c55 MM |
61 | |
62 | /* The type of a function used to iterate over the tree. */ | |
da61b7d5 | 63 | typedef int (*splay_tree_foreach_fn) PARAMS((splay_tree_node, void*)); |
52e90c55 MM |
64 | |
65 | /* The nodes in the splay tree. */ | |
66 | struct splay_tree_node | |
67 | { | |
68 | /* The key. */ | |
69 | splay_tree_key key; | |
70 | ||
71 | /* The value. */ | |
72 | splay_tree_value value; | |
73 | ||
74 | /* The left and right children, respectively. */ | |
75 | splay_tree_node left; | |
76 | splay_tree_node right; | |
77 | }; | |
78 | ||
79 | /* The splay tree itself. */ | |
80 | typedef struct splay_tree | |
81 | { | |
82 | /* The root of the tree. */ | |
83 | splay_tree_node root; | |
84 | ||
85 | /* The comparision function. */ | |
86 | splay_tree_compare_fn comp; | |
87 | ||
88 | /* The deallocate-key function. NULL if no cleanup is necessary. */ | |
89 | splay_tree_delete_key_fn delete_key; | |
90 | ||
91 | /* The deallocate-value function. NULL if no cleanup is necessary. */ | |
92 | splay_tree_delete_value_fn delete_value; | |
93 | } *splay_tree; | |
94 | ||
95 | extern splay_tree splay_tree_new PARAMS((splay_tree_compare_fn, | |
96 | splay_tree_delete_key_fn, | |
97 | splay_tree_delete_value_fn)); | |
98 | extern void splay_tree_delete PARAMS((splay_tree)); | |
99 | extern void splay_tree_insert PARAMS((splay_tree, | |
100 | splay_tree_key, | |
101 | splay_tree_value)); | |
102 | extern splay_tree_node splay_tree_lookup | |
103 | PARAMS((splay_tree, | |
104 | splay_tree_key)); | |
105 | extern int splay_tree_foreach PARAMS((splay_tree, | |
106 | splay_tree_foreach_fn, | |
107 | void*)); | |
108 | ||
109 | #ifdef __cplusplus | |
110 | } | |
111 | #endif /* __cplusplus */ | |
112 | ||
113 | #endif /* _SPLAY_TREE_H */ |