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

dda118e3 JM |
1 | /* A splay-tree datatype. |

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

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 | ||

40 | #ifdef HAVE_STDINT_H | |

41 | #include <stdint.h> | |

42 | #endif | |

43 | #ifdef HAVE_INTTYPES_H | |

44 | #include <inttypes.h> | |

45 | #endif | |

46 | ||

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

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

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

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

51 | typedef uintptr_t splay_tree_key; | |

52 | typedef uintptr_t splay_tree_value; | |

53 | ||

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

55 | typedef struct splay_tree_node_s *splay_tree_node; | |

56 | ||

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

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

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

60 | ||

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

62 | with the key. */ | |

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

64 | ||

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

66 | with the value. */ | |

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

68 | ||

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

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

71 | ||

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

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

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

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

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

77 | ||

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

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

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

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

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

83 | ||

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

85 | struct splay_tree_node_s { | |

86 | /* The key. */ | |

87 | splay_tree_key key; | |

88 | ||

89 | /* The value. */ | |

90 | splay_tree_value value; | |

91 | ||

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

93 | splay_tree_node left; | |

94 | splay_tree_node right; | |

95 | }; | |

96 | ||

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

98 | struct splay_tree_s { | |

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

100 | splay_tree_node root; | |

101 | ||

102 | /* The comparision function. */ | |

103 | splay_tree_compare_fn comp; | |

104 | ||

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

106 | splay_tree_delete_key_fn delete_key; | |

107 | ||

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

109 | splay_tree_delete_value_fn delete_value; | |

110 | ||

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

112 | splay_tree_allocate_fn allocate; | |

113 | ||

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

115 | splay_tree_deallocate_fn deallocate; | |

116 | ||

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

118 | void *allocate_data; | |

119 | }; | |

120 | ||

121 | typedef struct splay_tree_s *splay_tree; | |

122 | ||

123 | extern splay_tree splay_tree_new (splay_tree_compare_fn, | |

124 | splay_tree_delete_key_fn, | |

125 | splay_tree_delete_value_fn); | |

126 | extern splay_tree splay_tree_new_with_allocator (splay_tree_compare_fn, | |

127 | splay_tree_delete_key_fn, | |

128 | splay_tree_delete_value_fn, | |

129 | splay_tree_allocate_fn, | |

130 | splay_tree_deallocate_fn, | |

131 | void *); | |

132 | extern splay_tree splay_tree_new_typed_alloc (splay_tree_compare_fn, | |

133 | splay_tree_delete_key_fn, | |

134 | splay_tree_delete_value_fn, | |

135 | splay_tree_allocate_fn, | |

136 | splay_tree_allocate_fn, | |

137 | splay_tree_deallocate_fn, | |

138 | void *); | |

139 | extern void splay_tree_delete (splay_tree); | |

140 | extern splay_tree_node splay_tree_insert (splay_tree, | |

141 | splay_tree_key, | |

142 | splay_tree_value); | |

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

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

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

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

147 | extern splay_tree_node splay_tree_max (splay_tree); | |

148 | extern splay_tree_node splay_tree_min (splay_tree); | |

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

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

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

152 | ||

153 | #ifdef __cplusplus | |

154 | } | |

155 | #endif /* __cplusplus */ | |

156 | ||

157 | #endif /* _SPLAY_TREE_H */ |