1
0

bintree_findnext.c 2.1 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667
  1. /*********************** -*- Mode: C -*- ***********************
  2. * File : bintree_findnext.c
  3. *---------------------------------------------------------------
  4. * Description
  5. * ===========
  6. * This operation searches the specified "tree" for a "clientnode" which is
  7. * the one which logically follows the specified "key"
  8. *
  9. * A "clientnode" with the specified "key" doesn't need to be in the tree.
  10. *
  11. * tree - the "tree" instance to invoke this operation upon
  12. * key - the "key" to search with
  13. *
  14. * RETURNS
  15. * "clientnode" instance or NULL if no node is found.
  16. *---------------------------------------------------------------
  17. * Author : Graeme McKerrell
  18. * Created On : Wed Jan 28 10:32:28 2004
  19. * Status : TESTED
  20. *---------------------------------------------------------------
  21. * HISTORY
  22. * 7-Dec-2004 Graeme McKerrell
  23. * Renamed to the "lub_" namespace
  24. * 5-May-2004 Graeme McKerrell
  25. * updates following review
  26. * 27-Feb-2004 Graeme McKerrell
  27. * Fixed to account for empty tree
  28. * 9-Feb-2004 Graeme McKerrell
  29. * updated to use new node,key comparison ordering
  30. * 28-Jan-2004 Graeme McKerrell
  31. * Initial version
  32. *---------------------------------------------------------------
  33. * Copyright (C) 2004 3Com Corporation. All Rights Reserved.
  34. **************************************************************** */
  35. #include "private.h"
  36. /*--------------------------------------------------------- */
  37. void *lub_bintree_findnext(lub_bintree_t * this, const void *clientkey)
  38. {
  39. lub_bintree_node_t *t = this->root;
  40. int comp;
  41. /*
  42. * have a look for a direct match
  43. */
  44. t = this->root = lub_bintree_splay(this, t, clientkey);
  45. if (NULL != t) {
  46. /* now look at what we have got */
  47. comp = lub_bintree_compare(this, t, clientkey);
  48. if (comp <= 0) {
  49. /*
  50. * time to fiddle with the right hand side of the tree
  51. * we need the closest node from the right hand side
  52. */
  53. t = t->right =
  54. lub_bintree_splay(this, t->right, clientkey);
  55. }
  56. }
  57. if (NULL == t) {
  58. return NULL;
  59. } else {
  60. return lub_bintree_getclientnode(this, t);
  61. }
  62. }
  63. /*--------------------------------------------------------- */