URL https://opencores.org/ocsvn/or1k/or1k/trunk

Subversion Repositories or1k

[/] [or1k/] [tags/] [start/] [gdb-5.0/] [libiberty/] [splay-tree.c] - Blame information for rev 1778

Go to most recent revision | Details | Compare with Previous | View Log


/* A splay-tree datatype.
   Copyright (C) 1998, 1999 Free Software Foundation, Inc.
   Contributed by Mark Mitchell (mark@markmitchell.com).
 
This file is 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.  */
 
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
 
#ifdef HAVE_STDLIB_H
#include <stdlib.h>
#endif
 
#include "libiberty.h"
#include "splay-tree.h"
 
static void splay_tree_delete_helper    PARAMS((splay_tree,
                                                splay_tree_node));
static void splay_tree_splay            PARAMS((splay_tree,
                                                splay_tree_key));
static splay_tree_node splay_tree_splay_helper
                                        PARAMS((splay_tree,
                                                splay_tree_key,
                                                splay_tree_node*,
                                                splay_tree_node*,
                                                splay_tree_node*));
static int splay_tree_foreach_helper    PARAMS((splay_tree,
                                                splay_tree_node,
                                                splay_tree_foreach_fn,
                                                void*));
 
/* Deallocate NODE (a member of SP), and all its sub-trees.  */
 
static void
splay_tree_delete_helper (sp, node)
     splay_tree sp;
     splay_tree_node node;
{
  if (!node)
    return;
 
  splay_tree_delete_helper (sp, node->left);
  splay_tree_delete_helper (sp, node->right);
 
  if (sp->delete_key)
    (*sp->delete_key)(node->key);
  if (sp->delete_value)
    (*sp->delete_value)(node->value);
 
  free ((char*) node);
}
 
/* Help splay SP around KEY.  PARENT and GRANDPARENT are the parent
   and grandparent, respectively, of NODE.  */
 
static splay_tree_node
splay_tree_splay_helper (sp, key, node, parent, grandparent)
     splay_tree sp;
     splay_tree_key key;
     splay_tree_node *node;
     splay_tree_node *parent;
     splay_tree_node *grandparent;
{
  splay_tree_node *next;
  splay_tree_node n;
  int comparison;
 
  n = *node;
 
  if (!n)
    return *parent;
 
  comparison = (*sp->comp) (key, n->key);
 
  if (comparison == 0)
    /* We've found the target.  */
    next = 0;
  else if (comparison < 0)
    /* The target is to the left.  */
    next = &n->left;
  else
    /* The target is to the right.  */
    next = &n->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)->left)
        {
          *node = n->right;
          n->right = *parent;
        }
      else
        {
          *node = n->left;
          n->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)->left && *parent == (*grandparent)->left)
    {
      splay_tree_node p = *parent;
 
      (*grandparent)->left = p->right;
      p->right = *grandparent;
      p->left = n->right;
      n->right = p;
      *grandparent = n;
      return n;
    }
  else if  (n == (*parent)->right && *parent == (*grandparent)->right)
    {
      splay_tree_node p = *parent;
 
      (*grandparent)->right = p->left;
      p->left = *grandparent;
      p->right = n->left;
      n->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)->left)
    {
      (*parent)->left = n->right;
      n->right = *parent;
      (*grandparent)->right = n->left;
      n->left = *grandparent;
      *grandparent = n;
      return n;
    }
  else
    {
      (*parent)->right = n->left;
      n->left = *parent;
      (*grandparent)->left = n->right;
      n->right = *grandparent;
      *grandparent = n;
      return n;
    }
}
 
/* Splay SP around KEY.  */
 
static void
splay_tree_splay (sp, key)
     splay_tree sp;
     splay_tree_key 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 (sp, node, fn, data)
     splay_tree sp;
     splay_tree_node node;
     splay_tree_foreach_fn fn;
     void* data;
{
  int val;
 
  if (!node)
    return 0;
 
  val = splay_tree_foreach_helper (sp, node->left, fn, data);
  if (val)
    return val;
 
  val = (*fn)(node, data);
  if (val)
    return val;
 
  return splay_tree_foreach_helper (sp, node->right, fn, data);
}
 
/* Allocate a new splay tree, using COMPARE_FN to compare nodes,
   DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
   values.  */
 
