Commit | Line | Data |
---|---|---|

5796c8dc | 1 | /* A splay-tree datatype. |

cf7f2e2d | 2 | Copyright 1998, 1999, 2000, 2002, 2005, 2007, 2009, 2010 |

5796c8dc SS |
3 | Free Software Foundation, Inc. |

4 | Contributed by Mark Mitchell (mark@markmitchell.com). | |

5 | ||

6 | This file is part of GCC. | |

7 | ||

8 | GCC is free software; you can redistribute it and/or modify it | |

9 | under the terms of the GNU General Public License as published by | |

10 | the Free Software Foundation; either version 2, or (at your option) | |

11 | any later version. | |

12 | ||

13 | GCC is distributed in the hope that it will be useful, but | |

14 | WITHOUT ANY WARRANTY; without even the implied warranty of | |

15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |

16 | General Public License for more details. | |

17 | ||

18 | You should have received a copy of the GNU General Public License | |

19 | along with GCC; see the file COPYING. If not, write to | |

20 | the Free Software Foundation, 51 Franklin Street - Fifth Floor, | |

21 | Boston, MA 02110-1301, USA. */ | |

22 | ||

23 | /* For an easily readable description of splay-trees, see: | |

24 | ||

25 | Lewis, Harry R. and Denenberg, Larry. Data Structures and Their | |

26 | Algorithms. Harper-Collins, Inc. 1991. | |

27 | ||

28 | The major feature of splay trees is that all basic tree operations | |

29 | are amortized O(log n) time for a tree with n nodes. */ | |

30 | ||

31 | #ifndef _SPLAY_TREE_H | |

32 | #define _SPLAY_TREE_H | |

33 | ||

34 | #ifdef __cplusplus | |

