Mercurial > hg > CbC > CbC_gcc

comparison libiberty/splay-tree.c @ 145:1830386684a0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
gcc-9.2.0
author anatofuz
date Thu, 13 Feb 2020 11:34:05 +0900
parents 84e7813d76e9
children
comparison
equal deleted inserted replaced
131:84e7813d76e9 145:1830386684a0
1 /* A splay-tree datatype. 1 /* A splay-tree datatype.
2 Copyright (C) 1998-2018 Free Software Foundation, Inc. 2 Copyright (C) 1998-2020 Free Software Foundation, Inc.
3 Contributed by Mark Mitchell (mark@markmitchell.com). 3 Contributed by Mark Mitchell (mark@markmitchell.com).
4 4
5 This file is part of GNU CC. 5 This file is part of GNU CC.
6 6
7 GNU CC is free software; you can redistribute it and/or modify it 7 GNU CC is free software; you can redistribute it and/or modify it
316 tree itself and its nodes respectively. This is useful when variables of 316 tree itself and its nodes respectively. This is useful when variables of
317 different types need to be allocated with different allocators. 317 different types need to be allocated with different allocators.
318 318
319 The splay tree will use @var{compare_fn} to compare nodes, 319 The splay tree will use @var{compare_fn} to compare nodes,
320 @var{delete_key_fn} to deallocate keys, and @var{delete_value_fn} to 320 @var{delete_key_fn} to deallocate keys, and @var{delete_value_fn} to
321 deallocate values. 321 deallocate values. Keys and values will be deallocated when the
322 tree is deleted using splay_tree_delete or when a node is removed
323 using splay_tree_remove. splay_tree_insert will release the previously
324 inserted key and value using @var{delete_key_fn} and @var{delete_value_fn}
325 if the inserted key is already found in the tree.
322 326
323 @end deftypefn 327 @end deftypefn
324 328
325 */ 329 */
326 330
370 if (sp->root) 374 if (sp->root)
371 comparison = (*sp->comp)(sp->root->key, key); 375 comparison = (*sp->comp)(sp->root->key, key);
372 376
373 if (sp->root && comparison == 0) 377 if (sp->root && comparison == 0)
374 { 378 {
375 /* If the root of the tree already has the indicated KEY, just 379 /* If the root of the tree already has the indicated KEY, delete
376 replace the value with VALUE. */ 380 the old key and old value, and replace them with KEY and VALUE. */
381 if (sp->delete_key)
382 (*sp->delete_key) (sp->root->key);
377 if (sp->delete_value) 383 if (sp->delete_value)
378 (*sp->delete_value)(sp->root->value); 384 (*sp->delete_value)(sp->root->value);
385 sp->root->key = key;
379 sp->root->value = value; 386 sp->root->value = value;
380 } 387 }
381 else 388 else
382 { 389 {
383 /* Create a new node, and insert it at the root. */ 390 /* Create a new node, and insert it at the root. */
423 430
424 left = sp->root->left; 431 left = sp->root->left;
425 right = sp->root->right; 432 right = sp->root->right;
426 433
427 /* Delete the root node itself. */ 434 /* Delete the root node itself. */
435 if (sp->delete_key)
436 (*sp->delete_key) (sp->root->key);
428 if (sp->delete_value) 437 if (sp->delete_value)
429 (*sp->delete_value) (sp->root->value); 438 (*sp->delete_value) (sp->root->value);
430 (*sp->deallocate) (sp->root, sp->allocate_data); 439 (*sp->deallocate) (sp->root, sp->allocate_data);
431 440
432 /* One of the children is now the root. Doesn't matter much 441 /* One of the children is now the root. Doesn't matter much