1
0

bintree_remove.c 2.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081
  1. /*********************** -*- Mode: C -*- ***********************
  2. * File : bintree_remove.c
  3. *---------------------------------------------------------------
  4. * Description
  5. * ===========
  6. * This operation removes a "node" from the specified "tree"
  7. *
  8. * tree - the "tree" instance to invoke this operation upon
  9. * clientnode - the node to remove
  10. *
  11. * RETURNS
  12. * none
  13. *
  14. * POST CONDITIONS
  15. * The "node" will no longer be part of the specified tree, and can be
  16. * subsequently re-inserted
  17. *
  18. * If the node is not present in the specified tree, then an assert
  19. * will fire.
  20. *---------------------------------------------------------------
  21. * Author : Graeme McKerrell
  22. * Created On : Wed Jan 28 10:06:58 2004
  23. * Status : TESTED
  24. *---------------------------------------------------------------
  25. * HISTORY
  26. * 27-Dec-2004 Graeme McKerrell
  27. * added assert to catch removal of invalid node
  28. * 7-Dec-2004 Graeme McKerrell
  29. * Renamed to the "lub_" namespace
  30. * 5-May-2004 Graeme McKerrell
  31. * updates following review
  32. * 23-Mar-2004 Graeme McKerrell
  33. * fixed to ensure that control block is re-initialised.
  34. * 16-Mar-2004 Graeme McKerrell
  35. * removed assert.
  36. * 27-Feb-2004 Graeme McKerrell
  37. * removed spurious call to node_init
  38. * 9-Feb-2004 Graeme McKerrell
  39. * updated to use new node,key comparison ordering
  40. * 28-Jan-2004 Graeme McKerrell
  41. * Initial version
  42. *---------------------------------------------------------------
  43. * Copyright (C) 2004 3Com Corporation. All Rights Reserved.
  44. **************************************************************** */
  45. #include <assert.h>
  46. #include "private.h"
  47. /*--------------------------------------------------------- */
  48. void lub_bintree_remove(lub_bintree_t * this, void *clientnode)
  49. {
  50. lub_bintree_node_t *x, *t;
  51. lub_bintree_key_t key;
  52. int comp;
  53. /* get the key from the node */
  54. this->getkeyFn(clientnode, &key);
  55. /* bring the node in question to the root of the tree */
  56. t = lub_bintree_splay(this, this->root, &key);
  57. /* check that the node was there to remove */
  58. comp = lub_bintree_compare(this, t, &key);
  59. assert(0 == comp);
  60. if (0 == comp) {
  61. if (t->left == NULL) {
  62. x = t->right;
  63. } else {
  64. x = lub_bintree_splay(this, t->left, &key);
  65. x->right = t->right;
  66. }
  67. /* set the new root */
  68. this->root = x;
  69. /* re-initialise the node control block for re-use */
  70. lub_bintree_node_init(lub_bintree_getnode(this, clientnode));
  71. }
  72. }
  73. /*--------------------------------------------------------- */