35 | extern "C" { | |

36 | #endif /* __cplusplus */ | |

37 | ||

38 | #include "ansidecl.h" | |

39 | ||

ef5ccd6c JM |
40 | #ifdef HAVE_STDINT_H |

41 | #include <stdint.h> | |

cf7f2e2d | 42 | #endif |

ef5ccd6c JM |
43 | #ifdef HAVE_INTTYPES_H |

44 | #include <inttypes.h> | |

5796c8dc SS |
45 | #endif |

46 | ||

47 | #ifndef GTY | |

48 | #define GTY(X) | |

49 | #endif | |

50 | ||

51 | /* Use typedefs for the key and data types to facilitate changing | |

52 | these types, if necessary. These types should be sufficiently wide | |

53 | that any pointer or scalar can be cast to these types, and then | |

54 | cast back, without loss of precision. */ | |

ef5ccd6c JM |
55 | typedef uintptr_t splay_tree_key; |

56 | typedef uintptr_t splay_tree_value; | |

5796c8dc SS |
57 | |

58 | /* Forward declaration for a node in the tree. */ | |

59 | typedef struct splay_tree_node_s *splay_tree_node; | |

60 | ||

61 | /* The type of a function which compares two splay-tree keys. The | |

62 | function should return values as for qsort. */ | |

63 | typedef int (*splay_tree_compare_fn) (splay_tree_key, splay_tree_key); | |

64 | ||

65 | /* The type of a function used to deallocate any resources associated | |

66 | with the key. */ | |

67 | typedef void (*splay_tree_delete_key_fn) (splay_tree_key); | |

68 | ||

69 | /* The type of a function used to deallocate any resources associated | |

70 | with the value. */ | |

71 | typedef void (*splay_tree_delete_value_fn) (splay_tree_value); | |

72 | ||

73 | /* The type of a function used to iterate over the tree. */ | |

74 | typedef int (*splay_tree_foreach_fn) (splay_tree_node, void*); | |

75 | ||

76 | /* The type of a function used to allocate memory for tree root and | |

77 | node structures. The first argument is the number of bytes needed; | |

78 | the second is a data pointer the splay tree functions pass through | |

79 | to the allocator. This function must never return zero. */ | |

80 | typedef void *(*splay_tree_allocate_fn) (int, void *); | |

81 | ||

82 | /* The type of a function used to free memory allocated using the | |

83 | corresponding splay_tree_allocate_fn. The first argument is the | |

84 | memory to be freed; the latter is a data pointer the splay tree | |

85 | functions pass through to the freer. */ | |

86 | typedef void (*splay_tree_deallocate_fn) (void *, void *); | |

87 | ||

88 | /* The nodes in the splay tree. */ | |

89 | struct GTY(()) splay_tree_node_s { | |

90 | /* The key. */ | |

91 | splay_tree_key GTY ((use_param1)) key; | |

92 | ||

93 | /* The value. */ | |

94 | splay_tree_value GTY ((use_param2)) value; | |

95 | ||

96 | /* The left and right children, respectively. */ | |

97 | splay_tree_node GTY ((use_params)) left; | |

98 | splay_tree_node GTY ((use_params)) right; | |

99 | }; | |

100 | ||

101 | /* The splay tree itself. */ | |

102 | struct GTY(()) splay_tree_s { | |

103 | /* The root of the tree. */ | |

104 | splay_tree_node GTY ((use_params)) root; | |

105 | ||

106 | /* The comparision function. */ | |

107 | splay_tree_compare_fn comp; | |

108 | ||

109 | /* The deallocate-key function. NULL if no cleanup is necessary. */ | |

110 | splay_tree_delete_key_fn delete_key; | |

111 | ||

112 | /* The deallocate-value function. NULL if no cleanup is necessary. */ | |

113 | splay_tree_delete_value_fn delete_value; | |

114 | ||

cf7f2e2d | 115 | /* Node allocate function. Takes allocate_data as a parameter. */ |

5796c8dc | 116 | splay_tree_allocate_fn allocate; |

cf7f2e2d JM |
117 | |

118 | /* Free function for nodes and trees. Takes allocate_data as a parameter. */ | |

5796c8dc | 119 | splay_tree_deallocate_fn deallocate; |

cf7f2e2d JM |
120 | |

121 | /* Parameter for allocate/free functions. */ | |

5796c8dc SS |
122 | void * GTY((skip)) allocate_data; |

123 | }; | |

124 | ||

125 | typedef struct splay_tree_s *splay_tree; | |

126 | ||

127 | extern splay_tree splay_tree_new (splay_tree_compare_fn, | |

128 | splay_tree_delete_key_fn, | |

129 | splay_tree_delete_value_fn); | |

130 | extern splay_tree splay_tree_new_with_allocator (splay_tree_compare_fn, | |

131 | splay_tree_delete_key_fn, | |

132 | splay_tree_delete_value_fn, | |

133 | splay_tree_allocate_fn, | |

134 | splay_tree_deallocate_fn, | |

135 | void *); | |

cf7f2e2d JM |
136 | extern splay_tree splay_tree_new_typed_alloc (splay_tree_compare_fn, |

137 | splay_tree_delete_key_fn, | |

138 | splay_tree_delete_value_fn, | |

139 | splay_tree_allocate_fn, | |

140 | splay_tree_allocate_fn, | |

141 | splay_tree_deallocate_fn, | |

142 | void *); | |

5796c8dc SS |
143 | extern void splay_tree_delete (splay_tree); |

144 | extern splay_tree_node splay_tree_insert (splay_tree, | |

145 | splay_tree_key, | |

146 | splay_tree_value); | |

147 | extern void splay_tree_remove (splay_tree, splay_tree_key); | |

148 | extern splay_tree_node splay_tree_lookup (splay_tree, splay_tree_key); | |

149 | extern splay_tree_node splay_tree_predecessor (splay_tree, splay_tree_key); | |

150 | extern splay_tree_node splay_tree_successor (splay_tree, splay_tree_key); | |

151 | extern splay_tree_node splay_tree_max (splay_tree); | |

152 | extern splay_tree_node splay_tree_min (splay_tree); | |

153 | extern int splay_tree_foreach (splay_tree, splay_tree_foreach_fn, void*); | |

154 | extern int splay_tree_compare_ints (splay_tree_key, splay_tree_key); | |

155 | extern int splay_tree_compare_pointers (splay_tree_key, splay_tree_key); | |

156 | ||

157 | #ifdef __cplusplus | |

158 | } | |

159 | #endif /* __cplusplus */ | |

160 | ||

161 | #endif /* _SPLAY_TREE_H */ |