splay_tree.c 7.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323
  1. /*!
  2. Temelia - Splay tree implementation source file.
  3. Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).
  4. @author Dascalu Laurentiu
  5. This program is free software; you can redistribute it and
  6. modify it under the terms of the GNU General Public License
  7. as published by the Free Software Foundation; either version 3
  8. of the License, or (at your option) any later version.
  9. This program is distributed in the hope that it will be useful,
  10. but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12. GNU General Public License for more details.
  13. You should have received a copy of the GNU General Public License
  14. along with this program; if not, write to the Free Software
  15. Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  16. */
  17. #include "include/splay_tree.h"
  18. #include "include/common.h"
  19. #include <stdlib.h>
  20. static splay_tree_t _splay_tree_splay(void *key, splay_tree_t tree,
  21. int compare(void *x, void *y, void *context), void *context);
  22. splay_tree_t splay_tree_new(void *key)
  23. {
  24. return _binary_tree_new(key);
  25. }
  26. void splay_tree_delete_node(splay_tree_t splay_tree)
  27. {
  28. _ASSERT(splay_tree, ==, NULL, NULL_POINTER,);
  29. _delete(splay_tree);
  30. }
  31. void splay_tree_delete(splay_tree_t splay_tree)
  32. {
  33. _ASSERT(splay_tree, ==, NULL, NULL_POINTER,);
  34. splay_tree_delete(_binary_tree_get_left_child(splay_tree));
  35. splay_tree_delete(_binary_tree_get_right_child(splay_tree));
  36. splay_tree_delete_node(splay_tree);
  37. }
  38. int splay_tree_compare_trees(splay_tree_t splay_tree1,
  39. splay_tree_t splay_tree2, int compare(void *x, void *y, void *context),
  40. void *context)
  41. {
  42. return _binary_tree_compare_trees(splay_tree1, splay_tree2, compare,
  43. context);
  44. }
  45. int splay_tree_is_empty(splay_tree_t splay_tree)
  46. {
  47. return (_binary_tree_get_parent(splay_tree) == NULL)
  48. && (_binary_tree_get_left_child(splay_tree) == NULL)
  49. && (_binary_tree_get_right_child(splay_tree) == NULL)
  50. && (_binary_tree_get_key(splay_tree) == NULL);
  51. }
  52. int splay_tree_is_leaf(splay_tree_t splay_tree)
  53. {
  54. return _binary_tree_leaf(splay_tree);
  55. }
  56. splay_tree_t splay_tree_get_root(splay_tree_t splay_tree)
  57. {
  58. return _binary_tree_get_root(splay_tree);
  59. }
  60. void *splay_tree_get_key(splay_tree_t splay_tree)
  61. {
  62. void *node;
  63. _ASSERT(splay_tree, ==, NULL, NULL_POINTER, NULL);
  64. node = _binary_tree_get_key(splay_tree);
  65. return node;
  66. }
  67. int splay_tree_get_size(splay_tree_t splay_tree)
  68. {
  69. return _binary_tree_get_size(splay_tree);
  70. }
  71. splay_tree_t splay_tree_get_parent(splay_tree_t splay_tree)
  72. {
  73. return _binary_tree_get_parent(splay_tree);
  74. }
  75. splay_tree_t splay_tree_get_left_child(splay_tree_t splay_tree)
  76. {
  77. return _binary_tree_get_left_child(splay_tree);
  78. }
  79. splay_tree_t splay_tree_get_right_child(splay_tree_t splay_tree)
  80. {
  81. return _binary_tree_get_right_child(splay_tree);
  82. }
  83. int splay_tree_get_height(splay_tree_t splay_tree)
  84. {
  85. return _binary_tree_get_height(splay_tree);
  86. }
  87. int splay_tree_get_depth(splay_tree_t splay_tree)
  88. {
  89. return _binary_tree_get_depth(splay_tree);
  90. }
  91. splay_tree_t splay_tree_search(splay_tree_t splay_tree, void *key, int compare(
  92. void *x, void *y, void *context), void *context)
  93. {
  94. return _binary_search_tree_search(splay_tree, key, compare, context);
  95. }
  96. splay_tree_t splay_tree_insert(splay_tree_t _splay_tree, void *key,
  97. int compare(void *x, void *y, void *context), void *context)
  98. {
  99. splay_tree_t new;
  100. _ASSERT(compare, ==, NULL, NULL_POINTER, NULL);
  101. new = splay_tree_new(key);
  102. if (_splay_tree == NULL)
  103. {
  104. new->left = new->right = new->parent = NULL;
  105. return new;
  106. }
  107. _splay_tree = _splay_tree_splay(key, _splay_tree, compare, context);
  108. if (compare(key, _splay_tree->key, context) < 0)
  109. {
  110. new->left = _splay_tree->left;
  111. new->right = _splay_tree;
  112. _splay_tree->left = NULL;
  113. if (new->left)
  114. new->left->parent = new;
  115. if (new->right)
  116. new->right->parent = new;
  117. return new;
  118. }
  119. else if (compare(key, _splay_tree->key, context) > 0)
  120. {
  121. new->right = _splay_tree->right;
  122. new->left = _splay_tree;
  123. _splay_tree->right = NULL;
  124. if (new->left)
  125. new->left->parent = new;
  126. if (new->right)
  127. new->right->parent = new;
  128. return new;
  129. }
  130. else
  131. {
  132. splay_tree_delete_node(new);
  133. return _splay_tree;
  134. }
  135. return NULL;
  136. }
  137. splay_tree_t splay_tree_remove(splay_tree_t splay_tree, void *key,
  138. int compare(void *x, void *y, void *context), void *context)
  139. {
  140. splay_tree_t x = NULL;
  141. LOGGER("[splay tree remove] tree %p, key %p, compare %p, context %p\n",
  142. splay_tree, key, compare, context);
  143. _ASSERT(splay_tree, ==, NULL, NULL_POINTER, NULL);
  144. _ASSERT(compare, ==, NULL, NULL_POINTER, NULL);
  145. splay_tree = _splay_tree_splay(key, splay_tree, compare, context);
  146. if (compare(key, splay_tree->key, context) == 0)
  147. {
  148. if (splay_tree->left == NULL)
  149. x = splay_tree->right;
  150. else
  151. {
  152. x = _splay_tree_splay(key, splay_tree->left, compare, context);
  153. x->right = splay_tree->right;
  154. if (x->right)
  155. x->right->parent = x;
  156. }
  157. splay_tree_delete_node(splay_tree);
  158. return x;
  159. }
  160. return splay_tree;
  161. }
  162. splay_tree_t splay_tree_get_min(splay_tree_t splay_tree)
  163. {
  164. return _binary_search_tree_get_min(splay_tree);
  165. }
  166. splay_tree_t splay_tree_get_max(splay_tree_t splay_tree)
  167. {
  168. return _binary_search_tree_get_max(splay_tree);
  169. }
  170. void splay_tree_preorder(splay_tree_t splay_tree, void key_handler(void *x,
  171. void *context), void *context)
  172. {
  173. _binary_tree_preorder(splay_tree, key_handler, context);
  174. }
  175. void splay_tree_inorder(splay_tree_t splay_tree, void key_handler(void *x,
  176. void *context), void *context)
  177. {
  178. _binary_tree_inorder(splay_tree, key_handler, context);
  179. }
  180. void splay_tree_reverse_inorder(splay_tree_t splay_tree, void key_handler(
  181. void *x, void *context), void *context)
  182. {
  183. _binary_tree_reverse_inorder(splay_tree, key_handler, context);
  184. }
  185. void splay_tree_postorder(splay_tree_t splay_tree, void key_handler(void *x,
  186. void *context), void *context)
  187. {
  188. _binary_tree_postorder(splay_tree, key_handler, context);
  189. }
  190. void splay_tree_level_order(splay_tree_t splay_tree, void key_handler(void *x,
  191. void *context), void *context)
  192. {
  193. _binary_tree_level_order(splay_tree, key_handler, context);
  194. }
  195. void splay_tree_show_indented(splay_tree_t splay_tree, void key_handler(
  196. void *x, int level, void *context), void *context)
  197. {
  198. _binary_tree_show_indented(splay_tree, key_handler, context, 0);
  199. }
  200. static splay_tree_t _splay_tree_splay(void *key, splay_tree_t tree,
  201. int compare(void *x, void *y, void *context), void *context)
  202. {
  203. splay_tree_t left, right;
  204. struct _bt_node_t new_node;
  205. int comp;
  206. _ASSERT(tree, ==, NULL, NULL_POINTER, NULL);
  207. new_node.left = new_node.right = NULL;
  208. left = right = &new_node;
  209. for (;;)
  210. {
  211. comp = compare(key, splay_tree_get_key(tree), context);
  212. if (comp < 0)
  213. {
  214. if (_binary_tree_get_left_child(tree) == NULL)
  215. break;
  216. if (compare(key, _binary_tree_get_key(_binary_tree_get_left_child(
  217. tree)), context) < 0)
  218. {
  219. tree = _self_balanced_binary_search_tree_rotate_right(tree);
  220. if (_binary_tree_get_left_child(tree) == NULL)
  221. break;
  222. }
  223. _binary_tree_set_left_child(right, tree);
  224. right = tree;
  225. tree = _binary_tree_get_left_child(tree);
  226. }
  227. else if (comp > 0)
  228. {
  229. if (_binary_tree_get_right_child(tree) == NULL)
  230. break;
  231. if (compare(key, _binary_tree_get_key(_binary_tree_get_right_child(
  232. tree)), context) > 0)
  233. {
  234. tree = _self_balanced_binary_search_tree_rotate_left(tree);
  235. if (_binary_tree_get_right_child(tree) == NULL)
  236. break;
  237. }
  238. _binary_tree_set_right_child(left, tree);
  239. left = tree;
  240. tree = _binary_tree_get_right_child(tree);
  241. }
  242. else
  243. break;
  244. }
  245. _binary_tree_set_right_child(left, _binary_tree_get_left_child(tree));
  246. _binary_tree_set_left_child(right, _binary_tree_get_right_child(tree));
  247. _binary_tree_set_left_child(tree, new_node.right);
  248. if (tree->right)
  249. tree->right->parent = tree;
  250. _binary_tree_set_right_child(tree, new_node.left);
  251. if (tree->left)
  252. tree->left->parent = tree;
  253. tree->parent = NULL;
  254. return tree;
  255. }