splay_tree
splay_tree_new (compare_fn, delete_key_fn, delete_value_fn)
     splay_tree_compare_fn compare_fn;
     splay_tree_delete_key_fn delete_key_fn;
     splay_tree_delete_value_fn delete_value_fn;
{
  splay_tree sp = (splay_tree) xmalloc (sizeof (struct splay_tree_s));
  sp->root = 0;
  sp->comp = compare_fn;
  sp->delete_key = delete_key_fn;
  sp->delete_value = delete_value_fn;
 
  return sp;
}
 
/* Deallocate SP.  */
 
void
splay_tree_delete (sp)
     splay_tree sp;
{
  splay_tree_delete_helper (sp, sp->root);
  free ((char*) 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.  Returns the new node.  */
 
splay_tree_node
splay_tree_insert (sp, key, value)
     splay_tree sp;
     splay_tree_key key;
     splay_tree_value value;
{
  int comparison = 0;
 
  splay_tree_splay (sp, key);
 
  if (sp->root)
    comparison = (*sp->comp)(sp->root->key, key);
 
  if (sp->root && comparison == 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;
    }
  else
    {
      /* Create a new node, and insert it at the root.  */
      splay_tree_node node;
 
      node = (splay_tree_node) xmalloc (sizeof (struct splay_tree_node_s));
      node->key = key;
      node->value = value;
 
      if (!sp->root)
        node->left = node->right = 0;
      else if (comparison < 0)
        {
          node->left = sp->root;
          node->right = node->left->right;
          node->left->right = 0;
        }
      else
        {
          node->right = sp->root;
          node->left = node->right->left;
          node->right->left = 0;
        }
 
    sp->root = node;
  }
 
  return sp->root;
}
 
/* Remove KEY from SP.  It is not an error if it did not exist.  */
 
void
splay_tree_remove (sp, key)
     splay_tree sp;
     splay_tree_key key;
{
  splay_tree_splay (sp, key);
 
  if (sp->root && (*sp->comp) (sp->root->key, key) == 0)
    {
      splay_tree_node left, right;
 
      left = sp->root->left;
      right = sp->root->right;
 
      /* Delete the root node itself.  */
      if (sp->delete_value)
        (*sp->delete_value) (sp->root->value);
      free (sp->root);
 
      /* One of the children is now the root.  Doesn't matter much
         which, so long as we preserve the properties of the tree.  */
      if (left)
        {
          sp->root = left;
 
          /* If there was a right child as well, hang it off the
             right-most leaf of the left child.  */
          if (right)
            {
              while (left->right)
                left = left->right;
              left->right = right;
            }
        }
      else
        sp->root = right;
    }
}
 
/* Lookup KEY in SP, returning VALUE if present, and NULL
   otherwise.  */
 
splay_tree_node
splay_tree_lookup (sp, key)
     splay_tree sp;
     splay_tree_key key;
{
  splay_tree_splay (sp, key);
 
  if (sp->root && (*sp->comp)(sp->root->key, key) == 0)
    return sp->root;
  else
    return 0;
}
 
/* 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
splay_tree_foreach (sp, fn, data)
     splay_tree sp;
     splay_tree_foreach_fn fn;
     void *data;
{
  return splay_tree_foreach_helper (sp, sp->root, fn, data);
}
 
/* Splay-tree comparison function, treating the keys as ints.  */
 
int
splay_tree_compare_ints (k1, k2)
     splay_tree_key k1;
     splay_tree_key k2;
{
  if ((int) k1 < (int) k2)
    return -1;
  else if ((int) k1 > (int) k2)
    return 1;
  else
    return 0;
}
 
/* Splay-tree comparison function, treating the keys as pointers.  */
 
int
splay_tree_compare_pointers (k1, k2)
     splay_tree_key k1;
     splay_tree_key k2;
{
  if ((char*) k1 < (char*) k2)
    return -1;
  else if ((char*) k1 > (char*) k2)
    return 1;
  else
    return 0;
}

Browse

Tools

Subversion Repositories or1k

[/] [or1k/] [tags/] [start/] [gdb-5.0/] [libiberty/] [splay-tree.c] - Blame information for rev 1778

Line No.	Rev	Author	Line
1	106	markom	`/* A splay-tree datatype.`
2			`Copyright (C) 1998, 1999 Free Software Foundation, Inc.`
3			`Contributed by Mark Mitchell (mark@markmitchell.com).`
4
5			`This file is part of GNU CC.`
6
7			`GNU CC is free software; you can redistribute it and/or modify it`
8			`under the terms of the GNU General Public License as published by`
9			`the Free Software Foundation; either version 2, or (at your option)`
10			`any later version.`
11
12			`GNU CC is distributed in the hope that it will be useful, but`
13			`WITHOUT ANY WARRANTY; without even the implied warranty of`
14			`MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU`
15			`General Public License for more details.`
16
17			`You should have received a copy of the GNU General Public License`
18			`along with GNU CC; see the file COPYING. If not, write to`
19			`the Free Software Foundation, 59 Temple Place - Suite 330,`
20			`Boston, MA 02111-1307, USA. */`
21
22			`/* For an easily readable description of splay-trees, see:`
23
24			`Lewis, Harry R. and Denenberg, Larry. Data Structures and Their`
25			`Algorithms. Harper-Collins, Inc. 1991. */`
26
27			`#ifdef HAVE_CONFIG_H`
28			`#include "config.h"`
29			`#endif`
30
31			`#ifdef HAVE_STDLIB_H`
32			`#include <stdlib.h>`
33			`#endif`
34
35			`#include "libiberty.h"`
36			`#include "splay-tree.h"`
37
38			`static void splay_tree_delete_helper PARAMS((splay_tree,`
39			`splay_tree_node));`
40			`static void splay_tree_splay PARAMS((splay_tree,`
41			`splay_tree_key));`
42			`static splay_tree_node splay_tree_splay_helper`
43			`PARAMS((splay_tree,`
44			`splay_tree_key,`
45			`splay_tree_node*,`
46			`splay_tree_node*,`
47			`splay_tree_node*));`
48			`static int splay_tree_foreach_helper PARAMS((splay_tree,`
49			`splay_tree_node,`
50			`splay_tree_foreach_fn,`
51			`void*));`
52
53			`/* Deallocate NODE (a member of SP), and all its sub-trees. */`
54
55			`static void`
56			`splay_tree_delete_helper (sp, node)`
57			`splay_tree sp;`
58			`splay_tree_node node;`
59			`{`
60			`if (!node)`
61			`return;`
62
63			`splay_tree_delete_helper (sp, node->left);`
64			`splay_tree_delete_helper (sp, node->right);`
65
66			`if (sp->delete_key)`
67			`(*sp->delete_key)(node->key);`
68			`if (sp->delete_value)`
69			`(*sp->delete_value)(node->value);`
70
71			`free ((char*) node);`
72			`}`
73
74			`/* Help splay SP around KEY. PARENT and GRANDPARENT are the parent`
75			`and grandparent, respectively, of NODE. */`
76
77			`static splay_tree_node`
78			`splay_tree_splay_helper (sp, key, node, parent, grandparent)`
79			`splay_tree sp;`
80			`splay_tree_key key;`
81			`splay_tree_node *node;`
82			`splay_tree_node *parent;`
83			`splay_tree_node *grandparent;`
84			`{`
85			`splay_tree_node *next;`
86			`splay_tree_node n;`
87			`int comparison;`
88
89			`n = *node;`
90
91			`if (!n)`
92			`return *parent;`
93
94			`comparison = (*sp->comp) (key, n->key);`
95
96			`if (comparison == 0)`
97			`/* We've found the target. */`
98			`next = 0;`
99			`else if (comparison < 0)`
100			`/* The target is to the left. */`
101			`next = &n->left;`
102			`else`
103			`/* The target is to the right. */`
104			`next = &n->right;`
105
106			`if (next)`
107			`{`
108			`/* Continue down the tree. */`
109			`n = splay_tree_splay_helper (sp, key, next, node, parent);`
110
111			`/* The recursive call will change the place to which NODE`
112			`points. */`
113			`if (*node != n)`
114			`return n;`
115			`}`
116
117			`if (!parent)`
118			`/* NODE is the root. We are done. */`
119			`return n;`
120
121			`/* First, handle the case where there is no grandparent (i.e.,`
122			`PARENT is the root of the tree.) /`
123			`if (!grandparent)`
124			`{`
125			`if (n == (*parent)->left)`
126			`{`
127			`*node = n->right;`
128			`n->right = *parent;`
129			`}`
130			`else`
131			`{`
132			`*node = n->left;`
133			`n->left = *parent;`
134			`}`
135			`*parent = n;`
136			`return n;`
137			`}`
138
139			`/* Next handle the cases where both N and *PARENT are left children,`
140			`or where both are right children. */`
141			`if (n == (parent)->left && parent == (*grandparent)->left)`
142			`{`
143			`splay_tree_node p = *parent;`
144
145			`(*grandparent)->left = p->right;`
146			`p->right = *grandparent;`
147			`p->left = n->right;`
148			`n->right = p;`
149			`*grandparent = n;`
150			`return n;`
151			`}`
152			`else if (n == (parent)->right && parent == (*grandparent)->right)`
153			`{`
154			`splay_tree_node p = *parent;`
155
156			`(*grandparent)->right = p->left;`
157			`p->left = *grandparent;`
158			`p->right = n->left;`
159			`n->left = p;`
160			`*grandparent = n;`
161			`return n;`
162			`}`
163
164			`/* Finally, deal with the case where N is a left child, but *PARENT`
165			`is a right child, or vice versa. */`
166			`if (n == (*parent)->left)`
167			`{`
168			`(*parent)->left = n->right;`
169			`n->right = *parent;`
170			`(*grandparent)->right = n->left;`
171			`n->left = *grandparent;`
172			`*grandparent = n;`
173			`return n;`
174			`}`
175			`else`
176			`{`
177			`(*parent)->right = n->left;`
178			`n->left = *parent;`
179			`(*grandparent)->left = n->right;`
180			`n->right = *grandparent;`
181			`*grandparent = n;`
182			`return n;`
183			`}`
184			`}`
185
186			`/* Splay SP around KEY. */`
187
188			`static void`
189			`splay_tree_splay (sp, key)`
190			`splay_tree sp;`
191			`splay_tree_key key;`
192			`{`
193			`if (sp->root == 0)`
194			`return;`
195
196			`splay_tree_splay_helper (sp, key, &sp->root,`
197			`/grandparent=/0, /parent=/0);`
198			`}`
199
200			`/* Call FN, passing it the DATA, for every node below NODE, all of`
201			`which are from SP, following an in-order traversal. If FN every`
202			`returns a non-zero value, the iteration ceases immediately, and the`
203			`value is returned. Otherwise, this function returns 0. */`
204
205			`static int`
206			`splay_tree_foreach_helper (sp, node, fn, data)`
207			`splay_tree sp;`
208			`splay_tree_node node;`
209			`splay_tree_foreach_fn fn;`
210			`void* data;`
211			`{`
212			`int val;`
213
214			`if (!node)`
215			`return 0;`
216
217			`val = splay_tree_foreach_helper (sp, node->left, fn, data);`
218			`if (val)`
219			`return val;`
220
221			`val = (*fn)(node, data);`
222			`if (val)`
223			`return val;`
224
225			`return splay_tree_foreach_helper (sp, node->right, fn, data);`
226			`}`
227
228			`/* Allocate a new splay tree, using COMPARE_FN to compare nodes,`
229			`DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate`
230			`values. */`
231
232			`splay_tree`
233			`splay_tree_new (compare_fn, delete_key_fn, delete_value_fn)`
234			`splay_tree_compare_fn compare_fn;`
235			`splay_tree_delete_key_fn delete_key_fn;`
236			`splay_tree_delete_value_fn delete_value_fn;`
237			`{`
238			`splay_tree sp = (splay_tree) xmalloc (sizeof (struct splay_tree_s));`
239			`sp->root = 0;`
240			`sp->comp = compare_fn;`
241			`sp->delete_key = delete_key_fn;`
242			`sp->delete_value = delete_value_fn;`
243
244			`return sp;`
245			`}`
246
247			`/* Deallocate SP. */`
248
249			`void`
250			`splay_tree_delete (sp)`
251			`splay_tree sp;`
252			`{`
253			`splay_tree_delete_helper (sp, sp->root);`
254			`free ((char*) sp);`
255			`}`
256
257			`/* Insert a new node (associating KEY with DATA) into SP. If a`
258			`previous node with the indicated KEY exists, its data is replaced`
259			`with the new value. Returns the new node. */`
260
261			`splay_tree_node`
262			`splay_tree_insert (sp, key, value)`
263			`splay_tree sp;`
264			`splay_tree_key key;`
265			`splay_tree_value value;`
266			`{`
267			`int comparison = 0;`
268
269			`splay_tree_splay (sp, key);`
270
271			`if (sp->root)`
272			`comparison = (*sp->comp)(sp->root->key, key);`
273
274			`if (sp->root && comparison == 0)`
275			`{`
276			`/* If the root of the tree already has the indicated KEY, just`
277			`replace the value with VALUE. */`
278			`if (sp->delete_value)`
279			`(*sp->delete_value)(sp->root->value);`
280			`sp->root->value = value;`
281			`}`
282			`else`
283			`{`
284			`/* Create a new node, and insert it at the root. */`
285			`splay_tree_node node;`
286
287			`node = (splay_tree_node) xmalloc (sizeof (struct splay_tree_node_s));`
288			`node->key = key;`
289			`node->value = value;`
290
291			`if (!sp->root)`
292			`node->left = node->right = 0;`
293			`else if (comparison < 0)`
294			`{`
295			`node->left = sp->root;`
296			`node->right = node->left->right;`
297			`node->left->right = 0;`
298			`}`
299			`else`
300			`{`
301			`node->right = sp->root;`
302			`node->left = node->right->left;`
303			`node->right->left = 0;`
304			`}`
305
306			`sp->root = node;`
307			`}`
308
309			`return sp->root;`
310			`}`
311
312			`/* Remove KEY from SP. It is not an error if it did not exist. */`
313
314			`void`
315			`splay_tree_remove (sp, key)`
316			`splay_tree sp;`
317			`splay_tree_key key;`
318			`{`
319			`splay_tree_splay (sp, key);`
320
321			`if (sp->root && (*sp->comp) (sp->root->key, key) == 0)`
322			`{`
323			`splay_tree_node left, right;`
324
325			`left = sp->root->left;`
326			`right = sp->root->right;`
327
328			`/* Delete the root node itself. */`
329			`if (sp->delete_value)`
330			`(*sp->delete_value) (sp->root->value);`
331			`free (sp->root);`
332
333			`/* One of the children is now the root. Doesn't matter much`
334			`which, so long as we preserve the properties of the tree. */`
335			`if (left)`
336			`{`
337			`sp->root = left;`
338
339			`/* If there was a right child as well, hang it off the`
340			`right-most leaf of the left child. */`
341			`if (right)`
342			`{`
343			`while (left->right)`
344			`left = left->right;`
345			`left->right = right;`
346			`}`
347			`}`
348			`else`
349			`sp->root = right;`
350			`}`
351			`}`
352
353			`/* Lookup KEY in SP, returning VALUE if present, and NULL`
354			`otherwise. */`
355
356			`splay_tree_node`
357			`splay_tree_lookup (sp, key)`
358			`splay_tree sp;`
359			`splay_tree_key key;`
360			`{`
361			`splay_tree_splay (sp, key);`
362
363			`if (sp->root && (*sp->comp)(sp->root->key, key) == 0)`
364			`return sp->root;`
365			`else`
366			`return 0;`
367			`}`
368
369			`/* Call FN, passing it the DATA, for every node in SP, following an`
370			`in-order traversal. If FN every returns a non-zero value, the`
371			`iteration ceases immediately, and the value is returned.`
372			`Otherwise, this function returns 0. */`
373
374			`int`
375			`splay_tree_foreach (sp, fn, data)`
376			`splay_tree sp;`
377			`splay_tree_foreach_fn fn;`
378			`void *data;`
379			`{`
380			`return splay_tree_foreach_helper (sp, sp->root, fn, data);`
381			`}`
382
383			`/* Splay-tree comparison function, treating the keys as ints. */`
384
385			`int`
386			`splay_tree_compare_ints (k1, k2)`
387			`splay_tree_key k1;`
388			`splay_tree_key k2;`
389			`{`
390			`if ((int) k1 < (int) k2)`
391			`return -1;`
392			`else if ((int) k1 > (int) k2)`
393			`return 1;`
394			`else`
395			`return 0;`
396			`}`
397
398			`/* Splay-tree comparison function, treating the keys as pointers. */`
399
400			`int`
401			`splay_tree_compare_pointers (k1, k2)`
402			`splay_tree_key k1;`
403			`splay_tree_key k2;`
404			`{`
405			`if ((char) k1 < (char) k2)`
406			`return -1;`
407			`else if ((char) k1 > (char) k2)`
408			`return 1;`
409			`else`
410			`return 0;`
411			`}`