splay-tree.c revision 104834
160484Sobrien/* A splay-tree datatype. 289857Sobrien Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc. 360484Sobrien Contributed by Mark Mitchell (mark@markmitchell.com). 460484Sobrien 560484SobrienThis file is part of GNU CC. 660484Sobrien 760484SobrienGNU CC is free software; you can redistribute it and/or modify it 860484Sobrienunder the terms of the GNU General Public License as published by 960484Sobrienthe Free Software Foundation; either version 2, or (at your option) 1060484Sobrienany later version. 1160484Sobrien 1260484SobrienGNU CC is distributed in the hope that it will be useful, but 1360484SobrienWITHOUT ANY WARRANTY; without even the implied warranty of 1460484SobrienMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1560484SobrienGeneral Public License for more details. 1660484Sobrien 1760484SobrienYou should have received a copy of the GNU General Public License 1860484Sobrienalong with GNU CC; see the file COPYING. If not, write to 1960484Sobrienthe Free Software Foundation, 59 Temple Place - Suite 330, 2060484SobrienBoston, MA 02111-1307, USA. */ 2160484Sobrien 2260484Sobrien/* For an easily readable description of splay-trees, see: 2360484Sobrien 2460484Sobrien Lewis, Harry R. and Denenberg, Larry. Data Structures and Their 2560484Sobrien Algorithms. Harper-Collins, Inc. 1991. */ 2660484Sobrien 2760484Sobrien#ifdef HAVE_CONFIG_H 2860484Sobrien#include "config.h" 2960484Sobrien#endif 3060484Sobrien 3160484Sobrien#ifdef HAVE_STDLIB_H 3260484Sobrien#include <stdlib.h> 3360484Sobrien#endif 3460484Sobrien 3577298Sobrien#include <stdio.h> 3677298Sobrien 3760484Sobrien#include "libiberty.h" 3860484Sobrien#include "splay-tree.h" 3960484Sobrien 4060484Sobrienstatic void splay_tree_delete_helper PARAMS((splay_tree, 4160484Sobrien splay_tree_node)); 4260484Sobrienstatic void splay_tree_splay PARAMS((splay_tree, 4360484Sobrien splay_tree_key)); 4460484Sobrienstatic splay_tree_node splay_tree_splay_helper 4560484Sobrien PARAMS((splay_tree, 4660484Sobrien splay_tree_key, 4760484Sobrien splay_tree_node*, 4860484Sobrien splay_tree_node*, 4960484Sobrien splay_tree_node*)); 5060484Sobrienstatic int splay_tree_foreach_helper PARAMS((splay_tree, 5160484Sobrien splay_tree_node, 5260484Sobrien splay_tree_foreach_fn, 5360484Sobrien void*)); 5460484Sobrien 5560484Sobrien/* Deallocate NODE (a member of SP), and all its sub-trees. */ 5660484Sobrien 5760484Sobrienstatic void 5860484Sobriensplay_tree_delete_helper (sp, node) 5960484Sobrien splay_tree sp; 6060484Sobrien splay_tree_node node; 6160484Sobrien{ 6260484Sobrien if (!node) 6360484Sobrien return; 6460484Sobrien 6560484Sobrien splay_tree_delete_helper (sp, node->left); 6660484Sobrien splay_tree_delete_helper (sp, node->right); 6760484Sobrien 6860484Sobrien if (sp->delete_key) 6960484Sobrien (*sp->delete_key)(node->key); 7060484Sobrien if (sp->delete_value) 7160484Sobrien (*sp->delete_value)(node->value); 7260484Sobrien 73104834Sobrien (*sp->deallocate) ((char*) node, sp->allocate_data); 7460484Sobrien} 7560484Sobrien 7660484Sobrien/* Help splay SP around KEY. PARENT and GRANDPARENT are the parent 7760484Sobrien and grandparent, respectively, of NODE. */ 7860484Sobrien 7960484Sobrienstatic splay_tree_node 8060484Sobriensplay_tree_splay_helper (sp, key, node, parent, grandparent) 8160484Sobrien splay_tree sp; 8260484Sobrien splay_tree_key key; 8360484Sobrien splay_tree_node *node; 8460484Sobrien splay_tree_node *parent; 8560484Sobrien splay_tree_node *grandparent; 8660484Sobrien{ 8760484Sobrien splay_tree_node *next; 8860484Sobrien splay_tree_node n; 8960484Sobrien int comparison; 9060484Sobrien 9160484Sobrien n = *node; 9260484Sobrien 9360484Sobrien if (!n) 9460484Sobrien return *parent; 9560484Sobrien 9660484Sobrien comparison = (*sp->comp) (key, n->key); 9760484Sobrien 9860484Sobrien if (comparison == 0) 9960484Sobrien /* We've found the target. */ 10060484Sobrien next = 0; 10160484Sobrien else if (comparison < 0) 10260484Sobrien /* The target is to the left. */ 10360484Sobrien next = &n->left; 10460484Sobrien else 10560484Sobrien /* The target is to the right. */ 10660484Sobrien next = &n->right; 10760484Sobrien 10860484Sobrien if (next) 10960484Sobrien { 11060484Sobrien /* Continue down the tree. */ 11160484Sobrien n = splay_tree_splay_helper (sp, key, next, node, parent); 11260484Sobrien 11360484Sobrien /* The recursive call will change the place to which NODE 11460484Sobrien points. */ 11560484Sobrien if (*node != n) 11660484Sobrien return n; 11760484Sobrien } 11860484Sobrien 11960484Sobrien if (!parent) 12060484Sobrien /* NODE is the root. We are done. */ 12160484Sobrien return n; 12260484Sobrien 12360484Sobrien /* First, handle the case where there is no grandparent (i.e., 12460484Sobrien *PARENT is the root of the tree.) */ 12560484Sobrien if (!grandparent) 12660484Sobrien { 12760484Sobrien if (n == (*parent)->left) 12860484Sobrien { 12960484Sobrien *node = n->right; 13060484Sobrien n->right = *parent; 13160484Sobrien } 13260484Sobrien else 13360484Sobrien { 13460484Sobrien *node = n->left; 13560484Sobrien n->left = *parent; 13660484Sobrien } 13760484Sobrien *parent = n; 13860484Sobrien return n; 13960484Sobrien } 14060484Sobrien 14160484Sobrien /* Next handle the cases where both N and *PARENT are left children, 14260484Sobrien or where both are right children. */ 14360484Sobrien if (n == (*parent)->left && *parent == (*grandparent)->left) 14460484Sobrien { 14560484Sobrien splay_tree_node p = *parent; 14660484Sobrien 14760484Sobrien (*grandparent)->left = p->right; 14860484Sobrien p->right = *grandparent; 14960484Sobrien p->left = n->right; 15060484Sobrien n->right = p; 15160484Sobrien *grandparent = n; 15260484Sobrien return n; 15360484Sobrien } 15460484Sobrien else if (n == (*parent)->right && *parent == (*grandparent)->right) 15560484Sobrien { 15660484Sobrien splay_tree_node p = *parent; 15760484Sobrien 15860484Sobrien (*grandparent)->right = p->left; 15960484Sobrien p->left = *grandparent; 16060484Sobrien p->right = n->left; 16160484Sobrien n->left = p; 16260484Sobrien *grandparent = n; 16360484Sobrien return n; 16460484Sobrien } 16560484Sobrien 16660484Sobrien /* Finally, deal with the case where N is a left child, but *PARENT 16760484Sobrien is a right child, or vice versa. */ 16860484Sobrien if (n == (*parent)->left) 16960484Sobrien { 17060484Sobrien (*parent)->left = n->right; 17160484Sobrien n->right = *parent; 17260484Sobrien (*grandparent)->right = n->left; 17360484Sobrien n->left = *grandparent; 17460484Sobrien *grandparent = n; 17560484Sobrien return n; 17660484Sobrien } 17760484Sobrien else 17860484Sobrien { 17960484Sobrien (*parent)->right = n->left; 18060484Sobrien n->left = *parent; 18160484Sobrien (*grandparent)->left = n->right; 18260484Sobrien n->right = *grandparent; 18360484Sobrien *grandparent = n; 18460484Sobrien return n; 18560484Sobrien } 18660484Sobrien} 18760484Sobrien 18860484Sobrien/* Splay SP around KEY. */ 18960484Sobrien 19060484Sobrienstatic void 19160484Sobriensplay_tree_splay (sp, key) 19260484Sobrien splay_tree sp; 19360484Sobrien splay_tree_key key; 19460484Sobrien{ 19560484Sobrien if (sp->root == 0) 19660484Sobrien return; 19760484Sobrien 19860484Sobrien splay_tree_splay_helper (sp, key, &sp->root, 19960484Sobrien /*grandparent=*/0, /*parent=*/0); 20060484Sobrien} 20160484Sobrien 20260484Sobrien/* Call FN, passing it the DATA, for every node below NODE, all of 20360484Sobrien which are from SP, following an in-order traversal. If FN every 20460484Sobrien returns a non-zero value, the iteration ceases immediately, and the 20560484Sobrien value is returned. Otherwise, this function returns 0. */ 20660484Sobrien 20760484Sobrienstatic int 20860484Sobriensplay_tree_foreach_helper (sp, node, fn, data) 20960484Sobrien splay_tree sp; 21060484Sobrien splay_tree_node node; 21160484Sobrien splay_tree_foreach_fn fn; 21260484Sobrien void* data; 21360484Sobrien{ 21460484Sobrien int val; 21560484Sobrien 21660484Sobrien if (!node) 21760484Sobrien return 0; 21860484Sobrien 21960484Sobrien val = splay_tree_foreach_helper (sp, node->left, fn, data); 22060484Sobrien if (val) 22160484Sobrien return val; 22260484Sobrien 22360484Sobrien val = (*fn)(node, data); 22460484Sobrien if (val) 22560484Sobrien return val; 22660484Sobrien 22760484Sobrien return splay_tree_foreach_helper (sp, node->right, fn, data); 22860484Sobrien} 22960484Sobrien 230104834Sobrien 231104834Sobrien/* An allocator and deallocator based on xmalloc. */ 232104834Sobrienstatic void * 233104834Sobriensplay_tree_xmalloc_allocate (size, data) 234104834Sobrien int size; 235104834Sobrien void *data ATTRIBUTE_UNUSED; 236104834Sobrien{ 237104834Sobrien return xmalloc (size); 238104834Sobrien} 239104834Sobrien 240104834Sobrienstatic void 241104834Sobriensplay_tree_xmalloc_deallocate (object, data) 242104834Sobrien void *object; 243104834Sobrien void *data ATTRIBUTE_UNUSED; 244104834Sobrien{ 245104834Sobrien free (object); 246104834Sobrien} 247104834Sobrien 248104834Sobrien 24960484Sobrien/* Allocate a new splay tree, using COMPARE_FN to compare nodes, 25060484Sobrien DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate 251104834Sobrien values. Use xmalloc to allocate the splay tree structure, and any 252104834Sobrien nodes added. */ 25360484Sobrien 25460484Sobriensplay_tree 25560484Sobriensplay_tree_new (compare_fn, delete_key_fn, delete_value_fn) 25660484Sobrien splay_tree_compare_fn compare_fn; 25760484Sobrien splay_tree_delete_key_fn delete_key_fn; 25860484Sobrien splay_tree_delete_value_fn delete_value_fn; 25960484Sobrien{ 260104834Sobrien return (splay_tree_new_with_allocator 261104834Sobrien (compare_fn, delete_key_fn, delete_value_fn, 262104834Sobrien splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate, 0)); 263104834Sobrien} 264104834Sobrien 265104834Sobrien 266104834Sobrien/* Allocate a new splay tree, using COMPARE_FN to compare nodes, 267104834Sobrien DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate 268104834Sobrien values. */ 269104834Sobrien 270104834Sobriensplay_tree 271104834Sobriensplay_tree_new_with_allocator (compare_fn, delete_key_fn, delete_value_fn, 272104834Sobrien allocate_fn, deallocate_fn, allocate_data) 273104834Sobrien splay_tree_compare_fn compare_fn; 274104834Sobrien splay_tree_delete_key_fn delete_key_fn; 275104834Sobrien splay_tree_delete_value_fn delete_value_fn; 276104834Sobrien splay_tree_allocate_fn allocate_fn; 277104834Sobrien splay_tree_deallocate_fn deallocate_fn; 278104834Sobrien void *allocate_data; 279104834Sobrien{ 280104834Sobrien splay_tree sp = (splay_tree) (*allocate_fn) (sizeof (struct splay_tree_s), 281104834Sobrien allocate_data); 28260484Sobrien sp->root = 0; 28360484Sobrien sp->comp = compare_fn; 28460484Sobrien sp->delete_key = delete_key_fn; 28560484Sobrien sp->delete_value = delete_value_fn; 286104834Sobrien sp->allocate = allocate_fn; 287104834Sobrien sp->deallocate = deallocate_fn; 288104834Sobrien sp->allocate_data = allocate_data; 28960484Sobrien 29060484Sobrien return sp; 29160484Sobrien} 29260484Sobrien 29360484Sobrien/* Deallocate SP. */ 29460484Sobrien 29560484Sobrienvoid 29660484Sobriensplay_tree_delete (sp) 29760484Sobrien splay_tree sp; 29860484Sobrien{ 29960484Sobrien splay_tree_delete_helper (sp, sp->root); 300104834Sobrien (*sp->deallocate) ((char*) sp, sp->allocate_data); 30160484Sobrien} 30260484Sobrien 30360484Sobrien/* Insert a new node (associating KEY with DATA) into SP. If a 30460484Sobrien previous node with the indicated KEY exists, its data is replaced 30560484Sobrien with the new value. Returns the new node. */ 30660484Sobrien 30760484Sobriensplay_tree_node 30860484Sobriensplay_tree_insert (sp, key, value) 30960484Sobrien splay_tree sp; 31060484Sobrien splay_tree_key key; 31160484Sobrien splay_tree_value value; 31260484Sobrien{ 31360484Sobrien int comparison = 0; 31460484Sobrien 31560484Sobrien splay_tree_splay (sp, key); 31660484Sobrien 31760484Sobrien if (sp->root) 31860484Sobrien comparison = (*sp->comp)(sp->root->key, key); 31960484Sobrien 32060484Sobrien if (sp->root && comparison == 0) 32160484Sobrien { 32260484Sobrien /* If the root of the tree already has the indicated KEY, just 32360484Sobrien replace the value with VALUE. */ 32460484Sobrien if (sp->delete_value) 32560484Sobrien (*sp->delete_value)(sp->root->value); 32660484Sobrien sp->root->value = value; 32760484Sobrien } 32860484Sobrien else 32960484Sobrien { 33060484Sobrien /* Create a new node, and insert it at the root. */ 33160484Sobrien splay_tree_node node; 33260484Sobrien 333104834Sobrien node = ((splay_tree_node) 334104834Sobrien (*sp->allocate) (sizeof (struct splay_tree_node_s), 335104834Sobrien sp->allocate_data)); 33660484Sobrien node->key = key; 33760484Sobrien node->value = value; 33860484Sobrien 33960484Sobrien if (!sp->root) 34060484Sobrien node->left = node->right = 0; 34160484Sobrien else if (comparison < 0) 34260484Sobrien { 34360484Sobrien node->left = sp->root; 34460484Sobrien node->right = node->left->right; 34560484Sobrien node->left->right = 0; 34660484Sobrien } 34760484Sobrien else 34860484Sobrien { 34960484Sobrien node->right = sp->root; 35060484Sobrien node->left = node->right->left; 35160484Sobrien node->right->left = 0; 35260484Sobrien } 35360484Sobrien 35477298Sobrien sp->root = node; 35577298Sobrien } 35660484Sobrien 35760484Sobrien return sp->root; 35860484Sobrien} 35960484Sobrien 36077298Sobrien/* Remove KEY from SP. It is not an error if it did not exist. */ 36177298Sobrien 36277298Sobrienvoid 36377298Sobriensplay_tree_remove (sp, key) 36477298Sobrien splay_tree sp; 36577298Sobrien splay_tree_key key; 36677298Sobrien{ 36777298Sobrien splay_tree_splay (sp, key); 36877298Sobrien 36977298Sobrien if (sp->root && (*sp->comp) (sp->root->key, key) == 0) 37077298Sobrien { 37177298Sobrien splay_tree_node left, right; 37277298Sobrien 37377298Sobrien left = sp->root->left; 37477298Sobrien right = sp->root->right; 37577298Sobrien 37677298Sobrien /* Delete the root node itself. */ 37777298Sobrien if (sp->delete_value) 37877298Sobrien (*sp->delete_value) (sp->root->value); 379104834Sobrien (*sp->deallocate) (sp->root, sp->allocate_data); 38077298Sobrien 38177298Sobrien /* One of the children is now the root. Doesn't matter much 38277298Sobrien which, so long as we preserve the properties of the tree. */ 38377298Sobrien if (left) 38477298Sobrien { 38577298Sobrien sp->root = left; 38677298Sobrien 38777298Sobrien /* If there was a right child as well, hang it off the 38877298Sobrien right-most leaf of the left child. */ 38977298Sobrien if (right) 39077298Sobrien { 39177298Sobrien while (left->right) 39277298Sobrien left = left->right; 39377298Sobrien left->right = right; 39477298Sobrien } 39577298Sobrien } 39677298Sobrien else 39777298Sobrien sp->root = right; 39877298Sobrien } 39977298Sobrien} 40077298Sobrien 40160484Sobrien/* Lookup KEY in SP, returning VALUE if present, and NULL 40260484Sobrien otherwise. */ 40360484Sobrien 40460484Sobriensplay_tree_node 40560484Sobriensplay_tree_lookup (sp, key) 40660484Sobrien splay_tree sp; 40760484Sobrien splay_tree_key key; 40860484Sobrien{ 40960484Sobrien splay_tree_splay (sp, key); 41060484Sobrien 41160484Sobrien if (sp->root && (*sp->comp)(sp->root->key, key) == 0) 41260484Sobrien return sp->root; 41360484Sobrien else 41460484Sobrien return 0; 41560484Sobrien} 41660484Sobrien 41789857Sobrien/* Return the node in SP with the greatest key. */ 41889857Sobrien 41989857Sobriensplay_tree_node 42089857Sobriensplay_tree_max (sp) 42189857Sobrien splay_tree sp; 42289857Sobrien{ 42389857Sobrien splay_tree_node n = sp->root; 42489857Sobrien 42589857Sobrien if (!n) 42689857Sobrien return NULL; 42789857Sobrien 42889857Sobrien while (n->right) 42989857Sobrien n = n->right; 43089857Sobrien 43189857Sobrien return n; 43289857Sobrien} 43389857Sobrien 43489857Sobrien/* Return the node in SP with the smallest key. */ 43589857Sobrien 43689857Sobriensplay_tree_node 43789857Sobriensplay_tree_min (sp) 43889857Sobrien splay_tree sp; 43989857Sobrien{ 44089857Sobrien splay_tree_node n = sp->root; 44189857Sobrien 44289857Sobrien if (!n) 44389857Sobrien return NULL; 44489857Sobrien 44589857Sobrien while (n->left) 44689857Sobrien n = n->left; 44789857Sobrien 44889857Sobrien return n; 44989857Sobrien} 45089857Sobrien 45177298Sobrien/* Return the immediate predecessor KEY, or NULL if there is no 45277298Sobrien predecessor. KEY need not be present in the tree. */ 45377298Sobrien 45477298Sobriensplay_tree_node 45577298Sobriensplay_tree_predecessor (sp, key) 45677298Sobrien splay_tree sp; 45777298Sobrien splay_tree_key key; 45877298Sobrien{ 45977298Sobrien int comparison; 46077298Sobrien splay_tree_node node; 46177298Sobrien 46277298Sobrien /* If the tree is empty, there is certainly no predecessor. */ 46377298Sobrien if (!sp->root) 46477298Sobrien return NULL; 46577298Sobrien 46677298Sobrien /* Splay the tree around KEY. That will leave either the KEY 46777298Sobrien itself, its predecessor, or its successor at the root. */ 46877298Sobrien splay_tree_splay (sp, key); 46977298Sobrien comparison = (*sp->comp)(sp->root->key, key); 47077298Sobrien 47177298Sobrien /* If the predecessor is at the root, just return it. */ 47277298Sobrien if (comparison < 0) 47377298Sobrien return sp->root; 47477298Sobrien 47577298Sobrien /* Otherwise, find the leftmost element of the right subtree. */ 47677298Sobrien node = sp->root->left; 47777298Sobrien if (node) 47877298Sobrien while (node->right) 47977298Sobrien node = node->right; 48077298Sobrien 48177298Sobrien return node; 48277298Sobrien} 48377298Sobrien 48477298Sobrien/* Return the immediate successor KEY, or NULL if there is no 48577298Sobrien predecessor. KEY need not be present in the tree. */ 48677298Sobrien 48777298Sobriensplay_tree_node 48877298Sobriensplay_tree_successor (sp, key) 48977298Sobrien splay_tree sp; 49077298Sobrien splay_tree_key key; 49177298Sobrien{ 49277298Sobrien int comparison; 49377298Sobrien splay_tree_node node; 49477298Sobrien 49577298Sobrien /* If the tree is empty, there is certainly no predecessor. */ 49677298Sobrien if (!sp->root) 49777298Sobrien return NULL; 49877298Sobrien 49977298Sobrien /* Splay the tree around KEY. That will leave either the KEY 50077298Sobrien itself, its predecessor, or its successor at the root. */ 50177298Sobrien splay_tree_splay (sp, key); 50277298Sobrien comparison = (*sp->comp)(sp->root->key, key); 50377298Sobrien 50477298Sobrien /* If the successor is at the root, just return it. */ 50577298Sobrien if (comparison > 0) 50677298Sobrien return sp->root; 50777298Sobrien 50877298Sobrien /* Otherwise, find the rightmost element of the left subtree. */ 50977298Sobrien node = sp->root->right; 51077298Sobrien if (node) 51177298Sobrien while (node->left) 51277298Sobrien node = node->left; 51377298Sobrien 51477298Sobrien return node; 51577298Sobrien} 51677298Sobrien 51760484Sobrien/* Call FN, passing it the DATA, for every node in SP, following an 51860484Sobrien in-order traversal. If FN every returns a non-zero value, the 51960484Sobrien iteration ceases immediately, and the value is returned. 52060484Sobrien Otherwise, this function returns 0. */ 52160484Sobrien 52260484Sobrienint 52360484Sobriensplay_tree_foreach (sp, fn, data) 52460484Sobrien splay_tree sp; 52560484Sobrien splay_tree_foreach_fn fn; 52660484Sobrien void *data; 52760484Sobrien{ 52860484Sobrien return splay_tree_foreach_helper (sp, sp->root, fn, data); 52960484Sobrien} 53060484Sobrien 53160484Sobrien/* Splay-tree comparison function, treating the keys as ints. */ 53260484Sobrien 53360484Sobrienint 53460484Sobriensplay_tree_compare_ints (k1, k2) 53560484Sobrien splay_tree_key k1; 53660484Sobrien splay_tree_key k2; 53760484Sobrien{ 53860484Sobrien if ((int) k1 < (int) k2) 53960484Sobrien return -1; 54060484Sobrien else if ((int) k1 > (int) k2) 54160484Sobrien return 1; 54260484Sobrien else 54360484Sobrien return 0; 54460484Sobrien} 54560484Sobrien 54660484Sobrien/* Splay-tree comparison function, treating the keys as pointers. */ 54760484Sobrien 54860484Sobrienint 54960484Sobriensplay_tree_compare_pointers (k1, k2) 55060484Sobrien splay_tree_key k1; 55160484Sobrien splay_tree_key k2; 55260484Sobrien{ 55360484Sobrien if ((char*) k1 < (char*) k2) 55460484Sobrien return -1; 55560484Sobrien else if ((char*) k1 > (char*) k2) 55660484Sobrien return 1; 55760484Sobrien else 55860484Sobrien return 0; 55960484Sobrien} 560