1
0

bintree_insert.c 3.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103
  1. /*********************** -*- Mode: C -*- ***********************
  2. * File : bintree_insert.c
  3. *---------------------------------------------------------------
  4. * Description
  5. * ===========
  6. * This operation adds a client node to the specified tree.
  7. *
  8. * tree - the "tree" instance to invoke this operation upon
  9. * clientnode - a pointer to a client node. NB the tree can find the
  10. * necessary util_BintreeNodeT from it's stored offset.
  11. *
  12. * RETURNS
  13. * 0 if the "clientnode" is added correctly to the tree.
  14. *
  15. * If another "clientnode" already exists in the tree with the same key, then
  16. * -1 is returned, and the tree remains unchanged.
  17. *
  18. * If the "clientnode" had not been initialised, then an assert will fire.
  19. *
  20. * If the bintree "node" is already part of a tree, then an assert will fire.
  21. *
  22. *---------------------------------------------------------------
  23. * Author : Graeme McKerrell
  24. * Created On : Wed Jan 28 10:05:11 2004
  25. * Status : TESTED
  26. *---------------------------------------------------------------
  27. * HISTORY
  28. * 7-Dec-2004 Graeme McKerrell
  29. * Renamed to the "lub_" namespace
  30. * 5-May-2004 Graeme McKerrell
  31. * updates following review
  32. * 2-Mar-2004 Graeme McKerrell
  33. * fixed so that the insertion order is correct
  34. * 9-Feb-2004 Graeme McKerrell
  35. * updated to use the new getkey prototype and new node, key ordering
  36. * 28-Jan-2004 Graeme McKerrell
  37. * Initial version
  38. *---------------------------------------------------------------
  39. * Copyright (C) 2004 3Com Corporation. All Rights Reserved.
  40. **************************************************************** */
  41. #include <assert.h>
  42. #include "private.h"
  43. /*--------------------------------------------------------- */
  44. int lub_bintree_insert(lub_bintree_t * this, void *clientnode)
  45. {
  46. int result = -1;
  47. lub_bintree_node_t *new;
  48. lub_bintree_key_t key;
  49. assert(clientnode);
  50. if (NULL != clientnode) {
  51. /* obtain the control block from the clientnode */
  52. new = lub_bintree_getnode(this, clientnode);
  53. /* check this node is not currently in another tree */
  54. assert(new->left == NULL);
  55. assert(new->right == NULL);
  56. /* add this node to the splay tree */
  57. /* Insert "node" into the tree , unless it's already there. */
  58. if (NULL == this->root) {
  59. this->root = new;
  60. this->root->left = this->root->right = NULL;
  61. result = 0;
  62. } else {
  63. int comp;
  64. /* get a key from the node */
  65. this->getkeyFn(clientnode, &key);
  66. /* do the biz */
  67. this->root = lub_bintree_splay(this, this->root, &key);
  68. /*
  69. * compare the new key with the detail found
  70. * in the tree
  71. */
  72. comp = lub_bintree_compare(this, this->root, &key);
  73. if (comp > 0) {
  74. new->left = this->root->left;
  75. new->right = this->root;
  76. this->root->left = NULL;
  77. result = 0;
  78. } else if (comp < 0) {
  79. new->right = this->root->right;
  80. new->left = this->root;
  81. this->root->right = NULL;
  82. result = 0;
  83. } else {
  84. /* We get here if it's already in the tree */
  85. }
  86. }
  87. if (0 == result) {
  88. /* update the tree root */
  89. this->root = new;
  90. }
  91. }
  92. /* added OK */
  93. return result;
  94. }
  95. /*--------------------------------------------------------- */