/* 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. */ #include "tm.h" #include "ipc-entry.h" #include "ipc-splay-tree.h" #ifndef PARAMS #define PARAMS(x) x #endif /* Splay-tree comparison function, treating the keys as ints. */ static int splay_tree_compare_keys (rtmk_port_t k1, rtmk_port_t k2) { if (k1 < k2) return -1; else if (k1 > k2) return 1; else return 0; } /* Deallocate NODE (a member of SP), and all its sub-trees. */ static void splay_tree_delete_helper (struct ipc_splay_tree *sp, struct ipc_entry *node) { if (!node) return; splay_tree_delete_helper (sp, node->ie_left); splay_tree_delete_helper (sp, node->ie_right); if (sp->delete_key) (*sp->delete_key) (node->ie_key); #if 0 if (sp->delete_value) (*sp->delete_value) (node->value); #endif #if 0 free ((char *) node); #endif } /* Help splay SP around KEY. PARENT and GRANDPARENT are the parent and grandparent, respectively, of NODE. */ static ipc_entry splay_tree_splay_helper (struct ipc_splay_tree *sp, rtmk_port_t key, struct ipc_entry **node, struct ipc_entry **parent, struct ipc_entry **grandparent) { struct ipc_entry **next; struct ipc_entry *n; int comparison; n = *node; if (!n) return *parent; comparison = (*sp->comp) (key, n->ie_key); if (comparison == 0) /* We've found the target. */ next = 0; else if (comparison < 0) /* The target is to the left. */ next = &n->ie_left; else /* The target is to the right. */ next = &n->ie_right; if (next) { /* Continue down the tree. */ n = splay_tree_splay_helper (sp, key, next, node, parent); /* The recursive call will change the place to which NODE points. */ if (*node != n) return n; } if (!parent) /* NODE is the root. We are done. */ return n; /* First, handle the case where there is no grandparent (i.e., *PARENT is the root of the tree.) */ if (!grandparent) { if (n == (*parent)->ie_left) { *node = n->ie_right; n->ie_right = *parent; } else { *node = n->ie_left; n->ie_left = *parent; } *parent = n; return n; } /* Next handle the cases where both N and *PARENT are left children, or where both are right children. */ if (n == (*parent)->ie_left && *parent == (*grandparent)->ie_left) { ipc_entry p = *parent; (*grandparent)->ie_left = p->ie_right; p->ie_right = *grandparent; p->ie_left = n->ie_right; n->ie_right = p; *grandparent = n; return n; } else if (n == (*parent)->ie_right && *parent == (*grandparent)->ie_right) { ipc_entry p = *parent; (*grandparent)->ie_right = p->ie_left; p->ie_left = *grandparent; p->ie_right = n->ie_left; n->ie_left = p; *grandparent = n; return n; } /* Finally, deal with the case where N is a left child, but *PARENT is a right child, or vice versa. */ if (n == (*parent)->ie_left) { (*parent)->ie_left = n->ie_right; n->ie_right = *parent; (*grandparent)->ie_right = n->ie_left; n->ie_left = *grandparent; *grandparent = n; return n; } else { (*parent)->ie_right = n->ie_left; n->ie_left = *parent; (*grandparent)->ie_left = n->ie_right; n->ie_right = *grandparent; *grandparent = n; return n; } } /* Splay SP around KEY. */ static void splay_tree_splay (struct ipc_splay_tree *sp, rtmk_port_t key) { if (sp->root == 0) return; splay_tree_splay_helper (sp, key, &sp->root, /*grandparent= */ 0, /*parent= */ 0); } /* Call FN, passing it the DATA, for every node below NODE, all of which are from 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. */ static int splay_tree_foreach_helper (struct ipc_splay_tree *sp, struct ipc_entry *node, ipc_splay_tree_foreach_fn fn, void *data) { int val; if (!node) return 0; val = splay_tree_foreach_helper (sp, node->ie_left, fn, data); if (val) return val; val = (*fn) (node, data); if (val) return val; return splay_tree_foreach_helper (sp, node->ie_right, fn, data); } /* Initialize a new splay tree, using COMPARE_FN to compare nodes, DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate values. */ 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) { sp->root = 0; sp->comp = splay_tree_compare_keys; sp->delete_key = delete_key_fn; sp->delete_value = delete_value_fn; } /* Deallocate SP. */ void ipc_splay_tree_delete (struct ipc_splay_tree *sp) { splay_tree_delete_helper (sp, sp->root); } /* 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. */ void ipc_splay_tree_insert (struct ipc_splay_tree *sp, rtmk_port_t key, struct ipc_entry *node) { int comparison = 0; splay_tree_splay (sp, key); if (sp->root) comparison = (*sp->comp) (sp->root->ie_key, key); if (sp->root && comparison == 0) { #if 0 /* If the root of the tree already has the indicated KEY, just replace the value with VALUE. */ if (sp->delete_value) (*sp->delete_value) (sp->root->value); sp->root->value = value; #endif } else { if (!sp->root) node->ie_left = node->ie_right = 0; else if (comparison < 0) { node->ie_left = sp->root; node->ie_right = node->ie_left->ie_right; node->ie_left->ie_right = 0; } else { node->ie_right = sp->root; node->ie_left = node->ie_right->ie_left; node->ie_right->ie_left = 0; } sp->root = node; } } /* Lookup KEY in SP, returning entry if present, and NULL otherwise. */ struct ipc_entry * ipc_splay_tree_lookup (struct ipc_splay_tree *sp, rtmk_port_t key) { splay_tree_splay (sp, key); if (sp->root && (*sp->comp) (sp->root->ie_key, key) == 0) return sp->root; else return 0; } /* Delete node named KEY from splay-tree SP. Return node in NODEP. Returns false if there was no such node in the tree. */ bool ipc_splay_tree_delete_node (struct ipc_splay_tree *sp, rtmk_port_t key, struct ipc_entry **nodep) { struct ipc_entry *node, *n; int comparison = 0; splay_tree_splay (sp, key); if (sp->root) comparison = (*sp->comp) (sp->root->ie_key, key); if (sp->root && comparison == 0) { node = sp->root; if (node->ie_left == 0) sp->root = node->ie_left; else { n = node->ie_left; sp->root = n; splay_tree_splay (sp, key); n->ie_right = node->ie_right; sp->root = n; } *nodep = node; return true; } return false; } /* Return bounds of splay tree SP. KEY is the key to splay on. */ int ipc_splay_tree_bounds (struct ipc_splay_tree *sp, rtmk_port_t key, rtmk_port_t *lowerp, rtmk_port_t *upperp) { int comparison; splay_tree_splay (sp, key); if (sp->root) comparison = (*sp->comp) (sp->root->ie_key, key); *lowerp = 0; *upperp = ~0; if (sp->root) { if (sp->root->ie_left != 0) *lowerp = sp->root->ie_left->ie_key; else *lowerp = sp->root->ie_key; if (sp->root->ie_right != 0) *upperp = sp->root->ie_right->ie_key; else *upperp = sp->root->ie_key; if (sp->root->ie_right == 0) return 0; return 1; } return 0; } void ipc_splay_tree_first (struct ipc_splay_tree *sp, struct ipc_entry **entryp) { ipc_entry node; for (node = sp->root; node != 0;) { if (node->ie_left == 0) break; node = node->ie_left; } *entryp = node; } /* 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. */ int ipc_splay_tree_foreach (struct ipc_splay_tree *sp, ipc_splay_tree_foreach_fn fn, void *data) { return splay_tree_foreach_helper (sp, sp->root, fn, data); }