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 19218822Sdimthe Free Software Foundation, 51 Franklin Street - Fifth Floor, 20218822SdimBoston, MA 02110-1301, 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 40218822Sdimstatic void splay_tree_delete_helper (splay_tree, splay_tree_node); 41218822Sdimstatic inline void rotate_left (splay_tree_node *, 42218822Sdim splay_tree_node, splay_tree_node); 43218822Sdimstatic inline void rotate_right (splay_tree_node *, 44218822Sdim splay_tree_node, splay_tree_node); 45218822Sdimstatic void splay_tree_splay (splay_tree, splay_tree_key); 46218822Sdimstatic int splay_tree_foreach_helper (splay_tree, splay_tree_node, 47218822Sdim splay_tree_foreach_fn, void*); 4860484Sobrien 4960484Sobrien/* Deallocate NODE (a member of SP), and all its sub-trees. */ 5060484Sobrien 5160484Sobrienstatic void 52218822Sdimsplay_tree_delete_helper (splay_tree sp, splay_tree_node node) 5360484Sobrien{ 54218822Sdim splay_tree_node pending = 0; 55218822Sdim splay_tree_node active = 0; 56218822Sdim 5760484Sobrien if (!node) 5860484Sobrien return; 5960484Sobrien 60218822Sdim#define KDEL(x) if (sp->delete_key) (*sp->delete_key)(x); 61218822Sdim#define VDEL(x) if (sp->delete_value) (*sp->delete_value)(x); 6260484Sobrien 63218822Sdim KDEL (node->key); 64218822Sdim VDEL (node->value); 6560484Sobrien 66218822Sdim /* We use the "key" field to hold the "next" pointer. */ 67218822Sdim node->key = (splay_tree_key)pending; 68218822Sdim pending = (splay_tree_node)node; 6960484Sobrien 70218822Sdim /* Now, keep processing the pending list until there aren't any 71218822Sdim more. This is a little more complicated than just recursing, but 72218822Sdim it doesn't toast the stack for large trees. */ 7360484Sobrien 74218822Sdim while (pending) 7560484Sobrien { 76218822Sdim active = pending; 77218822Sdim pending = 0; 78218822Sdim while (active) 79218822Sdim { 80218822Sdim splay_tree_node temp; 8160484Sobrien 82218822Sdim /* active points to a node which has its key and value 83218822Sdim deallocated, we just need to process left and right. */ 8460484Sobrien 85218822Sdim if (active->left) 86218822Sdim { 87218822Sdim KDEL (active->left->key); 88218822Sdim VDEL (active->left->value); 89218822Sdim active->left->key = (splay_tree_key)pending; 90218822Sdim pending = (splay_tree_node)(active->left); 91218822Sdim } 92218822Sdim if (active->right) 93218822Sdim { 94218822Sdim KDEL (active->right->key); 95218822Sdim VDEL (active->right->value); 96218822Sdim active->right->key = (splay_tree_key)pending; 97218822Sdim pending = (splay_tree_node)(active->right); 98218822Sdim } 9960484Sobrien 100218822Sdim temp = active; 101218822Sdim active = (splay_tree_node)(temp->key); 102218822Sdim (*sp->deallocate) ((char*) temp, sp->allocate_data); 10360484Sobrien } 10460484Sobrien } 105218822Sdim#undef KDEL 106218822Sdim#undef VDEL 107218822Sdim} 10860484Sobrien 109218822Sdim/* Rotate the edge joining the left child N with its parent P. PP is the 110218822Sdim grandparents pointer to P. */ 11160484Sobrien 112218822Sdimstatic inline void 113218822Sdimrotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n) 114218822Sdim{ 115218822Sdim splay_tree_node tmp; 116218822Sdim tmp = n->right; 117218822Sdim n->right = p; 118218822Sdim p->left = tmp; 119218822Sdim *pp = n; 120218822Sdim} 12160484Sobrien 122218822Sdim/* Rotate the edge joining the right child N with its parent P. PP is the 123218822Sdim grandparents pointer to P. */ 12460484Sobrien 125218822Sdimstatic inline void 126218822Sdimrotate_right (splay_tree_node *pp, splay_tree_node p, splay_tree_node n) 127218822Sdim{ 128218822Sdim splay_tree_node tmp; 129218822Sdim tmp = n->left; 130218822Sdim n->left = p; 131218822Sdim p->right = tmp; 132218822Sdim *pp = n; 13360484Sobrien} 13460484Sobrien 135218822Sdim/* Bottom up splay of key. */ 13660484Sobrien 13760484Sobrienstatic void 138218822Sdimsplay_tree_splay (splay_tree sp, splay_tree_key key) 13960484Sobrien{ 14060484Sobrien if (sp->root == 0) 14160484Sobrien return; 14260484Sobrien 143218822Sdim do { 144218822Sdim int cmp1, cmp2; 145218822Sdim splay_tree_node n, c; 146218822Sdim 147218822Sdim n = sp->root; 148218822Sdim cmp1 = (*sp->comp) (key, n->key); 149218822Sdim 150218822Sdim /* Found. */ 151218822Sdim if (cmp1 == 0) 152218822Sdim return; 153218822Sdim 154218822Sdim /* Left or right? If no child, then we're done. */ 155218822Sdim if (cmp1 < 0) 156218822Sdim c = n->left; 157218822Sdim else 158218822Sdim c = n->right; 159218822Sdim if (!c) 160218822Sdim return; 161218822Sdim 162218822Sdim /* Next one left or right? If found or no child, we're done 163218822Sdim after one rotation. */ 164218822Sdim cmp2 = (*sp->comp) (key, c->key); 165218822Sdim if (cmp2 == 0 166218822Sdim || (cmp2 < 0 && !c->left) 167218822Sdim || (cmp2 > 0 && !c->right)) 168218822Sdim { 169218822Sdim if (cmp1 < 0) 170218822Sdim rotate_left (&sp->root, n, c); 171218822Sdim else 172218822Sdim rotate_right (&sp->root, n, c); 173218822Sdim return; 174218822Sdim } 175218822Sdim 176218822Sdim /* Now we have the four cases of double-rotation. */ 177218822Sdim if (cmp1 < 0 && cmp2 < 0) 178218822Sdim { 179218822Sdim rotate_left (&n->left, c, c->left); 180218822Sdim rotate_left (&sp->root, n, n->left); 181218822Sdim } 182218822Sdim else if (cmp1 > 0 && cmp2 > 0) 183218822Sdim { 184218822Sdim rotate_right (&n->right, c, c->right); 185218822Sdim rotate_right (&sp->root, n, n->right); 186218822Sdim } 187218822Sdim else if (cmp1 < 0 && cmp2 > 0) 188218822Sdim { 189218822Sdim rotate_right (&n->left, c, c->right); 190218822Sdim rotate_left (&sp->root, n, n->left); 191218822Sdim } 192218822Sdim else if (cmp1 > 0 && cmp2 < 0) 193218822Sdim { 194218822Sdim rotate_left (&n->right, c, c->left); 195218822Sdim rotate_right (&sp->root, n, n->right); 196218822Sdim } 197218822Sdim } while (1); 19860484Sobrien} 19960484Sobrien 20060484Sobrien/* Call FN, passing it the DATA, for every node below NODE, all of 20160484Sobrien which are from SP, following an in-order traversal. If FN every 20260484Sobrien returns a non-zero value, the iteration ceases immediately, and the 20360484Sobrien value is returned. Otherwise, this function returns 0. */ 20460484Sobrien 20560484Sobrienstatic int 206218822Sdimsplay_tree_foreach_helper (splay_tree sp, splay_tree_node node, 207218822Sdim splay_tree_foreach_fn fn, void *data) 20860484Sobrien{ 20960484Sobrien int val; 21060484Sobrien 21160484Sobrien if (!node) 21260484Sobrien return 0; 21360484Sobrien 21460484Sobrien val = splay_tree_foreach_helper (sp, node->left, fn, data); 21560484Sobrien if (val) 21660484Sobrien return val; 21760484Sobrien 21860484Sobrien val = (*fn)(node, data); 21960484Sobrien if (val) 22060484Sobrien return val; 22160484Sobrien 22260484Sobrien return splay_tree_foreach_helper (sp, node->right, fn, data); 22360484Sobrien} 22460484Sobrien 225104834Sobrien 226104834Sobrien/* An allocator and deallocator based on xmalloc. */ 227104834Sobrienstatic void * 228218822Sdimsplay_tree_xmalloc_allocate (int size, void *data ATTRIBUTE_UNUSED) 229104834Sobrien{ 230130561Sobrien return (void *) xmalloc (size); 231104834Sobrien} 232104834Sobrien 233104834Sobrienstatic void 234218822Sdimsplay_tree_xmalloc_deallocate (void *object, void *data ATTRIBUTE_UNUSED) 235104834Sobrien{ 236104834Sobrien free (object); 237104834Sobrien} 238104834Sobrien 239104834Sobrien 24060484Sobrien/* Allocate a new splay tree, using COMPARE_FN to compare nodes, 24160484Sobrien DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate 242104834Sobrien values. Use xmalloc to allocate the splay tree structure, and any 243104834Sobrien nodes added. */ 24460484Sobrien 24560484Sobriensplay_tree 246218822Sdimsplay_tree_new (splay_tree_compare_fn compare_fn, 247218822Sdim splay_tree_delete_key_fn delete_key_fn, 248218822Sdim splay_tree_delete_value_fn delete_value_fn) 24960484Sobrien{ 250104834Sobrien return (splay_tree_new_with_allocator 251104834Sobrien (compare_fn, delete_key_fn, delete_value_fn, 252104834Sobrien splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate, 0)); 253104834Sobrien} 254104834Sobrien 255104834Sobrien 256104834Sobrien/* Allocate a new splay tree, using COMPARE_FN to compare nodes, 257104834Sobrien DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate 258104834Sobrien values. */ 259104834Sobrien 260104834Sobriensplay_tree 261218822Sdimsplay_tree_new_with_allocator (splay_tree_compare_fn compare_fn, 262218822Sdim splay_tree_delete_key_fn delete_key_fn, 263218822Sdim splay_tree_delete_value_fn delete_value_fn, 264218822Sdim splay_tree_allocate_fn allocate_fn, 265218822Sdim splay_tree_deallocate_fn deallocate_fn, 266218822Sdim void *allocate_data) 267104834Sobrien{ 268104834Sobrien splay_tree sp = (splay_tree) (*allocate_fn) (sizeof (struct splay_tree_s), 269104834Sobrien allocate_data); 27060484Sobrien sp->root = 0; 27160484Sobrien sp->comp = compare_fn; 27260484Sobrien sp->delete_key = delete_key_fn; 27360484Sobrien sp->delete_value = delete_value_fn; 274104834Sobrien sp->allocate = allocate_fn; 275104834Sobrien sp->deallocate = deallocate_fn; 276104834Sobrien sp->allocate_data = allocate_data; 27760484Sobrien 27860484Sobrien return sp; 27960484Sobrien} 28060484Sobrien 28160484Sobrien/* Deallocate SP. */ 28260484Sobrien 28360484Sobrienvoid 284218822Sdimsplay_tree_delete (splay_tree sp) 28560484Sobrien{ 28660484Sobrien splay_tree_delete_helper (sp, sp->root); 287104834Sobrien (*sp->deallocate) ((char*) sp, sp->allocate_data); 28860484Sobrien} 28960484Sobrien 29060484Sobrien/* Insert a new node (associating KEY with DATA) into SP. If a 29160484Sobrien previous node with the indicated KEY exists, its data is replaced 29260484Sobrien with the new value. Returns the new node. */ 29360484Sobrien 29460484Sobriensplay_tree_node 295218822Sdimsplay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value) 29660484Sobrien{ 29760484Sobrien int comparison = 0; 29860484Sobrien 29960484Sobrien splay_tree_splay (sp, key); 30060484Sobrien 30160484Sobrien if (sp->root) 30260484Sobrien comparison = (*sp->comp)(sp->root->key, key); 30360484Sobrien 30460484Sobrien if (sp->root && comparison == 0) 30560484Sobrien { 30660484Sobrien /* If the root of the tree already has the indicated KEY, just 30760484Sobrien replace the value with VALUE. */ 30860484Sobrien if (sp->delete_value) 30960484Sobrien (*sp->delete_value)(sp->root->value); 31060484Sobrien sp->root->value = value; 31160484Sobrien } 31260484Sobrien else 31360484Sobrien { 31460484Sobrien /* Create a new node, and insert it at the root. */ 31560484Sobrien splay_tree_node node; 31660484Sobrien 317104834Sobrien node = ((splay_tree_node) 318104834Sobrien (*sp->allocate) (sizeof (struct splay_tree_node_s), 319104834Sobrien sp->allocate_data)); 32060484Sobrien node->key = key; 32160484Sobrien node->value = value; 32260484Sobrien 32360484Sobrien if (!sp->root) 32460484Sobrien node->left = node->right = 0; 32560484Sobrien else if (comparison < 0) 32660484Sobrien { 32760484Sobrien node->left = sp->root; 32860484Sobrien node->right = node->left->right; 32960484Sobrien node->left->right = 0; 33060484Sobrien } 33160484Sobrien else 33260484Sobrien { 33360484Sobrien node->right = sp->root; 33460484Sobrien node->left = node->right->left; 33560484Sobrien node->right->left = 0; 33660484Sobrien } 33760484Sobrien 33877298Sobrien sp->root = node; 33977298Sobrien } 34060484Sobrien 34160484Sobrien return sp->root; 34260484Sobrien} 34360484Sobrien 34477298Sobrien/* Remove KEY from SP. It is not an error if it did not exist. */ 34577298Sobrien 34677298Sobrienvoid 347218822Sdimsplay_tree_remove (splay_tree sp, splay_tree_key key) 34877298Sobrien{ 34977298Sobrien splay_tree_splay (sp, key); 35077298Sobrien 35177298Sobrien if (sp->root && (*sp->comp) (sp->root->key, key) == 0) 35277298Sobrien { 35377298Sobrien splay_tree_node left, right; 35477298Sobrien 35577298Sobrien left = sp->root->left; 35677298Sobrien right = sp->root->right; 35777298Sobrien 35877298Sobrien /* Delete the root node itself. */ 35977298Sobrien if (sp->delete_value) 36077298Sobrien (*sp->delete_value) (sp->root->value); 361104834Sobrien (*sp->deallocate) (sp->root, sp->allocate_data); 36277298Sobrien 36377298Sobrien /* One of the children is now the root. Doesn't matter much 36477298Sobrien which, so long as we preserve the properties of the tree. */ 36577298Sobrien if (left) 36677298Sobrien { 36777298Sobrien sp->root = left; 36877298Sobrien 36977298Sobrien /* If there was a right child as well, hang it off the 37077298Sobrien right-most leaf of the left child. */ 37177298Sobrien if (right) 37277298Sobrien { 37377298Sobrien while (left->right) 37477298Sobrien left = left->right; 37577298Sobrien left->right = right; 37677298Sobrien } 37777298Sobrien } 37877298Sobrien else 37977298Sobrien sp->root = right; 38077298Sobrien } 38177298Sobrien} 38277298Sobrien 38360484Sobrien/* Lookup KEY in SP, returning VALUE if present, and NULL 38460484Sobrien otherwise. */ 38560484Sobrien 38660484Sobriensplay_tree_node 387218822Sdimsplay_tree_lookup (splay_tree sp, splay_tree_key key) 38860484Sobrien{ 38960484Sobrien splay_tree_splay (sp, key); 39060484Sobrien 39160484Sobrien if (sp->root && (*sp->comp)(sp->root->key, key) == 0) 39260484Sobrien return sp->root; 39360484Sobrien else 39460484Sobrien return 0; 39560484Sobrien} 39660484Sobrien 39789857Sobrien/* Return the node in SP with the greatest key. */ 39889857Sobrien 39989857Sobriensplay_tree_node 400218822Sdimsplay_tree_max (splay_tree sp) 40189857Sobrien{ 40289857Sobrien splay_tree_node n = sp->root; 40389857Sobrien 40489857Sobrien if (!n) 40589857Sobrien return NULL; 40689857Sobrien 40789857Sobrien while (n->right) 40889857Sobrien n = n->right; 40989857Sobrien 41089857Sobrien return n; 41189857Sobrien} 41289857Sobrien 41389857Sobrien/* Return the node in SP with the smallest key. */ 41489857Sobrien 41589857Sobriensplay_tree_node 416218822Sdimsplay_tree_min (splay_tree sp) 41789857Sobrien{ 41889857Sobrien splay_tree_node n = sp->root; 41989857Sobrien 42089857Sobrien if (!n) 42189857Sobrien return NULL; 42289857Sobrien 42389857Sobrien while (n->left) 42489857Sobrien n = n->left; 42589857Sobrien 42689857Sobrien return n; 42789857Sobrien} 42889857Sobrien 42977298Sobrien/* Return the immediate predecessor KEY, or NULL if there is no 43077298Sobrien predecessor. KEY need not be present in the tree. */ 43177298Sobrien 43277298Sobriensplay_tree_node 433218822Sdimsplay_tree_predecessor (splay_tree sp, splay_tree_key key) 43477298Sobrien{ 43577298Sobrien int comparison; 43677298Sobrien splay_tree_node node; 43777298Sobrien 43877298Sobrien /* If the tree is empty, there is certainly no predecessor. */ 43977298Sobrien if (!sp->root) 44077298Sobrien return NULL; 44177298Sobrien 44277298Sobrien /* Splay the tree around KEY. That will leave either the KEY 44377298Sobrien itself, its predecessor, or its successor at the root. */ 44477298Sobrien splay_tree_splay (sp, key); 44577298Sobrien comparison = (*sp->comp)(sp->root->key, key); 44677298Sobrien 44777298Sobrien /* If the predecessor is at the root, just return it. */ 44877298Sobrien if (comparison < 0) 44977298Sobrien return sp->root; 45077298Sobrien 451130561Sobrien /* Otherwise, find the rightmost element of the left subtree. */ 45277298Sobrien node = sp->root->left; 45377298Sobrien if (node) 45477298Sobrien while (node->right) 45577298Sobrien node = node->right; 45677298Sobrien 45777298Sobrien return node; 45877298Sobrien} 45977298Sobrien 46077298Sobrien/* Return the immediate successor KEY, or NULL if there is no 461130561Sobrien successor. KEY need not be present in the tree. */ 46277298Sobrien 46377298Sobriensplay_tree_node 464218822Sdimsplay_tree_successor (splay_tree sp, splay_tree_key key) 46577298Sobrien{ 46677298Sobrien int comparison; 46777298Sobrien splay_tree_node node; 46877298Sobrien 469130561Sobrien /* If the tree is empty, there is certainly no successor. */ 47077298Sobrien if (!sp->root) 47177298Sobrien return NULL; 47277298Sobrien 47377298Sobrien /* Splay the tree around KEY. That will leave either the KEY 47477298Sobrien itself, its predecessor, or its successor at the root. */ 47577298Sobrien splay_tree_splay (sp, key); 47677298Sobrien comparison = (*sp->comp)(sp->root->key, key); 47777298Sobrien 47877298Sobrien /* If the successor is at the root, just return it. */ 47977298Sobrien if (comparison > 0) 48077298Sobrien return sp->root; 48177298Sobrien 482130561Sobrien /* Otherwise, find the leftmost element of the right subtree. */ 48377298Sobrien node = sp->root->right; 48477298Sobrien if (node) 48577298Sobrien while (node->left) 48677298Sobrien node = node->left; 48777298Sobrien 48877298Sobrien return node; 48977298Sobrien} 49077298Sobrien 49160484Sobrien/* Call FN, passing it the DATA, for every node in SP, following an 49260484Sobrien in-order traversal. If FN every returns a non-zero value, the 49360484Sobrien iteration ceases immediately, and the value is returned. 49460484Sobrien Otherwise, this function returns 0. */ 49560484Sobrien 49660484Sobrienint 497218822Sdimsplay_tree_foreach (splay_tree sp, splay_tree_foreach_fn fn, void *data) 49860484Sobrien{ 49960484Sobrien return splay_tree_foreach_helper (sp, sp->root, fn, data); 50060484Sobrien} 50160484Sobrien 50260484Sobrien/* Splay-tree comparison function, treating the keys as ints. */ 50360484Sobrien 50460484Sobrienint 505218822Sdimsplay_tree_compare_ints (splay_tree_key k1, splay_tree_key k2) 50660484Sobrien{ 50760484Sobrien if ((int) k1 < (int) k2) 50860484Sobrien return -1; 50960484Sobrien else if ((int) k1 > (int) k2) 51060484Sobrien return 1; 51160484Sobrien else 51260484Sobrien return 0; 51360484Sobrien} 51460484Sobrien 51560484Sobrien/* Splay-tree comparison function, treating the keys as pointers. */ 51660484Sobrien 51760484Sobrienint 518218822Sdimsplay_tree_compare_pointers (splay_tree_key k1, splay_tree_key k2) 51960484Sobrien{ 52060484Sobrien if ((char*) k1 < (char*) k2) 52160484Sobrien return -1; 52260484Sobrien else if ((char*) k1 > (char*) k2) 52360484Sobrien return 1; 52460484Sobrien else 52560484Sobrien return 0; 52660484Sobrien} 527