binutils/libiberty/splay-tree.c

52 splay_tree_delete_helper (splay_tree sp, splay_tree_node node)
60 #define KDEL(x)  if (sp->delete_key) (*sp->delete_key)(x);
61 #define VDEL(x)  if (sp->delete_value) (*sp->delete_value)(x);
102 	  (*sp->deallocate) ((char*) temp, sp->allocate_data);
138 splay_tree_splay (splay_tree sp, splay_tree_key key)
140   if (sp->root == 0)
147     n = sp->root;
148     cmp1 = (*sp->comp) (key, n->key);
164     cmp2 = (*sp->comp) (key, c->key);
170 	  rotate_left (&sp->root, n, c);
172 	  rotate_right (&sp->root, n, c);
180 	rotate_left (&sp->root, n, n->left);
185 	rotate_right (&sp->root, n, n->right);
190 	rotate_left (&sp->root, n, n->left);
195 	rotate_right (&sp->root, n, n->right);
206 splay_tree_foreach_helper (splay_tree sp, splay_tree_node node,
214   val = splay_tree_foreach_helper (sp, node->left, fn, data);
222   return splay_tree_foreach_helper (sp, node->right, fn, data);
268   splay_tree sp = (splay_tree) (*allocate_fn) (sizeof (struct splay_tree_s),
270   sp->root = 0;
271   sp->comp = compare_fn;
272   sp->delete_key = delete_key_fn;
273   sp->delete_value = delete_value_fn;
274   sp->allocate = allocate_fn;
275   sp->deallocate = deallocate_fn;
276   sp->allocate_data = allocate_data;
278   return sp;
284 splay_tree_delete (splay_tree sp)
286   splay_tree_delete_helper (sp, sp->root);
287   (*sp->deallocate) ((char*) sp, sp->allocate_data);
295 splay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value)
299   splay_tree_splay (sp, key);
301   if (sp->root)
302     comparison = (*sp->comp)(sp->root->key, key);
304   if (sp->root && comparison == 0)
308       if (sp->delete_value)
309 	(*sp->delete_value)(sp->root->value);
310       sp->root->value = value;
318               (*sp->allocate) (sizeof (struct splay_tree_node_s),
319                                sp->allocate_data));
323       if (!sp->root)
327 	  node->left = sp->root;
333 	  node->right = sp->root;
338       sp->root = node;
341   return sp->root;
347 splay_tree_remove (splay_tree sp, splay_tree_key key)
349   splay_tree_splay (sp, key);
351   if (sp->root && (*sp->comp) (sp->root->key, key) == 0)
355       left = sp->root->left;
356       right = sp->root->right;
359       if (sp->delete_value)
360 	(*sp->delete_value) (sp->root->value);
361       (*sp->deallocate) (sp->root, sp->allocate_data);
367 	  sp->root = left;
379 	sp->root = right;
387 splay_tree_lookup (splay_tree sp, splay_tree_key key)
389   splay_tree_splay (sp, key);
391   if (sp->root && (*sp->comp)(sp->root->key, key) == 0)
392     return sp->root;
400 splay_tree_max (splay_tree sp)
402   splay_tree_node n = sp->root;
416 splay_tree_min (splay_tree sp)
418   splay_tree_node n = sp->root;
433 splay_tree_predecessor (splay_tree sp, splay_tree_key key)
439   if (!sp->root)
444   splay_tree_splay (sp, key);
445   comparison = (*sp->comp)(sp->root->key, key);
449     return sp->root;
452   node = sp->root->left;
464 splay_tree_successor (splay_tree sp, splay_tree_key key)
470   if (!sp->root)
475   splay_tree_splay (sp, key);
476   comparison = (*sp->comp)(sp->root->key, key);
480     return sp->root;
483   node = sp->root->right;
497 splay_tree_foreach (splay_tree sp, splay_tree_foreach_fn fn, void *data)
499   return splay_tree_foreach_helper (sp, sp->root, fn, data);