| /* A splay-tree datatype. |

| Copyright (C) 1998-2015 Free Software Foundation, Inc. |

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

| |

| This file is part of the GNU Offloading and Multi Processing Library |

| (libgomp). |

| |

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

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

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

| any later version. |

| |

| Libgomp is distributed in the hope that it will be useful, but WITHOUT ANY |

| WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS |

| FOR A PARTICULAR PURPOSE. See the GNU General Public License for |

| more details. |

| |

| Under Section 7 of GPL version 3, you are granted additional |

| permissions described in the GCC Runtime Library Exception, version |

| 3.1, as published by the Free Software Foundation. |

| |

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

| a copy of the GCC Runtime Library Exception along with this program; |

| see the files COPYING3 and COPYING.RUNTIME respectively. If not, see |

| <http://www.gnu.org/licenses/>. */ |

| |

| /* The splay tree code copied from include/splay-tree.h and adjusted, |

| so that all the data lives directly in splay_tree_node_s structure |

| and no extra allocations are needed. |

| |

| Files including this header should before including it add: |

| typedef struct splay_tree_node_s *splay_tree_node; |

| typedef struct splay_tree_s *splay_tree; |

| typedef struct splay_tree_key_s *splay_tree_key; |

| define splay_tree_key_s structure, and define |

| splay_compare inline function. */ |

| |

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

| |

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

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

| |

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

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

| |

| #ifndef _SPLAY_TREE_H |

| #define _SPLAY_TREE_H 1 |

| |

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

| struct splay_tree_node_s { |

| struct splay_tree_key_s key; |

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

| splay_tree_node left; |

| splay_tree_node right; |

| }; |

| |

| /* The splay tree. */ |

| struct splay_tree_s { |

| splay_tree_node root; |

| }; |

| |

| extern splay_tree_key splay_tree_lookup (splay_tree, splay_tree_key); |

| extern void splay_tree_insert (splay_tree, splay_tree_node); |

| extern void splay_tree_remove (splay_tree, splay_tree_key); |

| |

| #endif /* _SPLAY_TREE_H */ |