/* A splay-tree datatype. Copyright 1999, 2000, 2001 Johan Rydberg, jrydberg@opencores.org. Copyright (C) 1998 Free Software Foundation, Inc. This file was a part of GNU CC. GNU CC 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 2, or (at your option) any later version. GNU CC 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. You should have received a copy of the GNU General Public License along with GNU CC; see the file COPYING. If not, write to the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ /* 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 __ipc_splay_tree_h #define __ipc_splay_tree_h 1 #include #include #include #include "ipc-entry.h" /* The type of a function which compares two splay-tree keys. The function should return values as for qsort. */ typedef int (*ipc_splay_tree_compare_fn) (rtmk_port_t, rtmk_port_t); /* The type of a function used to deallocate any resources associated with the key. */ typedef void (*ipc_splay_tree_delete_key_fn) (rtmk_port_t); /* The type of a function used to deallocate any resources associated with the value. */ typedef void (*ipc_splay_tree_delete_value_fn) (struct ipc_entry *); /* The type of a function used to iterate over the tree. */ typedef int (*ipc_splay_tree_foreach_fn) (struct ipc_entry *, void *); /* The splay tree itself. */ struct ipc_splay_tree { /* The root of the tree. */ struct ipc_entry *root; /* The comparision function. */ ipc_splay_tree_compare_fn comp; /* The deallocate-key function. NULL if no cleanup is necessary. */ ipc_splay_tree_delete_key_fn delete_key; /* The deallocate-value function. NULL if no cleanup is necessary. */ ipc_splay_tree_delete_value_fn delete_value; }; /* Initialize a new splay tree, using COMPARE_FN to compare nodes, DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate values. */ extern void ipc_splay_tree_init (struct ipc_splay_tree *sp, ipc_splay_tree_delete_key_fn delete_key_fn, ipc_splay_tree_delete_value_fn delete_value_fn); /* Deallocate SP. */ extern void ipc_splay_tree_delete (struct ipc_splay_tree *sp); /* Insert a new node (associating KEY with DATA) into SP. If a previous node with the indicated KEY exists, its data is replaced with the new value. */ extern void ipc_splay_tree_insert (struct ipc_splay_tree *sp, rtmk_port_t key, struct ipc_entry *node); /* Lookup KEY in SP, returning entry if present, and NULL otherwise. */ extern struct ipc_entry *ipc_splay_tree_lookup (struct ipc_splay_tree *sp, rtmk_port_t key) ; /* Delete node named KEY from splay-tree SP. Return node in NODEP. Returns false if there was no such node in the tree. */ extern bool ipc_splay_tree_delete_node (struct ipc_splay_tree *sp, rtmk_port_t key, struct ipc_entry **nodep); /* Return bounds of splay tree SP. KEY is the key to splay on. */ extern int ipc_splay_tree_bounds (struct ipc_splay_tree *sp, rtmk_port_t key, rtmk_port_t *lowerp, rtmk_port_t *upperp); /* ??? */ extern void ipc_splay_tree_first (struct ipc_splay_tree *sp, struct ipc_entry **entryp); /* Call FN, passing it the DATA, for every node in SP, following an in-order traversal. If FN every returns a non-zero value, the iteration ceases immediately, and the value is returned. Otherwise, this function returns 0. */ extern int ipc_splay_tree_foreach (struct ipc_splay_tree *sp, ipc_splay_tree_foreach_fn fn, void *data); #endif /* ipc-splay-tree.h */